OCaml

Small tutorials

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)))

GADT

In the discuss post Representing data more compactly but unsafely, Emile Trotignon gave the following example which I really like:

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

Small riddles

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.

First answer:

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 !

Second answer:

let equal x y = true

Well, dune will make the compiler shrill because of unused variables. Let's try again.

Third answer:

let equal _ _ = true

Better, but this has the signature val equal : 'a -> 'b -> bool (and the previous answer too). How can we fix this ?

Fourth answer:

let equal (_ : unit) (_ : unit) = true

OK. Now this is correct, but it's annoying we have to write the types. Unless...

Fifth answer:

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 ?

Sixth answer:

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:

let f=Obj.magic

Fourth solution in 14 characters:

let f _=exit 1

I don't know any better solution, if you do please tell me !