Practical PLT Part 1: A Scheme Interpreter

April 22nd, 2008

“What?! You’re going to create another programming language? It’s going to be too hard for new people to learn, and there’s just too much complication involved! Interpreters, type-checkers, compilers, parsers, garbage collectors: these things are too difficult for average programmers to understand. And what’s the real business value anyway? You shouldn’t reinvent the wheel! Have you taken a look at Jimmy’s XML configuration system? He says that his files let you just wire up components, and surely that’s simpler than a new language.”

This series of articles on practical programming language theory (PLT) will be an answer to the above refrain. In this first article, I’ll show just how simple it is to make an interpreter for a basic functional language using any modern C++ compiler.


Philosophical Preliminaries

What is an interpreter? There are many different ways to view an interpreter, but (since we’re choosing to implement a particular one) we’ve got to choose a consistent way to think about it. Generically, an interpreter has some input (a program), and some output (what the program computes). We can view interpretation as the progressive refinement of our program, up to a fixed point. For example, imagine the program 1+1+1. The first step in a refinement of this program will either be 2+1 or 1+2, and in this case that choice is arbitrary. Either way, the final result will be 3, which can be refined no further (evaluation reaches a fixed point in that 3 evaluates to 3, which evaluates to 3, …).

All that’s necessary to make this view match our intuition of programming is to add abstractions. An abstraction, as its name implies, is an expression with a single value abstracted out of it. For example, with the expression 1+2, we may want to abstract away the number 1. This is written λx.x+2. Finally, we’ll need to apply values to abstractions, which requires substituting the actual value where the abstraction’s variable appears in its expression. For example, to regain our original 1+2, we can write the application ((λx.x+2) 1) — substituting 1 for x yields 1+2.

This perspective is elaborated colorfully in these famous videos, based on Harold Abelson and Gerald Sussman’s foundational book Structure and Interpretation of Computer Programs.

This view of interpretation follows the tradition of the λ-calculus, in contrast to the view in Turing machines. A useful rule of thumb in thinking about these two views is that the λ-calculus closely matches the way people traditionally think (and write) about calculation, while Turing machines closely match the way real physical computers are organized and manufactured.

Actual Code

Now that we’ve chosen a theoretical model of computation, we’ve got to get our hands dirty and write some code to make it work. There are many problems to start with in building a real interpreter, but a good first approximation is to start with the type signature:

Value* Eval(Value* program, EnvironmentFrame* env);

This says that the Eval function will take a Value and an EnvironmentFrame (a map of variables -> values, which accounts for the substitutions necessary when applying abstractions) and return a Value — the fixed point of evaluating the input program. We should expect that the following examples of the Eval function should be defined:

Eval(1, {}) = 1
Eval(x, { x -> 42 }) = 42
Eval(1+1+1, { + -> machine-code }) = 3
Eval(((λx.1+x) 2), { + -> machine-code }) = 3

Having covered the essential boundary of the problem, let’s refine it further to fill out these Value and EnvironmentFrame types, and provide a full definition of this special Eval function.

Data Types

In the example definitions of Eval above, we actually define the function over four different data types. In the first case we interpret a number, in the second case we interpret a symbol (the variable x), in the third case we interpret a compound expression representing the function associated with the symbol “+” applied to three numbers, and in the fourth case we apply an abstraction (itself a kind of function) to a value. Somehow we’ll have to capture all of these cases in the Value data type. Classes in the C++ language give us a method of describing each of these cases, inheriting from the most generic case — which we can use to define the empty base type:

class Value
{
};

Having set this much down, we can try to cover every case we considered above. First, numbers can be defined as:

class Number : public Value
{
public:
    Number(double v) : val(v) { }
    double value() const { return val; }
private:
    double val;
};

This effectively “boxes” the primitive double type. Moving on, we can similarly represent symbols:

class Symbol : public Value
{
public:
    Symbol(std::string v) : val(v) { }
    std::string value() const { return val; }
private:
    std::string val;
};

Having put those two cases to rest, we have to deal with the case of compound values. We could approach this in a number of ways, but perhaps the simplest is to view any case of compound values as a pair of values. In the case of a compound computation (as in the third example of Eval above), the head of the pair will represent the function to apply to the values represented by the tail of the pair. Following from this, the tail can be another pair, which allows us to chain together several values (or compound values) up to some final value: nil, the empty pair. For example, the expression 1+1+1 above can be represented in constructor form as:

