Next: Conclusions Up: The Logic/Functional Style Previous: wang: On-the-Fly Construction

eval: Interpreting a LISP Subset in RELFUN

Most LISP-in-LISP metainterpreters descended from the metacircular eval/apply specification of LISP 1.5 [MAE+62]. The operational semantics of pure LISP was later transcribed to a concise pure PROLOG relation eval [PP82]. The below deterministic RELFUN function eval, corecursive with apply, defines, without concern for efficiency, a non-trivial LISP subset including closures, macros, and an object-level eval.

LISP lists (and function calls) are represented as RELFUN lists (with distinguished first elements). As usual, lists with first element lambda are interpreted as temporary functions. Permanent functions (and macros) become relational defun (and defmacro) facts from which calls extract lambda functions.

For instance, defun(ff,[x],[cond,[[atom,x],x],[t,[ff,[car,x]]]]), asserted as a fact, can be called as in eval([ff,[list,[cdr,[quote,[a,[[b,c],d]]]],2,3]],[]), returning the atom b.


eval([],A) !-& [].
eval(t,A) !-& t.
eval(E,A) :- numberp(E) !& E.
eval(E,A) :- atom(E) ! [_,V] is assoc(E,A) & V.

eval([quote,Exp],A) !-& Exp.
eval([function,Fn],A) !-& [closure,Fn,A].

eval([cond],A) !-& [].
eval([cond,[P,Q]|R],A) :- [] is eval(P,A) !& eval([cond|R],A).
eval([cond,[P,Q]|R],A) !-& eval(Q,A).

eval([Fn|Exps],A) :-
    atom(Fn),
    defmacro(Fn,Args,Body) !&
    eval(apply([lambda,Args,Body],Exps,A),A).

eval([Fn|Exps],A) :-& apply(Fn,evlis(Exps,A),A).


apply(Fn,Vals,A) :-
    atom(Fn),
    defun(Fn,Args,Body) !&
    apply([lambda,Args,Body],Vals,A).

apply(car,[[Hd|Tl]],A) !-& Hd.
apply(cdr,[[Hd|Tl]],A) !-& Tl.
apply(cons,[Hd,Tl],A) !-& [Hd|Tl].
apply(atom,[Val],A) !-& lispatom(Val).
apply(eq,[Val1,Val2],A) !-& lispeq(Val1,Val2).

apply(add1,[Val],A) !-& 1+(Val).
apply(sub1,[Val],A) !-& 1-(Val).

apply(list,Vals,A) !-& Vals.
apply(eval,[Val],A) !-& eval(Val,A).

apply([lambda,[],Body],[],A) !-& eval(Body,A).
apply([lambda,[Arg|Rargs],Body],[Val|Rvals],A) !-&
    apply([lambda,Rargs,Body],Rvals,[[Arg,Val]|A]).

apply([closure,Fn,Env],Vals,A) !-& apply(Fn,Vals,Env).

apply(Fn,Vals,A) :-& apply(eval(Fn,A),Vals,A).

evlis([],A) :-& [].
evlis([E|Re],A) :-& tup(eval(E,A)|evlis(Re,A)).

assoc(N,[]) :-& [].
assoc(N,[[N,V]|Ar]) !-& [N,V].
assoc(N,[_|Ar]) :-& assoc(N,Ar).


lispatom([Hd|Tl]) !-& [].
lispatom(X) :-& t.

lispeq(X,X) :-& t is lispatom(X)!.
lispeq(X,Y) :-& [].

This LISP interpreter performs more well-formedness checks than most LISP-based ones: the correct number and structure of arguments is verified by unification (e.g., quote should have exactly one argument), yielding unknown for ill-formed expressions. The eval function corecurses with the usual evlis auxiliary to evaluate actual arguments; for uniformity, even arguments of special forms and macros are submitted to evlis (in the final eval clause) iff their function is itself the result of an evaluation (in the final apply clause). The specification has no need for the usual pairlis auxiliary because a lambda application leads to an apply recursion through the lambda-argument and actual-value lists; that the Arg/Val pairs thus extend the environment, A, in reversed order does not matter for legal LISP operators, having no duplicate lambda variables (as usual, our interpreter does not prevent formal-argument repetitions; however, by reversing the pair order in the A-list it effects LISP's normal left-to-right evaluation even on lambda binding).



Next: Conclusions Up: The Logic/Functional Style Previous: wang: On-the-Fly Construction


Harold Boley & Michael Sintek (sintek@dfki.uni-kl.de)