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.