It's programs all the way down

This is the first of a series of articles on "Monadic EDSLs in Scala."

Embedded domain specific languages (EDSLs) are a powerful tool for abstracting complexities such as effects and business logic from our programs. Instead of mixing ad-hoc error handling, database access, and web calls through our code, we isolate each domain into a little language. These little languages can then be used to write "mini-programs" describing, for example, how to create a web page for a user.

Our program then becomes a composition of mini-programs, and running our program becomes interpreting these mini-programs into actions. This is analogous to running an interpreter, itself a program, which turns code into actions.

The following illustrates what an EDSL might look like in Scala.

// An embedded program for fetching data for a user
def process(id: UserId): Program[Page] = for {
  bio  <- getBio(id)
  feed <- getFeed(id)
  page <- createPage(bio, feed)
} yield page

def interpretProgram[A](page: Program[A]): IO[A] = page.interpret {
  case GetBio(id)            => ...
  case GetFeed(id)           => ...
  case CreatePage(bio, feed) => ...
}

Here process defines a program in our embedded language. No action has actually been performed yet, that happens when it gets interpreted by interpretProgram and run at runtime.

In many situations a program in one EDSL is translated into another EDSL, much like a compiler (again another program).

// Translate each term of the program into a database call
def compile[A](program: Program[A]): Database[A] = program.interpret {
  case GetBio(id)            => ...
  case GetFeed(id)           => ...
  case CreatePage(bio, feed) => ...
}

def interpretDatabase(db: Database[A]): IO[A] = db.interpret { ... }

Sometimes you can even optimize programs in an EDSL, much like an optimizing compiler. In the above example, interpretDatabase could deduplicate identical requests and batch requests to the same table.

In this series of articles we will explore a couple approaches to embedding such DSLs in Scala. These techniques will be evaluated against the following axes:

• Abstraction: Separation of structure from interpretation. Programs describe only the structure of a computation, to be interpreted later on. A common use case is to have a live interpreter that queries databases and API endpoints and a test interpreter that works with in-memory stores.

• Composition: Given two or more EDSLs, how simple is it to compose them? Given EDSLs for database access and RPC, can we query for data and send it over the wire while maintaining the abstraction requirement?

• Performance: At the end of the day we must run our programs and therefore interpret our mini-programs. How EDSLs are encoded will affect how they perform and therefore affect any downstream consumers of our programs, be it other programs or end users.

In the next post we'll take a look at the first of these approaches.