Pair(+, Pair(1, Pair(Pair(+, Pair(1, Pair(1, nil))), nil)))

This type of structure is commonly visualized in box-pointer diagrams like this:

(+ 1 (+ 1 1))

Here, each box points to a value, and each box-pair represents a Pair (itself a value), and the image represents nil.

This structure can also be written as an S-expression: (+ 1 (+ 1 1)).

With all of that said, the actual definition of this pair type is very simple:

class Pair : public Value
{
public:
    Pair(Value* h, Value* t) : hd(h), tl(t) { }
    Value* head() const { return hd; }
    Value* tail() const { return tl; }
private:
    Value* hd; Value* tl;
};

Finally, we need to define the data type of functions, so that we can make the above program (with its references to a “+” function) meaningful and so that we can generally define abstractions.

class Function : public Value
{
public:
    virtual Value* Invoke(Pair* args, EnvironmentFrame* env)=0;
};

This leaves us with an interface that all functions must satisfy. It’s important to define this interface, because we’ll implement it differently for primitive functions than we will for abstractions. In either case, when a “function” is invoked, it will be given an argument list (a linked list of values, as described above) of unevaluated expressions (later we’ll see why it’s important that they be unevaluated). Because the argument list is unevaluated, we will also need to provide the EnvironmentFrame (the record of variable/value mappings).

To fill this out, let’s look at implementing the addition function required by the 1+1+1 program:

class AddFunction : public Function
{
    Value* Invoke(Pair* args, EnvironmentFrame* env)
    {
        Number* n1 = (Number*)Eval(args->head(), env);
        Pair* arg_tail = (Pair*)args->tail();

        Number* n2 = (Number*)Eval(arg_tail->head(), env);

        return allocate<Number>(n1->value() + n2->value());
    }
};

Later we’ll see how primitive functions can be defined more concisely, but for now it’s useful to stop here and understand just what the class is doing.First of all, it’s a subclass of Function, so it provides an Invoke method. Next it calls Eval (the interpreter function we have yet to define) on the head of the argument list, casting the result to a Number. Of course we could be safer here, perhaps using dynamic_cast to ensure that it’s safe to treat the value as a number, but for the purposes of this exercise we’ll keep it simple (and unsafe).

Next, the tail of the argument list is read (and cast to a Pair). Because the argument list is effectively a linked list, this is similar to (say) incrementing a std::list<Value*>::iterator. Having loaded the next node in the argument list, we again evaluate the head of this node, to acquire the second argument.

Finally, we return a new Number value made of the sum of the first two numbers. Ignoring the allocate<T> function for now (which should allocate a garbage collected value of type T), we’ve now completely come to terms with how a primitive function can be defined for this interpreter.

We now have almost enough detail worked out to implement Eval, the actual interpreter. Before we do that, we should fill out the EnvironmentFrame type, which keeps track of variable-name to Value substitutions:

class EnvironmentFrame
{
public:
    EnvironmentFrame(EnvironmentFrame* p) : parent(p) { }

    void define(const std::string& var, Value* val)
    {
        substitutions[var] = val;
    }

    Value* lookup(const std::string& var)
    {
        ValMap::iterator vi = substitutions.find(var);

        if (vi != substitutions.end())
            return vi->second;
        else if (parent != 0)
            return parent->lookup(var);
        else
            throw std::runtime_error(“Undefined: ” + var);
    }
private:
    typedef std::map<std::string, Value*> ValMap;
    EnvironmentFrame* parent;
    ValMap substitutions;
};

This type effectively just maps variable names to values, with the small distinction that it defers to an outer EnvironmentFrame if the variable isn’t immediately defined. Later we’ll look at implementing abstractions, where this ability to define hierarchies of substitutions is critical.  With this type defined, we can create the root environment frame to hold our addition function:

EnvironmentFrame* root = allocate<EnvironmentFrame>(0);
root->define(“+”, allocate<AddFunction>());

Now we’ve come far enough to finally define Eval, the actual interpreter.

The Eval Function

Value* Eval(Value* e, EnvironmentFrame* env)
{
    if (Symbol* s = dynamic_cast<Symbol*>(e))
        return env->lookup(s->value());
    else if (dynamic_cast<Pair*>(e) == 0)
        return e;

    Pair* p = (Pair*)e;
    Function* fn = (Function*)Eval(p->head(), env);

    return fn->Invoke(p->tail(), env);
}

