Building Regular DSLs in Scala

A well-designed, domain-specific language makes code expressive and easy to understand. But designing a nice DSL was always a challenging task. In this article, I present a simple framework for constructing regular DSLs in Scala.

Most internal domain specific languages I’ve seen so far belong to a class of regular languages. For an explanation of the upcoming parts, let’s use the following definition from Wikipedia:

Regular language is the language accepted by a deterministic finite automaton.

A deterministic finite automaton (DFA) consists of:

• A finite set of states.
• A finite set of input symbols (in a given case — a finite set of DSL keywords).
• A set of transitions between the states.
• An initial state.
• A set of accept (terminal) states.

Consider a simple language that describes the delegation of tasks by managers to workers. It contains only five keywords: lets, delegate, and, to, and supervisedBy. The language rules restrict a set of valid sentences to only three possible formats, listed below:

1. lets delegate Task1 [ and Task2 … ] to Worker1 supervisedBy Supervisor1
2. lets delegate Task3 [ and Task4 … ] supervisedBy Supervisor2 to Worker2
3. lets delegate Task5 [ and Task6 … ] to Worker3

It’s easy to build a DFA that uniquely defines this language:

The DFA has:

• Five states.
• A start state S1, which is reached via the lets keyword.
• Two final states — S3 and S5.
• Six transitions triggered by the keywords delegate, and, to, and supervisedBy.

The following is a step-by-step manual on how to transform this and other DFAs to Scala code.

The General Overview

Once the language is designed and the corresponding DFA is built, it’s time to reflect the DFA in code. It’s easy to model the automaton when each state is mapped to a unique type. All the transitions can then be associated with corresponding states via ad-hoc polymorphism. All accept states can be defined either as a set of implicit proof values or as a set of conversions to a single result type.

Step 1: Mapping States on Unique Types

There is obviously more than one way of mapping the states to custom types. The approach I find the most powerful it to create a parametrized type and express all other types in terms of this pivotal type. For instance, all states can be expressed via a combination of the pivotal type  DFA[T <: State]  and 5 subtypes of type State – State1 , State2 … State5.

Provided you have some insight into the domain, it’s more practical to express these specifics not only in the DSL semantics but also in the implementation of the DSL. Future code supporters will be grateful for that choice.

As for the sample DSL in this article, the good pivot may outline three qualitative distinctions between different states of given automaton: whether at least one task is specified; whether a task executor is specified; whether a supervisor is specified.

sealed trait TaskDefined 
sealed trait WorkerDefined 
sealed trait SupervisorDefined 

trait Yes extends SupervisorDefined with TaskDefined with WorkerDefined 
trait No extends SupervisorDefined with TaskDefined with WorkerDefined 

trait DFA[T <: TaskDefined, W <: WorkerDefined, S <: SupervisorDefined] {   
  private val _tasks: List[String] = Nil   
  private val _executor: Option[String] = None   
  private val _supervisor: Option[String] = None 
}

The five states are then expressed the following way:

• S1 -> DFA[No, No, No]
• S2 -> DFA[Yes, No, No]
• S3 -> DFA[Yes, Yes, No]
• S4 -> DFA[Yes, No, Yes]
• S5 -> DFA[Yes, Yes, Yes]

Step 2: Adding Transitions

The transitions are defined separately for each state. As we already have the mapping from each state to a unique type, it’s convenient to define an implicit extension class with the appropriate transitions for each type. Bear in mind that naming can be a tough problem here, though.

implicit class TransitionsAfterLets(sentence: DFA[No, No, No]) {   
  def delegate(task: String) = new DFA[Yes, No, No] {     
    override private val _delegatedTasks = List(task)   
  } 
} 

implicit class TransitionsAfterDelegate(sentence: DFA[Yes, No, No]) {   
  def and(task: String) = new DFA[Yes, No, No] {     
    override private val _delegatedTasks = sentence._delegatedTasks :+ task   
  }   
  def to(executor: String) = new DFA[Yes, Yes, No] {     
    override private val _delegatedTasks = sentence._delegatedTasks     
    override private val _executor = Some(executor)   
  }   
  def supervisedBy(supervisor: String) = new DFA[Yes, No, Yes] {     
    override private val _delegatedTasks = sentence._delegatedTasks     
    override private val _supervisor = Some(supervisor)   
  } 
} 

implicit class TransitionsAfterDelegateTo(sentence: DFA[Yes, Yes, No]) {
  def supervisedBy(supervisor: String) = new DFA[Yes, Yes, Yes] {
    override private val _executor = sentence._executor     
    override private val _delegatedTasks = sentence._delegatedTasks    
    override private val _supervisor = Some(supervisor)   
  } 
}

