The evaluation function for terms can now be used on
Sexpressions as well. For example,
Exercise: Add all the clauses needed to define Eval and Apply for the full Pure Lisp language.
The functions Eval and Apply are recursively defined functions that simply manipulate Sexpressions and Environments. An environment can be represented as an association list as we showed in CN93, 16. So Eval and Apply could be written themselves as Sexpressions. Call the resulting programs EVAL and APPLY. We can arrange things so that
We call EVAL a metacircular evaluator. It is defined entirely inside Lisp, as an Sexpression, and it mirrors the external evalutor Eval. EVAL cannot be used to evaluate since it is just an Sexpression not a function (an Mexpression belonging to a function type).
Exercise: Problem with Lisp Reflection
Notice that for Sexpressions ,
But
and
So . This means that trans does not even respect the basic computational equality on
Mexpressions.
Give an example of nonintuitive behavior that arises from the fact that trans is not a well-defined function.
Try to diagnose the reason for this situation and suggest a possible remedy.