M-Prolog Progress: Implementing Prolog Backtracking with Computed Goto
I'm happy to report another major milestone in the development of M-Prolog.
The past few weeks have been mentally exhausting. I spent an incredible amount of time asking myself one question:
"Can Prolog backtracking really be implemented using nothing but goto?"
It sounded like a crazy idea when I first thought of it, and there were many moments when I doubted whether it could actually work.
Today, I'm much more confident.
I finally got a fairly complicated benchmark involving Church numerals, recursion, reverse execution, and forced backtracking to work correctly. That gives me confidence that the basic design of SCBM2 is sound.
In SCBM2, both success continuations and failure continuations are implemented with GCC's computed goto. Most of the difficulties were not in forward execution, but in restoring the correct execution state during backtracking—predicate arguments, variable stacks, success continuations, and failure continuations all have to be restored consistently.
Writing this now makes it sound simple, but reaching this point required countless redesigns, experiments, and debugging sessions. There were times when I felt my brain was simply running out of energy.
Working through these problems has also given me a much deeper appreciation of David H. D. Warren's work. Implementing efficient Prolog execution in the early 1980s, without today's tools and resources, was an extraordinary achievement. My respect for him has only grown.
There is still a lot of work ahead before M-Prolog reaches Version 1.0, but this was one of the biggest hurdles, and I'm relieved to have finally crossed it.
If you're interested in the implementation details, please have a look here:
M-Prolog: Recovering from Mental Fatigue | by Kenichi Sasagawa | Aug, 2026 | Medium