open Ast

exception Unification_failed

let rec eval term env f s = match term with
  | ICons("Fail") -> f s
  | ICons(t) -> s (VTuple(t, []))
  | IVar i -> s (List.nth env i)
  | ILam (pat, body) -> s (VClos (env, pat, body, f))
  | IAlt (e1, e2) ->
      eval e1 env (fun k -> print_string "trying alternative\n"; 
        eval e2 env f s) s
  | IApp (e1, e2) ->
      eval e1 env f (function
        | VClos (env', pat, body, f') ->
            eval e2 env f (fun arg ->
              match (try Some (make_env env' pat arg)
                with Unification_failed -> None) with
                | Some env'' -> eval body env'' f' s
                | None -> f' s)
        | VTuple (t, items) ->
            eval e2 env f (fun arg ->
              s (VTuple (t, items@[arg])))
        | _ -> failwith "invalid application")
        
and make_env env pat arg = match pat, arg with
  | PHole (_), v -> v :: env
  | PTuple (tag, items), VTuple (tag', items')  when tag = tag' ->
      List.fold_left2 (fun env' i1 i2 -> make_env env' i1 i2) env items items'
  | _ -> raise Unification_failed

let run imm = eval imm []
  (fun _ ->                             (* fail *)
    failwith "No pattern matched")
  (fun v -> v)                          (* succeed *)