[Caml-list] plc, a One-Day Prolog Compiler

Skip to first unread message

Bruno De Fraine

May 31, 2007, 10:41:09 AM5/31/07
to caml-list ml

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:


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:


(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)


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.

Thanks and best regards,
Bruno De Fraine

Bruno De Fraine
Vrije Universiteit Brussel
Faculty of Applied Sciences, DINF - SSEL
Room 4K208, Pleinlaan 2, B-1050 Brussels
tel: +32 (0)2 629 29 75
fax: +32 (0)2 629 28 70
e-mail: Bruno.D...@vub.ac.be

Caml-list mailing list. Subscription management:
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

Bruno De Fraine

Jun 4, 2007, 9:34:30 AM6/4/07
to caml-list ml

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
% 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
% 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

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

real 0m5.069s
user 0m4.749s
sys 0m0.191s


Reply all
Reply to author
0 new messages