I guess expressions don’t really need to read left-to-right on a line.
Why can’t a < b be written vertically too?
a
<
b
All this time we’ve been writing expressions in 1D space, but what happens when we unlock an extra dimension?
Of course the IDE and parser need to play nicely for all this to work. Even then, what’s the point? Well, let’s take a look at these examples below.
3-arity functions
We don’t really see 3-arity functions written in infix notation much.
For example, in Python (and most other languages), you can and 3+ things at once:
x and y and z
Technically, that’s just composing multiple binary functions together.
Even this shortcut in Python to simplify (a < b) and (b < c) is more of the same thing:
a < b < c
Now, let me introduce you to a funny little operator I’ve been playing with called andFlip, which motivates the need for a true 3-arity infix notation. First, here’s the definition of the function:
def andFlip(args):
if args[0] and args[1]:
args[2] = not args[2]
return args[2]
It takes 2 inputs and flips the target if both inputs are true.
There’s just no good way to write this with infix notation. But let’s try anyways!
Define @@ to be the infix symbol for the andFlip operator. What does it look like in practice?
Method 1: the standard way
One option is to curry andFlip: the infix @@ takes 2 args and returns a function awaiting the 3rd, like so:
(a1 @@ a2) a3
Yeah, that’s alright. It works. But…
Method 2: the goofy way
Forget what you know about code for a second. If I could flick a magic wand, I’d wish for the 3-arity notation to look like this:
a3
a1 @@ a2
Might as well make use of the y-axis, right?
It makes chaining so much easier:
t1 = 0
t2 = 0
t1 t2
(x @@ y) @@ z
In the chain, x @@ y toggles t1, and t1 continues the chain t1 @@ z, which toggles t2.
That’s a successful three-way toggle, where all x, y, and z must be true for the target to toggle.
Btw, since we’re working in 2D space now, the following expression,
t1
x @@ y
is equivalent to:
x @@ y
t1
Example: my chicken coop door
Consider the automatic door I’ve installed on my chicken coop.
With just a photometer and its internal clock, the microcontroller tracks:
x– the photometer crossed its dusk/dawn thresholdy– the reading has held steady for five minutesz– the gate has not recently toggled
The door toggles only when all three line up. A passing cloud trips x but never outlasts y, so the door stays put.
The coop’s controller is the same chained expression from above:
t1 = 0
t2 = 0
t1 t2
(x @@ y) @@ z
You might be wondering, why not just write x and y and z? Because then the door would mirror the sensors, swinging right back the moment a condition fades. @@ toggles in place: the door moves once and stays, and the partial answer lands in t1, a scratch bit.
Spatial languages get even more fascinating when we introduce vertical chaining!
Vertical chaining
That mutable variable t1 disqualifies the expression from being called a “pure function”. But can we fake it? Can we reset t1 back, all within the same expression?
I’d like to introduce vertical chaining through two puzzles.
Puzzle 1: reset t1 back to 0
As mentioned, in the chaining examples above, the variable t1 is mutable.
Here’s a puzzle: how can we reset it back to 0, so the expression “appears” immutable?
You may be tempted to just append the statement t1 = 0 and call it a day, but the goal of the puzzle is to do it all within the same expression.
Give it a shot before you scroll down!
Here’s the answer. Since t1 can be reset by repeating the same thing that was used to toggle it, we can combine expressions into a larger 2D one, like so:
t1 = 0
t2 = 0
(x @@ y) @@ z
t1 t2
(x @@ y)
Ok, I’m probably blowing your mind right now.
The data flow is still as you’d expect in a programming language, left-to-right and top-to-bottom. If x and y are true, the first x @@ y flips t1 and then the second x @@ y resets it. Otherwise, both leave t1 untouched.
This puzzle actually models the CCCX gate in quantum computing, where uncomputing the intermediate t1 value within the same circuit is an important requirement.
Puzzle 2: reset the temporary variable back to the original value
If t1 starts off with an unknown boolean value n, then it gets more complicated.
t1 = n
t2 = 0
t1 t2
(x @@ y) @@ z
The same trick above to reset t1 back to its original value won’t work.
See for yourself: when t1 = 1 and x, y, and z are all true, then t2 remains 0, which is incorrect.
t1 = 1
t2 = 0
(1 @@ 1) @@ 1
t1 t2
(1 @@ 1)
So, what’s the answer?
Tada!
t1 = n
t2 = 0
t1 t2
(x @@ y) @@ z
t1 t2
(x @@ y) @@ z
Absolutely legendary. This single 2D expression resets t1 back to n while producing the correct result for t2.
This puzzle is inspired by the concept of resetting a borrowed ancilla in quantum computing. t1 is the “borrowed” or “dirty” value that remains unchanged.
Here’s the same circuit in Qiskit:
from qiskit import QuantumCircuit, QuantumRegister
x = QuantumRegister(1, "x")
y = QuantumRegister(1, "y")
z = QuantumRegister(1, "z")
t1 = QuantumRegister(1, "t1") # starts in unknown state n
t2 = QuantumRegister(1, "t2") # target, starts at 0
qc = QuantumCircuit(x, y, z, t1, t2)
qc.ccx(x, y, t1)
qc.ccx(t1, z, t2)
qc.ccx(x, y, t1)
qc.ccx(t1, z, t2)
I’d argue that the Qiskit implementation is harder to follow, because of the back-and-forth variable tracking.
By the way, here’s the corresponding quantum circuit diagram:
wires: x, y, z, t1 = n, t2 = 0
outputs: x, y, z, n, x·y·z
ccx x y t1
ccx t1 z t2
ccx x y t1
ccx t1 z t2
In some ways, this circuit diagram is easier to follow, but probably not scalable.
The spatial language syntax is the best of both worlds.
Defining new operators
First, meet @@’s little sibling. A single @ takes one condition instead of two: x @ y flips y whenever x is true.
With @ and @@ in hand, we can define new operators, spatially. The left side of := is a shape, and the right side is what that shape rewrites to:
b maj c (a @ b) @@ (a @ c)
a := a
This strange operator flips both b and c when a is true, and then flips a if both sides came out true. That computes a ^ ((a^b) & (a^c)) into a, which happens to equal the majority of the three inputs, which is why this operator is called maj.
And maj is no arbitrary choice. It’s the MAJ gate from the classic quantum ripple-carry adder, where the majority of (carry, bit, bit) is the next carry.
You may have noticed that maj leaves b and c dirty, holding a^b and a^c, the same kind of mess as our borrowed t1. To clean up, we’ll also introduce uma, the partner operator. The name comes from the same adder paper, “UnMajority and Add”: it un-majorities c, restores a, and adds the sum onto b:
c uma b ((b @@ a) @ a) @ b
a := c
Let’s see what happens when we wire them up.
3-bit adder
We can build a 3-bit adder out of three majs that ripple the carry up through the a wires, with the final @ dropping the carry-out on c3, and finally one line of umas resetting all the scratch wires:
c0 = 0
c3 = 0
(b2 maj (b1 maj (b0 maj c0))) @ c3
a2 a1 a0
(( . uma b2) uma b1) uma b0
c0
That’s a full 3-bit adder in a single 2D expression that also cleans up after itself. The b wires now hold a + b, c3 holds the carry-out, and c0 and the a wires come back exactly as we found them. (Set c0 = 1 and you get a + b + 1 for free.)
Notice the two lines mirror each other. The top nests rightward down to b0 and ripples the carry back up; the bottom nests leftward down to b2 and unwinds back out. The shared a1 and a0 labels are the pivots, each serving the maj above it and the uma below it, and the . is a vertical pipe, standing for whatever wire sits directly above it, here a2. The carry chain is stitched together vertically: the uncompute touches the compute, just like in the puzzles.
Speedrunning other spatial languages
Here’s a quick tour of a few more spatial languages.
Befunge
The grandparent of 2D languages (Befunge, 1993): the instruction pointer physically travels the grid, and >v<^ steer it. Hello world bounces off the walls:
> v
v"Hello World!"<
>:v
^,_@
Orca
Orca is a livecoding sequencer where every letter is an operator that reads its neighbors: A adds the value to its left and the value to its right, and writes the sum directly below itself. Sound familiar?
1A2
.3.
Racket #2d
A real, shipping language extension: Racket’s #2dcond is a cond evaluated in two dimensions. The left column tests b, the top row tests a, and the cell where both are true runs.
#lang 2d racket
(require 2d/cond)
(define (same? a b)
#2dcond
╔═════════════╦═══════════════════════╦═════════════╗
║ ║ (pair? a) ║ (number? a) ║
╠═════════════╬═══════════════════════╬═════════════╣
║ (pair? b) ║ (and (same? (car a) ║ #f ║
║ ║ (car b)) ║ ║
║ ║ (same? (cdr a) ║ ║
║ ║ (cdr b))) ║ ║
╠═════════════╬═══════════════════════╬═════════════╣
║ (number? b) ║ #f ║ (= a b) ║
╚═════════════╩═══════════════════════╩═════════════╝)
Hexagony
Hexagony runs on a pointy-topped hexagonal grid, like a certain background you may have noticed. Six instruction pointers start at the six corners. Hello world:
H ; e ;
l ; d ; *
; r ; o ; W
l ; ; o ; * 4
3 3 ; @ . >
; 2 3 < \
4 ; * /
Ladder logic
Ladder logic is how PLCs run factories (and, done properly, chicken coop doors): each rung is a relay circuit read rail-to-rail, and parallel branches are OR. This classic seal-in rung computes Run = (Start OR Run) AND (NOT Stop):
--+----[ ]--+----[\]----( )
| Start | Stop Run
| |
+----[ ]--+
Run
And an honorable mention for the most successful spatial language of all time: the spreadsheet, where every formula lives at a 2D coordinate and reads its neighbors.
“This Is Water”
If you know me, you know I love bringing up the Sapir-Whorf hypothesis, which proposes that language shapes the way you think:
- Some Australian Aboriginal languages have no words for left and right, only compass directions, so their speakers always know which way north is.
- Russian has two separate words for blue, so Russians are faster at telling two blues apart when the shades straddle that word boundary.
- Haskell is purely functional, so you start recognizing monads everywhere you go. That sort of thing.
Likewise, I believe technology shapes which languages emerge.
- A shell terminal forces us to write commands left-to-right, so we think of code horizontally instead of vertically.
- Most keyboards are built for English and the standard ASCII symbols, so we think in those symbols :).
Being aware of our biases is a justified mental exercise, at least according to David Foster Wallace, who delivered a commencement speech titled This Is Water. Though his speech was less about ancilla uncomputation in quantum circuits and maybe more about growing up and being compassionate, you get the point. By challenging our habits, we can explore new ideas.