Outline

• Motivation
• Object Algebras
  • Object algebras in a nutshell
  • Variations in Scala
• Notable features
  • Extensibility
  • Modular expressive power
  • DSL families
• Comparison with free monads

Software engineer

• I spent the past five years to essentially build Web apps

Example: e-shop (server)

val readItem = Router.from {
  case GET(p"/item/$id") =>
    itemsRepository.lookup(id)
      .map(item => Ok(representation(item)))
}

Example: e-shop (client)

def eventualItem(id: String): Future[Item] =
  httpClient
    .url(s"http://eshop.com/item/${urlEncode(id)}")
    .get()
    .map(response => decodeItemFromJsonRepresentation(response))

• The request URL and entities must be consistent with the server implementation!

Example: e-shop (documentation)

$ curl http://eshop.com/item

{
  "data": [
    {
      "href": "http://eshop.com/item/123abc",
      "format": {
        "name": "string",
        "price": "decimal"
      }
    }
  ]
}

• The format description must be consistent with the server implementation!

What we want

• A well-defined language whose vocabulary effectively describes an HTTP API ;
• Ways to bring this vocabulary to “life” by giving it useful interpretations.
  • Server router (request dispatcher) ;
  • Client(s) ;
  • Machine readable documentation ;
  • Human readable documentation ;
  • … ?

Engineering concern: extensibility

• To avoid reinventing the vocabulary to describe HTTP APIs for each new project, we want to move it into a library ;
• Libraries aim to be reusable across many applications ;
• But they can not tackle some application-specific concerns (e.g. authentication) ;
• We need a way to introduce new vocabulary (and their possible interpretations) into the mix.

Engineering concern: language modularization

• Define “language modules” that can be composed together to define a richer language ;
• E.g. to leverage some technical specificity of a given interpreter, in order to not dumb down the whole language according to the limitations of some interpreters.

References

• Christian Hofer et al. 2008. Polymorphic Embedding of DSLs. GPCE. (paper) ;
• Bruno Oliveira. 2009. Modular Visitor Components. ECOOP. (paper) ;
• Bruno Oliveira et al. 2012. Extensibility for the Masses. ECOOP. (paper) ;
• Bruno Oliveira. 2014. Functional Programming, Object-Oriented Programming and Algebras! WGP. (slides).

First, specify the DSL domain

• Let’s start with a small part of HTTP APIs: URL paths ;
• Examples of paths:
  • /foo/bar, /item, /item/123abc ;
• A path is made of segments (e.g. foo, bar) that can be chained (like in foo/bar).

An algebra interface for URL paths

trait PathAlg[A] {

  def segment(value: String): A

  def chained(first: A, second: A): A

}

• PathAlg is an object algebra interface, A is its carrier type ;
• segment and chained are path constructors ;
• Think of that as an abstract factory for defining paths, but whose return type is not yet known: it will depend on the interpreter.

Usage

trait PathAlg[A] {

  def segment(value: String): A

  def chained(first: A, second: A): A

}

// defines the URL path “item/123abc”
def someItemPath[A](alg: PathAlg[A]): A = {
  import alg._
  chained(segment("item"), segment("123abc"))
}

Client interpreter

object PathClient extends PathAlg[String] {

  def segment(value: String): String = URLEncoder.encode(value)

  def chained(first: String, second: String): String = s"$first/$second"

}

• PathClient is an object algebra that uses String as the concrete representation for the carrier type ;
• Indeed, from a client point of view, a path is just a String ;

someItemPath(PathClient) // "item/123abc"

Server interpreter

object PathRouting extends PathAlg[String => Boolean] {

  def segment(value: String): String => Boolean =
    incoming => URLDecoder.decode(incoming) == value

  def chained(fst: String => Boolean, snd: String => Boolean): String => Boolean =
    incoming => {
      val i = incoming.indexOf("/")
      i >= 0 && fst(incoming.take(i)) && snd(incoming.drop(i + 1))
    }
}

