Prolog to C

Appeared in Volume 7/1, February 1994

mlevy@csr.uvic.ca
Michael Levy
27th June 1993

Stephan Raaijmakers writes:
Is there some straighforward way of compiling Prolog to C?

Nigel Horspool and I have written a translator that is WAM-based. Essentially, it translates Prolog programs into a sequence of C function or macro calls to WAM functions. Some details are given in our paper:

"Translating Prolog to C: a WAM-based Approach" The Second Compulog Network Area Meeting on Prog. Langs, and Workshop on Logic Langs, Pisa, May 1993.

R.B.Scott@ed.ac.uk
Robert Scott
27th June 1993

One way is to not really translate anything. You need a Prolog compiler that compiles from Prolog to WAM instructions. Then for each WAM instruction you should write a C macro that implements it. You should then wrap up the WAM program in a C switch statement like so:

go()
{	top:
 	switch(nxt_lbl){
  		/* WAM code */
		:
 	}
} 

nxt_lbl = append_3_1; goto top;

I've written an FGHC system that uses this approach. The main problem is that a small Prolog program can be compiled into very large object code. However, the code is reasonably fast.

This idea comes from the papers on JANUS by Saraswat et al.

mlevy@csr.uvic.ca
Michael Levy
27th June 1993

We are interested in translating Prolog to C because of multi-paradigm programming - software where some components are written in C and others in Prolog.

If this strategy is to make sense, it must be possible to have C-style modules - a system made up of many C files (some of them translated from Prolog).

Our translation approach is to use a switch statement within predicates, but "dispatch" across predicates. The advantage when compared with the single switch approach is modularity: you can translate several files of Prolog code into the same number of C files.

Code expansion is about 12 or 15 to 1 if you go straight to WAM code; 1 line of Prolog results in 12 to 15 lines of WAM code.

If I had a Prolog system with several modules (such as a compiler) that was about 2000 Prolog lines long, it would just not be practical to try to use a C function with a single switch and 30,000 lines of C. It wouldn't even be compilable on some machines.

We are looking at ways to reduce the number of C lines generated, but that's another story.

ridoux@irisa.fr
Olivier Ridoux
28th June 1993

A simple and quite robust way of translating Prolog into C is to devise a representation for the success and failure continuations (and others, if any), and then to translate every predicate into a function that uses and modifies the continuations. A motor, the remnant of an interpreting loop, iterates on calling these functions. Inside the function, you use whatever intermediate machine you like. Clauses can be either the branches of a switch statement, or simply labelled when using a C system that can store labels.

Miscellaneous remarks:

1) Someone objected: "What for? Prolog and C are so different!". That's the only reason it is worth translating Prolog to C.

2) "A motor! Calling every function! That's inefficient!". Not that much, and it can often be avoided.

3) Our experience (the compilation of LambdaProlog) is that it works: e.g. the compiler compiles itself. In the art of compiling LambdaProlog we are not yet at the point where a function call matters.

4) Someone complained: "That cannot be done! Prolog programs are modifiable while C programs are not!". There is no reason for being proud about being able to modify Prolog programs with assert and retract. In LambdaProlog, one can modify them using intuitionistic implication only.