plc, a One-Day Prolog Compiler

plc, a One-Day Prolog Compiler

[Bruno De Fraine]

Hello,

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.

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.De.Fraine@vub.ac.be

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

[Bruno De Fraine]

[-- Attachment #1: Type: text/plain, Size: 1641 bytes --]


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

Regards,
Bruno


[-- Attachment #2: prolog.pl --]
[-- Type: text/x-perl-script, Size: 425 bytes --]


letter(a).
letter(b).
letter(c).
letter(d).
letter(e).
letter(f).
letter(g).
letter(h).
letter(i).
letter(j).
letter(k).
letter(l).
letter(m).
letter(n).
letter(o).
letter(p).
letter(q).
letter(r).
letter(s).
letter(t).
letter(u).
letter(v).
letter(w).
letter(x).
letter(y).
letter(z).

winner(p,r,o,l,o,g).

win(A,B,C,D,E,F) :- 
	letter(A),
	letter(B),
	letter(C),
	letter(D),
	letter(E),
	letter(F),
	winner(A,B,C,D,E,F).

[-- Attachment #3: driver.ml --]
[-- Type: application/octet-stream, Size: 155 bytes --]


let soa = Prolog.string_of_atom ;;

Prolog.win_oooooo (fun a b c d e f ->
	print_endline ((soa a) ^ (soa b) ^ (soa c) ^ (soa d) ^ (soa e) ^ (soa f))
) ;;

[-- Attachment #4: Type: text/plain, Size: 213 bytes --]


--
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.De.Fraine@vub.ac.be