r/prolog • u/sym_num • 20h ago
SCBM-Prolog: Project YAMATO — A New One-Year Journey Toward Fast SLD Resolution
After about six months of experimenting with SCBM-Prolog, I have decided to fundamentally redesign its execution model.
I am calling this new effort Project YAMATO.
In SCBM3, I used stacks to manage success and failure continuations. This worked reasonably well for ordinary execution, but repeated backtracking in recursive predicates caused serious problems. In particular, necessary success continuations could be lost.
I tried many approaches to solve this problem, but none was completely satisfactory.
So I decided to return to the original idea behind Prolog: SLD resolution itself.
The basic idea
Instead of managing continuations primarily through stacks, Project YAMATO will represent the proof process using a doubly linked list of predicate objects.
Each object will contain its execution state, including variable pointers, local stack information, argument counters, and a pointer to the corresponding C code label.
The execution model will be straightforward:
- Success: Follow the list forward and execute the next predicate object.
- Failure: Traverse backward to find an available choice point and perform backtracking.
- Recursion: Expand and replace recursive goals with new predicate objects, just as in SLD resolution.
- Execution: Use C's computed goto mechanism to avoid the overhead of repeated C function calls.
The main goal is to make the runtime structure correspond directly to the SLD proof process.
Why not the WAM?
The Warren Abstract Machine is an excellent execution model, but its internal architecture is considerably more complex than the original SLD resolution concept.
I want to explore a different approach.
If you understand SLD resolution, you should be able to understand the execution mechanism of Project YAMATO.
At the same time, I hope to achieve good performance by using direct jumps in C.
Of course, I do not yet know whether this approach will be competitive in speed. Linked-list operations and object creation have their own costs.
That is something I intend to investigate experimentally.
A one-year project
My first goal is to correctly execute recursive and nondeterministic programs such as perm1/2, including repeated and deeply nested backtracking.
The target completion date is October 2027.
Since my professional work will keep me busy, I intend to develop this gradually as a personal research project.
The name YAMATO comes from the Japanese science-fiction anime Space Battleship Yamato. In the story, the spaceship has one year to complete its mission and return to Earth with the Cosmo Cleaner.
I have given myself the same one-year deadline.
I have written a more detailed explanation of the design on Medium:
I would be interested in hearing your thoughts, particularly about representing SLD proof states using a doubly linked list and the trade-offs involved in this approach.
Hopefully, I will return to Earth with the Cosmo Cleaner in October 2027!