External DSLs made easy with Scala Parser Combinators

External DSLs are hard since implementing them involves reinventing most of the mechanisms found in a general purpose language. Designing internal DSLs are equally hard, more so in a statically typed language. Dynamically typed languages like Ruby offer strong meta-programming facilities, which help in implementing internal DSLs. But metaprogramming in Ruby is still considered elitist by many, and is not an art mastered by programmers at large.

Parser combinators offer a unique value here. They allow programmers to write executable grammars, in the sense that designing and implementing a DSL is almost equivalent to writing the EBNF notations in the syntax of the native language. So what really are parser combinators and what kind of language support do we need to implement parser combinator libraries ? Here is how Gilad Bracha describes them ..

The basic idea is to view the operators of BNF (or regular expressions for that matter) as methods that operate on objects representing productions of a grammar. Each such object is a parser that accepts the language specified by a particular production. The results of the method invocations are also such parsers. The operations are called combinators for rather esoteric technical reasons (and to intimidate unwashed illiterates wherever they might lurk).

Combinators have their theoretical underpinnings in functional programming. A parser combinator is a higher order function that accepts a parser and applies transformation functions to generate more complex parsers. Hence parser combinators are easily implemented in languages that have strong support for functional programming. In Scala, parsers are implemented as monads - hence defining combinators for parsers are just monadic transformations implementing sequencing, alternation or any other composition operations.

This post is not an introductory material on parser combinators or their implementations in Scala. Here I would like to narrate my experience in designing an external DSL for a financial application using the parser combinator library of Scala. In one of my earlier posts, I had talked about monads as abstractions for containers and computations. Parser combinator implementation in Scala is a great example of the power of monads in evolving a DSL.

In developing a financial application involving securities trade and settlement processing, we've been using XML as the DSL for getting buy/sell orders from client, trade/execution information from the exchange and settlement information from clearing agencies. Needless to say, XML processing is one of the key functions that pervade our codebase. In one of my very early posts, I had ranted about executable XMLs (aka Lisp) and had considered using Scheme as the DSL for securities trade processing operations. SISC offers a fully compliant Scheme implementation on top of the JVM, still all ideas fell through the cracks of enterprise decision making deliberations. After a fairly long time, I have found out another alternative - DSLs designed using Scala parser combinators ..

• easy to implement


• as concise as your EBNF productions


• algebraic data types to generate ASTs and


• powerful pattern matching techniques to inspect them.

Add to them the fact that I can have the entire stack running on the JVM, with Java objects still running the show at the backend. This imples that I do not have to reimplement my current Java application. I can just plug in the DSL and have the parser cook up my Java objects at the AST level. And that is exactly what I plan to do here.

Here is a sample DSL (simplified for brevity) for accepting client orders to buy/sell equities ..

(buy 100 IBM shares at max USD 45, sell 50 CISCO shares at min USD 25, buy 100 Google shares at max USD 800) for trading_account "SSS1234"

The equivalent XML will be too verbose, too painful for the eyes, and will definitely need more extraneous infrastructure over native language support for meaningful processing.

and here is the Scala parser for recognizing the DSL ..

import scala.util.parsing.combinator.syntactical._
object OrderDSL extends StandardTokenParsers {
  lexical.delimiters ++= List("(", ")", ",")
  lexical.reserved += ("buy", "sell", "shares", "at", "max", "min", "for", "trading", "account")

  def instr = trans ~ account_spec

  def trans = "(" ~> repsep(trans_spec, ",") <~ ")"

  def trans_spec = buy_sell ~ buy_sell_instr

  def account_spec = "for" ~> "trading" ~> "account" ~> stringLit

  def buy_sell = ("buy" | "sell")

  def buy_sell_instr = security_spec ~ price_spec

  def security_spec = numericLit ~ ident ~ "shares"

  def price_spec = "at" ~ ("min" | "max") ~ numericLit
}


This is really all that I need to parse my DSL. Really. And the most interesting part is that, the methods above have almost a one-to-one correspondence to EBNF production rules, as I would write them in a natural language. All the heavy lifting of lexical analysis and parsing are taken care of by the Scala parser combinator library.

