Skip to content

Instantly share code, notes, and snippets.

@mhyee

mhyee/slow_typechecking.ml

Last active April 14, 2018 20:37
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mhyee/11129840 to your computer and use it in GitHub Desktop.
Save mhyee/11129840 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
slow_typechecking.ml
(* B. C. Pierce, Types and Programming Languages. MIT Press, 2002, ch. 22, sec 7. *)
(* This progam is well typed, but demonstrates worst-case exponential time of the typechecker. *)
(* In practice, typechecking takes linear time. *)
let f0 = fun x -> (x,x) in
let f1 = fun y -> f0(f0 y) in
let f2 = fun y -> f1(f1 y) in
let f3 = fun y -> f2(f2 y) in
let f4 = fun y -> f3(f3 y) in
let f5 = fun y -> f4(f4 y) in
f5 (fun z -> z)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment