30 Mar 1998 21:52:19 -0500

Related articles |
---|

Cactus Stack Algebraic Data Type tysona@idirect.com (Albert Henry Tyson) (1998-03-30) |

From: | "Albert Henry Tyson" <tysona@idirect.com> |

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.