Title: M-Prolog SCBM compiler now runs the N-Queens problem

After about four months of experimenting with a new Prolog compiler architecture, I finally got the N-Queens problem working correctly in compiled M-Prolog.

I call the architecture SCBM (Success Continuation Backtracking Machine).

The basic idea is fairly simple: instead of compiling Prolog to an abstract machine such as the WAM, SCBM compiles nondeterministic predicates directly into C and implements control flow and backtracking using goto and GCC's computed goto extension.

The hardest problem was restoring local variables correctly after backtracking.

After a lot of trial and error, I ended up with a relatively simple solution: variable pointers are propagated through success continuations. When backtracking occurs, local variables are reconstructed from information preserved in the original success continuation.

It took a lot of debug output to find this solution. AI was also very useful as a second pair of eyes for analyzing traces and generated C code.

The result:

• 4-Queens: all solutions generated correctly by backtracking
• 8-Queens: all 92 solutions confirmed
• 9-Queens: working correctly as well

Performance is not yet the main focus. For the complete 9-Queens search, the current implementation is roughly 3–4x slower than SWI-Prolog.

https://preview.redd.it/xkad54c7n8jh1.jpg?width=468&format=pjpg&auto=webp&s=39ad2f994ca6ecf1e2ff782b426e0e87d1c49577

https://preview.redd.it/3tscnfjkn8jh1.jpg?width=468&format=pjpg&auto=webp&s=d2fd9f0ba4b9a568d63f9c9d8fcf27380f3d180e

There is still plenty of low-hanging fruit in the implementation, particularly in data structures, pointer handling, generated code, and builtin calls, so I think there is considerable room for improvement.

For me, getting Queens working is an important milestone because it exercises recursion, nondeterminism, nested backtracking, and restoration of local variables together.

I'm aiming for M-Prolog Ver. 1.0 on August 31, 2026.

SCBM is not intended as a replacement for the WAM. I'm exploring whether a much simpler direct-to-C approach can provide another practical way to implement a Prolog compiler.

I'll be interested to hear what experienced Prolog implementers think of the approach.

I have published a follow-up on the development of M-Prolog, my experimental Prolog compiler that generates C code directly without using the WAM.

The first version of SCBM (Sasagawa & Chat Backtracking Mechanism) successfully handled recursive and nondeterministic predicates, and now executes both Church numeral prime programs and the Queens problem.

However, after extensive testing with the Queens benchmark, I discovered an important limitation.

The current SCBM reconstructs the C call stack by replaying skipped computations during backtracking. While this works correctly, it becomes increasingly inefficient for recursive nondeterministic programs with large search spaces. The first solution is found successfully, but searching for subsequent solutions requires many skipped computations, making the approach impractical.

Rather than continuing to optimize an increasingly complex design, I have decided to start the second stage of the project.

The new idea (SCBM2) completely eliminates dependence on the C runtime stack. Instead of generating C function calls, every predicate will become a label inside one large C function, and execution will proceed using goto together with an explicit SCBM execution stack managed by the compiler itself.

This should greatly simplify backtracking while allowing tail-recursive execution to become simple loops.

The article describes what worked, what did not, and why I decided to redesign the compiler architecture.

Medium article:
The Second Stage of M-Prolog SCBM | by Kenichi Sasagawa | Jul, 2026 | Medium

As always, comments and suggestions from the Prolog community are greatly appreciated.

I've been experimenting with a different approach to implementing a Prolog compiler.

For more than 40 years, the Warren Abstract Machine (WAM) has been the standard implementation technique for efficient Prolog systems. Rather than trying to improve WAM, I asked a different question:

>

This led me to an experimental architecture that I call SCBM (Sasagawa & Chat Backtracking Mechanism).

The key idea is to separate continuation information into two independent dimensions:

• recursive execution
• conjunction (non-deterministic predicate) execution

Instead of preserving the entire execution state, SCBM reconstructs previously successful execution paths during backtracking. Recursive and non-recursive non-deterministic predicates are handled differently, which keeps the generated C code relatively simple while still supporting recursive backtracking.

The current implementation successfully runs recursive examples such as append/3 and a recursive prime number generator based on Church numerals. Of course, this is still experimental, and there is much more work to do before claiming general applicability.

