Hello
Here is the latest OCaml Weekly News, for the week of September 23 to 30, 2014.
Archive: https://sympa.inria.fr/sympa/arc/caml-list/2014-09/msg00239.html
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
https://github.com/ocaml-batteries-team/batteries-included/releases/tag/v2.3.0
or from the sources
https://github.com/ocaml-batteries-team/batteries-included
The online API documentation is at:
http://ocaml-batteries-team.github.io/batteries-included/hdoc2/
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
list`
(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
versions)
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)
Archive: https://sympa.inria.fr/sympa/arc/caml-list/2014-09/msg00243.html
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.
## calc_prio.ml ##############################################################
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
parser
| f:RE(float_re) -> float_of_string f
let prod_sym =
parser
| CHR('*') -> ( *. )
| CHR('/') -> ( /. )
let sum_sym =
parser
| CHR('+') -> ( +. )
| CHR('-') -> ( -. )
let _ = set_expr (fun prio ->
parser
| 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:
http://lama.univ-savoie.fr/decap/
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: http://lama.univ-savoie.fr/mantis
Archive: https://sympa.inria.fr/sympa/arc/caml-list/2014-09/msg00244.html
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 List.map
function.
By seeing the source code of OCaml's List module, it seems that map
function
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 List.map like this?
Malcolm Matalka replied:
https://blogs.janestreet.com/optimizing-list-map/
And from the horse's mouth:
https://groups.google.com/forum/#!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:
https://github.com/janestreet/core_kernel/blob/release-112.01.00/lib/core_list.ml#L380
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:
http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html
> 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.
> List.map f [a1; ...; an] applies function f to a1, ..., an, and
builds the list [f a1; ...; f an] with the results returned by f. Not
tail-recursive.
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
http://batteries.forge.ocamlcore.org/ ) which directly extend the
compiler library, and are therefore usable as a drop-in replacement
for it, some others (such as Core
https://ocaml.janestreet.com/ocaml-core/111.28.00/doc/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 `List.map f li` with
`List.rev_map f (List.rev li)` if you know `li` may be long.)
Thanks to Alp Mestan, we now include in the OCaml Weekly News the links to the
recent posts from the ocamlcore planet blog at http://planet.ocaml.org/.
What is gained and lost with 63-bit integers?:
https://blogs.janestreet.com/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:
http://jobs.github.com/positions/0a9333c4-71da-11e0-9ac7-692793c00b45
Eighth OCaml compiler hacking evening (at Mill Lane, by the river):
http://ocamllabs.github.com/compiler-hacking/2014/09/23/compiler-hacking-by-the-river.html
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.