|Cactus Stack Algebraic Data Type email@example.com (Albert Henry Tyson) (1998-03-30)|
|From:||"Albert Henry Tyson" <firstname.lastname@example.org>|
|Date:||30 Mar 1998 21:52:19 -0500|
|Organization:||"TUCOWS Interactive Inc"|
I would be interested in any references or suggestions concerning the
algebraic data type or the abstract data type for the Cactus stack (also
called the Saguaro stack or the Spaghetti stack).
The Cactus stack is named after the appearance of the Saguaro cactus:
! ! ! !_!
!_! ! !
For example, each ! represents the stack frame for an instance of a
procedure and in practice could be of any height. Each of the branches of
the tree represents a separate stack of frames which must coexist with
those to its left and right.
The basic stack algebraic data type is:
put: STACK[G] * G --> STACK[G]
remove: STACK[G] -/-> STACK[G] -/-> notates a partial
item: STACK[G] -/-> G
empty: STACK[G] --> BOOLEAN
For any x of type G and any s of type STACK[G]
A1 item ( put (s,x)) = x
A2 remove ( put (s,x)) = s
A3 empty ( new) is true
A4 not empty ( put (s,x)) is true
For any s of type STACK[G]
remove ( s) requires that not empty (s) is true
item ( s) requires that not empty (s) is true
The question is:
What is the specification for a Cactus stack?
Return to the
Search the comp.compilers archives again.