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

65 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

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

  19. Howardsomb said, on 04.24.14 at 4:52 am

    парсить людей вконтакте
    Скоростной парсер вконтакте
    парсер вконтакте груп
    парсер людей вконтакте
    приватный парсер вконтакте
    парсер вконтакте груп

  20. JessiejeD said, on 04.30.14 at 9:23 am

    Как я счастлив, что нашел для себя этот сайт! Ведь только здесь можно найти вот это:
    BMW 3 характеристики. Спасибо всем!

  21. RobertCom said, on 05.01.14 at 2:31 am

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

  22. Willieol said, on 05.03.14 at 2:41 am

    Как я счастлив, что нашел для себя этот сайт! Ведь только здесь можно найти вот это:
    Колесо Фортуны на твоей стороне – счастливчик, ты можешь выиграть. . Наконец-то нашлось что-то стоящее.

  23. BrandonOn said, on 05.08.14 at 3:45 am

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

  24. Marrikaquox said, on 05.16.14 at 3:43 pm

    High class escort London

    High class escort London

  25. depatoarriday said, on 05.17.14 at 8:51 am

    The PILOT company suggests rent of cars for private and corporate clients, provides transfer services. Компания Pilot занимается продажей новых автомобилей, автомобилей с пробегом и автозапчастями как на внутренний рынок, так и на экспорт.

  26. AlbertPt said, on 05.27.14 at 4:28 am

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

  27. Justinmt said, on 06.17.14 at 3:02 pm

    Дамы и господа, приглашаю Вас посетить этот удивительный сайт. Ведь именно тут Вы увидите:
    http://embargo.cc – кардинг форум. Вы не пожалеете, что побывали тут.

  28. Ernestkt said, on 06.19.14 at 8:09 am

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

  29. Samueljelm said, on 06.20.14 at 5:22 am

    this blog
    minecraft unblocked
    minecraft launcher unblocked
    unblocked minecraft download
    unblocked minecraft at school
    minecraft unblocked free download

  30. MarvinRilt said, on 06.27.14 at 11:34 am

    Здравствуйте! Представляю Вам очень хороший ресурс, в котором Вы найдете все самое нужное:
    http://ad1game.ru/start – Эффективный заработок на CPA. Вы не пожалеете, что побывали тут.

  31. Martinbew said, on 07.01.14 at 6:37 am

    Однажды я случайно наткнулся на один очень интересный сайт. Хотите и Вам покажу? Вот:
    http://viateck.ru/ – диспетчер грузоперевозок. Удивительно, не правда ли.

  32. RobertTon said, on 07.01.14 at 1:49 pm

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

  33. Josiahsi said, on 07.09.14 at 6:38 pm

    Я и не знал, что существует такой великолепный сайт. Ведь тут есть множество интересной информации, в том числе:
    доставка еды в офис. Вы не пожалеете, что побывали тут.

  34. MatthewVela said, on 07.14.14 at 6:31 pm

    Я и не знал, что существует такой великолепный сайт. Ведь тут есть множество интересной информации, в том числе:
    Неисправности Great Wall. Очень хорошо, что есть такие сайты.

  35. AndrewLaf said, on 07.19.14 at 7:10 am

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

  36. TimothyDaph said, on 07.22.14 at 1:09 pm

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

  37. CharlesPa said, on 07.27.14 at 12:23 am

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

  38. GeorgePync said, on 07.27.14 at 8:12 pm

    Я и не знал, что существует такой великолепный сайт. Ведь тут есть множество интересной информации, в том числе:
    Юридический консалтинг на самых выгодных условиях, юридическая консультация . Удачи всем!

  39. Stevengaw said, on 07.29.14 at 8:29 pm

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

  40. AshleyMl said, on 08.01.14 at 7:47 pm

    http://metronidazoles.com – metronidazole online

  41. Robertomix said, on 08.01.14 at 9:03 pm

    naltrexone

  42. AshleyMl said, on 08.02.14 at 4:47 am

    http://metronidazoles.com – metronidazole

  43. Josephcopy said, on 08.02.14 at 6:28 am

    http://trazodone.info – buy trazodone

  44. EugeneSi said, on 08.02.14 at 6:50 am

    cost of duloxetine

  45. StanleyWape said, on 08.02.14 at 11:18 am

    http://vardenafils.com – buy generic levitra

  46. JosephCedy said, on 08.03.14 at 2:51 pm

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

  47. Andreymn said, on 08.05.14 at 3:40 am

    Однажды я случайно наткнулся на один очень интересный сайт. Хотите и Вам покажу? Вот:
    скачать shadowfight. Всем добро пожаловать!

  48. Normansi said, on 08.05.14 at 6:33 am

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

  49. Michaelsype said, on 08.06.14 at 3:33 pm

    Всем доброго времени суток! Сегодня нашел в интернете один замечательный ресурс. Вот посмотрите пожалуйста:
    http://hackportal.ru/ – Скачать читы для кросс фаер. Наконец-то нашлось что-то стоящее.

  50. DennisvaH said, on 08.06.14 at 11:26 pm

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

  51. VictorBaMp said, on 08.07.14 at 6:25 am

    Получи $1000 БЕСПЛАТНО! Poker Automatics. Гарантированный Пассивный Доход от покера 24/7. Без навыков! Без риска!
    Создайте аккаунт, пополните его и наблюдайте, как сумма на Вашем счете растет каждый день без Вашего участия.
    самый большой процент

  52. FreddieSus said, on 08.08.14 at 1:21 am

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

  53. Danielvof said, on 08.08.14 at 9:45 am

    Как я счастлив, что нашел для себя этот сайт! Ведь только здесь можно найти вот это:
    Прикольные картинки, фотоприколы, юмор, мемы, демотиваторы. Наконец-то нашлось что-то стоящее.

  54. Andrewrop said, on 08.10.14 at 6:13 am

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

  55. Josephcled said, on 08.12.14 at 3:10 pm

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

  56. Charlesen said, on 08.22.14 at 1:46 am

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

  57. Ronaldvek said, on 08.23.14 at 3:05 am

    Сколько уже можно безрезультатно просиживать в интернете? Добро пожаловать к нам, т.к. тут можно найти https://vk.com/club69836430 – кредит в москве. Удивительно, не правда ли.

  58. GerardoMr said, on 08.23.14 at 5:01 am

    Как я счастлив, что нашел для себя этот сайт! Ведь только здесь можно найти вот это: check ip. Всего наилучшего!

  59. StephenFep said, on 08.25.14 at 2:20 pm

    online pharmacy without a prescription
    penis gets erect
    prostate laparoscopy
    nabp website
    health online shop
    best herbs for prostate health

  60. Michaellar said, on 09.02.14 at 11:04 am

    Вчера я вдруг наткнулся на один полезный адрес в интернете и с приятным удивлением обнаружил это: http://tifani.kh.ua – женская кожаная обувь харьков. Это действительно то, что Вы искали.


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.