Cactus Stack

A CactusStack is a data structure for storing ActivationRecords in a language where LexicalClosures and the like can have unlimited extent; in particular, where a closure can outlive the context it is created in.

Essentially, it's a stack with branches. When a possibly-long-lasting closure is created, it gets a new stack for its execution; the topmost ActivationRecord on this closure stack has its StaticChain pointer pointing to the context it was created in.

When the closure goes away, its corresponding branch is deleted. The portions of the original stack above the branch point are only released when all branches are no longer in use; otherwise the branches would have StaticChains pointing to garbage.

Outside the special case of branching, a CactusStack is like any other stack--it uses LIFO discipline.

The name "cactus stack" derives from the fact that the structure, when drawn on paper, bears a resemblance to a saguaro cactus--a giant cactus, indigenous to the southwest UnitedStates and much of Mexico, that is famous for growing "arms" in mature plants. Sometimes, the name "saguaro stack" is used instead.


Aside from Googling for more information (and it's out there), many programming language texts have info on cactus stacks. ProgrammingLanguagePragmatics has a nice explanation of cactus stacks.

http://www.desertusa.com/july96/du_saguaro.html :-)

EditText of this page (last edited April 6, 2004) or FindPage with title or text search