val4(plus(X, Y), Context, Value) :-
  val4(X, Context, XValue),
  val4(Y, Context, YValue),
  Value is XValue + YValue.

val4(times(X, Y), Context, Value) :-
  val4(X, Context, XValue),
  val4(Y, Context, YValue),
  Value is XValue * YValue.

val4(const(X), _, X).

val4(var(X), Context, Value) :-
  lookup(X, Context, Value).

val4(let(X, Exp1, Exp2), Context, Value2) :-
  val4(Exp1, Context, Value1),
  val4(Exp2, [bind(X, Value1) | Context], Value2).

val4(fn(Formal, Body), Context, fval(Formal, Body, Context)).

val4(apply(Function, Actual), Context, Value) :-
  val4(Function, Context, fval(Formal, Body, Nesting)),
  val4(Actual, Context, ParamValue),
  val4(Body, [bind(Formal, ParamValue)|Nesting], Value).

lookup(Variable, [bind(Variable, Value)|_], Value).
lookup(VarX, [bind(VarY, _)|Rest], Value) :-
  VarX \= VarY, lookup(VarX, Rest, Value).

/*
   val4(let(y, const(1), let(y, const(2), var(y))), nil, X).
 
   val4(let(a, plus(const(3), const(4)), times(var(a), const(5))), nil, V).

   val4(apply(fn(x,times(var(x), var(x))), const(3)), nil, X).

   val4(let(x, const(1), let(f, fn(n, plus(var(n), var(x))), let(x, const(2), apply(var(f), const(0))))), nil, X).

   val4(let(f,fn(x,let(g,fn(y,plus(var(y),var(x))), var(g))), apply(apply(var(f),const(1)),const(2))),nil, X).
 */