One interesting aspect of this project is that it was developed through continuous collaboration with ChatGPT. The architecture itself is my own design, but AI proved extremely useful for reviewing generated code, analyzing execution traces, and discussing alternative designs during implementation.

I've written a detailed description of the architecture here:

Medium:
SCBM: A New Backtracking Architecture for Direct C Compilation of Prolog | by Kenichi Sasagawa | Jul, 2026 | Medium

I'd be very interested in hearing feedback from people familiar with Prolog implementation or WAM. In particular, I'd appreciate comments on possible weaknesses, edge cases, or related work that I may have overlooked.

A few days ago, I posted here about my attempt to design a simpler Prolog compiler architecture as an alternative to the classic Warren Abstract Machine (WAM).

Since then, I have been struggling quite a bit while trying to implement the idea. For simple examples, everything worked well. However, when dealing with complex backtracking involving deeply intertwined recursion, I found myself completely stuck. At one point, I even began to wonder whether the entire idea itself was fundamentally flawed.

After spending many long hours discussing the problem with AI, I finally managed to arrive at a much simpler conceptual model.

The core idea is inspired by weaving fabric.

I began to think of recursion as the vertical threads and conjunctions as the horizontal threads. By separating these two dimensions clearly, it now seems possible to handle backtracking without the conceptual confusion that had been causing so many problems.

At last, I feel that the original idea I had envisioned is starting to take shape.

Of course, there is still a major unanswered question: whether this approach can achieve practical execution speed comparable to Warren Abstract Machine remains completely uncertain.

But after many difficult days, the design is finally beginning to look real.

I have written a more detailed explanation in my Medium article. If this sounds interesting to you, I would be very grateful if you took a look and shared any thoughts or feedback.　The Hardest Challenge in M-Prolog: Recursive Backtracking and AI as a Research Partner | by Kenichi Sasagawa | Jun, 2026 | Medium

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

I spent the entire weekend working on a very difficult problem in my new compiler for M-Prolog.

The challenge was implementing backtracking for recursive nondeterministic predicates.

After thinking about it literally all day long, debugging endlessly, and discussing the problem with AI, I finally got it working.

The test case was this simple program:

mappend([],X,X).
mappend([A|X],Y,[A|Z]) :-
    mappend(X,Y,Z).

apptest :-
    mappend(X,Y,[1,2,3]),
    write(X),
    write(Y),
    fail.

And now it correctly produces all solutions:

?- apptest.
[][1,2,3]
[1][2,3]
[1,2][3]
[1,2,3][]
no

Why this was difficult

M-Prolog compiles proof trees directly into C code.

To implement backtracking, execution returns from the predicate once, and then re-enters using goto while restoring the previous execution state.

For ordinary nondeterministic predicates, this already worked.

But recursive predicates kept failing.

The program entered infinite recursion and eventually crashed with a segmentation fault.

I kept thinking:

>

I inserted debug prints, trace steps, and tried many different ideas.

Nothing worked.

The breakthrough

Then I stopped looking at the code and asked myself:

What is append/3 actually doing during backtracking?

Consider:

mappend(R,S,[1,2,3])

First solution:

R = []
S = [1,2,3]

Backtrack.

Second solution:

R = [1]
S = [2,3]

Backtrack again.

Third solution:

R = [1,2]
S = [3]

And then:

R = [1,2,3]
S = []

Then I realized something fundamental.

The solutions are not independent.

Variable bindings are connected incrementally:

R = [] -> [1] -> [1,2] -> [1,2,3]

That was the missing piece.

I had to preserve not only the execution state, but also the addresses of variables from the previous successful state, so that when execution re-enters through goto, the previous structure can continue growing correctly.

Once I understood this, the implementation became straightforward.

Result

The final boss is defeated.

The implementation became a bit more complicated, and execution speed dropped slightly.

But correctness comes first.

Now that the hardest part is solved, I can go back to squeezing performance again 😄

Building a Prolog compiler is fun.

I have been continuing work on the M-Prolog compiler.

M-Prolog takes a different approach from traditional WAM-based systems. Instead of interpreting WAM instructions, it generates C code directly from Prolog predicates. Proof trees are translated into C control flow, and backtracking is implemented using stacks and goto-based state transitions.

