Combinators as the sublanguage of DSL syntax

In my presentation on DSLs in PhillyETE I had talked about organizing DSL syntax around a sub language of combinators. The underlying implementation model needs to be segregated from the engine that renders the syntax of your DSL. Doing this you can decouple your semantic model and reuse it in the context of other DSLs or even in some entirely different context. I called this the model-view architecture of DSLs. In this post I would like to extend my thoughts along similar lines and claim that publishing combinators that wire your model elements is a very effective way towards compositionality of your DSL syntax.

Functions compose naturally - hence if your DSL publishes combinators then your client can compose them to form larger structures. But for this composition to be effective, you need to have the proper types for each of them - yes, we are talking about type-safe composition.

In Scala I tend to use the curried syntax a lot when I design combinators. Let’s have a look at an example .. we assume that we have a domain model designed using some paradigm - it can be OO, it can be functional or maybe a mix of the two. When we implement a business rule, we use these model elements, wire them up and present a proper syntax to the user. As an example here's a domain rule for enrichment of a securities trade as it goes through its processing pipeline ..

1. get the tax/fee ids for a trade
2. calculate tax/fee values
3. enrich trade with net cash amount

Here are a few snippets of combinators that help users implement the rule ..

// get the list of tax/fees applicable for this trade
// depends on the market
val forTrade: Trade => Option[List[TaxFeeId]] = {trade =>
  taxFeeForMarket.get(trade.market) <+> taxFeeForMarket.get(Other)
}

// all tax/fees for a specific trade
val taxFeeCalculate: Trade => List[TaxFeeId] => List[(TaxFeeId, BigDecimal)] = {t => tids =>
  tids zip (tids ? valueAs(t))
}

val enrichTradeWith: Trade => List[(TaxFeeId, BigDecimal)] => BigDecimal = {trade => taxes =>
  taxes.foldLeft(principal(trade))((a, b) => a + b._2)
}


Note each of these combinators return a function instead of a concrete business abstraction. Of course combinators are supposed to return a function only. But my point is that with such a strategy it becomes easier to build larger abstractions out of these smaller ones. And these combinators will be domain facing - each of them implements a snippet of a business rule. Hence take special care to name them appropriately so that you have that ubiquitous language going within your DSL syntax. Here’s how we combine the above to form a larger business rule that implements the “enrichment of trade” functionality ..

// enrichment of trade
// implementation follows problem domain model
val enrich = for {
  // get the tax/fee ids for a trade
  taxFeeIds      <- forTrade 

  // calculate tax fee values
  taxFeeValues   <- taxFeeCalculate 

  // enrich trade with net amount
  netAmount      <- enrichTradeWith 
}
yield((taxFeeIds map taxFeeValues) map netAmount)

// enriching a trade
trade map enrich should equal(…)


.. very concise, very succinct and brings out the domain semantics very explicitly. This composition was possible only because we used the curried syntax in designing our combinators. Haskell has curry-by-default - no wonder it revels in designing of embedded DSLs.

So, is combinators as the building block of DSL syntax a good idea to follow ?

I have been using this strategy for some time now and it has been working out quite nicely for me. It’s not essential that your underlying domain model has to be purely functional. I have been using libraries like scalaz in scala that offers a good hierarchy of typeclasses which help a lot in designing generic combinators that work across an unrelated family of abstractions. In my PhillyETE talk I discussed how functors allows you to map over entities across diverse abstractions like List, Option and Functions. And once you make your combinators generic, they tend to be adopted within the DSL as part of the ubiquitous language.

Killing a var and Threading a State

In my earlier post on CQRS using functional domain models and Akka actors, I had implemented a data store that accumulates all events associated with individual trades. We call this EventSourcing that allows us to rollback our system in time and replay all events over the earlier snapshot to bring it up to date. This has many uses to detect any problems that might have occured in the past or to profile your system on a retroactive basis. This post is not about event sourcing or the virtues of CQRS.

In this post I start taking cue from the EventSourcing example and discuss some strategies of improving some aspects of the domain model. This is mostly related to raising the level of abstraction at which to program the solution domain. Consider this post to be a random rant to record some of my iterations in the evolution of the domain model.

