Continuation Passing Style
In the discuss post What is the use of Continuation Passing Style (CPS)? I wrote a small explanation that I often link to people when they want to learn about CPS. I believe Jean-Christophe Filliâtre was the first one who told me about CPS and used this example to explain it to me. Here's a copy of my post.
I wrote a small (classical) example:
(* computing the length of a list, not tail-recursive *) let rec list_length = function |  -> 0 | _::s -> 1 + list_length s (* not a tail call *) (* tail-recursive version adding an accumulator *) let list_length_tail l = let rec aux acc = function |  -> acc | _::s -> aux (acc + 1) s in aux 0 l type 'a binary_tree = | Empty | Node of 'a * ('a binary_tree) * ('a binary_tree) (* computing the height of a tree, not tail-recursive *) let rec tree_height = function | Empty -> 0 | Node (_, l, r) -> 1 + max (tree_height l) (tree_height r) (* really hard to make it tail-recursive by adding an accumulator, try it... *) (* tail-recursive version using CPS *) let tree_height_tail t = let rec aux t k = match t with | Empty -> k 0 | Node (_, l, r) -> aux l (fun lh -> aux r (fun rh -> k (1 + max lh rh))) in aux t (fun x -> x) let () = let l = [1; 2; 3; 4] in Format.printf "size of the list is: %d@." (list_length l); Format.printf "size of the list is: %d@." (list_length_tail l); let t = Node (1, Empty, Node(2, Node (3, Empty, Empty), Empty)) in Format.printf "height of the tree is: %d@." (tree_height t); Format.printf "height of the tree is: %d@." (tree_height_tail t)
Also note that getting from the non-CPS version to the CPS one is only a syntactic transformation:
let rec tree_height t = match t with | Empty -> 0 | Node (_, l, r) -> 1 + max (tree_height l) (tree_height r) (* add intermediate values: *) let rec tree_height t = match t with | Empty -> 0 | Node (_, l, r) -> let lh = tree_height l in let rh = tree_height r in 1 + max lh rh (* add a continuation to the args and before returning any value: *) (* this is not valid OCaml *) let rec tree_height t k = match t with | Empty -> k 0 | Node (_, l, r) -> let lh = tree_height l in let rh = tree_height r in k (1 + max lh rh) (* replace all intermediate `let x = f y` by `tree_height y (fun x ->` : *) let rec tree_height t k = match t with | Empty -> k 0 | Node (_, l, r) -> tree_height l (fun lh -> tree_height r (fun rh -> k (1 + max lh rh)))
type a = | Int of int | Float of float (* Safe but uses unnecessary boxing *) let f_safe = function | Int i -> i | Float f -> int_of_float f type b = | Int | Float (* Very unsafe but no useless boxing *) let f_unsafe tag n = match tag with | Int -> (Obj.magic n : int) | Float -> int_of_float (Obj.magic n : float) type _ c = | Int : int c | Float : float c (* Same runtime behaviour as f_unsafe but safe *) let f_gadt : type t. t c -> t -> int = fun tag n -> match tag with | Int -> n | Float -> int_of_float n
How to write the
val equal : unit -> unit -> bool function ?
When I teach OCaml to some people, after some time, I like to ask them this question. Here are the answer I usually get.
let equal x y = if x = y then true else false
Come on ! First you should write it
let equal x y = x = y. But more importantly, there's no need to test for equality, there's only one inhabitant for the
unit type, so it's always
true. Try again !
let equal x y = true
dune will make the compiler shrill because of unused variables. Let's try again.
let equal _ _ = true
Better, but this has the signature
val equal : 'a -> 'b -> bool (and the previous answer too). How can we fix this ?
let equal (_ : unit) (_ : unit) = true
OK. Now this is correct, but it's annoying we have to write the types. Unless...
let equal () () = true
Yippee ! Usually the beginner is a little dumbfounded by this, as I was the first time I found this code in the stdlib. By the way, if you know a shortest way to write these (modulo whitespace changes), please tell me.
Then, what if you want to confuse the beginner completly ?
let equal () = (=) ()
What's the shortest code producing the signature
val f : 'a -> 'b ?
This question has been asked to me by Jean-Christophe Filliâtre while we were working on WebAssembly - don't ask me how we ended up talking about this. I quickly found a solution in 15 characters, but couldn't do better. He had one with 14 characters.
First solution in 20 characters:
let f _=assert false
Second solution in 15 characters:
let rec f x=f x
Third solution in 15 characters:
Fourth solution in 14 characters:
let f _=exit 1
I don't know any better solution, if you do please tell me !