mal: Step 5

project:

mal-py

filename:

step5_tco.py

read

mal-py step5_tco.py 
import itertools

from core import ns
from env import Env
from reader import Fn, S, read_str
from printer import print_form


def read(ins):
    return read_str(ins)

evaluate

To evaluate code we “just” have to switch on the form

Tail Call Optimization

Step 5 brings in tail call optimization.

Apparently this means we wrap everything in a while True loop.

Then going from the guide, I think, rather than calling into evaluate again, we modify the value of form (and possibly env) so that the next cycle of the loop uses the new values see:

mal-py step5_tco.py 
def evaluate(form, env: Env):
    while True:
        match form:
{{ insert(slots['eval'], indent=12) }}

  • Symbol values are looked up in the environment

    mal-py step5_tco.py 
    case S(name):
    return env.get(name)

  • Special case the empty list

    mal-py step5_tco.py 
    case []:
    return []

  • Unsurprisingly, a list of terms is where most of the action is

    mal-py step5_tco.py 
    case [*fs]:
    match fs[0]:
{{ insert(slots['special-form'], indent=8) }}

    We dispatch on the first item in the list and treat it accordingly.

  • Finally, everything else (numbers, strings etc.) return as-is

    mal-py step5_tco.py 
    case _:
    return form

Special forms

By definition, each special form is an edge case and needs to be handled separately.

def!

def! is how mal spells setq and updates the current environment

mal-py step5_tco.py 
case S('def!'):
    env.set(fs[1].name, v := evaluate(fs[2], env))
    return v

do

Equivalent to progn, evals all terms and returns the last one.

mal-py step5_tco.py 
case S('do'):
    # tco: evaluate() everything except for the final item
    for f in fs[1:-1]:
        evaluate(f, env)

    # tco: update ``form`` to be the final element so that it's evaluated on the
    # next iteration
    form = fs[-1]

fn*

a.k.a lambda.

I’m surprised at how simple conceptually it is.

A function definition:

  • Creates a new Env as a child of the current environment, it’s parameters define names that are yet to have values associated with them.

  • When called, these missing values are provided from its arguments and the function then calls evaluate on its body with the new local environment.

mal-py step5_tco.py 
case S('fn*'):
    def fn(*args):
        localenv = Env(outer=env, binds=fs[1], exprs=args)
        return evaluate(fs[2], localenv)

    # tco: return Fn rather than Python function def
    return Fn(params=fs[1], body=fs[2], env=env, f=fn)

Of course, the fact Python already has closures means that it is doing all the heavy lifting!

if

mal considers anything that is not false or nil to be true. Python however, considers other values like 0 to also be False!

This mismatch made implementing if surprinsgly difficult, especially when it likes to coerce 0 to False or False to 0.

The best I have come up with so far is to call print_form on the result and check the string values.

mal-py step5_tco.py 
case S('if'):
    t = print_form(evaluate(fs[1], env))
    if t not in {'false', 'nil'}:
        # tco: change ``form`` so that it's evaluated on the next iteration
        form = fs[2]
    elif len(fs) > 3:
        # tco: change ``form`` so that it's evaluated on the next iteration
        form = fs[3]
    else:
        return None

let*

let* is used to introduce a new local Env with additional bindings.

mal-py step5_tco.py 
case S('let*'):
    letenv = Env(env)
    for binding, expr in itertools.batched(fs[1], n=2):
        letenv.set(binding.name, evaluate(expr, letenv))

    # tco: update both ``form`` and ``env`` so that it's evaluated on the next iteration
    form = fs[2]
    env = letenv

Non-special forms

If the first symbol isn’t any of the above, then normal semantics apply i.e. all items are evaluated, the first is assumed to be a function and passed the remainder as arguments.

mal-py step5_tco.py 
case _:
    f, *args = [evaluate(f, env) for f in fs]
    match f:
        # tco: handle mal function calls.
        case Fn(params, body, fenv, fn):
            form=body
            env = Env(outer=fenv, binds=params, exprs=args)
        case _:
            return f(*args)

print

mal-py step5_tco.py 
def printit(form):
    return print_form(form)

REPL

rep

mal-py step5_tco.py 
def rep(ins: str, env: Env):
    try:
        return printit(evaluate(read(ins), env))
    except EOFError:
        return f"EOF"
    except KeyError as e:
        return f"{e.args[0]!r} not found"
    except Exception as e:
        print(f"RuntimeError: {e}")
        # import pdb; pdb.post_mortem()

repl

mal-py step5_tco.py 
def repl(ins: io.TextIO):
    env = Env()
    for symb, val in ns.items():
        env.set(symb, val)

    print("user> ", end='', flush=True)
    while (line := ins.readline()) != "":
        print(rep(line, env))
        print("user> ", end='', flush=True)


if __name__ == "__main__":
    import sys
    repl(sys.stdin)