Hello
Here is the latest Caml Weekly News, for the week of November 11 to 18, 2008.
Archive: http://groups.google.com/group/fa.caml/browse_thread/thread/e60bdd5aa7207048#
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 though... + 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 :) p ----------------------------- 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) http://www.lri.fr/~filliatr/ftp/publis/hash-consing2.ps.gz Paper http://www.lri.fr/~filliatr/ftp/ocaml/bdd/ Code * bindings to the CUDD BDD library http://www.inrialpes.fr/pop-art/people/bjeannet/mlxxxidl-forge/ Code * Olivier Michel (ocaml implementation) http://www.ibisc.univ-evry.fr/~michel/BDD/ Code * Xavier Leroy (part of an experimental sat solver) https://gforge.inria.fr/plugins/scmsvn/viewcvs.php/attic/xlsat/?root=sodiac Code * John Harrison http://www.cl.cam.ac.uk/~jrh13/atp/OCaml/bdd.ml Code * Ocaml implementation (who is the author ?) http://oops.tepkom.ru/projects/ocamlbdd/ Wiki ==C/C++ Libraries== * http://buddy.wiki.sourceforge.net/ Buddy * http://vlsicad.eecs.umich.edu/BK/Slots/cache/www.itu.dk/research/buddy/index.html Old version of Buddy * http://vlsi.colorado.edu/~fabio/CUDD/cuddIntro.html CUDD * 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 http://caml.inria.fr/pub/ml-archives/caml-list/2000/01/405b651014b09c51c691aab72d69166a.en.html 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 http://groups.google.com/group/fa.caml/browse_frm/thread/4af5391f52279e38/550b7df324ae1900#550b7df324ae1900 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 http://caml.inria.fr/pub/ml-archives/caml-list/2001/04/8bbf7629ef3ef299c16f78bd2b986e36.en.html David Mentre announces a preliminary work on binding for the cudd library, but the link is broken... this link currently is broken: http://www-rocq.inria.fr/~mentre/software/ocaml-bdd/ and there is a mention to a caml-light implementation of a robdd library that I was also not able to retrieve.
Archive: http://groups.google.com/group/fa.caml/browse_thread/thread/2b4312187d690796#
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.
Archive: http://groups.google.com/group/fa.caml/browse_thread/thread/eaa6d0d88018b21f#
Christophe Raffalli said:Here is what I mostly like (you have a comparison table here http://www.lama.univ-savoie.fr/~raffalli/ocaml-parsing.html: 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 ...
Archive: http://groups.google.com/group/fa.caml/browse_thread/thread/346ccf5d690a1f68#
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.
http://hg.et.redhat.com/misc/fedora-mingw--devel/
(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
cross-compilation.
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:
i686-pc-mingw32-ocamlopt
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)
eg:
$ cat /tmp/test.ml
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/test.ml \
-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"
ok
There are about a million things to fix, but this should be enough to
get people started.
Rich.
[1] https://fedoraproject.org/wiki/MinGW
Archive: http://groups.google.com/group/fa.caml/browse_thread/thread/0d089365ca982195#
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. [1] http://www.pps.jussieu.fr/~canou/obrowser-0.1.tar.bz2 [2] http://www.pps.jussieu.fr/~canou/obrowser/tutorial [3] http://www.pps.jussieu.fr/~canou/obrowser/examples.html [4] http://www.pps.jussieu.fr/~canou/
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
zM
If you know of a better way, please let me know.
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.