Lisp in Lisp: An S-Lisp Interpreter

CMPT 384 Lecture Notes
Robert D. Cameron
October 1, 1999

Running a Small Lisp program =: evaluating a Small Lisp expression in the context of a set of constant and function definitions.

Two environments:

fn-env maps function names to their (global) definitions.
value-env maps variable names to their values, which may come from
1. global constant definitions.
2. parameter bindings for user-defined functions.
3. local bindings for let expressions.

To allow for different representations, we will process function environments using functions name null-fn-env, defined-fn-p, apply-fn-env, and extend-fn-env.

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 will be the same S-expression (Lisp value) that would be computed by smlisp given the m-Lisp version of expr and an equivalent context.

Analysis of Environment Processing

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:
  1. Evaluate arguments in current (global + local) environment.
  2. Reset to the global environment before call.
    New environment function: reset-to-global-frame.
  3. 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).

Binary Trees for Function Environments

100--1000 function definitions/program.

Linear searches in apply-fn-env would be expensive.

Environments based on binary trees provide for faster access.

<env-tree> ::= <empty-node> | <tree-node>
<empty-node> ::= ( )

<tree-node> ::= ( <key:ident> <left-env:env-tree> <right-env:env-tree> <key-value:fn-def> )

A <treenode> splits the environment in two:

<left-env:env-tree> for all the identifiers less than the <key:ident>.
<right-env:env-tree> for all the identifiers greater than the <key:ident>.

apply-fn-env[env; name] = 
  [empty-node-p[env] --> 
     error2[(Undefined function --); name];
   eq[name; key[env]] --> key-value[env];
   sym-lessp[name; key[env]] --> 
     apply-fn-env[left-env[env]; name];
   otherwise --> apply-fn-env[right-env[env]; name]]

<env-tree>	::=	<empty-node> \| <tree-node>
<empty-node>	::=	`(` `)`
<tree-node>	::=	`(` <key:ident> <left-env:env-tree> <right-env:env-tree> <key-value:fn-def> `)`

extend-fn-env[env; name; val] = 
  [empty-node-p[env] -->
     make-tree-node
       [name; empty-node; empty-node; val];
   eq[name; key[env]] -->
     make-tree-node
       [name; left-env[env]; right-env[env]; val];
   sym-lessp[name; key[env]] -->
     make-tree-node
       [key[env]; 
        extend-fn-env[left-env[env]; name; val];
        right-env[env]; 
        key-value[env]];
   otherwise -->
     make-tree-node
       [key[env]; 
        left-env[env];
        extend-fn-env[right-env[env]; name; val]; 
        key-value[env]]]

null-fn-env = empty-node

Value Environments with Global/Local Frames

Extend association lists with frames.

<value-env> ::= ( <local-frame:assoc-list> <global-frame:assoc-list> )

apply-env[env; name] =
  {local-binding = assoc[local-frame[env]; name] :
   [endp[local-binding] -->
      {global-binding = assoc[global-frame[env]; name] :
       [endp[global-binding] -->
          error2[(Undefined variable --); name];
        otherwise --> assoc-val[global-binding]]};
    otherwise --> assoc-val[local-binding]]}

null-env = (() ())

extend-env[env; name; val] =
  make-value-env
    [cons[make-binding[name; val]; local-frame[env]];
     global-frame[env]]

mark-global-frame[env] =
   make-value-env[(); local-frame[env]]

reset-to-global-frame[env] = 
  make-value-env[(); global-frame[env]]

Evaluation: `sl-eval`

From the GRAIL grammar:

<expression> ::= <identifier> | <numeric-atom-expr> | <symbolic-atom-expr> | <list-expr> | <fn-call> | <cond-expr> | <let-expr>

<identifier> ::= <id-name:symbolic atom>

<numeric-atom-expr> ::= <numeric-val:numeric atom>

<symbolic-atom-expr> ::= ( quote <symbolic-val:symbolic-atom> )

<list-expr> ::= ( quote <list-val:list> )

<fn-call> ::= ( <callee:identifier> <arguments:expression⁺> )

<cond-expr> ::= ( cond <clauses:clause⁺> )

<clause> ::= ( <predicate:expression> <result:expression> )

<let-expr> ::= ( let ( <local-defs:local-def⁺> ) <final-expr:expression> )

<local-def> ::= ( <local-var:variable> <local-val:expression> )

We expect:

