Previous week Up Next week


Here is the latest OCaml Weekly News, for the week of September 23 to 30, 2014.

  1. batteries 2.3.0 -- with support for OCaml 4.02.0
  2. Alpha release of DeCaP (combinator library + extensible OCaml parser)
  3. Why does not be implemented tail-recursively?
  4. Other OCaml News

batteries 2.3.0 -- with support for OCaml 4.02.0


Gabriel Scherer announced:
Batteries (OCaml Batteries Included) is a community-developed overlay
over the "standard" library distributed with the compiler, that aims
to provide general-purpose data-structures and convenient functions.

The project follows a semantic versioning scheme; the new version is
backward-compatible with the previous releases (2.2.0 was in January
2014). The lowest OCaml version certainly supported is 3.12.

The new release is available in OPAM, or as a tarball
or from the sources
The online API documentation is at:

The main novelty of this new version is the support for the new OCaml
version 4.02. Whenever possible, we have backported new functions from
the 4.02 compiler library: using Batteries 2.3.0 will let you use them
from any OCaml version. You can thus write code using the new 4.2.0
functions that compiles on old OCaml versions. The only exception is
the support for inspecting the callstack, which is not available on
older OCaml versions -- it depends on an OCaml runtime change.

In particular, all new functions related to the new `bytes` datatype
are usable with Batteries 2.3.0, even from older OCaml
versions. However, the new Batteries release does *not* itself compile
with -safe-string (the new OCaml option to make strings immutable). We
plan to release another minor version soon that is -safe-string
ready. You can use Batteries 2.3.0 in user programs compiled with
-safe-string themselves, but you should expect compilation under
-safe-string to break at the next Batteries release, as some
interfaces change from `string` to `bytes`.

With many thanks to the contributors to this new release, including
François Berenger, Vincent Bernardoff, Simon Cruanes, Jacques-Pascal
Deplaix, Mads Hartmann, Max Mouratov, Gabriel Radanne, Xavier Van de
Woestyne, Ralf Vogler and Christopher Zimmermann.

# Detailed changelog

