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
"Separating Syntactic Analysis from Execution", chapter 4.1.7 of Structure and Interpretation of Computer Programs by Abelson et all
"Fast Interpretation", chapter 6 in Lisp In Small Pieces by Christian Queinnec
Structs
Meaning | The |
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 |
TrampolineResult | Either a |