• From a server point of view, a path is a function that checks whether an incoming request’s path matches the path’s value

val isSomeItem: String => Boolean = someItemPath(PathRouting)
isSomeItem("foo/bar") // false
isSomeItem("item/123abc") // true

Summary

• We defined an object algebra interface defining the rules to construct and combine paths ;
• These path definitions can be interpreted in various ways:
  • a client interpretation builds a String out of a path definition (to build an URL to perform a request on) ;
  • a server interpretation checks if the path of an incoming request matches a path definition (to dispatch an incoming request to the corresponding endpoint implementation).

Type members

• In practice, we often have several carrier types:

trait UrlAlg[A, B, C] {

  def segment(value: String): A
  def chained(first: A, second: A): A

  def queryStringParameter(name: String): B

  def url(path: A, queryString: B): C
}

• Distinct carrier types allow more precise concrete representations in the interpretation side

Type members (2)

trait UrlAlg {

  type Path
  def segment(value: String): Path
  def chained(first: Path, second: Path): Path

  type QueryString
  def queryStringParameter(name: String): QueryString

  type Url
  def url(path: Path, queryString: QueryString): Url
}

• In Scala, it is more convenient, in this case, to trade type parameters for type members

Type members (3)

def someItemPath[A, B, C](alg: UrlAlg[A, B, C]): A = {
  import alg._
  chained(segment("item"), segment("123abc"))
}

def someItemPath(alg: UrlAlg): alg.Path = {
  import alg._
  chained(segment("item"), segment("123abc"))
}

Syntax

trait PathAlg {

  type Path <: PathSyntax
  def segment(value: String): Path
  def chained(first: Path, second: Path): Path

  trait PathSyntax {
    final def / (that: String): Path = chained(this, segment(that))
  }

  val path: Path = segment("")
}

• Fancy syntax can be supported by providing a trait that will be mixed into the carrier type’s concrete representation

Syntax (2)

// defines the URL path “/item/123abc”
def someItemPath(alg: PathAlg): alg.Path = {
  import alg._
  path / "item" / "123abc"
}

Type constructors as carrier types

• Until now, the paths we can define with our DSL are constant ;
• We can “express” /item/abc123 or /item/456def, but not /item/{id} (where {id} is any string segment) ;
• We can fix that by making Path a type constructor.

Type constructors as carrier types (2)

trait PathAlg {

  type Path[A]

  def constSegment(value: String): Path[Unit]

  def stringSegment: Path[String]

  def integerSegment: Path[Int]

  def chained[A, B](first: Path[A], second: Path[B]): Path[(A, B)]

}

Type constructors as carrier types (3)

// “{name}/{id}”
def item(alg: PathAlg): alg.Path[(String, Int)] = {
  import alg._
  stringSegment / integerSegment
}

Type constructors as carrier types (4)

object PathClient extends PathAlg {

  type Path[A] = A => String

  …
}

item(PathClient)(("foo", 42)) // "foo/42"

• A is the information needed to build a path

Type constructors as carrier types (5)

object PathRouting extends PathAlg {

  type Path[A] = String => Option[A]

  …
}

item(PathRouting)("foo/42")  // Some(("foo", 42))
item(PathRouting)("foo/bar") // None

• A is the information that is extracted from the path of an incoming request

Retroactive addition of new vocabulary

• New terms are introduced as abstract methods in algebra interfaces:

trait EndpointAlg extends UrlAlg {
  type Request
  def get(url: Url): Request
}

val someItemRequest =
  get(url(path / "item" / "123abc"))

Retroactive addition of new interpreters

• An interpreter is an algebra interface implementation:

trait UrlDocumentation extends UrlAlg {

  type Path = Html
  type QueryString = Html
  type Url = Html

  def segment(value: String) = …
  def chained(first: Path, second: Path) = …
  def queryStringParameter(name: String) = …
  def url(path: Path, queryString: QueryString) = …

}

Languages and interpreters can be combined by mixing traits

Remember the variant of PathAlg that uses a type constructor as a carrier type

