type terme =
  | Var of string
  | Lambda of string * terme
  | Application of terme * terme
  | Nothing
  | Multiplication of terme * terme
  | Addition of terme * terme
  | Number of int
  | Boolean of bool
  | If of terme * terme * terme
;;

let t_true = Boolean(true) and
    t_false = Boolean(false) and
    t_three = Number(3) and
    identity = Lambda("x", Var("x")) and
    multiplication = Lambda("x", Lambda("y", Multiplication(Var("x"), Var("y"))))
;;


let get_val = function
    Var s -> s
  | _ -> failwith "Bad Type in get_val"
;;


let identity = Lambda("x", Var("x"));;
let three = Application(identity, Number(3));;

let lookup env k =
  snd  (List.find (fun x-> ((fst x)=k)) env)
;;

let rec remplace l t i = match l with
    Lambda(v, b) -> Lambda(v, (remplace b t i))
  | Var(x) ->
      if x = t then
    i
      else
    l
  | _ -> failwith "test"
;;

remplace (Lambda ("x", Var("x"))) "x" (Number(3))
;;

let rec evaluate terme env = match terme with
  | Application(l, t) ->(
      let l = evaluate l env in
      let t = evaluate t env in
    match l with
        Lambda(v, b) -> evaluate b ((v, t)::env)
    )
  | Var(v) ->
      begin
    try
      lookup env v
    with Not_found -> terme
      end
  | Multiplication(t1, t2) ->
      begin
    let t1v = evaluate t1 env and
        t2v = evaluate t2 env in
      match (t1v, t2v) with
        | (Number(x), Number(y)) -> Number(x*y)

        | _ -> Multiplication(t1v, t2v)
      end
  | Lambda(v, b) -> Lambda(v, (evaluate b env))
  | _ -> terme
;;


evaluate (Application(identity, Number(42))) [];; (* -> 42 *)

evaluate three [];;

evaluate (Application(Lambda("x",
                (Application(Lambda("y",
                        Multiplication(Var("x"), Var("y"))),
                     Number(3)))),
             Number(2))) [];;


evaluate (Application (Application (multiplication, Number(2)), Number(3))) [];;