Notes
2025/03/08
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.
...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>
</body>
</html>
Here's the grammar for the language, dubbed Kombucha (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))
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 Kombucha 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.
While the language might be an interesting starting point, there are a couple of things that need to be fixed:
catch foo!(x) as ... and a handler like catch foo!(x, y) as ... will catch the same effect foo!, the second handler will simply return a curried function until it gets its second argument. It would be nice to have handlers with a fixed arity, so that the same name can be overloaded with different implementations, but then handlers would work differently from normal functions.I'll revisit these as the language evolves.