Skip to content

Instantly share code, notes, and snippets.

@benjaminplee
Created October 2, 2010 04:02
Show Gist options
  • Save benjaminplee/607276 to your computer and use it in GitHub Desktop.
Save benjaminplee/607276 to your computer and use it in GitHub Desktop.
Proof of concept showing stack-size-aware macros for native piet commands
<!DOCTYPE html>
<html>
<head>
<script class="jsbin" src="http://ajax.googleapis.com/ajax/libs/jquery/1/jquery.min.js"></script>
<meta charset=utf-8 />
<title>Registers/Variables in Piet - Proof Of Concept</title>
</head>
<body>
<h1>Registers/Variables in Piet/QuickPiet - Proof of Concept</h1>
<p>
This quick and dirty code demonstrates that it is possible to emulate registers/variables in the single stack based
environment of Piet or QuickPiet. This is achieved by always maintaining the stacks size as the top most value on
the stack (stack size integer not counted in size calculation). By creating macro equivalents to each native Piet command
that are stack size aware, the size can be maintained through all normal operations (so long as the stack is seeded with a
single 0 pushed on to the stack to set the initial stack size -> empty). <u>Registers or variables can be created by seeding
additional values "below" the initial stack size value. These registers could be accessed by their relative offset from the
"bottom" of the stack</u>.
</p>
<p>
The "native" Piet commands are found on the QP object and implemented acting on the internal "stack" which is a normal JavaScript
array. New "enhanced" command which are stack size aware have an underscore after their name. The rudimentary assert command was
added to help in debugging since I didn't write the code test first initially and had a subtle bug in my native roll command. Each
"enhanced" command is simply a macro of several native commands. Most are 5-10 with the roll command being much larger since the
"depth" of changed stack values is variable (all others are static).
</p>
<p>
Test results should show below. If they don't, something is broke.
</p>
<h2 id="hello"></h2>
</body>
<script>
function QP() {
// **** Native commands from Piet/QuickPiet ****
var stack = [];
this.push = function(x) {
stack.push(x);
};
this.pop = function() {
stack.pop();
};
this.not = function() {
stack.push(stack.pop() == 0 ? 1 : 0);
};
this.greater = function() {
var top = stack.pop();
var second = stack.pop();
stack.push(second > top ? 1 : 0);
};
this.add = function() {
var top = stack.pop();
var second = stack.pop();
stack.push(second + top);
};
this.sub = function() {
var top = stack.pop();
var second = stack.pop();
stack.push(second - top);
};
this.mult = function() {
var top = stack.pop();
var second = stack.pop();
stack.push(second * top);
};
this.div = function() {
var top = stack.pop();
var second = stack.pop();
stack.push(Math.floor(second / top));
};
this.dup = function() {
var top = stack.pop();
stack.push(top);
stack.push(top);
};
this.mod = function() {
var top = stack.pop();
var second = stack.pop();
stack.push(((second % top) + top) % top);
};
this.roll = function() {
var count = stack.pop();
var depth = stack.pop();
var bottom = stack.slice(0, stack.length - depth);
var top = stack.slice(stack.length - depth);
count = ((count % depth) + depth) % depth;
for(var i = 0; i < count; i++) {
var top_element = top.pop();
top.unshift(top_element);
}
var new_stack = bottom.concat(top);
var len = stack.length;
for(var i = 0; i < len; i++) {
stack.pop();
}
var new_len = new_stack.length;
for(var i = 0; i < new_len ; i++) {
stack.push(new_stack.shift());
}
};
// **** Stack size aware Macros for original Native commands ****
this.push_ = function(x) {
this.push(1);
this.add();
this.push(x);
this.push(2);
this.push(1);
this.roll();
};
this.pop_ = function() {
this.push(1);
this.sub();
this.push(2);
this.push(1);
this.roll();
this.pop();
};
this.not_ = function() {
this.push(2);
this.push(1);
this.roll();
this.not();
this.push(2);
this.push(1);
this.roll();
};
this.dup_ = function() {
this.push(1);
this.add();
this.push(2);
this.push(1);
this.roll();
this.dup();
this.push(3);
this.push(2);
this.roll();
};
var helper_ = function(that, cmd) {
return function() {
that.push(3);
that.push(1);
that.roll();
cmd();
that.push(2);
that.push(1);
that.roll();
that.push(1);
that.sub();
}
};
this.add_ = helper_(this, this.add);
this.sub_ = helper_(this, this.sub);
this.mult_= helper_(this, this.mult);
this.div_= helper_(this, this.div);
this.mod_ = helper_(this, this.mod);
this.greater_= helper_(this, this.greater);
this.log = function() {
console.log(stack);
};
var log = this.log;
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();
};
this.stack = stack;
};
var qp = new QP();
var errors = "";
var error_count = 0;
var test_count = 0;
function assert() {
var expected = Array.prototype.slice.call(arguments);
test_count++;
var same = true;
same = same && (qp.stack.length == expected.length);
for(var i = 0; same && i < expected.length; i++) {
same = same && (qp.stack[i] == expected[i]);
}
if(!same) {
errors += ("Error (" + (test_count) + ") Expected: " + expected+ " Actual: " + qp.stack + "<br>");
error_count ++;
}
}
assert();
qp.push(0); assert(0);
qp.push(1); assert(0, 1);
qp.pop(); assert(0);
qp.push(2);
qp.push(3); assert(0, 2, 3);
qp.add(); assert(0, 5);
qp.push(4); assert(0, 5, 4);
qp.sub(); assert(0, 1);
qp.push(2);
qp.greater(); assert(0, 0);
qp.not(); assert(0, 1);
qp.not(); assert(0, 0);
qp.push(10);
qp.add(); assert(0, 10);
qp.dup(); assert(0, 10, 10);
qp.mult(); assert(0, 100);
qp.push(3);
qp.div(); assert(0, 33);
qp.push(10);
qp.mod(); assert(0, 3);
qp.pop();
qp.push(200); assert(0, 200);
qp.push(300); assert(0, 200, 300);
qp.push(3); assert(0, 200, 300, 3);
qp.push(1); assert(0, 200, 300, 3, 1);
qp.roll(); assert(300, 0, 200);
qp.push(3);
qp.push(-1);
qp.roll(); assert(0, 200, 300);
qp.push(500);
qp.push(3);
qp.push(2); assert(0, 200, 300, 500, 3, 2);
qp.roll(); assert(0, 300, 500, 200);
qp.push(1);
qp.push(8); assert(0, 300, 500, 200, 1, 8);
qp.roll(); assert(0, 300, 500, 200);
qp.pop();
qp.pop();
qp.pop();
qp.pop();
qp.push(0); assert(0);
qp.push_(100); assert(100, 1);
qp.push_(200); assert(100, 200, 2);
qp.pop_(); assert(100, 1);
qp.not_(); assert(0, 1);
qp.not_(); assert(1, 1);
qp.pop_();
qp.push_(2);
qp.push_(3); assert(2, 3, 2);
qp.add_(); assert(5, 1);
qp.pop_();
qp.push_(2);
qp.push_(3); assert(2, 3, 2);
qp.sub_(); assert(-1, 1);
qp.push_(5);
qp.mult_(); assert(-5, 1);
qp.push_(1);
qp.sub_(); assert(-6, 1);
qp.push_(3);
qp.div_(); assert(-2, 1);
qp.push_(10);
qp.mult_();
qp.push_(6); assert(-20, 6, 2);
qp.mod_(); assert(4, 1);
qp.push_(5);
qp.greater_(); assert(0, 1);
qp.push_(10); // roll command with "normal" scenario
qp.push_(20);
qp.push_(30);
qp.push_(40);
qp.push_(3);
qp.push_(1); assert(0, 10, 20, 30, 40, 3, 1, 7);
qp.roll_(); assert(0, 10, 40, 20, 30, 5);
qp.push_(2); // roll w/ 0 iterations should be no-op
qp.push_(0);
qp.roll_(); assert(0, 10, 40, 20, 30, 5);
qp.push_(2); // roll w/ iteration = 0 mod depth should be no-op
qp.push_(2);
qp.roll_(); assert(0, 10, 40, 20, 30, 5);
qp.push_(3); // roll with negative iterations goes backward
qp.push_(1);
qp.push_(2);
qp.sub_(); assert(0, 10, 40, 20, 30, 3, -1, 7);
qp.roll_(); assert(0, 10, 20, 30, 40, 5);
qp.push_(1); // any number iterations with depth 0 means no-op
qp.push_(10);
qp.roll_(); assert(0, 10, 20, 30, 40, 5);
$('#hello').append("Test count: " + test_count + "<br>" + "Error count: " + error_count + "<br>" + "Final Stack: " + qp.stack + "<br>" + errors);
</script>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment