Re: Prolog to WAM Register Allocation?

russell kym horsell <>
19 Jan 2006 23:16:56 -0500

          From comp.compilers

Related articles
Prolog to WAM Register Allocation? (Ludwig Wittgenstein) (2006-01-12)
Re: Prolog to WAM Register Allocation? (2006-01-17)
Re: Prolog to WAM Register Allocation? (Jens Kilian) (2006-01-17)
Re: Prolog to WAM Register Allocation? (Ivan A. Kosarev) (2006-01-17)
Re: Prolog to WAM Register Allocation? (russell kym horsell) (2006-01-19)
| List of all articles for this month |

From: russell kym horsell <>
Newsgroups: comp.compilers
Date: 19 Jan 2006 23:16:56 -0500
Organization: Central Iowa (Model) Railroad, Plano, TX, USA
References: 06-01-040
Keywords: prolog
Posted-Date: 19 Jan 2006 23:16:56 EST

Ludwig Wittgenstein <> wrote:
> Hello all,

> I'm currently studying how Prolog compiles its source into Warren
> Abstract Machine code and I was wondering what kind of algorithm does
> Prolog use to assign variables and constants to X and Y registers?

> For instance, predicate(X,Y,john) allocates X1 for X, X2 for Y, and X3
> for john ? or, when I pass a query ?- lives_in(john, X) Do I assume
> that X variable is bound value is in X1 or X2?

> I've seen numerous literature on code generation/register allocation
> for imperative languages (on register-based machines and stack-based
> machines) but there seems to be no literature at all on how Prolog code
> generation against Warren Abstract machines (Ait-Kaci's book barely
> touches on this subject). Any idea on where such information could be
> found?

Given that Prolog dates from the 70s, when I did a grad course on
Prolog compiling c1995 I was surprised the sources were still papers
written by Warren (the Edinburgh one) and some selected otherts.

In the WAM model there are "permanent" registers and "temporary" ones.
Whether something is temp/perm depends on whether it's referenced
in the body past goal #1. If so, it's permanent; else temp.

The model is highly optimised, as you probably gather, so stack frames
(and -- hence -- number of permanent vars that need to be restored on
backtracking) get shrunk as evaluation of a goal list proceeds. Numerous
other tricks are used to minimise stack usage (e.g. determining whether
variables need to be saved on the heap instead of the stack by a runtime
test). It's all very complicated in its full generality.

If you pop over to comp.prolog you might get something out of Jan W
who implemented a "WAM in 8 instructions" compiler back in the 90s.
His SWIPL implemention is much more complex than that, so don't get
diverted. :)

Post a followup to this message

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