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

Question

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.

1. 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.

2. 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)]
                                   ^                     |
                                    `---- [frame Y] <---´
   

   For example, I can imagine that frame Z belongs to some decision function, which either continues with frame X or frame Y (either of which would return to W). This means that spaghetti call stacks aren't "parent pointer trees".

3. However, I can't imagine any situation where a loop can be constructed. Take the following situation, for instance:

   [exit point] <-- ... <-- [frame P] --> [frame Q (active)]
                                   ^             |
                                   |             v
                                    `---- [frame R]
   

   I know that recursive bindings are a thing, but I highly doubt that this is sensible. If Q were to return to R, frame Q is "spent". If R were to return to P, and P can't simply return to Q, since it would need to be reinitialised first. As such, loops would cause inconsistent states. (Unless, of course, I misunderstand the purpose of this data structure, and you'd only use the nodes in it as a template for your current frame.)

From these observations, I have to conclude that a spaghetti call stack (without garbage) is actually a DAG. Is this correct? Or am I misunderstanding the purpose of this data structure?

---

Updates:

• I've skimmed through a copy of the following paper:

  E. A. Hauck and B. A. Dent. 1968. Burroughs' B6500/B7500 stack mechanism. In Proceedings of the April 30--May 2, 1968, spring joint computer conference (AFIPS '68 (Spring)). ACM, New York, NY, USA, 245-251. DOI=http://dx.doi.org/10.1145/1468075.1468111

  This paper seems to define the Suguaro Stack System. As it turns out, this Suguaro Stack System is a traditional call stack that allows multiple "jobs" to walk through the frames of a partially shared stack; it is absolutely not related to continuations.

• The following paper (and its 1996 companion paper) apparently explains what's going on in the SML/NJ compiler:

  Zhong Shao and Andrew W. Appel. 2000. Efficient and safe-for-space closure conversion. ACM Trans. Program. Lang. Syst. 22, 1 (January 2000), 129-161. DOI=http://dx.doi.org/10.1145/345099.345125

  I think I should read this paper (copy on author's website) before doing anything else with this question. The "Safely Linked Closures" concept is very similar to the Suguaro Stack System, in that it's always very shallow and only intended to share free variables:

  Our new closure-conversion algorithm uses safely linked closures (the 3rd column in Figure 1) that contain only variables actually needed in the function but avoid closure copying by grouping variables with the same lifetime into a sharable record. [...] Unlike linked closures, the nesting level of safely linked closures never exceeds more than two (one layer for the closure itself; another for records of different life time) so they still enjoy very fast variable access time.

  The paper also explicitly mentions that it doesn't use "any runtime stack":

  Instead, we treat all activation records as closures for continuation functions and allocate them in registers on in the heap.

  I'm think I misunderstood and/or misread the Wikipedia article, since spaghetti stacks are not used for flow control. However, after careful reading of the papers by Appel and Shao, I could perhaps restate the question in reference to the dependency graph of closures rather than the "spaghetti call stack" (which apparently isn't a thing).

Answer 1

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.