Assignment 3

So far, we have been able to compose built-in primitives over a couple of datatypes in our Scheme language. That makes for a fine calculator, but it isn’t very interesting to use yet.

To bring our programming language up to roughly the same expressive power as other high-level languages, we must add function calls. We will build up to true functions in two parts: first, we will add C-like procedure calls, then we will add closures and make functions first-class.

Procedure calls

• labels
• code
• primcall
• labelcall

Closures

Functions are objects too. They get tagged. We tag pointers exactly like the Ghuloum paper does. Note that we are using 64-bit words/pointers instead of 32-bit, though!

• closure
• funcall

Free-variable analysis

Writing out closures manually is error-prone and irritating. Our compiler should be able to pick up what free variables a function needs from its enclosing scope.

I do this in one pass, but you can also do as the Ghuloum paper suggests and do it in two passes.

def lift_lambdas_rec(expr, labels, bound, free):
    match expr:
        case int(_) | Char():
            return expr
        case str(_) if expr in bound or expr in BUILTINS:
            return expr
        case str(_):
            free.add(expr)
            return expr
        # ...
        case _:
            raise NotImplementedError(expr)

def lift_lambdas(expr):
    labels = {}
    expr = lift_lambdas_rec(expr, labels, set(), set())
    labels = [[name, code] for name, code in labels.items()]
    return ["labels", labels, expr]

I suggest writing tests specifically for this code transformation, completely separately from the rest of the compilation process.

Submitting your homework