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(fun(Name, Formal, Body), Context, funval(Name, 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).

val4(applyrec(Function, Actual), Context, Value) :-
  val4(Function, Context, funval(Name, Formal, Body, Nesting)),
  val4(Actual, Context, ParamValue),
  val4(Body, [bind(Name, funval(Name, Formal, Body, Nesting)), bind(Formal, ParamValue)|Nesting], Value).

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

/*
   Example: val4(let( g, fun(f, x, applyrec(var(f), var(x))), applyrec(var(g), const(1))), nil, X).
 */