Scala Parsers and Implicit Ordered Conversion

Question

The following snippet of parser combinations demonstrates the goal of summarizing binary comparison operations such as > using Ordered[T] . Gt seems to achieve this at the AST level, but I am having problems expanding this concept.

The intGt parser intGt , but is it possible to generalize it around Ordered[T] in such a way that we do not need to write a second parser for floatGt (and, therefore, one for all supported ordered types * all supported operating systems - no thanks).

 object DSL extends JavaTokenParsers { // AST abstract class Expr[+T] { def eval: T } case class Literal[T](t: T) extends Expr[T] { def eval = t } case class Gt[T <% Ordered[T]](l: Expr[T], r: Expr[T]) extends Expr[Boolean] { def eval = l.eval > r.eval // view-bound implicitly wraps eval result as Ordered[T] } // Parsers lazy val intExpr: Parser[Expr[Int]] = wholeNumber ^^ { case x => Literal(x.toInt) } lazy val floatExpr: Parser[Expr[Float]] = decimalNumber ^^ { case x => Literal(x.toFloat) } lazy val intGt: Parser[Expr[Boolean]] = intExpr ~ (">" ~> intExpr) ^^ { case l ~ r => Gt(l, r) } } 

Answer 1

I tried to play, and this is the best I could think of in the time I had:

 import scala.util.parsing.combinator.JavaTokenParsers object DSL extends JavaTokenParsers { // AST abstract class Expr[+T] { def eval: T } case class Literal[T](t: T) extends Expr[T] { def eval = t } case class BinOp[T,U]( val l : Expr[T], val r : Expr[T], val evalOp : (T, T) => U) extends Expr[U] { def eval = evalOp(l.eval, r.eval) } case class OrderOp[O <% Ordered[O]](symbol : String, op : (O, O) => Boolean) def gtOp[O <% Ordered[O]] = OrderOp[O](">", _ > _) def gteOp[O <% Ordered[O]] = OrderOp[O](">=", _ >= _) def ltOp[O <% Ordered[O]] = OrderOp[O]("<", _ < _) def lteOp[O <% Ordered[O]] = OrderOp[O]("<=", _ <= _) def eqOp[O <% Ordered[O]] = OrderOp[O]("==", _.compareTo(_) == 0) def ops[O <% Ordered[O]] = Seq(gtOp[O], gteOp[O], ltOp[O], lteOp[O], eqOp[O]) def orderExpr[O <% Ordered[O]]( subExpr : Parser[Expr[O]], orderOp : OrderOp[O]) : Parser[Expr[Boolean]] = subExpr ~ (orderOp.symbol ~> subExpr) ^^ { case l ~ r => BinOp(l, r, orderOp.op) } // Parsers lazy val intExpr: Parser[Expr[Int]] = wholeNumber ^^ { case x => Literal(x.toInt) } lazy val floatExpr: Parser[Expr[Float]] = decimalNumber ^^ { case x => Literal(x.toFloat) } lazy val intOrderOps : Parser[Expr[Boolean]] = ops[Int].map(orderExpr(intExpr, _)).reduce(_ | _) lazy val floatOrderOps : Parser[Expr[Boolean]] = ops[Float].map(orderExpr(floatExpr, _)).reduce(_ | _) } 

Essentially, I defined a class of small classes, OrderOp , that binds a string representing the ordering operation of the function that will evaluate this operation. Then I defined an ops function that can create the Seq[OrderOp] all such ordering operations for a given type of Orderable . These operations can then be converted to parsers using orderExpr , which takes a syntax parser and operation. This is displayed for all ordering operations for your int and float types.

Some problems with this approach:

• In the AST type hierarchy, there is only one node type for all binary operations. This is not a problem if everything you ever do evaluates, but if you ever wanted to perform rewriting operations (for example, excluding obvious tautologies or contradictions), then there is not enough information for the current definition of BinOp.
• I still needed to display orderExpr for each individual type. There may be a way to fix this, but I did not have enough time.
• orderExpr expects the left and right subexpressions to be parsed with the same parser.