METACIRCULAR IS EASY


NB. This is meant to be a simple tutorial on how to implement a toy interpreter for a tiny LISP dialect.

Metacircular is easy. Or I should say, writing an interpreter is easy. People normally forget that they should always have a "toy meter" when they look at pieces of software; they should know there's always a certain "toy-ness" associated with every piece of them, ranging from "very serious" to "very toy-ish", and that toy-ish is easy and serious is hard. So if someone one day says that he has his LISP dialect, that does not explain much other than he does have one; it goes the same for other "big things" like your operating system, your game engine, your version management software, etc..

Now I'm trying to convince you that this is actually the case: think highly of someone just because they've got their own LISP really looks somewhat stupid to me, because you can be the guy you think highly of, in the course of a weekend or a whole afternoon, depending on your actual speed going through this article.

I use Python. You better get your Python installation ready. It better be Python 3.6+ or compatible.

The problem with Python, and overall planning

I use Python simply because it's the language used at my workplace & my go-to language for short, simple scripts - I myself don't like Python. Before the actual coding begins, I just have to offer some advice to you:

  • Don't use OOP constructs like class; specifically, don't use the so-called "Design Patterns" from that I-don't-know-why-but-it-somehow-got-popular (or, more like it-really-shouldn't-be-this-popular-but-it-is-anyway-so-just-live-with-it) book.
  • Use type checkers or linting tools like mypy if you've got the time to set it up; if you don't, just skip it as I did.

Python suffers from being a so-called "Object-Oriented Programming" language. OOP can do stuff when used "correctly" (which is a state that we mere mortals can neither achieve nor truly understand), but can do serious harm when used "not so correctly". Bad-OOP-infected libraries are everywhere in libraries bundled with the standard CPython distribution.

One more advice for anyone at their first time writing a toy interpreter:

  • Do NOT start by (either manually or using tools like lex and yacc) writing a lexer or parser. Start by directly writing AST in Python. (If you're using JavaScript/Go/[insert your language here], that's also the case).

