## Programming-Language Theory Explained for the Working Programmer: Simple Interpreter

Interpreters are programs for running programs. They receive a program as input, evaluate it, and output the results. How does this process work? In this article we start to address this question by writing a simple interpreter. The goal is to explore the underlying principles of computation and to understand how programming languages support *communication*, which is their essential feature. We do not to produce a realistic interpreter for an industrial-grade language, but we introduce ideas and techniques that are generally applicable to everyday problem solving. In subsequent articles we will explore the question further, developing variants of the simple interpreter from this article. We avoid the mathematical notation and jargon usually associated with this kind of topic, driving the exposition by working code. So this article is approachable to all programmers.

### Language§

To start writing our interpreter, we need to answer two questions: Which language do we use to write it? Which language does it interpret? For the former, we choose Racket. It has features that make interpreters easier to read, for example, *pattern matching* and *quasiquoting*—which we introduce in due time. This choice is solely based on convenience, this article could be rewritten in any other programming language.

More interesting than the choice of base language is the choice of target language. Our interpreter evaluates programs written in which language? We are not interested in language design, our objective is not to understand how particular language features are interpreted. Instead, we are interested in studying interpretation itself, and in understanding how interpreters support the fundamental principles behind computation. So the target language should be as *simple* as possible.

We choose *simplicity* over *convenience*. Our target language preferably includes as few features as possible, so that our interpreter is small and understandable, and changing it requires minimal effort. The price we pay is that our target language is *difficult* to use; programs written in it are verbose and unintelligible. This would be a bad choice for everyday programming tasks, but it is a good target language for this article, because, despite its simplicity, it remains a programming language with enough features to support arbitrary computations.

There exist many languages that fit our requirements. From all of them, we choose one that is particularly elegant, for its compactness. This target language represents a minimal core with only the following features: (1) definitions of anonymous functions of single argument and single return value; (2) applications of these functions; and (3) variable references. The following listing is an example of a program in this language:

```
(λ (x) x)
```

The program above defines a function which has no name (anonymous function). Function definitions are enclosed in parentheses, and start with the Greek letter lambda (`λ`

). After the `λ`

there is the name of the argument received by the function, also in parentheses, `(x)`

. Finally, there is the function body, an expression specifying which computation the function performs. In the example, the computation is to just return the argument `x`

, unaltered.

In our target language, functions are values. They are the only kind of value; there are no numbers, booleans, strings, data structures and other constructs usually found in programming languages. This highlights how *simple* the language is. Despite its simplicity, our target language is capable of performing arbitrary computations. In the case of the listing above, the function definition is the whole program. This is similar to how the following is a complete program in languages including Racket, Ruby, JavaScript and Python:

```
5
```

The listing above defines a full program in the mentioned languages. Its result is the number `5`

, because numbers are values in these languages. Functions are values in our target language, so the result of our first program is the function `(λ (x) x)`

.

Our first program is an example of function definition—`(λ ...)`

—and of variable reference—the `x`

in the function body. There is only one other feature in our target language, function application. It is represented by a function and an argument enclosed in parentheses. For example, if `f`

is a function and `a`

is an argument, then `(f a)`

is a function application. This is equivalent to the mathematical notation used by many popular programming languages: `f(a)`

. The following listing is a full program illustrating function application in our target language:

```
((λ (x) x) (λ (y) y))
```

This program is an application of the function `(λ (x) x)`

to the argument `(λ (y) y)`

. The interpretation of this is the same as in mathematics and most programming languages: to replace every occurrence of the argument name `x`

in `(λ (x) x)`

’s body with the argument `(λ (y) y)`

. Because `(λ (x) x)`

’s body is just `x`

, the result of this program is `(λ (y) y)`

.

We covered all features of our target language, but there are two corner cases that we need to address: variable-name reuse and variable references that have not been defined. The first case, variable-name reuse, can occur in two ways, the simplest of which is illustrated by the following listing:

```
((λ (x) x) (λ (x) x))
```

This is a variation on the program we used above to discuss function application. The only difference is that the variable `y`

has been consistently renamed to `x`

, so the name `x`

is used by both functions. These names occur in separate functions, so they do not interfere with each other. The same reasoning as before applies, and the result of this program is `(λ (x) x)`

. This is the same result as the previous example, except that the variable `y`

is consistently renamed to `x`

in the result as well.

A more interesting corner case occurs when a variable name is reused not by functions which sit side-by-side, as in the example above, but by nested functions. Consider the following function:

```
(λ (x) (λ (x) x))
```

Is the `x`

in the inner function body referring to the argument of the inner function or to the argument of the outer function? The answer is that variable references always refer to the nearest argument whose name (`x`

, in the example) matches. So the `x`

in the inner function body is referring to the argument of the inner function.

The final corner case is a variable reference to an undefined name. The following program is an example of this:

```
x
```

The program consists of a variable reference to `x`

, but `x`

has not been defined, it is not an argument to any function. This program has no precise meaning on its own, so our interpreter fails to evaluate it. This decision is consistent with that of most programming languages. Racket, for example, errors when trying to run the program above: “`x`

: unbound identifier in module.”

### Representation§

How do we represent in our base language (Racket) the programs from our target language? Generally, programs are plain text files, which interpreters read from the disk. They transform the text of the program into data structures in memory, through processes called *lexical analysis* (*lexing*) and *syntactic analysis* (*parsing*). This would be easy to do because our target language is a subset of Racket, which comes with *lexical* and *syntactical analyzers* for itself. But we take an even easier approach, and represent our programs as data structures in Racket directly. The language has a feature to make this representation convenient: *quasiquoting*. Consider the example of function application in our target language from the previous section:

```
((λ (x) x) (λ (y) y))
```