trait PathAlg {

  type Path[A]

  def constSegment(value: String): Path[Unit]

  def stringSegment: Path[String]

  def integerSegment: Path[Int]

  def chained[A, B](fst: Path[A], snd: Path[B]): Path[(A, B)]

}

Let’s make the carrier type an applicative functor

trait PathApplicativeAlg extends PathAlg {

  val pathApplicative: Applicative[Path]

  import pathApplicative._

  def chained[A, B](fst: Path[A], snd: Path[B]) =
    map2(fst, snd)((a, b) => (a, b))

}

Let’s make the carrier type a monad

trait PathMonadAlg extends PathApplicativeAlg {

  val pathMonad: Monad[Path]

  import pathMonad._

  lazy val pathApplicative = pathMonad

}

• Because all monads are applicative functors, we can make PathMonadAlg extend PathApplicativeAlg

Let’s revisit the PathRouting interpreter

trait PathRouting extends PathMonadAlg {

  type Path[A] = String => Option[(String, A)]

  val pathMonad =
    new Monad[Path] {
      def pure[A](a: A): Path[A] = s => Some((s, a))
      def flatMap[A, B](path: Path[A])(f: A => Path[B]): Path[B] =
        (s: String) => path(s).flatMap { case (ss, a) => f(a)(ss) }
    }

}

• Our Path[A] is a state monad that attempts to extract some A from a path value, and returns the remaining path along with this A

Let’s revisit the PathDocumentation interpreter

trait PathDocumentation extends PathApplicativeAlg {

  type Path[A] = String

  val pathApplicative =
    new Applicative[Path] {
      def pure[A](a: A): Path[A] = ""
      def map[A, B](path: Path[A])(f: A => B): Path[B] = path
      def ap[A, B](f: Path[A => B], path: Path[A]): Path[B] = s"$f/$path"
    }

  def constSegment(value: String) = value
  val integerSegment = "{number}"
  val stringSegment = "{string}"
}

• Our Path[A] is a simple String, so we can not implement a Monad[Path] ;
• We can implement Applicative[Path], though.

At use site, pick the expressive power you need

def program1(alg: PathApplicativeAlg) = …

• program1 is limited to the expressive power of applicative functors, but it accepts more interpreters (PathRouting and PathDocumentation) ;

def program2(alg: PathMonadAlg) = …

• program2 can leverage the expressive power of monads, but it accepts less interpreters (only PathRouting).

We can encode subtyping relationships between carrier types

trait UrlAlg {

  type Path <: Url
  def segment(value: String): Path
  def chained(first: Path, second: Path): Path

  type QueryString
  def queryStringParameter(name: String): QueryString

  type Url
  def url(path: Path, queryString: QueryString): Url
}

• I call this DSL families, by analogy with type families

DSL families are DSLs that specialize other DSLs

trait UrlAlg {

  type Path <: Url
  def segment(value: String): Path
  def chained(first: Path, second: Path): Path
  …
  type Url
  …
}

• We can give more capabilities to some terms ;
• E.g. in the particular case of URLs that are just made of a path, we can chain them together.

Remember the motivating example

• Server:

val readItem = Router.from {
  case GET(p"/item/$id") =>
    lookupAndRenderItem(id)
}

• Client:

def eventualItem(id: String): Future[Item] =
  httpClient
    .url(s"http://eshop.com/item/${urlEncode(id)}")
    .get()
    .map(response => decodeItemFromJsonRepresentation(response))

Let’s define the request once, using our DSL

def readItemRequest(alg: EndpointAlg): alg.Request[String] = {
  import alg._
  get(path / "item" / stringSegment)
}

Revisited server part

Before:

val readItem = Router.from {
  case GET(p"/item/$id") =>
    lookupAndRenderItem(id)
}

After:

val readItem = Router.from {
  readItemRequest(EndpointRouting).returning { id =>
    lookupAndRenderItem(id)
  }
}

Revisited client part

Before:

