abstract syntax
The Lisp 1.5 manual defined these ``meta'' expressions. A variable,
, is an Mexpression, and an Sexpression is an Mexpression (these
are the constants). Then the lambda terms and conditionals are as well. Here
is an inductive definition.
Exercise: This Mexpression - Pure Lisp is a
typed language. Write the types of cons, car, cdr, atom?,
null?, ,
and
.
semantics
We have given an environment semantics for Mexpressions without the constants. It is routine to extend this to the full set of Mexpressions either using rewrite semantics or natural semantics or environment semantics.
Exercise: Give a complete environment semantics for these Mexpressions. Write it in such a way that you could implement it in ML.