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)] ^ | `---- [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".
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).