Browse Prior Art Database

Method for Efficient Stack Usage using a Unique Stack Exception

IP.com Disclosure Number: IPCOM000116611D
Original Publication Date: 1995-Oct-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 2 page(s) / 77K

Publishing Venue

IBM

Related People

Johnston, GM: AUTHOR

Abstract

A new type of stack and its use are disclosed. A new type of stack was implemented which signals a unique exception when underflow occurs. Because this exception is distinguishable from all other runtime exceptions, it is useful for the programmer to catch it in code. This allows the programmer to remove all stack checks from the code in many, if not most, iteration loops which are based on the use of a stack. Instead, the iteration code can be enclosed within a block which catches the unique stack underflow exception when it occurs.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 53% of the total text.

Method for Efficient Stack Usage using a Unique Stack Exception

      A new type of stack and its use are disclosed.  A new type of
stack was implemented which signals a unique exception when underflow
occurs.  Because this exception is distinguishable from all other
runtime exceptions, it is useful for the programmer to catch it in
code.  This allows the programmer to remove all stack checks from the
code in many, if not most, iteration loops which are based on the use
of a stack.  Instead, the iteration code can be enclosed within a
block which catches the unique stack underflow exception when it
occurs.

      A "stack"  is a frequently used abstract data type whose basic
operations include push, pop, top, and isEmpty.  In Smalltalk, a
stack is implemented by class Stack, which provides the methods
#push:, #pop, #top, and #isEmpty.  Many other languages
(object-oriented and otherwise) also include an implementation of
stack.  Hereafter, stack is referred to in the context of Smalltalk,
but it applies equally well to other languages as well (e.g., C++).

      A Stack  is often used in the context of an iteration loop in
which some set of actions is taken within the body of the loop.  The
specific actions taken depend on the value on the top of the Stack,
and possibly on other state information.  These actions might include
#push:  and/or #pop  operations on the Stack  itself.  Examples of
this include parsing and syntax analysis engines and execution
engines of interpreted languages.

      Such a loop typically needs to terminate when the Stack
underflows or becomes empty; therefore, one must check for this
condition at the beginning of each iteration.  In addition, if the
actions performed during an iteration include a #pop  operation, the
check must usually be done at this point as well.

Example using traditional Stack:
  | stack |
  stack :=  Stack new.
  "Loop until stack is empty."
  (stack isEmpty) whileFalse: (
    .
    .
    .
    "Code here does #push:  and/or #pop  operations,
     but stack must be checked before each #pop
     to ensure that underflow does not occur."
    .
    .
    .
   ).

This arrangement has at least three problems:
  1.  The checks introduce additional overhead into each loop
       iteration.  If the loop is coded ve...