Notes

A Static Site Generator in Lambda Calculus With Effect Handlers

How much must be added to a minimal language like lambda calculus to write practical programs in it, such as a static site generator? Turns out, not much, if you add data types and more importantly, effects and effect handlers.

A simple static site generator written in such a minimal language comes in at around 150 lines, with IO such as reading and writing files implemented as effects that are handled by a host language (in this case Rust), turning Markdown such as... 

# Blog Post

This is a paragraph with _emphasized_ text.

```
foo(bar, baz) // some code
```

...into HTML such as...

<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8" />
<title>Blog Post</title>
<link rel="stylesheet" href="styles/style.css" />
</head>
<body>
<h1>Blog Post</h1>
<p>This is a paragraph with <em>emphasized</em> text.</p>
<pre><code>
foo(bar, baz) // some code
</code></pre>
</body>
</html>

Vorpal: Lambda Calculus + Data + Effects

Here's the grammar for the language, dubbed “Vorpal” (with syntax examples below). Variables are identifiers starting with a lowercase letter and ending with “!” (like “foo”, “foo-bar”, “fooBar”), tags are identifiers starting with an uppercase letter or enclosed in quotation marks (like “Foo”, “"some string"”), and effects are identifiers that end with “!” (like “print!”, “read-char!”). 

t = var                        // variable
  | var "=>" t                 // abstraction
  | t "(" t ")"                // application
  | tag                        // tag
  | "if" t "is" pat t "else" t // conditional
  | var "~>" t                 // recursion
  | eff                        // effect
  | "try" t catch              // handler

pat = tag
    | pat "(" var ")" // must be distinct (!) vars

catch = ""
      | "catch" pat "as" var t catch

The first three constructs (variables, abstractions and applications) are standard lambda calculus, just using a more familiar JS-like notation: 

foo           // a variable
foo(bar)      // calling the function foo with argument bar
foo(bar, baz) // sugar for foo(bar)(baz)
foo => bar    // a function with argument foo and body bar

// let is sugar for (foo => baz)(bar)
let foo = bar
baz

// () is sugar for the empty tag "",
// foo() is sugar for foo("")
foo()

The next two constructs (tags and conditionals) add data to the language and allow us to match on it. Tags just stand for themselves and are basically interned strings (but without any string operations on them, the only thing you can do with them is compare them for equality using if-else). To build up data structures, tags are applied to other values. For example, “Pair(x, y)” is the tag “Pair” applied first to x, then to y. 

let first = p =>
  if p is Pair(x, y)
    x
  else
    Error

first(Pair(Foo, Bar)) // == Foo

Another construct (recursion) adds named recursion to the language, making implicit recursion via fixed-point combinators unnecessary. It can be used to build either recursive functions or recursive values: 

r ~> Cons(Foo, r)
// == Cons(Foo, r ~> Cons(Foo, r))
// == Cons(Foo, Cons(Foo, r ~> Cons(Foo, r)))
// == ...

// "loop" is a recursive version of "let",
// in other words it's sugar for (foo => baz)(foo ~> bar)
loop foo = bar // bar can call foo recursively
baz

Putting this all together, here's how the classic map function can be defined: 

loop map = f => xs =>
  if xs is Cons(x, xs)
    Cons(f(x), map(f, xs))
  else
    xs

map(
    x => Foo(x),
    Cons(Bar, Cons(Baz, Nil))
) // == Cons(Foo(Bar), Cons(Foo(Baz), Nil))

Effects + Effect Handlers

Now for the interesting part, effects and how to handle them! Effects work just like normal functions, except that their names end with “!” and that they are dynamically bound: It is not necessary to define what the effect “foo!” does in the code before using it, it can be supplied later. Effect handlers provide this late-binding, they “catch” an effect, capture the computation that called the effect and can resume it with a value: 

let twice = x => pair!(x, x)

try
  Foo(twice(Bar))
catch pair!(x, y) as resume
  resume(Pair(x, y)) // == Foo(Pair(Bar, Bar))

An effect handler does not need to resume the computation though, in which case such a handler acts more like an exception handler: 

let twice = x => pair!(x, x)

try
  Foo(twice(Bar))
catch pair!(x, y) as _
  BailingOut // == BailingOut

The possibility to resume existing computations makes effect handlers quite flexible, they can for example be used to build an effect that works like a stateful variable with getter and setter: 

loop with-state = val => f =>
  try
    f()
  catch get!() as resume
    resume(val)
  catch set!(x) as resume
    with-state(x, _ => resume())

with-state(
  (),
  _ => List(
    get!(),
    set!(Foo),
    get!(),
    set!(Bar),
    set!(Baz),
    get!()
  )
) // == List((), (), Foo, (), (), Baz)

What happens when a program uses an effect but there is no handler defined? Execution will stop and return back to the host language that called the evaluator, in this case Rust, which is then free to handle the effect and can decide whether or not to resume the computation with a value.

This is a surprisingly powerful combination, because it keeps the embedded language simple, leading to an almost symbiotic relationship between host and embedded language: The embedded language can always use effects as an escape hatch and ask the host to handle things like IO.

For reference, here's the Vorpal program that converts a Markdown subset (of headings, emphasized text and code blocks) into HTML. It relies on two effects, “read-char!”, to read a single char as a tag, and “write-strs!”, to write a cons-list of tags to a file. It is definitely not the most ergonomic language, nesting if-else blocks leads to very verbose code, for example. But considering that the language does not provide much more than lambda calculus and has no standard library at all, the ease of programming in it is quite surprising.

The Rust code for Vorpal with effects and handlers is on Github.

Observations

While the language might be an interesting starting point, there are a couple of things that need to be fixed: