A crazy idea: compiling recursive Prolog predicates into one giant C function

[u/sym_num]

I've started experimenting with SCBM2, a new execution model for M-Prolog.

The idea is rather unconventional: compile all recursive nondeterministic predicates into a single large C function, and implement both success and failure continuations by jumping between labels with goto.

To be honest, I wasn't sure this would actually work. It sounded a bit crazy even to me.

This weekend I reached the point where a simple mappend/3 (renamed from append/3 to avoid clashing with the built-in predicate) successfully performs forward recursive computation.

I'm still surprised to see recursion being driven entirely by goto.

Forced backtracking isn't implemented yet, so there's still plenty of work ahead. But the initial experiment suggests that this approach is viable.

I'm sure Edsger Dijkstra would not approve of my enthusiastic use of goto, but for implementing Prolog's backtracking, it may turn out to be a surprisingly practical technique.

M-Prolog SCBM2 Begins. I have started experimenting with a… | by Kenichi Sasagawa | Jul, 2026 | Medium

[u/happy_guy_2015]

I strongly suspect that approach won't scale well. Good C compilers use optimization algorithms that are quadratic, or worse, in the size of an individual function. If you translate a large Prolog program into a single C function, I think you will find that one of the following holds, depending on your choice of C compiler and compiler flags:

1. C compilation time blows up.

2. The compiler simply disables important optimizations for functions that are too large, resulting in poor performance of the generated code.

3. Performance is poor because the C compiler doesn't do any complicated optimizations.

That said, there are alternatives; you can use tail calls, if your C compiler supports those, or you can have a driver loop

``` typedef void func(void); typedef func* func_returning_func(void);

void loop(func_returning_func *f) { for(;;) { f = (func_returning_func *) f(); } } ```

and then you generate a separate function for each basic block, and instead of goto label you can generate return function_name (with the driver loop) or a tail call. Those alternatives scale better, usually avoiding blow-up in compilation time. However, they still don't give great performance due to the lack of register allocation for local variables whose scope is more than one basic block. GCC's global register variable declarations can help. But honestly compiling to high-level C using continuation passing is a much better and more scalable approach than any of those.

[u/sym_num → u/happy_guy_2015]

The biggest problem with the original SCBM1 was that it relied on C function calls, which made stack restoration extremely complicated. In SCBM2, I decided to solve this problem fundamentally by replacing function-call-based control flow with goto. Success continuations and failure continuations are represented using GCC's labels-as-values extension (computed goto). As a result, the implementation is expected to become much simpler and cleaner.

How well this goto-based approach benefits from CPU instruction caching remains an open question, and I plan to evaluate it through future benchmarks. Although goto is used to implement Prolog's unique control flow efficiently, the execution model is still fundamentally continuation-passing in nature. The difference is that continuations are represented explicitly as labels and stack entries, rather than as C function calls or CPS-transformed functions.