Conway’s Game of Life implemented in PURE (no scummy Apps Script) Google Sheets

(also related my – admittedly less dynamic – Cellular Automata Google Sheet)

Hey future of coding folks,

I want to advertise the idea of non-abelian spreadsheets. The idea has slowly drifted into the center of my thinking this last year. I'm not sure if its a good idea or not. It kinda depends on how you build on it. So for now I just want to convey the general idea.

Picture in your mind a normal spreadsheet. In some sense it is 'abelian' (commutative) because from any cell going down and then right is the same as going right and then going down. If we make it non-abelian, so the order we go right and down matters, we get something like the picture attached below.

If you tilt your head slightly you may recognize it as the infinite binary tree. So an infinite binary tree is just the non-abelian version of the usual grid-based spreadsheet. The nodes of the tree are the cells. We can also think of finite binary trees as the analogue of tables.

A key feature of regular spreadsheets is the ability to write formulas with relative references. For instance in a regular spreadsheet you can use relative references so a formula always refers to the cell to the right of the given one, and in a tree you can write a formula that always refers to the cell you get by going down and to the right from the given cell.

Another key feature of spreadsheets is that you put stuff in cells! And we do that with trees all the time. For example if we write down the syntax tree for (a+b)*c what we are doing is putting each of the symbols into a cell of the tree.

We can push this analogy to account for all trees (in particular all syntax trees). This tree can't really be visualized because it branches infinitely at each node. It is much easier to describe algebraically. I'll use the term 'free monoid on a set X', which if you aren't in the know just means the set of strings made out of the elements of X regarded as distinct characters. The infinite binary tree, or more precisely the set of nodes of the infinite binary tree, can be described as the free monoid on a two element set {L, R}. e.g. RLL describes the node you get by going right, then left, and then left again. Now let X_n denote a set with n elements and X the disjoint union of the X_n for all n. It suffices to take the free monoid on X.

A reasonable question at this point is what is the interface for an infinitely branching tree? You would think it is even worse than an infinite dimensional grid, which is the abelian version. But if we are restricting ourselves to trees coming from symbolic expressions then for the most part we already have the interface. It is just the symbolic expressions we would have written down in the first place.

I'll leave it at that.

I created a wiki page about Propagators any resource you would add? Do you know of related ideas?

Turnstyle is a graphical esoteric programming language loosely inspired by Piet. Both encode programs as images, however, the similarities end at the syntax level.

Where Piet is really a stack machine in disguise, Turnstyle is an encoding of the (untyped) Lambda calculus. This allows for building more reusable images at a higher level of abstraction, while still keeping the specification small, making it relatively easy to develop new interpreters.