
% write a little prolog interpreter in prolog

% write a little scheme interpreter in prolog

% s_eval(+, +, -)


% representation:
%  - hunk of "scheme" code
%  - lists, numbers, symbols: use prolog lists, num, sym
%  - environment: mapping variable names to values
%  - function (as returned by lambda): hunk of code, env, formals

% HUNK OF CODE:
% (cons (+ 1 2) (foo y))
% [cons, [+,1,2], [foo,y]]

% ENV
% x->3, y->7, z->blah
% [[x,3],[y,7],[z,blah]]

% FUNCTION
% thing returned by
%   (let ((x 1) (y 2)) (lambda (z) (+ z x)))
%   ((lambda (x y) (lambda (z) (+ z x)))  1 2)
%   [[lambda, [x,y], [lambda, [z], [+,z,x]]], 1, 2]
%   fun([z],  [+,z,x],   [[x,1],[y,2]])

s_eval(N, _, N) :- number(N).
s_eval([quote,X], _, X).
s_eval([], _, []).
s_eval([lambda, Formals, Body], Env, fun(Formals, Body, Env)).

s_eval(+, _, +).
s_eval(*, _, *).
s_eval(cons, _, cons).
s_eval(=, _, =).

s_eval(Exp, Env, Val) :- atom(Exp), member([Exp,Val], Env).

s_eval([if,Test,Then,Else], Env, Val) :-
	s_eval(Test,Env,Tval),
	s_evalif(Tval, Then, Else, Env, Val).

%% Macro expand LET:
s_eval([let, Vardefs, Body], Env, Val) :-
	maplist(Vars, Defs, Vardefs),
	s_eval([[lambda,Vars,Body] | Defs], Env, Val).

s_eval(Exprlis, Env, Val) :-
	s_evlist(Exprlis, Env, [Fun|Args]),
	s_apply(Fun, Args, Val).

s_evlist([], _, []).
s_evlist([Exp|Lis], Env, [Val|Vlis]) :-
	s_eval(Exp, Env, Val),
	s_evlist(Lis, Env, Vlis).

s_apply(+, [X,Y], Z) :- Z is X+Y.
s_apply(*, [X,Y], Z) :- Z is X*Y.
s_apply(cons, [X,Y], [X|Y]).
s_apply(=, [X,X], true) :- !.
s_apply(=, [_,_], false).

s_apply(fun(Formals, Body, Env), Arglist, Val) :-
	maplist(Formals, Arglist, Rib),
	append(Rib, Env, NewEnv),
	s_eval(Body, NewEnv, Val).

maplist([],[],[]).
maplist([A|X], [B|Y], [[A,B] | Z]) :- maplist(X, Y, Z).

s_evalif(false, _   , Else, Env, Val) :- !, s_eval(Else, Env, Val).
s_evalif(_,     Then, _,    Env, Val) :-    s_eval(Then, Env, Val).
