CODEWITHSUNDEEP
parsingscalaimplicit-conversion
drekbour
drekbour

Reputation: 3081

Scala Parsers and implicit Ordered conversion

The following snippet of parser combinator demonstrates am aim of generalising binary comparison ops like > by using Ordered[T]. Gt seems to accomplish this at the AST level but I'm having trouble extending this concept.

The intGt parser works but is it possible to generalise this around Ordered[T] such that we don't need to write a second parser for floatGt (and hence one for all supported orderable types * all supported ops - 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) }
}

Upvotes: 4

Views: 168

Answers (1)

iainmcgin
iainmcgin

Reputation: 2751

I tried playing around and this is the best I could come up with 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 small case class OrderOp that relates a string representing an ordering operation to a function which will evaluate that operation. I then defined a function ops capable of creating a Seq[OrderOp] of all such ordering operations for a given Orderable type. These operations can then be turned into parsers using orderExpr, which takes the sub expression parser and the operation. This is mapped over all the ordering operations for your int and float types.

Some issues with this approach:

  • There is only one node type in the AST type hierarchy for all binary operations. This isn't a problem if all you are ever doing is evaluating, but if you ever wanted to do rewriting operations (eliminating obvious tautologies or contradictions, for instance) then there is insufficient information to do this with the current definition of BinOp.
  • I still needed to map orderExpr for each distinct type. There may be a way to fix this, but I ran out of time.
  • orderExpr expects the left and right subexpressions to be parsed with the same parser.

Upvotes: 1

Related Questions