[cwn] Attn: Development Editor, Latest Caml Weekly News
Alan Schmitt
alan.schmitt at polytechnique.org
Tue Nov 18 00:24:43 PST 2008
Hello,
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
========================================================================
1) BDD reloaded
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.
========================================================================
2) Parametrizing ocamlyacc
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.
========================================================================
3) dypgen vs menhir
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 ...
========================================================================
4) Windows cross-compiler
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>
========================================================================
5) O'Browser : OCaml on browsers
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/>
========================================================================
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
zM
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
(alan.schmitt at polytechnique.org) and I'll mail it to you, or go take a
look at
the archive (<http://alan.petitepomme.net/cwn/>) or the RSS feed of the
archives (<http://alan.petitepomme.net/cwn/cwn.rss>). If you also wish
to receive it every week by mail, you may subscribe online at
<http://lists.idyll.org/listinfo/caml-news-weekly/> .
========================================================================
--
Alan Schmitt <http://alan.petitepomme.net/>
The hacker: someone who figured things out and made something cool
happen.
.O.
..O
OOO
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.idyll.org/pipermail/caml-news-weekly/attachments/20081118/ea3ca7c2/attachment-0001.htm
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 186 bytes
Desc: This is a digitally signed message part
Url : http://lists.idyll.org/pipermail/caml-news-weekly/attachments/20081118/ea3ca7c2/attachment-0001.pgp
More information about the caml-news-weekly
mailing list