Alternatives to the WAM

Question

I remember once reading that there were at least two other alternatives invented roughly at the same time as the WAM. Any pointers?

Predicable

Answer 1

Prior to the WAM, there was the ZIP by Clocksin. Its design is still very interesting. SWI-Prolog uses it. And also B-Prolog has slowly migrated from a WAM design towards the ZIP. Of course, on that way many new innovations were developed. Another alternative is the VAM.

A comparison as of 1993 is:

http://www.complang.tuwien.ac.at/ulrich/papers/PDF/binwam-nov93.pdf

In the meantime, the most interesting architectural developments are related to B-Prolog.

WAM vs. ZIP

The key difference between the WAM and the ZIP is the precise interface for a predicate's arguments. In the WAM, the arguments are all passed via registers, that is, either real registers or at least fixed locations in memory. The ZIP passes all arguments via the stack.

Let's consider a minimal example:

p(R1,R2,R3,L1,L2,L3) :-  % WAM                % ZIP
                         % store L1..L3       % nothing
                         % nothing            % push R1..R3
                         % init X1..X3        % push X1..X3
   q(R1,R2,R3,X1,X2,X3),
                         % put unsafe X1..X3  % push X1..X3
                         % load       L1..L3  % push L1..L3
   r(X1,X2,X3,L1,L2,L3).

Prior to calling q:

The WAM does not need to do any action for arguments that are passed on to the first goal at the very same positions (R1..R3). This is particularly interesting for binary clauses - that is, clauses with exactly one regular goal at the end. Here the WAM excels.

The other arguments L1..L3 need to be stored locally. So for these arguments, the register interface did not do anything good.

The ZIP on the other hand does not need to save arguments - they are already saved on the stack. This is not only good for clauses with more than one goal, but also for other interrupting goals like constraints or interrupts.

As a downside, the ZIP must push again R1..R3.

Both have to initialize X1..X3 and store them on the stack.

Calling q:

When calling q, the WAM has to allocate stack space for X1..X3 and L1..L3 thus 6 cells, whereas the ZIP needs R1..R3,L1..L3,X1..X3. So here, the WAM is more space efficient. Also, the WAM permits environment trimming (for more complex situations) which is next-to-impossible for the ZIP.

Prior to calling r:

This r is the last call, and systems try to free the space for this clause, provided no choice point is present.

For the WAM, the existential variables X1..X3 have to be checked for being still uninstantiated local variables (put_unsafe), and if, they are moved onto the heap - that's expensive, but occurs rarely. L1..L3 are just loaded. That's all, the WAM can now safely deallocate the local frame. So last call optimization is dirt cheap.

For the ZIP, everything has to be pushed as usual. Then only, an extra scan has to examine all the values on the stack and moves them accordingly. That's rather expensive. Some optimizations are possible, but it is still much more than what the WAM does. ((A possible improvement would be to push arguments in reverse order. Then the variables L1..L3 might be left in their location. So these variables would not need any handling. I have not seen such an implementation (yet).))

Throughput

Answer 2

In the technical note entitled An abstract Prolog instruction set, Warren also references another compiler by Bowen, Byrd, and Clocksin. However, he says that the two architectures have much in common, so I don't know whether that compiler could be really considered as an alternative.

Urania

Answer 3

Not sure if this is what you mean, but the first two Prolog implementations were an interpreter written in Fortran by Colmerauer et al. and a DEC PDP-10 native compiler by Warren et al.

Warren mentions these in his foreword to Ait-Kaci's Tutorial Reconstruction of the WAM. If this is not what you mean, you may find it in that document or its references.

Mandate

The first Prolog implementation was written in Algol-W. The second was written in Fortran by Battani, Meloni. – Throughput

@false, Warren apparently disagrees with you. What's the source for the Algol version being first? – Mandate

Thank you for the precise reference, let me quote it. On page ix it reads: "The first implementation of Prolog was an interpreter written in Fortran by members of Colmerauer’s group." – Throughput

.. however, The birth of Prolog by Colmerauer and Roussel mention the Algol-W version. See, e.g. citeseerx.ist.psu.edu/viewdoc/… – Throughput

.. and, the very same Warren wrote some years earlier in his 1977 thesis, p.74 sect. 1.2: The first implementation of Prolog was an interpreter written in Algol-W by Philippe Roussel [1972]. This work led to better techniques for implementing the language, which were realised in a second interpreter, written in Fortran by Battani and Meloni [1973]. – Throughput