Cactus Stack Algebraic Data Type

"Albert Henry Tyson" <>
30 Mar 1998 21:52:19 -0500

          From comp.compilers

Related articles
Cactus Stack Algebraic Data Type (Albert Henry Tyson) (1998-03-30)
| List of all articles for this month |

From: "Albert Henry Tyson" <>
Newsgroups: comp.compilers
Date: 30 Mar 1998 21:52:19 -0500
Organization: "TUCOWS Interactive Inc"
Keywords: theory, question

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
          new: STACK[G]

          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?

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.