Compiling a Lisp: Lambda Lifting

Summary

first – previous I didn’t think this day would come, but I picked up the Ghuloum tutorial (PDF) again and I got a little bit further. There’s just one caveat: I have rewritten the implementation in Python. It’s available in the same repo in compiler.py. It’s brief, coming in at a little over 300 LOC + tests (compared to the C version’s 1200 LOC + tests). I guess there’s another caveat, too, which is that the Python version has no S-expression reader. But that’s fine: consider it an exercise for you, dear reader. That’s hardly the most interesting part of the tutorial. Oh, and I also dropped the instruction encoding. I’m doing text assembly now. Womp womp. Anyway, lifting the lambdas as required in the paper requires three things: Keeping track of which variables are bound Keeping track of which variables are free in a given lambda Keeping a running list of code objects that we create as we recurse We have two forms that can bind variables: let and lambda. This means that we need to recognize the names in those special expressions and modify the environment. What environment, you ask? The lifter Well, I have this little LambdaConverter class. class LambdaConverter: def __init__(self): self.labels: dict[str, list] = {} def convert(self, expr, bound: set[str], free: set[str]): match expr: case _: raise NotImplementedError(expr) def lift_lambdas(expr): conv = LambdaConverter() expr = conv.convert(expr, set(), set()) labels = [[name, code] for name, code in conv.labels.items()] return ["labels", labels, expr] We keep the same labels dict for the entire recursive traversal of the program, but we modify bound at each binding site and free only at lambdas. To illustrate how they are used, let’s fill in some sample expressions: 3, 'a, and #t: class LambdaConverter: # ... def convert(self, expr, bound, free): match expr: case int(_) | Char(): # bool(_) is implied by int(_) return expr # ... class LambdaTests(unittest.TestCase): def test_int(self): self.assertEqual(lift_lambda...