Module oxischeme::eval [-]  [+] [src]

Oxischeme is an interpreter, but it is not a naiive AST walking interpreter. In contrast to an AST walking interpreter, syntactic analysis is separated from execution, so that no matter how many times an expression might be evaluated, it is only ever analyzed once.

When evaluating a form, first we analyze it to derive its semantic Meaning. The meanings form an intermediate language containing everything we statically know about the expression, such as whether it is a conditional or a lambda form, or the location of a value bound to a variable name, so that we don't need to compute these things at execution time. After analysis has produced a meaning for the form, the meaning is then interpreted. This approach results in a speed up in the realm of 10 - 50 times faster than simple AST-walking evaluation.

In SICP and LiSP, the implementation language is also Scheme, and the meanings are just elegant closures. Because we cannot rely on the host language's GC like they can, we require more fine-grained control of the data and its lifetime. Therefore, we explicitly model all data that can be statically gathered in the MeaningData type. Evaluation of each special form is implemented by two things: first, a variant in MeaningData, and secondly a MeaningEvaluatorFn function that takes the heap, an activation, and the meaning data for that form. The simplest example is quoted forms: we determine the quoted value during analysis and at runtime simply return it.

enum MeaningData {
    ...
    Quotation(RootedValue),
    ...
}

fn evaluate_quotation(heap: &mut Heap,
                      data: &MeaningData,
                      act: &mut RootedActivationPtr) -> TrampolineResult {
    if let MeaningData::Quotation(ref val) = *data {
        return Ok(Trampoline::Value(Rooted::new(heap, **val)));
    }

    panic!("unsynchronized MeaningData and MeaningEvaluatorFn");
}

References

Structs

Meaning

The Meaning type is our intermediate language produced by syntactic analysis. It is a triple containing a MeaningData variant, its corresponding MeaningEvaluatorFn, and the source location this Meaning originates from.

Enums

Trampoline

To optimize tail calls and eliminate the stack frames that would otherwise be used by them, we trampoline thunks in a loop and encode that process in this type.

Functions

analyze

The main entry point for syntactic analysis.

apply_invocation
evaluate

Evaluate the given form in the global environment.

evaluate_file

Evaluate the file at the given path and return the value of the last form.

Type Definitions

MeaningResult

Either a Meaning, or a String explaining the error.

TrampolineResult

Either a Trampoline, or a String describing the error.