Practicing Scala — Writing a basic boolean expression parser

I happened to research on how arbitrary boolean expressions can be parsed at runtime to compute true / false values. Since I wanted to implement this in Scala, I did some research and found this interesting nugget in StackOverflow. It was a way to idiomatically expressing the grammar in Scala. And then using the generated parser to parse the expression and finally you had to hand write the expression evaluation logic yourself. I was not comfortable with how the DSL was expressed and the use of custom Parsers. See the code snippet from that SO post

object ConditionParser extends JavaTokenParsers with PackratParsers {

  val booleanOperator : PackratParser[String] = literal("||") | literal("&&")
  val comparisonOperator : PackratParser[String] = literal("<=") | literal(">=") | literal("==") | literal("!=") | literal("<") | literal(">")
  val constant : PackratParser[Constant] = floatingPointNumber.^^ { x => Constant(x.toDouble) }
  val comparison : PackratParser[Comparison] = (comparisonOperator ~ constant) ^^ { case op ~ rhs => Comparison(op, rhs) }
  lazy val p1 : PackratParser[BooleanExpression] = booleanOperation | comparison
  val booleanOperation = (p1 ~ booleanOperator ~ p1) ^^ { case lhs ~ op ~ rhs => BooleanOperation(op, lhs, rhs) }
}

You have operations such as ^^ and ~ which does not clearly signify what that operator is supposed to do. At this point, I would prefer an API with simply has named methods for being able to understand the code better. THis also helps act as a form of documentation.

But this challenge also helped clarify a requirement. I just needed an expression parser that works with general Java style expressions, period. This scala based expression parser (simply called expression-parser)seems to fit the bill. I am however not sure of the popularity of this lib. So use at your own risk.

There is also FastParse which seems to balance out coding succinctness with expressivity. However in many cases where a good regex can express the matching constraint nicely, one is forced to express it in the custom DSL of fastparse. One would highly yearn to have the DSL look as close to a regex style matcher to the extent possible. From the link, here is a code snippet of what a fastparse parser builder would look like:

def parser[_: P] = P( ("hello" | "goodbye") ~ (" ".rep(1) ~ ("world" | "seattle")).? ~ End )

Can you guess what the equivalent regex would look like?

(hello|goodbye)\s+(world|seattle)?$

Duh!

So while being a capable parser, it would be awesome to be able to leverage the power of regex like DSL some more OR rather express it in named method syntax. For example even if we can’t setup our setup our scala DSL to be regex like, I find this fluent style more usable: (pseudo-syntax)

expr(lit("hello").or(lit("goodbye"))).and(lit("\s").min(1)).and(expr(lit("world").or(lit("seattle"))).min(0).max(1)).and(END)

Of course the reader may argue that this is verbose and potentially harder to read. But in this kind of a fluent style API, I would argue it is also self documenting to a good extent.

Since Scala is interoperable with Java libs, I decided to find some good general expression parsers in Java Land. There are definitely more options in Java. Let me list those out quickly:

• SPEL: Spring expression language
• MVEL: http://mvel.documentnode.com/
• JEP: Java expression parser
• JEXL: Java Expression Language

Just a note that JEP is not free product and you can use a limited trial for that lib. Other than that SPEL, MVN and JEXL are all fairly expressive and could fit the bill for a general expression parser.

This ends the search in terms of what lib can be used. But I also got curious on whether code can be handrolled for a simple boolean expression evaluator. Coincidentally I found a boolean expression parser problem listed in Leetcode. What’s nice about this problem is that simplifies the challenge to its essence and also clearly specifies the grammar. This helps in quickly focus on designing a boolean expression evaluator without getting stuck in the weeds of cleaning the input, parsing numbers etc and focus on creating the AST for the problem. The challenge here is to make the code as functional as possible using all the awesome Scala constructs such as List.head, List.tail etc instead of fighting with indexes as we do in Java collections.

So here is version 1 of the code. I use a lot of imperative programming constructs such as the while loop or declaring vars instead of vals.

The test expression is: |(&(t,f,t),!(t)) and the output is List(Or(And(Lit(t),Lit(f),Lit(t)),Not(Lit(t)))) Ignore the List since the parse method return a List of one expression. In effect the parsed expression looks great!

While there is some recursion, there are still a lot of imperative constructs such as the while loop and a bunch of vars . Typically in functional languages you want to use recursion and not while loop type constructs. So after more trying here is a much more functional version which does away with the while loop and is all recursion. Voila!

Awesome! No while loop and no vars! Getting the hang of functional programming and liking it…

Can we do better? Hmmm…

There is a weakness with the current solution. As the nesting of the operators get deeper the call stack for the recursive method call gets deeper. Which means there are situations it could throw a StackOverflow Error. There is the concept of tail recursion in Scala. As long as the recursive call to parse method is the last task in the method, scala can optimize it so that essentially only one stack frame is ever needed thus obviating a stack overflow error. Also don’t forget to add in the @tailrec annotation to the recursive method call. In case the method is not truly tail recursive, it will flag it with a compiler error.

One word of warning: some thought needs to be put in to covert a imperative program into a functional recursive one. And even more effort is needed to convert a standard functional recursive program into a tail recursive one. But once that is done, I can promise you it is worth the effort. Both the elegance of the program as well as the succinctness really shine through. So without further ado, here the tail recursive version of the boolean expression parser.

Hope you enjoyed taking the journey into functional scala with me.