Programming in Color (fixed)

Todays programming pathology is programs as art.

Start with a really simple stack based language, add in a crazy way of encoding instructions using color, and you end up with a masterpiece of beautiful insanity. It's not too exciting from a purely computational point of view, but the programs are really great to look at. Yes, it's a pathological language with truly beautiful source code!

*(The original version of this post had some trouble because I linked to the original images in-place,
which the owner of the Piet webpage had blocked. I didn't realize he didn't want links. I've since downloaded
the images, coverted them to jpegs, and posted them here. I initially thought that the problem with the images was formats, which is what I originally said in this explanation. It's not the image format, but the linking; but converting the files to jpeg and uploading them removed the links that caused the problem.)*

Here's the complete list of
instructions (without control flow):

1. **Push**: Push a value onto the stack.
2. **Pop**: discard the top value from the stack.
3. **Add**: Take the top two values off of the stack, add them, and push the result.
4. **Subtract**: like add, but subtract the values.
5. **Multiply**: like add, but multiply.
6. **Divide**: like add, but divide.
7. **Mod**: like add, by modulo.
8. **Not**: pop the top value off the stack; if it's 0, push 1, otherwise push 0.
9. **Greater**: pop the top two values off the stack, push 1 if the second value on the
stack is greater than the top, otherwise, push 0.
10. **Roll**: pop the top two values of the stack. Call the top one "count", and the second
one "depth". Now, take the top "depth" set of values on the stack, and rotate them by taking
the value on top, and putting it on the bottom. Do the rotation count times.
11. **In**: read a value from input and push it on the stack.
12. **Out**: pop a value from the stack and print it.

So far, seems pretty trivial, right? Standard stack based language, nothing unusual.

Ok. So, now let's start getting weird. We're looking at a two dimensional language, so the control flow operators are all based on *direction*. There are two things that control the flow of the program: the direction of motion, and the direction of selection. The direction of motion describes where the pointer goes on a step; the direction of selection determines where it looks if it needs more information than it has under the instruction pointer. So the control flow operations are:

1. **Switch**: pop the top stack value *n*, and switch the selection direction *n* times.
2. **Rotate**: pop the top stack value *n*, and rotate the motion direction 90 degrees clockwise
*n* times.

Ok, getting a bit weird now... But still, overall, pretty mundane. This isn't a particularly
interesting model of computation, nothing exciting about it. Certainly nothing do beat, say,
Snusp for the beauty of 2d programming.

Now... Here's where it gets *really* interesting. How are instructions encoded? By *color*. The program source is a PNG image!

Yes, todays language is called "[Piet][piet]", in honor of Piet Mondrian, a modern abstract artist, because programs are intended to look as much like a painting by Mondrian as possible. There are twenty colors in Piet that have semantic significance, given in the table below:

Most commands are given by the color transition between the pixel under the instruction pointer, and the pixel next to it in the selection direction. You'll definitely need to keep that table handy to see how the instructions work.

So, let's look at how we encode instructions. We take the current pixel, and the pixel next to it in the selection direction, and consider their *difference* in the two dimensions given in the color table: hue, and darkness:

* **Add**: +1 hue; no change in lightness.
* **Divide**: +2 hue; no change in lightness.
* **Greater**: +3 hue; no change in lightness.
* **Dup**: +4 hue; no change in lightness.
* **In** (input character): +5 hue; no change in lightness.
* **Push**: No change in hue, +1 darkness.
* **Subtract**: +1 hue, +1 darkness.
* **Mod**: +2 hue, +1 darkness.
* **Rotate**: +3 hue, +1 darkness.
* **Roll**: +4 hue, +1 darkness.
* **Out** (output number): +5 hue, +1 darkness.
* **Pop**: No change in hue, +2 darkness.
* **Multiply**: +1 hue, +2 darkness.
* **Not**: +2 hue, +2 darkness.
* **Switch**: +3 hue, +2 darkness.
* **In** (input number): +4 hue, +2 darkness.
* **Out** (output character): +5 hue, +2 darkness.

Numbers in Piet come from the *size* of the color blocks. The number of pixels in the block correspond to a number. So, for example, a block of 6 light yellow pixels followed by a yellow pixel will push the number 6 onto a stack.

Black and white are special colors - white is a separator; white pixels are just skipped over as if they weren't there. Black pixels are blocks; if the program hits a black pixel, it will try switching the selection directions (ignoring white pixels); if that is also black, it will try rotating the motion direction +90 degrees. If it can't find any non-black pixels using an sequence of alternating SWITCH/ROTATE instructions, the program will halt.

So now, finally, you can look at a few nifty examples of [Piet programs][programs]. To make them easier to read, the Piet programs are scaled up, so the pixels are actually represented by largish squares. As usual, we'll start with "Hello World":

That *is* hello world. Each of the large color blocks is one of the characters; the narrow lines are stack manipulations and output statements; and the little black arrowhead toward the top left captures the pointer and forces the program to halt.

Moving on, here's a much fancier "Hello world":

One that really meets the goal of looking like a Mondrian painting, this program prints
out "Piet":

My personal favorite Piet program; this one prints out the alphabet; and the author provided
an [annotated version][annote] of it to help you understand how it works! Here's the program:

One last brilliant Piet program, which even the guy who *designed* Piet can't figure out... It's the towers of Hanoi in Piet!

[annote]: http://www.dangermouse.net/esoteric/piet/alpha_filled_trace.png
[programs]: http://www.dangermouse.net/esoteric/piet/samples.html
[piet]: http://www.dangermouse.net/esoteric/piet.html