I follow the Hassan’s reconstruction manual (now at page 24 of 129) and it seems short and nice but hard in some way.
I’m an experienced Java software engineer
I take you are referring to
“Warren’s abstract machine : a tutorial reconstruction” by Hassan Aït-Kaci (WorldCat)
How many days will it realistically take to code up a working prototype of WAM (without optimization)?
As for the timeline, it depends heavily on your experience. For someone already comfortable with Prolog internals and abstract machines, it might take a few weeks. For others, it could take significantly longer, or remain incomplete.
Even assuming you do get a prototype working, the more difficult question is how you would establish its correctness?
Once you get to the level of the ISO core standard, it should be easy enough to get Logtalk running and use its pretty extensive test suite. The real question IMO is “why would you”? There are plenty of Prolog engines out there and while getting the basics to work is pretty easy, getting it to scale, properly optimized, provide a debugger, foreign language interface, supporting more modern features such as constraints or tabling is pretty involved. Why not take an existing Prolog system and if it does not exactly what you want, collaborate with the developers to improve it? It saves you a lot of time and works towards fewer sustainable implementations rather than more unsustainable ones.
Writing a WAM is probably easier than writing a decent compiler from Prolog to WAM (I did both for a master’s thesis a long time ago). Also, there are quite a few built-in predicates that need to be implemented.
You might want to look at Peter Van Roy’s thesis on the Aquarius compiler.
(If you want to deal with just pure Prolog, it’s somewhat easier; “cut” can be tricky to get right, for example)
See also: https://www.ps.uni-saarland.de/Publications/documents/VanRoy_SequentialPro.pdf
Is this what you are referring, or was it close and you had something else in mind?
Knowing about the extensive test suite, this might be a good test for a Long-Horizon project for an LLM.
For any one thinking about doing this, it is not uncommon for these sorts of projects to run for a few days and cost several thousand dollars in tokens. However if you write a well defined prompt with the right details, you might get it done with just a few hundred dollars of tokens.
Years ago I started keeping track of task that LLMs just failed at and year after year they would fail at being able to create useful SWI-Prolog code, starting with Claude Sonnet 4.5 that changed. Now both OpenAI and Anthropic models can create SWI-Prolog more or less.
So the next tasks for LLMs that I am starting to track are Long-Horizon tasks, this looks to be a good candidate.
One reason I mentioned earlier is using it as a test case for a long-horizon task.
Another practical motivation is that many programmers currently aim to migrate systems to Rust, or to rebuild them from the ground up using it.
From a different angle, I would be interested in exploring whether a WAM—or another Prolog engine—could be implemented in Lean 4 alongside formal proofs. I do not yet know what the full set of required proofs would look like, but the exercise itself would likely be a valuable learning experience.
Thank you very much
My main goal is educational purpose: to have 100% understanding of Prolog engine. It is only possible if I code it up from scratch. I’ve already implemented a working interpreter using ISO standard part I model (stack-based) as a reference, but from time to time I feel like this part of the standard (7.7 Executing a Prolog goal) has some deep flaws and their model isn’t very codable, but I can be wrong.
I thought that WAM can bring me deeper conceptual understanding, but now I’m not sure. Maybe it is better to continue with ISO model and think about it deeper.
Can you recommend me a Prolog execution model or engine which is the best one for understanding/educational purposes/pedagogical clearness and neatness? No need to be the fastest one
Better write a new tutorial that shows WAM with sharing,
or more flexibly heap sharing, or even a WAM with some
forms of interning, maybe taylored towards ground terms.
It could be that in the age of Explanation such a WAM
is needed. Just judging from the recent ErgoAI paper,
and some problems and benchmarks mentioned there.
The standard WAM is already very close to heap sharing, you
have only to change the sequential heap here, to a more
non-sequential heap with garbage collection (sic!):
A Verified Prolog Compiler for the Warren Abstract Machine
David M. Russinoff - 1992
https://www.russinoff.com/papers/wam.html
In the above there are two types of variables already,
in the memory model, and for other reasons there is
also a forking in the instructions.
BTW: The ErgoAI paper has an interesting table:
I suspect ErgoAI does automatically explanation,
and my hypthoses it can be done cheaper by a
clause reference stored in the answer cache of tabling.
Could this be the beginning of new WAMs, like from
@stassa.p ILP colleague his Prolog^2 ? WebPL has
already a set of laws for its heap WAM but more towards
constraint logic programming and shunting of attributed
variables. Not sure whether WebPL can do XSB WAM.
SWI Prolog can also do garbage collection, aka environ-
ment triming, but interning needs links to and from clauses.
The compromise could be indeed CHR, this would explain
SWI resilience against other WAMs. But CHR might also lack
interning features, like when it comes to indexing, especially
hash based ones. You could test the CHR performance question
via Egraph problems. Didn’t do that yet, little rusty with CHR.
Well, this paper started SWI-Prolog. It is really easy to implement and describes Prolog compiled into 7 instructions. Currently SWI-Prolog has over 200 instructions in its VM 
Is your goal to learn the virtual machine instructions that power a Prolog implementation or to understand Prolog?
When I learned Java I also took a similar route to understand the JVM and while it was nice to know the only practical piece of information I learned from months of work was that the JVM did not implement tail recursion, they may have done it since.
The other thing about learning Prolog is that there is text book Prolog code and real world Prolog code. The only book that actually helped with real world Prolog coding was The Craft of Prolog by Richard A O`Keefe (WorldCat)
Also see:
You might find the history section of value.
What I do for a hobby, I sometimes list the instructions via
vm_list/1. You can do the same for Scryer Prolog with their library
library(diag). I find that SWI-Prolog might have probably
started with more than 7 instructions, since the 7 instructions
only work when you have already a Prolog system, running
them inside a Prolog system, emulating a Prolog inside a
Prolog. So variables have not only one instruction as in the original
ZIP, by A Portable Prolog Compiler, Clocksin et al. from 1983.
But if you list a code example suddently instructions fork:
rev(cons(H,T), R) :- rev(T, J), app(J, cons(H,nil), R).
into pairs, in the case of SWI-Prolog:
?- vm_list(rev).
0 h_functor(cons/2)
2 h_firstvar(2)
4 h_firstvar(3)
6 h_pop
7 i_enter
8 b_var(3)
10 b_firstvar(4)
12 i_call(rev/2)
14 b_var(4)
16 b_functor(cons/2)
18 b_argvar(2)
20 b_atom(nil)
22 b_pop
23 b_var1
24 i_depart(app/3)
26 i_exit
And also in the case of Scryer Prolog:
?- wam_instructions(rev/2, Is),
maplist(portray_clause, Is).
allocate(3).
get_structure(level(shallow),cons,2,x(1)).
unify_variable(y(1)).
unify_variable(x(3)).
get_variable(y(2),2).
put_value(x(3),1).
put_variable(y(3),2).
call(rev,2).
put_unsafe_value(3,1).
put_structure(cons,2,x(2)).
set_value(y(1)).
set_constant(nil).
put_value(y(2),3).
deallocate.
execute(app,3)
So the SWI ZIP becomes WAM-ish having h_XXX (head) instructions
and b_XXX (body) instructions, just like Scryer Prolog has
get_XXX/unify_XXX instructions and put_XXX/set_XXX instructions.
This has to do that the ZIP was designed for Prolog emulation
in Prolog, while the WAM is more designed for a less declarative
and thus less flexible target, something that is fed with more hints.
It is possible to code directly in opcodes of JVM (Jasmin project) and also decompile your class files with javap command. I coded in pure JVM opcodes here and I feel it was useful. I also enjoyed x86 assembler programming when I was a kid. As a result, I decided to try WAM to code directly in opcodes but it doesn’t seem to be so helpful or maybe I just lack of understanding and need to invest more time
Hi,
Writing your own WAM, can be quite an enjoyabe project,
and you can even gain considerable performance, as the
Rust WebPL project showed inside the web browser.
Every WAM, at some moment, routes into a unification routine.
And you might experience the benenfit of the particular WAM
memory model, possibly also adopted by SWI, which is quite
good at variable backfixes. In the below the variable T, is
such a backfix of a cons cell in the second clause. This is
an example clause set such as for the usual append/3 predicate:
app([], X, X).
app([X|Y], Z, [X|T]) :- app(Y, Z, T).
If you call app([], S, T), the Prolog system has to do a
unification with what ever Prolog terms S and T come along,
and the unification has to be trailed. Do you intend to support
rational trees, or will you have an occurs check?
Exercise 2.2 (pg. 14)
Trace the effects of executing unify(a1, a2)
https://github.com/rm-hull/wam#exercise-22-pg-14
Bye
P.S.: The obsession with variable backfixes and the tagged
memory model, is also one of the weaknesses of the WAM
model, and makes it more difficult to use the provided objects
of a programming language such as Java. Java itself is also
a programming language that doesn’t support cheap interior
pointers to arrays making variable backfixes unrealistic, unlike
assembly approaches using your own memory model.
Unfortunately the history does not go back that far. If I recall correctly though, I started with the original 7 instructions (as long as you initialize the variables there is no need for distinct head and body instructions) and compiling the Prolog compiler using Edinburgh C-Prolog. Next I wrote a simple read/1 and write/1 in C, so I could actually run Prolog The rest is history
Good to hear.
Please do not take my earlier replies as discouragement. They are intended more as cautionary notes—this is a path many start but relatively few complete. That said, it is also one of those efforts where the value often lies more in what you learn along the way than in the final result.
One additional point worth noting: many of the people responding in this thread have decades of experience. It would not be surprising if the combined experience represented here exceeds a century. There is a substantial amount of hard-earned perspective behind the feedback.
Since you have already explored assembly, JVM opcodes, and other low-level or virtual machine models, you may also find the following resources relevant:
The title and description of the second resource do not fully convey its practical value. It provides a solid, ground-up understanding of how Lambda Calculus is applied in real systems. If you are interested, this older discussion gives additional context:
One additional option for tackling the more difficult parts is to use an LLM-based coding tool, such as OpenAI Codex or Claude Code.
In my experience, there have been projects where I was blocked for years; with the assistance of these tools, I was able to overcome a key hurdle and continue making progress.
Yeah, could probably get quite a long way with some C-code that
realizes some primitives with multiple modes, like arg/3, functor/3
and (=..)/2. As a side benefit you could also already provide them
as built-ins in your Prolog system. One difficulty with A PORTABLE
PROLOG COMPILER by Clocksin et al., its formulated tail recursive.
But many implementations end up realizing a “trampolin”, i.e. turning
the tail recursive solution into an iterative solution, with success
and failure outlets. Maintaining a continuation and choice points,
I think the Prolog^2 WAM recently described that again.
The choice point can be located in the A PORTABLE PROLOG
COMPILER by Clocksin et al. Prolog emulation at this
member/2 call inside arrive/3:
In this respect, the WAM is more explicit about choice points.
Choice points give rise to the try_XXX, retry_XXX and trust_XXX
instructions. The original ZIP has no such instructions. Its also
quite difficult to describe a Prolog “trampolin” in Prolog itself.
The A PORTABLE PROLOG COMPILER by Clocksin et al.,
when it backtracks back to member/2, it has also backtracked
back over the “make new variables” step, and already untrailed
variables, and reinitialized variables, and it has also undone the
execute. In a WAM this happens more explicitly, and is also
part of the choice point mechanism.
Some equivalents also exist in SWI-Prolog. But they are not
so much seen for clauses, since for clauses there is a
supervisor architecture. But if you use a local disjunction:
test(X) :- (X=a; X=b).
You see it:
?- vm_list(test).
0 i_enter
1 c_or('L1')
3 b_unify_vc(0,a)
6 c_jmp('L2')
L1: 8 b_unify_vc(0,b)
L2: 11 i_exit
The instuction c_or is described in pl-comp.c:
C_OR jmp Generate a choicepoint. It the continuation
fails skip `jmp' instructions and continue
there.
https://github.com/SWI-Prolog/swipl-devel/blob/master/src/pl-comp.c
Possibly pl-wam.c also contains choice point stuff.
I think that implementing a compiler to WAM (or similar, such as the 7 instruction machine) is more useful than implementing WAM – you’ll learn about the WAM by doing this and also learn about the issues involved with compiling Prolog. I don’t know if there’s an existing WAM implementation that you could use as a target (I don’t have the Hassan Aït-Kaci’s paper handy - I vaguely recall that it has at least pseudo code for the WAM instructions).
Basically you can do it in one day, I suspect. Its straight forward.
Since it doesn’t have cut (!) and clause/2 you could do it in one day.
For example using the numbervars/3 trick.
The ZIP paper with the 7 instructions, has a subset 4 instructions
called “data” instructions, these are already good to unify with the
head of a clause and to instantiate a clause.
The rest of the instructions, 3 more, of the ZIP make the ZIP
interesting, because the ZIP shows how to realize last call
optimization. But you can also run code without them.
Compiling the 4 “data” instructions can be done with
numbervars/3 and utilizing DCG, taking the first solution
of data/3. Your data should not contain $VAR(n) already:
data('$VAR'(K)) --> {integer(K)}, [var, K].
data(C) --> {compound(C), functor(C, F, N)},
[functor, F/N],
{C=..[_|L]},
data_list(L),
[pop].
data(X) --> [const, X].
data_list([]) --> [].
data_list([X|L]) --> data(X), data_list(L).
?- T=f(X,g(a,X),b), numbervars(T, 1, _), data(T, L, []).
L = [functor, f/3, var, 1, functor, g/2, const, a,
var, 1, pop, const, b, pop]
The paper doesn’t show these things, in A Portable Prolog Compiler,
Clocksin et al. from 1983 we merely find only a description
of the intermediate language (IL) and its execution and less
how to compile it. But one can sense the vibe of the paper,
and the facination of having created something inbetween
interpreter and compiler. Whats also missing is the cut (!),
but the code is reversible. One can easily implement clause/2,
and turn the “data” back into a clause by “executing” it
in a special way so as to obtain the body instead running it.
BTW: Historical bit, the intermediate language was designed
for Prolog-X, right? But at one moment of time Prolog-X was
ditched, so we have only the intermediate language surviving.
Not quite, the software preservation group has more resources:
Prolog-X
“Prolog-X was designed just before I left Edinburgh in 1980.
[..] The first version of the Prolog-X system was written in
Pascal under VMS for the DEC VAX in 1982.”
https://softwarepreservation.computerhistory.org/prolog/#Edinburgh
You find in the above, that the intermediate language had even a
prototype adding a microcode for a hardware emulator ORION.
This was all around the time of the Japan Fifth Generation Project.
The first version of SWI-Prolog implemented it as a foreign predicate that manipulated the choice points. That is not so hard.
That is a key feature that is still maintained in SWI-Prolog. assert/1 is pretty much the standard compiler with some options disabled. clause/2 does decompilation. Dynamic predicates are not significantly different from static predicates and clause/2 works both on dynamic and static code. As static code is not so different from dynamic code, we can easily implement hot swap, i.e., recompile code while the code is running in another thread. The ZIP also easily implements a debugger without specializing the code or interpreting it.
The downside is that some operations remain a bit slower. Notably tail calls, although recent versions reduced the gap significantly by introducing two sets of instructions for the last call, one that creates a new frame and one that manipulates the running frame for running the tail call.