Maybe it’s surprising that it takes less code to define the core of the interpreter than it took to define the type EnvironmentFrame, but (modulo safety) this is all we’ve got to write! Again, let’s cover the cases here (which roughly correspond to the four cases we considered when we first set out to define ).  First, if the expression is a Symbol value, we should interpret it as a variable, so we’ll return whatever is defined for that variable in the current EnvironmentFrame. Then, if the expression is not a compound value, we’ll return it immediately (currently this would just catch the Number type and the special nil value, but would catch any other special types we may create).

If the expression is a compound value, it’s interpreted as a function application. As we saw previously, the head of this compound expression must evaluate to a Function value. Having produced a Function value then, all that’s left is to call its Invoke implementation with the tail of the compound expression (the function’s argument list).

In a sense, that’s all there is to writing an interpreter. Although this explanation may appear lengthy, there’s very little code involved. All that’s left for us to do now is to “fill out” the interpreter with useful functions (since presently the only function we can apply is addition).

Additional Functions

In most “real world” programs, we’ll need some form of conditional statement. Currently our interpreter doesn’t support this, but it’s easy enough to add as a Function value.

class IfFunction : public Function
{
public:
    Value* Invoke(Pair* args, EnvironmentFrame* env)
    {
        // extract function arguments
        Value* test_exp = args->head();
        args = (Pair*)args->tail();
        Value* cons_exp = args->head();
        args = (Pair*)args->tail();

        Value* alt_exp = args->head();

        // if the condition is true, evaluate the
        // consequent else evaluate the alternative
        if (Eval(test_exp, env) != 0)
            return Eval(cons_exp, env);
        else
            return Eval(alt_exp, env);
    }
};

First we extract the expressions standing in for the condition of the if statement, the consequence, and the alternative. Then, we evaluate the condition expression and return either the evaluation of the consequence (if the condition does not evaluate to nil), or the evaluation of the alternative. It’s clear now that iterating over and extracting values out of the argument list is tedious (it required even more code above than the central logic of the IfFunction!). To save ourselves from this hassle, we can define a simple utility to extract the nth element of a list:
 
Value* nth(Pair* p, int n)
{
    int i = 0;
    while (i++ != n) p = (Pair*)p->tail();
    return p->head();
}

Now we can use this utility to create a function that allows programmers to define new variables:

class DefineFunction : public Function
{
public:
    Value* Invoke(Pair* args, EnvironmentFrame* env)
    {
        Symbol* var = (Symbol*)nth(args, 0);
        Value*    v = Eval(nth(args, 1), env);

        env->define(var->value(), v);
        return 0;
    }
};

Here it’s important that we not evaluate the first argument, since it should be the name of the variable we want to define (and since it isn’t already defined, if we evaluated it we’d get an error!). The second value (the value to be associated with the variable) should be evaluated though, and so it is. Finally, we update the environment with this new variable and (arbitrarily) return.  Just to fill out our interpreter a little more, we can also add more arithmetic-related functions: one to multiply two numbers and another to check two numbers for equality:

class MultiplyFunction : public Function
{
public:
    Value* Invoke(Pair* args, EnvironmentFrame* env)
    {
        Number* n1 = (Number*)Eval(nth(args, 0), env);
        Number* n2 = (Number*)Eval(nth(args, 1), env);

        return allocate<Number>(n1->value() * n2->value());
    }
};

class EqFunction : public Function
{
public:
    Value* Invoke(Pair* args, EnvironmentFrame* env)
    {
        Number* n1 = (Number*)Eval(nth(args, 0), env);
        Number* n2 = (Number*)Eval(nth(args, 1), env);

        if (n1->value() == n2->value())
            return allocate<Number>(1);
        else
            return 0;
    }
};

Here, the result of EqFunction is meant to match the condition value of IfFunction — so the value returned to represent “true” is arbitrary, but the value for “false” must be nil. Now that we’ve collected some important functions, we should add them all to our root environment:

root->define(“if”,     allocate<IfFunction>());
root->define(“define”, allocate<DefineFunction>());
root->define(“*”,      allocate<MultiplyFunction>());
root->define(“=”,      allocate<EqFunction>());

We’ve now assembled a pretty respectable interpreter and runtime environment, but we’ve still got one critical feature to define.

Abstractions

