Mailing list for all users of the OCaml language and system.
 help / color / mirror / Atom feed
* plc, a One-Day Prolog Compiler
@ 2007-05-31 14:39 Bruno De Fraine
  2007-06-04 13:32 ` [Caml-list] " Bruno De Fraine
  0 siblings, 1 reply; 2+ messages in thread
From: Bruno De Fraine @ 2007-05-31 14:39 UTC (permalink / raw)
  To: caml-list ml

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



^ permalink raw reply	[flat|nested] 2+ messages in thread
end of thread, other threads:[~2007-06-04 13:33 UTC | newest]

Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-05-31 14:39 plc, a One-Day Prolog Compiler Bruno De Fraine
2007-06-04 13:32 ` [Caml-list] " Bruno De Fraine

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox