(* The core of an interpreter *)

type value = int;;
type variable = string;;

type expression =
  | Int of value
  | Plus of expression * expression
  | Times of expression * expression
  | Variable of variable
  | Let of variable * (*named value*)expression * (*body*)expression;;

(* A map from variable name to int values: *)
type environment =
    (variable * value) list;;

(* Look for the value corresponding to the given variable: *)
let rec lookup variable environment =
  match environment with
    | [] -> failwith "unbound variable"
    | (first_variable, first_value) :: rest ->
      if variable = first_variable then
        first_value
      else
        lookup variable rest;;

(* Given a variable, a value and an environment, return the environment
   exteded with the pair <variable, value>: *)
let rec bind variable value environment =
  (variable, value) :: environment;;

let rec eval expression environment =
  match expression with
    | Variable v ->
      lookup v environment
    | Int i ->
      i
    | Plus(e1, e2) ->
      (eval e1 environment) + (eval e2 environment)
    | Times(e1, e2) ->
      (eval e1 environment) * (eval e2 environment)
    | Let(v, named_expression, body) ->
      let named_value = eval named_expression environment in
      let extended_environment = bind v named_value environment in
      eval body extended_environment;;


let e =
  Let("x",
      Plus(Int 2,
           Int 2),
      Plus(Int 42,
           Times(Variable "x",
                 Plus(Int 3,
                      Int 7))));;

print_int (eval e []);;
print_newline ();;