Review

• Symbols, Environments and Expression Evaluation

Environment Processing in a Small Lisp Interpreter

Environment processing in the context of a programming language interpreter is more complex than our math evaluation application, for several reasons.

• We may have several different environments or namespaces. In Small Lisp, functions and variables each have their own namespace.
• During execution of programs, the environment of symbols available for evaluation of expressions may be constantly changing.

Function Environments in Small Lisp

In Small Lisp, there are two types of function environment that make sense.

• One is the environment mapping the predefined functions such as first, rest, endp and so on to the Haskell routines that will implement the semantic operations associated with these primitives.
• The second is an environment that comprises the set of user-defined functions that occur in the Small Lisp program.

Value Environments in Small Lisp

Value environments are the environments that map variable names to their values as Small Lisp S-expressions. These environments are changing throughout program execution.

• Every time a function is called, the evaluations are carried out in an updated environment having mappings from the function parameters to the value of corresponding arguments.
• Every time a let-expression is evaluated, we need to update the environment with mappings from the local variables of the let expression to their corresponding values.

In addition, we may have some predefined global values of variables. In Small Lisp, this means that we have an initial global environment with the following mappings.

[("otherwise", SymAtom "T"), ("T", SymAtom "T"), ("F", SymAtom "F")]

Analysis of Environment Processing

Assuming the environments are available, the heart of the interpreter will be implemented by:

sl-eval[expr; fn-env; value-env]

Evaluate an S-Lisp expression in the context of given environments. The result is an S-expression (Lisp value).

• Function Environments.
  • One global set of function definitions.
  • extend-fn-env builds the environment only before the start of evaluation.
  • fn-env may be large (many function definitions).
  • apply-fn-env must search these every time a function is called during evaluation.
  • Possibly optimize apply-fn-env at the expense of extend-fn-env.
• Value Environments.
  • Global: typically a small number of constant definitions.
  • Local: a small number of function parameters and possibly let expression variables.
  • On function calls:
    • Evaluate arguments in current (global + local) environment.
    • Reset to the global environment before call.
    • New environment function: reset-to-global-frame.
    • Establish new local environment for parameters.
    • Let expression also add bindings with extend-env.
    • Keep extend-env efficient.
    • apply-env can use linear search (very few bindings).