def eventualItem(id: String): Future[Item] =
  httpClient
    .url(s"http://eshop.com/item/${urlEncode(id)}")
    .get()
    .map(response => decodeItemFromJsonRepresentation(response))

After:

def eventualItem(id: String): Future[Item] =
  readItemRequest(EndpointClient)(id)
    .map(response => decodeItemFromJsonRepresentation(response))

Applying a documenting interpreter

readItemRequest(EndpointDocumentation) // "GET  /item/{string}"

Free monads abstract over the monadic context of a DSL interpreter

1. Define your language as a data type ;
2. Wrap the data type constructors into the free monad ;
3. Users can write programs using them ;
   • They can benefit from the expressive power of a monad,
4. Implement an interpreter, which eventually is a monad.

Object algebras vs free monads

• A key difference is that:
  • with free monads your interpreter has to be a monad,
  • with object algebras, your interpreter can be a monad, but this is not required.
• Free monads drastically reduce the space of possible interpreters ;
  • e.g. in my example, only the routing interepreter can be made a monad, but not the documentation nor the client interpreters,
  • more generally, one can not implement dual interpreters (like a client and server), because at most one of them could be made a monad.

Object algebras

• Way to define extensible embedded DSLs ;
• Fit well with object oriented programming languages ;
• More powerful while simpler (IMHO) than free monads!

Alternative way of using an algebra interface

def readItemRequest(alg: EndpointAlg): alg.Request[String] = {
  import alg._
  get(path / "item" / stringSegment)
}

def createItemRequest(alg: EndpointAlg): alg: Request[CreateItem] = {
  import alg._
  post(path / "item", jsonRequest[CreateItem])
}

Alternative way of using an algebra interface (2)

trait ItemEndpoints extends EndpointAlg {

  val readItemRequest: Request[String] =
    get(path / "item" / stringSegment)

  val createItemRequest: Request[CreateItem] =
    post(path / "item", jsonRequest[CreateItem])

}

object ItemClient extends ItemEndpoints with EndpointClient

Performance overhead of library-level abstractions

• Embedded DSLs may introduce some performance overhead, as they are just libraries ;
• We basically have two ways to define optimizations:
  • Implement an interpreter that generates (optimized) code,
  • Introduce explicit term representations, allowing the implementation of program transformations performing optimizations.

An interpreter that generates code

• Very powerful (see e.g. Lightweight Modular Staging), but:
  • Integration of generated code and hand-written code has frictions ;
  • All program parts may not cross stages ;
  • More complex build chain.

Program transformations applying rewrite rules

• Explicit term representation hinders extensibility ;
• Some solutions exist, based on modular visitors, but they introduce a lot of complexity (see e.g. [Hofer, 2010]).

Fold algebras?

• First, what are fold algebras?
• Let’s define the following algebraic data type to model URL paths:

sealed trait Path
case class Segment(value: String) extends Path
case class Chained(first: Path, second: Path) extends Path

• We recognize our two constructors, Segment and Chained.

We can then construct paths in a similar way than previously

sealed trait Path
case class Segment(value: String) extends Path
case class Chained(first: Path, second: Path) extends Path

val someItemPath: Path =
  Chained(Segment("item"), Segment("123abc"))

And we can define interpreters as folds

def fold[A](s: String => A, c: (A, A) => A): Path => A = {
  case Segment(value) => s(value)
  case Chained(fst, snd) => c(fold(s, c)(fst), fold(s, c)(snd))
}

val client: Path => String =
  fold[String](URLEncoder.encode, (fst, snd) => s"$fst/$snd")

val server: Path => String => Boolean =
  fold[String => Boolean](
    value => incoming => URLDecoder.decode(incoming) == value,
    (fst, snd) => incoming => {
      val i = incoming.indexOf("/")
      i >= 0 && fst(incoming.take(i)) && snd(incoming.drop(i + 1))
    }
  )

Example of use

client(someItemPath) // "item/123abc"

server(someItemPath)("item/123abc") // true
server(someItemPath)("foo/bar") // false

