To play around with graphics and wasm I implemented a renderer for a neat computer known as wang tiles. The project consists of a canvas-based tile visualizer, an interpreter that computes using tiles, and a W-Machine-to-Tile compiler to generate the tile sets. The renderer is fed visual data generated by the interpreter which is executing a program compiled from w-machine. Everything is written in rust and compiles to wasm. This article will give implementation details of the interpreter and renderer while providing some commentary about the state of wasm on rust. Of course you can simply play with the visualizer to generate pictures.
If you're eager to program the machine, skip to this section. The full source code is also available.
Dominoes are Programmable
Dominoes, those little rectangular tiles whose ends must match, are probably more powerful than you realize. But instead of those dominoes we'll be talking about wang tiles. You can get wang tiles from simple dominoes, just extend the pattern on the domino to include an east/west component as well as the original north/south component. This is the framework we'll be using to simulate a turing machine. When you dig into exactly how this is accomplished the real magic is in the matching and having two independent axes whereby you can pass data between.
Before digging in, we'll need to flesh out what exactly is meant by programmable. Abstractly, it means that these tiles are Turing-complete. Practically Concretely, we're trying to simulate the execution of a virtual machine somehow with these tiles. Before we can simulate some abstract machine, we need to create a mapping of the abstract machine state into the tile machine state. This step is where most of the fun comes in because we're taking a solid block of marble and chipping away at it until the abstract machine pops out. When we're satisfied with how to represent the abstract machine state with our components, usually creating the state transitions to "execute" the abstract machine are trivial.
W-Machine as a Bundle of Tiles
With the problem roughly outlined, let's choose a particular abstract machine called the W-Machine. I've written about this simple Turing-machine before in the context of tag systems. The pros are that it is simple and each execution step does very little, which is convenient for understanding at this level. The cons are that it is essentially 1-bit brainfuck but with more traditional branching. Ok so there are no cons.
The representation I settled on was to have each tile represent a single bit on the infinite tape. The north pip holds the value of the bit during the incoming transition and the southern pip is the outgoing value. For the most part... The head gets a special encoding, but it must also include the incoming and outgoing bit of the given cell. East/West pips are only used to differentiate "border" tiles from the void, and to transition the head left and right. The code is more clear and for those that care a good start is at the entry to the compiler.
This means that the set of all tiles corresponds in some sense to a tile machine language. A particular subset of tiles given an initial seed row (i.e., starting state) corresponds to a particular program. The implemented compiler is one mechanism for selecting a particular subset of tiles with certain properties, such as adhering to w-machine semantics given a specific representation. Now we obviously constructed this subset but thinking in terms of searches is useful for having to actually interpret these tile programs.
Tiles as a Mosaic
Given our tile machine is completely specified at some instant by a row of tiles, and each row determines the subsequent row, we can track the execution state of the machine as a series of rows. If we plot these rows we get a nice visual representation of the tile machine's execution of a given program. And you know, that's pretty neat.
Try it out
You can zoom in and out (on desktop; sorry mobile), click-and-drag to scroll the plane, as well as change the colors. The mosaic source and color parameters are sharable so you can link people to a pretty wallpaper directly. Not only is this a thoughtful gift but it will literally warm their heart as their computer heats up rendering each lovingly curated tile. I'm partial to this colorscheme and imagine others will be too.
W-Machine Semantics
Tape Movement
<
Move the head left one bit.
>
Move the head right one bit.
Memory Access
+
Set the bit under the head.
-
Clear the bit under the head.
Control Flow
label
Create a label named label; used as a jmp destination.
jmp TrueLabel
Test the bit under the head, jmp to TrueLabel if set or fallthrough if clear.
jmp TrueLabel, FalseLabel
Test the bit under the head, jmp to FalseLabel if clear.
Input/Output
,
Read a single bit from the environment and preserve it under the head.
.
Write a single bit to the environment taken from under the head.
NOTE These are unimplemented in the visual (wasm) code. But if you run this as a standalone executable it'll use stdin/stdout.
Rule 110 as a Mosaic
The tile machine is pretty general. In fact, we can simulate rule 110 with just a few tiles.
The tile-set was taken from Hao.
C -> W-Machine
A few years back I implemented a backend targetting w-machine for the wonderful Esoteric Language Virtual Machine (elvm) project. This means, in a certain sense, you can write programs in C and execute them with tiles. Something to consider for your shower renovation.
Conclusion
I like writing rust. Debugging the wasm target, however, was not fun. It turns out there is really no debugging and reminded me of writing firmware for some really strange hardware. I'm confident this situation will improve with time.
This was my first time doing anything web-related and it was a lot to take in. I am likely doing a lot of very strange things but that's life.
The performance could be better.
Overall, I am satisfied. I think the visualizer looks good and it was fun threading all of the components together.