When used as call stack, do garbage-free spaghetti stacks form a DAG?

I'm looking into implementation techniques for programming
languages, and recently came across spaghetti stacks, which are
supposedly a good fit for a continuation passing style model
(given their use in e.g.
Scheme and SML/NJ).
For sake of simplicitly, let's only consider a single-threaded
processes for this question.

However, I'm a bit confused by the
diagram on Wikipedia
(also found elsewhere).
In particular, I don't understand how such a situation can arise.
I can only imagine that the grayed-out branches are unreachable
and should be garbage-collected. On the other hand, with my
vague understanding of how to implement CPS using spaghetti
stacks, I can't imagine how you could ever get a loop in that
structure. I have to conclude that, rather than a "parent-pointer
tree", it's actually a directed acyclic graph, with as many
non-garbage sources as there are threads, and as many sinks as
there are (potential) "exit points".

But my understanding of this implementation is pretty vague, so
I guess I'm probably missing something. I hope someone can
enlighten me here on "spaghetti call stacks", by which I mean
the data structure as used in Scheme and/or SML/NJ to implement
CPS-based processes.

-
Given the following spaghetti call stack:

[exit point] <-- ... <-- [frame A] <-- [frame B (active)]
                                ^
                                 `---- [frame C]

As far as I understand, any flow control from B either unwinds
the stack by jumping to a parent (A becomes active, unreachable
B is now garbage), or replacing the active frame by a subgraph,
connected only using references held by B or references to
the new frames. Execution can't flow to frame C, which must
mean that frame C is garbage.

-
Rather than the previous situation, I'd think that the following
garbage-free situation may arise:

```
[exit point] <-- ... <-- [frame W] <-- [frame X] <-- [frame Z (active)]
^ |

Are Spaghetti Stacks Parent-Pointer Trees?

Yes, spaghetti stacks are parent-pointer trees. You can think of a spaghetti stack as having the same structure as a collection of single-linked lists which share structure. When viewed as a whole, the collection of lists form a tree. But when viewed individually, each list forms a stack.

Each process in the system will have one of these lists, which represents its control stack. The head of the list is the top of the stack (i.e., active frame).
Its next pointer references the parent frame.

What you see in the diagram is the structure for multiple processes. The stack for the "active" process is highlighted. The portions of the tree that are not part of the active stack are grayed out. These represent stacks for other processes.

Do Spaghetti Stacks Form a DAG?

Since Spaghetti stacks are parent-pointer trees, they are indeed DAGs. But only DAGs that are also trees can be Spaghetti stacks. So no, Spaghetti stacks do not form DAGs that are not trees.

Your example of a decision function conflates the structure of a control stack with the data stored in the stack. Certainly, any structure could be formed if we start considering the data. But as a datastructure, each node in a spaghetti stack will have exactly one parent.

StackExchange Computer Science Q#60381, answer score: 3