The product of functions matching the Path constructors is called a fold algebra

sealed trait Path
case class Segment(value: String) extends Path
case class Chained(first: Path, second: Path) extends Path

def fold[A](s: String => A, c: (A, A) => A): Path => A = …

From fold algebras to object algebras

type PathAlg[A] = (String => A, (A, A) => A)
def fold[A](alg: PathAlg[A]): Path => A = …

• This PathAlg is the fold algebra of Path

trait PathAlg[A] {
  def segment(value: String): A
  def chained(fst: A, snd: A): A
}
def fold[A](alg: PathAlg[A]): Path => A = …

• This PathAlg is our original object algebra interface!

By using Church encoded values, the Path type does not even need to exist!

val someItemPath: Path =
  Chained(Segment("item"), Segment("123abc"))

def someItemPath[A](alg: PathAlg[A]): A = {
  import alg._
  chained(segment("item"), segment("123abc"))
}

Relation With Fold Algebras

• Object algebras are basically a combination of two techniques:
  • Fold algebras ;
  • Church encodings.

Free monads abstract over the monadic context of a DSL interpreter

• Let’s first define our constructors as a data type:

sealed trait PathF[A]
case class ConstSegment(value: String) extends PathF[Unit]
case object StringSegment extends PathF[String]
case object IntegerSegment extends PathF[Int]
case class Chained[A, B](fst: Path[A], snd: Path[B]) extends PathF[(A, B)]

type Path[A] = Free[PathF, A]

• Path[A] is a monad (though we did not implement Monad[PathF]) that will be bound to an actual monadic context at interpretation time.

Actual Path[A] constructors

def constSegment(value: String): Path[Unit] =
  liftF(ConstSegment(value))

val stringSegment: Path[String] =
  liftF(StringSegment)

val integerSegment: Path[Int] =
  liftF(IntegerSegment)

def chained[A, B](fst: Path[A], snd: Path[B]): Path[(A, B)] =
  liftF(Chained(fst, snd))

Server interpreter

type PathRouting[A] = String => Option[A]

• The interpreter’s type must be a Monad ;

val pathRoutingMonad: Monad[PathRouting] =
  new Monad[PathRouting] {
    def pure[A](a: A): PathRouting[A] = _ => Some(a)
    def flatMap[A, B](
      path: PathRouting[A],
      f: A => PathRouting[B]
    ): PathRouting[B] =
      incoming => path(incoming).flatMap(f)(incoming)
  }

Server interpreter (2)

• An interpreter is a natural transformation from PathF to the interpreter’s type:

object Routing extends NaturalTransformation[PathF, PathRouting] {
  def apply[A](path: PathF[A]): PathRouting[A] =
    path match {
      case ConstSegment(value) =>
        incoming => if (URLDecoder.decode(incoming) == value) Some(()) else None
      case StringSegment =>
        incoming => Some(URLDecoder.decode(incoming))
      case IntegerSegment =>
        incoming => Try(incoming.toInt).toOption
      case Chained(fst, snd) =>
        incoming => {
          val i = incoming.indexOf("/")
          if (i >= 0) {
            fst.foldMap(Routing).apply(incoming.take(i))
              .zip(snd.foldMap(Routing).apply(incoming.drop(i + 1)))
              .headOption
          } else None
        }
    }
}

Usage

// {name}/{id}
val item = chained(stringSegment, integerSegment)

• Finally, we apply an interpreter to a value by using foldMap:

item.foldMap(Routing).apply("foo/42")  // Some(("foo", 42))
item.foldMap(Routing).apply("foo/bar") // None

DSLs combination

sealed trait PathF[A]
…
type Path[A] = Free[PathF, A]

sealed trait QueryStringF[A]
…
type QueryString[A] = Free[QueryStringF, A]

type PathAndQS[A] = Free[???, A]

• Monads do not compose in general, so we can not directly define PathAndQS out of Path and QueryString

DSLs combination (2)

