Prolog State Saving Interpreter is not strictly a graph interpreter

Is Green's Prolog State Saving Interpreter a graph interpreter, given that it goes straight from choice-point to choice-point and exits predicates directly?

ChatGPT: Short answer: SSI is close to a graph interpreter, but not purely one—it’s better described as a choice-point–driven execution graph with stack/trace semantics hybridised in.

⸻

Why it looks like a graph interpreter

From your code, especially:
• Explicit choice point trail (Choice_point_trail)
• Direct jumps via:
• ssi1(...) calls
• get_last_cp_before_n
• delete_cp, cut_cps_if_necessary
• No strict reliance on recursive call stack unwinding
• Execution moves:
• from one choice point node → another
• sometimes skipping intermediate “call frames”

This gives you:

A non-linear control flow, where execution follows edges between states (choice points) rather than returning through a stack.

That is fundamentally graph-like execution.

⸻

But it is not a pure graph interpreter

A pure graph interpreter would:
• Represent predicates as nodes
• Represent control flow as explicit edges
• Evaluate by traversing a graph structure directly

SSI still retains:

1. Predicate-oriented structure

You still have:

d(...),
e(...),
ssi1(...)

These simulate predicate calls, even if you shortcut them.

1. Embedded stack semantics

Even though you jump, you still track:
• Level
• "returns to" metadata
• Pred_id chains

This is effectively a flattened / externalised call stack, not eliminated.

⸻

1. Choice points are graph nodes, but:

They are not the only control structure.

You also have:
• Variable environments (Vars, Globals)
• Predicate identity tracking (Pred_id)
• Structured transitions (predicate vs line)

So the system is:

A graph overlaid on a logical interpreter, not a pure graph VM.

⸻

The key insight (your system’s real nature)

SSI is best described as:

A control-flow graph interpreter over a logical program, using choice points as primary nodes and explicit state transitions instead of implicit backtracking.

Or more sharply:

A compiled Prolog execution graph with manual continuation passing.

⸻

Why your observation is still important

You said:

“it goes straight from choice point to choicepoint and exits predicates directly”

That’s the crucial shift:

Traditional Prolog:
• Stack-based
• Backtracking unwinds stack frames

SSI:
• Continuation-driven
• Choice points = resumable states
• Execution = jump to next valid continuation

That is a graph traversal.

⸻

Final classification

Property SSI
Stack-based interpreter ❌ (not primarily)
Graph interpreter ⚠️ partially
Continuation-passing interpreter ✅
Choice-point graph execution ✅
Pure dataflow/graph VM ❌

⸻

Clean conclusion

SSI is not strictly a graph interpreter, but it implements Prolog as a graph of continuations (choice points), effectively behaving like a graph interpreter with residual stack semantics.

⸻

Extra insight (important for your pl2c work)

This architecture is exactly why your idea works:
• You can compile SSI to C using loops + jumps
• Because:
• Choice points → labels
• Transitions → gotos / state machine
• No need for recursion

So SSI is already:

Halfway between Prolog and a state-machine compiler IR

⸻

If you want, I can:
• Formalise SSI as a graph IR (nodes + edges)
• Or show how to compile it into pure C loops with no recursion at all