What is news in 4.14.0 ?
OCaml 4.14 is the last release of the OCaml 4 branch. If there is much anticipation
for OCaml 5, OCaml 4.14 still brings many quality of life improvement to OCaml 4.
In this no-so-short-any-longer post, I will try to describe a few personal highlights in this new release:
- Integrated support for “go to definitions”
- Standard library improvements
- Improved error messages
- Runtime optimisation for the Garbage Collector
- More tailcall guarantee
- Syntax fine-tuning
- Experimental TMC transformation
Integrated support for “go to definitions”
Finding the original definition of a type or expression is quite common features
in code editors for many languages. However, most languages don’t have a
powerful module system that allows to easily transport definitions from one
module to another module like OCaml.
Consider for instance a file const.ml
module type S = sig val euler_mascheroni: float end
module Origin = struct
let euler_mascheroni = 0.577215664901532866
end
module F(X:S)(Y:S) = struct
module A = Y
module B = X
end
module G(X:sig module A:S end)=X.A
include G(F(Origin)(Origin))
At some point in the future, I might want to to modify the definition of the
Euler-mascheroni constant in const.ml, for instance to switch to an
hexadecimal representation to avoid rounding errors.
When querying for the original definition of the constant, I don’t want to be
sent to the functor application:
include G(F(Origin)(Origin))
by my editor: the original definition is not here.
Similarly, the original definition of constant does not belong to the body of the functor G
module G(X:sig module A:S end)=X.A
nor to the body of the functor F
module F(X:S)(Y:S) = struct
module A = Y
...
end
And it is only after traversing two functors applications and two functor bodies
that I can at last reach the original definition in the Origin module.
This is possibly a quite involved process, that I don’t want to do manually
for every definitions.
Before 4.14, Merlin was doing this tracking of original definitions on its own,
with some difficulties and some bugs. To avoid those issues, the calculus needed
to track the origin of such definitions has been upstreamed in the compiler.
Moving this computation upstreams means that the compiler itself can record the
information needed to track original definitions through functor applications,
module projection, inclusions, and saves this information in the cmt files
as a new field that can be used directly by Merlin. This is done by computing
a shape for each modules that record new definitions, but also functor
applications and module projections (M.X). This shape information is also
optimised to reduce future query time. This optimisation might increase the
compilation for the most heavy-user of modules, but that was deemed a reasonable
compromise.
Standard library
Seq
The previously slightly bare-bone API of the Seq module has been significantly
expanded with more than 40 functions that should make it easier to produce (6 new functions),
consume (15 new functions), transform (11 new functions), combine (6 new functions),
split (6 new functions), or convert sequences (2 new functions).
In_channel and Out_channel
Two new modules have been added to the standard library: In_channel and Out_channel.
All functions operating on in_channel and out_channel in the Stdlib module are now also available
in those modules. But those modules also provides new function like In_channel.input_all which reads
the full content of an input channel, or Out_channel.with_open_in which guarantees that the opened
channel is closed after its use.
UTF decoding and validation
Continuing with the spirit of defining strings and bytes as array of chars,
that might contain valid unicode data, new functions have been added to the modules Uchar, String,
and Bytes to help validate and decode unicode contents stored in strings or bytes
Deprecations
In preparation to OCaml 5, the standard library has added many deprecation warnings on functions
or modules that were “well-known” to be deprecated. In particular, the Stream and Genlex module
have been deprecated in OCaml 4.14 and will not be available in OCaml 5 as a part of the standard library.
Those modules are now available in a new separate library, camlp-streams, for packages that depends
on those modules.
Improved error messages
In 4.14.0, the on-going work on better error messages has been particularly
fruitful for error message at the module level, but there was also some
interesting progress for type error messages.
Full trace for module errors
Module errors are possibly one of the hardest to read error message in OCaml.
This phenomenon was worsened by the fact that module-level error were often
laconic on the reason why two type were mismatched. For instance, reading the
error for
module M: sig
type ('a,'b) arrow
val app : ('a,'b) arrow -> 'a -> 'b
end = struct
type 'a pr = Format.formatter -> 'a -> unit
type ('a,'b) arrow = <name:string; a:'a pr; b:'b pr; f:'a -> 'b>
let app arrow x =
let y = arrow#f x in
Format.printf "%t(%a)=%a" arrow#name (arrow#a: _ pr) x (arrow#b: _ pr) y;
y
end
Error: Signature mismatch:
...
Values do not match:
val app :
< a : 'a pr; b : 'b pr; f : 'a -> 'b;
name : Format.formatter -> unit; .. > ->
'a -> 'b
is not included in
val app : ('a, 'b) arrow -> 'a -> 'b
only tell us that there is some incompatibility between the interface and
implementation type.
And that’s it.
With OCaml 4.14, the compiler is much more loquacious, and the type incompatibility is fully explained:
The type
< a : 'a pr; b : 'b pr; f : 'a -> 'b;
name : Format.formatter -> unit > ->
'a -> 'b
is not compatible with the type ('a, 'b) arrow -> 'a -> 'b
Type
< a : 'a pr; b : 'b pr; f : 'a -> 'b;
name : Format.formatter -> unit >
is not compatible with type
('a, 'b) arrow = < a : 'a pr; b : 'b pr; f : 'a -> 'b; name : string >
Types for method name are incompatible
This result was achieved by making sure that error message at the module level are chained with
the type error that lead to the module-level error message.
Mismatched definitions
Have you ever swapped a handful of constructors in a type definition and forgot
to update the corresponding interface file?
module A: sig
type t = A | B | C | D | E | F | G | H
end = struct
type t = A | B | E | D | C | F | H | G
end
This situation is certainly caught by the typechecker. However, the error
message was often very indirectly related to the issue at hand:
Type declarations do not match:
type t = A | B | E | D | C | F | H | G
is not included in
type t = A | B | C | D | E | F | G | H
Constructors number 3 have different names, E and C.
It is certainly true that the third constructor has a different name between the signature and the implementation.
However, if I follow this error message blindly, I would stumble into another error message
module A: sig
type t = A | B | C | D | E | F | G | H
end = struct
type t = A | B | C | D | C | F | H | G
end
Error: Two constructors are named C
And if I apply another fix following blindly the error message step-by-step,
I will need 10 iteration to reach the correct definition. To avoid this long
chain of error message, OCaml 4.14 has extended the use of the new diffing
algorithms for functor to type definitions.
The idea is to compute a minimal patch that can transform the implementation
definition into the interface declaration by using semantic actions
(like adding a constructor, or swapping two constructors) and use this
minimal patch to explain this error. The previous example was for instance
constructed by swapping two constructors, and the diffing algorithm
sucessfullly decompose the error in two swaps:
module A: sig
type t = A | B | C | D | E | F | G | H
end = struct
type t = A | B | E | D | C | F | H | G
end
Error: Signature mismatch:
...
Type declarations do not match:
type t = A | B | E | D | C | F | H | G
is not included in
type t = A | B | C | D | E | F | G | H
5<->3. Constructors C and E have been swapped.
8<->7. Constructors G and H have been swapped.
This new error message format works also quite well when either the implementation
or the interface is missing constructors or record fields:
module M: sig
type t = { a:int; b:int; c:int; d:int}
end = struct
type t = { a: int; b : int }
end
Error: Signature mismatch:
Modules do not match:
sig type t = { a : int; b : int; } end
is not included in
sig type t = { a : int; b : int; c : int; d : int; } end
Type declarations do not match:
type t = { a : int; b : int; }
is not included in
type t = { a : int; b : int; c : int; d : int; }
3. A field, c, is missing in the first declaration.
4. A field, d, is missing in the first declaration.
Type-directed disambiguation should fail early
One of the disadvantage of type-directed disambiguation is that it may delay
a type error and leads to surprising error messages.
For instance, before OCaml 4.14, the following function
let () = match Seq.return 10 with Nil | Cons _ -> ()
raised the error about an unknown Nil constructor.
Error: Unbound constructor Nil
At first glance, one might be tempted to fix this issue by using
the fully qualified name
let () = match Seq.return 10 with Seq.Nil | Seq.Cons _ -> ()
But this updated code is rejected with
Error: This pattern matches values of type 'a Seq.node
but a pattern was expected which matches values of type
int Seq.t = unit -> int Seq.node
In other words, we were sent to a wild good chase, and the true error laid in a
missing argument to Seq.return function
let () = match Seq.return 10 () with Nil | Cons _ -> ()
At this point, one may wonder why the compiler complained initially about an unbound Nil constructor.
And the true reason is that the type constructor Seq.t does not define a constructor Nil;
ore more precisely, it does not define any constructors at all since it is a type abbreviation for
unit -> 'a Seq.node.
The error logic was definitively backward here. Fortunately, this point is fixed in 4.14, and now
let () = match Seq.return 10 with Nil | Cons _ -> ()
is rejected with an error message that does mention that there is something
wrong with this pattern matching:
Error: This pattern should not be a constructor, the expected type is int Seq.t
Hopefully, this should decrease the time spent debugging this kind of issue in the future.
Improved printing
When printing types in errror message, OCaml should be much more parcimonious in its use of as bindings.
For instance, the error message for
type 'a t
type a
let f : < .. > t -> unit = fun _ -> ()
let _ = fun (x : a t) -> f x
Error: This expression has type a t but an expression was expected of type
(< .. > as 'a) t
Type a is not compatible with type < .. > as 'a
used to add an as 'a because the printer for type expressions anticipated that it might need
a name for linking recursive occurences. With 4.14, such names are only printed when they are really necessary:
Error: This expression has type a t but an expression was expected of type
< .. > t
Type a is not compatible with type < .. >
Runtime optimisation : GC prefetching
The code of the major GC has been fine tuned to better use the processor cache.
One of the phase of the major GC consists in marking live objects starting
from roots of known-to-be alive objects.
In the previous version of OCaml, this marking was a depth-first traversal of
reachable objects: newly discovered objects were added to the top of the marking
stack. Since those newly discovered objects were unlikely to be in the cache,
this means that this phase spent a significant amount of time waiting for load
after a cache miss.
This lack of cache locality has been fixed in OCaml 4.14 by adding
a prefetching circular buffer in front of the marking stack.
The new scanned element is then:
- draw from the front of prefetchting buffer if it contains more than
pq_min
elements - draw from the marking stack otherwise
Newly discovered objects are added to the back of the prefetching queue except
in case of overflow, in which case they are added to the stack.
This new design ensures that discovered elements spend enough time in the
prefetching buffer to have been likely be loaded in cache once we try to scan
them.
For programs that were spending a significant amount of times in the GC, this
can result in a 20% speedup.
Tailcall optimisation for functions with many arguments
Before OCaml 4.14, mutually recursive functions with too many arguments were not subject to
tail-call optimisation. For instance,
let rec h x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 =
if x1 = 0 then
x11
else
i (x1 - 1) x2 (x1 + x2) (x2+x3) (x4+x5) (x5+x6) (x6+x7) (x7 + x8) (x8 + x9) (x9+x10) (x10+x11)
and i x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 =
h x1 x2 (x1 + x2) (x2+x3) (x4+x5) (x5+x6) (x6+x7) (x7 + x8) (x8 + x9) (x9+x10) (x10+x11)
The call to h might not tail-call optimised by ocamlopt in OCaml 4.13.
Moreover, the precise number hidden the words “too many” was function of the
processor architecture.
The OCaml function call convention have been updated to ensure that recursive
tail-call of functions with less than 64 arguments are always optimised to not
consume stack frames.
Syntax fine-tuning
Explicit quantified type variables in declaration
Type variables can be explicitly introduced in the declarations of values and variant constructors.
For instance,
val fold: ('acc -> 'elt -> 'acc) -> 'acc -> 'elt list -> 'acc
type showable = Show: a * ('a -> string) -> showable
can now be written as
val fold: 'acc 'elt. ('acc -> 'elt -> 'acc) -> 'acc -> 'elt list -> 'acc
type showable = Show: 'a. 'a * ('a -> string) -> showable
Less parentheses for immediate objects
Immediate objects no longer requires parentheses:
let print x = x#name
let name = print object method name = "Named" end
Experimental TMC transformation
It is well-known that there is many algorithms on recursive data types where there is
compromise between readability and speed on large values. For instance, when comparing
let rec map f = function
| [] -> []
| x :: xs -> f x :: map f xs
and
let rec map f acc = function
| [] -> List.rev acc
| x :: xs -> map f (f x::acc) xs
let map f l = map f [] l
the first implementation is easier on the eyes and faster on smaller lists.
However, this first function is not tail-recursive, it is using stack spaces and
might trigger a stack overflow on larger lists. The second function is thus
better behaved (and in fact generally faster) on large input.
The experimental tail-modulo-cons program transformation offer a solution to this compromise
between speed and readability when every recursive calls happen under a constructor.
By annotating a function with [@tail_mod_cons] and each tail call with [@tailcall] annotation
let rec map[@tail_mod_cons] f = function
| [] -> []
| x :: xs -> f x :: (map[@tailcall]) f xs
the compiler will generate an optimised version of the function that does not use stack space
by using an initializable hole.
Informally, the TMC transformation is rewritting
f x :: (map[@tailcall]) f xs
as
let $hole in
let result = f x :: $hole in
previous_result.$hole <- result;
map_dps result f xs
using a new destination passing style function map_dps that rewrites the content
of the hole in result once it is available.
For a better explanation, there is a whole new manual chapter explaining this
transformation at OCaml - The “Tail Modulo Constructor” program transformation and that the
feature is still slightly in flux in term of user interface. (Once the updated manual will be online).