Oh yeah, those flat environments

I did finally get flat environments working the way I want, and then refactored to be simpler and clearer. The basic idea is that rather than chasing down environment frames looking for a binding, we keep the lexical variables in a vector. A closure now looks like this:

    class Closure
    {
        protected readonly Lambda closureLambda;
        protected readonly Environment closureEnvironment;
        protected readonly ValueCell [] staticBindings;
        ...
    }

When we need the value of a lexical variable, we find it at a precomputed offset in the staticBindings. (They are ‘static’ because the location of the binding cell doesn't move.) When we create a closure, we need to copy some of the static bindings from the parent environment. For this we need a StaticMapping.

class StaticMapping
{
    int [] offsets;
    ....
}

The StaticMapping is stored in the StaticLambda from which we construct the StaticClosure. We copy the bindings when we construct the StaticClosure.

bool EvalStep (out object answer, ref Control expression, ref Environment environment)
{
    answer = new StaticClosure (this, environment.BaseEnvironment, environment.GetValueCells (this.staticMapping));
    return false;
}

And the code for GetValueCells is this:

internal override ValueCell [] GetValueCells (StaticMapping mapping)
{
    int count = mapping.Size;
    ValueCell [] cells = new ValueCell [count];
    for (int index = 0; index < count; index++) {
        int o = mapping.GetOffset(index);
        if (o < 0)
            cells [index] = this.bindings [(-o) - 1];
        else
            cells [index] = this.Closure.StaticCell (o);
    }
    return cells;
}

The StaticMapping encodes argument bindings as negative numbers and static bindings as positive numbers. The appropriate cells are copied from the parent environment.

Going to flat environments makes a substantial improvement. Our baseline median time for the sboyer benchmark was 6.596 seconds. With flat environments, the median time is now 4.346 seconds.

Variable lookup is no longer the bottleneck in the interpreter. Procedure application is. It was worth the tradeoff, but let's see what procedure application involves:

bool Apply (out object answer, ref Control expression, ref Environment environment, object [] args)
{
    if (args.Length != this.arity)
        throw new NotImplementedException ();
    expression = this.closureLambda.Body;
    environment = new StaticEnvironment (this, args);
    answer = null; // keep the compiler happy
    return true;
}

internal StaticEnvironment (Closure closure, object [] initialValues)
    : base (closure)
{
    object [] formals = closure.Lambda.Formals;
    this.bindings = new ValueCell [initialValues.Length];
    for (int i = 0; i < initialValues.Length; i++)
        this.bindings [i] = new ValueCell (formals [i], initialValues [i]);
}

The big problem is that we are allocating ValueCells for the argument bindings. We'll deal with this next.