To complete the goal we set out for ourselves initially, we’ve still got to implement abstractions. Our implementation should support the intuition we’ve developed that the application of an abstraction just substitutes the arguments for the parameters in the body of the abstraction. Luckily, in the EnvironmentFrame type we have already implemented a method of mapping variable names to values. Also, because we have implemented this substitution method by recording variable/value mappings in an EnvironmentFrame, we’ll need to capture the active EnvironmentFrame in the implementation for an abstraction.

To motivate this notion of capturing an EnvironmentFrame in an abstraction, consider the case of λx.λy.x+y. Here we have an abstraction that returns an abstraction! The inner abstraction refers to a variable bound by the outer abstraction, and the clearest way to make that work in our interpreter is to give the outer abstraction’s EnvironmentFrame to the inner abstraction.

Now we should be able to define the Abstraction type:

class Abstraction : public Function
{
public:
    Abstraction(Pair* pa, Pair* pb, EnvironmentFrame* pe) :
        arg_names(pa), body(pb), edef(pe) { }

    Value* Invoke(Pair* arg_vals, EnvironmentFrame* env)
    {

        // prepare a fresh environment for this call
        EnvironmentFrame* cenv = allocate(edef);

        // evaluate each input value and map it to the
        // appropriate parameter name
        Pair* argn_iter = arg_names;
        Pair* argv_iter = arg_vals;

        while (argn_iter != 0)
        {
            Symbol* var = (Symbol*)argn_iter->head();
            Value* val = Eval(argv_iter->head(), env);
            cenv->define(var->value(), val);

            argn_iter = (Pair*)argn_iter->tail();
            argv_iter = (Pair*)argv_iter->tail();
        }

       // now evaluate the list of expressions in the body
        // of the abstraction in the EnvironmentFrame
        // for this call
        Value* r = 0;
        Pair* body_iter = body;

        while (body_iter != 0)
            r = Eval(body_iter->head(), cenv);

        return r;
    }
private:
    Pair* arg_names;
    Pair* body;
    EnvironmentFrame* edef;
};

This is probably the most complicated piece of code we’ve written in this interpreter! Still, if we go through it line-by-line we shouldn’t find anything particularly surprising. First, an Abstraction must be constructed with an argument list (a list of Symbols representing parameter names), a body (a list of expressions to be evaluated when the abstraction is applied), and an EnvironmentFrame (the active substitutions when the Abstraction is created).

Next, a new EnvironmentFrame is created to hold the variable/value mappings for the parameters of the Abstraction. It is then filled by iterating over both the list of parameter names and the list of arguments (expressions applied to the Abstraction). Each argument is evaluated and associated with its parameter name.

Finally, once the EnvironmentFrame for the call has been filled, it is used to evaluate each expression in the body (with the result of evaluating the last expression in the body used as the return value for Invoke).

To come to grips with this important aspect of our interpreter, let’s consider the case of ((λx.x+2) 1), which we considered early on. First, we’ll create Abstraction((x), ((+ x 2)), root). Here, (x) is just the parameter list, ((+ x 2)) the (one-element) list of expressions in the body, and root is the EnvironmentFrame in use when the Abstraction is first created (this should contain the definition of + which we use in the body). Then we apply the abstraction to the argument list (1). This produces an EnvironmentFrame for the call that looks like { x -> 1 { + -> PlusFunction } } (the nested mapping is meant to represent the contents of the parent EnvironmentFrame). Finally, the body is evaluated in this EnvironmentFrame, yielding a sequence of evaluations that looks as follows:

Eval((+ x 2), { x -> 1 { + -> PlusFunction } })
PlusFunction->Invoke((x 2), { x -> 1 { + -> PlusFunction } })
3

All that’s left is to provide a way for the programmer to construct these Abstraction values at runtime:

class MakeAbstractionFn : public Function
{
public:
    Value* Invoke(Pair* args, EnvironmentFrame* env)
    {
        Pair* pa = (Pair*)args->head();
        Pair* pb = (Pair*)args->tail();

        return allocate<Abstraction>(pa, pb, env);
    }
};

And we’ll need to put this function into the root EnvironmentFrame, so that it’s available to use. Traditionally, this function is written “lambda” (the less-convenient way of saying “λ“) so we’ll (arbitrarily) stick with that:

root->define(“lambda”, allocate<MakeAbstractionFn>());

Bringing it all together

We now have a minimalist interpreter for a Scheme-like programming language. There are still additions we may want to make, and plenty of supporting tools, but at this point we can already write very sophisticated programs. For example, we can construct a program to compute factorials:

