Challenge #5: Turing Tumble Compiler

[paul]

Someone mentioned this idea during the Kickstarter campaign and I’ve been excited about it ever since. Their idea was to write a compiler that could take code written in some language (say, C++ or Python, for instance) and translate it into a Turing Tumble layout.

I’ve never written a compiler, but I imagine it would be no small undertaking. Nevertheless, it sounds like a fun challenge, and it would answer important questions like:

• How big would the TT board need to be to run Doom?
• What is the question to the answer ‘42’?

But more seriously, it would be useful to see how big of a TT board would be necessary to do more complex operations. Is it worth making a bigger version? How big a board would you need to create a simple, but functioning processor? How fast would it run? How many marbles would it take to run a simple program on it?

I hope someone decides to take on this challenge!

[mspencer]

This is interesting and I’d like to unpack this a bit.

What does it mean for a physical TT board to execute a program? I believe the most narrow interpretation is that the physical TT board produces an output state with the same meaning as the output produced by the symbolic source code being “compiled,” without regard for how the output is produced.

It’s also reasonable to interpret this as a requirement that the physical TT board must perform the same operations in the same sequence as what the symbolic source code describes. Even if there’s a faster or simpler way available, if the original source uses a 32-bit int to count from 0 to 9, the TT version must use a register composed of 32 blue bit pieces on a board large enough to hold it, and must have a meaningful way to compare any arbitrary 32 bit integer with a terminating condition value of 9 or 10.

To put it another way, if I have this program:
int i = 0;
while (true)
{
i++;
if (i % 2 == 0)
output-a-red-ball;
else
output-a-blue-ball;
}
Is it reasonable to render this as a program containing only green ramps, which sends each color’s balls to the other side’s levers? (edit: okay, green ramps and a crossover )

[paul]

Hi mspencer,

I think I see what you’re getting at. Very good point. Usually a compiler converts readable code into a set of instructions a processor can execute. In this case, there is…no processor. At least not yet. So maybe it would have to use a language like Verilog or VHDL, not something like C or Python.

Paul

[rmsgrey]

I think it’s legitimate to duck-type numerical storage to only require enough bits to store the range of values required - so if you’re counting to 10, you only need 4 bits. Use of a 32-bit integer is a hardware limitation of standard PCs, not an important piece of semantics in the code - and the same code might compile to an 8-bit integer on a significantly older compiler running on much older hardware…

But, yeah, Turing Tumble is closer to circuit design than to coding - to get into code, you’d want something that reads off a register and selects which operation to perform based on that value - or, rather, you’d want a very large number of registers to contain the code, and some way of selecting an active register and then either copying that value (non-destructively!) into the work area to be used to determine the next action, or using the value from an arbitrary register to select the next operation…

Just coming up with a design that lets you both increment and decrement a given register isn’t trivial (I think you’d need three columns of gear bits with two columns of gears between them, so that they’re linked in rows, so the left column is used for adding, while the left column for subtracting, with the middle column just there to link the other two).

[mspencer]

Would we want to pursue this more as CPU design? Assuming some magical way to link TT boards, or simulating some huge single TT board, can we build a super simple stored-program computer? I have no real background in this.

Anybody know how to reach that guy who made a CPU in Minecraft?

[elendiastarman]

I don’t know the guy that made a CPU in Minecraft, but I was one of six people that programmed Tetris in Conway’s Game of Life. I can confidently say that Assembly is the place to start, not a high-level language like C or Python. Or, more properly, it’s best to design the circuit structure and the corresponding Assembly language together and then work down/up to low-level mechanics and a higher-level language.

Broadly speaking, these are the main features needed:

• Random Access Memory (RAM) - store potentially-changing values using registers.
• Read-Only Memory (ROM) - store instructions for executing the program. Technically this is not necessary as one can use RAM to store instructions, but it might be more convenient depending on the circuit design.
• Program counter (PC, probably in line 0 of RAM) that specifies which line of ROM (or RAM) to execute next.
• Mini-circuit to increment the program counter on each loop.
• Arithmetic Logic Unit - mini-circuits that execute each arithmetic instruction (such as ADD, SUB, MUL, etc) or instructions such as jumps.
• Conditional jumps - much like the gear bits, this is what makes a program really capable of computing anything. These compare two values and use the result to choose which of two addresses to set the PC to next. There are two main variants: 1) compare variables A and B, then jump to address C or simply move to the succeeding address, and 2) compare variable A with constant (usually 0), then jump to address C or D.

Once one has implementations of these, then the next step is to wire them all together. Then write an interpreter for the Assembly language chosen/created so actually running the circuitry is not strictly necessary. Then write the compiler to convert a higher-level language to that Assembly language.

It’s…much harder than it seems at first glance to compile human-readable code to a Turing Tumble board.

[hammerquill]

If anyone is interested in working on this - on any level - or is intrigued by elendiastarman’s comment but doesn’t understand all the terms they used, or you just want to learn more about how computers work at the very most elementary levels, and how that connects to the level at which we normally interact with them, I highly recommend the book Introduction to Computing Systems: From Bits and Gates to C and Beyond, by Patt and Patel. It’s an undergraduate university textbook, but it’s so well written it’s easy to learn from and follow on your own.

[dneary]

Interesting! I wonder if a hardware description language like VHDL would be a good fit for something like Turing Tumble - you could write “modules” to do simple tasks, and chain them together to make an instruction set. These get very big very quickly, though!

[ConwayNerd]

Hi I’m new, and like elendiastarman, I am obsessed with CGoL. We would want something similar to APGsembly, that takes some states and components and compiles a board state from that. However, we’ve got nothing so easy as gliders! There are plenty of components though. (Basically every practical answer to the puzzles). Each step would take 2 balls. The first ball is guided through a selector to the relevant state part. This then goes to the components that perform the action. This action returns true or false (say, if a register has overflowed or not) which goes through an extremely long gear bit chain that changes a gear bit in the state part. When the next ball goes into the state part, it changes the state selector to the next state it should use. I might draw a picture.

Technology wise, I think we can pass a ball through a gear bit chain, either setting the value of the chain to 0 or 1, or just pass through. This would be essential to work the machine.

[buddha]

I created an S-R-Flip-Flop.
IT Looks Like this(I labled all of the Inputs and Outputs):

[buddha]

I’ve built a fast adder. To add a three-bit number to another three-bit number, it only needs 4 red
( and 1 blue ball for the status “finished”).
Here is the link:Tumble Together
Register A are the outer three bits, register B the inner.
To reset this machine, just point those gearbits right.

[buddha]

Here ist the draft of an ALU: Tumble Together
Explanation:

To reset the ALU, point all bits and gear bits left.
If Function Choose points right, the ALU adds.
Else it checks if both input bits point right.