Comment by DanielCristofan
16 hours ago
This is interesting. But the generated code has some weaknesses typical of projects that generate brainfuck algorithmically (whether done by humans or LLM agents).
-You're generating brainfuck through layers of abstractions. This doesn't work well, or at least nobody has done it well yet to my knowledge.
-You're also trying to define most of these abstractions in a position-agnostic way. To that end you maintain a relation where no command in your program is executed at more than one data pointer location.
-(You mention Turing-completeness, but this restriction reduces brainfuck to the power of a finite automaton)
-(It also makes massive code duplication at the brainfuck level almost inevitable)
-One consequence is that you need to move or copy values whenever you use them for anything. You've also gone a step further (also typical of these projects), and tend to give values a primary location, so they end up where they started after each operation, which means when you want to use values you're mostly making a copy, restoring the original, then using the copy and discarding it during or after. So the program spends most of its time and code moving values, copying values, zeroing copies, zeroing zeroes...
-(The pattern of zeroing cells before use is also a red flag. What was in that space before? Presumably nothing valuable, since you're comfortable zeroing it; then was it junk data left from some earlier calculation? That implies your compiler is leaving junk data scattered through the array in its wake, and doesn't remember what it left where? A bad sign. The efficient thing to do is usually, when you're using a value, save a copy if you're going to need that value again, or let it get wiped naturally during use the last time it's needed. Zero-after-use means much less explicit zeroing needed.)
I should acknowledge that many of your details look well conceived; it's just that the whole approach is (as far as I can tell) not capable of producing concise or efficient brainfuck code.
Good luck; -Daniel Cristofani
I’m happy to get such a constructive response from you.
This whole experiment was a way to experience some first-principles techniques rather than find the best way to compile to Brainfuck, so I agree with these limitations and will look into making it more efficient, where I can.
1. I’m not sure how far I could get rid of the layers of abstraction, since I would still need some abstractions, but they could perhaps be designed around Brainfuck’s tape and be more dynamic than addresses in a fixed layout.
2. Speaking of which, yes, I could use a better layout for scratch space, move values around while tracking where they currently are, and make more judicious use of dirty scratch cells instead of clearing them immediately.
3. And agreed, some form of lifetime tracking to zero at drop, or only when it was set earlier. The explicit zeroing was added because operations such as addition expected empty destination cells.
4. I hadn’t noticed that this made it a finite automaton, that’s interesting, I suppose removing the fixed-address restriction would let the same commands keep moving through the tape.
I might study more of your programs and try to apply some of the techniques used there.