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.

About these ads

20 Responses

Subscribe to comments with RSS.

  1. MoonShadow said, on 11.24.10 at 7:10 pm

    Nice – hadn’t thought of trying to implement Piet in Piet.

    You might be interested to know I’ve implemented a high-level language that compiles to Piet, yet supports functions, recursion and flow of control ;) Writing a compiler is actually pretty straightforward: each function is a strip of image, with some stub code hardcoded into the compiler (analogous to C++’s crt0.s) that sets up the initial stackframe and contains code to redirect flow of control to each function’s image area based on the value on the top of the stack. On entry to a function, more hardwired code pops the top value off the stack and branches to a location within the function based on that. On entry to a block, a value is pushed for every variable local to that block; the compiler keeps track of the local stackframe size so is able to generate the appropriate number of pops when leaving a block or exiting the function; this together with the table of local variables provides enough information to generate the rolls for fetching and storing variable values. To call a function, its arguments are pushed, followed by the index of the current function and return location within it, followed by the index of the target function and 0 for the entrypoint, and flow of control is transferred to the init stub.

    See http://www.toothycat.net/wiki/wiki.pl?MoonShadow/Piet – scroll down a little way past the assembler example for links to the compiler and samples.

  2. IngaPseulky said, on 07.21.13 at 5:02 am

    Like a crazy Microsoft!

  3. RopleMox said, on 11.13.13 at 7:02 am

    Вчера я вдруг наткнулся на один полезный адрес в интернете и с приятным удивлением обнаружил это:
    Индивидуалки Нижний Новгород. Я очень доволен этим сайтом.

  4. crodonaw said, on 12.05.13 at 12:25 pm

    Сегодня я представлю Вам сайт, который сам постоянно посещаю по одной простой причине. Тут есть очень полезная информация, например:
    компания Supernova for business продает готовый бизнес. Спасибо всем!

  5. Stevenmi said, on 01.16.14 at 7:07 am

    Как я счастлив, что нашел для себя этот сайт! Ведь только здесь можно найти вот это:
    скачать скайп без регистрации бесплатно. Это действительно то, что Вы искали.

  6. Alexmtlevsr said, on 01.21.14 at 8:25 pm

    Администраторам сайта
    Подскажите пожалуйста как можно связатся с администраторами этого сайта?

  7. Richardbip said, on 01.26.14 at 10:50 pm

    Дамы и господа, приглашаю Вас посетить этот удивительный сайт. Ведь именно тут Вы увидите:
    лестница. Спасибо всем!

  8. WillieKl said, on 02.06.14 at 6:15 am

    Сегодня я представлю Вам сайт, который сам постоянно посещаю по одной простой причине. Тут есть очень полезная информация, например:
    цікаві факти про україну. Я очень доволен этим сайтом.

  9. Rafaelbib said, on 02.14.14 at 6:59 am

    Предлагаем вам наилучший выбор игровых автоматов от Игрософт! совешенно бесплатно!

  10. BernardOn said, on 02.19.14 at 12:00 pm

    Всем доброго времени суток! Сегодня нашел в интернете один замечательный ресурс. Вот посмотрите пожалуйста:
    создание дизайна группы вконтакте. Это действительно то, что Вы искали.

  11. Thomasmors said, on 02.22.14 at 1:22 pm

    Здравствуйте! Представляю Вам очень хороший ресурс, в котором Вы найдете все самое нужное:
    оформление группы. Это действительно то, что Вы искали.

  12. RobertSak said, on 03.13.14 at 6:18 am

    мало

  13. DouglasBon said, on 03.14.14 at 6:29 pm

    Однажды я случайно наткнулся на один очень интересный сайт. Хотите и Вам покажу? Вот:
    интернет магазин волгоград секс шоп. Это действительно то, что Вы искали.

  14. RichardPn said, on 03.15.14 at 8:17 pm

    Всем доброго времени суток! Сегодня нашел в интернете один замечательный ресурс. Вот посмотрите пожалуйста:
    Приключения 3D. Всем успехов!

  15. Robertlasp said, on 03.17.14 at 6:54 pm

    Сколько уже можно безрезультатно просиживать в интернете? Добро пожаловать к нам, т.к. тут можно найти
    кредит онлайн сбербанк. Я всегда с удовольствием посещаю этот сайт. Ведь есть очень многое полезных материалов, например это:

  16. Philipmum said, on 03.18.14 at 2:51 pm

    Сколько бы я ни бродил по просторам интернета, но такого сайта больше нет нигде. Ведь только тут есть это:
    настройка директа. Наконец-то нашлось что-то стоящее.

  17. Freddyrage said, on 03.31.14 at 8:29 am

    Я и не знал, что существует такой великолепный сайт. Ведь тут есть множество интересной информации, в том числе:
    http://www.snob.ru/selected/entry/74276 – Президент Украины. Наконец-то нашлось что-то стоящее.

  18. Denvertak said, on 04.12.14 at 1:30 pm

    Дамы и господа, приглашаю Вас посетить этот удивительный сайт. Ведь именно тут Вы увидите:
    мойка окон. Это действительно то, что Вы искали.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.