sl-eval[expr; fn-env; value-env] =
  [identifier-p[expr] -->
   numeric-atom-expr-p[expr] --> 
   symbolic-atom-expr-p[expr] -->
   list-expr-p[expr] --> 
   fn-call-p[expr] -->
   cond-expr-p[expr] --> 
   let-expr-p[expr] -->
   otherwise --> error2[(Bad S-Lisp expression --); expr]]

Evaluating Variables and Constants

<identifier>	::=	<id-name:symbolic atom>
<numeric-atom-expr>	::=	<numeric-val:numeric atom>
<symbolic-atom-expr>	::=	`(` `quote` <symbolic-val:symbolic-atom> `)`
<list-expr>	::=	`(` `quote` <list-val:list> `)`

Variables:

identifier-p[expr] --> 
  apply-env[value-env; id-name[expr]];

Constants:

numeric-atom-expr-p[expr] --> numeric-val[expr];
symbolic-atom-expr-p[expr] --> symbol-val[expr];
list-expr-p[expr] --> list-val[expr]

Evaluating Conditional Expressions

<cond-expr>	::=	`(` `cond` <clauses:clause⁺> `)`
<clause>	::=	`(` <predicate:expression> <result:expression> `)`

Evaluate clause predicates in order until one returns T.

Then evaluate and return the corresponding result.

We call an auxiliary function from sl-eval:

cond-expr-p[expr] -->
  sl-evcond[clauses[expr]; fn-env; value-env];

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]]

Evaluating Let Expressions

<let-expr>	::=	`(` `let` `(` <local-defs:local-def⁺> `)` <final-expr:expression> `)`
<local-def>	::=	`(` <local-var:variable> <local-val:expression> `)`

Evaluate the final expression in the context of an updated local environment.

let-expr-p[expr] -->
  sl-eval
    [final-expr[expr];
     fn-env;
     extend-local-env
       [fn-env; value-env; local-defs[expr]]];

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]]}

Evaluating Function Calls: `sl-apply`

<fn-call> ::= ( <callee:identifier> <arguments:expression⁺> )

First we need to evaluate the argument list.

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]]]}

The sl-apply is defined to apply the function to the evaluated arguments.

fn-call-p[expr] -->
  sl-apply
    [callee[expr]; 
     sl-evlis[arguments[expr]; fn-env; value-env];
     fn-env; 
     reset-to-global-frame[value-env]];

Note that the environment must be reset to the global frame so that the current local definitions are not available to the called function.

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; "eq"] --> eq[first[args]; second[args]];
    eq[fn; "cons"] --> cons[first[args]; second[args]];
    eq[fn; "plus"] --> plus[first[args]; second[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]]]}

Putting it All Together

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]]

Interpreting a Program

To run a program, we need an interpret function to build the environments.

First idea:

interpret[defs; expr] =
  sl-eval[expr; mk-func-env[defs]; mk-const-env[defs]]

Doesn't allow constant definitions to use previously defined functions and constants.

Solution: use accumulating parameters for the value and function environments set up so far.

Define the auxiliary

setup-envs-then-eval[fn-env; val-env; defs; expr]

to process definitions with the accumulating parameters fn-env and val-env and finally evaluate the 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]

<fn-def>	::=	`(` `defun` <fn-name:identifier> `(` <parameters:identifier⁺> `)` <body:expression> `)`
<const-def>	::=	`(` `setc` <const-name:identifier> <const-val:expression> `)`

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]]

<expression>	::=	<identifier> \| <numeric-atom-expr> \| <symbolic-atom-expr> \| <list-expr> \| <fn-call> \| <cond-expr> \| <let-expr>
<identifier>	::=	<id-name:symbolic atom>
<numeric-atom-expr>	::=	<numeric-val:numeric atom>
<symbolic-atom-expr>	::=	`(` `quote` <symbolic-val:symbolic-atom> `)`
<list-expr>	::=	`(` `quote` <list-val:list> `)`
<fn-call>	::=	`(` <callee:identifier> <arguments:expression⁺> `)`
<cond-expr>	::=	`(` `cond` <clauses:clause⁺> `)`
<clause>	::=	`(` <predicate:expression> <result:expression> `)`
<let-expr>	::=	`(` `let` `(` <local-defs:local-def⁺> `)` <final-expr:expression> `)`
<local-def>	::=	`(` <local-var:variable> <local-val:expression> `)`