To turn this program in our target language into a data structure in Racket, we introduce a quasiquote (```

):

```
`((λ (x) x) (λ (y) y))
```

The snippet above is a Racket program which defines a program in our target language. Programs in our target language are data from Racket’s perspective, so the Racket program above by itself just outputs ``((λ (x) x) (λ (y) y))`

. In a later section we will implement an interpreter which receives this data structure as input.

Besides the convenient and terse notation, another advantage of using *quasiquoting* to represent programs in our target language is that we can use Racket programs to build programs in our target language. For this, we use *unquoting* (`,`

), which interpolates Racket expressions in parts of the data structure. For example, consider the following rewrite of the program above:

```
(define argument `(λ (y) y))
`((λ (x) x) ,argument)
```

This listing has the same meaning as the previous program. First, it defines a variable named `argument`

, whose value is a data structure representing a program fragment in our target language: `(λ (y) y)`

. Then, it uses *quasiquote* and *unquote* to define the program `((λ (x) x) (λ (y) y))`

in our target language. The *quasiquote* (```

) starts a program in our target language embedded in Racket (a data structure), and the *unquote* (`,`

) escapes back to Racket. The result of the expression under the *unquote* is interpolated in place. In the given example, the expression under the *unquote* is just a reference to the variable defined right above: `argument`

. So its value (the program fragment `(λ (y) y)`

in our target language) is interpolated in place, resulting in the program `((λ (x) x) (λ (y) y))`

in our target language.

As a consequence of using *quasiquote* and *unquote* to build programs in our target language, it is not possible to write a whole class of syntax errors in our target language. For example, the program ``(λ (x) x`

has unbalanced parentheses, but our interpreter does not have to handle this case, because it is a syntax error in Racket itself. This would not be the case had we decided to represent programs in our target language as plain text files on disk: a parser would have to detect the issue.

Nevertheless, there are many problematic programs that one can still write. For example, the program `(λ (x y) x)`

is not syntactically valid in our target language, because it defines a function which receives two arguments (`x`

and `y`

), and our target language only supports functions with a single argument. In the following section we implement a program to detect these classes of errors and validate the well-formedness of programs in our target language before the interpreter can evaluate them.

### Well-Formedness Checker§

Before we start the implementation of our first interpreter, we address the issue of checking whether a program is well-formed. In this section, we introduce a well-formedness checker, which runs before the interpreter, so it does not have to account for error cases. Also, the well-formedness checker is illustrative of the techniques we use to process programs in our language.

The well-formedness checker has two responsibilities: (1) check whether the program is syntactically valid; and (2) check whether all variables are defined before use. The first check rejects programs which are not in the forms defined by our target language. For example, `(λ (a b) a)`

is invalid because it is an anonymous function with two arguments (`a`

and `b`

), whereas our target language only allows for functions with one argument. Another example of syntactically invalid program is `(f a b)`

, which is a call to function `f`

with arguments `a`

and `b`

; this too is disallowed because functions only receive one argument.

The second responsibility of the well-formedness checker is to check whether all variables are defined before use. As mentioned in the previous section, the interpreter does not support these programs, which are said to be *open*. With this knowledge, we are ready to implement the `well-formed?`

function:

```
(define (well-formed? program)
(and (syntactically-valid? program) (closed? program)))
```

This implementation is simplistic, because it receives a `program`

as input and just delegates the responsibilities described above to two auxiliary functions `syntactically-valid?`

and `closed?`

. For the rest of this section, we implement these two auxiliary functions.

We start with `syntactically-valid?`

:

```
(define (syntactically-valid? program-fragment)
; TODO
)
```

This function receives a `program-fragment`

as argument, which is not necessarily a whole program. It makes sense to ask whether a smaller part of a bigger program is syntactically valid, for example, from the program `(λ (a) (a a))`

, we can ask whether `(a a)`

is syntactically valid (it is).

Let us first consider the simplest case, in which the `program-fragment`

is just a variable, for example, the `program-fragment`

`x`

. This fragment on its own is syntactically valid, despite not being well-formed for being open (`x`

is used but not defined). To check the syntactical validity, the function just has to check that the `program-fragment`

is a symbol which stands for a variable, as opposed to, for example, a number:

```
(define (syntactically-valid? program-fragment)
(symbol? program-fragment))
```

This simple implementation is just calling Racket’s `symbol?`

function, and it is already enough to check the syntactical validity of variables:

```
> (syntactically-valid? `x)
#t
> (syntactically-valid? `42)
#f
```

The next form of `program-fragment`

we address in `syntactically-valid?`

is the anonymous function definition, for example:

```
(λ (x) (x x))
```

Though, before `syntactically-valid?`

even considers the syntactical validity of the anonymous function definition, it needs to detect that the given `program-fragment`

is of this kind—as opposed to, for example, a variable reference, which we considered above. To this end, we introduce *pattern matching*. The simplest form of *pattern matching* is the following:

```
(match-define `(λ (,argument-name) ,body) `(λ (x) (x x)))
```

This form matches the program ``(λ (x) (x x))`

in our target language with the pattern ``(λ (,argument-name) ,body)`

. As a result, the Racket variable `argument-name`

is bound to the variable name `x`

in our target language; and the Racket variable `body`

is bound to the program fragment `(x x)`

.

In `syntactically-valid?`

, the data structure which is *subject* of the *pattern match* (`program-fragment`

) might have different forms. Moreover, we want to perform different computations depending on the kind of `program-fragment`

. So the `match-define`

form does not suffice, we have to reach for the `match`

form. The following is an example of *pattern matching* with the `match`

form:

The *pattern match* with the `match`

form works by matching the *subject* with each of the *patterns*, in order. The first *pattern* that matches determines which *match clause* has its *body* executed. In the example above, the *subject* and the *patterns* are simple data: numbers. The first *match clause* whose *pattern* matches the *subject* is `[5 "five"]`

, so the *result* of the *pattern match* is the *clause body* `"five"`

.

The example above demonstrates that the `match`

form in Racket has two uses: (1) multiway branching; and (2) destructing data structures. Using it, we can detect in which case the `program-fragment`

given to `syntactically-valid?`

falls. There are only three possibilities, which are the three constructs in our language: (1) definitions of anonymous functions of single argument and single return value; (2) applications of these functions; and (3) variable references.

```
(define (syntactically-valid? program-fragment)
(match program-fragment
#;[`(λ (,argument-name) ,body)
; TODO: (1) Anonymous function definition.
]
#;[`(,function ,argument)
; TODO: (2) Function application.
]
#;[`,variable
; TODO: (3) Variable reference.
]))
```

In the listing above, the *subject* of the pattern match is the `program-fragment`

, and there are three *match clauses*, corresponding to the three kinds of `program-fragment`

s. The first *pattern* is ``(λ (,argument-name) ,body)`