The combinators used in the above example look like operators, though, actually they are Scala methods. Every combinator method works on a portion of the input, parses it and may optionally pass on the remaining part to the next combinator in the chain. e.g. the sequencing combinator ~ composes two parsers sequentially. In the above example, for the first production, trans ~ account_spec succeeds only if trans succeeds and then account_spec succeeds on the portion of the input left by trans. And the final result is another parser on which an optional function application combinator (^^) can work, applying the function on the result of the sequencing combinator.

Once I have the basic parsing productions defined in Scala, I can work towards building my abstract syntax tree (AST), which will accumulate necessary parsed information and provide me the model of the abstraction that the DSL embodies. This model depends on how I would like to process the abstraction defined by the language, and may vary based on the requirements of the backend system which receives the AST. In the above example, I may like to abstract the client order details into a POJO and pass on to the database layer for persistence. Alternatively I may like to pass on the AST to the pretty printer function, which generates an HTML for confirming the client order. Hence, it is always better if we can decouple the two concerns - recognising the language and processing the information to generate the AST. Gilad Bracha talks about similar decoupling in Newspeak using a combination of closures and inheritance. But Newspeak is a dynamic language and I am not sure if this decoupling can be achieved in a statically typed language like Scala.

Hence, in Scala it is not possible to ensure that multiple back end systems share the same grammar instance while working on different models of the AST. Scala offers combinators to plug in function application on the above production rules, which get executed on successful parsing of the rule. This is achieved by the function application combinator (^^) provided by the Scala library that enables plugging in of processing code towards evolution of the AST.

Depending on what processing I would like to do with the AST, I can choose an appropriate data structure. If I choose to perform heavy recursive traversals, tree manipulations and node annotations, the AST can be modeled as Scala algebraic data structures, which can then be inspected using pattern matching techniques. In the target application that I propose to use this, the backend contains the POJO based domain model and I would like to generate domain objects from ASTs to be used for transparent persistence in the data layer. Hence I choose to map the AST with my domain model for processing client orders.

Here are some Java classes (simplified for brevity) for abstracting a client order ..

// ClientOrder.java
public class ClientOrder {
  public enum BuySell {
    BUY,
    SELL
  }
  private String accountNo;

  private List<LineItem> lineItems = new ArrayList<LineItem>();

  // constructors, getters ..
}

// LineItem.java
public class LineItem {
  private final String security;
  private final int quantity;
  private final ClientOrder.BuySell bs;
  private final int price;

  public LineItem(String security, int quantity, ClientOrder.BuySell bs, int price) {
    this.security = security;
    this.quantity = quantity;
    this.bs = bs;
    this.price = price;
  }
  //..
  //..
}


I can plug in function application combinators with the production rules and have my AST model a ClientOrder. Remember I am plugging in the DSL to a system based on POJOs - hence I need to do some conversions between Java and Scala collections. But the final AST is a Java object to be consumed by the existing backend that does client order processing.

import scala.util.parsing.combinator.syntactical._
import org.dg.biz.ClientOrder
object OrderDSL extends StandardTokenParsers {

  def scala2JavaList(sl: List[LineItem]): java.util.List[LineItem] = {
    var jl = new java.util.ArrayList[LineItem]()
    sl.foreach(jl.add(_))
    jl
  }

  lexical.delimiters ++= List("(", ")", ",")
  lexical.reserved += ("buy", "sell", "shares", "at", "max", "min", "for", "trading", "account")

  def instr: Parser[ClientOrder] =
    trans ~ account_spec ^^ { case t ~ a => new ClientOrder(scala2JavaList(t), a) }

  def trans: Parser[List[LineItem]] =
    "(" ~> repsep(trans_spec, ",") <~ ")" ^^ { (ts: List[LineItem]) => ts }

  def trans_spec: Parser[LineItem] =
    buy_sell ~ buy_sell_instr ^^ { case bs ~ bsi => new LineItem(bsi._1._2, bsi._1._1, bs, bsi._2) }

  def account_spec =
    "for" ~> "trading" ~> "account" ~> stringLit ^^ {case s => s}

