text:
In this blog post, we explain how
ocp-memprof helped us identify a piece of code in Alt-Ergo that needed to be improved. Simply put, a function that merges two maps was performing a lot of unnecessary allocations, negatively impacting the garbage collector's activity. A simple patch allowed us to prevent these allocations, and thus speed up Alt-Ergo's execution.
Il all started with a challenging example coming from an industrial user of Alt-Ergo, our SMT solver. It was proven by Alt-Ergo in approximately 70 seconds. This seemed abnormnally long and needed to be investigated. Unfortunately, all our tests with different options (number of triggers, case-split analysis, ...) and different plugins (satML plugin, profiling plugin, fm-simplex plugin) of Alt-Ergo failed to improve the resolution time. We then profiled an execution using
ocp-memprof to understand the memory behavior of this example.
As usual, profiling an OCaml application with
ocp-memprof is very simple (see the user manual for more details). We just compiled Alt-Ergo in the OPAM switch for
ocp-memprof (version
4.01.0+ocp1) and executed the following command:
$ ocp-memprof --exec ./ae-4.01.0+ocp1-public-without-patch pb-many-GCs.why
The execution above triggers 612 garbage collections in about 114 seconds. The analysis of the generated dumps produces the evolution graph below. We notice on the graph that:
we have approximately 10 MB of hash-tables allocated since the beginning of the execution, which is expected;
the second most allocated data in the major heap are maps, and they keep growing during the execution of Alt-Ergo.
We are not able to precisely identify the allocation origins of the maps in this graph (maps are generic structures that are intensively used in Alt-Ergo). To investigate further, we wanted to know if some global value was abnormally retaining a lot of memory, or if some (non recursive-terminal) iterator was causing some trouble when applied on huge data structures. For that, we extended the analysis with the
--per-root option to focus on the memory graph of the last dump. This is done by executing the following command, where 4242 is the PID of the process launched by
ocp-memprof --exec in the previous command:
$ ocp-memprof --load 4242 --per-root 611
The per-root graph (above, on the right) gives more interesting information. When expanding the
stack node and sorting the sixth column in decreasing order, we notice that:
a bunch of these maps are still in the stack: the item
Map_at_192_offset_1 in the first column means that most of the memory is retained by the
fold function, at line 192 of the
Map module (resolution of stack frames is only available in the commercial version of
the "kind" column corresponding to
Map_at_192_offset_1 gives better information. It provides the signature of the function passed to fold. This information is already provided by the online version.
Uf.Make(Uf.??Make.X).LX.t ->
Explanation.t ->
Explanation.t Map.Make(Uf.Make(Uf.??Make.X).LX).t ->
Explanation.t Map.Make(Uf.Make(Uf.??Make.X).LX).t
This information allows us to see the precise origin of the allocation: the map of module
LX used in uf.ml. Lucky us, there is only one
fold function of
LX's maps in the
Uf module with the same type.
Thanks to the information provided by the
--per-root option, we identified the code responsible for this behavior:
(*** function extracted from module uf.ml ***)
01 | module MapL = Map.Make(LX)
02 |
03 | let update_neqs r1 r2 dep env =
04 | let merge_disjoint_maps l1 ex1 mapl =
05 | try
06 | let ex2 = MapL.find l1 mapl in
07 | let ex = Ex.union (Ex.union ex1 ex2) dep in
08 | raise (Inconsistent (ex, cl_extract env))
09 | with Not_found ->
10 | MapL.add l1 (Ex.union ex1 dep) mapl
11 | in
12 | let nq_r1 = lookup_for_neqs env r1 in
13 | let nq_r2 = lookup_for_neqs env r2 in
14 | let mapl = MapL.fold merge_disjoint_maps nq_r1 nq_r2 in
15 | MapX.add r2 mapl (MapX.add r1 mapl env.neqs)
Roughly speaking, the function above retrieves two maps
nq_r1 and
nq_r2 from
env, and folds on the first one while providing the second map as an accumulator. The local function
merge_disjoint_maps (passed to fold) raises
Exception.Inconsistent if the original maps were not disjoint. Otherwise, it adds the current binding (after updating the corresponding value) to the accumulator. Finally, the result
mapl of the fold is used to update the values of
r1 and
r2 in
After further debugging, we observed that one of the maps (
nq_r1 and
nq_r2) is always empty in our situation. A straightforward fix consists in testing whether one of these two maps is empty. If it is the case, we simply return the other map. Here is the corresponding code:
(*** first patch: testing if one of the maps is empty ***)
.. | ...
14 | let mapl =
15 | if MapL.is_empty nq_r1 then nq_r2
16 | else
17 | if MapL.is_empty nq_r2 then nq_r1
18 | else
19 | MapL.fold merge_disjoint_maps nq_r1 nq_r2
.. | ...
Of course, a more generic solution should not just test for emptiness, but should fold on the smallest map. In the second patch below, we used a slightly modified version of OCaml's maps that exports the
height function (implemented in constant time). This way, we always fold on the smallest map while providing the biggest one as an accumulator.
(*** second (better) patch : folding on the smallest map ***)
01 | module MapL = Emap.Make(LX)
.. | ...
14 | let small, big =
15 | if MapL.height nq_r1 < MapL.height nq_r2 then nq_r1, nq_r2
16 | else nq_r2, nq_r1
17 | in
18 | let mapl = MapL.fold merge_disjoint_maps small big in
.. | ...
Curious to see the result of the patch ? We regenerate the evolution and memory graphs of the patched code (fix 1), and we noticed:
a better resolution time: from 69 seconds to 16 seconds;
less garbage collection : from 53,000 minor collections to 19,000;
a smaller memory footprint : from 26 MB to 24 MB;
We show in this post that
ocp-memprof can also be used to optimize your code, not only by decreasing memory usage, but by improving the speed of your application. The interactive graphs are online in our gallery of examples if you want to see and explore them (without the patch and with the patch).
|AE + patch
|69.1 secs
|16.4 secs
|substantial improvement on the example
|76.3 secs
|17.1 secs
|when using the patched version of Alt-Ergo
|dumps generation
|114.3 secs (+49%)
|17.6 secs (+2.8%)
|(important) overhead when dumping
memory snapshots
|# dumps (major collections)
|612 GCs
|31 GCs
|impressive GC activity without the patch
|dumps analysis
(online ocp-memprof)
|759 secs
|24.3 secs
|dumps analysis
(commercial ocp-memprof)
|153 secs
|3.7 secs
|analysis with commercial ocp-memprof is
~ x5 faster than public version (above)
|AE memory footprint
|memory consumption is comparable
|minor collections
|fewer minor GCs thanks to the patch
Do not hesitate to use
ocp-memprof on your applications. Of course, all feedback and suggestions are welcome, just email us !
More information:
Homepage: http://memprof.typerex.org/
Gallery of examples: http://memprof.typerex.org/gallery.php
Free Version: http://memprof.typerex.org/free-version.php
Commercial Version: http://memprof.typerex.org/commercial-version.php
Report a Bug: http://memprof.typerex.org/report-a-bug.php
A few months ago, a memory leak in the
Scanf.fscanf function of OCaml's standard library has been reported on the OCaml mailing list. The following "minimal" example reproduces this misbehavior:
(* in file scanf_leak.ml *)
for i = 0 to 100_000 do
let ic = open_in "some_file.txt" in
Scanf.fscanf ic "%s" (fun _s -> ());
close_in ic
read_line ();;
Let us see how to identify the origin of the leak and fix it with our OCaml memory profiler.
We first install our modified OCaml compiler and the memory profiling tool thanks to the following opam commands:
#### Add memprof repository ####
$ opam remote add memprof http://memprof.typerex.org/opam
$ opam update
#### Install the patched compiler and ocp-memprof ####
$ opam switch 4.01.0+ocp1-20150202
$ opam install ocp-memprof
$ eval `opam config env`
That's all ! Installation is done after only five (opam) commands.
The second step consists in compiling the example above and profiling it. This is simply achieved with the commands:
#### Compile your example ####
$ ocamlopt scanf_leak.ml -o scanf.x
#### Execute your program with ocp-memprof ####
$ ocp-memprof --exec scanf.x
You may notice that no instrumentation of the source is needed to enable profiling.
In the last command above,
scanf.x dumps a lot of information (related to memory occupation) during its execution. Our "OCaml Memory Profiler" then analyzes these dumps, and generates a "human readable" graph that shows the evolution of memory consumption after each OCaml garbage collection. Concretely, this yields the graph below (the interactive graph generated by
ocp-memprof is available here). As you can see, memory consumption is growing abnormally and exceed 240Mb ! Note that we stopped the
scanf.x after 90 seconds.
ocp-memprof allows to group and show data contained in the graph w.r.t. several criteria. For instance, data are grouped by "Modules" in the capture below. This allows us to deduce that most allocations are performed in the
Scanf and
Buffer modules.
In addition to aggregation capabilities, the interactive graph generated by ocp-memprof also allows to "zoom" on particular data. For instance, by looking at
Scanf, we obtain the graph below that shows the different functions that are allocating in this module. We remark that the most allocating function is
Scanf.Scanning.from_ic. Let us have a look to this function.
The code of the function
from_ic, that is responsible for most of the allocation in
Scanf, is the following:
let memo_from_ic =
let memo = ref [] in
(fun scan_close_ic ic ->
try List.assq ic !memo with
| Not_found ->
let ib = from_ic scan_close_ic (From_channel ic) ic in
memo := (ic, ib) :: !memo;
It looks like that the leak is caused by the
memo list that associates a lookahead buffer, resulting from the call to
from_ic, with each input channel.
Benoit Vaugon quickly sent a patch based on weak-pointers that seems to solve the problem. He modified the code as follows:
he put the key in a weak set in order to test if it is gone;
he created a pair that stores the key and the associated value (
he put this pair in a weak set (
IcMemo), where it will be reclaimed at the next GC because;
he added a finalizer on the pair that adds again the pair in the weak set at each GC
let memo_from_ic =
let module IcMemo = Weak.Make (struct
type t = Pervasives.in_channel
let equal ic1 ic2 = ic1 = ic2
let hash ic = Hashtbl.hash ic
end) in
let module PairMemo = Weak.Make (struct
type t = Pervasives.in_channel * in_channel
let equal (ic1, _) (ic2, _) = ic1 = ic2
let hash (ic, _) = Hashtbl.hash ic
end) in
let ic_memo = IcMemo.create 16 in
let pair_memo = PairMemo.create 16 in
let rec finaliser ((ic, _) as pair) =
if IcMemo.mem ic_memo ic then (
Gc.finalise finaliser pair;
PairMemo.add pair_memo pair) in
(fun scan_close_ic ic ->
try snd (PairMemo.find pair_memo (ic, stdin)) with
| Not_found ->
let ib = from_ic scan_close_ic (From_channel ic) ic in
let pair = (ic, ib) in
IcMemo.add ic_memo ic;
Gc.finalise finaliser pair;
PairMemo.add pair_memo pair;
Curious to see the memory behavior after applying this patch ? The graph below shows the memory consumption of the patched version of
Scanf module. Again, the interactive version is available here. After each iteration of the
for-loop, the memory is released as expected and memory consumption does not exceed 2.1Mb during each
for-loop iteration.
This example is online in our gallery of examples if you want to see and explore the graphs (with the leak and without the leak).
Do not hesitate to use
ocp-memprof on your applications. Of course, all feedback and suggestions on using
ocp-memprof are welcome, just send us an email !
More information:
Homepage: http://memprof.typerex.org/
Gallery of examples: http://memprof.typerex.org/gallery.php
Commercial: http://memprof.typerex.org/commercial-version.php
In this blog post, we went on the hunt of memory leaks in Cumulus by using our memory profiler: ocp-memprof. Cumulus is a feed aggregator based on Eliom, a framework for programming web sites and client/server web applications, part of the Ocsigen Project.
To test and run the server, we use
ocp-memprof to start the process:
$ ocp-memprof --exec ocsigenserver.opt -c ocsigenserver.opt.conf -v
There are several ways to obtain snapshots:
automatically after each GC: there is nothing to do, this is the default behavior
by sending a SIGUSR1 signal (the default signal can be changed by using
--signal SIG option);
by editing the source code and using the dump function in the
Headump module:
val dump : string -> unit (* the string argument stands for the name of the dump *)
Here, we use the default behavior and get a snapshot after every GC.
After running the server for a long time, the server process shows an unusually high consumption of memory.
ocp-memprof automatically generates some statistics on the application memory usage. Below, we show the graph of memory consumption. On the x-axis, you can see the number of GCs, and on the y-axis, the memory size in bytes used by the most popular types in memory.
Eliom expert users would quickly identify that most of the memory is used by XML nodes and attributes, together with strings and closures.
Unfortunately, it is not that easy to know which parts of Cumulus source code are the cause for the allocations of these XML trees. These trees are indeed abstract types allocated using functions exported by the Eliom modules. The main part of the allocations are then located in the Eliom source code.
Generally, we will have a problem to locate abstract type values just using allocation points. It may be useful to browse the memory graph which can be completely reconstructed from the snapshot to identify all paths between the globals and the blocks representing XML nodes.
The approach that we chose to identify the leak is to take a look at the pointer graph of our application in order to identify the roots retaining a significant portion of the memory. Above, we can observe the table of the retained size, for all roots of the application. What we can tell quickly is that 92.2% of our memory is retained by values with finalizers.
Below, looking at them more closely, we can state that there is a significant amount of values of type:
'a Eliom_comet_base.channel_data Lwt_stream.t -> unit
Probably, these finalizers are never called in order to free their associated values. The leak is not trivial to track down and fix. However, a quick fix is possible in the case of Cumulus.
After further investigation into the source code of Cumulus, we found the only location where such values are allocated:
(* $ROOT/cumulus/src/base/feeds.ml *)
let (event , call_event ) =
let ( private_event , call_event ) = React.E. create () in
let event = Eliom_react .Down. of_react private_event in
(event , call_event )
The function
of_react takes an optional argument
~scope to specify the way that
Eliom_comet.Channel.create has to use the communication channel.
Changing the default value of the scope by another given in Eliom module, we have now only one channel and every client use this channel to communicate with the server (the default method created one channel by client).
(* $ROOT/cumulus/src/base/feeds.ml *)
let (event , call_event ) =
let ( private_event , call_event ) = React.E. create () in
let event = Eliom_react .Down. of_react
~scope : Eliom_common . site_scope private_event in
(event , call_event )let (event , call_event ) =
After patching the source code, we recompile our application and re-execute the process as before. Below, we can observe the new pointer graph. By changing the default value of
scope, the size retained by finalizers drops from 92.2% to 0% !
The new evolution graph below shows that the memory usage drops from 45Mb (still growing quickly) for a few hundreds connections to 5.2Mb for thousands connections.
As a reminder, a finalisation function is a function that will be called with the (heap-allocated) value to which it is associated when that value becomes unreachable.
The GC calls finalisation functions in order to deallocate their associated values. You need to pay special attention when writing such finalisation functions, since anything reachable from the closure of a finalisation function is considered reachable. You also need to be careful not to make the value, that you want to free, become reachable again.
This example is online in our gallery of examples if you want to see and explore the graphs (with the leak and without the leak).
Do not hesitate to use
ocp-memprof on your applications. Of course, all feedback and suggestions on using
ocp-memprof are welcome, just send us a mail !
More information:
Homepage: http://memprof.typerex.org/
Gallery of examples: http://memprof.typerex.org/gallery.php
Commercial: http://memprof.typerex.org/commercial-version.php
After the public release of Alt-Ergo 0.99.1 last December, it's time to announce a new major private version (1.00) of our SMT solver. A JavaScript version is freely available on Alt-Ergo's website, while source code is on our internal repositories, accessible by our customers and academia users.
A quick comparison between this new version and the previous releases is given below. Timeout is set to 60 seconds. The benchmark is made of 19044 formulas: (a) some of these formulas are known to be invalid, and (b) some of them are out of scope of current SMT solvers. The results are obtained with Alt-Ergo's native input language.
|public release
|public release
|private release
|Proved Valid
|Proved Valid (%)
|84,01 %
|85,77 %
|92,62 %
|Required time (seconds)
|Average speed
(valid formulas per second)
theories data structures: semantic values (internal theories representation of terms) are now hash-consed. This enables the use of hash-based comparison (instead of structural comparison) when possible
theories combination: the dispatcher component, that sends literals assumed by the SAT solver to different theories depending on whether these literals are equalities, disequalities or inequalities, has been re-implemented. The new code is much simpler and enables new optimizations and factorizations
case-split analysis: we made several improvements in the heuristics of the case-split analysis mechanism over finite domains
explanations propagation: we improved explanations propagation in congruence closure and linear arithmetic algorithms. This makes the proofs faster thanks to a better back-jumping in the SAT solver part
linear integer arithmetic: we re-implemented several parts of linear arithmetic and introduced important improvements in the Fourier-Motzkin algorithm to make it run on smaller sub-problems avoiding some redundant executions. These optimizations allowed a significant speed up on our internal benchmarks
data structures: we optimized hash-consing and some functions in the "formula" and "literal" modules
SAT solving: we made a lot of improvements to the default SAT-solver and to the SatML plugin. In particular, the decision procedure part now receives facts (literals) in bulk from the solvers, rather than individually, trimming the costs of intermediate calls to theories reasoners, such as Fourier-Motzkin
Matching: we extended the E-matching algorithm to also perform matching modulo the theory of records. In addition, we simplified matching heuristics and optimized the E-matching process to avoid computing the same instances several times
Memory management: thanks to the ocp-memprof tool (http://memprof.typerex.org/), we identified some parts of Alt-Ergo that needed some improvements in order to avoid useless memory allocations, and thus unburden the OCaml garbage collector
the function that retrieves the used axioms and predicates (when option 'save-used-context' is set) has been improved
6 in the "inequalities" module of linear arithmetic
4 in the "formula" module
3 in the "ty" module used for types representation and manipulation
2 in the "theories front-end" module that interacts with the SAT solvers
1 in the "congruence closure" algorithm
1 in "existential quantifiers elimination" module
1 in the "type-checker"
1 in the "AC theory" of associative and commutative function symbols
1 in the "union-find" module
profiling plugin: when activated, this plugin records and prints some information about the current execution of Alt-Ergo every 'n' seconds: In particular, one can observe a module being activated, a function being called, the amount of time spent in every module/function, the current decision/instantiation level, the number of decisions/instantiations that have been made so far, the number of case-splits, of boolean/theory conflicts, of assumptions in the decision procedure, of generated instances per axiom, ...
fm-simplex plugin: when activated, this plugin is used instead of the Fourier-Motzkin method to infer bounds for linear integer arithmetic affine forms (which are used in the case-split analysis process). This module uses the Simplex algorithm to simulate particular runs of Fourier-Motzkin. In practice, the new algorithm scales better on linear integer arithmetic problems containing lots of inequalities
-version-info: prints some information about this version of Alt-Ergo (release and compilation dates, release commit ID)
-no-theory: deactivate theory reasoning. In this case, only the SAT-solver and the matching parts are used
-inequalities-plugin: specify a plugin to use, instead of the "default" Fourier-Motzkin algorithm, to handle inequalities of linear arithmetic
-tighten-vars: when this option is set, the Fm-Simplex plugin will try to infer bounds for integer variables as well. Note that this option may be very expensive
-profiling-plugin: specify a profiling plugin to use to monitor an execution of Alt-Ergo
-profiling <delay>: makes the profiling module prints its information every <delay> seconds
-no-tcp: deactivate constraints propagation modulo theories
the pruning module used in the frontend is not available anymore
the SMT and SMT2 front-ends have been removed. We plan to implement a new front-end for SMT2 in upcoming releases
Here is a short report on some of our public activities in May and June 2014.
After a lot of discussions and work on OPAM itself, we are now getting to a clear workflow for OCaml developpers and packagers: the preliminary document for OPAM 1.2 is available here. The idea is that you can now easily create and test the metadata locally, before having to get your package included in any repo: there is less administrative burden and it's much quicker to start, fix it, test it and get it right.
Things getting pretty stable, we are closing the last few bugs and should be releasing 1.2~beta very shortly.
We participated in the first OCaml hacking session in Paris organized by Thomas Braibant and supervized by Gabriel Scherer, who had kindly prepared in advance a selection of tasks. In particular, he came with a list of open bugs in Mantis that makes for good first descents in the compiler's code.
It was the first event of this kind for the OCaml Users in Paris (OUPS) meetup group. It was a success since everybody enjoyed it and some work has actually been achieved. We'll have to wait for the next one to confirm that !
On our front, Fabrice started working (with others) on a good, consensual Emacs profile; Pierre worked on building cross-compilers using Makefile templates; Benjamin wanted to evaluate the feasability of handling ppx extension nodes correctly inside Emacs, and it turns out that elisp tools exist for the task! You can see a first experiment running in the following screen capture, or even try the code (just open it in emacs, do a
M-x eval-buffer on it and then a
M-x tuareg-mode-with-ppx on an OCaml file). But beware, it's not yet very mainstream and can make your Emacs crash.
During the last two months, we participated in the supervision of an intern, Albin Coquereau --- a graduted student at University Paris-Sud --- in the VALS team who worked on a conservative extension of the SMT2 standard input language with prenex polymorphism a la ML and overloading. First results are promising. In the future, we plan to replace Alt-Ergo's input language with our extension of SMT2 in order to get advantage from SMT2's features and polymorphism's expressiveness.
Recenlty, we have also published an online Javascript-based version of Alt-Ergo (based on private release 0.99).
We are currently working on the proper integration of our Scilab tools in the Scilab world, respecting its ways and conventions. For this, we built a Scilab module respecting the standard ATOMS interface. This module can embed an OCaml program inside the run-time environment of Scilab, so that OCaml functions can be called as external primitives. (Dyn)linking Scilab's various components, LLVM's and the OCaml run-time together was not that easy.
Symmetrically, we built an OCaml library to manipulate and build Scilab values from OCaml, so that our tools can introspect the dynamic envrionment of Scilab's interprete. We also worked with the Scilab team to defined an AST interchange mechanism.
We plan to use this module as an entry point for our JIT oriented type system, as well as to integrate Scilint, our style checker, so that a Scilab user can check their functions without leaving the Scilab toplevel.
As announced by a long discussion in the caml-list, OCaml 4.02 introduces the first step to eliminate a long known OCaml problem: String Mutability. The main difficulty being that resolving that problem necessarilly breaks backward compatibility.
To achieve this first step, OCaml 4.02 comes with a new
bytes type and a corresponding
Bytes module, similar to OCaml 4.01
String module, but using the
bytes type. The type of a few functions from the
String module changed to use the
bytes type (like
String.blit... ). By default the
string and
bytes types are equal, hence ensuring backward compatibility for this release, but a new argument "
-safe-string" to the compiler can be used to remove this equality, and will probably become the default in some future release.
# let s = "foo";;
val s : string = "foo"
# s.[0] <- 'a';;
Characters 0-1:
s.[0] <- 'a';;
Error: This expression has type string but an expression was expected of type bytes
Notice that even when using
-safe-string you shouldn't rely on strings being immutable. For instance even if you compile that file with
-safe-string, the assertion in the function
g does not necessarilly hold:
If the following file
a.ml is compiled with
let s = "foo"
let f () = s
let g () = assert(s = "foo")
and the following file
b.ml is compiled without -safe-string`
let s = A.f () in
s.[0] <- 'a';
A.g ()
b.ml the equality holds, so modifying the string is possible, and the assertion from
A.g will fail.
So you should consider that for now
-safe-string is only a compiler-enforced good practice. But this may (and should) change in future versions. The
ocamlc man page says:
Enforce the separation between types string and bytes, thereby
making strings read-only. This will become the default in a
future version of OCaml.
In other words if you want your current code to be forward-compatible, your code should start using
bytes instead of
string as soon as possible.
In our experiments, we found a convenient solution to start using the
bytes type while still providing compatibility with 4.01: we use a small
StringCompat module that we open at the beginning of all our files making use of
bytes. Depending on the version of OCaml used to build the program, we provide two different implementations of
Before 4.02, our
stringCompat.ml file provides a
bytes type and a
Bytes module, including the
String module plus an often used
Bytes.to_string equivalent:
type bytes = string
module Bytes = struct
include String
let to_string t = t
After 4.02, our
stringCompat.ml file is much simpler:
type t = bytes
type bytes = t
module Bytes = Bytes
You might actually even wonder why it is not empty ? In fact, it is also a good practice to compile with a warning for unused
open, and an empty
stringCompat.ml would always trigger a warning in 4.02 for not being useful. Instead, this simple implementation is always seen as useful, as any use of
bytes or
Bytes will use the (virtual) indirection through
We plan to upload this module as a
string-compat package in OPAM, so that everybody can use this trick. If you have a better solution, we'll be pleased to discuss it via the pull on
When your code have been adapted to use the bytes whenever you need to modify a string, you can test if you didn't miss a case using OCaml 4.02 without changing your build system. To do that, you can just set the environment variable
OCAMLPARAM to
"safe-string=1,_". Notice that "
OCAMLPARAM" should only be used for testing purpose, never set it in your build system or tools, this would prevent testing new compiler options on your package (and you will receive complaints when the core developers can't desactivate the
"-w A -warn-error" generated by your build system) !
If your project passes this test and you don't use
"-warn-error", your package should continue to build without modification in the near and the not-so-near future (unless you link with the compiler internals of course).
Recently, we worked on an online Javascript-based serverless version of the Alt-Ergo SMT solver. In what follows, we will explain the principle of this version of Alt-Ergo, show how it can be used on a realistic example and compare its performances with bytecode and native binaries of Alt-Ergo.
.js file is generated following the scheme given below. Roughly speaking, it consists of three steps:
A new frontend (
main_js.ml) is added to the sources of Alt-Ergo. This file contains some glue code that allows the generated
.js file to interact with an HTML file (insertion of buttons, modification of DIV contents, ...)
The sources of Alt-Ergo and
main_js.ml are compiled with
ocamlc. The compilation make use of a preprocessor provided by
js_of_ocaml compiler is used to transform the bytecode generated by
ocaml into a javascript file.
.js file is then plugged into an HTML file that fits with the glue code inserted in
The HTML interface is made of four panels:
The left panel is an editable textarea in which you can write/past/load the formula you want to prove.
The bottom-left panel is used to display the answer of Alt-Ergo.
The middle panel contains a set of buttons that allow to interact with both the interface and the javascript version of Alt-Ergo.
The right panel is used to display different views. The default view ("Options") allows to control the options of Alt-Ergo. When a formula is proved valid, one may switch to "Statistics" view, thanks to the corresponding button in the middle, to see what are the quantified axioms and predicates that are used/instantiated during the proof. The "Debug" view shows the information received by
main_js.ml from the HTML interface. The "Examples" view shows some basic examples in Alt-Ergo's native input language that can be loaded in the left panel by a simple click.
Let us see how "Try Alt-Ergo" works on a formula translated from Atelier-B in the context of the BWare project:
First, open Try Alt-Ergo in a new tab/window.
Download the formula try-alt-ergo.why. This formula contains 177 quantified axioms and 132 predicates.
Click on the "Load a Local File" button of Try alt-ergo's interface and load the example into the left panel.
Go to "Options" panel and set the
maximum number of steps to 1000, the
maximum number of triggers to 1, and deactivate
Click on "Ask Alt-Ergo" button and wait approximately 60 seconds (depending on your computer). On my laptop, Alt-Ergo given the following answer after, approximately, 40 seconds.
# Alt-Ergo's answer: Valid (37.2260 seconds) (222 steps)
Now, you can navigate into the "Statistics" panel to see the quantified axioms and predicates that are instantiated during the proof, those that are potentially used, and those that have never been instantiated.
The Javascript version is slower than native and bytecode versions. In fact, bytecode executable is 4 times faster and native executable is 42 times faster than "Try Alt-Ergo", as shown below.
./alt-ergo.byte -nb-triggers 1 -no-Ematching -max-split infinity -save-used-context try-alt-ergo.why
File "/home/mi/Bureau/po.why", line 3017, characters 1-2450:Valid (9.3105) (222)
./alt-ergo.opt -nb-triggers 1 -no-Ematching -max-split infinity -save-used-context try-alt-ergo.why
File "/home/mi/Bureau/po.why", line 3017, characters 1-2450:Valid (0.8750) (222)
Since it is not possible to set a time limit in javascript. The "steps" mechanism should be used instead. This limit controls the number of calls to the decision procedure component of the solver.
Currently, the integration of external plugins (such as our miniSAT-based SAT solver) is not supported
Compared to AltGr-Ergo, statistics and debug information are only shown at the end of the execution.
"Asking Alt-Ergo" may report "syntax error" on well formed files for Safari and Midori users. The "Load a Local File" button is not working on Opera browser.
[ Acknowledgement: this work is financially supported by the BWare project. ]
Here is a short report on some of our activities in April 2014, and a short analysis of OCaml evolution since its first release.
We're still working on release 1.2. It was decided to include quite a few new features in this release, which delayed it a little bit since we want to be sure to get it right. It's now getting stabilized, documented and tested. One of the biggest improvements concerns the development workflow and the use of pinned packages, which is a powerful and complex feature that could also get a bit confusing. We are grateful for the large amount of feedback from the community that helped in its design. The basic idea is to use OPAM metadata from within the source packages, because it's most useful while developping and helps get the packaging right. It was possible before, but a little bit awkward : you now only need to provide an
opam file or directory at the root of your project, and when pinned to either a local path or a version-controlled repository, opam will pick it up and use it. It will then be synchronized on any subsequent
opam update. You can even do this if there is no corresponding package in the repository, OPAM will create it and store it in its internal repository for you. And in case this metadata is getting in the way, or you just want a quick local fix, you can always do
opam pin edit <package> to locally change the metadata used by opam.
During this month, we've also been improving performance by a large amount in several areas, because delays could become noticeable for people using it on eg. raspberry pis. There is an important clarification on the handling of optional dependencies; and we worked hard on making the build of OPAM as painless as possible on every possible setting.
Last month, we presented an online service for OPAM, to provide advanced CUDF solvers to every OPAM user. The service is provided by IRILL, and based on the tools they implemented to manipulate CUDF files (some of them are also used directly in OPAM).
This month, we are happy to introduce a new service, that we helped them put online: the OPAM Weather Service, an instantiation for OPAM of a service they also provide for Debian. It shows the evolution of the installability of all packages in the official OPAM repository, for three stable versions of OCaml (3.12.1, 4.00.1 and 4.01.0). It should help maintainers track dependency problems with their packages, when old packages are removed or new conflicting dependencies are introduced.
This month, we welcomed Pierrick Couderc for an internship in our lab. He is going to work on adding namespaces to OCaml. His goal is to design a kind of namespaces that extend the current module mechanism in a consistent but powerful way. One challenge of his job will be to make these namespaces also extend our big functors to provide functors at the namespace level.
Pierrick is not a complete newcomer in our team: last year, he already worked for us with David Maison (now working at TrustInSoft) on an online service to edit and compile OCaml code for students.
This month, there was also a lot of activity for the Core team, as we are closing to the feature freeze for OCaml 4.02. We took this opportunity to have a look at the evolution of OCaml sources since the first release of OCaml 1.00, in 1996.
Our first graph plots the size of uncompressed OCaml sources in bytes, from the first release to the current trunk:
The graph shows four interesting events:
in 2002-2003, between 3.02 and 3.06, an increase of 4 MB
in 2007, between 3.09.3 and 3.10.0, an increase of again 4 MB
in 2013, between 4.00.1 and 4.01.0, an increase of 2 MB
in 2014, between 4.01.0 and 4.02.0, a decrease of 6 MB
Our second graph plots the number of files per kind (OCaml sources, OCaml interfaces, C sources and C headers):
We can now check the files that were added and removed at the four events that we noticed on the first graph:
the first event corresponds to the addition of 174 files for
camlp4 in 3.04, and then 70 files for
ocamldoc in 3.06. Also,
labltk increased a lot, with many new examples;
the second event corresponds to the addition of 225 files for
ocamlbuild in 3.10.0, and the replacement of
camlp4 (renamed into
camlp5) by a new implementation;
the third event corresponds to ... a change in the size of
boot/myocamlbuild.boot, the bytecode file used by
ocamlbuild to bootstrap itself !
finally, the incoming new event corresponds to the removal of
camlp4 and
labltk from 4.02, i.e. about 300 files for each of them.
Our third graph shows the number of lines per kind of file, again:
This graph does not show us much more than what we have seen by number of files, but what might be interesting is to compute the ratio, i.e. the number of lines per file, for each kind of file:
There is a general trend to increase the number of lines per file, from about 200 lines in an OCaml source file in 1996 to about 330 lines in 2014. This ratio increased considerably for release 3.04, because
camlp4 used to generate a huge bootstrap file of its own pre-preprocessed OCaml sources. More interestingly, the ratio didn't decrease in 2014, when
camlp4 was removed from the distribution ! Interface files also grew bigger, but most of the increase was in 3.06, when
ocamldoc was added to the distribution, and an effort was done to document
mli files.
Here is a short report of some of our activities in March 2014 !
First, we would like to welcome Thomas Blanc on board ! Thomas is starting a PhD at OCamlPro, with Michel Mauny from ENSTA as his PhD advisor. So, he will stay with us for three years, working on static analysis of whole OCaml programs, with two main objectives:
To detect uncaught exceptions, using a different approach than
ocamlexc, the tool that François Pessaux developed during his PhD thesis, a method that will make Thomas' tool easier to upgrade at each new OCaml version;
To optimize generated code, with the benefits of whole program knowledge;
OPAM has seen its share of code quality improvements during this month, with a rewritten parser for OPAM description files, now reporting error locations, better handling of some corner cases, more expressive install requests from the command-line, and a more friendly way of handling
pinned packages. We are now stabilizing these features and you should expect soon a Beta release of OPAM 1.2.0.
We also spent some time this month working on using OPAM to distribute binary releases of OCaml. OPAM is great to use, but it sometimes takes a lot of time to compile OCaml when a new switch is needed for some small experimentation. We decided it would be interesting to experiment with a binary package of OCaml (4.01.0 for now).
The results are quite interesting, in most of our tests, downloading the compiler binary archive and uncompressing it takes an order of magnitude less time than compiling from sources, even with a slow connection:
|From Sources
|Binary Download
|Binary Install
|Intel i7 2.10GHz, Linux 64 bits, 16 GB RAM, SSD
|220s (DSL)
|Intel i7 2.60GHz, Linux 64 bits, 8 GB, SSD
|22s (Cable)
|Intel i5 2.67GHz, Linux 64 bits, 2 GB, SATA
|65s (Wifi)
|Intel Core2 2.53 GHz, Linux 32 bits, 4 GB, SSD
|68s (Wifi)
|Intel Xeon 2.67GHz, Linux 64 bits, 8 GB, SATA
|Intel core2 3.00 Ghz, Linux 32 bits, 4 GB, SATA
|15s (Cable)
You can try our compiler on your system (on Intel Linux only for now, but we plan to add binary versions for other architectures):
opam switch 4.01.0+bin-ocp
So now, the fastest way to get OCaml running on a computer is downloading OPAM and calling:
opam init --comp 4.01.0+bin-ocp
Another great thing with this compiler is that the binary archive is kept in a cache (in
~/.opam/ocp-compiler-cache/), so that creating more switches for this compiler is almost cost free. For example, you can try:
opam switch 4.01.0+test+my+soft --switch 4.01.0+bin-ocp
If you have an Intel Linux computer, and you get any problem with this distribution, you should send us the output of OPAM and we will try to fix the problem ! Unfortunately for CentOS users, we had to choose a recent libc, so that it will probably not run on this system.
In some cases, OPAM's internal heuristic is not enough -- upgrades are a np-complete problem after all. For this reason, OPAM has been thought from the beginning to be able to use an external solver, using the CUDF format to interoperate with solvers. Unfortunately, depending on your system, such a solver, like
aspcud, may not be available or easy to install.
So last month, we worked with the Mancoosi team to set up on one of their servers a CUDF solver farm, to work around this issue. Following the instructions on the site:
you can setup your OPAM configuration to use a remote CUDF solver, that will usually propose better solutions than the one provided internally by OPAM.
A bit "hackish" way of using it immediatly is to copy the following script in a file
aspcud in your path:
if bzip2 -c $1 | curl -f --data-binary @- http://$SERVER/cudf.bz2?criteria="$3" | bunzip2 -c > $2;
then exit 0
else echo FAIL > $2
In the context of the Bware project, where we are working on improving automatic solvers for Atelier B, we submitted a short paper to the ABZ conference describing the improvements we made in Alt-Ergo to increase its success rate on formulas translated from B proof obligations. Our paper has been accepted for publication! We will present it at ABZ 2014, which will be held in Toulouse (France) in the beginning of June.
We are pursuing our quest for a JIT for Scilab. Scilab really is a dynamic scripting language, in terms of typing, scoping, constructs and of how its users consider it. For most of them, it is basically an advanced, scriptable calculator. A common usecase is to pause in the middle of a function, open a toplevel at this point to edit some local variable or open a graphical visualisation, and then resume the execution.
In this context, we decided to adopt a really pragmatic approach, which is to detect statement-level code patterns that we know to be JITable, instead of trying to JIT whole functions. This way, we'll be able to leave the intro and outro of functions (which may do whatever they want to control and scope) to the interpreter, and concentrate on the inner, performance critical loop.
So, this month, we worked on several tasks required to achieve this goal. First, we worked on the detection of code snipplets, and as a side effect of this work, we plan to provide Scilab users with a new syntax-aware grep-like tool. We also worked on how to customize Scilab's loading function to replace some parts of the code by foreign calls to the future JIT. We also worked on the introspection of Scilab's context to build the environment of the JIT's type system.
OCaml 4.01 with its new feature to disambiguate constructors allows to do a nice trick: a simple and generic syntax extension that allows to define your own syntax without having to write complicated parsetree transformers. We propose an implementation in the form of a ppx rewriter.
it does only a simple transformation: replace strings prefixed by an operator starting with ! by a series of constructor applications
for instance:
!! "hello 3"
is rewriten to
!! (Start (H (E (L (L (O (Space (N3 (End))))))))
How is that generic ? We will present you a few examples.
For instance, if you want to declare base 3 arbitrary big numbers, let's define a syntax for it. We first start by declaring some types.
type start = Start of p
and p =
| N0 of stop
| N1 of q
| N2 of q
and q =
| N0 of q
| N1 of q
| N2 of q
| Underscore of q
| End
and stop = End
This type will only allow to write strings matching the regexp 0 | (1|2)(0|1|2|_)*. Notice that some constructors appear in multiple types like N0. This is not a problem since constructor desambiguation will choose for us the right one at the right place. Let's now define a few functions to use it:
open Num
let rec convert_p = function
| N0 (End) -> Int 0
| N1 t -> convert_q (Int 1) t
| N2 t -> convert_q (Int 2) t
and convert_q acc = function
| N0 t -> convert_q (acc */ Int 3) t
| N1 t -> convert_q (Int 1 +/ acc */ Int 3) t
| N2 t -> convert_q (Int 2 +/ acc */ Int 3) t
| Underscore t -> convert_q acc t
| End -> acc
let convert (Start p) = convert_p p
# val convert : start -> Num.num = <fun>
And we can now try it:
let n1 = convert (Start (N0 End))
# val n1 : Num.num = <num 0>
let n2 = convert (Start (N1 (Underscore (N0 End))))
# val n2 : Num.num = <num 3>
let n3 = convert (Start (N1 (N2 (N0 End))))
# val n3 : Num.num = <num 15>
And the generic syntax extension allows us to write:
let ( !! ) = convert
let n4 = !! "120_121_000"
val n4 : Num.num = <num 11367>
We can implement specialised format strings for a particular usage. Here, for concision we will restrict to a very small subset of the classical format: the characters %, i, c and space
Let's define the constructors.
type 'a start = Start of 'a a
and 'a a =
| Percent : 'a f -> 'a a
| I : 'a a -> 'a a
| C : 'a a -> 'a a
| Space : 'a a -> 'a a
| End : unit a
and 'a f =
| I : 'a a -> (int -> 'a) f
| C : 'a a -> (char -> 'a) f
| Percent : 'a a -> 'a f
Let's look at the inferred type for some examples:
let (!*) x = x
let v = !* "%i %c";;
# val v : (int -> char -> unit) start = Start (Percent (I (Space (Percent (C End)))))
let v = !* "ici";;
# val v : unit start = Start (I (C (I End)))
This is effectively the types we would like for a format string looking like that. To use it we can define a simple printer:
let rec print (Start cons) =
main cons
and main : type t. t a -> t = function
| I r ->
print_string "i";
main r
| C r ->
print_string "c";
main r
| Space r ->
print_string " ";
main r
| End -> ()
| Percent f ->
format f
and format : type t. t f -> t = function
| I r ->
fun i ->
print_int i;
main r
| C r ->
fun c ->
print_char c;
main r
| Percent r ->
print_string "%";
main r
let (!!) cons = print cons
And voila!
let s = !! "%i %c" 1 'c';;
# 1 c
It may not look like it, but we can do almost any syntax we might want this way. For instance we can do any regular language. To explain how we transform a regular language to a type definition, we will use as an example the language a(a|)b
type start = Start of a
and a =
| A of a'
and a' =
| A of b
| B of stop
and b = B of stop
and stop = End
We can try a few things on it:
let v = Start (A (A (B End)))
# val v : start = Start (A (A (B End)))
let v = Start (A (B End))
# val v : start = Start (A (B End))
let v = Start (B End)
# Characters 15-16:
# let v = Start (B End);;
# ^
# Error: The variant type a has no constructor B
let v = Start (A (A (A (B End))))
# Characters 21-22:
# let v = Start (A (A (A (B End))));;
# ^
# Error: The variant type b has no constructor A
Assumes the language is given as an automaton that:
has 4 states, a, a', b and stop
with initial state a
with final state stop
with transitions: a -- A --> a' a' -- A --> b a' -- B --> stop b -- B --> stop
let's write {c} for the constructor corresponding to the character c and [c] for the type corresponding to a state of the automaton.
For each state q we have a type declaration [q]
For each letter a of the alphabet we have a constructor {a}
For each transition p -- l --> q we have a constructor {l} with parameter [q] in type [p]:
type [p] = {l} of [q]
The End constructor without any parameter must be present in any final state
The initial state e is declared by
type start = Start of [e]
In fact we can encode deterministic context free languages (DCFL) also. To do that we encode pushdown automatons. Here we will only give a small example: the language of well parenthesised words
type empty
type 'a r = Dummy
type _ q =
| End : empty q
| Rparen : 'a q -> 'a r q
| Lparen : 'a r q -> 'a q
type start = Start of empty q
let !! x = x
let m = ! ""
let m = ! "()"
let m = ! "((())())()"
To encode the stack, we use the type parameters: Lparen pushes an r to the stack, Rparen consumes it and End checks that the stack is effectively empty.
There are a few more tricks needed to encode tests on the top value in the stack, and a conversion of a grammar to Greibach normal form to allow this encoding.
In fact we don't need to restrict to DCFL, we can for instance encode the a^n.b^n.c^n language which is not context free:
type zero
type 'a s = Succ
type (_,_) p =
| End : (zero,zero) p
| A : ('b s, 'c s) p -> ('b, 'c) p
| B : ('b, 'c s) q -> ('b s, 'c s) p
and (_,_) q =
| B : ('b, 'c) q -> ('b s, 'c) q
| C : 'c r -> (zero,'c s) q
and _ r =
| End : zero r
| C : 'c r -> 'c s r
type start = Start of (zero,zero) p
let v = Start (A (B (C End)))
let v = Start (A (A (B (B (C (C End))))))
We can also encode solutions of Post Correspondance Problems (PCP), which are not recursive languages:
Suppose we have two alphabets A = { X, Y, Z } et O = { a, b } and two morphisms m1 and m2 from A to O* defined as
m1(X) = a, m1(Y) = ab, m1(Z) = bba
m2(X) = baa, m2(Y) = aa, m2(Z) = bb
Solutions of this instance of PCP are words such that their images by m1 and m2 are equal. for instance ZYZX is a solution: both images are bbaabbbaa. The language of solution can be represented by this type declaration:
type empty
type 'a a = Dummy
type 'a b = Dummy
type (_,_) z =
| X : ('t1, 't2) s -> ('t1 a, 't2 b a a) z
| Y : ('t1, 't2) s -> ('t1 a b, 't2 a a) z
| Z : ('t1, 't2) s -> ('t1 b b a, 't2 b b) z
and (_,_) s =
| End : (empty,empty) s
| X : ('t1, 't2) s -> ('t1 a, 't2 b a a) s
| Y : ('t1, 't2) s -> ('t1 a b, 't2 a a) s
| Z : ('t1, 't2) s -> ('t1 b b a, 't2 b b) s
type start = Start : ('a,'a) z -> start
let v = X (Z (Y (Z End)))
let r = Start (X (Z (Y (Z End))))
Can every context free language (not deterministic) be represented like that ? Notice that the classical example of the palindrome can be represented (proof let to the reader).
So we have a nice extension available that allows you to define a new syntax by merely declaring a type. The code is available on github. We are waiting for the nice syntax you will invent !
PS: Their may remain a small problem... If inadvertently you mistype something you may find some quite complicated type errors attacking you like a pyranha instead of a syntax error.
Here is a short report of some of our activities in February 2014 !
After releasing version 1.1.1, we have been very busy preparing the next big things for OPAM. We have also steadily been improving stability and usability, with a focus on friendly messages: for example, there is a whole new algorithm to give the best explanations on what OPAM is going to do and why:
With OPAM 1.1.1, you currently get this information:
# opam install custom_printf.109.15.00
The following actions will be performed:
- remove pa_bench.109.55.02
- downgrade type_conv.109.60.01 to 109.20.00 [required by comparelib, custom_printf]
- downgrade uri.1.4.0 to 1.3.11
- recompile variantslib.109.15.03 [use type_conv]
- downgrade sexplib.110.01.00 to 109.20.00 [required by custom_printf]
- downgrade pa_ounit.109.53.02 to 109.18.00 [required by custom_printf]
- recompile ocaml-data-notation.0.0.11 [use type_conv]
- recompile fieldslib.109.20.03 [use type_conv]
- recompile dyntype.0.9.0 [use type_conv]
- recompile deriving-ocsigen.0.5 [use type_conv]
- downgrade comparelib.109.60.00 to 109.15.00
- downgrade custom_printf.109.60.00 to 109.15.00
- downgrade cohttp.0.9.16 to 0.9.15
- recompile cow.0.9.1 [use type_conv, uri]
- recompile github.0.7.0 [use type_conv, uri]
0 to install | 7 to reinstall | 0 to upgrade | 7 to downgrade | 1 to remove
With the next
trunk version of OPAM, you will get the much more informative output on real dependencies:
# opam install custom_printf.109.15.00
The following actions will be performed:
- remove pa_bench.109.55.02 [conflicts with type_conv, pa_ounit]
- downgrade type_conv from 109.60.01 to 109.20.00 [required by custom_printf]
- downgrade uri from 1.4.0 to 1.3.10 [uses sexplib]
- recompile variantslib.109.15.03 [uses type_conv]
- downgrade sexplib from 110.01.00 to 109.20.00 [required by custom_printf]
- downgrade pa_ounit from 109.53.02 to 109.18.00 [required by custom_printf]
- recompile ocaml-data-notation.0.0.11 [uses type_conv]
- recompile fieldslib.109.20.03 [uses type_conv]
- recompile dyntype.0.9.0 [uses type_conv]
- recompile deriving-ocsigen.0.5 [uses type_conv]
- downgrade comparelib from 109.60.00 to 109.15.00 [uses type_conv]
- downgrade custom_printf from 109.60.00 to 109.15.00
- downgrade cohttp from 0.9.16 to 0.9.14 [uses sexplib]
- recompile cow.0.9.1 [uses type_conv]
- recompile github.0.7.0 [uses uri, cohttp]
0 to install | 7 to reinstall | 0 to upgrade | 7 to downgrade | 1 to remove
Failsafe behaviour is being much improved as well, because things do happen to go wrong when you access the network to download packages and then compile them, and that was the biggest source of problems for our users: errors are now more tightly controlled in each stage of the opam command.
For example, nothing will be changed in case of a failed or interrupted download, and if you press
C-c in the middle of an action, you'll get something like this:
^C[ERROR] User interruption while waiting for sub-processes
[ERROR] Failure while processing typerex.1.99.6-beta
=-=-= Error report =-=-=
These actions have been completed successfully
install conf-gtksourceview.2
upgrade cmdliner from 0.9.2 to 0.9.4
The following failed
install typerex.1.99.6-beta
Due to the errors, the following have been cancelled
install ocaml-top.1.1.2
install ocp-index.1.0.2
install ocp-build.1.99.6-beta
recompile alcotest.0.2.0
install ocp-indent.1.4.1
install lablgtk.2.16.0
The former state can be restored with opam switch import -f "<xxx>.export"
You also shouldn't have to dig anymore to find the most meaningful error when something fails.
With the ever-increasing number of packages and versions, resolving requests becomes a real challenge and we're glad we made the choice to rely on specialized solvers. The built-in heuristics may show its limits when attempting long-delayed upgrades, and everybody is encouraged to install an external solver (aspcud being the one supported at the moment).
Consequently, we have also been working more tightly with the Mancoosi team at IRILL to improve interaction with the solver, and how the user can get the best of it is now well documented, thanks to Roberto Di Cosmo.
At OCamlPro, we often use OPAM with multiple switches, to test whether our tools are working with different versions of OCaml, including the new ones that we are developing. Switching between versions is not always as intuitive as we would like, as we sometimes forget to call
eval `opam config env`
in the right location or at the good time, and end up compiling a project with a different version of OCaml that we would have liked.
It was quite surprising to discover that a tool that we had developed a long time ago, ocp-manager, would actually become a solution for us to a problem that appeared just now with OPAM:
ocp-manager was a tool we used to switch between different versions of OCaml before OPAM. It would use a directory of wrappers, one for each OCaml tool, and by adding this directory once and for all to the PATH, with:
eval `ocp-manager -config`
You would be able to switch to OPAM switch 3.12.1 (that needs to have been installed first with OPAM) immediatly by using:
ocp-manager -set opam:3.12.1
Nothing much different from OPAM ? The nice thing with
ocp-manager is that wrappers also use environment variables and per-directory information to choose the OCaml version of the tool they are going to run. For example, if some top-directory of your project contains a file
.ocp-switch with the line "opam:4.01.0", your project will always be compiled with this version of OCaml, even if you change the global per-user configuration. You can also override the global and local configuration by setting the
OCAML_VERSION environment variable.
Maybe ocp-manager can also be useful for you. Just install it with
opam install ocp-manager, change your shell configuration to add its directory to your PATH, and check if it also works for you (the manpage can be very useful!).
ocamlopt under Reviewing Process
This month, we also spent a lot of time improving the optimization patches that we submitted for inclusion into OCaml, and that we have described in our previous blog posts. Mark Shinwell from Jane Street and Gabriel Scherer from INRIA kindly accepted to devote some of their time in a thorough reviewing process, leading to many improvements in the readability and maintenability of our optimization code. As this first patch is a prerequisite for our next patches, we also spent a lot of time propagating these modifications, so that we will be able to submit them faster once this one has been merged!
In our study to understand the memory behavior of OCaml applications, we have investigated the distribution of block sizes, both in the heap (live blocks) and in the free list (dead blocks). This information should help the programmer to understand which GC parameters might be the best ones for his application, by showing the fragmentation of the heap and the time spent searching in the free list. It is all the more important that improving the format of the free list with bins has been discussed lately in the Core team.
Here, we display the distribution of blocks at a snapshot during the execution of
why3replayer, a tool that we are trying to optimize during the Bware Project. The number of free blocks is displayed darker than live blocks, from size 21 to size 0.
It is interesting to notice that, for this applications, almost all allocations have a size smaller than 6. We are planning to use such information to simulate the cost of allocation for this application, and see which data structure for the free list would benefit the most to the performance of the application.
The static OCaml analyszer is going quite well. Our set of (working) test samples is growing in size and complexity. Our last improvement was what is called widening. What's widening ? Well, the main idea is "when I go through a big loop 5000 times, I don't want the analyzer to do that too". If we take this sample test:
let () = for i = 0 to 5000 do () done
Without widening, the analysis would loop 5000 times through that loop. That's quite useless, not to mention that replacing 5000 by
Random.int () would make the analysis loop until max_int (2^62 times on a 64-bits computer) ! Worse, let's take this code:
let () =
let x = ref 0 in
for i = 1 to 10 do
x := !x + 1
Here, the analysis would not see that the increment on !x and i would be linked (that's one of the aproximations we do to make the computation doable). So, the analyzer does not loop ten times, but again 2^62 times: we do not want that to happen.
The good news now: we can say to the analyzer "every time you go through a loop, check what integers you incremented, and suppose you'll increment them again and again until you can't". This way we only go twice through our for-loop: first to discover it, then to propagate the widening approximation.
Of course this is not that simple, and we'll often loose information by doing only two iterations. But in most cases, we don't need it or we can get it in a quicker way than iterating billions of times through a small loop.
Hopefully, we'll soon be able to analyze any simple program that uses only
Pervasives and the basic language features, but
for and
while loops are already a good starting point !
The SPARK toolset, developped by the AdaCore company, targets the verification of programs written in the SPARK language; a subset of Ada used in the design of critical systems. We published this month a use-case of Alt-Ergo that explains the integration of our solver as a back-end of the next generation of SPARK.
Discussions with SPARK 2014 developpers were very important for us to understand the strengths of Alt-Ergo for them and what would be improved in the solver. We hope this use-case will be helpful for IT solutions providers that would need an automatic solver in their products.
We are still working at improving the Scilab environment with new tools written in OCaml. We are soon going to release a new version of Scilint, our style-checking tool for Scilab code, with a new parser compatible with Scilab 5 syntax. Changing the parser of Scilint was not an easy job: while our initial parser was partially based on the yacc parser of the future Scilab 6, we had to write the new parser from scratch to accept the more tolerant syntax of Scilab 5. It was also a good opportunity to design a cleaner AST than the one copied from Scilab 6: written in C++, Scilab 6 AST would for example have all AST nodes inherit from the
Exp class, even instructions or the list of parameters of a function prototype !
We have also started to work on a type-system for Scilab. We want the result to be a type language expressive enough to express, say, the (dependent) sizes of matrices, yet simple enough for clash messages not to be complete black magic for Scilab programmers. This is not simple. In particular, there is the other constraint to build a versatile type system that could serve a JIT or give usable information to the programmer. Which means that the type environment is a mix of static information coming from the inference and of annotations, and dynamic information gotten by introspection of the dynamic interpreter.
In the mean time, we are also planning to write a simpler JIT, to mitigate the impatience of Scilab programmers expecting to feel the underlying power of OCaml!
Here is a short report of some of our activities in last December and January !
With the support of LexiFi, we started working on a new Intel backend for the
ocamlopt native code compiler. Currently, there are four Intel backends in
i386/emit.mlp and
i386/emit_nt.mlp, i.e. support for two processors (amd64 and i386) and two OS variants (Unices and Windows). These backends directly output assembly sources files, on which the platform assembler is called (
gas on Unices, and
masm on Windows).
The current organisation makes it hard to maintain these backends: code for a given processor has to be written in two almost identical files (Unix and Windows), with subtle differences in the syntax: for example, the destination operand is the second parameter in
gas syntax, while it is the first one in AT&T syntax ('masm').
Our current work aims at merging, for each processor, the Unix and Windows backends, by making them generate an abstract representation of the assembly. This representation is shared between the two processors ('amd64' and 'i386'), so that we only have to develop two printers, one for
gas syntax and one for
masm syntax. As a consequence, maintenance of the backend will be much easier: while writting the assembly code, the developer does not need to care about the exact syntax. Moreover, the type-checker can verify that each assembler instruction is used with the correct number of well-formatted operands.
Finally, our hope is that it will be also possible to write optimization passes directly on the assembly representation, such as peephole optimizations or instruction re-scheduling. This work is available in OCaml SVN, in the "abstract_x86_asm" branch.
OPAM has been shifted from the 1.1.0-RC to 1.1.1, with large stability and UI improvements. We put a lot of effort on improving the interface, and on helping to build other tools in the emerging ecosystem around OPAM. Louis visited OCamlLabs, which was a great opportunity to discuss the future of OPAM and the platform, and contribute to their effort towards opam-in-a-box, a new way to generate pre-configured VirtualBox instances with all OCaml packages locally installable by OPAM, particularly convenient for computer classrooms.
The many plans and objectives on OPAM can be seen and discussed on the work-in-progress OPAM roadmap. Lots of work is ongoing for the next releases, including Windows support, binary packages, and allowing more flexibility by shifting the compiler descriptions to the packages.
ocp-index and its new Brother,
On our continued efforts to improve the environment and tools for OCaml hackers, we also made some extensions to
ocp-index, which in addition to completing and documenting the values from your libraries, using binary annotations to jump to value definitions, now comes with a tiny
ocp-grep tool that offers the possibility to syntactically locate instances of a given identifier around your project -- handling
open, local opens, module aliases, etc. In emacs,
C-c / will get the fully qualified version of the ident under cursor and find all its uses throughout your project. Simple, efficient and very handy for refactorings. The
ocp-index query interface has also been made more expressive. Some documentation is online and will be available shortly in upcoming release 1.1.
ocp-cmicomp: Compression of Interface Files for Try-OCaml
While developing Try-OCaml, we noticed a problem with big compiled interface files (.cmi). In Try-OCaml, such files are embedded inside the JavaScript file by
js_of_ocaml, resulting in huge code files to download on connection (about 12 MB when linking
Dom_html from
js_of_ocaml, and about 40 MB when linking
Core_kernel), and the browser freezing for a few seconds when opening the corresponding modules.
To reduce this problem, we developed a tool, called
ocp-cmicomp, to compress compiled interface files. A compiled interface file is just a huge OCaml data structure, marshalled using
output_value. This data structure is often created by copying values from other interface files (types, names of values, etc.) during the compilation process. As this is done transitively, the data structure has a lot of redundancy, but has lost most of the sharing.
ocp-cmicomp tries to recover this sharing: it iterates on the data structure, hash-consing the immutable parts of it, to create a new data structure with almost optimal sharing.
To increase the opportunities for sharing,
ocp-cmicomp also uses some heuristics: for example, it computes the most frequent methods in objects, and sort the list of methods of each object type in increasing order of frequency. As a consequence, different object types are more likely to share the same tail. Finally, we also had to be very careful: the type-checker internally uses a lot physical comparison between types (especially with polymorphic variables and row variables), so that we still had to prevent sharing of some immutable parts to avoid typing problems.
The result is quite interesting. For example,
dom_html.cmi was reduced from 2.3 MB to 0.7 MB (-71%, with a lot of object types), and the corresponding JavaScript file for Try-OCaml decreased from 12 MB to 5 MB.
core_kernel.cmi was reduced from 13.5 MB to 10 MB (-26%, no object types), while the corresponding JavaScript decreased from 40 MB to 30 MB !
A common problem when writing portable software is to locate the resources of the program, and its predefined configuration files. The program has to know the system on which it is running, which can be done like in old times by patching the source, generating a set of globals or at run-time. Either way, paths may then vary depending on the system. For instance, paths are often completely static on Unix while they are partially forged on bundled MacOS apps or on Windows. Then, there is always the task of bundling the binary with its auxiliary files which depends on the OS.
For big apps with lots of system interaction, it is something you have to undertake. However, for small apps, it is an unjustified burden. The alternative proposed by OCamlRes is to bundle these auxiliary files at compile time as an OCaml module source. Then, one can just compile the same (partially pre-generated) code for all platforms and distribute all-inclusive, naked binary files. This also has the side advantage of turning run-time exceptions for inexistent or invalid files to compile-time errors. OCamlRes is made of two parts:
ocplib-ocamlres library to manipulate resources at run-to time, scan input files to build resource trees, and to dump resources in various formats
a command line tool
ocp-ocamlres, that reads the ressources and bundles them into OCaml source files.
OCamlRes has several output formats, some more subtle than the default mechanism (which is to transform a directory structure on the disk into an OCaml static tree where each file is replaced by its content), and can (and will) be extended. An example is detailed in the documentation file.
The last post mentioned improvements on the prototype compiler optimization allowing recursive functions specialization. Some quite complicated corner cases needed a rethink of some parts of the architecture. The first version of the patch was meant to be as simple as possible. To this end we chose to avoid as much as possible the need to maintain non trivialy checkable invariants on the intermediate language. That decision led us to add some constraints on what we allowed us to do. One such constraint that matters here, is that we wanted every crucial information (that break things up if the information is lost) to be propagated following the scope. For instance, that means that in a case like:
let x = let y = 1 in (y,y) in x
the information that
y is an integer can escape its scope but if the information is lost, at worst the generated code is not as good as possible, but is still correct. But sometimes, some information about functions really matters:
let f x =
let g y = x + y in
let h a =
let g = f a in
g a
Let's suppose in this example that
f cannot be inlined, but
g can. Then,
h becomes (with
g.x being access to
x in the closure of
let h a =
let g = f a in
a + g.x
Let's suppose that some other transformation elsewhere allowed
f to be inlined now, then
h becomes:
let h a =
let x = a in
let g y = x + y in (* and the code can be eliminated from the closure *)
a + g.x
Here the closure of of
g changes: the code is eliminated so only the
x field is kept in the block, hence changing its offset. This information about the closure (what is effectively available in the closure) must be propagated to the use point (
g.x) to be able to generate the offset access in the block. If this information is lost, there is no way to compile that part. The way to avoid that problem was to limit a bit the kind of cases where inlining is possible so that this kind of information could always be propagated following the scope. But in fact a few cases did not verify that property when dealing with inlining parameters from different compilation unit.
So we undertook to rewrite some part to be able to ensure that those kinds of information are effectively correctly propagated and add assertions everywhere to avoid forgeting a case. The main problem was to track all the strange corner cases, that would almost never happen or wouldn't matter if they were not optimally compiled, but must not loose any information to satisfy the assertions.
Last month, we considered the formalization and the proof of a critical component of Alt-Ergo's core. This component handles equalities solving to produce equivalent substitutions. However, since Alt-Ergo handles several theories (linear integer and rational arithmetic, enumerated datatypes, records, ...), providing a global routine that combines solvers of these individual theories is needed to be able to solve mixed equalities.
The example below shows one of the difficulties we faced when designing our combination algorithm: the solution of the equality
r = {a = r.a + r.b; b = 1; c = C} cannot just be of the form
r |-> {a = r.a + r.b; b = 1; c = C} as the pivot r appears in the right-hand side of the solution. To avoid this kind of subtle occur-checks, we have to solve an auxiliary and simpler conjunction of three equalities in our combination framework:
r = {a = k1 + k2; b = 1; c = C},
r.a = k1 and
r.b = k2 (where
k1 and
k2 are fresh variables). We will then deduce that
k2 |-> 1 and that
k1 + k2 = k1, which has no solution.
type enum = A | B | C
type t = { a : int ; b : enum }
logic r : t
goal g: r = {a = r.a + r.b; b = 1; c = C} -> false
After having implemented a new combination algorithm in Alt-Ergo a few months ago, we considered its formalization and its proof, as we have done with most of the critical parts of Alt-Ergo. It was really surprising to see how types information associated to Alt-Ergo terms helped us to prove the termination of the combination algorithm, a crucial property that was hard to prove in our previous combination algorithms, and a challenging research problem as well.
On the development side, we conducted some preliminary experiments in order to extend Alt-Ergo with a model generation feature. This capability is useful to derive concrete test-cases that may either exhibit erroneous behaviors of the program being verified or bugs in its formal specification.
In a first step, we concentrated on model generation for the combination of the theories of uninterpreted functions and linear integer arithmetic. The following example illustrates this problem:
logic f : int -> int
logic x, y : int
goal g: 2*x >= 0 -> y >= 0 -> f(x) <> f(y) -> false
We have a satisfiable (but non-valid) formula, where
x and
y are in the integer intervals
[0,+infinity[ and
f(x) <> f(y). We would like to find concrete values for
y and
f that satisfy the formula. A first attempt to answer this question may be the following:
From an arithmetic point of view,
x = 0 and
y = 0 are possible values for
x and
y. So, Linear arithmetic suggests this partial model to other theories.
The theory of uninterpreted functions cannot agree with this solution. In fact,
x = y = 0 would imply
f(x) = f(y), which contradicts
f(x) <> f(y). More generally,
x should be different from
Now, if linear arithmetic suggests,
x = 0 and
y = 1, the theory of uninterpreted functions will agree. The next step is to find integer values for
f(0) and
f(1) such that
f(0) <> f(1).
After having implemented a brute force technique that tries to construct such models, our main concern now is to find an elegant and more efficient 'divide and conquer' strategy that allows each theory to compute its own partial model with guarantees that this model will be coherent with the partial models of the other theories. It would be then immediate to automatically merge these partial solutions into a global one.
We are pleased to welcome three new members in our OCamlPro team since the beginning of November:
Benjamin Canou started working at OCamlPro on the Richelieu project, an effort to bring better safety and performance to the Scilab language. He is in charge of a type inference algorithm that will serve both as a developper tool and in coordination with a JIT. He spent his first month understanding the darkest corners of the language, and then writing a versatile AST with a parser to build it. Actually, this is not an easy task, because the language gives different statuses to characters (including spaces) depending on the context, leading to non-trivial lexing. But the real source of problems is the fact that the original lexparser is intermingled with the interpreter inside a big bunch of venerable
FORTRAN code. This old fellow makes parsing choices depending on the dynamic typing context, allows its users to catch syntax errors at runtime, among other fun things. The new OCaml lexer and parser is handwritten in around a thousand lines, has performance comparable to a
Yacc generated one, and is resilient to errors so it could be integrated into an IDE to detect errors on the fly without stopping on the first one. Once again, it's OCaml to the rescue of the weak and elderly!
An example of the kind of code that can be written in Scilab:
if return = while then [ 12..
34.. ... .. ...
56 } ; else '"'"
which is parsed into:
-- parsed in 0.000189--
(script (if (== !return !while) (matrix (row 123456)) "'"))
-- messages
1.10:1.11: use of deprecated operator '='
-- end
Gregoire Henry started working at OCamlPro on the Bware project. He is tackling the optimization of memory performance of automatic provers written in OCaml, in collaboration with Cagdas Bozman. One of his first contributions after joining us was to exhume his internship work of 2004, an implementation of Graphics for Mac OS X that we are going to use for our online OCaml IDE!
Thomas Blanc started a PhD at OCamlPro after his summer internship with us. He is going to continue his work on whole-program analysis, especially as a way to detect uncaught exceptions. We hope his tool will be a good replacement for the ocamlexn tool written by Francois Pessaux.
On the compiler optimization front, Pierre Chambart got direct access to the OCaml SVN, so that he will soon upload his work directly into an SVN branch, easier for reviewing and integration into the official compiler. A current set of optimizations is already scheduled for the new branch, and is now working on inlining recursive functions, such
List.map, by inlining the function definition at the call site, when at least one of its arguments is invariant during recursion.
An function that can benefit a lot from that transformation is:
let f l = List.fold_left (+) 0 l
movq %rax, %rdi
movq $1, %rbx
jmp camlTest__fold_left_1017@PLT
cmpq $1, %rdi
je .L100
movq 8(%rdi), %rsi
movq (%rdi), %rdi
leaq -1(%rbx, %rdi), %rbx
movq %rsi, %rdi
jmp .L101
.align 4
movq %rbx, %rax
After lots of testing and fixing, the official version
1.1.0 of OPAM has finally been released. It features lots of stability improvements, and a reorganized and cleaner repo now hosted at https://opam.ocaml.org. Work goes on on OPAM as we'll release
opam-installer soon, a small script that enables using and testing
.install files. This is a step toward a better integration of OPAM with existing build tools, and are experimenting with ways to ease usage for Coq packages, to generate binary packages, and to enhance portability.
We also started to experiment with binary packages. We developed a very small tool,
ocp-bin, that monitors the compilation of every OPAM package, takes a snapshot of OPAM files before and after the compilation and installation, and generates a binary archive for the package. The next time the package is re-installed, with the same dependencies, the archive is used instead of compiling the package again.
For a typical package, the standard OPAM file:
build: [
[ "./configure" "--prefix" "%{prefix}%"]
[ "make]
[ make "install"]
remove: [
[ make "uninstall" ]
has to be modified in:
build: [
[ "ocp-bin" "begin" "%{package}%" "%{version}%" "%{compiler}%" "%{prefix}%"
"-opam" "-depends" "%{depends}%" "-hash" "%{hash}%"
"-nodeps" "ocamlfind." ]
[ "ocp-bin" "--" "./configure" "--prefix" "%{prefix}%"]
[ "ocp-bin" "--" make]
[ "ocp-bin" "--" make "install"]
[ "ocp-bin" "end" ]
remove: [
[ "!" "ocp-bin" "uninstall"
"%{package}%" "%{version}%" "%{compiler}%" "%{prefix}%" ]
Such a transformation would be automated in the future by adding a field
ocp-bin: true. Note that, since
ocp-bin takes care of the deinstallation of the package, it would ensure a complete and correct deinstallation of all packages.
We also implemented a client-server version of
ocp-bin, to be able to share binary packages between users. The current limitation with this approach is that many binary packages are not relocatable: if packages are compiled by Bob to be installed in
/home/bob/.opam/4.01.0, the same packages will only be usable on a different computer by a user with the same home path! Although it can still be useful for a user with several computers, we plan to investigate now on how to build relocatable packages for OCaml.
Always looking for a way to provide better tools to the OCaml programmer, we are happy to announce the first stable release of ocp-index, which provides quick access to the installed interfaces and documentation as well as some source-browsing features (lookup ident definition, search for uses of an ident, etc).
One of the most exciting events this month is the use of the ocp-memprof tool to profile an execution of Alt-Ergo on a big formula generated by the Cubicle model checker. The story is the following:
The formula was generated from a transition system modeling the FLASH coherence cache protocol, plus additional information computed by Cubicle during the verification of FLASH's safety. It contains a sub-formula made of nested conjunctions of 999 elements. Its proof requires reasoning in the combination of the free theory of equality, enumerated data types and quantifiers. Alt-Ergo was able to discharge it in only 10 seconds. However, Alain Mebsout --- who is doing his Phd thesis on Cubicle --- noticed that Alt-Ergo allocates more than 60 MB during its execution.
In order to localize the source of this abnormal memory consumption, we installed the OCaml Memory Profiler runtime, version
4.00.1+memprof (available in the private OPAM repository of OCamlPro) and compiled Alt-Ergo using
-bin-annot option in order to dump
.cmt files. We then executed the prover on Alain's example as shown below, without any instrumentation of Alt-Ergo's code.
$$ OCAMLRUNPARAM=m ./alt-ergo.opt formula.mlw
This execution caused the modified OCaml compiler to dump a snapshot of the typed heap at every major collection of the GC. The names of dumped files are of the form
memprof.<PID>.<DUMP-NAME>.<image-number>.dump, where
PID is a natural number that identifies the set of dumped files during a particular execution.
Dumped files were then fed to the
ocp-memprof tool (available in the TypeRex-Pro toolbox) using the syntax below. The synthesis of this step (
.hp file) was then converted to a
.ps file thanks to
hp2ps command. At the end, we obtained the diagram shown in the figure below.
$$ ./ocp-memprof -loc -sizes PID
From the figure above, one can extract the following information:
there were 15 major collections of OCaml's GC during the above execution (the x-axis),
Alt-Ergo allocated more than 60 MB during its execution (the y-axis),
Some function in file
src/preprocess/why_typing.ml is allocating a lot of data of type
Parsed.pp_desc at line
868 (the first square of the legend).
The third point corresponds to a piece of code used in a recursive function that performs alpha renaming on parsed formulas to avoid variable captures. This code is the following:
let rec alpha_renaming_b s f =
| PPinfix(f1, op, f2) -> (* 'op' may be the AND operator *)
let ff1 = alpha_renaming_b s f1 in
let ff2 = alpha_renaming_b s f2 in
PPinfix(ff1, op, ff2) (* line 868 *)
Actually, in 99% there are no capture problems and the function just reconstructs a new value
PPinfix(ff1, op, ff2) that is structurally equal (=) to its argument
f. In case of very big formulas (recall that Alain's formula contains a nested conjunction of 999 elements), this causes Alt-Ergo to allocate a lot.
Fixing this behavior was straightforward. We only had to check whether recursive calls to alpha renaming function returned modified values using physical equality
==. If not, no renaming is performed and we safely return the formula given in the argument. This way, the function will never allocate for formulas without capture issues. For instance, the piece of code given above is fixed as follows:
let rec alpha_renaming_b s f =
| PPinfix(f1, op, f2) ->
let ff1 = alpha_renaming_b s f1 in
let ff2 = alpha_renaming_b s f2 in
if ff1 == f1 && ff2 == f2 then f (* no renaming performed by recursive calls ? *)
else PPinfix(ff1, op, ff2)
Once we applied the patch on the hole function
alpha_renaming_b, Alt-Ergo only needed 2 seconds and less than 2.2MB memory to prove our formula. Profiling an execution of patched version of the prover with OCaml
4.00.1+memprof and
ocp-memprof produced the diagram below. The difference with the first drawing was really impressive.
This month our work on Richelieu was mainly focused on improving Scilint. After some discussions with Scilab knowledgeable users, we chose a new set of warnings to implement. Among other things those warnings analyze primitive fonctions and their arguments as well as loop variables. Another important thing was to allow SciNotes, Scilab's editor, to display our warnings. This has been done by implementing support for Firehose. Finally some minor bugs were also fixed.
Here is a short report of our activities in September-October 2013.
We were very happy to participate to OCaml'2013, in Boston. The event was a great success, with a lot of interesting talks and many participants. It was a nice opportunity for us to present some of our recent work:
Fabrice presented his work on the design of the wxOCaml library. Although the wxOCaml library itself is an interesting project, the goal of his talk was to show that binding thousands of functions from a C++ library can be automated very easily in OCaml, and make the bindings easy to maintain and to improve.
The work of Thomas and Louis on OPAM was presented in a talk by Anil on the OCaml Platform v0.1. The OCaml Platform is a set of tools, including OPAM, to provide an ever increasing set of packages for OCaml developers, including high-quality documentation and broad portability. Some statistics showed how OPAM, in less than a year, grew from 200 packages to more than 1400 packages, and from 2-3 contributors to about 130 contributors in September. Another talk, Ocamlot: OCaml Online Testing presented how sets of packages will now be automatically tested, to give immediate feedback to contributors, and an evaluation of packages quality to users.
Pierre presented his work on Improving OCaml high level optimisations that he also presented in a recent blog post.
Grégoire presented his work with Jacques Garrigue on Runtime types in OCaml. In particular, he showed how abstraction is hard to deal with, as there is a dilemma between the ability to write powerful polytipic functions and the preservation of the abstraction wanted by the developer for code modularity.
Finally, Çagdas presented his work on Profiling the Memory Usage of OCaml Applications without Changing their Behavior. This new profiler will be able to provide precise memory information on production OCaml software, by snapshoting the memory and recovering type information. It is currently being tested on several projects, such as the Why3 verification tool.
Of course, the day was full of interesting talks, and we can only advise to see all of them on the complete program that is now online.
CUFP'2013 Program was also very dense. For OCaml users, Dave Thomas, first keynote, reminded us how important it is to build two-way bridges between OCaml and other languages: we have the bad habit to only build one-way bridges to just use other languages from OCaml, and forget that new users will have to start by using small OCaml components from their existing software written in another language. Then, Julien Verlaguet presented the use of OCaml at Facebook to type-check and compile a typed version of PhP, HipHop, that is now used for a large part of the code at Facebook.
The period of September-October was also very busy trying to find some funding for our projects. Fortunately, we still managed to make a lot of progress in the development of these projects:
Lots has been going on regarding OPAM, as the 1.1 release is being pushed forward, with a beta and a RC available already. This release focuses on stability improvements and bug-fixes, but is nonetheless a large step from 1.0, with an enhanced update mechanism, extended metadata, an enhanced 'pin' workflow for developers, and much more.
We are delighted by the success met by OPAM, which was mentioned again and again at the OCaml'2013 workshop, where we got a warming lot of positive feedback. To be sure that this belongs to the community, after licensing all metadata of the repository under CC0 (as close to public domain as legally possible), we have worked hand in hand with OCamlLabs to migrate it to opam.ocaml.org. External repositories for Windows, Android and so on are appearing, which is a really good thing, too.
In September, we officially announced the distribution and the support of Alt-Ergo by OCamlPro and launched its new website. This site allows to download public releases and to discover available support offerings. We have also published a new public release (version 0.95.2) of the prover. The main changes in this minor release are: source code reorganization, simplification of quantifier instantiation heuristics, GUI improvement to reduce latency when opening large files, as well as various bug fixes.
During September, we also re-implemented and simplified other parts of Alt-Ergo. In addition, we started the integration of a new SAT-solver based on miniSAT (implemented as a plug-in) and the development of a new tool, called Ctrl-Alt-Ergo, that automates the most interesting strategies of Alt-Ergo. The experiments we made during October are very encouraging as shown by our previous blog post.
Luca Saiu completed his work at Inria and on the multi-runtime branch, fixing the last bugs and leaving the code in a shape not too far removed from permitting its eventual integration into the OCaml mainline.
Now, the code has a clean configuration-time facility for disabling the multi-runtime system, and compatibility is restored with architectures not including the required assembly support to at least compile and work using a single runtime. A crucial optimization permits to work in this mode with extremely little overhead with respect to stock OCaml. Testing on an old PowerPC 32-bit machine revealed a few minor portability problems related to word size and endianness.
We have been working on allowing cross module inlining. We wanted to be able to show a version generating strictly better code than the current compiler. This milestone being reached, we are now preparing a patch series for upstreaming the base parts. We are also working on polishing the remaining problems: the passes were written in an as simple as possible way, so compilation time is still a bit high. And there are a few difficulties remaining with cross module inlining and packs.
The team is also evolving, and some of us are now leaving the team to join other projects:
After two years with us, Thomas Gazagnaire has left OCamlPro in October to work most of his time on Mirage in Cambridge (UK). Thomas was OCamlPro's first employee, and OCamlPro probably wouldn't exist without him. Thomas has also been the main architect of OPAM, and was involved in the design of many of our projects. Louis Gesbert will continue his work on developing and maintaining OPAM.
After one year with us, Luca Saiu has left Inria in October. Luca has made a tremendous work on the implementation of a multicore-OCaml, where every runtime runs in a different memory space with its own garbage collector. We hope to be able to upstream his work soon to the official OCaml distribution.
After an internship with us, Pierrick Couderc, Souhire Kenawi and David Maison are back to their masters' studies since September. Souhire worked on testing the development of iOS applications on Linux with OCaml, a very challenging task ! Pierrick and David developed an online editor for OCaml that we are going to release very soon.
This blog post was about departures, but stay connected, next month, we are going to announce some newcomers who decided to join the team for the winter !
As announced in a previous post, I joined OCamlPro at the beginning of September and I started working on Alt-Ergo. Here is a report presenting the tool and the work we have done during the two last months.
Alt-Ergo is an open source automatic theorem prover based on SMT technology. It is developed at Laboratoire de Recherche en Informatique, Inria Saclay Ile-de-France and CNRS since 2006. It is capable of reasoning in a combination of several built-in theories such as uninterpreted equality, integer and rational arithmetic, arrays, records, enumerated data types and AC symbols. It also handles quantified formulas and has a polymorphic first-order native input language. Alt-Ergo is written in OCaml. Its core has been formally proved in the Coq proof assistant.
Alt-Ergo has been involved in a qualification process (DO-178C) by Airbus Industrie. During this process, a qualification kit has been produced. It was composed of a technical document with tool requirements (TR) that gives a precise description of each part of the prover, a companion document (~ 450 pages) of tests, and an instrumented version of the tool with a TR trace mechanism.
Alt-Ergo is mainly used to prove the validity of mathematical formulas generated by program verification platforms. It was originally designed and tuned to prove formulas generated by the Why tool. Now, it is used by different tools and in various contexts, in particular via the Why3 platform. As shown by the diagram below, Alt-Ergo is used to prove formulas:
generated from Ada code by SPARK 2005 and SPARK 2014,
produced from WhyML programs by Why3,
translated from proof obligations generated by Atelier-B,
Moreover, Alt-Ergo is used in the context of cryptographic protocols verification by EasyCrypt and in SMT-based model checking by Cubicle.
Below are some basic formulas written in the why input syntax. Each example is proved valid by Alt-Ergo. The first formulas is very simple and is proved with a straightforward arithmetic reasoning.
"goal g2" requires reasoning in the combination of functional arrays and linear arithmetic, etc. The last example contains a quantified sub-formula with a polymorphic variable
x. Generating four ground instances of this axiom where
x is replaced by
1.4 and
a respectively is necessary to prove
"goal g5".
(*** Simple arithmetic formula ***)
goal g1 : 1 + 2 = 3
(*** Theories of functional arrays and linear integer arithemtic ***)
logic a : (int, int) farray
goal g2 : forall i:int. i = 6 -> a[i<-4][5] = a[i-1]
(*** Theories of records and linear integer arithmetic ***)
type my_record = { a : int ; b : int }
goal g3 : forall v,w : my_record. 2 * v.a = 10 -> { v with b = 5} = w -> w.a = 5
(*** theories of enumerated data types and uninterpreted equality ***)
type my_sum = A | B | C
logic P : 'a -> prop
goal g4 : forall x : my_sum. P(C) -> x<>A and x<>B -> P(x)
(*** formula with quantifiers and polymorphism ***)
axiom a: forall x : 'a. P(x)
goal g5 : P(1) and P(true) and P(1.4) and P(a)
$$ alt-ergo examples.why
File "examples.why", line 2, characters 1-21:Valid (0.0120) (0)
File "examples.why", line 6, characters 1-53:Valid (0.0000) (1)
File "examples.why", line 10, characters 1-81:Valid (0.0000) (3)
File "examples.why", line 15, characters 1-59:Valid (0.0000) (6)
File "examples.why", line 19, characters 1-47:Valid (0.0000) (10)
On September 20, we officially announced the distribution and the support of Alt-Ergo by OCamlPro and launched its new website. This site allows to download public releases of the prover and to discover available support offerings. It'll be enriched with additional content progressively. The former Alt-Ergo's web page hosted by LRI is now devoted to theoretical foundations and academic aspects of the solver.
We have also published a new public release (version 0.95.2) of Alt-Ergo. The main changes in this minor release are: source code reorganization into sub-directories, simplification of quantifiers instantiation heuristics, GUI improvement to reduce latency when opening large files, as well as various bug fixes.
In addition to the re-implementation and the simplification of some parts of the prover (e.g. internal literals representation, theories combination architecture, ...), the main novelties of the current master branch of Alt-Ergo are the following:
The user can now specify an external (plug-in) SAT-solver instead of the default DFS-based engine. We experimentally provide a CDCL solver based on miniSAT that can be plugged to perform satisfiability reasoning. This solver is more efficient when formulas contain a rich propositional structure.
We started the development of a new tool, called Ctrl-Alt-Ergo, in which we put our expertise by implementing the most interesting strategies of Alt-Ergo. The experiments we made with our internal benchmarks are very promising, as shown below.
We compared the performances of latest public releases of Alt-Ergo with the current master branch of both Alt-Ergo and Ctrl-Alt-Ergo (commit
ce0bba61a1fd234b85715ea2c96078121c913602) on our internal test suite composed of 16209 formulas. Timeout was set to 60 seconds and memory was limited to 2GB per formula. Benchmarks descriptions and the results of our evaluation are given below.
This benchmark contains 2470 formulas generated from Why3's gallery of WhyML programs. Some of these formulas are out of scope of current SMT solvers. For instance, the proof of some of them requires inductive reasoning.
This benchmark is composed of 3167 formulas generated from Ada programs used during Hi-lite project. It is known that some formulas are not valid.
This test-suite contains 10572 formulas translated from proof obligations generated by Atelier-B. These proof obligations are issued from industrial B projects and are proved valid.
version 0.95.1
version 0.95.2
master branch*
master branch*
|Release date
|Mar. 05, 2013
|Sep. 20, 2013
|- - -
|- - -
|Why3 benchmark
(91.90 %)
(92.63 %)
(93.44 %)
(95.67 %)
|SPARK benchmark
(74.23 %)
(74.52 %)
(74.93 %)
(75.91 %)
|BWare benchmark
(53.05 %)
(89.26 %)
(95.27 %)
(98.12 %)
(*) commit
Here is a short report on the different projects we have been working on in August.
After our reports on better inlining have raised big expectations, we have been working hard on fixing the few remaining bugs. An enhanced alias/constant analysis was added, to provide the information needed to lift some constraints on the maintained invariants, and simplifying some other passes quite a lot in the process. We are now working on reestablishing cross-module inlining, by exporting the new information between compilation units.
On the memory profiling front, now that the compiler patch is well tested and quite stable, we started some cleanup to make it more modular, easier to understand and extend. We also worked on improving the performance of the profiler (the tool that analyzes the heap snapshots), by caching some expensive computations, such as extracting type information from 'cmt' files associated with each location, in files that are shared between executions. We have started testing the profiler on the Why3 verification platform, and these optimizations proved very useful to analyze longer traces.
On OPAM, we are still preparing the release of version 1.1. The release date has shifted a little bit -- it is now planned to happen mid-September, before the OCaml'2013 meeting -- because we are focusing on getting speed and stability improvements in a very good shape. We are now relying on opam-rt, our new regression testing infrastructure, to be sure to get the best level of quality for the release.
Regarding the package and compiler metadata, we are very proud to announce that our community has crossed an important line, with more than 100 contributors and 500 different packages ! In order to ensure that these hours of packaging efforts continue to benefit everyone in the OCaml community in the future, we are (i) clarifying the license for all the metadata in the package repository to use CC0 and (ii) discussing with OCamlLabs and the different stakeholders to migrate all the metadata to the ocaml.org infrastructure.
We also made progress on the design of our simple build-manager for OCaml, ocp-build. The next branch in the GIT repository features a new, much more expressive package description language : ocp-build can now be used to build arbitrary files, for example to generate new source files, or to compile files in other languages than OCaml. We successfully used the new language to build Try-ocaml and wxOCaml, completely avoiding the use of "make".
It can also automatically generate basic HTML documentation for libraries using ocamldoc with "ocp-build make -doc". There are still some improvements on our TODO list before an official release, for example improving the support of META files, but we are getting very close ! ocp-build is very efficient: compiling Merlin with ocp-build takes only 4s on a quad-core while ocamlbuild needs 13s in similar conditions and with the same parallelisation settings.
Try-OCaml has been improved with a dedicated implementation of the Graphics module: type "lesson 19", and you will get some fun examples, including a simple game by Sylvain Conchon.
We are also happy to welcome Mohamed Iguernelala in the team, starting at the beginning of September. Mohamed is a great OCaml programmer, and he will be working on the Alt-Ergo theorem prover, an SMT-solver in OCaml developed by Sylvain Conchon, and heavily used in the industry for safety-critical software (aircrafts, trains, etc.).
After thorough testing, the multi-runtime branch is getting stable enough for being submitted upstream. The build system has been fixed to enable the modified OCaml to run, in single-runtime mode, on architectures for which no multi-runtime port exists yet, while maintaining API compatibility with mainline OCaml. Thanks to some clever preprocessor hacks, the performance impact in single-runtime mode will be negligible.
Our work on whole program analysis, while still in the early stages, is quickly getting forward, and we managed to generate well-formed graphs representing a whole OCaml program. The tool can be fed sources and .cmt files, and at each point of the program, will compute all of the plausible values every variable can take, plus the calculations that allowed to get those values. We hope to have it ready for testing the detection of uncaught exceptions soon.
For the Richelieu project, after testing some type inference analysis on Scilab code in the last months, we have now started to implement a new tool, Scilint, to perform some of this analysis on whole Scilab projects and report warnings on suspect code. We hope this tool will soon be used by every Scilab user, to avoid wasting hours of computation before reaching an easy-to-catch error, such as a misspelled -- thus undefined -- variable.
Some of us are going to present part of this work at OCaml'2013, the OCaml Users and Developers Workshop in Boston. We expect it to be a good opportunity to get some feedback on these projects from the community!
Once again, here is the summary of our activities for last month. The highlight this month is the release of ocaml-top, an interactive editor for education which works well under Windows and that we hope professors all around the world will use to teach OCaml to their students. We are also continuying our work on the improvement of the performance of OCaml, with new inlining heuristics in the compiler and adding multicore support to the runtime.
Last month, we started to get very nice results with our compiler performance improvements. First, Pierre Chambart polished the prototype implementation of his new
flamba intermediate language and he started to get impressive micro-benchmarks results, with around 20% - 30% improvements on code using exceptions or functors. Following a discussion with our industrial users, he is currently focusing on improving the compilation of local recursive functions such as the very typical:
let f x y =
let rec loop v =
... x ...
loop z
loop x
A simple and reasonably efficient solutions is to eta-expand the auxiliary function, i.e. add an intermediate function calling the loop with all closure parameters passed as variables. The hard part is to then to add the right arguments to all the call sites: luckily enough the new inlining engine already does that kind of analysis so it can be re-used here. This means that these constructs will be compiled efficiently by the new inlining heuristics.
Second, Luca Saiu has finished debugging the native thread support on top of his multi-runtime variant of OCaml, which has become quite usable and is pretty robust now. He has tentatively started adding support for
vmthreads as well, concurrently cleaning up context finalization and solving other minor issues, such as configuration scripts for architectures that do not support the multi-runtime features yet. Then, after writing documentation and running a full pass over the sources to remove debugging stubs and prints which pollute the code after months of low-level experimentation, he is going to prepare patches for discussion and submission to the main OCaml compiler.
Çagdas Bozman continued to improve the implementation of his profiling tools for both native and byte-code programs. A great output of his recent work is that the location information is much more precise: with very different techniques for native and byte code, the program locations are now uniquely identified. The usability was improved as well, as the profiling location tables are now embedded directly into the programs. He also improved the post-mortem profiling tools to re-type dumped heaps, which also leads to much more accurate profiling information. Çagdas is now actively using these tools on why3 and he expects to get feedback results very soon to continue to improve his tools.
Finally, Thomas Blanc is still working on whole program analysis for his internship, in order to find possibly uncaught exceptions. The project is moving quite well and the month was spent on analyzing the lambda intermediate representation of the compilation step. With the help of Pierre Chambart, he is working on a 0-CFA library that should allow to compute the "possible" values for each variable at each point of the program. The idea is to make a directed hypergraph with each hyperedge representing an instruction and each vertex being a state of the program. Then search a fixpoint in the possible values propagated through the graph. This allows the compiler to know everywhere in the program what possible values may be returned or what possible exceptions may be raised. In order to create a well-designed graph, it is needed to create a new intermediate representation that looks like Lambda except (mainly) that every expression gets an identifier. The next step is to specify a hypergraph construction for each primitive and control-flow.
This month, Louis Gesbert has been busy making the first release of ocaml-top, the simple graphical top-level for beginners and students. Together with the web-IDE, this project aims at lowering the entry barrier to OCaml. Ocaml-top features a clean and easy to access interface, with nonetheless advanced features like automatic semantic indentation, error marking, and integrated display of standard library types -- using the engines of ocp-indent and ocp-index of course. The biggest challenge was probably to make everything work as expected on Microsoft Windows, which was required for most beginners and classrooms.
The two main issues were:
Setup the build environment: there are several versions of OCaml for Windows ; we generally want to avoid any dependency on cygwin on the generated program, but it's very hard to avoid any need for it in the build chain. The easiest solution at the moment is to "cross-compile" from cygwin using the mingw32 gcc compiler. The hard part is to get all the needed libraries properly setup: this felt a lot like Linux 15 years ago, you can find some binaries but generally not properly configured, and there is no consistent packaging system (or at least you can't find what you want in it).
Process management: ocaml-top runs the OCaml toplevel as a sub-process, so as not to be inpaired by any problem in the user program. Interacting with that process in a portable way is close to impossible, Windows having no POSIX signals, and read/write operations being very different in terms of blocking, etc. Some obscure C bindings were required to simulate a SIGINT that could tell the ocaml process to stop the current computation and return to the prompt. But at this cost, ocaml-top can be run with any existing external OCaml toplevel.
Not mentioning some gtk/lablgtk bugs that were often OS-specific. After having read horror stories about the most commonly used "Windows installer generator" NSIS, Louis opted for the Microsoft open source solution WiX which turned out to be quite clean and efficient, although using a lot of XML. The only point that might be in favor of NSIS is that it can generate the installer from Linux, so it's much convenient when you cross-compile, which is not the case here ; also worth mentioning, Xen and LVM are really great tools which do save a lot of time when working and testing between two (or more) different OSes.
Meanwhile, most of my time last month has been spent preparing the next release of OPAM, with the help of Louis Gesbert. This new release will contain a lot of bug-fixes and an improved
opam update mechanism: it will be much more flexible, faster and more stable than the one present in
1.0. Few months ago, I had already pushed a first batch of patches to the development version, which started to make things look much better. I decided last month to continue improving that feature and make it rock-solid: hence I have started a regression testing platform for OPAM which is still young but already damn useful to stabilize my new set of patches.
opam-rt is also written in OCaml: it generates random repositories with random packages, shuffles everything around and checks that OPAM correctly picks-up the changes. In the future this will make it easier to test complex OPAM scenarios and will hopefully lead to a better OPAM.
ocp-index has seen some progress, with lots of rough edges rounded, and much better performance on big
cmi files (typically module packs, like
We are proud to be well represented at the OCaml Developer Workshop 2013. This year it happens in Boston, in September, co-located with the Conference of Users of Functional Programming. Both conferences will contains a lot of OCaml-related talks: I am especially excited to hear about PHP type-inference efforts at Facebook using OCaml! If you are in the area around the 22/23 and 24 of September and you want to chat about OCamlPro and OCaml, we will be around!
As announced some time ago, I am working on a new intermediate language within the OCaml compiler to improve its inlining strategy. After some time of bug squashing, I prepared a testable version of the patchset, available either on Github (branch
flambda_experiments), or through OPAM, in the following repository:
opam repo add inlining https://github.com/OCamlPro/opam-compilers-repository.git
opam switch flambda
opam install inlining-benchs
The series of patches is not ready for benchmarking against real applications, as no cross module information is propagated yet (this is more practical for development because it simplifies debugging a lot), but it already works quite well on single-file code. Some very simple benchmark examples are available in the
inlining-benchs package.
The series of patches implements a set of 'reasonable' compilation passes, that do not try anything too complicated, but combined, generates quite efficient code.
As said in the previous post, I decided to design a new intermediate language to implement better inlining heuristics in the compiler. This intermediate language, called
flambda, lies between the
lambda code and the
Clambda code. It has an explicit representation of closures, making them easier to manipulate, and modules do not appear in it anymore (they have already been compiled to static structures).
I then started to implement new inlining heuristics as functions from the
lambda code to the
flambda code. The following features are already present:
intra function value analysis
variable rebinding
dead code elimination (which needs purity analysis)
known match / if branch elimination
In more detail, the chosen strategy is divided into two passes, which can be described by the following pseudo-code:
if function is at toplevel
then if applied to at least one constant OR small enough
then inline
else if applied to at least one constant AND small enough
then inline
if function is small enough
AND does not contain local function declarations
then inline
The first pass eliminates most functor applications and functions of the kind:
let iter f x =
let rec aux x = ... f ... in
aux x
The second pass eliminates the same kind of functions as Ocaml 4.01, but being after the first pass, it can also inline functions revealed by inlining functors.
I ran a few benchmarks to ensure that there were no obvious miscompilations (and there were, but they are now fixed). On benchmarks that were too carefully written there was not much gain, but I got interesting results on some examples: those illustrate quite well the improvements, and can be seen at
$(opam config var lib)/inlining-benchs (binaries at
$(opam congfig var bin)/bench-*).
Performance gains against OCaml 4.01 are around 20%. The main difference is that exceptions are compiled to constants, hence not allocated when raised. In that particular example, this halves the allocations.
In general, constant exceptions can be compiled to constants when predefined (
Failure, ...). They cannot yet when user defined: to improve this a few things need to be changed in
translcore.ml to annotate values created by exceptions.
Performance gains are around 30% against OCaml 4.01. This code uses a lot of higher order functions of the kind:
let map_triple f (a,b,c) = (f a, f b, f c)
OCaml 4.01 can inline
map_triple itself but then cannot inline the parameter
f. Moreover, when writing:
let (x,y,z) = map_triple f (1,2,3)
the tuples are not really used, and after inlining their allocations can be eliminated (thanks to rebinding and dead code elimination)
Performance gains are around 20% compared to OCaml 4.01. This example shows how inlining can help defunctorization: when inlining the
Set functor, the provided comparison function can be inlined in
Set.add, allowing direct calls everywhere.
A problem may arise in a rare case of recursive values where a field access can be considered to be a constant. Something that would look like (if it were allowed):
type 'a v = { v : 'a }
let rec a = { v = b }
and b = (a.v, a.v)
I have a few solutions, but not sure yet which one is best. This probably won't appear in any normal test. This bug manifests through a segmentation fault (
cmmgen fails to compile that recursive value reasonably).
The new passes assume that every identifier is declared only once in a given module, but this assumption can be broken on some rare pattern matching cases. I will have to dig through
matching.ml to add a substitution in these cases. (the only non hand-built occurence that I found is in
since there is no cross-module information at the moment, calls to functions from other modules are always slow.
In some rare cases, there could be functions with more values in their closure, thus resulting in more allocations.
I would now like to add back cross-module information, and after a bit of cleanup the first series of patches should be ready to propose upstream.
It is time to give a brief summary of our recent activities. As usual, our contributions were focused on three main objectives: (i) make the OCaml compiler faster and easier to use; (ii) make the OCaml developers more efficient by releasing new development tools and improving editor supports; and (iii) organize and participate to community events around the language. We are also welcoming four interns who will work with us on these objectives during the summer.
Following the ideas he announced in his recent blog post, Pierre Chambart has made some progress on his inlining branch. He is currently working on stabilizing and cleaning-up the code for optimization which does not take into account inter-module information.
We also continue to work on our profiling tool and start to separate the different parts of the project. We have patched the compiler and runtime, for both bytecode and native code, to generate (i)
.prof files which contain the id-loc information and allow us to recover the location from the identifiers in the header of the block; and (ii) to dump a program heap in a file on demand or to monitor a running program without memory and performance overhead. Çagdas Bozman has presented the work he has done so far regarding his PhD to members of the Bware project and we started to test our prototype on industrial use-cases using the why3 platform.
On the multi-core front, Luca Saiu is continuing his post-doc with Fabrice le Fessant and is modifying the OCaml runtime to support parallel programming on multi-core computers. Their version of the "multi-runtime" OCaml provides a message-passing abstraction in which a running OCaml program is "split" into independent OCaml programs, one per thread (if possible running on its separate core) with a separate instance of the runtime library in order to reduce resource contention both at the software and at the hardware level. Luca is now debugging the support for OCaml multi-threading running on top of a multi-context parallel program. A recent presentation covering this work and its challenges is available online.
A new intern from ENS Cachan, Thomas Blanc is working on a whole program analysis system. His internship's final goal is to provide a good hint of exceptions that may be left uncaught by the program, resulting a failure. It is quite interesting as exceptions are pretty much the part of the program "hard to foresee". The main difficulty comes from higher-order functions (like
List.iter). Because of them, a simple local analysis becomes impossible. So the first task is to take the whole program in the form of separated
.cmt files, merge it, and remove every higher-order functions (either by direct inlining if possible or by a very big pattern matching). The merging as already been done through a deep browsing of the compiler's typedtrees. Thomas is now focusing in reordering the code so that higher-order functions can be safely removed.
Finally, we are helping to prepare the release 4.01.0 of the OCaml compiler: Fabrice has integrated his frame-pointer patch, that can be used to profile the performance of OCaml applications using Linux
perf tool; he has added in
Pervasives two application operators that had been optimized before, but were only available for people who knew about that; he has also added a new environment variable,
OCAMLCOMPPARAM, that can be used to change how a program is compiled by
ocamlopt, without changing the build system (for example,
OCAMLCOMPPARAM='g=1' make can be used to compile a project in debug mode without modifying the makefiles).
Since the initial release of OPAM in March, we have been kept busy preparing the upcoming
1.1.0 version, which should interface nicely with the forthcoming set of automatic tools which will constitute the first version of the OCaml Platform that we are helping OCamlLabs to deliver. We have constantly been focused on fixing bugs and implementing feature requests (more than 70 issues have been closed on Github) and we have recently improved the speed and reliability of
opam update. More good news related to OPAM: The number of packages submitted to official repository is steadily increasing with around 20 new packages integrated every-months (and much more already existing package upgrades), and the official Debian package should land in testing very soon.
This month, Louis was still busy improving different tools for ocaml code edition.
ocp-index and
ocp-indent, made for the community to improve the general ocaml experience and kindly funded by Jane Street, have seen some updates:
ocp-index: the library data access tool which was first presented in April has seen some progress, with the ability to locate definitions and resolve type names. It is still not yet considered stable though, expect more from it soon. An early release (0.2.0) is in OPAM.
ocp-indent the generic ocaml source code indenter, has seen its usual bunch of fixes, along with some new customisation options. Also, its library interface has been rewritten, offering much better flexibility and opening the gate to uses like restarting from checkpoints to avoid full reparsing, detecting top-expression boundaries, syntax coloration, etc. We will be releasing 1.3.0 in OPAM very soon.
We are also developing in-house projects aiming at providing a better first experience of OCaml to beginners and students:
the new ocaml-top (previous project name
ocp-edit-simple) aims to offer a simple, but clean and easy-to-use interface to interact with the ocaml top-level. It is intended mainly for exercises, tutorials and practicals. A release should be coming soon, the Linux version being quite stable while some bugs remain on Windows.
two new interns, David and Pierrick, have started working on a web-IDE for OCaml. As students, they have seen sometimes how difficult it could be to install OCaml on some OSes, or simply configure editors like emacs or vim. To solve these issues, the idea is to use only a web browser-based editor and provide a way to compile a project without having to install anything on your computer. For the editing part, the idea is to use Ace and improve it for OCaml, using ocp-indent for example, which is possible by using js_of_ocaml. The next step will be to glue this editor with both TryOCaml to execute code, and a cloud computing part, to store projects and files and access them from anywhere.
We are also trying to improve cross-compilation tutorials and tools for developing native iOS application under a Linux system, using the OCaml language. Souhire, our fourth new intern, is experimenting with that idea and will document how to set up such an environment, from the foundation until the publication on the application store (if it is possible). She is starting to look at how iOS applications (with a native graphical interface) written in C can be cross-compiled on Linux, and how the ones written in OCaml can be cross-compiled on MacOSX.
On the library front, Fabrice has completely rewritten the way his wxOCaml library is generated, compared to what was described in a previous blog post. It does not share any code anymore with other wxWidgets bindings (wxHaskell or wxEiffel), but directly generates the stubs from a DSL (close to C++) describing the wxWidgets classes. It should make binding more widgets (classes) and more methods for each widget much easier, and also help for maintenance, evolution and compatibility with wxWidgets version. There are now an interesting set of samples in the library, covering many interesting usages.
We have also been pretty active during the last months to promote the use of OCaml in the free-software and research community: we are actively participating to the upcoming OCaml 2013 and Commercial User of Functional Programming conference which will be help next September in Boston.
While I was visiting Jane Street with OCamlLabs's team, I had the pleasure to be invited to give a talk at the NYC OCaml meetup on OPAM (my slides can be found online here). It was a nice meetup, with more than 20 people, hosted in the great Jane-Street New-York offices.
OCamlPro is still organizing OCaml meetups in Paris, hosted by IRILL and sponsored by LexiFi : our last Ocaml Users in PariS (OUPS) meetup was in May, there were more than 50 persons ! It was a nice collection of talks, where Esther Baruk spoke about the usage of OCaml at Lexifi, Benoit Vaugon about all the secrets that we always wanted to know about the OCaml bytecode, Frédéric Bour presents us Merlin, the new IDe for VIM, and Gabriel Scherer told us how to better interact with the OCaml core team.
We are now preparing our next OUPS meeting which will take place at IRILL on Tuesday, July 2nd. Emphasis will be on programming in OCaml in different context. Thus, there will be some js_of_ocaml experiences, GPGPU in OCaml and GADTs in practice. There is still many seats available, so do not hesitate to register to the meetup, but if you cannot, this time, videos of the talks (in French) will be available afterwards.
Not really related to OCaml, we also attend the Teratec 2013 Forum which brings together a lot of Scilab users. This is part of the Richelieu research project that Michael is working on: his goal is to analyze Scilab code, before just-in-time compilation. It requires a basic type-inference algorithm, but for a language that has not been designed for that ! He is currently struggling with the dynamic aspects of Scilab language. After some work on preprocessing
eval and
evalstr functions, he is now focusing on how Scilab programers usually write functions. He is currently using different kinds of analyses on real-world Scilab programs to understand how they are structured.
Finally, we are happy to announce that we finally found the time to release the sources of our OCaml cheat-sheets. Feel free to contribute by sending patches if you are interested to improve them!
Working at OCamlPro may have some drawbacks. I spend a lot of time hacking the OCaml compiler. Hence when I write some code, I have a good glimpse of what the generated assembly will look like. This is nice when I want to write performance sensitive code, but as I usually write code for which execution time doesn't matter much, this mainly tends to torture me. A small voice in my head is telling me "you shouldn't write it like that, you known you could avoid this allocation". And usually, following that indication would only tend to make the code less readable. But there is a solution to calm that voice: making the compiler smarter than me.
OCaml compilation mechanisms are quite predictable. There is no dark magic to replace your ugly code by a well-behaving one, but it always generates reasonably efficient code. This is a good thing in general, as you won't be surprised by code running more slowly than what you usually expect. But it does not behave very well with dumb code. This may not often seem like a problem with code written by humans, but generated code, for example coming from camlp4/ppx, or compiled from another language to OCaml, may fall into that category. In fact, there is another common source for non-human written code: inlining.
Inlining (or inline expansion) is a key optimisation in many compilers and particularly in functional languages. Inlining replaces a function call by the function body. Let's apply inlining to f in this example.
let f x = x + 1
let g y = f (f y)
We replace the calls to f by let for each arguments and then copy the body of f.
let g y =
let x1 = y in
let r1 = x1 + 1 in
let x2 = r1 in
let r2 = x2 + 1 in
Inlining allows to eliminate the cost of a call (and associated spilling), but the main point is elsewhere: it puts the code in its context, allowing its specialisation. When you look at that generated code after inlining your trained eyes will notice that it looks quite dumb. And you really want to rewrite it as:
let g y = y + 2
The problem is that OCaml is compiling smart code into smart assembly, but after inlining your code is not as smart as it used to be. What is missing in the current compiler is a way to get back a nice and smart code after inlining. (To be honest, OCaml is not that bad and on that example it would generate the right code: put this on the sake of the mandatory blog-post dramatic effect.)
In fact you could consider inlining as two separate things: duplication and call elimination. By duplication you make a new version of the function that is specialisable in its context, and by call elimination you replace the call by specialised code. This distinction is important because there are some cases where you only want to do duplication: recursive functions.
In a recursive function duplicating and removing a call is similar to loop unrolling. This can be effective in some cases, but this is not what we want to do in general. Lets try it on
let rec list_map f l = match l with
| [] -> []
| a::r -> f a :: list_map f r
let l' =
let succ = (fun x -> x + 1) in
list_map succ l
If we simply inline the body of list_map we obtain this
let l' =
let succ = (fun x -> x + 1) in
match l with
| [] -> []
| a::r -> succ a :: list_map succ r
And with some more inlining we get this which is probably not any faster than the original code.
let l' =
let succ = (fun x -> x + 1) in
match l with
| [] -> []
| a::r -> a + 1 :: list_map succ r
Instead we want the function to be duplicated.
let l' =
let succ = (fun x -> x + 1) in
let rec list_map' f l = match l with
| [] -> []
| a::r -> f a :: list_map' f r in
list_map' succ l
Now we know that
list_map' will never escape its context hence that its f parameter will always be succ. Hence we can replace
f by succ everywhere in its body.
let l' =
let succ = (fun x -> x + 1) in
let rec list_map' f l = match l with
| [] -> []
| a::r -> succ a :: list_map' succ r in
list_map' succ l
And we can now see that the
f parameter is not used anymore, we can eliminate it.
let l' =
let succ = (fun x -> x + 1) in
let rec list_map' l = match l with
| [] -> []
| a::r -> succ a :: list_map' r in
list_map' l
With some more inlining and cleaning we finally obtain this nicely specialised function which will be faster than the original.
let l' =
let rec list_map' l = match l with
| [] -> []
| a::r -> a + 1 :: list_map' r in
list_map' l
Inlining can gain a lot, but abusing it will increase code size a lot. This is not only a problem of binary size (who cares?): if your code does not fit in processor cache anymore, its speed will be limited by memory bandwidth.
To avoid that, OCaml has a threshold to the function size allowed for inlining. The compiler may also refuse to inline in other cases that are not completely justified though, mainly for reasons related to its architecture:
duplication and call elimination are not separated, hence recursive function duplication is not possible.
functions containing structured constants or local functions are not allowed to be duplicated, preventing those functions to be inlined.
let constant x =
let l = [1] in
let local_function x =
let g x = some closed function in
... g x ...
The assumption is that if a function contains a constant or a function it will be too big to be reasonably inlined. But there is a reasonable transformation that could allow it.
let l = [1]
let constant x =
let g x = some closed function
let local_function x = ... g x ...
and then we can reasonably inline
constant and
local_function. Those cases are only technical limitation that could easily be lifted with the new implementation.
But improving the OCaml inliner is not that easy. It is well written, but it is also doing a lot of other things at the same time:
closure conversion transforms functions to a data structure containing a code pointer and the free variables of the function. You could imagine it as that transformation:
let a = 1
let f x = x + a (* a is a free variable in f *)
let r = f 42
a is a free variable of
f. We cannot compile
f while it contains reference to free variables. To get rid of the free variables, we add a new parameter to the function, the environment, containing all the free variables.
let a = 1
let f x environment =
(* the new environment parameter contains all the free variables of f *)
x + environment.a
let f_closure = { code = f; environment = { a = a } }
let r = f_closure.code 42 f_closure.environment
In functional languages inlining is not as simple as it is for languages like C because the function name does not tells you which function is used at a call site:
let f x = (x,(fun y -> y+1))
let g x =
let (a,h) = f x in
h a
To be able to inline h as (fun y -> y+1) the compiler needs to track which values flows to variables. This is usually called a value analysis. This example can look a bit contrived, but in practice functor application generate quite similar code. This allows for instance to inline Set.Make(...).is_empty. The result of this value analysis is used by other optimisations:
When the value analysis can determine that the result of an operation is a constant, it can remove its computation:
let f x =
let a = 1 in
let b = a + 1 in
x + b
b always have the value
2 and
a + 1 does not have side effects it is possible to simplify it.
let f x =
x + 2
Sometimes it is impossible to know which function will be used at a call site:
let f g x = g x
There is a common representation (the closure) that allows to call a function without knowing anything about it. Using a function through its closure is called a generic call. This is efficient, but of course not as efficient as a simple assembly call (a direct call). The work of the direct call specialisation is to turn as many as possible generic call into direct ones. In practice, the vast majority of calls can be optimised.
The current architecture is very fast and works well on a lot of cases, but it is quite difficult to improve the handling of corner cases.
I have started a complete rewrite of those passes, I am currently working on splitting all those things in their own passes. The first step was to add a new intermediate representation (flambda) more suited to doing the various analysis. The main difference with the current representation (clambda) is that closures are explicitly represented, making them easier to manipulate. As a nice side effect this intermediate representation allows to plug passes in or out, or loop on them without changing anything to the architecture. But we are losing the possibility to enforce some invariants in the type of the representation, hence we need to be careful to correctly maintain them.
With this new architecture, the closure conversion is done first (going from lambda to flambda). Then on flambda are provided a set of simple analysis:
simple intraprocedural value and alias analysis
purity analysis
constant analysis
dead expression analysis
And there is a set of simple passes using their results:
dead code elimination
constant folding/direct call specialisation/type specialisation: a simple traversal replacing expressions with more efficient ones when the result of the value analysis allows it.
alias rebinding: Use results of alias analysis to know when a field access can be simplified:
let f x =
let tuple = (x,x) in
let (y,z) = tuple in
y + z
let f x =
x + x
Of course nobody would write that, but access to variables bounded in a closure can looks a lot like that after inlining:
let f x =
let g y = x + y in
g x
After closure conversion we obtain this.
let f x =
let g_closure =
{ code = fun x environment -> environment.x + y;
environment = { x = x } } in
g_closure.code x g_closure.environment
And after inlining
let f x =
let g_closure =
{ code = fun x environment -> environment.x + y;
environment = { x = x } } in
x + closure.environment.x
g makes some code that looks a bit stupid.
closure.environment.x is always the same value as
x. So there is no need to access it through the structure.
let f x =
let g_closure =
{ code = fun x environment -> environment.x + y;
environment = { x = x } } in
x + x
Now that we have simplified the code, we notice that g_closure is not used anymore, and dead code elimination can simply get rid of it.
let f x =
x + x
a really, really dumb inliner: it inlines almost anything. Its interest is to demonstrate what can be achieved when putting some code in its context.
After the different optimisation passes we need to send the result to the compiler back-end. This is done by the final conversion from flambda to clambda, which is mainly doing a lot of bureaucratic transformations and mark constant structured values. Doing this constant marking separately also allows to improve a bit the generated code.
let rec f x =
let g y = f y in
g x
f and
g are closed functions but the current compiler will not be able to detect it and allocate a closure for g at each call of f.
As you noticed that there were no fancy improvements charts, and there won't be any below. Those are demonstrations passes, the generated code can (and probably will) be worse than the one generated by the current compiler. This is mainly done to show what can be achieved by combining simple passes and simple analysis and allowing to apply them multiple times. What is needed to get fast code is to change the inlining heuristic (and re-enable cross module inlining).
My current work is to write more serious analysis allowing better optimisations. In particular I expect that a reasonable interprocedural value analysis could help a lot with handling recursive function specialisation.
Then I'd like to play a bit with other common things like
unused parameters elimination: when a function does not use one of its parameters, remove it. This is trivial with simple functions, but it can get a bit tricky with multiply recursive functions. (that kind of code can appear after constant folding with informations from interprocedural analysis )
lambda lifting: turning closure into closed function by adding arguments. This can eliminate some allocations
let f x =
let g y = x + y in
g 4
If we add the
x parameter to
g we can avoid building its closure each time
f is called.
let f x =
let g y x = x + y in
g 4 x
This can get quite tricky if we want to handle cases like
let f x n =
let g i = i + x in
Array.init n g
We need to add a new parameter to init also to be able to pass it to g.
common sub-expression elimination:
let f x =
let a = x + 1 in
let b = x + 1 in
a + b
f We clearly don't need to compute
x + 1 two times
let f x =
let a = x + 1 in
a + a
earlier unboxing: Floats are boxed in ocaml, this means that there is an indirection when accessing the constant of a value of type float. To reduce the cost of allocating and accessing floats unboxing eliminates the indirections between some operations. I'd like to try to do this as a flambda pass to be able to use the results of the value analysis.
If you want to play/hack a bit with the demo look at my github branch (be warned, this branch may sometimes be rebased)
This post aims at summarizing the activities of OCamlPro for the past month. As usual, we worked in three main areas: the OCaml toolchain, development tools for OCaml and R&D projects.
Our multi-runtime implementation of OCaml had gained stability. Luca fixed a lot of low-level bugs in the "master" branch of his OCaml repository, which were mainly related to the handling of signals. There are still some issues, which seem to be related to thread-switching (ie. when using OS level mutli-threading).
We made great progress on improved inlining strategy. In the current OCaml compiler, inlining, closure conversion and constant propagation are done in a single pass interleaved with analysis. It has served well until now, but to improve it in a way which is easily extensible in the future, it needs a complete rewrite. After a few prototypes, Pierre is now coming up with a suitable intermediate language (IR) more suited for the job, using a dedicated value analysis to guide the simplification and inlining passes. This IR will stand between the lambda code and the C-lambda and is designed such that future specialized optimization can be easily be added. There are two good reasons for this IR: First, it is not as intrusive and reduces the extent of the modifications to the compiler, as it can be plugged between two existing passes and turned on or off using a command-line flag. Second, it can be tweaked to make the abstract interpretation more precise and efficient. For instance, we want the inlining to work with higher-order functions as well as modules and functors, performing basic defunctorization. It is still in an experimentation phase, but we are quickly converging on the API and hope to have something we can demo in the next months.
Our frame-pointer patch has also been accepted. Note that, as this patch changes the calling sconvention of OCaml programs, you cannot link together libraries compiled with and without the patch. Hence, this option will be provided as a configuration switch (
./configure --with-frame-pointer).
Regarding memory profiling, we released a preliminary prototype of the memory profiler for native code. It is available in Çagdas repository. We are still in the process of testing and evaluating the prototype before making it widely available through OPAM. As the previous bytecode prototype, you need to compile the libraries and the program you want to profile as usual in order to build a table associating unique identifier to program locations (.prof file). Then, for each allocated block, we have then patched the runtime of OCaml to encode in the header the identifier of the line which allocated it. To be able to dump the heap, you can either instrument your program, or send a signal, or set the appropriate environment variable (
OCAMLRUNPARAM=m). Finally, you can use the profiler which will read the .prof and .cmt files in order to generate a pdf file which is the amount of memory use by type. More details on this will come soon, you can already read the README file available on github.
Finally, we organized a new meeting with the core-team to discuss some of the bugs in the OCaml bug tracker. It was the first of the year, but we are now going to have one every month, as it has a very positive impact on the involvement of everybody in fixing bugs and helps focus work on the most important issues.
Since the latest release of ocp-indent, Louis continued to improve the tool. We plan to release version 1.2.0 in the next couple of days, with some bug fixes (esp. related to the handling of records) and the following new features: operators are now aligned by default (as well as opened parentheses not finishing a line) and indentation can be bounded using the
max_indent parameter. We are also using the great cmdliner which means
ocp-indent now has nice manual pages.
We are also preparing a new minor release of OPAM, with a few bug fixes, an improved solver heuristic and improved performance. OPAM statistics seem to converge towards round numbers, as OcamlPro/opam repository has recently reached 100 "stars" on Github, OCamlPro/opam-repository is not very far from being forked 100 times, while the number of unique packages on opam.ocamlpro.com is almost 400. We are also preparing the platform release, with a cleaner and simpler client API to be used by the upcoming "Ocamlot", the automated infrastructure which will test and improve the quality and consistency of OPAM packages.
Last, we released a very small - but already incredibly useful tool: ocp-index. This new tool provides completion based on what is installed on your system, with type and documentation when available. Similarly to
ocp-indent, the main goal of this tool is to make it easy to integrate in your editor of choice. As a proof of concept, we also distribute a small curses-based tool, called
ocp-browser, which lets you browse interactively the libraries installed on your system, as well as an emacs binding for
auto-complete.el. Interestingly enough, behind the scene
ocp-index uses a lazy immutable prefix tree with merge operations to efficiently store and load cmis and cmt files.
We continued to work on the Richelieu project. We are currently adding basic type-inference for Scilab programs to our tool scilint, to be able to print warnings on possible programers mistakes. A first part of the work was to understand how to automatically get rid of some of the
eval constructs, especially
deff and
evalstr primitives that are often used. After this, Michael manually analyzed some real-world Scilab programs to understand how typing should be done, and he is now implementing the type checker and a table of types for primitive functions.
We are also submitting a new project, called SOCaml, for funding by the French government. In 2010, ANSSI, the French agency for the security of computer systems, commanded a study, called LAFOSEC, to understand the advantages of using functional languages in the domain of security. Early results of the study were presented in JFLA'2013, with in particular recommandations on how to improve OCaml to use it for security applications. The goal of the SOCaml project would be to implement these recommandations, to improve OCaml, to provide additional tools to detect potential errors and to implement libraries to verify marshaled values and bytecode. We hope the project will be accepted, as it opens a new application domain for OCaml, and would allow us to work on this topic with our partners in the project, such as LexiFi and Michel Mauny's team at ENSTA Paristech (the project would also contribute to their ocamlcc bytecode-to-c compiler).
Last week, I was bored doing some paperwork, so I decided to hack a little to relieve my mind...
Some time ago, at OCamlPro, we had discussed the fact that OCaml was lacking more GUI frameworks. Lablgtk is powerful, but I don't like it (and I expect that some other people in the OCaml community share my opinion) for several reasons:
LablGTK makes an extensive use of objects, labels and polymorphic variants. Although using these advanced features of OCaml can help expert OCaml developers, it makes LablGTK hard to use for beginners... and a good reason to have better GUIs is actually to attract beginners!
GTK does not look native under Windows and Mac OS X, giving an outdated feeling about interfaces written with it.
Now, the question was, which GUI framework to support for OCaml ? A long time ago, I had heard that wxWidgets (formerly wxWindows) had contributed to the popularity of Python at some point, and I remembered that there was a binding called wxCaml that had been started by SooHyoung Oh a few years ago. I had managed to compile it a two years ago, but not to make the examples work, so I decided it was worth another try.
wxCaml is based on wxHaskell, itself based on wxEiffel, a binding for wxWidgets done for the Eiffel programming language. Since wxWidgets is written in C++, and most high-level programming languages only support bindings to C functions, the wxEiffel developers wrote a first binding from C++ to C, called the ELJ library: for each class wxCLASS of wxWidgets, and for each method Method of that class, they wrote a function wxCLASS_Method, that takes the object as first argument, the other arguments of the method, and then call the method on the first argument, with the other arguments. For example, the code for the wxWindow looks a lot like that:
EWXWEXPORT(bool,wxWindow_Close)(wxWindow* self,bool _force)
return self->Close(_force);
From what I understood, they stopped maintaining this library, so the wxHaskell developers took the code and maintained it for wxHaskell. In wxHaskell, a few include files describe all these C functions. Then, they use a program 'wxc' that generates Haskell stubs for all these functions, in a class hierarchy.
In the first version of wxCaml, camlidl was used to generate OCaml stubs from these header files. The header files had to be modified a little, for two reasons:
They are actually not correct: some parts of these header files have not been updated to match the evolution of wxWidgets API. Some of the classes for which they describe stubs does not exist anymore. The tool used by wxHaskell filters out these classes, because their names are hardcoded in its code, but camlidl cannot.
camlidl needs to know more information than just what is written in C header files. It needs some attributes on types and arguments, like the fact that a char pointer is actually a string, or that a pointer argument to a function is used to return a value. See wxc_types.idl for macros to automate parts of this step.
camlidl was not used a lot, and not maintained for a long time, so there are some bugs in it. For example, the names of the arguments given in IDL header files can conflict with variables generated in C by camlidl (such as "_res") or with types of the caml C API (such as "value").
Since the version of wxCaml I downloaded used outdated versions of wxWidgets (wxWindows 2.4.2 when current version is wxWidgets 2.9) and wxHaskell (0.7 when current version is 0.11), I decided to upgrade wxCaml to the current versions. I copied the ELJ library and the header files from the GitHub repository of wxHaskell. Unfortunately, the corresponding wxWidgets version is 2.9.4, which is not yet officially distributed by mainstream Linux distributions, so I had to compile it also.
After the painful work of fixing the new header files for camlidl, I was able to run a few examples of wxCaml. But I was not completely satisfied with it:
To translate the relation of inheritance between classes for camlidl, wxCaml makes them equivalent, so that the child can be used where the ancestor can be used. Unfortunately, it means also that the ancestor can be used wherever the child would, and since most classes are descendant of wxObject, they can all be used in place of each other in the OCaml code !
A typed version of the interface had been started, but it was already making heavy use of objects, which I had decided to ban from the new version, as other advanced features of OCaml.
So, I decided to write a new typed interface, where each class would be translated into an abstract type, a module containing its methods as functions, and a few cast functions, from children to ancestors.
I wrote just what was needed to make two simple examples work (hello_world and two_panels, from wxWidgets tutorials), I was happy with the result:
But writting by hand the complete interface for all classes and methods would not be possible, so I decided it was time to write a tool for that task.
My first attempt at automating the generation of the typed interface failed because the basic tool I wrote didn't have enough information to correctly do the task: sometimes, methods would be inherited by a class from an ancestor, without noticing that the descendant had its own implementation of the method. Moreover, I didn't like the fact that camlidl would write all the stubs into a single file, and my tool into another file, making any small wxOCaml application links itself with these two huge modules and the complete ELJ library, even if it would use only a few of its classes.
As a consequence, I decided that the best spot to generate a modular and typed interface would be camlidl itself. I got a copy of its sources, and created a new module in it, using the symbolic IDL representation to generate the typed version, instead of the untyped version. The module would compute the hierarchy of classes, to be able to propagate statically methods from ancestors to children, and to generate cast functions from children to ancestors.
A first generated module, called WxClasses defines all the wxWidgets classes as abstract types:
type eLJDragDataObject
and eLJMessageParameters
and wxDocument
and wxFrameLayout
and wxMenu
and wxMenuBar
and wxProcess
and ...
Types started by "eLJ..." are classes defined in the ELJ library for wxWidgets classes where methods have to be defined to override basic behaviors.
For each wxWidget class, a specific module is created with:
the constructor function, usually called "wxnew"
the methods of the class, and the methods of the ancestors
the cast functions to ancestors
For example, for the WxFrame module, the tool generates this signature:
open WxClasses
external wxnew : (* constructor *)
wxWindow -> int -> wxString -> int -> int -> int -> int -> int
-> wxFrame
= "camlidl_wxc_idl_wxFrame_Create_bytecode"
... (* direct methods *)
external setToolBar : wxFrame -> wxToolBar -> unit
= "camlidl_wxc_idl_wxFrame_SetToolBar"
... (* inherited methods *)
external setToolTip : wxFrame -> wxString -> unit
= "camlidl_wxc_idl_wxWindow_SetToolTip"
(* string wrappers *)
val wxnew : wxWindow -> int -> string -> int -> int -> int -> int -> int -> wxFr
val setToolTip : wxFrame -> string -> unit
val ptrNULL : wxFrame (* a NULL pointer *)
external wxWindow : wxFrame -> wxWindow = "%identity" (* cast function *)
In this example, we can see that:
WxFrame first defines the constructor for wxFrame objects. The constructor is later refined, because the stub makes use of wxString arguments, for which the tool creates a wrapper to use OCaml strings instead (using WxString.createUTF8 before the stub and WxString.delete after the stub).
Stubs are then created for direct methods, i.e. functions corresponding to new methods of the class wxFrame. String wrappers are also produced if necessary.
Stubs are also created for inherited methods. Here, "setToolTip" is a method of the class wxWindow (thus, its stub name wxWindow_SetToolTip). Normally, this function is in the WxWindow module, and takes a wxWindow as first argument. But to avoid the need for a cast from wxFrame to wxWindow to use it, we define it again here, allowing a wxFrame directly as first argument.
The module also defines a ptrNULL value that can be used wherever a NULL pointer is expected instead of an object of the class.
Finally, functions like "wxWindow" are cast functions from children to ancestor, allowing to use a value of type wxFrame wherever a value of type wxWindow is expected.
All functions that could not be put in such files are gathered in a module WxMisc. Finally, the tool also generates a module WxWidgets containing a copy of all constructors with simpler names:
val wxFrame : wxWindow -> int -> string -> int -> int -> int -> int -> int -> wxFrame
val wxFontMapper : unit -> wxFontMapper
and functions to ignore the results of functions:
external ignore_wxFontMapper : wxFontMapper -> unit = "%ignore"
external ignore_wxFrame : wxFrame -> unit = "%ignore"
We expect wxOCaml applications to just start with "open WxWidgets" to get access to these constructors, to use functions prefixed by the class module names, and to use constants from the Wxdefs module.
Here is how the minimal application looks like:
open WxWidgets
let _ =
let onInit event =
let frame_id = wxID () in
let quit_id = wxID() in
let about_id = wxID() in
(* Create toplevel frame *)
let frame = wxFrame WxWindow.ptrNULL frame_id "Hello World"
50 50 450 350 Wxdefs.wxDEFAULT_FRAME_STYLE in
WxFrame.setStatusText frame "Welcome to wxWidgets!" 0;
(* Create a menu *)
let menuFile = wxMenu "" 0 in
WxMenu.append menuFile about_id "&About" "About the application" false;
WxMenu.appendSeparator menuFile;
WxMenu.append menuFile quit_id "E&xit" "Exit from the application" false;
(* Add the menu to the frame menubar *)
let menuBar = wxMenuBar 0 in
ignore_int (WxMenuBar.append menuBar menuFile "&File");
WxFrame.setMenuBar frame menuBar;
ignore_wxStatusBar (WxFrame.createStatusBar frame 1 0);
(* Handler for QUIT menu *)
WxFrame.connect frame quit_id Wxdefs.wxEVT_COMMAND_MENU_SELECTED
(fun _ -> exit 0);
(* Handler for ABOUT menu *)
WxFrame.connect frame about_id Wxdefs.wxEVT_COMMAND_MENU_SELECTED
(fun _ ->
ignore_int (
WxMisc.wxcMessageBox "wxWidgets Hello World example."
"About Hello World"
(Wxdefs.wxOK lor Wxdefs.wxICON_INFORMATION)
(WxFrame.wxWindow frame)
(* Display the frame *)
ignore_bool ( WxFrame.show frame );
ELJApp.setTopWindow (WxFrame.wxWindow frame)
WxMain.main onInit (* Main WxWidget loop starting the app *)
The current code can be downloaded from our repository on GitHub. It should work with wxWidgets 2.9.4, and the latest version of ocp-build (1.99-beta5).
Of course, as I never wrote an application with wxWidgets before, I could only write a few examples, so I would really appreciate any feedback given by beta testers, especially as there might be errors in the translation to IDL, that make important functions impossible to use, that I cannot detect by myself.
I am also particularly interested by feedback on the use of modules for classes, to see if the corresponding style is usable. Our current feeling is that it is more verbose than a purely object-oriented style, but it is simpler for beginners, and improves the readability of code.
Finally, it was a short two-day hack, so it is far from finished. Especially, after hacking wxCamlidl, and looking at the code of the ELJ library, I had the feeling that we could go directly from the C++ header files, or something equivalent, to produce not only the OCaml stubs and the typed interface, but also the C++ to C bindings, and get rid completely of the ELJ library.
Since our last activity report we have released the first stable versions of two projects: OPAM, an installation manager for OCaml source packages, and ocp-indent, an indentation tool.
We have already described the basics of OPAM in two precedent blog posts, so today we will focus on the release of
When you work on a very large code-base, it is crucial to keep a consistent indentation scheme. This is not only good for code review purposes (when the indentation carries semantic properties) but also when your code is starting to evolve and when the one who makes the change is not the one who wrote the initial piece of code. In the latter case, the variety of editors and local configurations usually leads to lot of small changes carrying no semantic value at all (such as changing tabs to spaces, adding few spaces at the beginning or end of lines, and so on). This semantic noise considerably decreases the efficiency of any code-review and change process and is usually very good at hiding hard-to-track bugs in your code-base.
A few months ago, the solutions for OCaml to this indentation problem were limited. For instance, you could write coding guidelines and hope that all the developers in your project would follow them. If you wanted to be more systematic, you could create and share a common configuration file for some popular editors (most OCaml developers use the emacs'
tuareg-mode or vim) but it is very hard to get consistent indentation result across multiple tools. Moreover, having to rely on a specific editor mode means that it is harder to fully automatize the indentation process, for instance when setting-up a VCS hook.
In order to overcome these pitfalls, Jane Street asked us to design a new external tool with the following high-level specification:
it should be easy to use inside and outside any editor;
it should understand the OCaml semantics and reflect it in the indentation;
it should be easy to maintain and to extend;
So we started to look at the OCaml tools' ecosystem and we found an early prototype of Jun Furuse's ocaml-indent. The foundation looked great but the result on real-world code sources was not as nice as it could be, so we decided to start from this base to build our new tool, that we called
ocp-indent. Today,
ocp-indent and
ocaml-indent do not have much code in common anymore, but the global architecture of the system remains the same.
An indentation engine may seem like a rather simple problem: given any line in the program, we want to compute its indentation level, based on the code structure.
It turns out to be much more difficult than that, mainly because indentation is only marginally semantic, and, worse, is a matter of taste and "proper layout". In short, it's not a problem that can be expressed concisely, because one really does want lots of specific cases handled "nicely", depending on the on-screen layout -- position of line breaks -- rather than the semantic structure.
Ocp-indent does contain lots of ad-hoc logic for such cases. To make things harder, the OCaml syntax is known to be difficult to handle, with a few ambiguities.
Ocp-indent processes code in a simple and efficient way:
We lex the input with a modified version of the OCaml lexer, to guarantee complete consistency with OCaml itself. The parser had to be modified to be more robust (ocaml fails on errors, the indentation tool should not) and to keep tokens like comments, quotations, and, in the latest version, some ocamldoc block delimiters.
Taking the token stream as input, we maintain a "block" stack that keeps informations like the kinds of blocks we have been through to get to the cursor position, the column and the indentation parameters. For instance, the "block" stack
[KBody KFfun; KLet; KBody KModule] corresponds to the position of
X in the following piece of (pseudo-) code:
module Foo = struct
let f = fun a -> X
Each token may look up the stack to find its starting counterpart (
in will look for
KLet, etc.), or disambiguate (
= will look for
KLet, stopping on opening tokens like
KBracket, and will be inserted as an operator if none is found). This is flexible enough to allow for "breaking" the stack when incorrect grammar is found. For example, the unclosed paren in
module let x = ( end should not break indent after the
end. Great care was taken in deciding what tokens should be able to remove from the stack in which conditions.
The stack can also be used to find a token that we want to align on, typically bars
| in a pattern-matching.
On every line break, the stack can be used to compute the indentation of the next line.
In the case of partial file indentation (typically, reindenting one line or a single block), on lines that shouldn't be reindented the stack is reversely updated to adapt to the current indentation.
The part where some abstraction can be put into the engine is the knowledge of the semantics, and more precisely of the scope of the operations. It's also in that case that the indenter can help you write, and not only read, your code. On that matter,
ocp-indent has a knowledge of the precedence of operators and constructs that is used to know how far to unwind the stack, and what to align on. For example, a
; will flush function applications and most operators.
It is that part that gives it the most edge over
tuareg, and avoids semantically incorrect indents. All infix operators are defined with a priority, a kind of indentation (indentation increment or alignment over the above concerned expression), and an indentation value (number of spaces to add). So for example most operators have a priority lower than function application, but not
., which yields correct results for:
let f =
+ z
Boolean operators like
&& and
|| are setup for alignment instead of indentation:
let r = a
|| b
&& c
|| d
Additionally, some special operators are wanted with a negative alignment in some cases. This is also handled in a generic way by the engine. In particular, this is the case for
; or
type t = A
let r = { f1 = x
; f2 = y
ocp-indent can be used on the command-line to reindent whole files (or part of them with
--lines), but the most common use of an indenter is from an editor. If you are lucky enough to be able to call OCaml code from your editor, you can use it directly as a library, but otherwise, the preferred way is to use the option
--numeric: instead of reprinting the file reindented, it will only output indentation levels, which you can then process from your editor (for instance, using
indent-line-to with emacs). That should be cheaper and will help preserve cursor position, etc.
Currently, a simple emacs binding working on either the ocaml or the tuareg mode is provided, together with a vim mode contributed by Raphaël Proust and David Powers.
We've built
ocp-indent based on a growing collection of unit-tests. If you find an indentation bug, feel free to send us a code snippet that we will incorporate into our test suite.
Our tests clearly show that the deep understanding that
ocp-indent has of the OCaml syntax makes it shines on specific cases. We are still discussing and evaluating the implementation of few corner-cases related, see for instance the currently failing tests.
We have also run some benchmarks on real code-bases and the result is quite conclusive:
ocp-indent is always better than tuareg! This is a very nice result as most of the existing source files are either indented manually or are following tuareg standards. But
ocp-indent is also orders of magnitude faster, which means you can integrate it seamlessly into any automatic process.
We have previously announced the beta-release of OPAM. After two intense months of work, we are now very proud to announce the first official release of OPAM!
This release fixes many bugs and adds few new features to the previously announced beta-release.
The most visible new feature, which should be useful for beginners with OCaml and OPAM, is an auto-configuration tool. This tool easily enables all the features of OPAM (auto-completion, fix the loading of scripts for the toplevel, opam-switch-eval alias, etc). This tool runs interactively on each
opam init invocation. If you don't like OPAM to change your configuration files, use
opam init --no-setup. If you trust the tool blindly, use
opam init --auto-setup.
opam init # Interactive setup
opam init --no-setup # No configuration change
opam init --auto-setup # Automatic setup
You can later change the setup by doing:
opam config setup --list # show your current setup
opam config setup --all # Enable all the features of OPAM
You can of course manually review and modifye the changes made b by editing your
~/.profile (or
~/.zshrc for zsh users),
~/.ocamlinit and the
~/.opam/opam-init/* init scripts.
Please report:
Bug reports and feature requests for the OPAM tool here.
Packaging issues or requests for a new package here.
General queries to the platform list.
More specific queries about the internals of OPAM to the OPAM devel list.
Packages for Debian and OSX (at least homebrew) should follow shortly and I'm looking for volunteers to create and maintain rpm packages. The binary installer is up-to-date for Linux and Darwin 64-bit architectures, the 32-bit version for Linux should arrive shortly.
If you want to build from sources, the full archive (including dependencies) is available at:
If you are upgrading from 0.9.* (eg. if you have at least installed the beta release announced in January) you won't have anything special to do apart installing the new binary. You can then update your package metadata by running
opam update. If you want to use the auto-setup feature, remove the "eval
opam config env line you have previously added in your
~/.profile and run
opam config setup --all.
So everything should be fine. But you never know ... so if something goes horribly wrong in the upgrade process (of if your are upgrading from an old version of OPAM) you can still trash your
~/.opam, manually remove what OPAM added in your
~/.profile (
~/.zshrc for zsh users) and
~/.ocamlinit, and start again from scratch.
The OPAM project on Github is very pleasantly active. We have got lot of contribution from a lot of different people, and I am very pleased to regularly discover new and interesting OCaml projects pushed to the OPAM repository. So thanks everybody for the great contributions!
We have worked hard to deliver OPAM and we are very delighted to get a warm welcome from the community. This give us a lot of motivation to continue improving OPAM!
https://github.com/OCamlPro/opam: +2000 commits, 26 contributors
https://github.com/OCamlPro/opam-repository: +1700 commits, 75 contributors, 370+ packages
+400 unique visitor per week, 15k
opam update per week
+1300 unique visitor per month, 55k
opam update per month
3815 unique visitor since the alpha release
The full change-log is available here
From the early days of OCamlPro, people have been curious about our plans; they were asking how we worked at OCamlPro and what we were doing exactly. Now that we have started releasing projects more regularly, these questions come again. They are very reasonable questions, and have resolved to be more public and communicate more regularly. This post covers our activities from the beginning of 2013 and updates are scheduled on a monthly basis.
OCamlPro has been created to promote the use of OCaml in the industry. In order to do so, we provide a wide range of services targeted at all stages of typical software projects: we train engineers and we improve the efficiency and usability of the OCaml compiler and tools, we help design new projects, advise on which open-source software components to use and how, we help deliver OCaml software projects and we do custom software development. One extra focus is the increase of the accessibility of OCaml for beginners and students.
Our customers are well-known industrial users such as Jane-Street, Citrix and Lexifi but we also help individual developers lost in the wild of non-OCaml environments inter-operate OCaml with other components. We also believe that collaborative R&D projects are a great opportunity to make existing companies discover OCaml and its benefits to their products and we are involved in several of them (see below).
Our engineering team is steadily growing (currently 9 full-time engineers in a joint lab between OCamlPro and INRIA) located in Paris and Nice. We gather a wide range of technical skills and industrial world expertise as we are all coming from major academic and industrial actors such as INRIA, Dassaut Systèmes, MLstate and Citrix. We also love the OCaml open-source ecosystem: we have been participating to the development of ocsigen, mirage, XCP, mldonkey, marionet and so on. By the way, OCamlPro has some open positions and we are still looking to hire excellent software engineers!
The first of our technical activities is related to work on the OCaml distribution itself. We are part of the OCaml compiler development team -- our INRIA members are part of the Gallium project which develops OCaml at INRIA -- and we regularly contribute patches to improve the usability and performance of the compiler itself.
We have recently proposed a series of patches to improve the performance of functions with float arguments and we have started developing a framework to benchmark the efficiency of compiler optimizations.
We are also actively exploring the design-space for concurrency and distribution in OCaml, with an implementation of (i) a reentrant runtime; (ii) a way to instantiate different runtimes in separate system threads in the same process, and (iii) an efficient multi-scale communication library, between threads and between processes. We call this multi-runtime OCaml and a prototype is available on github.
Last, we are also making progress with the memory profiling tools. We work on a modified OCaml runtime which can store the location of each allocated block in the heap, with hooks to dump that heap on demand. External tools can then use that dump to produce useful statistics about memory usage of the program. The good news is that we now have a working and usable bytecode runtime and an external tool that produces basic memory information. We are preparing an alpha release in the next month, so stay tuned!
Our efforts to make OCaml more usable go further than looking at the compiler. We are improving the development tools already existing in the community, such as the recently released indentation tool which was initially coming from an experiment from Jun Furuse, and creating new ones when the lack is blatant.
Most recent news on that front concern OPAM, the package manager for OCaml that we are developing since mid-2012. For people not familiar with it yet, OPAM is a source-based package manager for OCaml. It supports resolution of complex dependency constraints between packages, multiple simultaneous compiler installations, flexible package constraints, and a Git-friendly development workflow. The beta release was announced in January, and we expect the first official release to happen in the next weeks. The OCaml community has gratefully welcomed OPAM, and the repository of its package metadata has already become the most forked OCaml project on github! Interestingly, two meetups have gathered more than fifty OPAM users in Paris and Cambridge in January. We really hope this kind of meetup can be generalized: if you want to help us organize one in your area, feel free to contact us!
The other major part of our work around development tools for OCaml is TypeRex. TypeRex is a collection of tools which focus on improving developer efficiency, and lowering the entry barrier for experienced developers who are used to shiny IDEs in other languages. The first version of TypeRex, that was released last year, was a first step in this direction: it provided an enhanced emacs mode for OCaml code, with colorization, indentation, refactoring facilities, completion, code-navigation, documentation tooltips, etc. The next version of TypeRex (simply dubbed typerex2) is underway, with more independent tools (like ocp-indent), less tightly coupled to Emacs, and focused on better integration with various IDEs. If you are interested in following the progress of these tools, you can check the typerex2 OPAM packages with 1.99.X+beta version numbers, which we release on a regular basis.
The idea that OCaml is the right choice to create new innovative products is at the core of OCamlPro. We are very involved in the research community, especially on Functional Languages, with participation into the Program Committees of various conferences such as the OCaml User and Developer (OUD) workshop and the Commercial User of Functional Programming (CUFP) conference. We also joined two collaborative R&D projects in 2012, the Richelieu FUI and BWare ANR. As part of the Richelieu project, we are developing a JIT compiler for the Scilab language. As part of the Bware project, we improve the efficiency of automatic theorem provers, with a specific focus on Alt-Ergo, an SMT solver particularly suited to program verification. We are always interested in bringing our expertise in compiler technologies and knowledge of complex and distributed systems to new R&D projects: contact us if you are interested!
In the Richelieu project, our combined technical and theoretical expertise proved particularly effective. The research consortium is led by Scilab Entreprises which needed a safer and more efficient execution engine for Scilab in order to compete with Matlab. We joined the consortium to implement the early analysis required by the JIT compiler. The project started last December, and we have since specified the semantics of the language and implemented a working prototype of an interpreter that is already as fast as the current C++ engine of Scilab 6.
Our last important domain of activity is geared towards the OCaml community. It is important to us that the community grows bigger, and to achieve this goal there are some basic blocks that we need to help build, together with the other main actors of the community.
The first missing block is a good reference documentation. This year will end with (at least) one new important book for the language: Real-World OCaml which targets experienced software engineers who do not know OCaml yet. We collaborate with OCamlLabs to make the technical experience of this book a success. We also work to improve the general experience of using OCaml for complete beginners by creating a stable replacement to the broken ocamlwin, the simple editor distributed with OCaml on Windows.
It is also important to us that OCaml uses the web as a platform to attract new users, as is becoming the norm for modern programming languages. We are members of the ocaml.org building effort and have created tryocaml to let newcomers easily discover the language directly from their browser. TryOcaml has been welcomed as a great tool, already adopted and adapted: see for instance tryrtt or try ReactiveML. We are in the process of simplifying the integration with other compiler variants.
Last, but not least, we collaborate very closely with OCamlLabs to create the OCaml Plateform: a consistent set of libraries, thoroughly tested and integrated, with a rolling release schedule of 6 months. The platform will be based on OPAM and we are currently designing and prototyping a testing infrastructure to improve and guarantee the quality of packages.
OPAM is a source-based package manager for OCaml. It supports multiple simultaneous compiler installations, flexible package constraints, and a Git-friendly development workflow. I have recently announced the beta-release of OPAM on the caml-list, and this blog post introduces the basics to new OPAM users.
We have decided to start writing a brand new package manager for OCaml in the beginning of 2012, after looking at the state of affairs in the OCaml community and not being completely satisfied with the existing solutions, especially regarding the management of dependency constraints between packages. Existing technologies such as GODI, oasis, odb and ocamlbrew did contain lots of good ideas that we shamelessly stole but the final user-experience was not so great -- and we disagreed with some of the architectural choices, so it wasn't so easy to contribute to fix the existing flaws. Thus we started to discuss the specification of a new package manager with folks from Jane Street who decided to fund the project and from the Mancoosi project to integrate state-of-the-art dependency management technologies. We then hired an engineer to do the initial prototyping work -- and this effort finally gave birth to OPAM!
OPAM packages are already available for homebrew, macports and arch-linux. Debian and Ubuntu packages should be available quite soon. In any cases, you can either use a binary installer or simply install it from sources. To learn more about the installation process, read the installation instructions.
Once you've installed OPAM, you have to initialize it. OPAM will store all its state under
~/.opam, so if you want to reset your OPAM configuration, simply remove that directory and restart from scratch. OPAM can either use the compiler installed on your system or it can also install a fresh version of the compiler:
opam init # Use the system compiler
opam init --comp 4.00.1 # Use OCaml 4.00.1
OPAM will prompt you to add a shell script fragment to your
.profile. It is highly recommended to follow these instructions, as it let OPAM set-up correctly the environment variables it needs to compile and configure the packages.
OPAM user manual is integrated:
opam --help # Get help on OPAM itself
opam init --help # Get help on the init sub-command
Once OPAM is initialized, you can ask it to list the available packages, get package information and search for a given pattern in package descriptions:
opam list *foo* # list all the package containing 'foo' in their name
opam info foo # Give more information on the 'foo' package
opam search foo # search for the string 'foo' in all package descriptions
Once you've found a package you would like to install, just run the usual
install command.
opam install lwt # install lwt and its dependencies
opam remove lwt # remove lwt and its dependencies
Later on, you can check whether new packages are available and you can upgrade your package installation.
opam update # check if new packages are available
opam upgrade # upgrade your packages to the latest version
Casual users of OCaml won't need to know more about OPAM. Simply remind to update and upgrade OPAM regularly to keep your system up-to-date.
A new release of OCaml is available and you want to be able to use it. How to do this in OPAM ? This is as simple as:
opam update # pick-up the latest compiler descriptions
opam switch 4.00.2 # switch to the new 4.00.2 release
opam switch export --switch=system | opam switch import -y
The first line will get the latest package and compiler descriptions, and will tell you if new packages or new compilers are available. Supposing that 4.00.2 is now available, you can then
switch to that version using the second command. The last command imports all the packages installed by OPAM for the OCaml compiler installed on your system (if any).
You can also easily use the latest unstable version of OCaml if you want to give it a try:
opam switch 4.01.0dev+trunk # install trunk
opam switch reinstall 4.01.0dev+trunk # reinstall trunk
Reinstalling trunk means getting the latest changesets and recompiling the packages already installed for that compiler switch.
Sometimes, you want to let people use a new version of your software early. Or you are working in a company and expose internal libraries to your coworkers but you don't want them to be available to anybody using OPAM. How can you do that with OPAM? It's easy! You can set-up your own repository (see for instance xen-org's development packages) and add it to your OPAM configuration:
opam repository list # list the repositories available in your config
opam repository add xen-org git://github.com/xen-org/opam-repo-dev.git
opam repository list # new xen-org repository available
This will add the repository to your OPAM configuration and it will display the newly available packages. The next time you run
opam update OPAM will then scan for any change in the remote git repository.
Repositories can either be local (e.g. on your filesystem), remote (available through HTTP) and stored in git or darcs.
You want to try the latest version of a package which have not yet been released, or you have a patched version of a package than you want to try. How could you do it? OPAM has a
pin sub-command which let you do that easily:
opam pin lwt /local/path/
opam install lwt # install the version of lwt stored in /local/path
You can also use a given branch in a given git repository. For instance, if you want the library
re to be compiled with the code in the
experimental branch of its development repository you can do:
opam pin re git://github.com/ocaml/ocaml-re.git#experimental
opam install re
When building the packages, OPAM will use the path set-up with the pin command instead of using the upstream archives. Also, on the next update, OPAM will automatically check whether some changes happened and if the packages needs to be recompiled:
opam update lwt # check for changes in /local/path
opam update re # check for change in the remote git branch
opam upgrade lwt re # upgrade re and lwt if necessary
I've briefly explained some of the main features of OPAM. If you want to go further, I would advise to read the user and packager tutorials. If you really want to understand the internals of OPAM, you can also read the developer manual.
OCaml 4.00.0 has been released on July 27, 2012. For the first time, the new OCaml includes some of the work we have been doing during the last year. In this article, I will present our main contributions, mostly funded by Jane Street and Lexifi.
OCaml 4.00.0 has a new option
-bin-annot (undocumented, for now, as it is still being tested). This option tells the compiler to dump in binary format a compressed version of the typed tree (an abstract syntax tree with type annotations) to a file (with the
.cmt extension for implementation files, and
.cmti for interface files). This file can then be used by development tools to provide new features, based on the full knowledge of types in the sources. One of the first tools to use it is the new version of
ocamlspotter, by Jun Furuse.
This new option will probably make the old option
-annot obsolete (except, maybe, in specific contextes where you don't want to depend on the internal representation of the typedtree, for example when you are modifying this representation !). Generated files are much smaller than with the
-annot option, and much faster to write (during compilation) and to read (for analysis).
As requested on the bug tracker, we implemented a set of new options for
-all will print all the dependencies, i.e. not only on
.cmo and
.cmx files, but also on source files, and for
.o files. In this mode also, no proxying is performed: if there is no interface file, a bytecode dependency will still appear against the
.cmi file, and not against the
.cmo file as it would before;
-one-line will not break dependencies on several lines;
-sort will print the arguments of
ocamldep (filenames) in the order of dependencies, so that the following command should work when all source files are in the same directory:
ocamlopt -o my_program `ocamldep -sort *.ml *.mli`
OCaml tries to make the best use of available registers and stack space, and consequently, its layout on the stack is much different from the one of C functions. Also, function names are mangled to make them local to their module. As a consequence, debugging native code OCaml programs has long been a problem with previous versions of OCaml:, since the debugger cannot print correctly the backtrace of the stack, nor put breakpoints on OCaml functions.
In OCaml 4.00.0, we worked on a patch submitted on the bug tracker to improve the situation: x86 and amd64 backends now emit more debugging directives, such as the locations in the source corresponding to functions in the assembly (so that you can put breakpoints at function entry), and CFI directives, indicating the correct stack layout, for the debugger to correctly unwind the stack. These directives are part of the DWARF debugging standard.
Unfortunately, line by line stepping is not yet available, but here is an example of session that was not possible with previous versions:
let f x y = List.map ( (+) x ) y
let _ = f 3 [1;2;3;4]
$ ocamlopt -g toto.ml
$ gdb ./a.out
(gdb) b toto.ml:1
Breakpoint 1 at 0x4044f4: file toto.ml, line 1.
(gdb) run
Starting program: /home/lefessan/ocaml-4.00.0-example/a.out
Breakpoint 1, 0x00000000004044f4 in camlToto__f_1008 () at toto.ml:1
1 let f x y = List.map ( (+) x ) y
(gdb) bt
#0 0x00000000004044f4 in camlToto__f_1008 () at toto.ml:1
#1 0x000000000040456c in camlToto__entry () at toto.ml:2
#2 0x000000000040407d in caml_program ()
#3 0x0000000000415fe6 in caml_start_program ()
#4 0x00000000004164b5 in caml_main (argv=0x7fffffffe3f0) at startup.c:189
#5 0x0000000000408cdc in main (argc=<optimized out>, argv=<optimized out>)
at main.c:56
Few people know that partial applications with multiple arguments are not very efficient. For example, do you know how many closures are dynamically allocated in in the following example ?
let f x y z = x + y + z
let sum_list_offsets orig list = List.fold_left (f orig) 0 list
let sum = sum_list_offsets 10 [1;2;3]
Most programmers would reply one,
f orig, but that's not all (indeed,
f and
sum_list_offsets are allocated statically, not dynamically, as they have no free variables). Actually, three more closures are allocated, when
List.fold_left is executed on the list, one closure per element of the list.
The reason for this is that Ocaml has only two modes to execute functions: either all arguments are present, or just one argument. Prior to 4.00.0, when a function would enter the second mode (as
f in the previous example), then it would remain in that mode, meaning that the two other arguments would be passed one by one, creating a partial closure between them.
In 4.00.0, we implemented a simple optimization, so that whenever all the remaining expected arguments are passed at once, no partial closure is created and the function is immediatly called with all its arguments, leading to only one dynamic closure creation in the example.
It is sometimes convenient to use the pipe notation in OCaml programs, for example:
let (|>) x f = f x;;
let (@@) f x = f x;;
[1;2;3] |> List.map (fun x -> x + 2) |> List.map print_int;;
List.map print_int @@ List.map (fun x -> x + 1 ) @@ [1;2;3];;
However, such
|> and
@@ operators are currently not optimized: for example, the last line will be compiled as:
let f1 = List.map print_int;;
let f2 = List.map (fun x -> x + 1);;
let x = f2 [1;2;3;];;
f1 x;;
Which means that partial closures are allocated every time a function is executed with multiple arguments.
In OCaml 4.00.0, we optimized these operators by providing native operators, for which no partial closures are generated:
external (|>) : 'a -> ('a -> 'b) -> 'b = "%revapply";;
external ( @@ ) : ('a -> 'b) -> 'a -> 'b = "%apply"
Now, the previous example is equivalent to:
List.map print_int (List.map ( (+) 1 ) [1;2;3])
Of course, a lot of our contributions are not always as visible as the previous ones. We also spent a lot of time fixing small bugs. Although it doesn't sound very fun, fixing bugs in OCaml is also fun, because bugs are often challenging to understand, and even more challenging to remove without introducing new ones !
We have recently worked on modifying the OCaml system to be able to profile OCaml code on Linux amd64 systems, using the processor performance counters now supported by stable kernels. This page presents this work, funded by Jane Street.
The patch is provided for OCaml version 4.00.0. If you need it for 3.12.1, some more work is required, as we would need to backport some improvements that were already in the 4.00.0 code generator.
Here is an example of a session of profiling done using both Linux performance tools and a modified OCaml 4.00.0 system (the patch is available at the end of this article).
Linux performance tools are available as part of the Linux kernel (in the
linux-tools package on Debian/Ubuntu). Most of the tools are invoked through the
perf command, à la git. For example, we are going to check where the time is spent when calling the
ocamlopt.opt command:
perf record -g ./ocamlopt.opt -c -I utils -I parsing -I typing typing/*.ml
This command generates a file
perf.data in the current directory, containing all the events that were received during the execution of the command. These events contain the values of the performance counters in the amd64 processor, and the call-chain (backtrace) at the event.
We can inspect this file using the command:
perf report -g
The command displays:
Events: 3K cycles
+ 9.81% ocamlopt.opt ocamlopt.opt [.] compare_val
+ 8.85% ocamlopt.opt ocamlopt.opt [.] mark_slice
+ 7.75% ocamlopt.opt ocamlopt.opt [.] caml_page_table_lookup
+ 7.40% as as [.] 0x5812
+ 5.60% ocamlopt.opt [kernel.kallsyms] [k] 0xffffffff8103d0ca
+ 3.91% ocamlopt.opt ocamlopt.opt [.] sweep_slice
+ 3.18% ocamlopt.opt ocamlopt.opt [.] caml_oldify_one
+ 3.14% ocamlopt.opt ocamlopt.opt [.] caml_fl_allocate
+ 2.84% as [kernel.kallsyms] [k] 0xffffffff81317467
+ 1.99% ocamlopt.opt ocamlopt.opt [.] caml_c_call
+ 1.99% ocamlopt.opt ocamlopt.opt [.] caml_compare
+ 1.75% ocamlopt.opt ocamlopt.opt [.] camlSet__mem_1148
+ 1.62% ocamlopt.opt ocamlopt.opt [.] caml_oldify_mopup
+ 1.58% ocamlopt.opt ocamlopt.opt [.] camlSet__bal_1053
+ 1.46% ocamlopt.opt ocamlopt.opt [.] camlSet__add_1073
+ 1.37% ocamlopt.opt libc-2.15.so [.] 0x15cbd0
+ 1.37% ocamlopt.opt ocamlopt.opt [.] camlInterf__compare_1009
+ 1.33% ocamlopt.opt ocamlopt.opt [.] caml_apply2
+ 1.09% ocamlopt.opt ocamlopt.opt [.] caml_modify
+ 1.07% sh [kernel.kallsyms] [k] 0xffffffffa07e16fd
+ 1.07% as libc-2.15.so [.] 0x97a61
+ 0.94% ocamlopt.opt ocamlopt.opt [.] caml_alloc_shr
Using the arrow keys and the
Enter key to expand an item, we can get a better idea of where most of the time is spent:
Events: 3K cycles
- 9.81% ocamlopt.opt ocamlopt.opt [.] compare_val ◆
- compare_val ▒
- 71.68% camlSet__mem_1148 ▒
+ 98.01% camlInterf__add_interf_1121 ▒
+ 1.99% camlInterf__add_pref_1158 ▒
- 21.48% camlSet__add_1073 ▒
- camlSet__add_1073 ▒
+ 93.41% camlSet__add_1073 ▒
+ 6.59% camlInterf__add_interf_1121 ▒
+ 1.44% camlReloadgen__fun_1386 ▒
+ 1.43% camlClosure__close_approx_var_1373 ▒
+ 1.43% camlSwitch__opt_count_1239 ▒
+ 1.34% camlTbl__add_1050 ▒
+ 1.20% camlEnv__find_1408 ▒
+ 8.85% ocamlopt.opt ocamlopt.opt [.] mark_slice ▒
- 7.75% ocamlopt.opt ocamlopt.opt [.] caml_page_table_lookup ▒
- caml_page_table_lookup ▒
+ 50.03% camlBtype__set_commu_1704 ▒
+ 49.97% camlCtype__expand_head_1923 ▒
+ 7.40% as as [.] 0x5812 ▒
+ 5.60% ocamlopt.opt [kernel.kallsyms] [k] 0xffffffff8103d0ca ▒
+ 3.91% ocamlopt.opt ocamlopt.opt [.] sweep_slice ▒
Press '?' for help on key bindings
We notice that a lot of time is spent in the
compare_val primitive, called from the
Pervasives.compare function, itself called from the
Set module in
asmcomp/interp.ml. We can locate the corresponding code at the beginning of the file:
module IntPairSet =
Set.Make(struct type t = int * int let compare = compare end)
Let's replace the polymorphic function
compare by a monomorphic function, optimized for pairs of small ints:
module IntPairSet =
Set.Make(struct type t = int * int
let compare (a1,b1) (a2,b2) =
if a1 = a2 then b1 - b2 else a1 - a2
We can now compare the speed of the two versions:
peerocaml:~/ocaml-4.00.0% time ./ocamlopt.old -c -I utils -I parsing -I typing typing/*.ml
./ocamlopt.old 7.38s user 0.56s system 97% cpu 8.106 total
peerocaml:~/ocaml-4.00.0% time ./ocamlopt.new -c -I utils -I parsing -I typing typing/*.ml
./ocamlopt.new 6.16s user 0.50s system 97% cpu 6.827 total
And we get an interesting speedup ! Now, we can iterate the process, check where most of the time is spent in the new version, optimize the critical path and so on.
A modified OCaml system is required because, for each event, the Linux kernel must attach a backtrace of the stack (call-chain). However, the kernel is not able to use standard DWARF debugging information, and current OCaml stack frames are too complex to be unwinded without this DWARF information. Instead, we had to modify OCaml code generator to follow the same conventions as C for frame pointers, i.e. using saving the frame pointer on function entry and restoring it on function exit. This required to decrease the number of available registers from 13 to 12, using
%rbp as the frame pointer, leading to an average 3-5% slowdown in execution time.
The patch for OCaml 4.00.0 is available here:
omit-frame-pointer-4.00.0.patch (20 kB, v2, updated 2012/08/13)
To use it, you can use the following recipe, that will compile and install the patched version in ~/ocaml-4.00-with-fp.
~% wget http://caml.inria.fr/pub/distrib/ocaml-4.00.0/ocaml-4.00.0.tar.gz
~% tar zxf ~/ocaml-4.00.0.tar.gz
~% cd ocaml-4.00.0
~/ocaml-4.00.0% wget www.ocamlpro.com/files/omit-frame-pointer-4.00.0.patch
~/ocaml-4.00.0% patch -p1 < omit-frame-pointer-4.00.0.patch
~/ocaml-4.00.0% ./configure --prefix ~/ocaml-4.00-with-fp
~/ocaml-4.00.0% make world opt opt.opt install
~/ocaml-4.00.0% cd ~
~% export PATH=$HOME/ocaml-4.00.0-with-fp/bin:$PATH
It is important to know that the patch modifies OCaml calling convention, meaning that ALL THE MODULES AND LIBRARIES in your application must be recompiled with this version.
On our benchmarks, the slowdown induced by the patch is between 3 and 5%. You can still compile your application without frame pointers, for production, using a new option
-fomit-frame-pointer that was added by the patch.
This patch has been submitted for inclusion in OCaml. You can follow its status and contribute to the discussion here:
We have recently worked on modifying the OCaml system to be able to pack a set of modules within a functor, parameterized on some signatures. This page presents this work, funded by Jane Street.
All the patches on this page are provided for OCaml version 3.12.1.
The patch for OCaml 3.12.1 is available here:
ocaml+libfunctor-3.12.1.patch.gz (26 kB)
To use it, you can use the following recipe, that will compile and install the patched version in ~/ocaml+libfunctor-3.12.1/bin/.
~% wget http://caml.inria.fr/pub/distrib/ocaml-3.12/ocaml-3.12.1.tar.gz
~% tar zxf ~/ocaml-3.12.1.tar.gz
~% cd ocaml-3.12.1
~/ocaml-3.12.1% wget www.ocamlpro.com/code/ocaml+libfunctor-3.12.1.patch.gz
~/ocaml-3.12.1% gzip -d ocaml+libfunctor-3.12.1.patch.gz
~/ocaml-3.12.1% patch -p1 < ocaml+libfunctor-3.12.1.patch
~/ocaml-3.12.1% ./configure --prefix ~/ocaml+libfunctor-3.12.1
~/ocaml-3.12.1% make coldstart
~/ocaml-3.12.1% make ocamlc ocamllex ocamltools
~/ocaml-3.12.1% make library-cross
~/ocaml-3.12.1% make bootstrap
~/ocaml-3.12.1% make all opt opt.opt
~/ocaml-3.12.1% make install
~/ocaml-3.12.1% cd ~
~% export PATH=$HOME/ocaml+libfunctor-3.12.1/bin:$PATH
Note that it needs to bootstrap the compiler, as the format of object files is not compatible with the one of ocaml-3.12.1.
Now that you are equiped with the new system, you can start using it. The lib-functor patch adds two new options to the compilers ocamlc and ocamlopt:
-functor <interface_file> : this option is used to specify that the current module is compiled with the interface files specifying the argument of the functor. This option should be used together with -for-pack <module>, where <module> is the name of the module in which the current module will be embedded.
-pack-functor <module> : this option is used to pack the modules. It should be used with the option -o <object_file> to specify in which module it should be embedded. The <module> specified with -pack-functor specifies the name of functor that will be created in the target object file.
If the interface
x.mli contains :
type t
val compare : t -> t -> int
and the files
xset.ml and
xmap.ml contain respectively :
(* xset.ml *)
module T = Set.Make(X)
(* xmap.ml *)
module T = Map.Make(X)
Then :
~/test% ocamlopt -c -for-pack Xx -functor x.cmi xset.ml
~/test% ocamlopt -c -for-pack Xx -functor x.cmi xmap.ml
~/test% ocamlopt -pack-functor MakeSetAndMap -o xx.cmx xset.cmx xmap.cmx
will construct a compiled unit whose signature is (that you can get with
ocamlopt -i xx.cmi, see below) :
module MakeSetAndMap :
functor (X : sig type t val compare : t -> t -> int end) ->
module Xset :
module T :
type elt = X.t
type t = Set.Make(X).t
val empty : t
val is_empty : t -> bool
module Xmap :
module T :
type key = X.t
type 'a t = 'a Map.Make(X).t
val empty : 'a t
val is_empty : 'a t -> bool
OCaml only allows you to print the interface of a module or interface by compiling its source with the -i option. However, you don't always have the source of an object interface (in particular, if it was generated by packing), and you might still want to do it.
In such a case, the lib-functor patch allows you to do that, by using the -i option on an interface object file:
~/test% cat > a.mli
val x : int
~/test% ocamlc -c -i a.mli
val x : int
~/test% ocamlc -c -i a.cmi
val x : int
OCaml only allows you to pack object files inside another object file (.cmo or .cmx). When doing so, you can either provide an source interface (.mli) that you need to compile to provide the corresponding object interface (.cmi), or the object interface will be automatically generated by exporting all the sub-modules within the packed module.
However, sometimes, you would want to be able to specify the interfaces of each module separately, so that:
you can reuse most of the interfaces you already specified
you can use a different interface for a module, that the one used to compile the other modules. This happens when you want to export more values to the other internal sub-modules than you want to export to the user.
In such a case, the lib-functor patch allows you to do that, by using the -pack option on interface object files:
test% cat > a.mli
val x : int
test% cat > b.mli
val y : string
test% ocamlc -c a.mli b.mli
test% ocamlc -pack -o c.cmi a.cmi b.cmi
test% ocamlc -i c.cmi
module A : sig val x : int end
module B : sig val y : string end
Download the source file from:
ocp-pack-1.0.1.tar.gz (20 kB, GPL Licence, Copyright OCamlPro SAS)
Then, you just need to compile it with:
~% tar zxf ocp-pack-1.0.1.tar.gz
~% cd ocp-pack-1.0.1
~/ocp-pack-1.0.1% make
~/ocp-pack-1.0.1% make install
ocp-pack can be used to pack source files of modules within just one source file. It allows you to avoid the use of the -pack option, that is not always supported by all ocaml tools (for example, ocamldoc). Moreover, ocp-pack tries to provide the correct locations to the compiler, so errors are not reported within the generated source file, but within the original source files.
It supports the following options:
% ocp-pack -help
ocp-pack -o target.ml [options] files.ml*
-o <filename.ml> generate filename filename.ml
-rec use recursive modules
all .ml files must have a corresponding .mli file
-pack-functor <modname> create functor with name <modname>
-functor <filename.mli> use filename as an argument for functor
-mli output the .mli file too
.ml files without .mli file will not export any value
-no-ml do not output the .ml file
-with-ns use directory structure to create a hierarchy of modules
-v increment verbosity
--version display version information
ocp-pack automatically detects interface sources and implementation sources. When only the interface source is available, it is assumed that it is a type-only module, i.e. no val items are present inside.
Here is an example of using ocp-pack to build the ocamlgraph package:
test% ocp-pack -o graph.ml \
lib/bitv.ml lib/heap.ml lib/unionfind.ml \
src/sig.mli src/dot_ast.mli src/sig_pack.mli \
src/version.ml src/util.ml src/blocks.ml \
src/persistent.ml src/imperative.ml src/delaunay.ml \
src/builder.ml src/classic.ml src/rand.ml src/oper.ml \
src/path.ml src/traverse.ml src/coloring.ml src/topological.ml \
src/components.ml src/kruskal.ml src/flow.ml src/graphviz.ml \
src/gml.ml src/dot_parser.ml src/dot_lexer.ml src/dot.ml \
src/pack.ml src/gmap.ml src/minsep.ml src/cliquetree.ml \
src/mcs_m.ml src/md.ml src/strat.ml
test% ocamlc -c graph.ml
test% ocamlopt -c graph.ml
The -with-ns option can be used to automatically build a hierarchy of modules. With that option, sub-directories are seen as sub-modules. For example, packing a/x.ml, a/y.ml and b/z.ml will give a result like:
module A = struct
module X = struct ... end
module Y = struct ... end
module B = struct
module Z = struct ... end
The -pack-functor and -functor options provide the same behavior as the same options with the lib-functor patch. The only difference is that -functor takes the interface source as argument, not the interface object.
When trying to pack modules with ocp-pack, you might discover that your toplevel modules have recursive dependencies. This is usually achieved by types declared abstract in the interfaces, but depending on each other in the implementations. Such modules cannot simply packed by ocp-pack.
To handle them, ocp-pack provides a -rec option. With that option, modules are put within a module rec construct, and are all required to be accompagnied by an interface source file.
Moreover, in many cases, OCaml is not able to compile such recursive modules:
For typing reasons: recursive modules are typed in an environment containing only an approximation of other recursive modules signatures
For code generation reasons: recursive modules can be reordered depending on their shape, and this reordering can generate an order that is actually not safe, leading to an exception at runtime
To solve these two issues in most cases, you can use the following patch (you can apply it using the same recipe as for lib-functor, and even apply both patches on the same sources):
With this patch, recursive modules are typed in an environment that is enriched progressively with the final types of the modules as soon as they become available. Also, during code generation, a topological order is computed on the recursive modules, and the subset of modules that can be initialized using in that topological order are immediatly generated, leaving only the other modules to be reordered.
Recently, I have been experimenting wiht OCaml / MSVC running on Windows 7 64bit. I have mainly followed what the OCaml's README.win32 was saying and I learned some NSIS tricks. The result of this experiment is the following two (rather big) windows binaries :
ocaml-trunk-64-installer.exe (92 MB)
ocaml-3.12-64-installer.exe (92 MB)
These binaries are auto-installer for :
the OCaml distribution (either the 3.12.1+rc1 version or trunk);
Emacs (version 23.3) + tuareg mode (version 2.0.4);
OCamlGraph (version 1.7) : this is just a little experiment with packaging external libraries.
Hopefully, all of this might be useful to some people, at least to people looking for an alternative to WinOcaml which seems to be broken. You should need no other dependencies if you just want to use the OCaml top-level (ocaml.exe). If you want to compile your project you will need MSVC installed and correctly set-up. If your project is using Makefiles then you should probably install cygwin as well. I can give more details if some people are interested.
Unfortunately, the current process for creating these binaries involves an awlful lot of manual steps (including switching for Windows Termninal to cygwin shell) and further, many OCaml packages won't install directly on windows (as most of them are using shell tricks to be configured correctly). I hope we will be able to release something cleaner in a later stage.
When you are beginning in a new programming language, it is sometimes helpful to have an overview of the documentation, that you can pin on your wall and easily have a look at it while you are programming. Since we couldn't find such Cheat Sheets, we decided to start writting our own cheat sheets for OCaml.
Beware, these documents are drafts, that we plan to improve in the next months. In the meantime, feel free to tell us how we could improve them, what is missing, and where the focus should be !
The OCaml Language (June 8, 2011)
OCaml Standard Tools (June 7, 2011)
OCaml Standard Library (June 7, 2011)
OCaml Emacs Mode (Tuareg) (June 27, 2011)
Archive: ocaml-3.11.2-longval-byte-i686.tar.bz2
You will need OCaml 3.11.2 installed on a i686 linux computer. The archive contains:
The Makefile has two targets:
sudo make install will save /usr/bin/ocamlrun and /usr/lib/ocaml/libcamlrun.a in the current directory and replace them with the longval binaries.
sudo make restore will restore the saved files.
If your install directories are not the default ones, you should modify the Makefile. After installing, you can test it with the standard OCaml top-level:
# ocaml
Objective Caml version 3.11.2
# let s = ref "";;
val s : string ref = {contents = ""}
# s := String.create 20_000_000;;
- : unit = ()
Now you can enjoy big values in all your strings and arrays in bytecode. You will need to relink all your custom binaries. If you are interested in the native version of the longval compiler, you can contact us.