I need to take expressions, or programs, and break them down to a directed acyclic graph of binary logical operations.
In the end.... a cell has 4 inputs, and needs 4 outputs for each possible combination, a total of 64 bits (or 16 nibbles).
Heck, I'd settle for a good way to express said tree in a plain text file as a kick start.
[1] https://esolangs.org/wiki/Bitgrid
[2] https://github.com/mikewarot/Bitgrid
https://gist.github.com/int-e/c1b40dbed8a39a20dfc1d94fc25226...
By sheer coincidence, you appear to be the protagonist of a hard sci-fi novel:
https://www.amazon.com/dp/B0CJHQ4LZN
From the article author of a recent submission today:
This strikes me as not quite a correct description of the problem. What you described in that sentence above is closer to a description of compiling a combinational subset (just expressions, no state) of a hardware description language to logic gates.
The BitGrid has two differences from that. One, you have state registers after every cell: essentially it's pipelined at the single-cell level. Two, the routing of signals is fixed to be able to reach nearest-neighbors only. That means you end up needing to spend logic cells for routing and incur a one cycle delay for every hop away that you need to reach (whereas that's essentially "free" in gates).
Those make the problem significantly more complicated because you're not just mapping a function on to logic, but needing to do routing and a kind of delay analysis ("which cycle is this input signal from?) at the same time.
My suggestion would be to simplify the problem first. For example, allow routing any cell's input to any cell's output in the first stage of complication, then do a phase where you insert the routing.
To me, the level of pipelining and nearest-neighbor restriction makes it hard to approach the problem: the seeming simplicity ends up making it hard to wrap your mind around a larger computation. The routing is nontrivial; using cells for plain routing wastes logic resources; and the one-cycle delays become a complex problem to be worked around instead of a feature. It's interesting to think about but if it were my project, I'd think about changes to the model first to make life simpler.
> I'd settle for a good way to express said tree in a plain text file
What you are referring to is commonly called an IR (intermediate representation). Compilers typically take the AST generated by the parser and translate (“lower”) it into increasingly hardware-near and optimized IRs before performing instruction selection.
I briefly browsed through the links you provided. IIUC, BitGrid is essentially one of the Turing-complete 2-D cellular automata. This Reddit thread might be interesting to you [0].