The code snippets that I present below may sometimes look out of context since they're part of a bigger model. The entire prototype is there in my github repository ..

Story #1 : How to kill a var

Have a look at the event store that I implemented earlier ..

class EventStore extends Actor with Listeners {
  private var events = Map.empty[Trade, List[TradeEvent]]

  def receive = //..
  //..
}


With an actor based implementation the mutable var events is ok since the state is confined within the actor itself. In another implementation where I was using a different synchronous event store, I had to get around this mutable shared state. It was around this time Tony Morris published his Writer Monad in Scala. This looked like a perfect fit .. Here's the implementation of the abstraction that logs all events, shamelessly adopted from Tony's Logging Without Side-effects example ..

import TradeModel._
object EventLog {
  type LOG = List[(Trade, TradeEvent)]
}

import EventLog._

case class EventLogger[A](log: LOG, a: A) {
  def map[B](f: A => B): EventLogger[B] =
    EventLogger(log, f(a))

  def flatMap[B](f: A => EventLogger[B]): EventLogger[B] = {
    val EventLogger(log2, b) = f(a)
    EventLogger(log ::: log2 /* accumulate */, b)
  }
}

object EventLogger {
  implicit def LogUtilities[A](a: A) = new {
    def nolog =
      EventLogger(Nil /* empty */, a)

    def withlog(log: (Trade, TradeEvent)) =
      EventLogger(List(log), a)

    def withvaluelog(log: A => (Trade, TradeEvent)) =
      withlog(log(a))
  }
}


and here's a snippet that exercises the logging process ..

import EventLogger._

val trd = makeTrade("a-123", "google", "r-123", HongKong, 12.25, 200).toOption.get

val r = for {
  t1 <- enrichTrade(trd) withlog (trd, enrichTrade)
  t2 <- addValueDate(t1) withlog (trd, addValueDate)
} yield t2


Now I can check what events have been logged and do some processing on the event store ..

// get the log from the EventLogger grouped by trade
val m = r.log.groupBy(_._1)

// play the event on the trades to get the current snapshot
val x =
  m.keys.map {t =>
    m(t).map(_._2).foldLeft(t)((a,e) => e(a))
  }

// check the results
x.size should equal(1)
x.head.taxFees.get.size should equal(2) 
x.head.netAmount.get should equal(3307.5000)


Whenever you're appending data to an abstraction consider using the Writer monad. With this I killed the var events from modeling my event store.

Story #2: Stateful a la carte

This is a story that gives a tip for handling changing state of a domain model in a functional way. When the state does not change and you're using an abstraction repeatedly for reading, you have the Reader monad.

// enrichment of trade
// Reader monad
val enrich = for {
  taxFeeIds      <- forTrade // get the tax/fee ids for a trade
  taxFeeValues   <- taxFeeCalculate // calculate tax fee values
  netAmount      <- enrichTradeWith // enrich trade with net amount
}
yield((taxFeeIds map taxFeeValues) map netAmount)

val trd = makeTrade("a-123", "google", "r-123", HongKong, 12.25, 200)
(trd map enrich) should equal(Success(Some(3307.5000)))


Note how we derive the enrichment information for the trade keeping the original abstraction immutable - Reader monad FTW.

But what happens when you need to handle state that changes in the lifecycle of the abstraction ? You can use the State monad itself. It allows you to thread a changing state across a sequence transparently at the monad definition level. Here's how I would enrich a trade using the State monad as implemented in scalaz ..

val trd = makeTrade("a-123", "google", "r-123", HongKong, 12.25, 200).toOption.get

val x =
  for {
    _ <- init[Trade]
    _ <- modify((t: Trade) => refNoLens.set(t, "XXX-123"))
    u <- modify((t: Trade) => taxFeeLens.set(t, some(List((TradeTax, 102.25), (Commission, 25.65)))))
  } yield(u)

x ~> trd == trd.copy(refNo = "XXX-123")


In case you're jsut wondering what's going around above, here's a bit of an explanation. init initializes the state for Trade. init is defined as ..

def init[S]: State[S, S] = state[S, S](s => (s, s))


