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.

If you want to go in all four directions (like down, right, and then up) you'll need to have a four-ways infinite tree, like the diagram shown here of the free group on two generators. I don't know if this is relevant to what you're getting at, cuz I don't know what you're getting at.

What would be a simple and real example of this?

Oh rad, I see why it's the free monoid, since the parse tree is built up by concatenation (no inverse required).

@Joshua Horowitz I was trying to avoid 'getting at anything'. I definitely have ideas for what you can do with this kind of a spreadsheet, but I wanted to convey the idea of this kind of a spreadsheet independently.

Somehow this reminds me of Ted Nelson's ZigZag. In the spirit of this thread, I have no idea if this relation is helpful in any way.

I'm working on something related to this discussion! Here's two screenshots. One with a structure corresponding to @Robin's initial image, and the second corresponding to @Joshua Horowitz' response image. I was thinking along the line of circuits rather than spreadsheets, where arrows roughly mean "depend on" but I think the interesting common ground is doing computation over geometric/topological structures that aren't euclidean.

@Elliot I love the general idea of doing computation over interesting geometric/topological structures. Are those images part of your library for manipulating infinite recursive things? It looks very similar to what you shared earlier.