<br />
<b>Deprecated</b>:  The each() function is deprecated. This message will be suppressed on further calls in <b>/home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php</b> on line <b>456</b><br />
(* 1.6 lambda-calcul *****************************************************)

module VarSet = Set.Make (struct type t = int let compare=compare end);;

type lambda_term = Var of int | Abstr of int*lambda_term |
        Appl of lambda_term*lambda_term ;;

let var_count = ref 0;;

let new_var () = var_count:=!var_count+1; !var_count;;

let rec free_vars = function (Var x) -> VarSet.singleton x
        | (Abstr(x,e)) -> VarSet.remove x (free_vars e)
        | (Appl(e1,e2)) -> VarSet.union (free_vars e1) (free_vars e2);;

let rec subst e1 (x,e2) fv = match e1 with (Var y) when x=y -> e2
        | (Var y) -> Var y
        | (Abstr(y,e)) when x=y -> Abstr(y,e)
        | (Abstr(y,e)) when (VarSet.mem y fv) -> let z = new_var() in
              Abstr(z, subst (subst e (y,Var z) (VarSet.singleton z)) (x,e2) fv)
        | (Abstr(y,e)) -> Abstr(y, subst e (x,e2) fv)
        | (Appl(e,f)) -> Appl(subst e (x,e2) fv, subst f (x,e2) fv);;

let substitution e1 (x,e2) = subst e1 (x,e2) (free_vars e2);;

let rec interpret = function (Var x) -> Var x
        | (Abstr(x,e)) -> Abstr(x,interpret e)
        | (Appl(e1,e2)) -> let ie1 = interpret e1 in ( match ie1 with
                (Abstr(x,e)) -> interpret (substitution e (x,e2))
                | _ -> Appl(ie1, interpret e2) );;

let x = new_var();;
let y = new_var();;
let t = Abstr(x, Abstr(y, Var x));;
let f = Abstr(x, Abstr(y, Var y));;
let cond e1 e2 e3 = Appl(Appl(t, e1), e2);;

interpret(cond t t f);;