Previous week Up Next week


Here is the latest Caml Weekly News, for the week of November 11 to 18, 2008.

  1. BDD reloaded
  2. Parametrizing ocamlyacc
  3. dypgen vs menhir
  4. Windows cross-compiler
  5. O'Browser : OCaml on browsers

BDD reloaded


Pietro Abate said:
I've done my homework and I've collected few links about bdd
libraries. I still have few questions: 

+ Is there a native (and efficient) ocaml BDD implementation ? In
 particular, as pointed out on this mailing list, with variable ordering
 and other possible optimizations that can be compared in speed with
 buddy/cudd (c/c++).

= From what I can see, the answer is no. A lot of toy implementations

+ Do you know if there is an ocaml binding for buddy ? 

= I guess no, but I hope I'm wrong...

+ Does anybody have experience with the bindings done at inrialpes to
 CUDD ? Is this project still actively maintained / used ? How does it
 compare efficiency-wise with other bdd libraries ?

+ If I was to start writing my ocaml bindings, which c/c++ library would
 you advice ? Buddy seems widely used, but I wasn't able to find any
 hard evidence that it is the best bdd library available... Do you know 
 of any paper surveying different bdd implementations ?

thanks :)

----------------------------- My links for reference ----------------

Please add to the list if you know of other libraries that I forgot to
mention. This might end up to be a FAQ...

==Ocaml libraries (bindings and native in no particular order) :==

* Jean-Christophe Filliâtre (ocaml implementation) Paper Code

* bindings to the CUDD BDD library Code

* Olivier Michel (ocaml implementation) Code

* Xavier Leroy (part of an experimental sat solver) Code

* John Harrison Code

* Ocaml implementation (who is the author ?) Wiki

==C/C++ Libraries==

* Buddy

* Old version of Buddy 


* many other cited in the wikipedia link on bdds

==Relevant Mailing list Messages==

The ocaml ml has several references to BDDs. These are 3 interesting threads
that I've used as a starting point for my research. 

In this thread
there is mention of a possible binding for Jørn Lind-Nielsen's BDD
library BuDDy. I'm wondering if this binding was ever released.

In this thread
Alain Frish points out that none of existing ocaml libraries implements
automatic reordering of variables... And I don't know if the state of affairs
is changed at this regard.

In this thread
David Mentre announces a preliminary work on binding for the cudd
library, but the link is broken... this link currently is broken: 
and there is a mention to a caml-light implementation of a robdd library
that I was also not able to retrieve.

Parametrizing ocamlyacc


Andrej Bauer asked and François Pottier answered:
> I have the following situation: 
> - a signature S 
> - two modules A and B, which both implement S 
> - an ocamlyacc file which refers to an implementation of S 
> I want to generate two executable, one where A is used and another 
> where B is used. 
> The most logical thing would be to turn the ocamlyacc part into a 
> functor which accepts an implementation of S. But there does not seem 
> to be any way of doing this. What can I do? 
> Can menhir do this?

Yes, Menhir has a keyword (%parameter) that allows precisely this.

dypgen vs menhir


Christophe Raffalli said:
Here is what I mostly like (you have a comparison table here

dypgen :

- GLR instead of LR(1) : this gives much more elegant description of the
  grammar (and the possibiliy of ambigous grammar) and there is never a
  conflict. These are replaced by multiple parse trees (you can choose a merge
  function that will report that as an error, if you think your grammar should
  not be ambiguous).

- pattern matching in rule. Example: you define a grammar for list of
  expressions of any-size, but you can restrict the usage to list of length at
  least 1, 2, ... by pattern matching)

- late reject of a rule by raising an exception.

- self extensible lexer and parser with delimited scope.

menhir :

- should be faster because it is only LR(1), but I did not test

- you know for sure that your grammer is not ambiguous ...

Windows cross-compiler


Richard Jones announced:
Here is a Linux -> Win32 OCaml cross-compiler, developed and sponsored
by Red Hat's Fedora MinGW project[1].  Red Hat are sponsoring this
project so that we can build our OCaml virt tools for Windows without
the hassle of using Windows.
 (There is no direct link - to get the latest version you have
 to click "manifest" then "ocaml").

If you're not familiar with RPM builds, then start with the .spec file
and the patches.  Pay close attention to the 'BuildRequires' which are
the parts of the MinGW project you will need to build it - in
particular, we use a version of FlexDLL which we have modified for

It's probably best to say what does work, because the list of what
_doesn't_ work is quite long.  But with this you get:

      The cross-compiler replacement for ocamlopt
         (bytecode so you need a corresponding
          ocamlrun interpreter to use it)

 *.cmx, *.cmxa
      The usual OCaml stdlib libraries, eg. nums, dynlink, unix, threads
         (only lightly tested)


 $ cat /tmp/

 open Printf

 let () =
   printf "reported os_type = %S\n" Sys.os_type;
   printf "ok\n"

 $ boot/ocamlrun i686-pc-mingw32-ocamlopt -verbose -I stdlib /tmp/ \
   -o /tmp/test.exe
 + i686-pc-mingw32-as -o '/tmp/test.o' '/tmp/camlasm56b36c.s'
 + i686-pc-mingw32-as -o '/tmp/camlstartup4b26a5.o' '/tmp/camlstartup76cf6d.s'
 + flexlink -chain mingw -exe -o '/tmp/test.exe'  -I'/usr/lib64/i686-pc-mingw32-ocaml' '-Lstdlib' '-L/usr/lib64/i686-pc-mingw32-ocaml' '/tmp/camlstartup4b26a5.o' 'stdlib/std_exit.o' '/tmp/test.o' 'stdlib/stdlib.a' 'stdlib/libasmrun.a'  

 $ file /tmp/test.exe 
 /tmp/test.exe: PE32 executable for MS Windows (console) Intel 80386 32-bit

 $ wine /tmp/test.exe
 reported os_type = "Win32"

There are about a million things to fix, but this should be enough to
get people started.



O'Browser : OCaml on browsers


Benjamin Canou announced:
O'Browser is an implementation of the OCaml virtual machine in JavaScript,
designed to run in web browsers.
It features a runtime library compatible with OCaml's standard one (including
OOP and concurrent threads) and bindings of some JavaScript functions to
manipulate the DOM primitives.

The distribution is available at [1] and an online version of the tutorial is
reachable at [2].

Please note that this is an early version, in particular the DOM interface
module is neither pretty nor well typed.
However, it can already be used to create little applets or scripts (as in the
tutorial [2], the examples of the distribution [3] or my webpage [4]) and
we'll be glad to receive your comments or bug reports.

Have fun.

Benjamin Canou.


Using folding to read the cwn in vim 6+

Here is a quick trick to help you read this CWN if you are viewing it using vim (version 6 or greater).

:set foldmethod=expr
:set foldexpr=getline(v:lnum)=~'^=\\{78}$'?'<1':1

If you know of a better way, please let me know.

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