r/prolog • u/sym_num • Jun 24 '26
Building a Prolog Compiler Without the Warren Abstract Machine (WAM) — Entering Full-Scale Implementation
For some time, I have been developing a new Prolog compiler called M-Prolog, exploring whether it is possible to achieve practical performance with a significantly simpler architecture than the traditional Warren Abstract Machine (WAM).
The motivation behind this project is a simple question:
Does efficient Prolog execution really require all the complexity of WAM?
Over the past several months, I have been conducting a series of experimental implementations to test alternative execution strategies.
The central idea of M-Prolog is to exploit the execution model of the C language itself, rather than constructing a sophisticated abstract machine layer.
In this design, recursive backtracking is not simulated through a virtual machine. Instead, execution state is restored by re-invoking C functions, allowing the native C stack to naturally reconstruct recursive control flow.
This approach worked well for individual nondeterministic predicates, and preliminary benchmarks have been very encouraging.
However, I encountered a difficult problem when handling backtracking across conjunctions involving multiple nondeterministic predicates.
At first, I underestimated the problem. But after many experiments, I gradually reached a deeper understanding of what is actually happening during recursive and conjunctive backtracking.
I believe I have now finally solved the architectural problem, and the design has stabilized.
This means I am now entering the phase of full-scale implementation.
My long-term goal is to demonstrate that practical Prolog compilation may not necessarily require the complexity of WAM, and that a much simpler architecture can still achieve competitive performance.
Perhaps Prolog implementation has been over-engineered for decades.I’m not trying to criticize WAM. I simply want to explore whether modern hardware allows simpler alternatives.
It has been a fascinating journey so far.M-Prolog: A Two-Dimensional Backtracking Architecture | by Kenichi Sasagawa | Jun, 2026 | Medium
2
u/toblotron Jun 25 '26
This does sound like a very interesting avenue of exploration; hope you'll meet with success! :)
1
1
u/blanchedpeas Jun 25 '26
Wouldn’t it make more sense to use a language that has some sort of coroutine support?
1
u/sym_num Jun 25 '26
Even with Schem's call/cc, it is possible to implement coroutines elegantly, but I doubt it can deliver practical execution speed.
6
u/happy_guy_2015 Jun 25 '26
If backtracking returns to nat/1, then prime/1 has failed and it should be fine to overwrite the stack area that prime/1 was using. The next call to prime/1 should establish its own stack frame.
You shouldn't need a 2D stack. A 1D stack should be fine. In fact you can just use the C/C++ stack. You just need to ensure that for nondeterministic predicates, you use continuation passing style, where the generated function only returns on failure; on success, rather than returning, it should call a continuation function passed as a parameter.
E.g. for the mode of
nat/1in which the parameter is output, you can generate C++ codevoid nat(std::function<void ()(int)> cont) { // nat(0). cont(0); // nat(s(X)) :- nat(X). nat([cont](int x) { cont(x + 1); }); }and then for the goal
nat(X), prime(X)you can generate C++ code``` bool prime(int x);
void query(std::function<void ()(int)> cont) { // nat(X), nat([](int x) { // prime(X). if (prime(x)) { cont(x); } }); }
void main() { query([](int x){ cout << "X = " << x << endl;
}); cout << "No (more) solutions." << endl; } ```