After a number of recent optimizations, M-Prolog now slightly outperforms SWI-Prolog on a simple nondeterministic benchmark on my Linux Mint / AMD Ryzen system.

Benchmark program:

n(1). n(2). n(3). n(4). n(5).
n(6). n(7). n(8). n(9). n(10).

bench :-
    n(X),
    n(Y),
    n(Z),
    n(A),
    n(B),
    fail.
bench.

Executed as:

between(1,1000,_), bench, fail.

The improvements came mostly from simplifying generated code, reducing unnecessary unify/unbind operations, and generating code that GCC can optimize more effectively.

This is only a small benchmark, so I do not claim that M-Prolog is generally faster than SWI-Prolog. There is still a lot of work to do, especially for cuts, disjunctions, and more realistic programs.

My next goal is to integrate mode inference and generate specialized code for function-like predicates while remaining within standard Prolog syntax.

I first encountered Prolog around 1980, so it is very satisfying to finally see some of these ideas working in practice.

Comments and suggestions are welcome.

M-Prolog Partially Surpasses SWI-Prolog | by Kenichi Sasagawa | Jun, 2026 | Medium

A few days ago I asked for feedback about M-Prolog's compilation strategy. Thank you to everyone who took the time to comment and share references. The suggestions were very helpful.

I wanted to give a quick update on the project.

The basic idea is to compile Prolog proof trees directly into C code rather than generating WAM instructions. At first I wasn't sure whether this approach would work well for nondeterministic predicates, but after debugging and benchmarking, it now appears to be a viable approach.

Recently I focused on reducing runtime overhead. In particular, I eliminated several dynamically linked runtime calls by combining backtracking-related operations and removing unnecessary state saves. These changes significantly improved performance.

On WSL2 running on an Intel Core i7 system, M-Prolog now exceeds 40 MLIPS on my benchmark. Under the same benchmark conditions, execution time is now within about 12% of SWI-Prolog.

There is still a lot of work to do, and this is only one benchmark, so I do not want to overstate the result. However, I think it provides some evidence that direct C generation can be a practical alternative to the traditional WAM-based approach.

Thanks again for the comments and encouragement. They helped me continue exploring this rather unusual direction. M-Prolog Almost Catches Up with SWI-Prolog | by Kenichi Sasagawa | Jun, 2026 | Medium

M-Prolog: Am I missing something fundamental?

I am still not completely confident about the C code generated by the new M-Prolog compiler, so I added some of the generated C code to my Medium article.

The basic idea is to compile non-deterministic Prolog predicates by representing the proof tree directly in C code, using labels and a backtracking stack, rather than implementing a WAM-style abstract machine.

The simple test cases now seem to work correctly, and the benchmark results are encouraging. However, since this approach is different from the usual WAM-based implementation, I would like to ask people here whether I am making any major conceptual mistake.

In particular, I would appreciate comments on points such as:

- whether this way of representing choice points and backtracking in C is basically sound,

- whether there is some obvious case where this approach will break,

- whether the generated code is doing something fundamentally wrong from a Prolog implementation point of view.

I know that small examples working correctly do not prove that the design is correct. That is why I would like to hear opinions from people with more experience in Prolog implementation.

The article now includes the generated C code, so any feedback would be very welcome.

M-Prolog Reaches a World-Class Level | by Kenichi Sasagawa | Jun, 2026 | Medium

I’ve started experimental work on the new M-Prolog compiler.

The goal is to achieve practical Prolog performance by generating efficient C code, while exploring an approach different from the traditional WAM architecture.

Recently I confirmed that nondeterministic predicates and backtracking can work using a much simpler mechanism based on C stack/goto control flow and thread-local backtrack pointers.

Still experimental, but the core idea now seems feasible.

Medium article:Experimental Verification of the New M-Prolog Compiler | by Kenichi Sasagawa | May, 2026 | Medium

I wrote a short article about why Prolog may become more important in the age of AGI, not less.

Humans and LLMs both confuse similar things sometimes. A famous near-miss air traffic incident in Japan happened because controllers mixed up JAL907 and JAL958. I also recently wasted time debugging because I confused nprolog and mprolog.

This made me realize again why strict symbolic reasoning still matters.

AGI may be intelligent, but intelligence and logical exactness are different things. Prolog’s “stubbornness” may become increasingly important as a verification layer for AI systems.

