Cactus Stack Algebraic Data Type

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:


TYPES
          STACK[G]


FUNCTIONS
          put: STACK[G] * G --> STACK[G]
          remove: STACK[G] -/-> STACK[G] -/-> notates a partial
function
          item: STACK[G] -/-> G
          empty: STACK[G] --> BOOLEAN
          new: STACK[G]


AXIOMS
          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


PRECONDITIONS
          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 comp.compilers page.
Search the comp.compilers archives again.