Popping a Register from a Stack: QuickPiet Macros

Piet slide deck on Prezi.com

And now for something completely different …

Back in March I went crazy.  I spent WAY too many nights hacking in David Morgan-Mar’s Piet programming language.  Piet programs are bitmaps which are executed as a “pointer” traverses the image.  To make matters even worse, the underlying native commands only allow the program to use a single stack for storage.  Nothing else.  The original goal was to learn enough to put together an interesting and funny presentation for the Esoteric and Useless Languages April Fool’s Day meeting of the Lambda Lounge user group here in St. Louis.  In the end I think I succeeded but you can be the judge for yourself.  My slide deck can be found Prezi.com and a video of my talk can be found on blip.tv (Thanks to Alex Miller for recording it).  You can also find some other posts on Piet and the subset language I created QuickPiet here.

The most surprising outcome of all that image editing and eye-crossing stack tracing was a completely inappropriate desire to build more and more complex programs with the very basic tools [Quick]Piet offers. I became consumed with thoughts of how to replicate higher level ideas and abstractions built on top of a single stack. I am sure most of my work could easily be explained and improved upon in any Finite Automata or Language Theory textbook … but I wanted to do it myself.

My Piet Presentation @ Lambda Lounge (blip.tv)

When you only have a stack to work with, you realize you don’t have much.  Our ability as software developers to add layers of abstraction is such a powerful tool.  Without abstractions the entire complexity of an application has to fit into a developer’s head.  With only a stack, even small tasks are difficult because the entire state of the application has to be maintained as each command is execute.  I quickly realized that I needed a way to have stationary registers or variables that could hold data throughout the life-cycle of a program without me needing to know where they were on the stack constantly.

My solution was to keep track of the size of the stack.  Simple no?

Imagine a stack full of values.  The only constants of a stack are the top and bottom.  If we want to hide some registers inside our stack, it makes sense to keep them at one of the ends.  Only one problem: the top is highly volatile and we have no idea where the bottom is.  My idea was to keep the current size of the stack as the top most element on the stack at all times.  If you always knew the top value was the “size” of the stack, then when you first start your application you could stash a few extra values down in the “negative” and use these values as registers/variables throughout your application.  This leads to one big hurdle: how can we keep track of the stack size as we execute our program?

After a lot of soul searching and too many crumpled of pieces of notebook paper to count I conjectured that you could recreate all of the native stack commands that Piet offers as macros that would maintain and update the stack size as you went.  A Piet Developer (are there any other than me?) would simply need to work with these macros instead of the native commands and could build out new macros which would leverage that stack size to retrieve and store values from the registers.  Abstraction for the win.

Code examples from my proof of concept JavaScript implementation

this.push_ = function(x) {  // macro stack-size-aware PUSH command
  this.push(1);
  this.add();  // update stack size value

  this.push(x); // perform actual PUSH

  this.push(2);
  this.push(1);
  this.roll(); // roll new value to below stack size
};

this.dup_ = function() {    // macro stack-size-aware DUP command
  this.push(1);
  this.add();  // update net stack size value

  this.push(2);
  this.push(1);
  this.roll();  // hide stack size value under top stack value

  this.dup();  // perform actual DUP (creates new duplicate value on top of stack)

  this.push(3);
  this.push(2);
  this.roll(); // roll up stack size value from its hiding place
};

Several hours later I had built macros which mimicked all of the more basic commands which would preserve the stack size value (e.g. PUSH, POP, ADD, SUB, etc).  Each macro was 5 – 10 native commands depending on the number of stack values changing at a time.  The hard part came when I wanted to build a new ROLL command.  This command differed from all of the others since the area of the stack effected by executed the command depended on the input values.  All of the other commands effected a fixed number of values (e.g. PUSH always nets a single new value on the stack).  So while most macro-commands could be built with useful assumptions about how many values were changing, ROLL needed to effect a variable amount of the stack to varying depths.   When it was all said and done, my new ROLL command was more than 30 commands!

  this.roll_ = function() {
    // decrement counter
    // # -> (# - 2)
    this.push(2);
    this.sub();

    // find roll offset (iterations mod depth)
    // a b # -> # a (b % a) (b % a)
    this.push(3); // a b # 3
    this.push(1); // a b # 3 1
    this.roll();  // # a b
    this.push(2); // # a b 2
    this.push(1); // # a b 2 1
    this.roll();  // # b a
    this.dup();   // # b a a
    this.push(3); // # b a a 3
    this.push(1); // # b a a 3 1
    this.roll();  // # a b a
    this.mod();   // # a (b % a)
    this.dup();   // # a (b % a) (b % a)

    // find depth for count (offset + 2 + 1)
    // o -> (o + 3)
    this.push(3); // o 3
    this.add();   // (o + 3)

    // roll count to proper depth within roll area
    // # a b X -> # ...X... a b
    this.push(4); // # a b X 4
    this.push(3); // # a b X 4 3
    this.roll();  // a b X #
    this.push(2); // a b X # 2
    this.push(1); // a b X # 2 1
    this.roll();  // a b # X
    this.push(1); // a b # X 1
    this.roll();  // # ...X... a b

    // increase depth by one
    // a b -> (a + 1) b
    this.push(2); // a b 2
    this.push(1); // a b 2 1
    this.roll();  // b a
    this.push(1); // b a 1
    this.add(1);  // b (a + 1)
    this.push(2); // b (a + 1) 2
    this.push(1); // b (a + 1) 2 1
    this.roll();  // (a + 1) b

    // roll to finish?
    this.roll();
  };

Since a ROLL command has a variable depth the basic solution is to calculate how deep things are going to end up (iterations mod depth) and hide the stack size value in the middle of the roll’s depth and roll to a depth one greater than originally requested.  This should leave the stack size value at the top of the stack once again and everything else where it should be.

You can find my implementations of all macros in this gist hacked together in a small html file with JavaScript. I might be crazy, but damn it I did it. With these macros registers are possible (assuming you know how many registers you need at “compile time” — although an infinite amount is theoretically possible).  It seems like this is the first big step to a proof of Piet’s Turing completeness …. but that is a task for another day.