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 dont have % to have them if we dont 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 |