Pair* program =
allocate<Pair>
(
  allocate<Symbol>(“define”),
  allocate<Pair>
  (
   allocate<Symbol>(“factorial”),
   allocate<Pair>
   (
    allocate<Pair>
    (
     allocate<Symbol>(“lambda”),
     allocate<Pair>
     (
      allocate<Pair>(allocate<Symbol>(“x”), 0),
      allocate<Pair>
      (
       allocate<Symbol>(“if”),
       allocate<Pair>
       (
        allocate<Pair>
        (
         allocate<Symbol>(“=”),
         allocate<Pair>
         (
          allocate<Symbol>(“x”),
          allocate<Pair>
          (
           allocate<Number>(0),
           0
          )
         )
        ),
        allocate<Pair>
        (
         allocate<Number>(1),
         allocate<Pair>
         (
          allocate<Pair>
          (
           allocate<Symbol>(“*”),
           allocate<Pair>
           (
            allocate<Symbol>(“x”),
            allocate<Pair>
            (
             allocate<Pair>
             (
              allocate<Symbol>(“factorial”),
              allocate<Pair>
              (
               allocate<Pair>
               (
                allocate<Symbol>(“+”),
                allocate<Pair>
                (
                 allocate<Number>(-1),
                 allocate<Pair>
                 (
                  allocate<Symbol>(“x”),
                  0
                 )
                )
               ),
               0
              )
             ),
             0
            )
           )
          ),
          0
         )
        )
       )
      )
     )
    ),
    0
   )
  )
);

Yikes! That’s horrible! That will correctly construct a program to define the factorial function (which our interpreter will correctly evaluate), but nobody would want to write programs if they had to be written like that!

Using the S-Expression form, this program can be represented much more concisely:

(define factorial
(lambda (x)
  (if (= x 0)
   1
   (* x (factorial (+ x -1)))
  )
)
)

That’s certainly much closer to what we humans would prefer to write! The job of translating the convenient shorthand of S-Expressions into the explicit in-memory construction required by our interpreter is the responsibility of a parser. We’ll look at how to write an S-Expression parser in the next installment.

6 Responses to “Practical PLT Part 1: A Scheme Interpreter”

  1. Ken Overton Says:

    This was a great posting, Kalani, thanks a lot. I think the biggest argument you have to be prepared to counter when proposing a specific language for a problem is debugging. If ‘non-technical’ people are going to be expressing themselves in Jimmy++, how are they going to deal with problems in their code?

  2. Kalani Thielen Says:

    Thanks Ken.

    I agree that debugging will have to be addressed, but I can only do so much in one post! :)

    I think it’s important to cover parsing first, since you’ll want runtime errors (or debug-step sessions) to relate back to the original source files rather than the giant in-memory trees that get built up (so while we’re parsing expressions we’ll have to stick that info into parsed values).

    But really, adding a debugger is a pretty simple task. Already in the EnvironmentFrame values there’s effectively a stack trace, which includes “local variables” (in a string form already, convenient for printing out in a debugger). The only trick is to modify the Eval function to communicate with a debugger process, so the debugger can control single steps and get/set variable values.

  3. Kalani Thielen Says:

    PS: I think it’s worth emphasizing that Jimmy’s XML system (usually a kind of ad-hoc dataflow “message transformer”), which seems to be implemented all over the place, fills the need of a specialized interpreter. Following that, it needs all of these things too (parsers, debuggers, etc)! The problem is that a lot of people aren’t making this connection between Jimmy’s XML system and an interpreter, and so they don’t see these obvious accessories that they’d probably expect to accompany a programming language!

    With that in mind, hopefully I can show how easy it is to implement those things once you’ve implemented a basic interpreter (like the one above).

  4. Practical PLT Part 2: An S-Expression Parser » Lab49 Blog Says:

    [...] the last article we saw how to build a simple interpreter.  We quickly ran into the problem that complex [...]

  5. Practical PLT Part 3: Advanced Functions » Lab49 Blog Says:

    [...] the first article we saw how to build a simple interpreter.  In the second we saw how to create a parser for [...]

  6. Practical PLT Part 4: A Garbage Collector » Lab49 Blog Says:

    [...] the previous articles of this series we’ve seen how to create a simple Scheme interpreter, then how to write an S-Expression parser to feed the interpreter, and in the last article we saw [...]