Advertisement
Guest User

Untitled

a guest
Jun 24th, 2015
223
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Scala 7.69 KB | None | 0 0
  1. /**
  2.  * Example of using `CodeGraph` for a simple expression library.
  3.  */
  4. object Expressions {
  5.   import Exceptions._
  6.  
  7.   /** Node labels for expression graphs. */
  8.   object NodeLabels {
  9.     /** Base class for node labels in the expression graph. */
  10.     sealed abstract class ExprNodeLabel
  11.     /** Integer-valued graph-node. */
  12.     case class INT() extends ExprNodeLabel
  13.     /** Boolean-valued graph-node. */
  14.     case class BOOL() extends ExprNodeLabel
  15.   }
  16.  
  17.   /** Edge labels for expression graphs. */
  18.   object EdgeLabels {
  19.     import NodeLabels._
  20.  
  21.     /** Base class for edge labels in the expression graph. */
  22.     sealed abstract class ExprEdgeLabel
  23.     /** Load a constant `Int`. */
  24.     case class ConstInt(value: Int) extends ExprEdgeLabel with EdgeLabel.Nullary[INT]
  25.     /** Load a constant `Boolean`. */
  26.     case class ConstBool(value: Boolean) extends ExprEdgeLabel with EdgeLabel.Nullary[BOOL]
  27.     /** Integer addition. */
  28.     case object `add` extends ExprEdgeLabel with EdgeLabel.Binary[INT, INT, INT]
  29.     /** Integer subtraction. */
  30.     case object `sub` extends ExprEdgeLabel with EdgeLabel.Binary[INT, INT, INT]
  31.     /** Integer multiplication. */
  32.     case object `mul` extends ExprEdgeLabel with EdgeLabel.Binary[INT, INT, INT]
  33.     /** Integer division. */
  34.     case object `div` extends ExprEdgeLabel with EdgeLabel.Binary[INT, INT, INT]
  35.     /** Integer compares less than. */
  36.     case object `lt` extends ExprEdgeLabel with EdgeLabel.Binary[INT, INT, BOOL]
  37.     /** Integer compares greater than. */
  38.     case object `gt` extends ExprEdgeLabel with EdgeLabel.Binary[INT, INT, BOOL]
  39.     /** Integer compares equal. */
  40.     case object `equ` extends ExprEdgeLabel with EdgeLabel.Binary[INT, INT, BOOL]
  41.     /** Logical AND. */
  42.     case object `and` extends ExprEdgeLabel with EdgeLabel.Binary[BOOL, BOOL, BOOL]
  43.     /** Logical OR. */
  44.     case object `or` extends ExprEdgeLabel with EdgeLabel.Binary[BOOL, BOOL, BOOL]
  45.   }
  46.  
  47.   import NodeLabels._
  48.   import EdgeLabels._
  49.  
  50.   /**
  51.    * `CodeGraph` type representing expressions.
  52.    */
  53.   type ExpressionCodeGraph = CodeGraph[ExprNodeLabel, ExprEdgeLabel]
  54.  
  55.   /**
  56.    * Type-class supporting the promotion of constant literals to well-typed node names generated
  57.    * by nullary (zero-input) edges.
  58.    *
  59.    * The type `T` should be a primitive Scala type (i.e., `Int`),
  60.    * `NodeType` should be the corresponding node type (i.e., `INT`), and `EdgeType` should
  61.    * be the type of a nullary edge label that generates nodes of that type.
  62.    */
  63.   trait ConstEdge[T, NodeType <: ExprNodeLabel with Product, EdgeType <: ExprEdgeLabel with EdgeLabel.Nullary[NodeType]] {
  64.     def promote(value: T): EdgeType
  65.     def newNode: NodeName[NodeType]
  66.   }
  67.  
  68.   implicit def constIntEdge: ConstEdge[Int, INT, ConstInt] =
  69.     new ConstEdge[Int, INT, ConstInt] {
  70.       override def promote(value: Int): ConstInt = ConstInt(value)
  71.       override def newNode: NodeName[INT] = NodeName.fresh[INT](INT())
  72.     }
  73.  
  74.   implicit def constBoolEdge: ConstEdge[Boolean, BOOL, ConstBool] =
  75.     new ConstEdge[Boolean, BOOL, ConstBool] {
  76.       override def promote(value: Boolean): ConstBool = ConstBool(value)
  77.       override def newNode: NodeName[BOOL] = NodeName.fresh[BOOL](BOOL())
  78.     }
  79.  
  80.   /**
  81.    * A simple but helpful `CodeGraph` mutator that takes a constant of an arbitrary type
  82.    * and uses the [[ConstEdge]] typeclass to turn it into a well-typed CodeGraph node.
  83.    *
  84.    * This way we don't have to type a different constructor name (e.g., `ConstInt`) for
  85.    * every type of constant we wish to use.
  86.    */
  87.   def const[T, U <: ExprNodeLabel with Product, V <: ExprEdgeLabel with EdgeLabel.Nullary[U]](x: T)
  88.     (implicit pc: ConstEdge[T, U, V], cg: MutableCodeGraph[ExprNodeLabel, ExprEdgeLabel]): NodeName[U] = {
  89.       import cg.mutators._
  90.       val edgeLabel = pc.promote(x)
  91.       val node = pc.newNode
  92.       addNode(node)
  93.       addEdge(new CodeGraph.Edge[ExprEdgeLabel](edgeLabel, Seq(), Seq(node.key)))
  94.       node
  95.     }
  96.  
  97.   /**
  98.    * Fully evaluate an [[ExpressionCodeGraph]] and return the computed results.
  99.    * @param cg The [[ExpressionCodeGraph]] to evaluate.
  100.    * @param inputs The inputs to the CodeGraph.
  101.    * @return The computed results.
  102.    */
  103.   def evaluate(cg: ExpressionCodeGraph, inputs: Seq[Any]): Seq[Any] = {
  104.     import CodeGraphOps._
  105.     var env: Map[CodeGraph.NodeKey, Any] = cg.inputs.zip(inputs).toMap
  106.     for (edgeKey <- cg.topSort) {
  107.       val edge = cg.edge(edgeKey).head
  108.       def args = edge.args.map(x => env.getOrElse(x, throw new RuntimeException(s"Node not evaluated: $x")))
  109.  
  110.       def arg0[T] = args(0).asInstanceOf[T]
  111.       def arg1[T] = args(1).asInstanceOf[T]
  112.  
  113.       def results = edge.label match {
  114.         case ConstInt(x) => Seq(x)
  115.         case ConstBool(x) => Seq(x)
  116.         case `add` => Seq(arg0[Integer] + arg1[Integer])
  117.         case `sub` => Seq(arg0[Integer] - arg1[Integer])
  118.         case `mul` => Seq(arg0[Integer] * arg1[Integer])
  119.         case `div` => Seq(arg0[Integer] / arg1[Integer])
  120.         case `lt` => Seq(arg0[Integer] < arg1[Integer])
  121.         case `gt` => Seq(arg0[Integer] > arg1[Integer])
  122.         case `equ` => Seq(arg0[Integer] == arg1[Integer])
  123.         case `and` => Seq(arg0[Boolean] && arg1[Boolean])
  124.         case `or` => Seq(arg0[Boolean] || arg1[Boolean])
  125.       }
  126.       env = env ++ edge.results.zip(results).toMap
  127.     }
  128.     cg.outputs.map(x => env.getOrElse(x, throw InvalidNodeKeyException(x)))
  129.   }
  130.  
  131.   /**
  132.    * Specialized [[CodeGraphBuilder]] supporting extended syntax for expressions.
  133.    */
  134.   class ExpressionGraphBuilder extends CodeGraphBuilder[ExprNodeLabel, ExprEdgeLabel] {
  135.     import cg.mutators._
  136.  
  137.     implicit class IntegerOperations(n: NodeName[INT]) {
  138.       def +(m: NodeName[INT]): NodeName[INT] = add $(n, m)
  139.       def -(m: NodeName[INT]): NodeName[INT] = sub $(n, m)
  140.       def *(m: NodeName[INT]): NodeName[INT] = mul $(n, m)
  141.       def /(m: NodeName[INT]): NodeName[INT] = div $(n, m)
  142.       def <(m: NodeName[INT]): NodeName[BOOL] = lt $(n, m)
  143.       def >(m: NodeName[INT]): NodeName[BOOL] = gt $(n, m)
  144.       def ===(m: NodeName[INT]): NodeName[BOOL] = equ $(n, m)
  145.     }
  146.  
  147.     implicit class BooleanOperations(n: NodeName[BOOL]) {
  148.       def &&(m: NodeName[BOOL]): NodeName[BOOL] = and $(n, m)
  149.       def ||(m: NodeName[BOOL]): NodeName[BOOL] = or $(n, m)
  150.     }
  151.  
  152.     // Automatic constant promotion
  153.     implicit def toConst[T, U <: ExprNodeLabel with Product, V <: ExprEdgeLabel with EdgeLabel.Nullary[U]]
  154.       (value: T)(implicit ct: ConstEdge[T, U, V]): NodeName[U] =
  155.         const(value)
  156.   }
  157.  
  158.   // Simple expression
  159.   object simpleExprCodeGraph extends ExpressionGraphBuilder {
  160.     import cg.mutators._
  161.  
  162.     val (x, y) = input(INT, INT)
  163.  
  164.     val sum = x + y
  165.     val prod = x * y
  166.     val prodMinusSum = prod - sum
  167.     val resultGt100 = prodMinusSum > 100
  168.  
  169.     output(prodMinusSum, resultGt100)
  170.   }
  171.  
  172.   // Evaluate a polynomial
  173.   case class PolynomialGraph(coeffs: Seq[Int]) extends ExpressionGraphBuilder {
  174.     import cg.mutators._
  175.  
  176.     val x = input(INT)
  177.     var r = const(coeffs.head)
  178.     for (a <- coeffs.tail) {
  179.       r = (r * x) + a
  180.     }
  181.     output(r)
  182.   }
  183. }
  184.  
  185.  
  186. ///////////
  187.  
  188.  
  189. class ExpressionSpec extends Specification {
  190.   import Expressions._
  191.  
  192.   "simpleExprCodeGraph" should {
  193.     "evaluate correctly" in {
  194.       evaluate(simpleExprCodeGraph, Seq(10, 20)) must_== Seq(170, true)
  195.       evaluate(simpleExprCodeGraph, Seq(1, 2)) must_== Seq(-1, false)
  196.     }
  197.   }
  198.  
  199.   "HornerCodeGraph" should {
  200.     val cg3 = PolynomialGraph(Seq(1, 2, 3))
  201.     val cg5 = PolynomialGraph(Seq(2, 4, 6, 8, 10))
  202.  
  203.     "evaluate correctly" in {
  204.       evaluate(cg3, Seq(10)) must_== Seq(3 + 2*10 + 1*100)
  205.       evaluate(cg5, Seq(10)) must_== Seq(10 + 8*10 + 6*100 + 4*1000 + 2*10000)
  206.     }
  207.   }
  208.  
  209. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement