Log in

No account? Create an account
penrose orange



cat /var/log/stephen >/dev/eyes

Pushing and popping all the day long
penrose orange
Computers don't generally have dedicated stacks. They have blocks of memory, and that's all. (Most processor architectures do reserve an address register for use as a stack pointer, but it's just a pointer into the main memory. The same memory is addressable in other ways too).

Here's a very simple implementation of a stack in C. It's just for illustrative purposes; no-one would code a stack like this in a real program.
#define STACK_SIZE 4096
static int stack_index;
static int stack[STACK_SIZE];

int s_push(int item)
   if(stack_index == STACK_SIZE)
      return 0;

   stack[stack_index++] = item;
   return 1;

int s_pop(int *item)
   if(stack_index == 0)
      return 0;

   *item = stack[--stack_index];
   return 1;

(This implementation sucks because it's fixed size. Even if only a few entries are in use, it's still consuming [4096 int sizeof *] bytes of memory. And if someone manages to push that many ints, they're stuffed. s_push() just start returning 0 until some space is cleared by removing some items. Like I said, it's just an illustration).

Since the RPN calculator now has an addressable heap, I figured that it should be possible to write functions that simulate a stack in the same way as the above C code. There's no need to, of course. If there's one thing that the RPN calculator isn't short of, it's stacks. But hey.

Here are functions hpush and hpop, implementing the heap-based stack:
: hpush 1+ 1000 * dup dup load 1+ tuck swap store + store ;
: hpop 1+ 1000 * dup dup load tuck 1- swap store + load ;

The syntax is v n hpush to push value v onto heap-based stack number n, and n hpop to pop the value from the top of heap-based stack n.

Here's a breakdown of how hpush works. We'll assume that the top of the stack initially looks like 47 0; we're pushing 47 onto stack 0.
  1. 1+ 1000 *: increments the value on the top of the stack by one, then multiplies by 1000. The stack now contains 47 1000. 1000 is the heap address of the start of heap-stack 0. 2000 would be the start of heap-stack 1, 3000 would be the start of heap-stack 2, etc. The first address contains the heap-stack depth; the remaining 999 are used for the heap-stack entries.
  2. dup dup: duplicates the 1000 twice. The stack now contains 47 1000 1000 1000.
  3. load: retrieves the value from heap location 1000. This is the heap-stack size, initially zero. The stack now contains 47 1000 1000 0.
  4. 1+ tuck: increments the heap-stack size, and copies it below the penultimate stack entry. The stack now contains 47 1000 1 1000 1.
  5. swap store: exchanges the two items on the top of the stack, so that 1000 is on top and 1 is penultimate, then stores the 1 in heap address 1000. In other words, we've incremented the heap-stack depth variable and stored it back in its heap location. The stack now contains 47 1000 1.
  6. +: adds the incremented heap-stack depth to the last remaining 1000 on the stack, yielding the address of the next free heap-stack cell. The stack now contains 47 1001.
  7. store: stores 47 in heap address 1001.

hpop does pretty much the same thing, in reverse.

Since the RPN calculator has no conditionals, stack overflow and underflow can't be detected. Underflow is quite fun; it results in -1 being written into the heap-stack depth; and since the depth is stored immediately in front of the heap-stack, a subsequent hpush overwrites the depth with whatever you push, meaning that any further pushes and pops go off into la-la land.

In other news: no Valentines. The above geekitude is probably part of the reason why...