Why Prolog Remains Essential Even in an AGI Era | by Kenichi Sasagawa | May, 2026 | Medium

Started a new experimental branch: M-Prolog.

The goal is to rethink compilation of nondeterministic predicates without depending on the WAM.
Instead of classic WAM-style execution, I’m exploring direct C generation using explicit Choice-Point stack control and static cut analysis.

Modern CPUs and GCC optimizers are far beyond the 1980s era when the WAM became dominant, so I think it’s worth revisiting alternative implementation strategies in 2026.

Oddly enough, drum practice helped me organize the ideas in my head 😄

Medium article: A New Concept: M-Prolog and an Idea for Compiling Nondeterministic Predicates | by Kenichi Sasagawa | May, 2026 | Medium

I implemented a prototype mode inference system for N-Prolog.

The system analyzes predicates and infers input/output modes automatically using a two-pass analysis. The current prototype can already infer modes for predicates such as partition/4, fact/2, and even qsort/3.

The long-term goal is to identify predicates that behave like deterministic functions and replace them with optimized C functions while preserving normal Prolog semantics.

Preliminary experiments show speed improvements of around 3–4x for analyzable predicates.

I wrote a technical overview here:

N-Prolog Mode Inference Prototype | by Kenichi Sasagawa | May, 2026 | Medium

I’ve been experimenting with a new optimization idea for N-Prolog.

The basic idea is:

• detect predicates that are effectively functional,
• infer their input/output modes statically,
• and compile them into simpler C-style function calls.

As a first experiment, I manually wrote optimized C code using N-Prolog’s embedded C feature and compared the performance against the normal predicate execution path.

Benchmark: qsort repeated 10,000 times.

N-Prolog 5.19:

?- measure(run(qsort,10000)).
Elapsed Time=0.326355 (second)  15749722(LIPS)

SWI-Prolog:

?- time(run(qsort,10000)).
% 6,160,005 inferences, 0.358 CPU in 0.358 seconds
% (100% CPU, 17189389 Lips)

The optimized version became roughly 3–4x faster than the ordinary predicate-oriented execution path.

The motivation is that many Prolog programs contain predicates that are logically relational, but operationally behave almost like functions. qsort is a typical example.

If such predicates can be detected automatically through mode inference and static analysis, they may be compiled into much simpler execution paths while still preserving ordinary Prolog semantics for general predicates.

I’m currently working on the design of the mode inference engine itself.

Notes and experimental code are in mode.pl if anyone is interested.

I’d also be interested to hear whether similar ideas were explored historically in Prolog systems beyond the usual Mercury-style mode systems.

Recently I had an interesting realization while practicing drums.

I’ve been trying to play Burn like Ian Paice, and I discovered that fast drumming is not about brute force. The key is eliminating unnecessary motion and using rebound efficiently.

Oddly enough, this led me to rethink optimization in my Prolog compiler.

About a year ago I introduced TCO into N-Prolog and achieved decent performance improvements for nqueens. However, qsort still resisted optimization because predicates like partition/4 appear relational:

partition([X|L], Y, [X|L1], L2) :-
    X < Y, !, partition(L, Y, L1, L2).

But then I realized something important:

These predicates are only partially relational.

For example:

?- partition(X,2,[1],[2,3]).
X = [1,2,3].

This “reverse execution” works only incompletely. In practice, predicates like this behave much more like one-way functions than true relations.

I started calling them mut (“mutants”): predicates syntactically written in Prolog form, but whose computation direction is essentially fixed.

That opens an interesting possibility.

Instead of compiling everything into general relational machinery with full unification/backtracking overhead, mut predicates might be statically analyzed and translated into simple C functions.

In other words:

• ordinary relational predicates remain Prolog
• function-like predicates become optimized function code

I suspect operators such as <, arithmetic constraints, and mode usage may allow automatic direction inference.

Ironically, I originally tried to overcome this performance wall with parallelism. Now I’m beginning to think that removing unnecessary generality may be the more important optimization.

Drumming and compiler optimization turned out to share the same lesson:
eliminate unnecessary movement.

The Road to Speeding Up N-Prolog. After finishing the stress tests and… | by Kenichi Sasagawa | May, 2026 | Medium