Eval and Apply

The core of of a Lisp interpreter is a pair of functions called eval and apply. The eval function evaluates a Small Lisp in the context of environments of function and value environments.

Eval in Small Lisp

Below is the eval function for Small Lisp, written in Small Lisp!

;;;
;;; "sl-eval": The heart of the Small Lisp interpreter.
;;;
sl-eval[expr; fn-env; value-env] =
  [identifier-p[expr] --> apply-env[value-env; id-name[expr]];
   numeric-atom-expr-p[expr] --> numeric-val[expr];
   symbolic-atom-expr-p[expr] --> symbolic-val[expr];
   list-expr-p[expr] --> list-val[expr];
   fn-call-p[expr] -->
     sl-apply
       [callee[expr]; sl-evlis[arguments[expr]; fn-env; value-env];
        fn-env; reset-to-global-frame[value-env]];
   cond-expr-p[expr] --> sl-evcond[clauses[expr]; fn-env; value-env];
   let-expr-p[expr] -->
     sl-eval
       [final-expr[expr]; fn-env;
        extend-local-env[fn-env; value-env; local-defs[expr]]];
   otherwise --> error2[(Bad S-Lisp expression --); expr]]

;;;
;;; Evaluate a list of expressions in the context of function
;;; and value environments.
;;;
sl-evlis[explist; fn-env; val-env] =
  {val1 = sl-eval[first[explist]; fn-env; val-env] :
   [single-p[explist] --> list1[val1];
    otherwise -->
      cons[val1; sl-evlis[rest[explist]; fn-env; val-env]]]}

;;;
;;; Process conditional clauses by evaluating the clause
;;; predicates until one evaluates to T.  When this happens
;;; evaluate and return the corresponding result expression.
;;;
sl-evcond[condclauses; fn-env; env] =
  [sl-eval[predicate[first[condclauses]]; fn-env; env] -->
     sl-eval[result[first[condclauses]]; fn-env; env];
   single-p[condclauses] -->
     error[(Error in conditional expression -- no true predicate)];
   otherwise --> sl-evcond[rest[condclauses]; fn-env; env]]

;;;
;;; Update the local frame of the value environment with the
;;; bindings (local definitions) of a let expression.
;;;
extend-local-env[fn-env; value-env; local-defs] =
  {var-name = id-name[local-var[first[local-defs]]];
   val = sl-eval[local-val[first[local-defs]]; fn-env; value-env] :
   [single-p[local-defs] --> extend-env[value-env; var-name; val];
    otherwise -->
      extend-env
        [extend-local-env[fn-env; value-env; rest[local-defs]];
         var-name; val]]}

Apply in Small Lisp

;;;
;;; "sl-apply": the core routine for evaluation of
;;; function applications.
;;;
sl-apply[callee; args; fn-env; val-env] =
  {fn = id-name[callee] :
   [eq[fn; "first"] --> first[first[args]];
    eq[fn; "rest"] --> rest[first[args]];
    eq[fn; "endp"] --> endp[first[args]];
    eq[fn; "numberp"] --> numberp[first[args]];
    eq[fn; "symbolp"] --> symbolp[first[args]];
    eq[fn; "listp"] --> listp[first[args]];
    eq[fn; "eq"] --> eq[first[args]; second[args]];
    eq[fn; "cons"] --> cons[first[args]; second[args]];
    eq[fn; "plus"] --> plus[first[args]; second[args]];
    eq[fn; "minus"] --> minus[first[args]; second[args]];
    eq[fn; "times"] --> times[first[args]; second[args]];
    eq[fn; "divide"] --> divide[first[args]; second[args]];
    eq[fn; "rem"] --> rem[first[args]; second[args]];
    eq[fn; "eqp"] --> eqp[first[args]; second[args]];
    eq[fn; "lessp"] --> lessp[first[args]; second[args]];
    eq[fn; "greaterp"] --> greaterp[first[args]; second[args]];
    eq[fn; "sym-lessp"] --> sym-lessp[first[args]; second[args]];
    eq[fn; "explode"] --> explode[first[args]];
    eq[fn; "implode"] --> implode[first[args]];
    eq[fn; "error"] --> error[first[args]];
    otherwise -->
      {defn = apply-fn-env[fn-env; fn] :
       sl-eval
         [body[defn]; fn-env;
          add-associations[val-env; parameters[defn]; args]]}]}

add-associations[env; parms; args] =
  {new-env = extend-env[env; first[parms]; first[args]] :
   [single-p[parms] --> new-env;
    otherwise --> add-associations[new-env; rest[parms]; rest[args]]]}

The Main Program Driver

;;;
;;; This function contains the main driver functions for the
;;; Lisp-in-Lisp interpreter.
;;;
;;; The "interpret" function evaluates an expression (expr) in the
;;; context of a set of function and constant definitions (defs).
;;; It calls the "setup-envs-then-eval" auxiliary function to
;;; do the work of setting up the appropriate function and
;;; value environments before evaluating "expr".
;;;
interpret[defs; expr] =
  setup-envs-then-eval
    [null-fn-env; 
     extend-env
       [extend-env
         [extend-env[null-env; "F"; "F"]; 
          "T"; "T"]; 
        "otherwise"; "T"];
     defs; expr]

setup-envs-then-eval[fn-env; val-env; defs; expr] =
  [endp[defs] --> sl-eval[expr; fn-env; mark-global-frame[val-env]];
   fn-def-p[first[defs]] -->
     setup-envs-then-eval
       [extend-fn-env[fn-env; fn-name[first[defs]]; first[defs]];
        val-env; rest[defs]; expr];
   const-def-p[first[defs]] -->
     setup-envs-then-eval
       [fn-env;
        extend-env
          [val-env; const-name[first[defs]];
           sl-eval[const-val[first[defs]]; fn-env; val-env]];
        rest[defs]; expr]]