STLC from Types and Programming Languages, simplified based on https://github.com/hsk/simpletapl

sb0.ml

type ty =
| TArrow of ty * ty

type exp =
| EVar of string
| EAbs of string * ty * exp
| EApp of exp * exp

let rec typeof env = function
| EVar var -> List.assoc var env
| EAbs(var, t1, e1) -> TArrow(t1, typeof ((var,t1)::env) e1)
| EApp(e1, e2) ->
  let t2 = typeof env e2 in
  (match typeof env e1 with
   | TArrow(t11, t12) ->
     if t11 = t2 then t12
     else failwith "parameter type mismatch"
   | _ -> failwith "non-arrow type in function position")