Re: Compiling Prolog-like languages

"Neelakantan Krishnaswami" <neelk@alum.mit.edu> writes:


> Sarah Thompson <sarah@telergy.com> wrote:
> >
> > Before I weigh into this and start reinventing considerable quantities
> > of wheels, I thought it might make sense to ask some questions here.
> >
> > 1. Can someone point toward a good tutorial on implementing
> > Prolog-like programming languages?
>
> Hassan Ait-Kaci's _Warren's Abstract Machine: A Tutorial
> Reconstruction_ is probably the best there is.


It should be said that it's very hard to improve _substantially_ on
the WAM, once you go below the instruction set. Every little piece you
tinker with has repercussions. (A pareto-optimal design?)


The best-known tries are Aquarius Prolog by Peter Van Roy et al and
Andrew Taylor's Parma system. Lots of interesting little
implementation tips there. One big lesson is that you want to do static
analysis to strength-reduce primitive operations (esp. unifications).


I also should mention SICStus Prolog, which has an impressive yet
straightforward native compiler, and BIM Prolog, where Andre Marien
devised the so far best way of compiling unification known (to me, at
least :-). Both use the WAM.


You could also have a look at how the Mercury project compiles its
language, which is fairly close to Prolog. It provides inspiration if
you compile to C, but be aware that they can take shortcuts in doing
this that Prolog does not permit.


> > 2. Much of the literature mentions the Warren Abstract Machine. Is
> > this regarded as the best way to go, or are there
> > simpler/faster/better/newer alternatives worthy of consideration?
>
> Another possibility is to use a continuation-passing style framework.
> This mails tail merging easier to do, and there are a *lot* of papers
> on how to efficiently compile CPS code.


There is BinProlog by Paul Tarau, which is a simple and fairly
efficient way of compiling Prolog.


To beat my own drum a bit, I wrote a couple of papers on the topic of
CPS-compiling Prolog some years ago. The most convenient place to find
them is probably my thesis:


ftp://ftp.csd.uu.se/pub/papers/theses/0026.ps.gz


Also fizzily known as "Compilation Techniques for Prolog".


Todd Proebsting wrote a PLDI paper on compiling Icon (I think), which
at its basis came pretty close to "A Continuation-Passing Style for
Prolog", one of the papers above. It's a lot clearer in the
presentation than my paper, and I think it translated into C-like
code:


Todd A. Proebsting. Simple translation of goal-directed
evaluation. Proc. PLDI'97.


You should also consider memory management. There is quite a
bit of work on this, since Prolog's backtracking also can serve to
reclaim memory if you're careful.


Finally, I'm probably leaving out a lot of interesting work from
recent years. I departed the field after finishing my thesis, which
was in 1996.


Best,
Thomas
--
Thomas Lindgren
I'd rather write programs that write programs than write programs-[R. Sites]

Return to the comp.compilers page.
Search the comp.compilers archives again.