% CPSC 312 - 2024 Simple Functional Language FunLog
% Copyright D. Poole, 2023. This program is released under GPL,
%      version 3 or later; see http://www.gnu.org/licenses/gpl.html


:- op(700, xfx, ===).

% lookup(X,Env,V)  is true when X has value V in Env.
lookup(X,Env,V) :- member(val(X,V), Env).

% try:
%?- lookup(b,[val(aa,3), val(b,7), val(dd,23)],V).

%eval(Exp, Env, V) is true if expression Exp evaluates to V given environment Env
eval(X,Env,V) :-
    lookup(X,Env,V).
eval(N,_,N) :-
    number(N).
eval((A+B),Env,V) :-
    eval(A,Env,VA),
    eval(B,Env,VB),
    V is VA+VB.
eval((A-B),Env,V) :-
    eval(A,Env,VA),
    eval(B,Env,VB),
    V is VA-VB.
eval((A*B),Env,V) :-
    eval(A,Env,VA),
    eval(B,Env,VB),
    V is VA*VB.

eval(FV,Env,V) :-
    FV =.. [Fun|Args],
    eval_args(Args,Env,EAgs),
    FEA =.. [Fun|EAgs],
    FEA === Def,
    eval(Def,Env,V).

% eval_args(L0,E,L1) -  L1 is the list of the evaluation of each elements of L0 in environment E
eval_args([],_,[]).
eval_args([H|T],E,[HE|TE]) :-
    eval(H,E,HE),
    eval_args(T,E,TE).

sq(X) === X*X.
% try:
% ?- eval(sq(sq(3)),[],R).


fac(0) === 1.
fac(N) === N * fac(N-1)  :- N>0.

% try:
% eval(fac(4), [], V).
% eval(dd+fac(4+b-aa), [val(aa,3), val(b,7), val(dd,23)], V).

fib(0) === 1.
fib(1) === 1.
fib(N) === fib(N-1)+fib(N-2) :- N>1.


% eval(fib(10), [], V).
% eval(fib(20), [], V).
% eval(fib(30), [], V).

% fib1(N) returns the N'th Fibonacci number
fib1(0) === 1.
fib1(N) === fib2(N-1,1,1).

% fib2(N,F0,F1) returns the N'th Fibonacci number given
%    the current one is F1 and the previous one was F0.
fib2(0,_,F) === F.
fib2(N,F0,F1) === fib2(N-1,F1,F0+F1) :- N>0.

% eval(fib1(10), [], V).
% eval(fib1(500), [], V).  
% eval(fib1(dd*b)*aa-7, [val(aa,3), val(b,7), val(dd,23)], V).