  def buy_sell: Parser[ClientOrder.BuySell] =
    ("buy" | "sell") ^^ { case "buy" => ClientOrder.BuySell.BUY
                          case "sell" => ClientOrder.BuySell.SELL }

  def buy_sell_instr: Parser[((Int, String), Int)] =
    security_spec ~ price_spec ^^ { case s ~ p => (s, p) }

  def security_spec: Parser[(Int, String)] =
    numericLit ~ ident ~ "shares" ^^ { case n ~ a ~ "shares" => (n.toInt, a) }

  def price_spec: Parser[Int] =
    "at" ~ ("min" | "max") ~ numericLit ^^ { case "at" ~ s ~ n => n.toInt }
}


Here is a function within OrderDSL that uses the AST model ..

def doMatch() {
  val dsl =
    "(buy 100 IBM shares at max 45, sell 40 Sun shares at min 24,buy 25 CISCO shares at max 56) for trading account \"A1234\""

  instr(new lexical.Scanner(dsl)) match {
    case Success(ord, _) => processOrder(ord) // ord is a ClientOrder
    case Failure(msg, _) => println(msg)
    case Error(msg, _) => println(msg)
  }
}


The basic idea of polyglotism is to harness the power of multiple languages in their respective strength areas. Languages like Scala, despite being statically typed offer lots of flexibilities and conciseness. Offering the strong features of both OO and functional paradigms, Scala shines in providing parser combinator libraries straight out of the box. And the above example shows how easy it is to get a DSL working if we use the power of combinators. And the best part is that you can still use your existing Java objects to do the heavy backend lifting - truly it is the single platform of JVM that unifies the diversity of multiple programming languages.

Monads - Another way to abstract computations in Scala

You can view monads as containers or as computations. Isn't this confusing enough ?

To a programmer, the biggest scare with the name "monad" is the fact that it originates from the constructs of category theory and the rich mathematics that goes along with it. The simplest way to make an idea of monads is to look at applications and examples that use them to solve real life problems. Monads have been described as models of computation, code transformers, state transformers and what not. But unfortunately for someone uninitiated to monadic programming, and indoctrinated with the tenets of OO programming and design patterns, all these incarnations make little sense. Sometime back, after listening to a long dissertation on monads, I asked myself .. what the heck do I need monads for ? I can very well do the same thing with a Composite Command design pattern that serializes execution of its composing commands.

I have been playing around with Scala for some time now. Scala is a multiparadigm language. The nice thing about Scala is that you never feel out of the way writing either imperative or functional code. On one hand, you have the re-assignable vars, explicit IOs, side-effecting constructs. And on the other, you can write pure clean functional code without any side-effecting features. Coming from a Java / C++ background and seeing enough of OO over the last decade, my interest is in exploring the functional features that the language has to offer. Ok, I know you will refer me to the backyards of Haskell or OCamL as more pure functional languages. But hey, I need to have my appplication deployed on the JVM, and don't ask me why ..

This post is all about my exposure to monads in Scala. This is not meant to be a tutorial on monads, considered by some, to be the stairway to the heaven of Haskell. It looks at monads purely as a means to design complex computational abstractions using the phenomenal powers of closures and higher order functions in Scala. Functional programming is all about referential transparency, where you treat your functions algebraically, evaluating them in no specific order. Monads allow ordered computation within FP that allows us to model sequencing of actions in a nice structured form, somewhat like a DSL. And the greatest power comes with the ability to compose monads that serve different purposes, into extensible abstractions within an application.

This sequencing and threading of actions by a monad is done by the language compiler that does the transformation through the magic of closures. Scala provides some built-in support of monads, and offers the machinery to design your own monadic operations.

Consider the following Scala code fragment, which looks quite intuitive to anyone familiar with programming in a high level language :

for {
  x <- List(1, 2)
}
yield(x + 2)


The code snippet uses Scala for-comprehensions to perform a "+ 2" operation on individual elements of a list of integers. Scala for-comprehension, being a syntactic sugar, the compiler does the heavy lifting and converts it to a more traditional map operation ..

List(1, 2) map {x => x + 2}


Quite trivial .. huh ! But how does it relate to monads ? Hang on ..

Now how about this ?

val first = List(1, 2)
val next = List(8, 9)

