# Cactus Stack Algebraic Data Type

## "Albert Henry Tyson" <tysona@idirect.com>30 Mar 1998 21:52:19 -0500

From comp.compilers

Related articles
Cactus Stack Algebraic Data Type tysona@idirect.com (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:

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?
--

Post a followup to this message