Re: Compiling Prolog-like languages

"Sarah Thompson" <sarah@telergy.com> writes:




> 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?


"Compiler Design" by Wilhelm & Maurer (Addison Wesley) has a fairly
detailed chapter on Prolog implementation. It uses a simple abstract
machine that is designed for simplicity rather than efficiency, but it
should give you a good idea of the issues.


Hassan Ait-Kaci's "Warren's Abstract Machine - a Tutorial
Reconstruction" (MIT Press) is a good description of the WAM.


> 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?


Simpler, certainly. Faster, maybe. But most of the speed of the fast
Prolog compilers is not due to abstract machine choice, but due to the
amount of optimizations done. There is no all-around best choice, it
depends on your needs and how much time you want to invest in the
implementation.


> 3. I currently use C++ as a target language, although this is intended
> to be an interim step toward a lower level code generator. Is this
> likely to be good/bad/indifferent as regards implementing a WAM or
> something similar to it?


C++ is overkill, but C would be O.K. The main problem is the lack of
label pointers (useful for backtrack points etc.). GCC has these
added, so if you use that you can be fine. You could use function
pointers instead, but that makes tail-call optimization harder.


An alternative is to write an interpreter for an abstract machine.
Unless your problems are very speed critical, the reduction in speed
shouldn't be problematical.


Torben Mogensen (torbenm@diku.dk)

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