for {
  i <- first
  j <- next
}
yield(i * j)


I have added an extra step of computation in the sequence, that gets resolved as ..

first flatMap {
  f => next map {
    n => f * n
  }
}


and the last one ..

val first = List(1, 2)
val next = List(8, 9)
val last = List("ab", "cde", "fghi")

for {
  i <- first
  j <- next
  k <- last
}
yield(i * j * k.length)


that transforms to :

first flatMap {
  i => next flatMap {
    j => last map {
      k => i * j * k.length
    }
  }
}


The key abstraction is the flatMap, which binds the computation through chaining. Each invocation of flatMap returns the same data structure type (but of different value), that serves as the input to the next command in chain. In the above snippet, flatMap takes as input a closure (SomeType) => List[AnotherType] and returns a List[AnotherType]. The important point to note is that all flatMaps take the same closure type as input and return the same type as output. This is what "binds" the computation thread - every item of the sequence in the for-comprehension has to honor this same type constraint.

The above is an example of the List monad in Scala. Lists support filtering, and so does the List monad. In the for-comprehension, we can also filter data items through the if-guards :

for {
  i <- 1 until n
  j <- 1 until (i-1)
  if isPrime(i+j)
}
yield (i, j)


Consider another different computation involving sequencing of operations (not of the List type though) from an example which I mentioned in my previous Scala post :

case class Order(lineItem: Option[LineItem])
case class LineItem(product: Option[Product])
case class Product(name: String)

for {
  order <- maybeOrder
  lineItem <- order.lineItem
  product <- lineItem.product
}
yield product.name


This gets me the product name from the chain of order, lineItem and product. One more sequencing of operations, and the for-comprehension gets converted to :

maybeOrder flatMap {
  order => order.lineItem flatMap {
    lineItem => lineItem.product map {
      product => product.name
    }
  }
}


flatMap again!

Once again we have the magic of flatMap binding the thread of computation. And similar to the earlier example of the List monad, every flatMap in the entire thread is homogenously typed - input type being (T => Option[U]) and the output type (Option[U]). The types participating in this sequence of computation is the Maybe monad type, modeled as Option[T] in Scala.

What is the commonality of the above two examples ?

• It is the sequencing of operations, that leads to the evolution of higher order functional abstractions.

And what is the variability part ?

• It is the types that actually take part in the operations. In the first case, it is the operations on List type that gets chained. While in the second case, it is the Option type.

And what is the secret sauce ?

• The flatMap (aka bind in Haskell) operation, which works orthogonally across types and serves as the generic binder of the sequence of actions.

In the above examples, the two monad types discussed, List[T] and Option[T] are container types, if we consider the latter to be a degenerate version with only 2 elements. However, monads can be designed to be of other types as well e.g. those that work on state manipulation or on doing IO. And for these monads, possibly it is more intuitive to comprehend monads as computations. I hope to provide examples of some real life applications of State and IO monads using Scala in a future post.

Whole is bigger than the sum of its parts

As I mentioned earlier, the biggest power of monads is the ability to combine diverse monadic operations to design modular and extensible code. The following snippet gives an example that combines a List monad and Maybe monad within the same for-comprehension block :

val list = List("India", "Japan", "France", "Russia")
val capitals =
  Map("India" -> "New Delhi", "Japan" -> "Tokyo", "France" -> "Paris")

for {
  i <- list
  j <- capitals get(i) orElse(Some("None"))
}
yield(j)


The first operation of the sequence is one on a List monad, while the next one is on a Maybe monad. The syntactic sugar of the for-comprehensions abstracts the details nicely enough for the user, who is completely oblivious of the underlying machinery of binding monads. Here is what comes up after the code transformation :

list flatMap {
  i => capitals.get(i).orElse(Some("None")) map {
    j => j
  }
}


Developing modular software is all about working at the right level of abstraction. And monads offer yet another machinery to mix and match the right abstractions within your codebase. Consider adding the power of monads to your toolbox - they certainly are one of the potent design patterns that you will ever need.

Are you fully using your Static Typing ?

Back in 2005 in an LtU discussion on Dynamic vs. Static Typing, Anton van Straaten had this post ..