modify does the state change with the function passed to it as the argument ..

def modify[S](f: S => S) = init[S] flatMap (s => state(_ => (f(s), ())))


We apply the series of modify to enrich the trade. The actual threading takes place transparently through the magic of comprehensions.

There is another way of securely encapsulating stateful computations that allow in-place updates - all in the context of functional programming. This is the ST monad which has very recently been inducted into scalaz. But that is the subject of another post .. sometime later ..

Pushing the envelope on OO and functional with Scala

There has been quite a few inflamatory discussions in the twitterverse and the blogosphere recently regarding some of the ultra-functional voices dominating the Scala ecosystem. It's true that Scala is an object functional language. And it's also true that you can stretch Scala in both ways to get enough mileage out of it. Talking about the functional programming folks picking up Scala more and more, even Martin Odersky said this in his comment on one of such inflamatory posts ..

This is a good thing, IMO, because it pushes the envelope of what you can do with the language

Being a multi-paradigm language, I find Scala a wonderful mix. It has a very clean object model powered by its type system that helps programmers design scalable component abstractions. Scala also has a rich support for functional programming, which, though not as clean as Haskell, goes along very well complementing its OO capabilities. And from this perspective Scala offers an equal opportunity to developers coming from OO or FP paradigms.

In this post I will discuss one issue that can be solved elegantly in Scala using both of its paradigms. The OO version of the solution uses the elegance of mixins, abstract vals and the Cake pattern. While the functional version uses currying and partial applications.

Interface & Implementation

One of the recommended practices that we as software developers follow while designing domain models is to separate out the interface from an implementation. I am calling them by the terms interface and implementation. Replace them with the terminologies from your favorite language - contract, protocol, class, type .. etc. etc. But you know what I mean to say - distinguish between the nature of coupling of the generic and the specific parts of your abstraction.

Many people call this the Dependency Injection, where the actual implementation dependency is injected into your abstraction during runtime, resulting in reduced coupling. BTW I am not talking about DI frameworks, which may seem bolted on both in languages with a sane type system and those which don't have a static type system.

The OO way in Scala

Let's first consider how we can do dependency injection in Scala using the power of its object system. It has been covered in gory details by Jonas Boner in one of his Real World Scala blog posts. The example that I give here follows the same design that he used ..

Consider two abstractions that we use in our domain model for getting data out to the external world ..

// a repository for interacting with the underlying data store
trait TradeRepository {
  def fetch(refNo: String): Trade
  def write(t: Trade): Unit
}

// a domain service
trait TradeService {
  def fetchTrade(refNo: String): Trade
  def writeTrade(trade: Trade): Unit
}


And now the component for each of the above abstractions that contain the default implementations ..

trait TradeRepositoryComponent {
  val tradeRepo: TradeRepository

  class TradeRepositoryImpl extends TradeRepository {
    def fetch(refNo: String): Trade = //..
    def write(t: Trade): Unit = //..
  }
}

trait TradeServiceComponent{ this: TradeRepositoryComponent => // self type annotation that indicates the dependency
  val tradeService: TradeService

  class TradeServiceImpl extends TradeService {
    def fetchTrade(refNo: String) = tradeRepo.fetch(refNo)
    def writeTrade(trade: Trade) = tradeRepo.write(trade)
  }
}


Note how the self-type annotation is used in TradeServiceComponent to indicate a dependency on TradeRepositoryComponent. But still we are talking in terms of traits, without committing our final assembly to any specific object implementations. The abstract vals tradeRepo and tradeService have still not been materialized in terms of any concrete implementations. Thus we delay coupling to any implementation till the time we absolutely need them. And that is when we make the final assembly ..

// we are wiring up the components
object TradeServiceAssembly extends TradeRepositoryComponent with TradeServiceComponent {
  val tradeRepo = new TradeRepositoryImpl // impl
  val tradeService = new TradeServiceImpl // impl
}


Now we have the final object which encapsulates all implementation details and which we can use thus ..

// usage
import TradeServiceAssembly._
val t = tradeService.fetchTrade("r-123")
tradeService.writeTrade(t)


