10 Interpreters

\(\newcommand{\la}{\lambda} \newcommand{\Ga}{\Gamma} \newcommand{\ra}{\rightarrow} \newcommand{\Ra}{\Rightarrow} \newcommand{\La}{\Leftarrow} \newcommand{\tl}{\triangleleft} \newcommand{\ir}[3]{\displaystyle\frac{#2}{#3}~{\textstyle #1}}\)

An interpreter is code that takes another program as data and produces what that program would produce if it were run. The program-as-data could be in a very different language than the one that the interpreter is written in; for example, the interpreter could be written in Racket, but it interprets programs written in Python. Another technique for carrying out this task is a compiler, which in our example would translate the Python program (while preserving its behaviour) into yet another language that one has the means to run directly (often the machine language of a specific hardware processor, or a language that can be run in a Web browser, such as JavaScript).

Interpreters and compilers can be used to extend the range of languages in which we can write code. But if we want to explore them in our current context, we’ll need to define a suitably rich second language. To save us that work, we’re going to interpret Racket itself (or something close to it). We will develop a series of interpreters for a tiny language we will call Faux Racket (FR). More precisely, we will start with an even tinier subset of FR and gradually grow the language and its capabilities. We start with the arithmetic expressions we discussed in the Trees chapter.

There are other reasons to interpret the language one is working in. Implementing a language feature can give us a better understanding of its meaning and design choices than simply using an existing implementation. It can also provide insight into how existing implementations work (though DrRacket and other industrial-strength functional programming language implementations are considerably more sophisticated than the simple interpreters we will see here). With a small interpreter, we can vary choices and try different designs to see what impact such changes might have. The techniques involved in writing an interpreter can prove useful in applications that involve giving the user capability to script or automate actions using a domain-specific language. The ideas we will see can be refined for use in formal descriptions of the semantics of programming languages and in formal logic.

10.1 Evaluating arithmetic expressions

Here is the grammar for arithmetic expressions.

The expression '(* (+ 1 2) (+ 3 4)) satisfies the above grammar, and, as a Racket value, has a structure that mirrors the grammatical rules used in its construction. This leads to the simple structurally-recursive evaluator that we developed earlier.

It’s tempting as it is to stick with S-expressions (nested lists) as our primary data structure for FR. Racket, being a dialect of Scheme, is heavily optimized for the use of lists, with many convenient functions available to manipulate them. However, we sometimes want to keep additional information about subexpressions. While lists permit this, it can be awkward. Even the use of first, second, and third above is less readable than we might like, causing us to have to define synonyms. Other implementation languages do not have the convenient features of Racket, so it will be harder to transfer the ideas over.

We will keep S-expressions as the "concrete" syntax of FR (that is, an FR program will be an S-expression), but we will parse the concrete syntax (using a function parse that we will write) into a data structure known in general as an abstract syntax tree (AST). This will be built using structures (most other languages have some form of those). Here is an example of how we might represent '(* (+ 1 2) (+ 3 4)).

Our interpreter function, then, will consume an abstract syntax tree. We will maintain this general scheme (possibly adding more arguments as needed):

Writing the parser is relatively simple, though I will cheat a little by omitting error-checking.

In what follows, I will assume that this parser is augmented as needed when we grow the language; you will do this in the exercises. The evaluator then looks like this (again omitting error-checking):

Here is an example of the use of our new interpreter.

(eval (parse '(* (+ 1 2) (+ 3 4)))) \(\Rightarrow\) 21

We can now add more language features to FR and extend the interpreter to handle them. Before we do that, however, it is worth thinking about how this interpreter is not a direct implementation of the computational model that we used to define the meaning of a Racket program. Specialized to this case where we are evaluating only one expression and not a whole program, the substitution model defines a sequence of expressions, the first one being the original expression, the last one being a value, and each one in between being obtained from the previous one by one application of a reduction or rewrite rule. For example, in DrRacket’s Stepper, (* (+ 3 4) (+ 1 6)) steps to (* 7 (+ 1 6)), but in the Interactions window, it is fully evaluated to 49.

What the Interactions window does, and what our evaluator above does, is often called big-step evaluation. It takes a big step to the end result. In contrast, the Stepper does small-step evaluation. We can write a Stepper-like function for our representation, starting with a test to see whether a step can be taken, a function to take that step (which assumes that the test passes), and finally a small-step evaluator that repeatedly steps to the final value. This last function resembles the iterators we saw in the GCD and bottom-up mergesort examples of the previous chapter, and is not structurally recursive.

Intuitively, we believe that big-step evaluation and small-step evaluation give the same result. This can be proved by structural induction, but it gets progressively harder as new features are added (because they often use non-structural recursion). The reason to prefer big-step evaluation is that it is more efficient, but we’ll continue to think about small-step evaluation, which will be surprisingly useful in the second part of this flânerie.

10.2 Adding local names

The next feature we will add is the ability to bind a local name to the result of evaluating a subexpression. For simplicity, we’ll use the same syntax as Racket’s let form, but only bind a single variable at a time. Here is the grammar.

The only reason to keep the double parentheses around the binding is for compatibility with Racket. To evaluate (let ([id expr1]) expr2), the evaluator will recursively evaluate expr1, then substitute the resulting value for id in expr2 (respecting scope rules), and finally recursively evaluate the result. The evaluator is no longer structurally recursive (though the substitution is).

Exercise 53: For each of the following Racket expressions, predict what its value should be, and then check your prediction using the Interactions window.

Exercise 54: Extend the big-step arithmetic evaluator to handle let expressions as described above. Make sure you take into account what you learned from the previous exercise, and that you add appropriate error checking and reporting.

You should do this question in BSL+, to avoid features provided by ISL+ that can trivialize the exercise, and to make it clear that a very simple language can evaluate expression trees representing a more complex language. For additional challenge, further extend your evaluator to handle multiple bindings in a single let form. \(\blacksquare\)

Exercise 55: Extend the small-step arithmetic evaluator to handle let expressions. \(\blacksquare\)

10.3 Adding second-class functions

For our first try at adding functions, we will add second-class functions, as in BSL and BSL+. That is, user-defined functions are present in the program and can be applied, but cannot be passed as arguments, or created at run time. To mirror the separate nature of definitions and expressions in a Racket program, we will keep a separate list of function definitions while continuing to evaluate a single expression in the interpreter. For simplicity, our functions will have only one argument.

Here are the grammar additions for function definition and function application.

The function definitions do not appear in the program AST; instead, a separate list of function definitions is provided as a second argument to the evaluator. We need a new structure for the program AST to represent function application, and one for a function definition, containing the name of the function, the name of the variable, and the body expression.

To interpret a function application, the big-step evaluator must recursively evaluate the argument expression, look up the definition of the function being applied, substitute the value of the argument for the function parameter in the function body (respecting the scope rules) and recursively evaluate the result. Once again, this is non-structural recursion.

Exercise 56: Extend your answer to Exercise 54 to handle second-class functions. For additional challenge, handle functions with more than one argument. \(\blacksquare\)

Exercise 57: Extend your answer to Exercise 55 to handle second-class functions. \(\blacksquare\)

10.4 Adding first-class functions

As we did above with let and second-class functions above, we’ll simplify lambda in Faux Racket by allowing only a single parameter.

We also have to change the grammar rule for function application, and add one for the use of a variable. We know that let in Racket can be implemented as a simple rewrite using lambda. The same strategy works in Faux Racket also.

We can implement this rewrite in the parse function. let can be used in FR programs to name functions.

Function creation does require a new node structure type for the AST, holding the parameter and body of the lambda. Now with an FR expression of the form (f x), both f and x may be more complex expressions. To evaluate (f x), both f and x must be reduced to values by recursively applying the evaluator, and then the argument value can be substituted into the lambda body in a manner similar to before. This is exactly what is done in our computational model (the substitution model) for Racket.

Exercise 58: Extend the big-step evaluator for arithmetic expressions to handle both lambda and let in this fashion. For additional challenge, allow multiple parameters and bindings. As a more significant challenge, think about how to write recursive functions. Do you need to add additional features to enable this, or can it be done (perhaps awkwardly) with your implementation? \(\blacksquare\)

Exercise 59: Extend the small-step evaluator for arithmetic expressions to handle first-class functions. \(\blacksquare\)

10.5 Interlude: programs that don’t terminate

Putting a quote in front of a Racket expression turns it into data (an S-expression) that can be manipulated by a Racket program. This opens up many possibilities for programs that write or compute with other programs. It also lets us prove a surprising result about the limits of computation.

When this program is run, it does not produce a value, but runs forever. Can we detect behaviour like this? It turns out that we cannot, and we can prove that we cannot. Let’s start by specifying clearly what we are going to prove cannot be computed.

The function halting? we are specifying consumes a list of S-expressions sxl (representing a list of definitions in a program) and a value arg. It produces true if and only if the last function in sxl (assumed to be a function with one parameter) halts when applied to argument arg.

Our goal is to show that any attempt to complete the definition of halting? will be incorrect. Suppose someone gave us code for halting?. We can then write code that uses it. This code may seem to be doing something strange, but we’ll soon see the reason for its construction.

Let p be the list of S-expressions with the definitions of halting?, forever, and perverse. Does (perverse p) halt or not?

If (perverse p) halts, then it must not evaluate (forever 1). So (halting? p p) must be false. If halting? produces the correct answer in this case, then it must be that the last function in p (namely perverse) does not halt when applied to p. We conclude that (perverse p) does not halt, which is a contradiction.

If (perverse p) does not halt, then it must evaluate (forever 1). So (halting? p p) must be true. Thus last function in p (namely perverse) halts when applied to p. So (perverse p) halts, again a contradiction.

In either case, we can show that (halting? p p) must produce the wrong answer. There is no way to write halting? so that it is correct for all arguments.

This type of proof is called a diagonalization argument, famously used by Georg Cantor in 1891 to show that the set of subsets of the natural numbers is uncountable. The idea of applying this style of proof to computation is due to Alan Turing, from 1936, a few months after Alonzo Church published his work on the lambda calculus. Turing’s model of computation is very different from Church’s, but they are equivalent in power. Both have been influential in the development of computer science.

The halting problem can be used to show that most questions asked about programs are uncomputable. It can even be used to show that questions that don’t seem to involve programs at all are uncomputable. For example: whether or not a set of polynomial equations has an integer solution is uncomputable. We are still waiting for a similar proof to show that some "natural" problem whose solution is easily checkable cannot be solved efficiently.

10.6 Deferring substitution

Our computational model for Racket implements function application by substituting the argument value for the formal parameter of the function everywhere in the body expression of the function. But each substitution requires the whole body AST to be traversed, requiring time proportional to the number of nodes. Where the formal parameter occurs, it occurs at a leaf of the AST, and it may not occur very often, or may be in a subtree that is later pruned without being evaluated (for example, in an unasked question or unevaluated answer of a cond). Intuitively, this is too much work.

What we can do is defer the substitution until it is necessary. The idea is for the evaluator to record, in some data structure, the binding between the name of the formal parameter and the value of the argument, and then carry on with the evaluation of the expression. When the evaluator encounters a variable (left as a name), it looks up the associated value in the data structure, thereby performing the deferred substitution.

The data structure is, in this context, called an environment. There are many implementation possibilities, but we will use the simplest one, a list of name-value pairs. The environment is added as an accumulative parameter to the evaluator. To explore this idea, we’ll go back to the first time we used substitution, which was when adding the let form to the big-step arithmetic expression evaluator.

To evaluate (let [(var exp)] body), the environment-passing interpreter must add a binding for var to the environment (it is bound to the value of exp when evaluated), and then evaluate body in the augmented environment. If a name is reused, the previous binding to that name should be shadowed. We could remove it from the environment, or we could leave it on the list and simply cons the new binding information onto the front. This means that adding a new binding takes constant time, at the cost of potentially longer lookups because of longer lists containing irrelevant elements.

Exercise 60: Add environments to the big-step arithmetic evaluator to handle let expressions. \(\blacksquare\)

We add second-class functions in a manner similar to what we did above, but we must be careful about what environment to use. To evaluate a function application, we evaluate the argument in the current environment, look up the function name in the list of definitions, and then evaluate the body expression of the function in an environment. But what environment?

That last environment shouldn’t have anything to do with the current environment that was passed as an argument to the evaluator. The definitions are supposed to be at the top level, not local. The environment we need to use to evaluate the substituted-into body expression should have only a single binding in it, of the parameter name to the argument value.

Exercise 61: Add environments to your answer to exercise 60 to handle second-class functions. \(\blacksquare\)

We need to keep this lesson in mind when adding first-class functions. I’ll first describe an incorrect implementation, because it matches what was done in the original LISP interpreter. By the time the mistake was realized, people had learned to depend on the alternate behaviour, and it took many years to sort it out.

The incorrect implementation declares a lambda to be a value, and simply preserves its AST until it is used. When a lambda is applied, its argument is evaluated in the current environment, and then the body expression of the lambda is evaluated in the current environment extended with a binding of the parameter to the argument value.

What we saw just above should make you suspicious of that last evaluation. The current environment should not be used. But an environment containing only a binding of the parameter to the argument value will not suffice, either. The make-adder function we used as an example in the Functional Abstraction chapter helps illustrate this.

In the incorrect implementation, when (make-adder 4) is evaluated, a binding of x to 4 is added to the current environment. But add-four is bound to (lambda (y) (+ x y)). If, when evaluating (add-four 3), we use the current environment, it will have a binding of x to 6, and the result will be 9 when it should be 7. But if we use the environment with a single binding of y to 3, there is no binding for x, and the computation fails.

The value of add-four cannot just be (lambda (y) (+ x y)). It must include the environment with a binding of x to 4. More generally, the value created when a lambda expression is evaluated must include the environment at the time of creation. We call this package a closure; it includes the parameter and body from the lambda, and the environment at time of creation. For make-adder, that is the empty environment. That environment is later used when the body expression is evaluated. So evaluating (make-adder 4) has the body expression (lambda (y) (+ x y)) evaluated in the empty environment extended with a binding of x to 4. That single-binding environment is part of the closure that is the value bound to add-four, and that is what is used when (add-four 3) is evaluated, leading to the correct answer of 7.

Exercise 62: Add environments to your answer to exercise 60 to handle first-class functions. \(\blacksquare\)

The lesson here is that it’s easy to make subtle mistakes when complicating code for the sake of efficiency. Proving that an environment-passing interpreter always gives the same results as the corresponding direct-substitution interpreter gets progressively more difficult as features are added. We will make use of both kinds of interpreters in the second part of FICS.

10.7 What’s next?

We can do quite a lot with the Racket features we have seen. There is a remaining set of features that are used sparingly in Racket, but which are more central in more mainstream programming languages. These have to do with effects, things that happen when an expression is evaluated, apart from producing a value. Examples include interaction with other devices or with humans that is more interleaved with computation (input and output), mutation (changing name-value bindings, or changing values in a structure), and handling errors without immediately stopping the computation.

The reasons these play a more prominent role in mainstream programming languages are because, historically, the earliest programming languages were thin abstractions over the machine languages directly implemented in hardware. They can also be more efficient, though this is not guaranteed, and as we saw above, the tradeoffs between efficiency and clarity don’t always permit easy answers.

In the second part of this flânerie, we’ll start moving towards those languages and machines, both by looking at how full Racket deals with effects, and by using full Racket to write more interpreters and compilers for "faux" languages that illustrate how effects can be handled and how machine languages are designed. If you have to or want to use languages like Java, C++, Go, or Python, this gradual introduction is better than plunging into them directly. If, on the other hand, you’re happy continuing to explore functional programming, the additional exposure to full Racket and its features is good preparation for my further flâneries such as FDS and LACI (both of which involve functional programming with modest use of effects).