, which matches anonymous function definitions. For example, if `program-fragment`

is `(λ (x) (x x))`

, then `argument-name`

represents `x`

and `body`

stands for `(x x)`

. The other two patterns work similarly.

We already have an implementation for `variable`

s, so we can fill in the last hole in the template above:

```
(define (syntactically-valid? program-fragment)
(match program-fragment
#;[`(λ (,argument-name) ,body)
; TODO: (1) Anonymous function definition.
]
#;[`(,function ,argument)
; TODO: (2) Function application.
]
[`,variable
(symbol? variable)]))
```

The `syntactically-valid?`

function is once again working on the `program-fragment`

s consisting of `variable`

s, which we considered above:

```
> (syntactically-valid? `x)
#t
> (syntactically-valid? `42)
#f
```

Now that `syntactically-valid?`

can distinguish between the different forms of `program-fragment`

, we return to the issue of checking the syntactical validity of anonymous function definitions. Two conditions must hold: (1) the `argument-name`

must be a symbol (similar to variable references); and (2) the `body`

must be a `syntactically-valid?`

`program-fragment`

.

For the first condition, we can use Racket’s `symbol?`

function, as we did before for variable references. For the second, we can call `syntactically-valid?`

recursively on the `program-fragment`

which is the anonymous function `body`

:

```
(define (syntactically-valid? program-fragment)
(match program-fragment
[`(λ (,argument-name) ,body)
(and (symbol? argument-name) (syntactically-valid? body))]
#;[`(,function ,argument)
; TODO: (2) Function application.
]
[`,variable
(symbol? variable)]))
```

To test our implementation, we use the syntactically valid anonymous function `(λ (x) x)`

and the syntactically *invalid* anonymous function `(λ (x y) x)`

, which has more arguments than the one allowed:

```
> (syntactically-valid? `(λ (x) x))
#t
> (syntactically-valid? `(λ (x y) x))
#f
```

To complete the implementation of `syntactically-valid?`

, we consider the case of function applications. The condition for syntactical validity in this case is just that both `function`

and `argument`

are syntactically valid themselves, and we can use `syntactically-valid?`

recursively to check for that:

```
(define (syntactically-valid? program-fragment)
(match program-fragment
[`(λ (,argument-name) ,body)
(and (symbol? argument-name) (syntactically-valid? body))]
[`(,function ,argument)
(and (syntactically-valid? function) (syntactically-valid? argument))]
[`,variable
(symbol? variable)]))
```

To test this final case, we again consider one syntactically valid and one syntactically *invalid* `program-fragment`

:

```
> (syntactically-valid? `(f a))
#t
> (syntactically-valid? `(f a b))
#f
```

The function call `(f a b)`

is syntactically invalid because it has one argument more than allowed.

The implementation of `syntactically-valid?`

is complete. Let us turn to `closed?`

, the other well-formedness condition.

The implementation of the `closed?`

function is simple because it delegates most of the work to an auxiliary function, a strategy similar to the one used in `well-formed?`

. Specifically, `closed?`

receives a `program`

as argument and calls `free-variables`

on it. This auxiliary function returns the set of free variables in the program, in other words, the set of variables which are used before definition. If this set is empty, then the program is closed:

```
(define (closed? program)
(set-empty? (free-variables program)))
```

Of course, now we have to implement `free-variables`

. It receives a program fragment as argument and returns the set of variables used before definition it contains. We follow the technique we used to implement `syntactically-valid?`

, starting with the simplest program possible: `x`

. This program contains only one free variable, `x`

itself. So `free-variables`

just has to return a set containing it:

```
(define (free-variables program-fragment)
(set program-fragment))
```

We can test `free-variables`

with the simple program considered thus far:

```
> (free-variables `x)
(set 'x)
```

Next, we address the case of function application, for example `(f a)`

. We face the same issue as before, when implementing `syntactically-valid?`

: we need to distinguish between the different forms of `program-fragment`

s. The solution is the same, *pattern matching* with the `match`

form:

```
(define (free-variables program-fragment)
(match program-fragment
#;[`(λ (,argument-name) ,body)
; TODO: (1) Anonymous function definition.
]
#;[`(,function ,argument)
; TODO: (2) Function application.
]
#;[`,variable
; TODO: (3) Variable reference.
]))
```

Once again, we already have an implementation for the `variable`

case:

```
(define (free-variables program-fragment)
(match program-fragment
#;[`(λ (,argument-name) ,body)
; TODO: (1) Anonymous function definition.
]
#;[`(,function ,argument)
; TODO: (2) Function application.
]
[`,variable
(set variable)]))
```

And, with this implementation, the `variable`

case is still working:

```
> (free-variables `x)
(set 'x)
```

Coming back to the case of function application, consider the program `(f a)`

. The `function`

expression in this program is just a variable reference to `f`

, and the `argument`

is just a variable reference to `a`

. Both are free variables, so the set of free variables for the entire program is `(set 'a 'f)`

.

In general, the `free-variables`

of a function application are those from the `function`

expression, *and* those from the `argument`

expression. We can call `free-variables`

recursively on the `function`

and `argument`

expressions and union the resulting sets:

```
(define (free-variables program-fragment)
(match program-fragment
#;[`(λ (,argument-name) ,body)
; TODO: (1) Anonymous function definition.
]
[`(,function ,argument)
(set-union (free-variables function) (free-variables argument))]
[`,variable
(set variable)]))
```

Let us test this implementation:

```
> (free-variables `(f a))
(set 'a 'f)
```

Finally, we consider the case of anonymous function definitions. In the program `(λ (x) y)`

, the variable `y`

is free, but in the program `(λ (x) x)`

there are no free variables. The reason is that the anonymous function definition `(λ (x) ___)`

is defining a variable named `x`

, so any occurrence of `x`

in the body `___`

is *closed*.

In general, the set of free variables for an anonymous function definition is the set of free variables in its body *minus* the variable it defines:

```
(define (free-variables program-fragment)
(match program-fragment
[`(λ (,argument-name) ,body)
(set-remove (free-variables body) argument-name)]
[`(,function ,argument)
(set-union (free-variables function) (free-variables argument))]
[`,variable
(set variable)]))
```

We can test this case with the examples mentioned above:

```
> (free-variables `(λ (x) y))
(set 'y)
> (free-variables `(λ (x) x))
(set)
```

This completes the implementation of `free-variables`

and, consequently, the implementations of `closed?`

and `well-formed?`

as well. Hereafter, we only discuss interpretation of programs which are valid with respect to the `well-formed?`

predicate.

More importantly, note the similarities between the implementations of `syntactically-valid?`

and `free-variables`

. Both of these functions have to traverse the given `program-fragment`

, and they accomplish it using the same technique: first, `match`

on the given `program-fragment`

to detect its form; then, call the function recursively if it is necessary to traverse smaller `program-fragment`

s contained within the given `program-fragment`

. Abstractly, these functions that *traverse* the given `program-fragment`

have the shape:

```
(define (traverse program-fragment)
(match program-fragment
[`(λ (,argument-name) ,body)
___ (traverse body) ___]
[`(,function ,argument)
___ (traverse function) ___ (traverse argument) ___]
[`,variable
___]))
```

Our interpreter and auxiliary functions will follow the `traverse`

pattern. We are ready to move to their implementation.

### Interpreter§

Our interpreter is a function which receives a `program`

in our target language as argument and evaluates it to a value in our target language. We start with the template for *traversing* a `program`

, which we established in the previous section:

```
(define (interpret program)
(match program
#;[`(λ (,argument-name) ,body)
; TODO: (1) Anonymous function definition.
]
#;[`(,function ,argument)
; TODO: (2) Function application.
]
#;[`,variable
; TODO: (3) Variable reference.
]))
```

Let us first consider case (3), in which the `program`

is a `variable`

, for example, `x`

. In this case, the program is *open*, and is not well-formed. Our interpreter does not need to handle programs which are not well-formed, because they have already been discarded by the `well-formed?`

checker. So we can completely eliminate this case:

```
(define (interpret program)
(match program
#;[`(λ (,argument-name) ,body)
; TODO: (1) Anonymous function definition.
]
#;[`(,function ,argument)
; TODO: (2) Function application.
]))
```

Next, we address case (1), in which the program is the definition of an anonymous function, for example, `(λ (x) x)`

. Anonymous function definitions are already values in our language, so the interpreter can return the given `program`

unaltered:

```
(define (interpret program)
(match program
[`(λ (,argument-name) ,body)
program]
#;[`(,function ,argument)
; TODO: (2) Function application.
]))
```

This implementation is enough to interpret our first valid example program correctly:

```
> (interpret `(λ (x) x))
'(λ (x) x)
```

The final case is function application. The following is an example of function application in our language:

```
((λ (x) x) (λ (y) y)) ;; => (λ (y) y)
```

The applied function is `(λ (x) x)`

and the argument is `(λ (y) y)`

. The meaning of function application is the same as in mathematics and most programming languages: in the function body (in our example, the body is `x`

) substitute every occurrence of the argument name (in our example, `x`

) for the given argument (in our example, `(λ (y) y)`

).

The *pattern* we use in `interpret`

to match function application is ``(,function ,argument)`

. So, in our example, the Racket variable `function`

is bound to `(λ (x) x)`

and the Racket variable `argument`

is bound to `(λ (y) y)`

. Our first task is to *destruct* `function`

to retrieve its `argument-name`

and `body`

:

```
(match-define `(λ (,argument-name) ,body) function)
```

Then, we can call an auxiliary function to perform the substitution:

```
(define (interpret program)
(match program
[`(λ (,argument-name) ,body)
program]
[`(,function ,argument)
(match-define `(λ (,argument-name) ,body) function)
(substitute body argument-name argument)]))
```

The `substitute`

auxiliary function receives a function `body`

as argument and returns a modified version of it in which each occurrence of the given `argument-name`

has been substituted with the given `argument`

. To implement it, we use the same *traversal* template:

```
(define (substitute body argument-name argument)
(match body
#;[`(λ (,other-argument-name) ,other-body)
; TODO: (1) Anonymous function definition.
]
#;[`(,function ,other-argument)
; TODO: (2) Function application.
]
#;[`,variable
; TODO: (3) Variable reference.
]))
```

In our running example, the call to `substitute`

has the following form: `(substitute `x `x `(λ (y) y))`

. So `body`

is `x`

, `argument-name`

is `x`

and `argument`

is ``(λ (y) y)`

. This `body`

falls into the third kind in the *pattern match* above: variable reference. The expected result is the given `argument`

:

```
(define (substitute body argument-name argument)
(match body
#;[`(λ (,other-argument-name) ,other-body)
; TODO: (1) Anonymous function definition.
]
#;[`(,function ,other-argument)
; TODO: (2) Function application.
]
[`,variable
argument]))
```

This is enough to interpret our example:

```
> (interpret `((λ (x) x) (λ (y) y)))
'(λ (y) y)
```

But there are more details regarding function application that we need to consider. The first is that the implementation of `substitute`

for variable references above is overly simplistic. It replaces every `variable`

with `argument`

, not only those `variable`

s equal to the `argument-name`

. For example, if the `body`

had been `z`

, then `substitute`

would have substituted it for the `argument`

, which would have been incorrect, since the `argument-name`

was `x`

. We can simulate this scenario by calling `substitute`

directly:

```
> (substitute `z `x `(λ (y) y))
'(λ (y) y)
```

To fix this, we check if the `variable`

we found in the `body`

is equal to the `argument-name`

. If it is, then we substitute, otherwise, we leave it unaltered:

```
(define (substitute body argument-name argument)
(match body
#;[`(λ (,other-argument-name) ,other-body)
; TODO: (1) Anonymous function definition.
]
#;[`(,function ,other-argument)
; TODO: (2) Function application.
]
[`,variable
(if (equal? argument-name variable) argument variable)]))
```

With this modification, `substitute`

works as intended:

```
> (substitute `z `x `(λ (y) y))
'z
```

For the rest of its implementation, `substitute`

just calls itself recursively on the parts of the given `body`

. The effect is that it traverses the data structure representing our program fragment. This guarantees that every occurrence of `argument-name`

in `body`

is substituted, even those that occur deeper in the data structure:

```
(define (substitute body argument-name argument)
(match body
[`(λ (,other-argument-name) ,other-body)
`(λ (,other-argument-name)
,(substitute other-body argument-name argument))]
[`(,function ,other-argument)
`(,(substitute function argument-name argument)
,(substitute other-argument argument-name argument))]
[`,variable
(if (equal? argument-name variable) argument variable)]))
```

The following listing includes examples of uses of `substitute`

. These examples require traversing the `body`

with the recursive calls to `substitute`

we implemented above, because the `argument-name`

`x`

occurs deeper in the `body`

. In the first example, it occurs inside an anonymous function definition; and, in the second example, it occurs inside a function application:

```
> (substitute `(λ (z) x) `x `(λ (y) y))
'(λ (z) (λ (y) y))
> (substitute `(z x) `x `(λ (y) y))
'(z (λ (y) y))
```

In our next program, the `function`

to be applied is not immediately available. Instead, it is itself the result of a function application:

```
(((λ (x) x) (λ (y) y)) (λ (z) z)) ;; => (λ (z) z)
```

At the top level, this program is a function application, which matches the ``(,function ,argument)`

*pattern*. The `function`

is `((λ (x) x) (λ (y) y))`

and the `argument`

is `(λ (z) z)`

. The `function`

is not immediately available, it is a function application `((λ (x) x) (λ (y) y))`

itself. We can use `interpret`

on `function`

to evaluate it into a value:

```
(define (interpret program)
(match program
[`(λ (,argument-name) ,body)
program]
[`(,function ,argument)
(define interpreted-function (interpret function))
(match-define `(λ (,argument-name) ,body) interpreted-function)
(substitute body argument-name argument)]))
```

In the listing above, note the recursive call to `interpret`

. The result of this recursive call is a value, because `interpret`

returns values in our language. And values in our language are functions, which we can then *destruct* with `match-define`

. With this change, `interpret`

works for our program:

```
> (interpret `(((λ (x) x) (λ (y) y)) (λ (z) z)))
'(λ (z) z)
```

An issue similar to the one addressed above occurs in the `argument`

of a function application. It might not be an immediate value, but a computation. For example, consider the following program:

```
((λ (x) x) ((λ (y) y) (λ (z) z))) ;; => (λ (z) z)
```

In this function application, the `argument`

is `((λ (y) y) (λ (z) z))`

, which is not a value. So we have to call `interpret`

on the `argument`

before the substitution as well:

```
(define (interpret program)
(match program
[`(λ (,argument-name) ,body)
program]
[`(,function ,argument)
(define interpreted-function (interpret function))
(define interpreted-argument (interpret argument))
(match-define `(λ (,argument-name) ,body) interpreted-function)
(substitute body argument-name interpreted-argument)]))
```

Our interpreter now works for the given example:

```
> (interpret `((λ (x) x) ((λ (y) y) (λ (z) z))))
'(λ (z) z)
```

For our next program, the result of a function application is another function application:

```
((λ (i) ((λ (x) x) (λ (y) y))) (λ (z) z)) ;; => (λ (y) y)
```

This program is similar to our first example of function application `((λ (x) x) (λ (y) y))`

. The difference is that it has been wrapped in a function which ignores its argument `i`

. This function is immediately applied to the throwaway argument `(λ (z) z)`

.

Our interpreter does not work on this program:

```
> (interpret `((λ (i) ((λ (x) x) (λ (y) y))) (λ (z) z)))
'((λ (x) x) (λ (y) y))
```

This output is the result of the substitution of the throwaway argument `(λ (z) z)`

in the body of the function `(λ (i) ((λ (x) x) (λ (y) y)))`

. There were no occurrences of the argument name `i`

in the body, because it is an ignored argument. So the result of the substitution is just the body, `((λ (x) x) (λ (y) y))`

. But the interpreter should not stop at this point, it needs to proceed interpreting these intermediary program, until it reaches a value. To accomplish this, we call `interpret`

recursively, with the result of the substitution:

```
(define (interpret program)
(match program
[`(λ (,argument-name) ,body)
program]
[`(,function ,argument)
(define interpreted-function (interpret function))
(define interpreted-argument (interpret argument))
(match-define `(λ (,argument-name) ,body) interpreted-function)
(define substituted-body
(substitute body argument-name interpreted-argument))
(interpret substituted-body)]))
```

Now `interpret`

works correctly for the running example:

```
> (interpret `((λ (i) ((λ (x) x) (λ (y) y))) (λ (z) z)))
'(λ (y) y)
```

The next programs we address are those concerning variable-name reuse. First, the case in which the reused name occurs in separate functions:

```
> (interpret `((λ (x) x) (λ (x) x)))
'(λ (x) x)
```

Our interpreter already handles this program correctly. But it does not work for the second case, in which the reused variable name occurs in a nested function. Consider the following program:

We expect the result of this program to be `(λ (z) z)`

, and not `(λ (y) y)`

. But the current implementation outputs the wrong value:

```
> (interpret `(((λ (x) (λ (x) x)) (λ (y) y)) (λ (z) z)))
'(λ (y) y)
```

The reason for this is revealed after the inner function application:

```
> (interpret `((λ (x) (λ (x) x)) (λ (y) y)))
'(λ (x) (λ (y) y))
```

This program fragment is a function application, in which the `function`

is `(λ (x) (λ (x) x))`

and the `argument`

is `(λ (y) y)`

. The interpreter calls `substitute`

with the `body`

`(λ (x) x)`

and the `argument-name`

`x`

:

```
> (substitute `(λ (x) x) `x `(λ (y) y))
'(λ (x) (λ (y) y))
```

The `x`

in the body of the function `(λ (x) x)`

refers to its argument, not the outer declaration of `x`

, which we are currently substituting. The problem is in `substitute`

: when it finds a function definition whose `other-argument-name`

is the same as the given `argument-name`

, it should stop traversing the program fragment. It should not try to substitute occurrences of the `argument-name`

any further, because they refer to `other-argument-name`

:

```
(define (substitute body argument-name argument)
(match body
[`(λ (,other-argument-name) ,other-body)
(if (equal? argument-name other-argument-name)
body
`(λ (,other-argument-name)
,(substitute other-body argument-name argument)))]
[`(,function ,other-argument)
`(,(substitute function argument-name argument)
,(substitute other-argument argument-name argument))]
[`,variable
(if (equal? argument-name variable) argument variable)]))
```

Our program now works as we expected:

```
> (interpret `(((λ (x) (λ (x) x)) (λ (y) y)) (λ (z) z)))
'(λ (z) z)
```

This concludes the implementation of our interpreter. To test it in a realistic setting, we can use the final version of the program from the article that introduces our target language, which calculates the sum `1 + 2 + 3 + 4 + 5`

:

```
> (pretty-print
(eval
(interpret
`((λ (number)
(((λ (sum-up-to/rest)
(λ (number)
(((((λ (condition)
(λ (then)
(λ (else)
((condition then)
else))))
((λ (number)
((number
(λ (ignored-argument)
(λ (first)
(λ (second)
second))))
(λ (first)
(λ (second) first))))
number))
(λ (dummy)
(λ (function)
(λ (argument) argument))))
(λ (dummy)
(((λ (number-left)
(λ (number-right)
(λ (function)
(λ (argument)
((number-left
function)
((number-right
function)
argument))))))
number)
((sum-up-to/rest
sum-up-to/rest)
((λ (number)
((λ (pair)
(pair
(λ (left)
(λ (right) left))))
((number
(λ (current-pair)
(((λ (left)
(λ (right)
(λ (selector)
((selector
left)
right))))
((λ (pair)
(pair
(λ (left)
(λ (right)
right))))
current-pair))
(((λ (number-left)
(λ (number-right)
(λ (function)
(λ (argument)
((number-left
function)
((number-right
function)
argument))))))
((λ (pair)
(pair
(λ (left)
(λ (right)
right))))
current-pair))
(λ (function)
(λ (argument)
(function
argument)))))))
(((λ (left)
(λ (right)
(λ (selector)
((selector
left)
right))))
(λ (function)
(λ (argument)
argument)))
(λ (function)
(λ (argument)
argument))))))
number)))))
(λ (ignore-me) ignore-me))))
(λ (sum-up-to/rest)
(λ (number)
(((((λ (condition)
(λ (then)
(λ (else)
((condition then)
else))))
((λ (number)
((number
(λ (ignored-argument)
(λ (first)
(λ (second)
second))))
(λ (first)
(λ (second) first))))
number))
(λ (dummy)
(λ (function)
(λ (argument) argument))))
(λ (dummy)
(((λ (number-left)
(λ (number-right)
(λ (function)
(λ (argument)
((number-left
function)
((number-right
function)
argument))))))
number)
((sum-up-to/rest
sum-up-to/rest)
((λ (number)
((λ (pair)
(pair
(λ (left)
(λ (right) left))))
((number
(λ (current-pair)
(((λ (left)
(λ (right)
(λ (selector)
((selector
left)
right))))
((λ (pair)
(pair
(λ (left)
(λ (right)
right))))
current-pair))
(((λ (number-left)
(λ (number-right)
(λ (function)
(λ (argument)
((number-left
function)
((number-right
function)
argument))))))
((λ (pair)
(pair
(λ (left)
(λ (right)
right))))
current-pair))
(λ (function)
(λ (argument)
(function
argument)))))))
(((λ (left)
(λ (right)
(λ (selector)
((selector
left)
right))))
(λ (function)
(λ (argument)
argument)))
(λ (function)
(λ (argument)
argument))))))
number)))))
(λ (ignore-me) ignore-me)))))
number))
(λ (function)
(λ (argument)
(function
(function
(function
(function
(function argument)))))))))))
15
```

The output is what we expected, `15`

. Our interpreter is fully functional for any program in our target language.

But this interpreter is not revealing all interesting aspects of interpretation. For example, it depends on Racket’s support for recursive functions to compute nested expressions—see the recursive calls in `interpret`

’s implementation. When our interpreter finds a function application, it starts processing it; if the `function`

or the `argument`

are function applications themselves, then it defers the rest of the processing of the outer function application, interprets the inner function applications, and then resumes the work on the outer function application. This whole process is implicit, hidden by the recursive nature of `interpret`

’s implementation. Furthermore, if given a `program`

which does not terminate, then `interpret`

itself does not terminate, and there is no way to inspect the computations that are happening during interpretation.

We will address these aspects of interpretation in subsequent articles, making our interpreter more transparent and revealing more interesting facets of computation.

### Conclusion§

We started with a fundamental question: How do interpreters evaluate programs to values? The find an answer, we implemented a simple interpreter for a simple language. Despite the lack of features, this is machinery capable of general computation; adding support for numbers, data structures, more control-flow constructs and so forth would be a matter of convenience for humans, not enhancing the fundamental computational power. In the process of writing our interpreter, we used *pattern matching* and devised a template for traversing hierarchical data structures. Finally, we observed the limitations of the interpreter we implemented; there are a few interesting aspects of evaluation that it conceals for relying on the host language (Racket). We will address these issues by modifying our interpreter in subsequent articles.

### References§

The approach to interpretation followed by this article is inspired by Structure and Interpretation of Computer Programs, the classic textbook. We follow a more modern approach using pattern matching, which is based on PLT Redex and Semantics Engineering with PLT Redex. A great source for learning about interpretation in depth is the Lambda Papers. People interested in reading more recent research papers need to understand the associated formal notation, for which the book Principles of Programming Languages is a gentle introduction (disclaimer, the author is my advisor).

### Appendix: Full Listing§

```
#lang racket
;; ---------------------------------------------------------------------------------------------------
;; TEST CASES
(module+ test
(require rackunit))
(define open `x)
(define invalid-function-definition `(λ (a b) a))
(define invalid-function-application `(λ (a) (a a a)))
(define minimal-program `(λ (x) x))
(define minimal-program/result `(λ (x) x))
(define minimal-application `((λ (x) x) (λ (y) y)))
(define minimal-application/result `(λ (y) y))
(define function-is-application `(((λ (x) x) (λ (y) y)) (λ (z) z)))
(define function-is-application/result `(λ (z) z))
(define argument-is-application `((λ (x) x) ((λ (y) y) (λ (z) z))))
(define argument-is-application/result `(λ (z) z))
(define multiple-steps `((λ (i) ((λ (x) x) (λ (y) y))) (λ (z) z)))
(define multiple-steps/result `(λ (y) y))
(define non-shadowing-variable-name-reuse `((λ (x) x) (λ (x) x)))
(define non-shadowing-variable-name-reuse/result `(λ (x) x))
(define shadowing `(((λ (x) (λ (x) x)) (λ (y) y)) (λ (z) z)))
(define shadowing/result `(λ (z) z))
(define sum-up-to
`((λ (number)
(((λ (sum-up-to/rest)
(λ (number)
(((((λ (condition)
(λ (then)
(λ (else)
((condition then)
else))))
((λ (number)
((number
(λ (ignored-argument)
(λ (first)
(λ (second)
second))))
(λ (first)
(λ (second) first))))
number))
(λ (dummy)
(λ (function)
(λ (argument) argument))))
(λ (dummy)
(((λ (number-left)
(λ (number-right)
(λ (function)
(λ (argument)
((number-left
function)
((number-right
function)
argument))))))
number)
((sum-up-to/rest
sum-up-to/rest)
((λ (number)
((λ (pair)
(pair
(λ (left)
(λ (right) left))))
((number
(λ (current-pair)
(((λ (left)
(λ (right)
(λ (selector)
((selector
left)
right))))
((λ (pair)
(pair
(λ (left)
(λ (right)
right))))
current-pair))
(((λ (number-left)
(λ (number-right)
(λ (function)
(λ (argument)
((number-left
function)
((number-right
function)
argument))))))
((λ (pair)
(pair
(λ (left)
(λ (right)
right))))
current-pair))
(λ (function)
(λ (argument)
(function
argument)))))))
(((λ (left)
(λ (right)
(λ (selector)
((selector
left)
right))))
(λ (function)
(λ (argument)
argument)))
(λ (function)
(λ (argument)
argument))))))
number)))))
(λ (ignore-me) ignore-me))))
(λ (sum-up-to/rest)
(λ (number)
(((((λ (condition)
(λ (then)
(λ (else)
((condition then)
else))))
((λ (number)
((number
(λ (ignored-argument)
(λ (first)
(λ (second)
second))))
(λ (first)
(λ (second) first))))
number))
(λ (dummy)
(λ (function)
(λ (argument) argument))))
(λ (dummy)
(((λ (number-left)
(λ (number-right)
(λ (function)
(λ (argument)
((number-left
function)
((number-right
function)
argument))))))
number)
((sum-up-to/rest
sum-up-to/rest)
((λ (number)
((λ (pair)
(pair
(λ (left)
(λ (right) left))))
((number
(λ (current-pair)
(((λ (left)
(λ (right)
(λ (selector)
((selector
left)
right))))
((λ (pair)
(pair
(λ (left)
(λ (right)
right))))
current-pair))
(((λ (number-left)
(λ (number-right)
(λ (function)
(λ (argument)
((number-left
function)
((number-right
function)
argument))))))
((λ (pair)
(pair
(λ (left)
(λ (right)
right))))
current-pair))
(λ (function)
(λ (argument)
(function
argument)))))))
(((λ (left)
(λ (right)
(λ (selector)
((selector
left)
right))))
(λ (function)
(λ (argument)
argument)))
(λ (function)
(λ (argument)
argument))))))
number)))))
(λ (ignore-me) ignore-me)))))
number))
(λ (function)
(λ (argument)
(function
(function
(function
(function
(function argument)))))))))
(define sum-up-to/result
`(λ (function)
(λ (argument)
(((λ (function)
(λ (argument)
(function
(function
(function
(function
(function argument)))))))
function)
(((λ (function)
(λ (argument)
(((λ (function)
(λ (argument)
(((λ (function)
(λ (argument)
(((λ (function)
(λ (argument)
(((λ (function)
(λ (argument)
(((λ (function)
(λ (argument)
argument))
function)
(((λ (function)
(λ (argument)
(function
argument)))
function)
argument))))
function)
(((λ (function)
(λ (argument)
(function
argument)))
function)
argument))))
function)
(((λ (function)
(λ (argument)
(function
argument)))
function)
argument))))
function)
(((λ (function)
(λ (argument)
(function argument)))
function)
argument))))
function)
(((λ (function)
(λ (argument)
(((λ (function)
(λ (argument)
(((λ (function)
(λ (argument)
(((λ (function)
(λ (argument)
(((λ (function)
(λ (argument)
argument))
function)
(((λ (function)
(λ (argument)
(function
argument)))
function)
argument))))
function)
(((λ (function)
(λ (argument)
(function
argument)))
function)
argument))))
function)
(((λ (function)
(λ (argument)
(function
argument)))
function)
argument))))
function)
(((λ (function)
(λ (argument)
(((λ (function)
(λ (argument)
(((λ (function)
(λ (argument)
(((λ (function)
(λ (argument)
argument))
function)
(((λ (function)
(λ (argument)
(function
argument)))
function)
argument))))
function)
(((λ (function)
(λ (argument)
(function
argument)))
function)
argument))))
function)
(((λ (function)
(λ (argument)
(((λ (function)
(λ (argument)
(((λ (function)
(λ (argument)
argument))
function)
(((λ (function)
(λ (argument)
(function
argument)))
function)
argument))))
function)
(((λ (function)
(λ (argument)
argument))
function)
argument))))
function)
argument))))
function)
argument))))
function)
argument))))
function)
argument)))))
;; ---------------------------------------------------------------------------------------------------
;; WELL-FORMEDNESS CHECKER
(define (well-formed? program)
(and (syntactically-valid? program) (closed? program)))
(module+ test
(check-false (well-formed? open))
(check-false (well-formed? invalid-function-definition))
(check-false (well-formed? invalid-function-application))
(check-true (well-formed? minimal-program))
(check-true (well-formed? minimal-application))
(check-true (well-formed? function-is-application))
(check-true (well-formed? argument-is-application))
(check-true (well-formed? multiple-steps))
(check-true (well-formed? non-shadowing-variable-name-reuse))
(check-true (well-formed? shadowing))
(check-true (well-formed? sum-up-to)))
(define (syntactically-valid? program-fragment)
(match program-fragment
[`(λ (,argument-name) ,body)
(and (symbol? argument-name) (syntactically-valid? body))]
[`(,function ,argument)
(and (syntactically-valid? function) (syntactically-valid? argument))]
[`,variable
(symbol? variable)]))
(module+ test
(check-true (syntactically-valid? open))
(check-false (syntactically-valid? invalid-function-definition))
(check-false (syntactically-valid? invalid-function-application))
(check-true (syntactically-valid? minimal-program))
(check-true (syntactically-valid? minimal-application))
(check-true (syntactically-valid? function-is-application))
(check-true (syntactically-valid? argument-is-application))
(check-true (syntactically-valid? multiple-steps))
(check-true (syntactically-valid? non-shadowing-variable-name-reuse))
(check-true (syntactically-valid? shadowing))
(check-true (syntactically-valid? sum-up-to)))
(define (closed? program)
(set-empty? (free-variables program)))
(module+ test
(check-false (closed? open))
(check-true (closed? minimal-program))
(check-true (closed? minimal-application))
(check-true (closed? function-is-application))
(check-true (closed? argument-is-application))
(check-true (closed? multiple-steps))
(check-true (closed? non-shadowing-variable-name-reuse))
(check-true (closed? shadowing))
(check-true (closed? sum-up-to)))
(define (free-variables program-fragment)
(match program-fragment
[`(λ (,argument-name) ,body)
(set-remove (free-variables body) argument-name)]
[`(,function ,argument)
(set-union (free-variables function) (free-variables argument))]
[`,variable
(set variable)]))
(module+ test
(check-equal? (free-variables open)
(set 'x))
(check-equal? (free-variables minimal-program)
(set))
(check-equal? (free-variables minimal-application)
(set))
(check-equal? (free-variables function-is-application)
(set))
(check-equal? (free-variables argument-is-application)
(set))
(check-equal? (free-variables multiple-steps)
(set))
(check-equal? (free-variables non-shadowing-variable-name-reuse)
(set))
(check-equal? (free-variables shadowing)
(set))
(check-equal? (free-variables sum-up-to)
(set)))
;; ---------------------------------------------------------------------------------------------------
;; INTERPRETER
(define (interpret program)
(match program
[`(λ (,argument-name) ,body)
program]
[`(,function ,argument)
(define interpreted-function (interpret function))
(define interpreted-argument (interpret argument))
(match-define `(λ (,argument-name) ,body) interpreted-function)
(define substituted-body (substitute body argument-name interpreted-argument))
(interpret substituted-body)]))
(define (substitute body argument-name argument)
(match body
[`(λ (,other-argument-name) ,other-body)
(if (equal? argument-name other-argument-name)
body
`(λ (,other-argument-name) ,(substitute other-body argument-name argument)))]
[`(,function ,other-argument)
`(,(substitute function argument-name argument)
,(substitute other-argument argument-name argument))]
[`,variable
(if (equal? argument-name variable) argument variable)]))
(module+ test
(check-equal? (interpret minimal-program)
minimal-program/result)
(check-equal? (interpret minimal-application)
minimal-application/result)
(check-equal? (interpret function-is-application)
function-is-application/result)
(check-equal? (interpret argument-is-application)
argument-is-application/result)
(check-equal? (interpret multiple-steps)
multiple-steps/result)
(check-equal? (interpret non-shadowing-variable-name-reuse)
non-shadowing-variable-name-reuse/result)
(check-equal? (interpret shadowing)
shadowing/result)
(check-equal? (interpret sum-up-to)
sum-up-to/result))
```