Here's a nice bit of Java code I came across (here):

if ((value != null) && !returnedClass().isAssignableFrom(value.getClass())) {
    throw new IllegalArgumentException("Received value is not a [" +
       returnedClass().getName() + "] but [" + value.getClass() + "]");
}


This is from a piece of code that's trying very, very hard to avoid the need for the definition of boilerplate classes when persisting classes representing enumeration types to a SQL database.

This code is actually doing a kind of dynamic typechecking, illustrating the following generalization of Greenspun's 10th Law: "any sufficiently complicated program in a statically-typechecked language contains an ad-hoc, informally-specified bug-ridden slow implementation of a dynamically-checked language." ;)

Today's good Java frameworks use reflection quite sparingly and responsibly. Using Java generics, these frameworks allow compile time type checking for cases which would earlier have to be implemented using a slow and bug ridden simulation of runtime type checking. Guice and EasyMock stand out as two frameworks I have been using that have used the power of generics to implement extraordinary typesafety.

I really like the way small interface-heavy APIs of Guice enforce compile time type-safety.

Have a look at this piece of code, which binds an implementation SpecialServiceImpl to the interface Service using Guice Binder.

public class MyModule implements Module {
    public void configure(Binder binder) {
        binder.bind(Service.class)
              .to(SpecialServiceImpl.class)
              .in(Scopes.SINGLETON);
    }
}


Given the fact that DI frameworks are in the business of injecting implementations to objects dynamically, it may seem that the "implements" relationship between Service and SpecialServiceImpl is done during runtime. Thanks to Java generics, every bit of type checking is done during compile time.

A peek at the source code of Guice reveals that BinderImpl.bind() returns BindingBuilderImpl<T> ..

public <T> BindingBuilderImpl<T> bind(Class<T> clazz) {
    return bind(Key.get(clazz));
}


and BindingBuilderImpl<T>.to() takes as input Class<? extends T> - the bound on the wild card enforces the above "implements" relationship as part of compile time type checking of the arguments ..

public ScopedBindingBuilder to(Class<? extends T> implementation) {
    return to(TypeLiteral.get(implementation));
}


In comparison to Guice, Spring makes much heavier use of reflection, which, I think, is, kind of expected, from a pre-generics framework. Spring's implementation has lots of code similar to

// Check if required type matches the type of the actual bean instance.
if (requiredType != null && bean != null &&
      !requiredType.isAssignableFrom(bean.getClass())) {
    throw new BeanNotOfRequiredTypeException(name, requiredType, bean.getClass());
}


that does quite a bit of juggling with dynamic type checking at runtime.

Coming back to the above post by Anton, yes, the kind of runtime type checking exists in lots of popular Java frameworks, even today. And this is where frameworks like Guice and EasyMock really shine with their strongly typed API sets that make you feel more secure within the confines of your IDE and refactoring abilities.

The Morale

When you are programming in a statically typed language, use appropriate language features to make most of your type checking at compile time. This way, before you hit the run button, you can be assured that your code is well-formed within the bounds of the type system. And you have the power of easier refactoring and cleaner evolution of your codebase.

Maybe Scala

Working with languages that grow organically with your programs is real fun. You can simply visualize the whole program as a living organism evolving dynamically in front of you. Just fire up your REPL and see for yourself how the malleable syntactic structures of the language grow in front of your eyes, alongside your program. Whether this is through Lisp macros or Ruby meta-programming or Scala control structures, the secret sauce is in the ability to implement more and more powerful abstractions within the language. But what makes one language shine more compared to another is the ability to combine abstractions leading to more powerful syntactic structures.

Recently people have been talking about the Maybe monad and its myriads of implementation possibilities in Ruby. Because of its dynamic nature and powerful meta-programming facilities, Ruby allows you to write this ..

@phone = Location.find(:first, ...elided... ).andand.phone


Here andand is an abstraction of the Maybe monad that you can seamlessly compose with core Ruby syntax structures, effectively growing the Ruby language. Now, compare this with the Null Object design pattern in Java and C++, which is typically used in those languages to write null safe code. Abstractions like Null Object pattern encapsulate null handling logic, but do not relieve programmers from writing repetitive code structures - you need to have a Null Object defined for each of your abstractions!

