My Recurse Center batch ended a couple weeks ago, and I wanted to write a report on the project which took the biggest part of my time: reading Types and programming Languages, and building in Haskell the various flavours of lambda calculi described in the book.

I actually ended up only going through the most basic lambda calculus variant (called “untyped” lambda calculus), and building a CLI REPL for it. But I made a few additions, including:

• The possibility to assign variables.
• A full beta evaluation mode (while the book only focuses on a call by value strategy).
• A small webapp embedding the REPL.
• Inside this webapp, a gamified tutorial with some walkthrough / exercises to learn about lambda calculus. This is far from being perfect, but I encourage you to try it if you feel curious!

Here is the source code of the project. In the next sections I will go through some interesting challenges I encountered.

Challenge 1: Left recursion

Preliminary note: this section might not make sense if you don’t have knowledge about parsing; in this case you can head to the next section.

The (untyped) lambda calculus is conceptually simple, but as often with programming, the devil is in the details. The first notable challenge I faced was related to parsing (which, by the way, is not covered by TAPL).

I used the recursive descent technique, with the help of the parsec library. Unfortunately, this technique doesn’t deal very well with left recursion. Before explaining what left recursion is, let’s look at the syntax of the lambda calculus:

term -> <abstraction> | <application> | <var>
abstraction -> λ<var>.<expr>
application -> <term> <term>
var -> string

In English, this means:

• A term is either an abstraction, application, or variable.
• An abstraction (or function definition) is a lambda symbol followed by a variable, followed by a dot, followed by a term.
• A function application is two terms separated by a space.
• A variable is a string.

As per Wikipedia:

a nonterminal is left-recursive if the leftmost symbol in one of its productions is itself (in the case of direct left recursion) or can be made itself by some sequence of substitutions (in the case of indirect left recursion).

It turns out that the application rule (or nonterminal) is left recursive, because if in its right side we substitute the left term by application (we know we can because we know from the first rule that a term can be an application) we get this:

application -> <application> <term>

This fits the indirect case of left recursion, which, as said above, cause problems for the parsing technique I used, recursive descent. Namely, it creates an infinite recursion.

I spent quite some time on this issue, but I eventually solved it by taking inspiration from the Crafting Interpreters book.

Writing the parser manually was very instructive, but I think next time I’ll need to parse something, I’ll probably use yacc or Happy, the yacc equivalent for Haskell.

Challenge 2: bring Haskell to the browser

I wanted this project to be easily accessible, without needing to download the code and the Haskell ecosystem, hence I decided to make a web version of it.

More precisely, I made a frontend only app (or SPA) by compiling my Haskell code to Javascript with GHCJS. Here are a few things worth mentioning:

• I had to use the Nix package manager, since Stack (the haskell package manager I was using) dropped support for it.
• To develop the app, I started with the Reflex library, but got confused by its API, hence I switched to Miso, which has an API very similar to Elm, or React / Redux. While Reflex probably shines with complex UI needs, I believe the much smoother learning curve of Miso was more adapted to my needs.

All in all, I reckon that this could have been easier with better documentation, but at the end of the day it feels quite good to be able to target the browser with Haskell.

To go even further, there is Obelisk, which is a platform aiming to target not only the browser, but also desktop and mobile applications, with Haskell.

Other challenges

Here is a quick list of obstacles which were more or less challenging:

• Prevent variable capture: this turned out to be quite tricky.
• Implementing the semantics with operational semantics.
• Add some basic CSS to the webapp: I used Bulma.
• Get familiar with Haskell tooling (Cabal, Stack).
• Implement the tutorial / game mechanics.

What ‘s next ?

I probably won’t finish the book (at least not in the short term). But I would like, at the very least, to implement the simply typed flavour of lambda calculus, in order to to see what it’s like to implement a type checker.