This month I was hunting for a fun Python project I could get done with just the standard library when I read Jenn Schiffer's vart.institute article on Piet Mondrian. The article linked to the Piet Programming Language. With a limited set of instructions and equally limited state (a source file, a stack, and a few other variables), a toy Piet interpreter in Python sounded like a great fit for my goal!

Piet

Named after Piet Mondrian, Piet is a language crafted by David Morgan-Mar that uses abstract art as source code. You can find a thorough discussion of the language at the official Piet page, but I'll try to sum it up briefly.

Execution

Piet programs are images treated as sets of discrete blocks of color. A Piet interpreter behaves like a robot traversing the surface of the image: it moves from block to block, executing commands depending on the colors of the blocks it is transitioning between.

Navigation

At each execution step, the interpreter has to decide which adjacent block to move to next.

To make that decision, the interpreter uses three pieces of information: its current block, a direction pointer (DP) that indicates which direction to move next, and a codel chooser (CC) it uses to choose between blocks if there are multiple options adjacent to the current block in that direction.

The interpreter first finds the edge of the current block which is furthest in the direction of the DP, then uses the CC to select a block adjacent to the current block on that edge. The interpreter tries to move into that block next.

If that block is a color other than black or white, the move succeeds. If it's black, the move fails and the interpreter changes the DP or CC and looks for a new block to try. If it's white, the interpreter slips over the white block until it hits a black wall or a non-black block.

Colors/Instructions

Once the interpreter has successfully moved from one block to another, it tries to execute an instruction. To figure out which instruction to execute, it compares the color of the old block with the color of the new block. The difference in hue and lightness between the two colors is determined, and those values are used to look up the instruction to execute. The interpreter tries to execute that instruction and the cycle begins again!

Pyet

Pyet is my implementation of a Piet interpreter using the Python 3 standard library (with one notable exception).

Image cheat

Unfortunately, Python doesn't have an image handling module in the standard library. That's a pretty big obstacle when writing an interpreter for an image-based language! Rather than trying to re-implement image reading from scratch, I decided that it was within the spirit of the project to use a third-party library to turn the image into an equivalent text format before the actual interpreter got going. As a result my toy interpreter comes with a helper script to turn a Piet source file into a Pyet source file. I made it with Pillow, which made handling the popular image formats straightforward.

Program structure (Classes)

Pyet splits interpretation logic into four classes:

A PietStack which behaves as a stack and executes all of the stack-related operations Piet requires.
- Per the Piet spec, the PietStack is designed to fail by opting not to perform operations that would throw exceptions. It accomplishes this by returning None for pop operations that would fail and silently skipping stack manipulations that would be erroneous.
A SourceMap which holds and annotates the Pyet representation of the Piet source being interpreted.
- The annotation process splits the source into blocks and calculates information about those blocks for use in execution. More on this later.
A Navigator which holds the SourceMap and uses it to determine which block the interpreter should move to next.
- The Navigator takes care of all of the navigation logic mentioned earlier: sliding across white spaces, turning when obstacles are encountered, and transitioning between blocks.
An Interpreter which contains the PietStack and Navigator and uses them to interpret and execute the program.
- The Interpreter maintains the program's non-stack state and executes commands as required by movement between the blocks.

Interpretation

Pyet interpretation goes in three stages:

Initialization. the Interpreter is instantiated, creating an empty PietStack and Navigator in turn. The Navigator creates a SourceMap and passes the source to it.
Annotation. As part of its initialization step, the SourceMap numbers and annotates the color blocks in the source file, saving information about block sizes and corner locations that will be useful for navigation and instruction execution later.
Execution. The interpreter starts in the top left corner and starts traversing the source, executing instructions as it transitions between blocks.

Annotation & the Fill Algorithm

In order to interpret a program, the interpreter has to know which block it's in, know how big the block is, and know where the exit points from the block are. I opted to preprocess the source file to give each block a number, then save annotations about the size and exit points of each block. As a result, for a given location and DP/CC combination, the Navigator can look up which block it's in and how to exit that block.

To perform this preprocessing, I opted to run a simple flood fill algorithm over the source file. The SourceMap loops over each pixel in the source file, checking to see if that pixel already has already been assigned to a block and kicking off a flood fill at that location if not. The flood fill marks the pixel as visited, gives it a number, and adds the adjacent pixels of the same color to a queue. It works through that queue, giving those pixels the same number, marking them as visited, and adding same-colored pixels adjacent to them to the queue. When it runs out of pixels of the same color, the main loop continues on until it runs into another unfilled pixel.

That accounts for the block separation, but we still need annotations for size and exits. Luckily, we can take care of those while visiting the pixels to number them! By keeping a map from block numbers to block sizes, we just have to add one to our record of a block's size every time we add a pixel to it. Similarly, by storing candidate exit points the same way we can simply check every new pixel as it is added to see if it should replace any of the candidate exit points of the same number.

Room for improvement

The one aspect of the Piet spec I didn't nail (or intentionally compromise on) is the question of reading user input. Piet provides for two input instructions, in(char) and in(number). The specification indicates that the "in" command reads a value from STDIN as either a character or number, depending on the variant. While I was able to approximate appropriate input commands with sys.stdin.read, it's something I'd really like to revisit.

In terms of Python best practices, there are also a couple of things lacking in Pyet. While the project is PEP8 compliant, it's not PEP257 compliant: there are no docstrings at all! It's also pretty short on tests: other than a few tests to help me make sure the PietStack worked appropriately, the project is in need of many more unit tests to reach 100% coverage.

Future Directions

Now that I've got a (mostly) functional Piet interpreter, there are a lot of fun enhancements I can make to it. Here are a few that jumped out at me immediately.

Add another dimension: while the Piet instruction set and movement rules only account for travel along the x or y axis, most of it can be generalized to add another dimension without too much trouble. Anything that refers to block "area" now refers to block "volume" and when navigating there are now 8 possible directions (with 4 orientations each) rather than 4 possible directions (with 2 orientations each).
Add new colors/instructions: The Piet instruction set includes eighteen non-special colors and a corresponding seventeen instructions (one for every transition a given color can make to any other color). By adding a new set of colors, room opens up for more instructions.
Allow for configurable colors: While we're mucking about with the color sets, why not add configurable mappings between the actual image colors and the canonical Piet colors? Pyet uses a hardcoded list of what pixel colors map to which Piet colors and how the Piet colors are ordered, but by making those mappings configurable we can make programs with whatever twenty shades we want.
Create a transition graph: by annotating the source with the transition points between blocks, we're just one step away from being able to create a graph with the blocks as nodes and transitions as edges. Attach labels with the appropriate commands during each transition, and it might be possible to identify optimizations in the program or translate it to other languages.

It's clear that there's still a lot of potential in this project, and I have a feeling I'll be returning to it over time as I learn more about Python best practices and relevant design patterns. In the meantime I'm pleased to have put together a fun programmable toy from start to finish.