Previous Table of Contents Next


6.5.5. A Simple Lisp Interpreter

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