If we want to use different implementations (e.g. mocks for testing), we can either create another assembly module like the above and supply different implementation clasess to the abstract vals, or we can also directly mix in traits while we instantiate our assembly object ..

val assembly = new TradeRepositoryComponent with TradeServiceComponent {
  val tradeRepo = new TradeRepositoryMock
  val tradeService = new TradeServiceMock
}

import assembly._
val t = tradeService.fetchTrade("r-123")
tradeService.writeTrade(t)


So that was the implementation of DI using *only* the typesystem of Scala. All dependencies are indicated through self-type annotations and realized through concrete implementations specified in abstract vals right down to the object that you create as the final assembly. Shows the power of Scala's object model implemented over its type system.

The FP way in Scala

Now let's try to look at the same idiom through the functional lens of Scala.

We will still have the repository abstractions, but we implement the service contracts directly as functions.

trait TradeRepository {
  def fetch(refNo: String): Trade
  def update(trade: Trade): Trade
  def write(trade: Trade): Unit
}

// service functions
trait TradeService {
  val fetchTrade: TradeRepository => String => Trade = {repo => refNo => repo.fetch(refNo)}
  val updateTrade: TradeRepository => Trade => Trade = {repo => trade => //..
  val writeTrade: TradeRepository => Trade => Unit = {repo => trade => repo.write(trade)}
}


Now let's say we would like to work with a Redis based implementation of our TradeRepository. So somewhere we need to indicate the actual TradeRepository implementation class that the service functions need to use. We can define partial applications of each of the above functions for Redis based repository and put them in a separate module ..

object TradeServiceRedisContext extends TradeService {
  val fetchTrade_c = fetchTrade(new TradeRepositoryRedis)
  val updateTrade_c = updateTrade(new TradeRepositoryRedis)
  val writeTrade_c = writeTrade(new TradeRepositoryRedis)
}


So fetchTrade_c is now a function that has the type (String) => Trade - we have successfully abstracted the TradeRepository implementation class knowledge through currying of the first parameter.

These modules are somewhat like Spring ApplicationContext that can be swapped in and out and replaced with alternate implementations for other kinds of underlying storage. As with the OO implementation, you can plug in a mock implementation for testing.

We can now continue to use the curried versions of the service functions completely oblivious of the fact that a Redis based TradeRepository implementation has been sucked into it ..

import TradeServiceRedisContext._
val t = fetchTrade_c("ref-123")
writeTrade_c(t)


One of the potential advantages that you get with functional abstractions is the power of composability, which is, much better than what you get with objects. FP defines many abstraction models that composes in the mathematical sense of the term. If you can design your domain abstractions in compliance with these structures, then you can also get your models to compose as beautifully.

Instead of currying individual functions as above, we can curry a composed function ..

val withTrade = for {
  t <- fetchTrade
  u <- updateTrade
} 
yield(t map u)


withTrade is now a function of type (TradeRepository) => (String) => Trade. In order to make this work, you will need to have scalaz which defines higher order abstractions to make operations like bind (flatMap) available to a much larger class of abstractions than those provided by the Scala standard library. In our case we are using the function application as a monad. We can now inject the Redis based implementation directly into this composition ..

val withTradeRedis = withTrade(new TradeRepositoryRedis)


I find both variants quite elegant to implement in Scala. I use the version that goes better with my overall application design. If it's primarily an OO model, I go with the Cake based serving. When I am doing FP and scalaz, I use the functional approach. One advantage that I find with the functional approach is increased composability since free standing functions only need to agree on types to compose. While with objects, you need to cross over another layer of indirection which may not be that easy in some cases.

Applicatives for composable JSON serialization in Scala

It has been quite some time I have decided to play around with sjson once again. For the convenience of those who are not familiar with sjson, it's a tiny JSON serialization library that can serialize and de-serialize Scala objects. sjson offers two ways in which you can serialize your Scala objects :-

1. typeclass based serialization, where you define your own protocol (typeclass instances) for your own objects. The standard ones, of course come out of the box.
2. reflection based serialization, where you provide a bunch of annotations and sjson looks up reflectively and tries to get your objects serialized and de-serialized.

One of the things which bothered me in both the implementations is the way errors are handled. Currently I use exceptions to report errors in serializing / de-serializing. Exceptions, as you know, are side-effects and don't compose. Hence even though your input JSON value has many keys that don't match with the names in your Scala class, errors are reported one by one.

scalaz is a Haskell like library for Scala that offers myriads of options towards pure functional programming. I have been playing around with Scalaz recently, particularly the typeclasses for Applicatives. I have also blogged on some of the compositional features that scalaz offers that help make your code much more declarative, concise and composable.

The meat of scalaz is based on the two most potent forces that Scala offers towards data type generic programming :-

1. typeclass encoding using implicits and
2. ability to abstract over higher kinded types (type constructor polymorphism)

Using these features scalaz has made lots of operations available to a large family of data structures, which were otherwise available only for a smaller subset in the Scala standard library. Another contribution of scalaz has been to make many of the useful abstractions first class in Scala e.g. Applicative, Monad, Traversable etc. All of these are available in Haskell as typeclass hierarchies - so now you can use the goodness of these abstractions in Scala as well.

One of the areas which I focused on in sjson using scalaz is to make error reporting composable. Have a look at the following snippet ..

// an immutable value object in Scala
case class Address(no: Int, street: String, city: String, zip: String)
 
// typeclass instance for sjson serialization protocol for Address
object AddressProtocol extends DefaultProtocol {
 
