type expr =     Var of char
                    | Abs of char * expr
                    | App of expr * expr
                    ;;


let freevar var exp =
    let rec freevarIter var  = function
         Var  x           -> true
        |App (u,v)        -> ((freevarIter var u) or (freevarIter var v))
        |Abs (x,u) when x  = var -> false
        |Abs (x,u) when x  !=var -> freevarIter var u

        in freevarIter var exp;;



let rec subst var:expr trm:expr exp:expr = match exp with
        Var  x      when x  = var -> trm
    |   Var  y      when y != var -> y
    |   App (u,v)                           -> App((subst var trm u), (subst var trm v))
    |   Abs (x,u) when (occurrence x u) = false -> Abs(x,u)
    |   Abs (y,u) when ((y != var) AND  (freevar y trm) = false) -> Abs(y,subst var trm u)
    | Abs (y,u) when (freevar y trm) and  (let z = char_of_int( ( Random.int 25 ) + 65 ) );((freevar z u) OR (freevar z trm)) -> subst(var trm (Abs(z,subst z y)));;