Two Guys Arguing

Popping a Register from a Stack: QuickPiet Macros

Posted in javascript, math by benjaminplee on 11.08.10
Piet slide deck on Prezi.com

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

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.

First Cut – Piet Prezi Presentation

Posted in challenge by benjaminplee on 03.18.10

You can find the first cut of my Prezi based presentation on Piet and QuickPiet here:

http://prezi.com/fjqdfoigiipm/firstcutpiet/

I will update the link/presentation over the next week or so leading up to the next Lambda Lounge meeting.

Tagged with: , ,

Piet Roll Command

Posted in challenge by benjaminplee on 03.15.10

Roll-n-rolling with the Piet ROLL command

Mr. Young and a few others questioned how QuickPiet‘s command worked …. and to be honest, at first I didn’t either.  It turns out that the Piet ROLL command works fairly simply and is extremely powerful (according to npiet which I used as the basis for my testing).

The ROLL command pops two values off of the stack puts nothing back.  The top value from the stack defines how many “turns” the roll executes.  A turn will put the top value on the bottom and shift all other values “up” one place toward the top of the stack.  The second value defines the “depth” of the roll or how many elements should be included in each turn starting at the top of the stack.

As the main Piet page suggests, a ROLL to a depth of X and a single turn will effectively bury the top of the stack down X spots.  If that is as clear as mud, check out this image which shows two roll actions executed on a already populated stack.

Demonstration of the Piet ROLL command

Click to enlarge

[EDIT: Correction, the last roll in the above image shows a roll of depth 5, 2 turns. Not 3.  My bad.)

I used the nPiet command line Win32 interpreter to test this and the following program shown with 1 pixel per codel** and again with 20x20 pixels per codel.  nPiet is the most stable interpreter I have found and has some nice features like creating trace output images, tracing/logging statements, and automatically guessing codel sizes.  Below is the 20x20 codel version and nPiet trace output.

ROLL test program

ROLL test program

$ ./npiet.exe -v -t ben/roll-big.gif
info: verbose set to 1
info: trace set to 1
info: using file ben/roll-big.gif
info: got gif image with 320 x 120 pixel
info: codelsize guessed is 20 pixel
trace: step 0  (0,0/r,l nR -> 1,0/r,l dR):
action: push, value 1
trace: stack (1 values): 1
trace: step 1  (1,0/r,l dR -> 2,0/r,l lR):
action: push, value 2
trace: stack (2 values): 2 1
trace: step 2  (2,0/r,l lR -> 3,0/r,l nR):
action: push, value 3
trace: stack (3 values): 3 2 1
trace: step 3  (3,0/r,l nR -> 4,0/r,l dR):
action: push, value 4
trace: stack (4 values): 4 3 2 1
trace: step 4  (4,0/r,l dR -> 5,0/r,l lR):
action: push, value 5
trace: stack (5 values): 5 4 3 2 1
trace: step 5  (5,0/r,l lR -> 6,0/r,l nR):
action: push, value 3
trace: stack (6 values): 3 5 4 3 2 1
trace: step 6  (6,0/r,l nR -> 7,0/r,l dR):
action: push, value 2
trace: stack (7 values): 2 3 5 4 3 2 1
trace: step 7  (7,0/r,l dR -> 8,0/r,l lB):
action: roll
trace: stack (5 values): 3 5 4 2 1
trace: step 8  (8,0/r,l lB -> 9,0/r,l nB):
action: push, value 3
trace: stack (6 values): 3 3 5 4 2 1
trace: step 9  (9,0/r,l nB -> 10,0/r,l dB):
action: push, value 2
trace: stack (7 values): 2 3 3 5 4 2 1
trace: step 10  (10,0/r,l dB -> 11,0/r,l lG):
action: roll
trace: stack (5 values): 4 3 5 2 1
trace: entering white block at 12,0 (like the perl interpreter would)...
trace: step 11  (11,0/r,l lG -> 12,0/r,l WW):
trace: special case: we at a white codel - continuing
trace: white cell(s) crossed - continuing with no command at 12,2...
trace: step 12  (12,0/r,l WW -> 12,2/d,r lG):
info: program end

** Since small Piet programs are TINY, instead of using 1×1 pixels as the unit block or codel, Piet interpreters should be able to use codels of larger sizes.  Codels of larger sizes allow Piet programs to be easier to see and work with.

Tagged with: , ,

Challenge – QuickPiet Interpreter

Posted in challenge by benjaminplee on 03.14.10

Create an interpreter for a new Language based on Piet: QuickPiet

To pair off of Nate’s Rock Paper Scissors challenge, here is one I am offering up to him: create an interpreter which will execute QuickPiet commands.  What is QuickPiet?  QuickPiet is a very basic language based off of the commands found in the esoteric Piet programming language.

Piet_hello_big from http://www.dangermouse.net/esoteric/piet/samples.html

Big Piet Hello World (25 pixels / codel)

Piet programmers are written as images which can be interpreted as actions based on a stack.  Recently I signed up to give a talk at the April Fool’s Day meeting of the Lambda Lounge where several people will be giving short talks on esoteric and useless programming languages.  Programming in Piet poses several challenges including working only with a single stack and building up your logic into pixels and colors.  I should have a few posts on writing programs in Piet in the next week or so. Until then, I have been mainly struggling with how to accomplish real work with just a single stack and a very limited menu of commands to choose from.  QuickPiet is an attempt to make that process easier.

The challenge:

  • Write an interpreter for the QuickPiet language I have posted in a new GitHub Gist;  http://gist.github.com/332040.
    [Edit: The language spec is now in the base QuickPiet repo on GitHub]
  • The interpreter should allow the user to enter in QuickPiet commands from a file or GUI text box
  • The interpreter should allow the user to enter text to be handled by STDIN and should display to the user any characters sent to STDOUT
  • Ideally the interpreter would be written in a cross-platform way (e.g. JVM, Ruby, Javascript/HTML) but anything is valid
  • Extra points for GUIs and/or the ability to see how the stack changes through program execution and/or at the end

The “complete” spec can be found on the Gist page, but a very quick rundown is below:

  • Program execution is top down, except for GOTO commands
  • Each line can be blank (ignored), a label, a comment, or a command
  • Only one command per line
  • There are no explicit looping or other control structures
  • The interpreter maintains a single “infinitely large” stack which different commands can act on
  • Example commands include (IN, OUT, PUSH, POP, ADD, SUBTRACT, GOTO, etc)
  • Commands are case-insensitive, labels are not

If you have any questions or are willing to venture a solution please leave a comment.  I just had this idea this morning so I am very interested in any feedback you may have.  I am planning on working on my own solution and hope to have something put together today or tomorrow.

Click the tag links for QuickPiet and Piet below to see all posts

Tagged with: , ,
Follow

Get every new post delivered to your Inbox.