 implicit object AddressFormat extends Format[Address] {
   def reads(json: JsValue): ValidationNEL[String, Address] = json match {
     case m@JsObject(_) => 
       (field[Int]("no", m)        |@| 
        field[String]("street", m) |@| 
        field[String]("city", m)   |@| 
        field[String]("zip", m)) { Address }
 
     case _ => "JsObject expected".fail.liftFailNel
   }
 //..
}


In the current version of sjson, reads returns an Address. Now it returns an applicative, ValidationNEL[String, Address], which is a synonym for Validation[NonEmptyList[String], Address]. Validation is isomorphic to scala.Either in the sense that it has two separate types for error and success. But it has a much cleaner API and does not leave the choice to convention. In our case since we will be accumulating errors, we choose to use a List type for the error part. As a general implementation strategy, when Validation is used as an Applicative, the error type is modeled as a SemiGroup that offers an append operation. Have a look at scalaz for details of how you can use Validation as an applicative for cumulative error reporting.

Let's see what happens in the above snippet ..

1. field extracts the value the relevant field (passed as the first argument) from the JsObject. Incidentally JsObject is from Nathan Hamblen's dispatch-json, which sjson uses under the covers. More on dispatch-json's awesomeness later :). Here's how I define field .. Note if the name is not available, it gives us a Failure type on the Validation.

def field[T](name: String, js: JsValue)(implicit fjs: Reads[T]): ValidationNEL[String, T] = {
 val JsObject(m) = js
 m.get(JsString(name))
  .map(fromjson[T](_)(fjs))
  .getOrElse(("field " + name + " not found").fail.liftFailNel)
}


2. field invocations are composed using |@| combinator of scalaz, which gives us an ApplicativeBuilder that allows me to play around with the elements that it composes. In the above snippet we simply pass these components to build up an instance of the Address class.

Since Validation is an Applicative, all errors that come up during composition of field invocations get accumulated in the final list that occurs as the error type of it.

Let's first look at the normal usecase where things are happy and we get an instance of Address constructed from the parsed json. No surprises here ..

// test case
it ("should serialize an Address") {
 import Protocols._
 import AddressProtocol._ // typeclass instances
 val a = Address(12, "Tamarac Square", "Denver", "80231")
 fromjson[Address](tojson(a)) should equal(a.success)
}


But what happens if there are some errors in the typeclass instance that you created ? Things start to get interesting from here ..

implicit object AddressFormat extends Format[Address] {
 def reads(json: JsValue): ValidationNEL[String, Address] = json match {
   case m@JsObject(_) => 
     (field[Int]("number", m) |@| 
      field[String]("stret", m) |@| 
      field[String]("City", m) |@| 
      field[String]("zip", m)) { Address }
 
   case _ => "JsObject expected".fail.liftFailNel
 }
 //..
}


Note that the keys in json as passed to field API do not match the field names in the Address class. Deserialization fails and we get a nice list of all errors reported as part of the Failure type ..

it ("address serialization should fail") {
  import Protocols._
  import IncorrectPersonProtocol._
  val a = Address(12, "Tamarac Square", "Denver", "80231")
  (fromjson[Person](tojson(p))).fail.toOption.get.list 
    should equal (List("field number not found", "field stret not found", "field City not found"))
}


Composability .. Again!

A layer of monads on top of your API makes your API composable with any other monad in the world. With sjson de-serialization returning a Validation, we can get better composability when writing complex serialization code like the following. Consider this JSON string from where we need to pick up fields selectively and make a Scala object ..

val jsonString = 
  """{
       "lastName" : "ghosh", 
       "firstName" : "debasish", 
       "age" : 40, 
       "address" : { "no" : 12, "street" : "Tamarac Square", "city" : "Denver", "zip" : "80231" }, 
       "phone" : { "no" : "3032144567", "ext" : 212 },
       "office" :
        {
          "name" : "anshinsoft",
          "address" : { "no" : 23, "street" : "Hampden Avenue", "city" : "Denver", "zip" : "80245" } 
        }
     }"""


We would like to cherry pick a few of the fields from here and create an instance of Contact class ..

case class Contact(lastName: String, firstName: String, 
  address: Address, officeCity: String, officeAddress: Address)


Try this with the usual approach as shown above and you will find some of the boilerplate repetitions within your implementation ..

import dispatch.json._
import Js._

val js = Js(jsonString) // js is a JsValue

(field[String]("lastName", js)    |@| 
 field[String]("firstName", js)   |@| 
 field[Address]("address", js)    |@| 
 field[String]("city", (('office ! obj) andThen ('address ? obj))(js)) |@|
 field[Address]((('office ! obj) andThen ('address ! obj)), js)) { Contact } should equal(c.success)


Have a look at this how we need to repeatedly pass around js, though we never modify it any time. Since our field API is monadic, we can compose all invocations of field together with a Reader monad. This is a very useful technique of API composition which I discussed in an earlier blog post. (Here is a trivia : How can we compose similar stuff when there's modification involved in the passed around state ? Hint: The answer is within the question itself :D)

But for that we need to make a small change in our field API. We need to make it curried .. Here are 2 variants of the curried field API ..

// curried version: for lookup of a String name
def field_c[T](name: String)(implicit fjs: Reads[T]) = { js: JsValue =>
  val JsObject(m) = js
  m.get(JsString(name)).map(fromjson[T](_)(fjs)).getOrElse(("field " + name + " not found").fail.liftFailNel)
}

// curried version: we need to get a complete JSON object out
def field_c[T](f: (JsValue => JsValue))(implicit fjs: Reads[T]) = { js: JsValue =>
  try {
    fromjson[T](f(js))(fjs)
  } catch {
    case e: Exception => e.getMessage.fail.liftFailNel
  }
}


Note how in the second variant of field_c, we use the extractors of dispatch-json to take out nested objects from a JsValue structure. We use it below to get the office address from within the parsed JSON.

And here's how we compose all lookups monadically and finally come up with the Contact instance ..

// reader monad
val contact =
  for {
    last    <- field_c[String]("lastName")
    first   <- field_c[String]("firstName")
    address <- field_c[Address]("address")
    office  <- field_c[Address]((('office ! obj) andThen ('address ! obj)))
  }
  yield(last |@| first |@| address |@| office)

// city needs to be parsed separately since we are working on part of js
val city = field_c[String]("city")

// compose everything and build a Contact
(contact(js) |@| city((('office ! obj) andThen ('address ? obj))(js))) { 
  (last, first, address, office, city) => 
    Contact(last, first, address, city, office) } should equal(c.success)


I am still toying around with some of the monadic implementations of sjson APIs. It's offered as a separate package and will make a nice addition to the API families that sjson offers. You can have a look at my github repo for more details. I plan to finalize soon before I get to 1.0.