benjaminplee · October 2, 2010 04:02
diff --git a/Registers In Piet PoC b/Registers In Piet PoC
 <!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>
	<!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>