Anatomy of an interpreter: the Evaluator

Posts in this series: Lexer, Parser, Evaluator

I'm still really enjoying writing my Scheme interpreter Subs, which can now succesfully run all the example code from SICP up to section 2.3.4. I've made the changes I mentioned I would in the Lexer article, so now the Lexer returns Tokens that contain information about their basic types, and I've gone through a significant refactoring to replace one of the several massive switch statements with a virtual function call (Martin Fowler would be proud).

Last time I explained how the Parser takes the stream of tokens coming from the Lexer and returns a hierarchical tree of Values, each of which represents an operation or thing in the program.

The Evaluator takes in a tree of Values, "evaluates" it, and returns another Value object, which is the answer. The Evaluator class is by far the most complex part of Subs, so in this post we'll start with an overview of how it works. Future posts will break down the different parts in more detail.

The most interesting parts of the Evaluator class interface look like this:

class Evaluator
{
public:
    std::auto_ptr<Value> EvalInContext( const Value* value,
        boost::shared_ptr<Environment>& environment );
};

The EvalInContext method takes in a Value to evaluate, and an "environment" *in which to evaluate it. Note that the in the real code it takes a couple more arguments, including a mysterious and annoying boolean called is_tail_call which will be explained later.

* More on environments later. All you need to know for now is that they provide a way of keeping hold of all the things we currently know about, identified by name.

A very simplified version of EvalInContext would look like this:

std::auto_ptr<Value> Evaluator::EvalInContext( const Value* value,
    boost::shared_ptr<Environment>& environment )
{
    if( is_symbol( value ) )
    {
        return eval_symbol( value, environment );
    }

    if( !is_combination( value ) )
    {
        return auto_ptr<Value>( value->Clone() );
    }

    const CombinationValue* combo = to_combination( value );
    CombinationValue::const_iterator it = combo->begin();

    auto_ptr<Value> evaldoptr = EvalInContext( *it, environment );

    if( special_symbol( evaldoptr ) )
    {
        return process_special_symbol( evaldoptr, combo );
    }
    else
    {
        ++it;

        CombinationValue argvalues;
        for( ; it != combo->end(); ++it )
        {
            argvalues.push_back( EvalInContext( *it, environment ).release() );
        }

        return run_procedure( evaldoptr.get(), &argvalues, *this, environment );
    }
}

If the Value to be evaluated is just a symbol, we call eval_symbol which basically looks up the symbol's name in the environment and returns the value it finds.

If the Value is not a combination (i.e. the root of a tree of other values) it must be a basic type such as a string or an integer. In this case we simple copy the Value and return it.

Otherwise, it's a combination. To evaluate a combination, we follow the "eval-apply" pattern. The principle is to evaluate all the Values in the combination separately, and then "apply" (run) the first value (the "operator") as a procedure, using the other values as arguments. The first value must evaluate to something that is recognisable as a procedure, or this doesn't make sense and we will throw an error.

In practice it's a tiny bit more complicated. We evaluate the first Value in the combination (by calling EvalInContext recursively), then we check whether it's a special symbol such as if or let and if so, deal with it separately. Otherwise, we evaluate all the other Values (calling EvalInContext recursively again) and put them into a new CombinationValue, and pass the operator and the arguments to run_procedure, which looks something like this:

std::auto_ptr<Value> run_procedure( const Value* operator,
    const CombinationValue* args, Evaluator& ev,
    boost::shared_ptr<Environment>& environment )
{
    if( is_builtin_procedure( operator ) )
    {
        return handle_builtin_procedure( operator, args, environment );
    }
    else
    {
        std::auto_ptr<Value> ret;

        const CompoundProcedureValue* proc = to_compound_procedure( operator );

        boost::shared_ptr<Environment> new_env =
            proc->ExtendEnvironmentWithArgs( args );

        for( CombinationValue::const_iterator it = proc->GetBody()->begin();
            it != proc->GetBody()->end(); ++it )
        {
            ret = ev.EvalInContext( *it, new_env );
        }

        return ret;
    }
}

Running a procedure means either doing something built-in (for example adding up two numbers and returning the result) or evaluating some other code, which comes from the definition of the procedure being run. First we call ExtendEnvironmentWithArgs to create a new Environment, which contains the argument Values that were supplied, and then we loop through all the sections of the body of the procedure, evaluating each one. Note that we throw away the returned Values for all sections except the last one (this is how Scheme works).

Once we've evaluated and applied our procedure, which of course potentially includes numerous recursive calls to EvalInContext, we end up with a Value that is returned, and we're done.

Simple eh?

But now I must make a confession: almost everything I have written above is lie. Why would I lie to you? Because I missed out something wonderful and strange called "tail-call optimisation". I'll explain next time.