From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 617A8BC69 for ; Thu, 31 May 2007 16:39:15 +0200 (CEST) Received: from dorado.vub.ac.be (mailhost.vub.ac.be [134.184.129.10]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l4VEdE4M002671 for ; Thu, 31 May 2007 16:39:15 +0200 Received: from exchange.etro.vub.ac.be (etro10.vub.ac.be [134.184.2.10]) by dorado.vub.ac.be (Postfix) with ESMTP id 68C605C0 for ; Thu, 31 May 2007 16:39:14 +0200 (CEST) Received: from ssel.vub.ac.be ([10.0.4.37]) by exchange.etro.vub.ac.be with Microsoft SMTPSVC(6.0.3790.3959); Thu, 31 May 2007 16:39:14 +0200 Received: from localhost (localhost.localdomain [127.0.0.1]) by ssel.vub.ac.be (Postfix) with ESMTP id 1934E2468AAD for ; Thu, 31 May 2007 16:39:14 +0200 (CEST) X-Virus-Scanned: amavisd-new at ssel.vub.ac.be Received: from ssel.vub.ac.be ([127.0.0.1]) by localhost (ssel.vub.ac.be [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id sQWMTf-mvG7z for ; Thu, 31 May 2007 16:39:06 +0200 (CEST) Received: from [10.0.4.145] (unknown [10.0.4.145]) by ssel.vub.ac.be (Postfix) with ESMTP id 516672468AAC for ; Thu, 31 May 2007 16:39:06 +0200 (CEST) Mime-Version: 1.0 (Apple Message framework v752.3) Content-Transfer-Encoding: 7bit Message-Id: <05F057DE-3838-47A7-9ECC-813057C0BB9F@vub.ac.be> Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed To: caml-list ml From: Bruno De Fraine Subject: plc, a One-Day Prolog Compiler Date: Thu, 31 May 2007 16:39:04 +0200 X-Mailer: Apple Mail (2.752.3) X-OriginalArrivalTime: 31 May 2007 14:39:14.0195 (UTC) FILETIME=[7599D630:01C7A391] X-Miltered: at concorde with ID 465EDE12.003 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; compiler:01 graydon:01 makefile:01 compiler:01 ocamlc:01 gcc:01 camlp:01 ocaml:01 camlp:01 graydon:01 gcc:01 ocamlopt:01 makefiles:01 ocaml:01 computations:01 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