• In order to combine DSLs, the idea is to delay the process of lifting the case classes constructors into a Free[F[_], _] data type until this F[_] is fully known ;
• For instance, using freek (an experimental library for combining DSLs):

type PathAndQS[A] = PathF :|: QueryStringF :|: FXNil

• And then freek automatically lifts our constructors to Free[PathAndQS, A]:

// {name}?{id=…}
val item =
  for {
    name <- StringSegment.freek[PathAndQS]
    id <- QueryStringParameter("id").freek[PathAndQS]
  } yield (name, id)

DSLs combination (3)

• Finally, you have to implement an interpreter for each DSL ;
  • With the additional constraint that they must all have the same target type constructor

type PathAndQSRouting[A] = Request => Option[A]

object PathRouting extends (PathF ~> PathAndQSRouting) { … }

object QSRouting extends (QueryStringF ~> PathAndQSRouting) { … }

• Then you can combine the interpreters:

val PathAndQSRouting = PathRouting :&: QSRouting

Client interpreter

type PathClient[A] = A => String

• This type is not a monad…
• … so we can not define a client interpreter!

Documentation interpreter

type PathDocumentation[A] = String

• This type is not a monad either!
• But it is an applicative functor…
  • … so we could potentially define a FreeApplicative similar to Free ;
  • but then, the nature of the interpreter (either monadic or applicative) would be fixed by the program definition (because constructors are lifted either to Free or FreeApplicative).

Object algebras vs free monads

Complexity

• To use free monads you should be familiar with the concepts of monads and natural transformations,
• To use object algebras you should be familiar with object orientation.

Verbosity

• With free monads you have to lift your constructors into a Free[F[_], _] type,
• With object algebras you have to take an algebra as parameter (or extend it) to start using its constructors.

Object algebras vs free monads (2)

Extensibility

• New interpreters and new DSLs can be retroactively added with both free monads and object algebras.

DSL families

• Object algebras can represent subtyping relations between DSLs by using the subtyping mechanism of the host language,
• With free monads this is not possible (since algebraic data types are closed), so you have to rely on some explicit subtyping reification (or maybe use church encoding).

Object algebras vs free monads (3)

Practicality

• With free monads your interpreter has to be a monad,
• With object algebras, your interpreter can be a monad, but this is not required.

Modular expressive power

• You can alleviate the requirement of being a monad by using FreeApplicative, for instance, which would require the interpreter to be only an applicative functor,
• But it is difficult to build programs that can be used with both Free and FreeApplicative

Object algebras vs free monads (4)

Stack-safety

• Recursive monadic calls are stack-safe with free monads,
• That’s not the case with object algebras (so you have to explicitly use trampolines to solve stack overflows).

Embedding a DSL

• Define the DSL vocabulary by just reusing your programming language capabilities to name things ;
• Reuse all the compiler infrastructure.

Example in Scala:

val readItem: Endpoint[String, Item] =
  endpoint(
    get(path / "items" / segment[String]),
    jsonResponse[Item]
  )

Embeddedding a DSL (2)

• Code that uses the DSL is seen by the program as a first class citizen ;
• Can be abstracted out and over.

// e.g. "/fr/index", "/en/index", etc.
val index =
  endpoint(get(path / segment[Lang] / "index"), htmlResponse)
// e.g. "/fr/about/", "/en/about", etc.
val about =
  endpoint(get(path / segment[Lang] / "about"), htmlResponse)

def i18nPage(title: String): Endpoint[Lang, Html] =
  endpoint(get(path / segment[Lang] / title), htmlResponse)

val index = i18nPage("index")
val about = i18nPage("about")

Embeddedding a DSL (3)

• Code that uses the DSL can benefit from the expressive power of the host language

endpoint(
  get(path / "asset" / assetSegments),
  if (gzipEnabled) gzippedAssetResponse else assetResponse
)

Embedded DSL vs “external” DSL

• More details in this blogpost: “My Problem With Code Generation” ;
• See also [Landin, 1966], one of the first papers on this idea.