I wrote a ray tracer in Brainfuck | Hacker News Reader

I wrote a ray tracer in Brainfuck

epestr.com

94 pointsepestr21 comments

Open articleView on HN

Isn't this just a ray tracer in python/c that spits out brainfuck? By this logic gcc writes all my programs in assembly lol

Well the proper analogy would be that you write your programs in assembly. I think the more impressive thing here isn't the ray tracer, but the C (or was it C++?) to brainf** transpiler. That would be equivalent to you writing both C code and the C compiler. Pretty impressive, but depending on the complexity of the program not as impressive as writing whatever it is in assembly directly. A raytracer would be PAIN to write directly in brainf** - I think I'd want to use fixed precision everywhere rather than emulated floating point. (on second glance, it does look like the author of the article is also using fixed precision arithmetic, but confusing the label for the layout of the number with the type of number representation itself?)

Looks like I misunderstood what it meant to be a floating point, and this does match the description of a fixed-point representation.

> Pretty impressive, but depending on the complexity of the program not as impressive as writing whatever it is in assembly directly

I'd make the case assembly is easier here, given the DSL isn't much different in terms of it's experessiveness, and jumping around is easier in assembly too. Registers change the whole thing.

Pretty much, though the interesting bit is clearly the abstractions and work involved. Writing 22MB of code doesn't sound very maintainable :)

brainfuck is unpleasant to write directly - e.g. the language doesn't have variables, so you need to manually do the bookkeeping of which memory offset is storing what 'variable'. & if you need to refactor your program slightly, in a way that changes the memory layout, maybe you need to manually rework the absolute & relative offsets. So I can appreciate why the author didn't roll up their sleeves to directly write BF - that's neither a productive nor interesting exercise.

Interesting to see how the author decomposed the problem:

- C raytracer https://github.com/mTvare6/rayfuck/blob/master/ray.c

~~ LLM refactor of the C code ~~>

- SSA-style C raytracer code https://github.com/mTvare6/rayfuck/blob/master/ray_ssa.c

~~ c2dsl.py helper script (compiler) ~~>

- DSL raytracer https://github.com/mTvare6/rayfuck/blob/master/ray.dsl

~~ dsl2bf.py helper script (another compiler) ~~>

BF raytracer https://github.com/mTvare6/rayfuck/blob/master/ray.bf (~22 mb of unreadable nonsense)

The dsl2bf compiler has a bunch of examples of implementing slightly higher level abstractions atop BF primitives. E.g. "go" to move the pointer to a different offset, destructive & non-destructive copies, all the way up to things like division -- BF only natively offers unary addition/subtraction.

If we have a read of the code of the final compiler, dsl2bf.py, the abstractions used in that code are relatively simple: global variables, local variables, lists, dicts, for loops, function definitions & function calls. It is feasible to implement a simple compiler like dsl2bf in BF itself, with sufficient head scratching. Again, quite unpleasant to try it directly in BF, but a next step could be to implement the dsl2bf compiler in the DSL itself - extending it if necessary, then compiling it with itself to produce a dsl2bf compiler implemented in BF.

That does sound like a fun step, I'd already begun experimenting with some optimizations after having received suggestions in reddit to add fork/join primitives. Adding a compiler with these added performance gains sounds reasonable and something which will run quickly. dicts certainly involve some thought there.

I hadn't considered self-hosting the compiler, but having put it into works, I probably will.

This was the render the speed up version gave: https://paste.c-net.org/SpikingCarbs

> dicts certainly involve some thought there

One way to start could be to ignore performance of the data structure.

The first main job dicts are being used for is the `mem` dict mapping a key (variable name) to some value record.

A data structure that supports Store(K, V) & V = Get(K) could be something like an stack allocated array of (Key, Value) pairs, that you search through using linear search to implement Store & Get. It wouldn't be very fast, but you probably don't have too many items in a typical DSL program. You'd need to implement some kind of stack or so on - or perhaps you could get away with reserving some fixed capacity.

Well the problem is that the DSL uses strings, so any representation which keeps variable names as strings still needs storage and comparison, which currently only the fixed type does. Though c2dsl could instead use a unique integer for every string for variables.

The first value of each instruction would then always be one of a fixed set of opcodes, variables their IDs, and numbers left as-is (and we've invented machine code :)). Then (K, V) is always fixed-size and laid out predictably in memory, so the linear-search approach sounds reasonable.

another approach could be to support strings, of length exactly 1. would 256 unique strings be enough to name all the variables (& functions?) in an interesting program?

Yup.

> rg var ray.dsl | wc -l

142

> rg func ray.dsl | wc -l

6

+28 for opcodes, bringing it to 176. So it works for this interesting program, the raytracer, but the compiler likely requires way more. Maybe not the 4 cells I've been using, but 2^16 = 65k would be enough buckets but unique names.

There have been some other attempts to build compilers that output brainfuck.

This one supports some LLVM IR instructions: https://github.com/caozhanhao/llvm-brainfuck

There's a list of others here, with asm2bf seeming the most complete: https://esolangs.org/wiki/Brainfuck_code_generation

The operations generated for the DSL does cover most of the assembly instructions present in asm2bf on insoection. And goes further by supporting some math.h values by hardcoding them and making them more optimal.

Though the important distinction here is instructions there seem to be for integer types as the base and mine uses fixed point arithmetic by default.

Calling this "written in brainfuck" is like calling anything in C "written in machine code"

I suppose writing the compiler which produces the machine code interesting. Similiarly the blog is about the abstractions and techniques and less so about writing with hand.

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.

Thanks for posting something interesting without uttering LLM, AI, agents, etc. I thought you're going to explain your experience doing it in CMake but then it's true to the title.

Thanks. The CMake bit was to give some context and motivation. Judging by what reaches the front page usually, I should’ve titled it “Using Jev to parse C and decide optimal Brainfuck for 2¢.”

I'm kind of disappointed nobody writes this kind of stuff in Whitespace.

I seems to be easier to have written the same in whitespace given its richer featureset. In fact given BF skips past whitespace, both could be in a single file.

Crazy work

Reply on news.ycombinator.com