It's like advising people not reading the introduction & the prerequisite chapter of any math textbook: when it comes to the actual business, these parts are simply not that important at all. They consume time that you could have spent on actually doing the core, the more important stuff. If you don't know how to use lex/yacc, learning how to use them could be devastating. Writing parsers, especially doing it manually with no libraries or syntax sugar like DCG (oh my lord. Can't stress this enough; DCG is such a breeze) or monadic parser combinators, is a painful chore; I write them for a living, I know how they are to write.

The AST

So let's start by representing the AST. In case you don't know what AST is, it's an acronym for "Abstract Syntax Tree", it's used to (internally) represent the input program in a tree-like manner. Remember: I've just said that you should not use OOP constructs. "So, " you might ask, "how am I going to represent this tree without them?" The answer is simple. LISP programmers have been using this technique for almost 60 years, and it seems that this almost-crude solution has never bothered them too much.

You use tuples. Appropriately tagged tuples.

Don't be such a chicken; it's basically what the term "object" actually is if we think of "conventional", "Java/C++ style OOP" modulo methods & dispatching & whatnot, and it's also how Golang does OOP, so if you happened to be familiar with Golang this shouldn't be too hard to understand. So an integer literal would be something like ("integer", 3), a string ("string", "I am a string") and an anonymous function ("lambda", variables, body), etc..

Let's start by having some getters.

def ast_type(x):
    return x[0]
# that's it. that's all we need for now.

Of course, the code above, and the code presented throughout this blogpost is not robust - not robust at all. This is a perfect example of the luxury of you being your code's only producer, maintainer & user: you can make assumptions in your code so you can move quicker and have a working product in a short amount of time, and you can remove the assumption by filling in more related code over the time without really affecting too many people; even if you have no time to improve it, at least you can (somewhat) adjust your habit to it.

And let's decide what should we add in our new LISP dialect. You'll have a better time by starting simple. Here's a list that I assembled for you:

  • The ability to calculate stuff, where stuff can be an integer, a floating-point number, and a string. The list of available operations - or really, the options that we choose do provide - is listed as follows:

    • The "basic five operations" of integers: adding, subtracting, multiplying, dividing and modulo.
    • The basic four operations for floating-point numbers.
    • String concatenation & slicing.
    • Basic operations of pairs. A special constant denoting the empty list as well, because we're using nested pairs to construct "list"s - the "real", "FP" list, not the one Python have which is actually some kind of dynamic array.

    We will treat them as function calls, and we'll use "funcall" as the tag name for function calls, so (+ 1 2) (which is some kind of +(1, 2) and ultimately 1 + 2) will be like ("funcall", "+", [("int", 1), ("int", 2)]), etc..

  • The ability to create anonymous functions. Yes, only anonymous functions.

It turns out that these are all we need if we ignore issues like IO; even the special form of defining something is not necessary: for example, in Python you can do (lambda x: body)(value) and in body the name x is defined, so defining functions is no more than doing (lambda my_func: other_part_of_the_program)(lambda my_func_args: my_func_body) (modulo mutual recursive functions, which we'll talk about later).

Metacircular

The word "metacircular" is a combination of the prefix "meta" and the word "circular". The "circular" part is not hard to explain: our interpreter will "circularly" interpret our LISP dialect. The "meta" part is somewhat harder to explain, but the meaning does not matter that much so we'll just ignore it for now. Our interpreter is circular.

Now you should be asking this question: "What does 'circular' actually mean?". If you already know some Python, you probably know what will happen when a function is called. The process can be roughly divided into 3 steps:

  • Evaluates the object being called & its arguments, from left to right, with the environment the call was in.
  • Bind (or, "assign"; the meanings of the two words are different, though; the difference doesn't matter much here) the "actual" arguments to the function's "formal" arguments.
  • Execute whatever code is in the function.

The last two steps roughly make up what people called the "apply" process; the evaluation process also consists of applying things. So, when you evaluate, you'll be applying; when you apply, you'll be evaluating, and thus results in a circle (commonly depicted as a Tai-Chi graph), hence the word "circular".

From that we have the following code:

def my_eval(term, env):
    if ast_type(term) == 'funcall':
        actual_args = funcall_get_actual_args(term)
        # the actual detail of how to evaluate the called function depends on your
        # representation, so it might be very different in other pieces of demo
        # code in this article.
        evaluated_function = my_eval(funcall_get_function(term), env)
        evaluated_actual_args = [my_eval(arg, env) for arg in actual_args]
        return my_apply(evaluated_function, evaluated_actual_args, env)
    else:
        # handle other cases here.
        ...

# assumes that `arglist` only contains evaluated values.
def my_apply(function, arglist, env):
    if function == '+':
        if not arglist:
            return 0
        else:
            # Calling + with only one argument should just return that argument.
            # You might want to have some (dynamic) type checking, raising exceptions if the arguments aren't
            # numbers.
            result = arglist[0]
            for arg in arglist[1:]:
                result += arg
            return result
    # other cases for built-in functions are done in a similar fashion.
    else:
        body = function_get_body(function)
        formal_args = function_get_formal_args(function)
        new_env = make_new_env(env, bind_vars(formal_args, arglist))
        return my_eval(body, new_env)

(It's not that hard to grasp, actually; but it's important that you truly understand what it does.)

my_apply gets called in my_eval, my_eval gets called in my_apply. Circular. Just like an ouroboros.

Functions, environment

One thing I (deliberately) forgot to talk about is the anonymous function. If you tried to fill out the definitions of all the functions that did not have one in the snippet above, you might be having a hard time trying to figure out how to represent anonymous function because "they are so different", you have to execute them (and "sometimes" you don't - check out something called dead code elimination), you probably have to compile them to some weird machine code and whatnot; but no, we aren't going to compile stuff. For simplicity, we represent them as-is. A function for adding two numbers will be converted from (lambda (x y) (+ x y)) to ("lambda", ["x", "y"], ("funcall", "+", ["x", "y"])). Other anonymous functions follow the same pattern (not the primitive ones though - they are specially handled, shown in the code snippet above).

# assumes that a lambda expression is represented like `("lambda", vars, body)`.
def function_get_formal_args(term):
    # oh and by the way, you might want to do the guarding here, e.g. raise an exception
    # when the term is not a valid representation of any anonymous functions.
    return term[1]
def function_get_body(term):
    return term[2]

To represent the relation between variable names and their actual values we need some kind of "mapping" structure. Python has dict, we're going to use that:

# Here we again assuming stuff & writing code that's not robust at all, e.g. the definition
# listed here definitely needs some guarding clauses handling the corner case where the two
# lists have different lengths, etc..
def bind_vars(formal_args, values):
    return {varname: value for varname, value in zip(formal_args, values)}

And the code for constructing new environments:

def make_new_env(old_env, binding):
    return (binding, old_env)

Sorry (but not really) I lied. We aren't going to use dict directly - the decision made here is to represent environments as a 2-tuple containing the dict and the old environment. Why this instead of just dicts? You'll understand soon…

And now comes the code for finding the value of a variable:

def lookup(varname, env):
    while env:
        binding = env[0]
        if varname in binding:
            return binding[varname]
        env = env[1]
    raise Exception(f'not found: {varname}')

In the function lookup we always look up the "newest" binding first; that's for something called "shadowing", which basically means variable names bound inside of an anonymous function has nothing to do with any variables from outside the function even if they have the same name, or the variable bound inside "shadows" the one on the outside when evaluating expressions in the inner scope. For example, the two x bound by different lambda in the term (lambda (x) (lambda (x) x)) has nothing to do with each other - the one on the inside is simply a different x. We achieved this behaviour not because we put the new binding list to the left of the old one but rather always search the variable in the new binding list first so that only the "newest" (or "deepest") bound value will be found. It looks like we can fill in the gaps properly now.

Scopes

By now you probably already have something like the piece of code listed above; this is a version I came up with, only includes basic integer & pair operations because it is just for demonstration:

def bind_vars(formal_args, values):
    return {varname: value for varname, value in zip(formal_args, values)}
def make_new_env(old_env, binding):
    return [binding] + old_env
def lookup(varname, env):
    while env:
        binding = env[0]
        if varname in binding:
            return binding[varname]
        env = env[1]
    raise Exception(f'not found: {varname}')

def ast_type(x):
    return x[0]

def funcall_get_actual_args(term):
    return term[2]
def funcall_get_function(term):
    return term[1]
def function_get_formal_args(term):
    return term[1]
def function_get_body(term):
    return term[2]
def var_get_name(term):
    return term[1]
def int_get_value(term):
    return term[1]
def pair_get_value(term):
    return term[1:]

def is_primitive_function(term):
    return type(term) == str

def my_eval(term, env):
    if ast_type(term) == 'funcall':
        actual_args = funcall_get_actual_args(term)
        function = funcall_get_function(term)
        evaluated_function = function if is_primitive_function(function) else my_eval(funcall_get_function(term), env)
        evaluated_actual_args = [my_eval(arg, env) for arg in actual_args]
        return my_apply(evaluated_function, evaluated_actual_args, env)
    elif ast_type(term) == 'lambda':
        return term
    elif ast_type(term) == 'var':
        # notice that we use the tag "var" to represent variables.
        varname = var_get_name(term)
        lookup_res = lookup(var_get_name(term), env)
        if not lookup_res:
            raise Exception(f'not_found: {varname}')
        return lookup_res
    elif ast_type(term) == 'int':
        return int_get_value(term)
    elif ast_type(term) == 'pair':
        return pair_get_value(term)

# assumes that `arglist` only contains evaluated values.
def my_apply(function, arglist, env):
    if function == '+':
        if not arglist:
            return 0
        else:
            result = 0
            for arg in arglist:
                result += arg
            return result
    elif function == '-':
        if not arglist:
            return 0
        return arglist[0] - arglist[1]
    elif function == '*':
        if not arglist:
            return 0
        else:
            result = 1
            for arg in arglist:
                result *= arg
            return result
    elif function == '/':
        if not arglist:
            return 0
        return arglist[0] / arglist[1]
    elif function == 'cons':
        if not arglist:
            raise Exception('no value to cons')
        elif len(arglist) != 2:
            raise Exception('it has to be exactly 2 values when cons-ing')
        else:
            return (arglist[0], arglist[1])
    elif function == 'car':
        if not arglist:
            raise Exception('no value to car')
        return arglist[0][0]
    elif function == 'cdr':
        if not arglist:
            raise Exception('no value to car')
        return arglist[0][0]
    else:
        body = function_get_body(function)
        formal_args = function_get_formal_args(function)
        new_env = make_new_env(env, bind_vars(formal_args, arglist))
        return my_eval(body, new_env)

If you do have one then congratulations to you, because this is already a working interpreter. You can load this code in the CPython REPL and try out a few programs for yourself:

>>> my_eval(('funcall', '+', [('int', 3), ('int', 4)]), [])
7
>>> my_eval(('funcall', '+', [('var', 'a'), ('int', 4)]), [{'a': 3}])
7
>>> my_eval(('funcall', ('lambda', ['x'], ('funcall', '+', [('var', 'x'), ('int', 3)])), [('int', 4)]), [])
7

You can also try out expressions like (((lambda (x) (lambda (x) x)) 3) 4) which will be evaluated to 4 instead of 3 because of the shadowing:

>>> my_eval(('funcall', ('funcall', ('lambda', ['x'], ('lambda', ['x'], ('var', 'x'))), [('int', 3)]), [('int', 4)]), [])
4

Now let's evaluate the following program:

((lambda (f1)
    ((lambda (x)
	(f1 3)) 4))
    ((lambda (x) (lambda (y) (+ x y))) 3))

which is roughly:

f1 = (lambda x: lambda y: x + y)(3)
(lambda x: f1(3))(4)

which "should be" evaluate to 6, unless you try to do the same using our new interpreter:

>>> my_eval(('funcall', ('lambda', ['f1'], ('funcall', ('lambda', ['x'], ('funcall', ('var', 'f1'), [('int', 3)])), [('int', 4)])), [('funcall', ('lambda', ['x'], ('lambda', ['y'], ('funcall', '+', [('var', 'x'), ('var', 'y')]))), [('int', 3)])]), [])
7

Shouldn't it be 6? Why is that the case? Let's see what ((lambda (x) (lambda (y) (+ x y))) 3) evaluates to:

>>> my_eval(('funcall', ('lambda', ['x'], ('lambda', ['y'], ('funcall', '+', [('var', 'x'), ('var', 'y')]))), [('int', 3)]), [])
('lambda', ['y'], ('funcall', '+', [('var', 'x'), ('var', 'y')]))

Just like you might have expected, it's (lambda (y) (+ x y)); what you might not have expected is it's this anonymous function and this anonymous function only: it does not carry the information of "x should be 3", and when it gets evaluates our interpreter searches for the newest binding of x, which has the value 4. This behaviour is called "dynamic scope": every time a variable is looked up, it's looked up in the environment that's present at the moment in computer science, the word "dynamic" roughly means "when the program is running", hence the name. In the case above the binding presented at that particular moment associated x with 4, so we get a 7.

The original LISP implementation uses dynamic scope, while most modern-day languages (including Python), as we all have known, have a different behaviour called "lexical scope", which does… what we have already know it does when it comes to functions as first-class values. Modern LISP dialects often have both.

It's easy to fix this problem: we add the current environment to every function when we evaluate it, resulting in the following version of implementation:

# an anonymous function is now `('lambda', vars, body, env)`.
def function_get_assoc_env(term):
    return term[3]
# ...
def my_apply(function, arglist, env):
    # ...
    else:
        body = function_get_body(function)
        formal_args = function_get_formal_args(function)
        fun_env = function_get_assoc_env(function)
        # notice that we create the new environment based on the function's own environment
        # instead of the one passed in as argument.
        new_env = make_new_env(fun_env, bind_vars(formal_args, arglist))
        return my_eval(body, new_env)

We are not going to directly write the environment value in our AST, so this is also needed:

def my_eval(term, env):
    # ...
    elif ast_type(term) == 'lambda':
        # as I've said, the actual details varies according to how you represent the values.
        if len(term) <= 3:
            # manually adding an env
            return (*term, env)
        return term

Let's try it out again:

>>> my_eval(('funcall', ('lambda', ['f1'], ('funcall', ('lambda', ['x'], ('funcall', ('var', 'f1'), [('int', 3)])), [('int', 4)])), [('funcall', ('lambda', ['x'], ('lambda', ['y'], ('funcall', '+', [('var', 'x'), ('var', 'y')]))), [('int', 3)])]), [])
6

Remember, it's only this easy because CPython handles all the memory management chore for us: doing this, as well as other "simple" stuff, all come with a cost which (at least in some cases) we can't just pretend that they don't exist; but did I mentioned that you should always keep a "toy meter" when working on your own projects? This is definitely a toy, so even if we rely too much on CPython's garbage collector we are mostly good (unless the GC somehow broke down; that's a whole different story). There are also different techniques dealing with these "embedded" functions including lambda lifting, which basically "lift"s the functions defined inside to the top-level, adding free variables as its arguments along the way; but that's a whole different technique, it's for a different time, we won't use it now.

This is also where our earlier decision about how to represent an environment comes into play: remember that we used a 2-tuple instead of a single dict? It's basically the most direct way to implement all the environment-related behaviour that we want: when we going back and forth between function calls we need to creating and restore environments conveniently (and as efficient as possible). Creating environments is really not an issue; it's restoring old environments when returning from a function that matters. By using the 2-tuple method, we don't restore the old environment - we don't need to restore them, because new environments are created brand-new & not effecting the old one; if we don't need the new environment anymore, we just throw it away and let CPython's GC to do its thing.

IO, other interfaces & primitives

For a better demonstration in the future, it's the time to add in more primitives.

Logical operators

By logical operators I mean and, or and not. We actually can't treat the first two as normal primitive functions: we need to implement the "short-cut" behaviour, which means we have to handle them before their arguments get evaluated; not, in the other hand, is OK to be handled as primitive function, because its arguments has to be evaluated anyway.

def and_get_args(term):
    return term[1:]
def or_get_args(term):
    return term[1:]
def my_eval(term, env):
    # ...
    elif ast_type(term) == 'and':
        result = True
        arglist = and_get_args(term)
        for arg in arglist:
            result = my_eval(arg, env)
            if not result:
                return False
        # We also want to have the behaviour where `and` returns the value of the last arguments
        # when it's all true value. If you want to make `and` only return boolean values,
        # change `result` to `True`.
        return result
    elif ast_type(term) == 'or':
        result = False
        arglist = or_get_args(term)
        for arg in arglist:
            result = my_eval(arg, env)
            # If you want `or` to return just the boolean value instead, change `return result`
            # to `return True`.
            if result:
                return result
        return False

def my_apply(function, arglist, env):
    # ...
    elif function == 'not':
        return not arglist[0]

Python interop

You can also implement Python interop, yet implementing & depending on language-specific interfaces is generally not a good idea unless you have enough reasons (e.g. it's C/JavaScript interop interface that you're trying to make). If you do want to add this anyway, you'll need to know how stuff in Python actually works (e.g. the getattr function, etc.)

def my_apply(function, arglist, env):
    # ...
    # We weill allow hyphens to be used as part of identifiers, don't worry.
    elif function == 'py-import':
        # This is for demonstration only so I left out some necessary guarding here - you
        # might want to add the guardings to your own version.
        return __import__(arglist[0])
    elif function == 'py-getattr':
        return getattr(arglist[0], arglist[1])
    elif function == 'py-index':
        return arglist[0].__getitem__(arglist[1])
    elif function == 'py-call':
        return (arglist[0])(*arglist[1:])
    # ...and other Python-related stuff too.
    # But don't go too far and define all the built-in objects this way - we can define them
    # *inside* our language once we have the construct above; for example, the expression
    # `(py-getattr (py-import "builtin") "list")` gives you the access to the `list` function
    # in Python; other stuff can be retrieved in a similar way.

You can even provide an interface to your interpreter itself in the same way:

def my_apply(function, arglist, env):
    # ...
    elif function == 'apply':
        return my_apply(arglist[0], arglist[1:], env)
    elif function == 'eval':
        return my_eval(arglist[0], env)
    elif function == 'apply-with-env':
        # (apply-with-env ENV FUNCTION ARGLIST)
        return my_apply(arglist[1], arglist[2:], arglist[0])
    elif function == 'eval-with-env':
        # (eval-with-env ENV TERM)
        return my_eval(arglist[1], arglist[0])
    # ...and so on

Relational operators, IO and other stuff

These are essentially the same as handling other primtives, just add something like this into your interpreter:

def my_apply(function, arglist, env):
    # ...
    elif function == 'print':
        for arg in arglist:
            print(arg)
        return None
    elif function == 'input':
        for arg in arglist:
            print(arg)
        return input()
    elif function == '>':
        # Again this is for demonstration only so I left out some necessary guarding here.
        # You might want to add the guardings to your own version.
        return arglist[0] > arglist[1]
    elif function == '<':
        return arglist[0] < arglist[1]
    elif function == '=':
        # We will use another identifier for  the assignment operator - the equal symbol is
        # reserved for testing equality here.
        return arglist[0] == arglist[1]
    # ...and so on.

You might also want to add some built-in predicate as well:

def my_apply(function, arglist, env):
    # ...
    # We will allow question marks to be used as part of identifiers as well, don't worry.
    elif function == 'int?':
        return type(arglist[0]) == int
    elif function == 'str?':
        return type(arglist[0]) == str
    # ...and so on.

Special forms

Top-level definition

You might have already tired of throwing lambda everywhere. Fortunately, up to this point, we have enough tools and experiences to implement our own def for our own LISP dialect. This is actually very easy once you've decided how would you like to represent them in your AST. Just one more thing to mention before we start adding def: defining a function is in a way no more than binding a variable with an anonymous function.

# `def` directly inserts new binding into the current environment.
def insert_var(var, value, env):
    if env:
        env[0][var] = value

# ...

# some getters.
# a `def` form here is written as `(def Varname Value)`, or `("def", Varname, Value)`
# in Python.
def def_get_varname(term):
    return term[1]
def def_get_value(term):
    return term[2]

# ...
def my_eval(term, env):
    # ...
    elif ast_type(term) == 'def':
        # ('def', name, value)
        var = def_get_varname(term)
        body = def_get_value(term)
        insert_var(var, my_eval(body, env), env)
        return None

# at this point we need to have an evaluator that evaluates a *sequence* of
# expressions as well.
def my_eval_s(termlist, env):
    # this variable is here in case you want to wire it to an output.
    value = None
    for term in termlist:
        value = my_eval(term, env)
    return value

We can take the f1 example above as an example, which now can be written as:

(def f ((lambda (x) (lambda (y) (+ x y))) 3))
((lambda (x) (f1 3)) 4)

And now we can see we have a working def form:

>>> empty_env = ({}, None)
>>> my_eval_s([('def', 'f1', ('funcall', ('lambda', ['x'], ('lambda', ['y'], ('funcall', '+', [('var', 'x'), ('var', 'y')]))), [('int', 3)])), ('funcall', ('lambda', ['x'], ('funcall', ('var', 'f1'), [('int', 3)])), [('int', 4)])], empty_env)
6
>>> empty_env
({'f1': ('lambda', ['y'], ('funcall', '+', [('var', 'x'), ('var', 'y')]), ({'x': 3}, (...)))}, None)

Conditions

We haven't introduced conditions yet; technically we already have them - did I mention that our language is already Turing-complete after having first-class anonymous functions and function applications? Yet if we try do create some kind of "if" constructs it will be messy & awkward.

Time to add in more special forms. You can choose to implement cond (which is like if ... elif ... else in Python) or if (which is… well, if), they are sort of like the exact same thing written differently:

def if_get_cond(term):
    return term[1]
def if_get_then(term):
    return term[2]
def if_get_else(term):
    return term[3]
# or you can do both `if` and `cond`.
def cond_get_clause_list(term):
    return term[1:]
def my_eval(term, env):
    # ...
    # ("if", cond, then, else)
    elif ast_type(term) == 'if':
        evaluated_cond = my_eval(if_get_cond(term), env)
        return my_eval(if_get_then(term) if evaluated_cond else if_get_else(term), env)
    # ("cond", (cond, then), (cond, then), ...)
    elif ast_type(term) == 'cond':
        clause_list = cond_get_clause_list(term)
        for cond, body in clause_list:
            if my_eval(cond, env):
                return my_eval(body, env)
        return None

let

let forms are used to construct local bindings, they work (at least in a way) like local variables. There are essentially two forms of let binding: let (sometimes you'll see let*; that's syntactic sugar for multiple nested let form); and letrec which lets you define local mutual recursive functions, hence the name. The former is very easy: (let (var1 value1) (var2 value2) ... body) is just a syntactic sugar of the ((lambda (var1 var2 ...) body) value1 value2 ...) pattern we just saw earlier:

def let_get_binding_list(term):
    return term[1:-1]
def let_get_body(term):
    return term[-1]
def my_eval(term, env):
    # ...
    elif ast_type(term) == 'let':
        binding_list = let_get_binding_list(term)
        evaled_binding = {}
        for var, val in binding_list:
            evaled_binding[var] = my_eval(term, env)
        new_env = (evaled_binding, env)
        return my_eval(let_get_body(term), new_env)

I've just said that let* is syntactic sugar for multiple nested let; we can also treat it like it's not as long as it's working as intended. The implementation is mostly the same, except for the new_env part: we have to create a new environment for every "layer" of let binding:

def letstar_get_binding_list(term):
    return term[1:-1]
def letstar_get_body(term):
    return term[-1]
def my_eval(term, env):
    # ...
    elif ast_type(term) == 'let*':
        binding_list = let_get_binding_list(term)
        body_env = env
        for var, val in binding_list:
            binding = {}
            binding[var] = my_eval(term, body_env)
            body_env = (binding, body_env)
        return my_eval(let_get_body(term), body_env)

The necessity of letrec needs a little bit of explanation: you don't need letrec in Python, because local bindings refer to the same scope:

def f():
    is_odd = lambda x: x != 0 and is_even(x - 1)
    is_even = lambda x: x == 0 or is_odd(x - 1)
    # this works because when evaluating the body of `is_odd` or `is_even` Python will search
    # within the scope of f(); by the time of the scope being searched both definition of
    # `is_odd` and `is_even` are already bound.
    print(is_odd(3))

But we can't simply achieve the same thing with either let or let* in our LISP dialect:

(def f ()
    (let (is_odd (lambda (x) (and (not (= x 0)) (is_even (- x 1))))
	 (is_even (lambda (x) (or (= x 0) (is_odd (- x 1))))
	 (print (is_odd 3))))))

Try to evaluate this and you'll get an error. Add the following code at the end of your interpreter:

test = \
('def', 'f', ('lambda', [],
    ('let',
        ('is_odd', ('lambda', ['x'],
            ('and',
                ('funcall', 'not', [('funcall', '=', [('var', 'x'), ('int', 0)])]),
                ('funcall', ('var', 'is_even'), [('funcall', '-', [('var', 'x'), ('int', 1)])])))),
        ('is_even', ('lambda', ['x'],
            ('or',
                ('funcall', '=', [('var', 'x'), ('int', 0)]),
                ('funcall', ('var', 'is_odd'), [('funcall', '-', [('var', 'x'), ('int', 1)])])))),
        ('funcall', 'print', [('funcall', ('var', 'is_odd'), [('int', 3)])]))))

empty_env = ({}, None)

At the REPL:

>>> my_eval_s([test], empty_env)
>>> my_eval(('funcall', ('var', 'f'), []), empty_env)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  ...
  File "interpreter.py", line 79, in my_eval
    raise Exception(f'not_found: {varname}')
Exception: not_found: is_even

It's because is_odd is not bound when is_even is bound, and vice versa; is_odd and is_even have different environments which only contain the old, "parent" environment and a binding list containing only themselves. To make a program like this to work correctly, you have to provide a construct for creating a new, "shared" environment, which is what letrec (usually) does.

And of course it takes more effort to implement:

def letrec_get_binding_list(term):
    return term[1:-1]
def letrec_get_body(term):
    return term[-1]
def binding_get_varname(binding):
    return binding[0]
def binding_get_value(binding):
    return binding[1]
def my_eval(term, env):
    # ...
    elif ast_type(term) == 'letrec':
        binding_list = letrec_get_binding_list(term)
        mapping = {}
        # Basically what is happening here is we now first create the new environment with an
        # *empty* new binding list and use this newly-created environment to evaluate the bound
        # values. Because the new binding list is empty, looking up any variable using this
        # new environment will get the same result as using the old environment.
        # Don't worry about lambdas; in our interpreter they're left untouched when evaluating
        # as long as they're not applied to something.
        let_env = (mapping, env)
        for binding in binding_list:
            varname = binding_get_varname(binding)
            value = binding_get_value(binding)
            mapping[varname] = my_eval(value, let_env)
        let_body = letrec_get_body(term)
        return my_eval(let_body, let_env)

You can try the above example again after changing 'let' to 'letrec':

# in your interpreter:
test = \
('def', 'f', ('lambda', [],
    # notice that 'let' is changed to 'letrec'
    ('letrec',
        ('is_odd', ('lambda', ['x'],
            ('and',
                ('funcall', 'not', [('funcall', '=', [('var', 'x'), ('int', 0)])]),
                ('funcall', ('var', 'is_even'), [('funcall', '-', [('var', 'x'), ('int', 1)])])))),
        ('is_even', ('lambda', ['x'],
            ('or',
                ('funcall', '=', [('var', 'x'), ('int', 0)]),
                ('funcall', ('var', 'is_odd'), [('funcall', '-', [('var', 'x'), ('int', 1)])])))),
        ('funcall', 'print', [('funcall', ('var', 'is_odd'), [('int', 3)])]))))

# in REPL
>>> my_eval_s([test], empty_env)
>>> my_eval(('funcall', ('var', 'f'), []), empty_env)
True

Now, you might say, what if we only include letrec and don't implement let? If you want, you can; but this decision has its flaws. Check out the following example:

;; we bound `a` and `b`
(letrec (a 3) (b 4)
    ;; and try to swap their value here.
    (letrec (b a) (a b)
	(/ a b)))

You might expect the (/ a b) part will evaluate to (/ 4 3), but no: it will be evaluate to 1:

>>> my_eval(
... ('letrec', ('a', ('int', 3)), ('b', ('int', 4)),
...     ('letrec', ('b', ('var', 'a')), ('a', ('var', 'b')),
...         ('funcall', '/', [('var', 'a'), ('var', 'b')]))),
... ({}, None)
... )
1.0
>>>

This is because no matter in what order you handle the binding list in a letrec, a and b will be bound to the same value in the body of the second letrec. In the second letrec, a and b are meant to be able to access each other, thus one of them will be receiving the other one's bound value.

Assignment

Since we already have destructive update when we implement the def special form (remember I did not have any guarding code like raising exceptions when the variable/function was already defined), assignment should be pretty straightforward:

# the name "setbang" is actually "set!" - the exclamation mark is normally pronounced as "bang".
# this name comes from Scheme, a very famous LISP dialect.
# this is essentially the same as `def` but should be without the guarding (if your
# implementation has any).
def setbang_get_varname(term):
    return term[1]
def setbang_get_value(term):
    return term[2]
def my_eval(term, env):
    # ...
    elif ast_type(term) == 'set!':
        var = setbang_get_varname(term)
        body = setbang_get_value(term)
        insert_var(var, my_eval(body, env), env)
        return None

Sequential execution

A neat little feature that I think it's good to add. In Scheme, there's a thing called begin, which evaluates all its arguments from left to right, and returns the value of the last argument. While this can be easily achieved if our language has vararg function support, we didn't implement that feature either; if we want to add begin, we can only directly add another branch in my_eval like this:

def begin_get_body(term):
    return term[1:]

# ...

def my_eval(term, env):
    # ...
    elif ast_type(term) == 'begin':
        body = begin_get_body(term)
        result = None
        for expr in body:
            result = my_eval(expr, env)
        return result

A working parser (maybe)

Alright, no more fun semantics-related stuff, we are now finally left with the most tedious part of writing an interpreter. You might have already been tired of manually writing tags for your AST (you might have thought it would be better if you had used `class`es; it might, but from my personal experiences of manually writing ADT constructors in Haskell it's actually the same. If you have to tag the AST yourself, it will be tiring no matter what kind of tag you use).

There's one last thing before we start writing a parser: by far our AST doesn't really fit well in traditional LISP S-expression. To see why, let's see what a typical S-expression definition will look like:

// grammar #1
SExpr ::= Atom                      (Atom)
	| "(" SExpr "." SExpr ")"   (Pair)
	| "(" SExpr* ")"            (List)

The Pair rule is used to construct "grammatical pair": note that in LISP, "grammartical" lists are constructed from grammatical pairs, e.g. (1 2 3 4) is actually (1 . (2 3 4)) and ultimately (1 . (2 . (3 . (4 . nil)))) (where nil is the special constant denoting an empty list); in some LISP dialect you can define functions with variable length arguments like this:

(define (varag-f a b . c)
    ;; The caller must provide values for `a` and `b`; but he can also provide more, i.e.
    ;; calling `(vararg-f 1 2)` and `(vararg-f 1 2 3)` and etc. are valid, but `(vararg-f 1)`
    ;; and `(vararg-f)` is not. Values after those being bound for `a` and `b` will be "collected"
    ;; as a list which will be bound to `c`.
    ;; The following line does exactly what you think it does.
    (begin
        (display a) (display "\n")
        (display b) (display "\n")
        (display c) (display "\n")))
    (+ a b . c))

But have no fear: the language the grammar above recognizes can be recognized by the grammar below:

// grammar #2
SExpr ::= Atom             (Atom)
	| "."              ("Special component")
	| "(" SExpr* ")"   (List)

(Of course grammar #2 recognizes a superset of the one recognized by grammar #1 as it accepts strings like "(. . .)" which is illegal in grammar #1.)

The key is, we can always have a "second-layer", a "second-pass" where there is a separate "syntax tree" and move the burden of correctly handling these outliers to the "upper-layer" part. Don't worry about performance, you're using Python, and once again this is meant to be an educational toy, you'll be better off if you stop worrying too much about performances. From now on we'll be using this definition of S-expression:

SExpr ::= Atom           (Atom)
	| "(" SExpr* ")" (List)

And for simplicity neither vararg definition nor grammatical pair is allowed; those are saved for a different time.

The lexer

It is normally a good idea to separate the tokenization process and the "actual" parsing process (mostly for more flexibility), but the language is way too simple I just didn't bother having them seperated. Here are the regular expressions (used with the built-in re module) I used:

# `REGEX_FLOAT` must be checked first because it overlaps with `REGEX_INT`
REGEX_FLOAT = re.compile(r"[0-9]+\.[0-9]+")
REGEX_INT = re.compile(r"[0-9]+")
# I deliberately make it recognizes a subset of Python string literal so that I can directly use `eval`.
REGEX_STRING = re.compile("\"(?:\\\\n|\\\\t|\\\\r|\\\\\"|\\\\x[\\da-fA-F]{2}|[^\"\\t\\r\\n\\\\])*\"")
# You might have to change it to include any characters that primitives have to prevent errors.
REGEX_IDENTIFIER = re.compile(r"[\w+*/%?<>=:,.-]+")

The parser

Just do recursive descent. It's overkill to use lex/yacc or ANTLR, just a simple recursive descent parser will do.

import re
REGEX_FLOAT = re.compile(r"[0-9]+\.[0-9]+")
REGEX_INT = re.compile(r"[0-9]+")
REGEX_STRING = re.compile("\"(?:\\\\n|\\\\t|\\\\r|\\\\\"|\\\\x[\\da-fA-F]{2}|[^\"\\t\\r\\n\\\\])*\"")
REGEX_IDENTIFIER = re.compile(r"[\w+*/%?<>=:,.-]+")

# The key takeaway here is parsers have the type of String -> None | (Result * String); they return a 2-tuple containing
# the result & the rest of the string on success, and return `None` on failure. In a more sophisticated parser this will
# be a tagged union combined with an type representing syntax error and the said 2-tuple, e.g. ParseC library in Haskell,
# if I remembered correctly, uses `Either String Result` where the `String` part is used to store error messages.
def parse_atom(string):
    # It's actually not very good to return stuff like this. You might want to have them all stated more clearly.
    # Notice that I put `parse_float` before `parse_int`; it has to be in this order because what these two recognizes
    # overlap.
    return parse_float(string) or parse_int(string) or parse_string(string) or parse_identifier(string)

def parse_float(string):
    preres = REGEX_FLOAT.match(string)
    if preres:
        taken_string = preres.group()
        rest = string[len(taken_string):]
        return (('float', float(taken_string)), rest)
    return None

def parse_int(string):
    preres = REGEX_INT.match(string)
    if preres:
        taken_string = preres.group()
        rest = string[len(taken_string):]
        return (('int', int(taken_string)), rest)
    return None

def parse_string(string):
    preres = REGEX_STRING.match(string)
    if preres:
        taken_string = preres.group()
        rest = string[len(taken_string):]
        # Note that `eval` is used here instead of `str` because `str` does not do anything on string.
        return (('str', eval(taken_string)), rest)
    return None

def parse_identifier(string):
    preres = REGEX_IDENTIFIER.match(string)
    if preres:
        taken_string = preres.group()
        rest = string[len(taken_string):]
        return (taken_string, rest)
    return None

def skip_whitespace(string):
    # ...yep. We ignore all whitespaces.
    return string.lstrip()

def parse_list(string):
    # We do it in some kind of a "two-phase" fashion.
    if string.startswith("("):
        # This is phase 1: we process the input string into a "raw" syntax tree
        string = skip_whitespace(string[1:])
        result = []
        while string:
            buf = parse_atom(string)
            if not buf:
                buf = parse_list(string)
            if not buf:
                break
            result.append(buf[0])
            string = skip_whitespace(buf[1])
        if not string.startswith(")"):
            # if the code reaches here, the parenthesis is not balanced.
            raise Exception(f'syntax error at {string[:10] if len(string) > 10 else string}')
        return (result, string[1:])
    else:
        return None
def parse_list_phase2(result):
    # This is phase 2: we reconstruct the syntax tree into proper AST.
    # Normally you would want to add more guarding here - a lot of guarding.
    if type(result) == list:
        if len(result) > 1:
            if result[0] == 'lambda':
                return ('lambda', result[1], parse_list_phase2(result[2]))
            elif result[0] == 'def':
                return ('def', result[1], parse_list_phase2(result[2]))
            elif result[0] == 'if':
                return ('if', parse_list_phase2(result[1]), parse_list_phase2(result[2]), parse_list_phase2(result[3]))
            elif result[0] == 'cond':
                return ('cond', *((x[0], parse_list_phase2(x[1])) for x in result[1]))
            elif result[0] in ['let', 'let*', 'letrec']:
                return (result[0], *((x[0], parse_list_phase2(x[1])) for x in result[1:-1]), parse_list_phase2(result[-1]))
            elif result[0] in ['and', 'or']:
                return (result[0], *(parse_list_phase2(x) for x in result[1:]))
            elif result[0] in ['set!']:
                return ('set!', result[1], parse_list_phase2(result[2]))
            elif result[0] == 'begin':
                return ('begin', *(parse_list_phase2(x) for x in result[1:]))
            else:
                return ('funcall', parse_list_phase2(result[0]), [parse_list_phase2(x) for x in result[1:]])
    elif type(result) == str:
        if result in [
            '+', '-', '*', '/',
            'cons', 'car', 'cdr',
            'not',
            'py-import', 'py-getattr', 'py-index', 'py-call',
            'apply', 'eval', 'apply-with-env', 'eval-with-env',
            'print', 'input',
            '>', '<', '=',
            'int?', 'str?', 'pair?'
        ]:
            return result
        else:
            return ('var', result)
    else:
        return result

def parse_sexpr(string):
    res = parse_atom(string)
    if res:
        return res
    res = parse_list(string)
    if res:
        return (parse_list_phase2(res[0]), res[1])
    return None

We now have a parser that recognizes single S-expression; we need one that recognizes multiple S-expression as well:

def parse_source(string):
    result = []
    while string:
        buf = parse_sexpr(string)
        if not buf and string:
            # if there's still un-parsed string but our parser cannot recognize anything out of it
            raise Exception(f'grammar error at {string[:10] if len(string) > 10 else string}')
        result.append(buf[0])
        string = skip_whitespace(buf[1])
    return result

Let's test them out a little bit:

>>> parse_sexpr("3")
(('int', 3), '')
>>> parse_sexpr("3.234")
(('float', 3.234), '')
>>> parse_sexpr('"dfsdfsdf"')
(('str', 'dfsdfsdf'), '')
>>> parse_sexpr('(let (a 3) (b 4) c)')
(('let', ('a', ('int', 3)), ('b', ('int', 4)), ('var', 'c')), '')
>>> parse_sexpr('(a 3 4)')
(('funcall', 'a', [('int', 3), ('int', 4)]), '')
>>> parse_sexpr('(def myfunc (lambda (x) (+ x 3)))')
(('def', 'myfunc', ('lambda', ['x'], ('funcall', '+', [('var', 'x'), ('int', 3)]))), '')
>>> 

Looks good.

The REPL

What's REPL? It's an acronym for "read-eval-print loop", roughly speaking it's the ">>> " thing where most Python book will tell you that you can use Python as a calculator. It reads Python, then it evaluates it, then it prints the result, and it does all of this in a loop: after printing the result it starts to wait for your input again, starting another read-evaluate-print cycle. Before going for a REPL you might want to setup some code handling sys.argv so that you can have an "input-only" interpreter and a REPL:

import sys

# ...

# usage:
#     minilisp [input-source-file]          - run the file as a script.
#     minilisp --repl [input-source-file]   - start the REPL.
#     minilisp --help                       - display this help message.
if __name__ == '__main__':
    if sys.argv[1] == '--help':
        print_usage()
    elif sys.argv[1] == '--repl':
        # Of course you need to add guarding for corner cases like the provided
        # file name does not point to any existing file - this piece of code
        # is for demonstration only.
        loading_file_name = sys.argv[2] if len(sys.argv) >= 3 else None
        if loading_file_name:
            with open(loading_file_name, 'r') as f:
                loading_source = f.read()
            my_eval_s(parse_source(loading_source), empty_env)
        repl()
    else:
        loading_file_name = sys.argv[1] if len(sys.argv) >= 2 else None
        if loading_file_name:
            with open(loading_file_name, 'r') as f:
                loading_source = f.read()
            my_eval_s(parse_source(loading_source), empty_env)
        else:
            print_usage()
# ...and other accompanying stuff.

Writing a REPL is… easy:

_GLOBAL_ENV = ({}, None)

def read_expr():
    # The `.strip` method call below is for checking blank lines.
    # When the user input a blank line, the REPL should pretend that never happened
    # and do nothing. 
    expr = input('> ').strip()
    if not expr:
        raise Exception()
    return parse_sexpr(expr)[0]

def repl():
    while True:
        try:
            expr = read_expr()
        except EOFError:
            break
        except Exception as e:
            # You might also want to have a better error handling procedure, e.g. printing the error message
            print(f'Internal error: {str(e.args)}', file=sys.stderr)
            continue
        result = my_eval(expr, _GLOBAL_ENV)
        print(result)
# It's literally a Read-Eval-Print Loop!

You might want to take some additional measures to support multi-line. A crude version will look something like this:

def repl():
    buffer = []
    while True:
        try:
            user_input = input('> ')
            paren_balance = calc_paren_balance(user_input)
            if paren_balance > 0:
                buffer.append(user_input)
                continue
            elif paren_balance < 0:
                print('syntax error', file=sys.stderr)
                buffer = []
                continue
            else:
                buffer.append(user_input)
                input_string = '\n'.join(buffer)
                parsed_input = parse_sexpr(input_string)[0]
                result = my_eval(parsed_input, _GLOBAL_ENV)
                print(result)
        except EOFError:
            break
        except:
            # You might also want to have a better error handling procedure, e.g. printing the error message
            buffer = []
            continue
_PAREN_BALANCE = 0
def calc_paren_balance(input_str):
    global _PAREN_BALANCE
    for char in input_str:
        if char == '(':
            _PAREN_BALANCE += 1
        elif char == ')':
            _PAREN_BALANCE -= 1
            if _PAREN_BALANCE < 0:
                print('syntax error', file=sys.stderr)
                raise Exception()
    return _PAREN_BALANCE

A little bit of testing:

% python interpreter.py --repl
> (+ 3 4)
7
> (+
> 3
> 4)
7
> (()))
syntax error
> 

This is file hanoi.minilisp. Run it like python3 minilisp.py hanoi.minilisp:

(def to-string (lambda (x) (py-call (py-getattr (py-import "builtins") "str") x)))
(def to-int (lambda (x) (py-call (py-getattr (py-import "builtins") "int") x)))
(def hanoi (lambda (n from to via)
    (if (= n 1)
	(print (+ "Move " from " to " to))
	(begin
	    (hanoi (- n 1) from via to)
	    (print (+ "Move " from " to " to))
	    (hanoi (- n 1) via to from)))))
(hanoi (to-int (input)) "A" "C" "B")

…input 3 and press enter, you will be presented with the following result:

Move A to C
Move A to B
Move C to B
Move A to C
Move B to A
Move B to C
Move A to C

Looks good.

Let's put all these tiny bits together

My version of finished interpreter can be found here. Not all primitives have been included, but you can easily add your own.

The end (or not)

This article is definitely getting WAY too long, much longer than I have formerly had in my mind; I have to left out some feature I think one should include in his first LISP interpreter, and most features beyond these requires more PLT & compiler-related knowledge, a better overall understanding of how these things work - especially, how these things work together. Anyway, metacircular is easy, at least getting started is, it's no big deal.

Programming in your LISP dialect

Yes, I said it, it's Turing-complete (if you added enough features). Have you read the paper Lambda: the Ultimate Imperative yet?

OOP

You can have OOP right now if you really want it. Imagine you're a first-year college student pursuing a Bachelor's degree & you're at your first CS course where your teacher teaches you Java. You have something like this:

class Dog {
    private String _name;
    public Dog(String name) {
        this._name = name;
    }
    public getName() {
        return this._name;
    }
    public setName(String newName) {
        this._name = newName;
    }
    public bark() {
        System.out.println("(" + this._name + " barks)");
    }
}

In your newly-implemented LISP dialect you can do it like this:

(def Dog (lambda (name)
    (lambda (msgHead msgBody)
	(cond
	    ((= msgHead "getName") name)
	    ((= msgHead "setName") (set! name (car msgBody)))
	    ((= msgHead "bark")
		(print "(" name " barks)"))))))

…and then code like this:

// ...
Dog dog = new Dog("Winnie");
dog.setName("Rudolf");
dog.bark();

…can be written like this (or similar, if your LISP dialect has different primitives):

(let (dog (Dog "Winnie"))
    (begin (dog "setName" (cons "Rudolf" nil))
	   (dog "bark" nil)))

Normally one will define all OOP things in macros to hide all the boilerplate & making it more programmer-friendly (which we can't because our LISP dialect has no macro abilities). This is only a demonstration: it's not like you can't do OOP in a seemingly "FP" setting. (This is possible because our LISP is "impure", though.)

Back


© Sebastian Lin 2019 All Rights Reserved.
Content on this page is distributed under the CC BY-NC-SA 4.0 license unless further specified.
Last update: 2019.11.26