Hello
Here is the latest Caml Weekly News, for the week of May 22 to June 05, 2007.
Sorry for last week, I was away for a week with no internet access.
I have built the source and binary (i386) RPMs of OCaml 3.10.0 for Red Hat Enterprise Linux 4 and 5 and for Fedora 2-6. See http://rpm.nogin.org/ocaml.html for the listing of the RPMs. All packages are signed with my GPG key; the public key is available at http://rpmbin.nogin.org/GPG-PUBKEY.txt You can also download the latest RPMs of OCaml and OMake via yum/up2date - just point your client to the appropriate URL from the following list: http://rpmbin.nogin.org/MetaPRL/fedora-6/ http://rpmbin.nogin.org/MetaPRL/fedora-5/ http://rpmbin.nogin.org/MetaPRL/fedora-4/ http://rpmbin.nogin.org/MetaPRL/fedora-3/ http://rpmbin.nogin.org/MetaPRL/fedora-2/ http://rpmbin.nogin.org/MetaPRL/RHEL-5/ http://rpmbin.nogin.org/MetaPRL/RHEL-4/ A sample /etc/yum.repos.d/Nogin.repo for RHEL5 (i386) is attached below. (see the archive link for the file)
About six months ago, I sent a mail to this list asking for ideas and suggestions regarding teaching OCaml. Well, the term is over, except for a few students who're going to get a second chance at their exams, so I guess now is the time for a bottom line. All in all, I consider this a success. In the following mails, I'll detail the successes and problems me and my students have met during the term. = Program of the term = * Lectures (available in French from my webpage). * Short exercices during lab courses (also available on my page). * Short homework (also available on my page). * Term-long project on a subject selected by the students. -- Pacman (complete success) -- RSA Cryptography(success, despite ugly code) -- Connect 4 (mostly success) -- Sliding puzzle (complete failure) -- Sudoku (complete failure) -- Another Sudoku (mostly success) -- File explorer (half-success). * Day-long project on Othello/Reversi. I wrote the complete software, gave them only the .mli and a pseudo-Makefile and 10 hours to reimplement the modules of their choice. -- Rules (complete success) -- Graphics-based UI (complete failure) -- LablTk-based UI (mostly failure) -- AI (mostly failure) -- Board management (complete success) -- Utilities (complete success) -- Main program (complete success).
A number of things went well, sometimes impressively. * A number of students seem to get the hang of functional programming (programming without side effects, returning closures, functions as first-class citizens, recursive loops...) * Modules seem generally rather well understood. * The students enjoyed Graphics immensely. * When asking students to write a specific function, it's much easier to show examples with OCaml than with, say, Java. Consequently, exercices are generally better understood. * Some of the students have started answering some mathematical questions with OCaml programs. * One of my students did manage to write a function with type 'a -> 'b without using Obj or Marshal. Others managed to explain me (almost) correctly why this shouldn't be possible. * The students seem to have understood exceptions, as well as file management. Two things they just couldn't do at all in Java. * Most students seem to have no problems using references when they need them. * I believe that students actually understand better Java now that they have seen something a bit more abstract. Plus they had much more fun. * #trace is good. Very good.
Third and (probably) last part of my Teaching bottomline. I hope some of you find this useful. Let's start by problems I didn't cause. = Not my fault = == Environment == * OCamlWinPlus, in its current incarnation, is just awful. To improve it, one would need to fix the bugx, make it possible to remember the list of modules loaded, link it to the documentation, etc. * Camelia IDE is simple and good but difficult to install, as it requires Cygwin. It lacks project management, though -- and, now, ocamlbuild support. I believe that it could draw some inspiration from Dr.Java. * Students just can't install LablGtk, LablGl, Camlimage... by themselves, nor would I expect them to. A nice, centralised, installer, would be nice. * Building projects is just too hard. I hope ocamlbuild will solve this. * It seems that Graphics doesn't work with Cygwin, hence with Camelia for Windows. Which is bad, as they seem to enjoy both Graphics and Camelia. What prevents Graphics in Cygwin+X ? == Error messages == * Error messages of the type system are somewhat obscure. The reflex of many students is "OCaml wants it to be of type XXX", rather than "there is a contradiction in what I wrote". It would be nice if there was a way to ask OCaml to display additional information on type errors. Say something like, whenever typing of an expression fails, restarting the type algorithm but printing out the various unifications as they take place. == Documentation == * Documentation of LablTk is non-existent. I'm thinking about taking a student to write a more OCaml-ish layer on top of LablTk but I don't know if/when this will happen. * Type 'option' doesn't appear in the list of types of the documentation. Nor do 'Some' and 'None' appear in the list of values. * A nice *beginner-oriented* tutorial is really missing for students who failed to pay attention to the beginning of the lecture. Something more applied than _Developing applications with OCaml_ and less technical than http://ocaml-tutorial.org . Say, leading a beginner to define a Connect 4 game. I'm willing to participate into writing this, but not alone. I might launch a thread on this subject on the ML. = My fault = * That's not OCaml-specific but there must be some construction better suited than "for" or "while" to write loops without having to handcode a recursive loops. Right now, I can't think of anything better than a "hidden" Y combinator, but there must be something. * Arrays of arrays (of arrays...) are a bit obscure for students, although they're getting better at it. * Some students rely too much on references. * The usual note-taking/attention deficit/motivation deficit problems. * Anonymous functions are still beyond most of them.
We've started a documentation update for the new Camlp4. It is available as a Wiki: http://brion.inria.fr/gallium/index.php/Camlp4 Contributions are welcome (just send me an email for an account). Contributions are twofold: 1/ Enriching or adding pages. 2/ Arranging documentation priorities on: http://brion.inria.fr/gallium/index.php/Camlp4_documentation_priorities
I would like to announce the
The Enhanced Ocaml Documentation
Version 3.10
available via http://www.cs.ru.nl/~tews/htmlman-3.10
This version of the Ocaml manual enhances the original html
version in the following way:
- Changes (wrt version 3.09) are tagged with icons and color
- an additional appendix contains just the grammar rules
[The hot meta symbols are now already in the original docs.]
Changes not mentioned in the 3.10 announcement:
- profiler recognizes OCAMLPROF_DUMP environment variable
- new profiler options: -impl sourcefile, -intf sourcefile, -version
- positional specifiers for printf [probably broken]
- Printf.{kfprintf,ksprintf,kbprintf}
- Scanf.bscanf_format
- type Event.event is now covariant
- instance variables of objects are not any longer directly
available from C
- CAMLreturnT macro for C functions not returning a value
I finally released my EasyLanguage [1] to C# translator. You can see
it live at http://algokit.com. I actually wrote two versions over the
course of three months, one in OCaml and one in Haskell. After
briefly deploying the latter, I ended up going with the former.
The site is running on top of Cocan Wiki (kudos to Rich!) and I plan
to populate it as time goes by. I plan to charge traders per
translation, so I will need to add payment system integration, some
reporting, etc. Overall, I'm very satisfied with OCaml and my first
project using it.
Thanks, Joel
[1] http://lambda-the-ultimate.org/node/2201
I tried to find a full Lisp (or Scheme) parser in Ocaml, and did not immediately find one. Is my Google-fu not up to the task? Yes, I am aware that parsing s-expressions is trivial, but the full Lisp (or Scheme) grammar is somewhat more complicated, and I do not feel like reinventing the wheel. Any technology that integrates well with Ocaml is fine, since in the end in-memory ASTs is going to be what we're really interested in. Jacques PS: Other than CIL for C, are there other programming languages for which I can just get an off-the-shelf (non-commercial) parser?Pierre-Evariste Dagand answered:
There is an implementation of a minimal lisp called Minilisp here : http://www.bretagne.ens-cachan.fr/DIT/People/Luc.Bouge/Teaching/MIT1/Lisp/MLlisp/Dynamic/ It may fulfill your needs.John Skaller also answered:
OCS Scheme. http://will.iki.fi/software/ocs/Joel Reymont also answered:
This is the first result of the Google search for "scheme ocaml": http://home.arcor.de/chr_bauer/schoca.htmlEric Cooper answered the second question:
I wrote an OCaml parser for Java a while ago:
http://www.cs.cmu.edu/~ecc/joust.tar.gz
It handled the full language at the time I wrote it, but it probably
needs to be updated now (for generics at least).
We just released our vector graphics library Smoke, which was the core renderer in Presenta: http://www.ffconsultancy.com/products/smoke_vector_graphics/?o This library lets you create stunning interactive vector graphics quickly and easily from OCaml programs. The site contains three downloadable demos for Linux (both 32- and 64-bit) and the library is freely available for non-commercial use in the form of compiled bytecode for OCaml 3.09.2. Happy hacking!
[This email is an update on recent efforts to get OCaml packages included in the base Fedora distribution]. (1) Draft packaging guidelines for Fedora OCaml packages are published here: http://fedoraproject.org/wiki/PackagingDrafts/OCaml https://bugzilla.redhat.com/bugzilla/show_bug.cgi?id=239004 It would be a great help if people could look at these and point out any problems. Reports should go (in order of preference) to: that Bugzilla entry (but you will need to create an account), follow up here, or email me directly. (2) I've packaged up some things already: http://tinyurl.com/2rl4w6 This list was chosen fairly randomly, in order that I could get some of my own code to run for testing purposes. In the long run, I hope we can package most things, but if you think there are important packages that should be prioritised, please let me know. (3) Would your school[*] / company / organisation be more inclined to buy Red Hat Enterprise Linux licenses if it came with high quality OCaml packages? Having packages is nice, but having a business case behind them is better. Please mail me if so. (4) Lastly, if you would like to join or follow the effort, you can join the SIG here: http://fedoraproject.org/wiki/SIGs/OCaml Rich. [*] Educational discounts are available.
http://wagerlabs.com/2007/5/27/dear-diary/ Enjoy!
Below is the Final Call for Papers for the 2007 Workshop on ML.
It's only a few weeks until the submission deadline (June 15), so
whether you are a designer, developer or user of ML, please consider
contributing a paper!
Note that this year, we are introducing a new paper category of
"work-in-progress reports". These are intended as a way of informing
others in the ML community about the status of ML-related research or
implementation projects, as well as communicating insights gained from
such projects that do not quite constitute a full research paper. See
below for more details.
If you are interested in submitting a paper, but you are not sure
about what category it belongs in or if it would be appropriate for
the workshop, please contact me or Claudio Russo, the Workshop Organizer.
Derek Dreyer (Program Chair)
-------------------------------------------------------------------
The 2007 ACM SIGPLAN Workshop on ML
Friday, October 5, 2007
Freiburg, Germany
To be held in conjunction with ICFP '07
http://research.microsoft.com/~crusso/ml2007/
Submission web site (now open):
https://www.softconf.com/starts/ml07/submit.html
FINAL CALL FOR PAPERS
GOALS OF THE WORKSHOP:
The ML family of programming languages, whose most popular dialects
are Standard ML and Objective Caml, has inspired a tremendous amount
of computer science research, both practical and theoretical. ML
continues to be employed successfully in applications ranging from
compilers and theorem provers to low-level systems software, web
applications and video games. The Workshop on ML aims to bring
together researchers, developers and users of ML to hear about and
discuss the latest work on the design, semantics, implementation and
application of ML and ML-like languages. Previous ML workshops have
been held in Orlando, Florida (1994), Baltimore, Maryland (1998),
Tallinn, Estonia (2005), and Portland, Oregon (2006).
The 2007 Workshop on ML will be held in conjunction with the 12th ACM
SIGPLAN International Conference on Functional Programming (ICFP 2007)
in Freiburg, Germany on Friday, October 5, 2007.
SUBMISSION GUIDELINES:
This year, we are seeking paper submissions of two varieties:
*research papers* and *work-in-progress reports*.
*Research papers* must present original research that has not been
published elsewhere. We welcome research papers on any ML-related
topic, including (but not limited to):
* applications
* concurrent programming
* formal semantics
* language design
* language formalization and mechanization
* language implementation
* programming environments
* type systems
*Work-in-progress reports* need not present original research. Rather,
they are intended as a way of informing others in the ML community
about the status of ML-related research or implementation projects, as
well as communicating insights gained from such projects that do not
quite constitute a full research paper. As such, we expect that
work-in- progress reports will be shorter than research papers, and we
will not judge them to the same standard. If you have any questions
regarding the appropriate paper category for a potential submission or
its overall suitability for the workshop, please contact the program
chair.
All paper submissions must be at most 12 pages total length in the
standard ACM SIGPLAN two-column conference format:
http://www.acm.org/sigs/sigplan/authorInformation.htm
Authors of work-in-progress report submissions should designate their
papers as such by including the words "work in progress" or "status
report" in the title. Submissions authored by program committee
members are permitted, with the usual stipulation that they will be
judged to a higher standard.
Accepted papers will be published by the ACM and will appear in the
ACM Digital Library.
Submissions are now being accepted electronically via START:
https://www.softconf.com/starts/ml07/submit.html
IMPORTANT DATES:
Submission deadline: Friday, June 15, 2007
Notification of acceptance: Friday, July 13, 2007
Final revision due: Friday, August 3, 2007
Workshop: Friday, October 5, 2007
WORKSHOP ORGANIZER:
* Claudio Russo (Microsoft Research, Cambridge)
crusso_AT_microsoft.com
PROGRAM CHAIR:
* Derek Dreyer (Toyota Technological Institute at Chicago)
dreyer_AT_tti-c.org
PROGRAM COMMITTEE:
* Lars Birkedal (IT University of Copenhagen)
* Derek Dreyer (Toyota Technological Institute at Chicago)
* Jacques Garrigue (Nagoya University)
* Luc Maranget (INRIA Rocquencourt)
* Greg Morrisett (Harvard University)
* Atsushi Ohori (Tohoku University)
* Peter Sestoft (IT University of Copenhagen)
* Peter Sewell (University of Cambridge)
* Mark Shinwell (CodeSourcery UK Ltd)
* Don Syme (Microsoft Research, Cambridge)
Has anyone implemented a parallel map function in OCaml using Unix forks, pipes and maybe marshalling? This seems like an easy way to get concurrency in OCaml...Oliver Bandel said:
I have thought about such stuff, but ot implemented (because there was no real need for it). Since I found OCamlP3l, I'm not shure if implementing such stuff would make sense, because using OCamlP3l might be the right way. OCamlP3l: http://camlp3l.inria.fr/eng.htm I didn't tried it so far. If people already have done (or will do now), I would be interested in feedback.Luc Maranget said:
This is what we did for a a few examples of using JoCaml, the soon-to-be-released extension of OCaml for concurrent programming. Fork/Exec is an easy way to get simultaneous execution. JoCaml is not released yet, (I am writting the doc and web site at the moment). The much incomplete web site is at http://jocaml.inria.fr One example of fork under jocaml control http://jocaml.inria.fr/manual/concurrent.html#htoc25 The example may not meet all your concerns (speed I guess), but you can replace the shell in the example by somme C or Ocaml program that computes something and refine the control to collect results.
Jon Harrop asked about this recently and I thought it was an interesting idea and implemented it: http://yumegakanau.org/blog/2007/06/03/ (BTW I don't think you are "faking" concurrency by using fork...)
I just got a first working version of .NET style asynchronous invocation
working in OCaml using process forking.
The following OCaml function forks a new process and computes "f x" in that
process, returning a function that blocks and returns the result using
marshalling.
let invoke (f : 'a -> 'b) x : unit -> 'b =
let input, output = Unix.pipe() in
match Unix.fork() with
| 0 ->
Unix.close input;
let output = Unix.out_channel_of_descr output in
Marshal.to_channel output (try `Res(f x) with e -> `Exn e) [];
exit 0
| _ ->
Unix.close output;
let input = Unix.in_channel_of_descr input in
fun () ->
match Marshal.from_channel input with
| `Res x -> x
| `Exn e -> raise e
This function tries to account for reraising exceptions on the parent process
but that is untested.
You can write a higher-order "map" function in terms of invoke like this:
let ( |> ) x f = f x
let map (f : 'a -> 'b) a : 'b array =
Array.map (invoke f) a |>
Array.map (fun f -> f())
When you apply this map to an array, a new process is forked for each element.
As forking is time consuming, you should only apply this to short arrays.
The performance characteristics of this approach are very interesting.
Firstly, I can observe doubled performance on my dual core by invoking two
simple but CPU-intensive operations concurrently:
map fib [|43; 43|]
However, performance is easily degraded using this approach, partly because
forking is expensive but also because of other effects that I do not yet
understand. My original benchmark summed the elements of an array using
fold_left. For some reason, this is extremely inefficient, as if the entire
array is copied.
Anyway, this function is so simple that it took no time to work it into my ray
tracer benchmark. The benefits of concurrency on my dual-core system reduce
the time taken by OCaml from 4s to 3s.
I'll try a concurrent F# version and see how it compares...
We are proud to announce the latest release of the OMake Build System -
OMake 0.9.8.3 ("stable") and pre-announce that OMake 0.9.9 ("unstable")
is expected to be released within a week.
OMake is a build system designed for scalability and portability. It
uses a syntax similar to make utilities you may have used, but it
features many additional enhancements, including the following.
- Support for projects spanning several directories or directory
hierarchies.
- Fast, reliable, automated, scriptable dependency analysis using MD5
digests, with full support for incremental builds.
- Fully scriptable, includes a library that providing support for
standard tasks in C, C++, OCaml, and LaTeX projects, or a mixture
thereof.
Often, a configuration file is as simple as a single line
.DEFAULT: $(OCamlProgram prog, foo bar baz)
which states that the program "prog" is built from the files foo.ml,
bar.ml, and baz.ml. This one line will also invoke the default
standard library scripts for discovering implicit dependencies in
OCaml files.
- Full native support for rules that build several files at once.
- Portability: omake provides a uniform interface on Linux/Unix
(including 64-bit architectures), Win32, Cygwin, Mac OS X, and other
platforms that are supported by OCaml.
- Built-in functions that provide the most common features of programs
like grep, sed, find, and awk. These are especially useful on Win32.
- Active filesystem monitoring, where the build automatically restarts
whenever you modify a source file. This can be very useful during
the edit/compile cycle.
- A built-in command-interpreter osh that can be used interactively.
OMake preserves the style of syntax and rule definitions used in
Makefiles, making it easy to port your project to OMake. There is no
need to code in Perl (cons), or Python (scons). However, there are a few
things to keep in mind:
1. Indentation is significant, but tabs are not required.
2. The OMake language is functional: functions are first-class and
there are no side-effects apart from I/O.
3. Scoping is dynamic.
OMake is licensed under a mixture of the GNU GPL license (OMake engine
itself) and the MIT-like license (default configuration files).
Additional information and extensive documentation can be found on OMake
Home Page at http://omake.metaprl.org/
OMake version 0.9.8.3 is a minor feature enhancements and bugfixes
release. The changes in this version include:
- Made it easy to define default ("implicit") rules for phony targets.
- Detect case-insensitive filesystems on Unix-like operating systems
(especially important under Mac OS X).
- A number of performance improvements.
- Documentation improvements.
For a more verbose change log, please visit
http://omake.metaprl.org/changelog.html#0.9.8.3 .
Source and binary packages of OMake 0.9.8.3 may be downloaded from
http://omake.metaprl.org/download.html . In addition, OMake may be
obtained via the GODI packaging system.
To try it out, run the command "omake --install" in a project directory,
and modify the generated OMakefile.
Even though we call it "stable", OMake 0.9.8.3 should still be
considered an alpha release. While we have made an effort to ensure that
it is bug-free, it is possible some functions may not behave as you
would expect. Please report any comments and/or bugs to the mailing list
o...@metaprl.org and/or at http://bugzilla.metaprl.org/
OMake 0.9.9 will feature a large number of major changes that Jason
Hickey have been working on for the last two years. These changes include:
* Completely redesigned variable naming semantics aimed at making sure
that similarly named unrelated variables from different source
files do not clash.
* Optional ("keyword") arguments to functions.
* An option to use an alternative "programming-language-style" syntax,
where all string constants have to be quoted, but variable and
function references do not have to use the $(...) syntax.
* Dynamic loading of C libraries, including:
- Tools for automated creation of OCaml wrappers to C libraries by
parsing the C header files.
- As an example, _automatically generated_ OCaml and OMake wrappers
for the GTK library.
- As a demo for the above, an OMake GUI capable of presenting a
browseable dependency tree, and much more.
* And many other features (much more complete and detailed list will
accompany the release).
The new version of ODT has been released this evening. It now supports execution via the Java 1.5 JVM and, most of all, has a new feature: automatic indentation! Automatic indentation has been developed in less than two weeks (2 or 3 hours a day) and is completely configurable via an XML file: incredible !!! This release also fixes (minor) bugs. Everything is available on the ODT website: http://ocamldt.free.fr. The "overview" page explains its current main features, and the "install notes" page details some requirements and incompatibilities with older versions of OCaml. Some screenshots are also available to show the GUI. Please, don't hesitate to try ODT (for personal or professional use) and forward this mail to anyone which could be interested in.
We are happy to annouce the release of JoCaml.
JoCaml is an extension of Objective Caml for concurrent
and distributed programming based upon the join calculus.
More details (including a tutorial) are available on
the jocaml web site:
http://jocaml.inria.fr/.
The new JoCaml (born again jocaml) is a total re-implementation of
the new defunct JoCaml by F. Le Fessant. With respect to this previous
version, changes are important.
* New syntax. Believe it or not, the new syntax is better.
* More convenient command set (bytecode compiler jocamlc,
toplevel jocaml, native code compiler jocamlopt).
* Disparition of mobility features. More reasearch is needed
for those, besides they break OCaml compatibility.
* Full compatibility with OCaml. For that reason, we adopt
OCaml releasing scheme: initial version of JoCaml is 3.10.0.
---
Louis Mandel & Luc Maranget (jocaml-devel@inria.fr).
Joel Reymont asked and Luc Maranget answered:> How often do you pull patches from the OCaml tree into the JoCaml tree? At every ocaml release. > How is this done? I wonder why you neeed such information, nevertheless here it is: Basically, JoCaml is the 'jocamltrunk' branch in ocaml CVS, it also has a 'module' name: jocsl. Syncing jocaml with ocaml is a two step process: Checkout jocaml: cvs co -kk -r jocamltrunk jocsl Perform changes from (ocaml) release1 to release2 in jocaml cvs update -kk -j release1 -j release2 (There are a few details left, such as bootstrap)Yaron Minsky asked and Luc Maranget answered:
> A couple of questions:
> - Why is it that JoCaml is a full OCaml distribution as opposed to
> just a set of libraries plus a syntax extension. Was there some
> particular
> feature that required hacking the compiler directly, or was it just more
> convenient to build it that way?
As far as I know, access to the guts of the compiler is required at
least for the following two features.
- Specific typing rules.
- Pattern matching compilation.
See the buffer example in the doc for instance
http://jocaml.inria.fr/manual/concurrent.html#htoc20
Besides, JoCaml is not a full OCaml distribution. JoCaml is a restricted
OCaml distribution. On the light side, JoCaml compilation is very fast;
on the dark side, some of OCaml tools are not available, (camlp4, ocamlbuild,
labltk..)
> - What do you think the future of JoCaml is? Any thoughts on whether
> it will be supported in the future, and in particular whether it will get
> merged back into the OCaml mainline tree?
I can only wish a bright future to JoCaml :)
Our team will support JoCaml.
Merging JoCaml into the OCaml mainline tree is another story. We have
no plans for that at the moment. Let us wait a bit for JoCaml success
to deprecate OCaml thread libraries.
Jon Harrop asked and Luc Maranget answered:> Is there a JoCaml mailing list? I don't want to spam the OCaml list with my > noob questions (writing a concurrent ray tracer). :-) There is a JoCaml mailing list http://yquem.inria.fr/cgi-bin/mailman/listinfo/jocaml-list (As for the OCaml list, only subscribers can post). By the way we also have a web site http://jocaml.inria.fr with such information and others.
I always thought that the presentation "One-Day Compilers", in which
Graydon Hoare builds a Makefile compiler on top of ocamlc and gcc
using camlp4, contains very good material to demonstrate the power
and practicality of OCaml (and camlp4) to a certain audience. (For
other audiences it might be better to show that you can program a
real-time 2D simulation of bouncing balls in under 400 lines of
code.) It's also very funny:
http://www.venge.net/graydon/talks/mkc/html/
Nevertheless, some elements about the presentation could be improved:
(i) the detour via C and gcc makes things needlessly complex since
ocamlopt can directly generate native and independent executables
(although historically that was perhaps not yet the case in 2002),
and (ii) the choice of source language (Makefiles) does not seem
optimal in the sense that build files hardly contain any computation.
Anyhow, after some frustration about the execution speed when solving
a problem with existing Prolog implementations, I had the idea that
maybe a compiler - even a one-day one - could improve, and that it
would make a fabulous example for Graydon's approach. So I spent one
figurative day trying to build a Prolog compiler (plc) based on a
simplified set-up:
- a camlp4 preprocessor converts Prolog code to an OCaml AST that
embodies the (possible) computations
- ocamlopt can compile the OCaml AST to native code
At the moment, I have plc working for a simple subset of Prolog
(consisting only of atoms, variables, predicates and rules; no
structures/lists, no integers). You can check out the code (for OCaml/
camlp4 3.09, no 3.10 yet) at:
http://ssel.vub.ac.be/svn-gen/bdefrain/plc/
(Look at demo.pl and try "make demo". To see what is executed, look
at "make demo.output" and demo_driver.ml.)
Since there is not a lot of documentation, I will elaborate a bit below.
The difficult part is in translate.ml, and the approach I take to
translate Prolog to OCaml, is to represent each predicate as a number
of functions, one for each variation in state (open or closed) of the
arguments. The functions take a parameter for each "closed" argument,
as well as a function parameter. They invoke the latter for each
solution, with the binding of the "open" arguments as parameters. To
find solutions, we invoke the functions of the respective subgoals.
For example, a predicate with two arguments, such as sibling/2, is
translated to four versions:
(* both arguments open *)
val sibling_oo : (atom -> atom -> unit) -> unit
(* first argument closed *)
val sibling_co : (atom -> unit) -> atom -> unit
(* second argument closed *)
val sibling_oc : (atom -> unit) -> atom -> unit
(* both arguments closed *)
val sibling_cc : (unit -> unit) -> atom -> atom -> unit
If this predicate is defined by the following rule:
sibling(X,Y) :- parent(Z,X), parent(Z,Y).
The bodies of the sibling_xx functions will invoke the translations
of the parent/2 predicate in a manner appropriate to the binding
state of the variables, for example:
let sibling_oo _f =
(* subgoal parent(Z,X) where Z and X are still open *)
parent_oo (fun z x ->
(* subgoal parent(Z,Y) where Z is closed and Y open *)
parent_co (fun y ->
(* solution for sibling(X,Y) *)
_f x y)
z)
Similarly:
let sibling_co _f x =
parent_oc (fun z -> parent_co (fun y -> _f y) z) x
And so on.
As can be seen, the conjunction (,) is modeled as a nesting of the
invocations. plc also handles disjunction (multiple rules for the
same predicate) by translating them to a sequence of statements. Of
course, it also handles atoms (as in "person(joe).") and reuse of a
variable inside one goal (e.g. "same(X,X).") by appropriate bindings
and/or tests. I believe all of this models the execution semantics of
Prolog correctly.
I plan to extend plc at some point to support a more complete
language (so that it can handle the N-Queens problem, for example).
The intent of this early announcement is to raise some feedback and
(maybe) help. Do you see obvious mistakes? Could this approach be
extended to support structures/lists? (Will it be fast?) Can the
approach/implementation still be improved? Do you know just the right
high-order functions to make translate.ml more readable? Etc.
Bruno De Fraine then added (find the attached files at the archive):
An addendum to my previous message:
Some preliminary benchmarks indicate that plc is a vastly faster
execution platform than tried-and-tested (and optimized) Prolog
engines such as SWI Prolog and Sicstus Prolog (although it currently
only supports a restricted language).
For my example program, it is almost 12x faster than SWI and 3.7x
faster than Sicstus.
Some details: solving the win-predicate in the attached Prolog-file
causes a search in the space of all six-letter words (i.e. 26^6
strings); it reports those words that are "prolog". I collected the
following timings on my computer (Intel Core 2 Duo, MacOS X 10.4.9):
SWI-Prolog (Multi-threaded, Version 5.6.10):
$ time swipl -s prolog.pl -g true -t "win(A,B,C,D,E,F),write
([A,B,C,D,E,F]),nl,fail"
% prolog.pl compiled 0.00 sec, 4,280 bytes
[p, r, o, l, o, g]
real 0m59.065s
user 0m58.845s
sys 0m0.073s
SICStus 4.0.1:
$ time ~/sicstus/bin/sicstus -f -l prolog.pl --goal "win
(A,B,C,D,E,F),write([A,B,C,D,E,F]),nl,fail;halt."
% compiling /Users/bruno/my_svn/plc/prolog.pl...
% compiled /Users/bruno/my_svn/plc/prolog.pl in module user, 0 msec
2312 bytes
SICStus 4.0.1 (i386-darwin-8.9.1): Tue May 15 14:53:23 CEST 2007
Licensed to Bruno De Fraine
[p,r,o,l,o,g]
real 0m18.474s
user 0m18.417s
sys 0m0.038s
plc and ocamlopt 3.09.3:
$ time { make prolog.cmx; make driver.cmx; ocamlopt -o driver.opt
prolog.cmx driver.cmx; ./driver.opt; }
ocamlopt.opt -c -dtypes -pp 'camlp4 ./plc.cma pr_dump.cmo -impl' -
impl prolog.pl
ocamlopt.opt -c -dtypes driver.ml
prolog
real 0m5.069s
user 0m4.749s
sys 0m0.191s
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.