| Previous | Table of Contents | Next |
Finally, here is a simple pure Lisp interpreter.
In this interpreter, each Lisp s-expression (a b c) is encoded as a list [a,b,c]; thus, for instance, [append,x,y] for (append x y). Quoting must be done explicitly, as for instance [quote,[a,b]] for ‘(a b). I encourage you, as an exercise, to write a two-level parser using DCGs (section 6.3.9.5) to parse a Lisp source file into the form expected by this interpreter.
To evaluate an expression E, pose the query eval(E, Result); Result is instantiated to its value. Functions are defined by adding clauses of the form defun(Funcname, Arglist, Funcbody) to the program; they could instead be asserted after being parsed from an input file. Nexpr functions, which do not evaluate their arguments, are similarly defined using defun_nexpr.
Listing 6.6. A simple Lisp interpreter.
% Main predicate.
% eval(S, Result): Result is the result of evaluating S.
eval(S, Result) :-
eval1(S, [], Result).
% eval(S, Env, Result): Result is the result of evaluating
% S in the context of the variable bindings in Env.
eval1([F|Args], Env, Result) :-
!,
eval_appl(F, Args, Env, Result).
eval1([quote,Arg], _, Arg) :- !.
eval1(A, Env, Result) :-
eval_atom(A, Env, Result).
% eval_appl(F, Args, Env, Result): Result is the result
% of applying function F to Args, in environment Env.
eval_appl(F, Args, Env, Result) :-
( defined_func(F, Nargs) ->
( length(Args, Nargs) ->
eval_appl1(F, Args, Env, Result);
( write(‘Wrong number of arguments: ‘),
write([F|Args]), nl,
Result=nil
)
);
( write(‘Undefined function: ‘),
write(F), nl,
Result=nil
)
).
% defined_func(Funcname, N): Funcname is the name
% of a defined function with N arguments.
% Builtins…
defined_func(eq, 2).
defined_func(car, 1).
defined_func(cdr, 1).
defined_func(cons, 2).
defined_func(cond, _).
defined_func(quote, 1).
defined_func(eval, 1).
% …and user-defined functions.
defined_func(Func, Nargs) :-
defun(Func, Args, _),
length(Args, Nargs).
defined_func(Func, Nargs) :-
defun_nexpr(Func, Args, _),
length(Args, Nargs).
% Evaluate a function with the right number of arguments.
% Builtins…
eval_appl1(eq, [S,T], Env, Result) :-
eval1(S, Env, Sval),
eval1(T, Env, Tval),
decide_eq(Sval, Tval, Result).
eval_appl1(car, [S], Env, Result) :-
eval1(S, Env, Sval),
( Sval = [Result|_] ->
true;
Result = nil
).
eval_appl1(cdr, [S], Env, Result) :-
eval1(S, Env, Sval),
( Sval = [_|Result] ->
true;
Result = nil
).
eval_appl1(cons, [S,T], Env, [Sval|Tval]) :-
eval1(S, Env, Sval),
eval1(T, Env, Tval).
eval_appl1(cond, Clauses, Env, Result) :-
eval_cond(Clauses, Env, Result).
eval_appl1(quote, [S], _, S).
eval_appl1(eval, [S], Env, Result) :-
eval1(S, Env, Sval),
eval1(Sval, Env, Result).
% … and user-defined functions.
eval_appl1(Func, Aparams, Env, Result) :-
defun(Func, Fparams, Body),
map_eval1(Aparams, Env, Evalparams),
build_env(Fparams, Evalparams, Newenv),
eval1(Body, Newenv, Result).
eval_appl1(Func, Aparams, _Env, Result) :-
defun_nexpr(Func, Fparams, Body),
build_env(Fparams, Aparams, Newenv),
eval1(Body, Newenv, Result).
% Decide on the result of an eq
% decide_eq(S, T, Result): Result is t if S and T are
% identical (for Lisp purposes), and nil otherwise.
decide_eq(S, S, t) :- !.
decide_eq([], nil, t) :- !.
decide_eq(nil, [], t) :- !.
decide_eq(_S, _T, nil).
% eval_cond(Cond_clauses, Env, Result): Result is the
% result of evaluating a cond expression whose list of
% clauses is in Cond_clauses.
% If have reached end of cond, return nil.
eval_cond([], _, nil).
% Otherwise, evaluate the test and decide on the result.
eval_cond([[Test,S]|Clauses], Env, Result) :-
!,
eval1(Test, Env, Testval),
eval_cond1(Testval, S, Clauses, Env, Result).
% We could consider a list after the test in a cond clause
% to be correct, and return the last one evaluated, but in
% a pure Lisp this is probably erroneous.
eval_cond([[_Head|Rest]|_], _, nil) :-
!,
write(‘Error: list after cond test: ‘), write(Rest), nl.
eval_cond([Atom|_], _, nil) :-
write(‘Error: atom instead of cond clause: ‘),
write(Atom), nl.
% eval_cond1(Testval, S, Clauses, Env, Result): if Testval
% is non-nil, Result is the value of S; otherwise, Result is the
% value of a cond expression containing Clauses.
% Interpret nil as false, non-nil as true.
% If test value is nil, go on with other clauses
eval_cond1(nil, _, Clauses, Env, Result) :-
!,
eval_cond(Clauses, Env, Result).
% If test value is not nil but rest of clause is empty,
% return test value
eval_cond1(Testval, [], _, _, Testval) :-
!.
% Otherwise, evaluate rest of clause
eval_cond1(_Testval, S, _, Env, Result) :-
eval1(S, Env, Result).
% map_eval1(Exprs, Env, Values): Values is the list of
% the values of Exprs, when evaluated in binding
% environment Env.
map_eval1([], _, []).
map_eval1([S|Ss], Env, [T|Ts]) :-
eval1(S, Env, T),
map_eval1(Ss, Env, Ts).
% build_env(Varnames, Values, Env): Where Varnames is
% x1, …, xn and Values is v1, …, vn, build the
% environment bind(x1,v1), …, bind(xn,vn).
build_env([], [], []).
build_env([F|Fs], [A|As], [bind(F,A)|Env]) :-
build_env(Fs, As, Env).
% eval_atom(Atom, Env, Value): Value is the value of
% Atom, according to Env.
eval_atom(t, _, t) :- !.
eval_atom(nil, _, nil) :- !.
eval_atom(S, Env, Result) :-
getval(Env, S, Result).
% getval(Env, Atom, Val): bind(Atom,Val) is a member
% of Env.
getval([], S, nil) :-
write(‘Undefined atom: ‘), write(S), nl.
getval([bind(S,T)|_], S, T) :- !.
getval([bind(_S1,_)|Env], S, Result) :-
getval(Env, S, Result).
% Declare functions as dynamic, since don’t have
% to have them if we don’t want to.
:- dynamic defun/3.
:- dynamic defun_nexpr/3.
% Some sample function definitions
defun(null, [x],
[eq,x,nil]
).
defun(append, [x,y],
[cond,[[null,x],y],
[t,[cons,[car,x],[append,[cdr,x],y]]]]
).
defun(member, [x,y],
[cond,[[null,y],nil],
[[eq,x,[car,y]],t],
[t,[member,x,[cdr,y]]]]
| Previous | Table of Contents | Next |