- improved test coverage
(Simon Cruanes and Xavier Van de Woestyne)
- Enum: bugfix in `clamp`
(Simon Cruanes)
- Stream: add `concat_map`
(Gabriel Radanne)
- List: fix a stack-overflow bug in `transpose`
(Gabriel Scherer)
- List: add `unfold_exc : (unit -> a) -> 'a list * exn`
(François Berenger)
- List: add `fold_righti` and `fold_lefti`
(François Berenger)
- Substring : fix `fold_left`, add `fold_lefti`, `fold_righti`
(Xavier Van de Woestyne)
- String : add `fold_lefti` and `fold_righti`
(Xavier Van de Woestyne)
- Set.Make: add `of_list`
(Jacques-Pascal Deplaix)
- AvlTree: add `check : 'a tree -> bool` to check well-formedness
(Simon Cruanes)
- Hashtbl: make `modify_opt/def` resize the table to preserve
amortized costs
(Mads Hartmann, report by user 'jj-issuu')
- Enum: fix combine's count in presence of infinite enums
(Gabriel Scherer, report by user 'mwnx')
- Makefile: add a qtest-byte target
(Gabriel Scherer)
- List: add `modify_opt_at: int -> ('a -> 'a option) -> 'a list -> 'a
(Gabriel Scherer)
- List: add `modify_at: int -> ('a -> 'a) -> 'a list -> 'a list`
(Gabriel Scherer)
- List: add `remove_at: int -> 'a list -> 'a list`
(François Berenger)
- Int: add `copysign`
(Simon Cruanes)
- Deque: add `rotate_forward`, `rotate_backward : 'a dq -> 'a dq`
(Max Mouratov)
- Int: fix overflow checking in `Safe_int.mul`
(Max Mouratov, Christopher Zimmermann)
- add a local OPAM description
(Vincent Bernardoff)
- Queue: add `map : ('a -> 'b) -> 'a t -> 'b t`
(Christopher Zimmermann)
- compatibility with 4.02:
+ Printf: remove CamlinternalPr for OCaml versions >= 4.02
(Ralf Vogler)
+ Printf: legacy code assumed (string = fmt)
(Gabriel Scherer)
+ new 4.02 functions:
String.mapi (String.init was already in Batteries)
List.sort_uniq (List.sort_unique existed before)
Array.make_float (less efficient implementation provided for <4.02
a BatBytes module relying on ocamlfind's compatibility module
bytes-related functions in Buffer,Digest,Marshal,Printexc,Stream,Unix
new Printexc callstack interface (not available for <4.02 versions)
(Gabriel Scherer)

Alpha release of DeCaP (combinator library + extensible OCaml parser)


Christophe Raffalli announced:
We are proud to announce the release of a new parser combinator library called
DeCaP. It has been used to implement a new extensible parser for OCaml called
pa_ocaml, together with a syntax extension for writing parsers using a format
similar to Backus-Naur Form (BNF). Through this syntax extension, parsers are
compiled down to calls of DeCaP combinators. In this way, we manage to obtain
a user-friendly syntax for writing parsers, while preserving the advantages of
functional combinators. To give you an idea, we give bellow the example of a
small calculator.

## ##############################################################
open Decap

type calc_prio = Sum | Prod | Atom
let expr, set_expr = grammar_family "expr" 

let float_num =
  let float_re = "[0-9]+\\([.][0-9]+\\)?\\([eE][-+]?[0-9]+\\)?" in
  | f:RE(float_re) -> float_of_string f

let prod_sym =
  | CHR('*') -> ( *. )
  | CHR('/') -> ( /. )

let sum_sym =
  | CHR('+') -> ( +. )
  | CHR('-') -> ( -. )

let _ = set_expr (fun prio ->
  | f:float_num                    when prio = Atom -> f
  | CHR('(') e:(expr Sum) CHR(')') when prio = Atom -> e
  | CHR('-') e:(expr Atom)         when prio = Atom -> -. e
  | CHR('+') e:(expr Atom)         when prio = Atom -> e
  | e:(expr Atom) l:{fn:prod_sym e':(expr Atom)}*
                                   when prio = Prod ->
      List.fold_left (fun acc (fn, e') -> fn acc e') e l
  | e:(expr Prod) l:{fn:sum_sym  e':(expr Prod)}*
                                   when prio = Sum  ->
      List.fold_left (fun acc (fn, e') -> fn acc e') e l)

(* The main loop *)
let _ =
  let blank = blank_regexp (Str.regexp "[ \t]*") in
  try while true do
    Printf.printf ">> %!";
    let l = input_line stdin in
    let r = handle_exception (parse_string (expr Sum) blank) l in
    Printf.printf "%f\n%!" r
  done with End_of_file -> ()

The tools to write syntax extensions are similar to those of Camlp4 (quotation
and anti-quotation) but are not complete yet (quotation patterns are missing).
The corresponding part of the documentation is also unfinished.

On the side of performances, pa_ocaml is on average five times slower than the
original OCaml parser (implemented using Ocamlyacc) and two times faster than
Camlp4. The web-page of the project can be found here:

As DeCaP and pa_ocaml are still under development, we would greatly
appreciate feedback. We are particularly interested in bug in the
OCaml parser. At the moment, the grammar is supposed to be complete
from OCaml 3.12.1 to 4.01.0 while some of the extension of 4.02.0 are
missing. Our target is to produce identical parse trees compare to
those of the original ocamlyacc parser. On our test files, this is
achieved up to positions and we are working on positions currently.

Bug report on mantis:

Why does not be implemented tail-recursively?


Shuai Wang asked:
I am working on some stack_overflow exception in our recent project
written in OCaml
and eventually it turns out that this exception is thrown by

By seeing the source code of OCaml's List module, it seems that map
does not be implemented tail-recursively: 

let rec map f = function
    [] -> []
  | a::l -> let r = f a in r :: map f l

So my question is: 

Why would OCaml's implementation like this? 
Malcolm Matalka replied:

And from the horse's mouth:!msg/fa.caml/YaLYqkpn928/1jdo8a0K6AEJ
Yaron Minsky then added:
Indeed, the implementation from that post did make it into
Core_kernel.  Here's the link:
Gabriel Scherer replied to the initial question:
The compiler library chose to keep it's implementation simple and
clean, at the cost of not being tail-recursive, and therefore
unsuitable for large lists. This is documented in the manual:

> Some functions are flagged as not tail-recursive. A tail-recursive
function uses constant stack space, while a non-tail-recursive
function uses stack space proportional to the length of its list
argument, which can be a problem with very long lists.

> f [a1; ...; an] applies function f to a1, ..., an, and
builds the list [f a1; ...; f an] with the results returned by f. Not

Other libraries have made different design choices, so you can easily
use a different List module that provides tail-recursive operations.
There are several larger libraries, some (such as Batteries ) which directly extend the
compiler library, and are therefore usable as a drop-in replacement
for it, some others (such as Core ) which
use different conventions. They all provide tail-recursive mapping
functions suitable for use on long lists.

(Of course you can also simply replace ` f li` with
`List.rev_map f (List.rev li)` if you know `li` may be long.)

Other OCaml News

From the ocamlcore planet blog:
Thanks to Alp Mestan, we now include in the OCaml Weekly News the links to the
recent posts from the ocamlcore planet blog at

What is gained and lost with 63-bit integers?:

Full Time: Software Developer (Functional Programming) at Jane Street in New York, NY; London, UK; Hong Kong:

Eighth OCaml compiler hacking evening (at Mill Lane, by the river):

Old cwn

If you happen to miss a CWN, you can send me a message and I'll mail it to you, or go take a look at the archive or the RSS feed of the archives.

If you also wish to receive it every week by mail, you may subscribe online.

Alan Schmitt