At Scala Exchange 2015 I gave a workshop on building interpreters in Scala. Code and slides are here, though future development will take place here. The workshop covered untyped interpreters, GADTs, and ended with the free monad and free applicative.
So, why interpreters? The big idea here is to separate the representation of the computation from the code that runs it. This has many uses in functional programming (it underlies the approach to functional IO for example) but the most compelling reason to me is that it solves difficult problems. There are some examples in the slides:
The implementation techniques shown in the workshop allows increasing sophistication in the embedded DSL. Untyped interpreters are the baseline. Moving to GADTs (generalised algebraic datatypes) allows us to reuse Scala’s type system and remove a whole pile of boilerplate around checking tags. The free applicative and free monad allow us to reuse all of Scala except for small parts of our code where we can insert bits of our DSL. The free structures also allow us to compose together DSLs and their interpreters.
If you’d like more detailed material, it’s going into our book Essential Interpreters (currently very much under construction).