The goal of this lecture note is to explain the origin of type errors whose error messages include a slash (i.e., the character /) that is followed by a version number.
To consolidate his foundations, Halcyon is implementing the onion type all by himself. So he opens a file (C-x C-f Halcyon's onions.ml) and garnishes it as follows:
(* Halcyon's onions.ml *)
(* A miscellany of agricultural computations. *)
(* ********** *)
type onion =
| Bud
| Layer of onion;;
(* ********** *)
(* end of Halcyon's onions.ml *)
let end_of_file = "Halcyon's onions.ml";;
(* remember to put the digital signature here! *)
In words, he sets up the header and the footer of his file and declares the type of onions.
Thoughtfully, he then proceeds to implement a recursive function that counts the number of layers in any given onions:
(* Halcyon's onions.ml *)
(* A miscellany of agricultural computations. *)
(* ********** *)
type onion =
| Bud
| Layer of onion;;
(* ***** *)
let number_of_layers o =
let rec loop o =
match o with
| Bud ->
0
| Layer o' ->
succ (loop o')
in loop o;;
(* ********** *)
(* end of Halcyon's onions.ml *)
let end_of_file = "Halcyon's onions.ml";;
(* remember to put the digital signature here! *)
He then verifies his file with OCaml:
# #use "Halcyon's onions.ml";;
type onion = Bud | Layer of onion
val number_of_layers : onion -> int = <fun>
#
He then happily proceeds to also implement a tail-recursive version of the same function that uses an accumulator:
(* Halcyon's onions.ml *)
(* A miscellany of agricultural computations. *)
(* ********** *)
type onion =
| Bud
| Layer of onion;;
(* ***** *)
let number_of_layers o =
let rec loop o =
match o with
| Bud ->
0
| Layer o' ->
succ (loop o')
in loop o;;
(* ***** *)
let tr_number_of_layers o =
let rec loop o a =
match o with
| Bud ->
a
| Layer o' ->
loop o' (succ a)
in loop o 0;;
(* ********** *)
(* end of Halcyon's onions.ml *)
let end_of_file = "Halcyon's onions.ml";;
(* remember to put the digital signature here! *)
Again, he verifies his file with OCaml:
# #use "Halcyon's onions.ml";;
type onion = Bud | Layer of onion
val number_of_layers : onion -> int = <fun>
val tr_number_of_layers : onion -> int = <fun>
val end_of_file : string = "Halcyon's onions.ml"
#
Struck by inspiration, he then conceives a generator of random onions in order to test his code. Here is the result of his brainstorm with Vigfus:
let nat_fold_left zero_case succ_case n =
let () = assert (n >= 0) in
let rec loop i a =
if i = 0
then a
else loop (pred i) (succ_case a)
in loop n zero_case;;
let generate_random_onion n =
let () = assert (n > 0) in
let number_of_layers = Random.int n
in (number_of_layers, nat_fold_left Bud (fun o -> Layer o) number_of_layers);;
Applying generate_random_onion to a positive integer returns a pair: the resulting random onion together with its random number of layers. Neat, isn’t it? Here it is at work:
# generate_random_onion 10;;
- : onion * int = (Layer Bud, 1)
# generate_random_onion 10;;
- : onion * int = (Layer (Layer (Layer (Layer (Layer (Layer (Layer Bud)))))), 7)
#
By then Vigfus is up and running, so the unit-test function pretty much writes itself:
let test_number_of_layers name candidate =
let b0 = (candidate Bud = 0)
and b1 = (candidate (Layer Bud) = 1)
and b2 = (candidate (Layer (Layer Bud)) = 2)
and bn = (let (o, n) = generate_random_onion 100
in let expected_result = n
and actual_result = candidate o
in if actual_result = expected_result
then true
else let () = Printf.printf
"test_number_of_layers failed for %s with %d as result instead of the expected %n\n"
name
actual_result
expected_result
in false)
in b0 && b1 && b2 && bn;;
It says something about Vigfus that he dutifully tests this unit-test function with a fake implementation, he is such a friend:
let fake_number_of_layers o =
match o with
| Bud ->
0
| Layer Bud ->
1
| Layer (Layer Bud) ->
2
| _ ->
-1;;
As Vigfus said, the unit-test function sometimes succeeds and sometimes fails, it has something to do with the random integers that are generated:
# test_number_of_layers "fake_number_of_layers" fake_number_of_layers;;
- : bool = true
# test_number_of_layers "fake_number_of_layers" fake_number_of_layers;;
test_number_of_layers failed for fake_number_of_layers with -1 as result instead of the expected 6
- : bool = false
#
In any case, Halcyon’s file now starts to look pretty professional. First, it contains the unit tests, because one should write the unit tests first, and then it contains the implementation, each of them with a test:
(* Halcyon's onions.ml *)
(* A miscellany of agricultural computations. *)
(* ********** *)
let nat_fold_left zero_case succ_case n =
let () = assert (n >= 0) in
let rec loop i a =
if i = 0
then a
else loop (pred i) (succ_case a)
in loop n zero_case;;
let generate_random_onion n =
let () = assert (n > 0) in
let number_of_layers = Random.int n
in (nat_fold_left Bud (fun o -> Layer o) number_of_layers, number_of_layers);;
let test_number_of_layers name candidate =
let b0 = (candidate Bud = 0)
and b1 = (candidate (Layer Bud) = 1)
and b2 = (candidate (Layer (Layer Bud)) = 2)
and bn = (let (o, n) = generate_random_onion 100
in let expected_result = n
and actual_result = candidate o
in if actual_result = expected_result
then true
else let () = Printf.printf
"test_number_of_layers failed for %s with %d as result instead of the expected %n\n"
name
actual_result
expected_result
in false)
in b0 && b1 && b2 && bn;;
let fake_number_of_layers o =
match o with
| Bud ->
0
| Layer Bud ->
1
| Layer (Layer Bud) ->
2
| _ ->
-1;;
(*
# test_number_of_layers "fake_number_of_layers" fake_number_of_layers;;
- : bool = true
# test_number_of_layers "fake_number_of_layers" fake_number_of_layers;;
test_number_of_layers failed for fake_number_of_layers with -1 as result instead of the expected 6
- : bool = false
#
*)
(* ********** *)
type onion =
| Bud
| Layer of onion;;
(* ***** *)
let number_of_layers o =
let rec loop o =
match o with
| Bud ->
0
| Layer o' ->
succ (loop o')
in loop o;;
let () = assert (test_number_of_layers "number_of_layers" number_of_layers);;
(* ***** *)
let tr_number_of_layers o =
let rec loop o a =
match o with
| Bud ->
a
| Layer o' ->
loop o' (succ a)
in loop o 0;;
let () = assert (test_number_of_layers "tr_number_of_layers" tr_number_of_layers);;
(* ********** *)
(* end of Halcyon's onions.ml *)
let end_of_file = "Halcyon's onions.ml";;
(* remember to put the digital signature here! *)
But alas, three times alas, when Halcyon loads his file, the following error occurs:
# #use "Halcyon's onions.ml";;
val nat_fold_left : 'a -> ('a -> 'a) -> int -> 'a = <fun>
val generate_random_onion : int -> onion * int = <fun>
val test_number_of_layers : string -> (onion -> int) -> bool = <fun>
val fake_number_of_layers : onion -> int = <fun>
type onion = Bud | Layer of onion
val number_of_layers : onion -> int = <fun>
File "Halcyon's onions.ml", line 73, characters 58-74:
Error: This expression has type onion/1540 -> int
but an expression was expected of type onion/1502 -> int
Type onion/1540 is not compatible with type onion/1502
#
This error is so weird. Line 73 reads:
let () = assert (test_number_of_layers "number_of_layers" number_of_layers);;
which suggests that number_of_layers does not pass the unit test, which it should since Vigfus interactively checked that it did.
It took Brynja quite some time to explain, and to be honest her explanation about OCaml’s internal versioning of declarations doesn’t make sense. When the file is loaded, the unit-test function refers to the definition of the onion type that was declared the previous time the file was loaded. Then the onion type is declared and number_of_layers refers to this new definition. So when the test is ran, the unit-test function refers to the previous instance of the onion type and the tested function refers to its new instance, or something, which doesn’t make any sense since they have the same name: it’s the same elephant, no? Then Harald said to forget the elephant and to concentrate on the temporality of the onion as evidenced by its version number after the slash, Halcyon tried to joke his way out by suggesting that OCaml should go forth to the past, and Loki mumbled something about Marty McFly. That’s when Mimer arrived. But by then Halcyon had rebooted his laptop and re-loaded the file:
# #use "Halcyon's onions.ml";;
val nat_fold_left : 'a -> ('a -> 'a) -> int -> 'a = <fun>
File "Halcyon's onions.ml", line 17, characters 20-23:
Error: Unbound constructor Bud
#
Obviously, the definition of the onion should occur first in the file. With that fixed, the file loaded without any hiccup:
# #use "Halcyon's onions.ml";;
type onion = Bud | Layer of onion
val nat_fold_left : 'a -> ('a -> 'a) -> int -> 'a = <fun>
val generate_random_onion : int -> onion * int = <fun>
val test_number_of_layers : string -> (onion -> int) -> bool = <fun>
val fake_number_of_layers : onion -> int = <fun>
val number_of_layers : onion -> int = <fun>
val tr_number_of_layers : onion -> int = <fun>
val end_of_file : string = "Halcyon's onions.ml"
#
Not just that, but Mimer said it was a good idea to put the unit tests first, that the unit-test function was professional, and that the fake function was a nice touch because of Dijkstra. All in all, it was a pretty good day!
Halcyon: Moi, je m’occupe de mes oignons.
If a type error occurs with a slash followed by a versioning number, stop OCaml, restart it, and move a definition in this file so that what is defined is declared before it is used.