implicit class TransitionsAfterDelegateSupervisedBy(sentence: DFA[Yes, No, Yes]) {     
  def to(executor: String) = new DFA[Yes, Yes, Yes] {
    override private val _executor = Some(executor)     
    override private val _delegatedTasks = sentence._delegatedTasks     
    override private val _supervisor = sentence._supervisor   
  } 
}

Please note that each transition takes one state as an input (constructor parameter), and returns the same or a different state (each method’s return type).

To enter the DFA, we also have to define at least one transition to the start state:

def lets: DFA[No, No, No] = new DFA[No, No, No] {}

At this stage we can already compose compilable sentences e.g.:

val test = lets delegate "task1" and "task2" to "worker1" supervisedBy "supervisor1"

The only issue is that there’s no compile time validation yet so it is possible to construct an illegal method which will compile successfully.

Step 3: Defining Accept States

Depending on how many accept states are needed and on the concrete DSL syntax, there are at least three approaches to enable compile-time state verification.

Explicit Specification of the Expected Type

This is the simplest approach, which can be applied only if you don’t mind leaking the types used in DSL implementation to the client code and making the client responsible for verification. If we take the sample DSL sentence from the previous paragraph, the proof that we end up in an accept state will look like this:

val test: DFA[Yes, Yes, _] = lets delegate "task1" and "task2" to "worker1" supervisedBy "supervisor1"

Conversions to a Result Type

This approach is not suitable for making libraries, but other than that, it’s very powerful. One of many possible implementations for a given DSL is shown below:

class Assignment(worker: String, tasks: List[String]) 
class SupervisedAssignment(worker: String, supervisor: String, tasks: List[String]) 

//matches S3 on the graph 
implicit def fromDSL1(sentence: DFA[Yes, Yes, No]): Assignment =   
  new Assignment(sentence._executor.get, sentence._delegatedTasks) 

//matches S5 on the graph 
implicit def fromDSL2(sentence: DFA[Yes, Yes, Yes]): SupervisedAssignment =   
  new SupervisedAssignment(sentence._executor.get, sentence._supervisor.get, sentence._delegatedTasks) 

val test: SupervisedAssignment = lets delegate "task1" and "task2" to "worker1" supervisedBy "supervisor1"

A Set of Implicit Proofs

This is the most difficult and powerful approach, which affects the DSL as well. This approach can be found in Finagle RequestBuilder, used for compile-time request config validation.

In a nutshell, each sentence of the DSL must end up with a special last word (e.g.  build(),  send(), compile(), please(), etc). This method takes an implicit proof parameter of the same type as the current state type. A set of proof values is predefined by the library, so if there’s no proof for a given state’s type, the code will not compile.

Let’s add a  submit() word to our DSL. To enable the whole feature we only need to modify class DFA and its companion object:

@implicitNotFound("Delegation is not valid: " +
                  "Task Defined (exp: Yes): ${T}, " +    
                  "Worker Defined (exp: Yes): ${W}, " +   
                  "SupervisorDefined (exp: Yes or No): ${S}") 
trait DFA[T <: TaskDefined, W <: WorkerDefined, S <: SupervisorDefined] {   
  private val _delegatedTasks: List[String] = Nil   
  private val _executor: Option[String] = None   
  private val _supervisor: Option[String] = None   

  def submit(implicit proof: DFA[T, W, S]) =      
    println(s"Submiting tasks ${_delegatedTasks.mkString(",")} to worker ${_executor.get}") 
} 

object DFA {   
  implicit val acceptState3 = new DFA[Yes, Yes, No] {}   
  implicit val acceptState5 = new DFA[Yes, Yes, Yes] {} 
}

Now a valid sentence (that compiles fine) has the following form:

(lets delegate "task1" to "worker1" supervisedBy "supervisor1").submit

But if the sentence ends up not in an accept state of the DFA, error message is shown:

[error] /app/src/main/scala/dsls/DSL.scala:81: Delegation is not valid: Task Defined (exp: Yes): DSL.this.Yes, Worker Defined (exp: Yes): DSL.this.No, SupervisorDefined (exp: Yes or No): DSL.this.Yes
[error]   (lets delegate "task1" and "task2" supervisedBy "supervisor1").submit
[error]                                                                  ^
[error] one error found

And that’s it. Although the article appears bigger than I expected, all steps are fairly simple and once mastered, creating DSLs will be a piece of cake.