I have been working with Scala in recent times and really enjoying every bit of it. Professionally I belong to the Java/JVM community, and the very fact that Scala is a language for the JVM has made it easier for me. After working for a long time in enterprise projects, I have also been affiliated to the statically typed languages. I always believed that static encoding of type information on your values serve as the first level of unit testing, constraining your data to the bounds of the declared type, as early as the compile time. However, at times with Java, I also felt that complete static typing annotations adds to the visual complexity in reading a piece of code. Now working in Scala made me realize that static typing is not necessarily a cognitive burden in programming - a good type inferencing engine takes away most of the drudgery of explicit type annotations of your values.

Enough of Scala virtues, let's get going with the main topic .. Scala's Maybe monad, it's marriage to for-comprehensions and it's implicit extensibility ..

Scala offers the Option[T] datatype as its implementation of the monad. Suppose you have the following classes ..

case class Order(lineItem: Option[LineItem])
case class LineItem(product: Option[Product])
case class Product(name: String)


and you would like to chain accessors and find out the name of the Product corresponding to a LineItem of an Order. Without drudging through boilerplate null-checkers and Baton Carriers, Scala's Option[T] datatype and for-comprehensions offer a nice way of calling names ..

def productName(maybeOrder: Option[Order]): Option[String] = {
    for (val order <- maybeOrder;
         val lineItem <- order.lineItem;
         val product <- lineItem.product)
             yield product.name
}


The example demonstrates a very powerful abstraction in Scala, the for-comprehensions, which works literally on anything that implements map, flatMap and filter methods. This is also an illustration of how for-comprehensions in Scala blends beautifully with its implementation of the Maybe monad (Option[T]), leading to concise and powerful programming idioms. I think this is what Paul Graham calls orthogonal language in his On Lisp book.

David Pollack implements similar usage of the Maybe monad in his Lift framework. Here is a snippet from his own blog ..

def confirmDelete {
    (for (val id <- param("id"); // get the ID
        val user <- User.find(id)) // find the user
     yield {
         user.delete_!
         notice("User deleted")
         redirectTo("/simple/index.html")
     }) getOrElse {error("User not found"); redirectTo("/simple/index.html")}
}


The find method on the model class and the param method that extracts from the request, all return Option[T] - hence we do not need any explicit guard to check for null id or "user not found" checks.

In the first example, if the method productName() gets any null component in the path of accessing the name, it returns None (as it should be). What if I would like to know which part is None as part of the diagnostic message ?

Just pimp my Option !

class RichOption[T](value: Option[T]) {
    def ifNone(message: String) = {
        value.getOrElse(error(message))
    }
}


and add the implicit conversion ..

implicit def enrichOption[T](opt: Option[T]): RichOption[T]
    = new RichOption(opt)


Now the method becomes ..

def productName(maybeOrder: Option[Order]): Option[String] = {
    try {
        val nm = maybeOrder.ifNone("null order")
                           .lineItem.ifNone("null line item")
                           .product.ifNone("null product")
                           .name
        if (nm == null)
            None
        else
            Some(nm)

    } catch {
        case e => println(e.toString()); None
    }
}


and the method invocation reports with meaningful messages in case of null accesses.

Sunshine on Dynamic Languages rolls on

Lighting up enterprisey Java shops with Ruby and Python.

Sun is up in arms strengthening the ecosystem of the JVM. In fact the J in JVM is starting to fade away and is fast becoming the VM of choice for dynamic languages. I am sure, with Sun's hiring of Ted and Frank, invokedynamic is poised to gain more importance in the JCP world. After Ruby, Python is slated to be another first-class-citizen on the JVM.

But what happens to Java, the language ?

With more and more power of the dynamic languages being blessed on the JVM, are we prepared to see more and more polyglotism in enterprise applications ? BigCos and enterprise managers always like to remain sensitive to the platform they have invested in - you can implement in any language you want to, so long it runs on the JVM. In the days to come, expect more strategic support from Sun on features that will enrich Java, the platform, rather than Java, the language.

Next stop for Sun ? Scala ?