한 개발자가 8개 명령어만 있는 난해한 프로그래밍 언어인 브레인퍽(Brainfuck)으로 실제 동작하는 레이트레이서를 처음 원칙(first principles)부터 구현한 도전기입니다. 고정소수점 Q16.16 형식으로 부동소수점을 흉내 내고, 재귀 코드를 반복형으로 변환하는 등 극도로 제한된 언어의 한계를 극복한 과정을 다룹니다. 튜링 완전한 언어라면 이론상 무엇이든 만들 수 있음을 보여주는 재미있는 사례입니다.
번역된 본문
C++ 시스템 프로그래밍 대회를 준비하면서 CMake를 다시 배우기 시작했는데, 그동안 Cargo에 너무 익숙해져 있던 터라 튜토리얼에서 흥미로운 주장을 하나 발견했습니다. 종종 올바른 답은 문제를 해결하는 도구를 범용 프로그래밍 언어로 작성하고, CMake가 빌드 과정의 일부로 해당 도구를 호출하는 방법을 알려주는 것이라고 합니다. 코드 생성, 암호학적 서명 유틸리티, 심지어 레이트레이서까지 CMake 언어로 작성된 사례가 있지만, 권장되는 방식은 아니라고 되어 있었습니다.
CMake 언어의 기본 원리
예전에 레이트레이서를 작성해본 적이 있었고, GPU용으로 다시 작성한 경험이 있었기에, 이 문장이 눈에 띄었고 레이트레이서를 작성하기에 더 훌륭한 언어가 무엇일지 궁금해졌습니다. 마지막으로 다시 작성했을 때는 원리 기반 접근이 거의 없었고 비교적 복잡한 API 집합에 대부분 의존하는 코드를 작성했습니다. 그래서 제가 아는 가장 단순한 언어인 BF를 선택했습니다. 단순한 언어는 당연히 매우 단순한 코드베이스를 만들어내기 때문입니다. 실제로 BF로 작성된 코드베이스는 보통 몇 줄에 불과한 경우가 많습니다. 게다가 README에 있는 뮐러(Muller)의 코멘트에 반례를 보여주고 싶었습니다. 코드는 mTvare6/rayfuck에서 확인할 수 있습니다.
입문
BF는 확실히 단순한 언어로, 단 8개의 연산과 하나의 "자료구조"만 존재합니다. 각 셀이 u8을 저장할 수 있는, 한쪽으로 무한한 셀들의 테이프입니다. > 문자를 만나면 테이프의 셀을 가리키는 데이터 포인터가 오른쪽으로 이동하고, <를 만나면 반대로 이동합니다. 입출력은 , 와 . 로 처리됩니다. 전자는 데이터 포인터가 가리키는 위치에 입력 바이트를 저장하고, 후자는 그것을 출력합니다. 입출력 외에 값을 변경할 수 있는 유일한 기본 연산은 데이터 포인터 위치에서의 증가와 감소, 즉 + 와 - 입니다. 한계는 명백합니다. 다른 기계들이 보통 가지는 n > 1 개의 레지스터가 없고, 두 개 이상의 셀에 대해 작동하는 명령어가 없으며, 덧셈이나 곱셈을 위한 명령어도 없습니다. BF를 튜링 완전하게 만드는 마지막 요소는 [ 와 ] 로 작성되는 루프입니다. [ 토큰을 만나면 런타임은 데이터 포인터의 셀을 검사합니다. 값이 0이면 실행은 짝이 되는 ] 를 넘어 점프하고, 그렇지 않으면 루프에 진입합니다. ] 에서는 셀이 0이 아니면 짝이 되는 [ 로 돌아가고, 0이면 루프를 빠져나갑니다. 간단한 연습으로 cat 프로그램을 작성해보세요. 단 5글자로 작성해보면 이 환경에 대한 감각을 익힐 수 있습니다.
사전 계획
시작하기 전에 관련 자료를 읽었기 때문에, 어떤 결과나 구현 세부사항도 검색하지 않고 가능한 한 원리(first principles)부터 직접 작성하기로 했습니다. 범위를 최소화하고 프로그램을 명백한 레이트레이ser로 만들기 위해, RIW의 Metal 섹션에서 렌더링된 것과 정확히 동일한 이미지를 렌더링하도록 결정했습니다. C 코드는 어쨌든 너무 복잡했고, C 파서를 작성하는 것은 명백히 범위를 벗어났습니다. 유지보수되지 않는 C 파서를 작성하는 일은 Anthropic이 처리하는 게 더 나은 일입니다.
every double(및 bool 같은 다른 데이터 타입)은 셀들을 조합하여 표현하기로 했으며, 절반의 비트는 소수부를, 나머지 절반은 정수부를 나타내어 사실상 그 사이에 고정된 소수점을 두는 방식입니다. 나중에 이것이 Q 포맷(Q format)이라고 불린다는 것을 알게 되었습니다. 더 저렴한 부호 있는 Q8.8을 사용하면 해상도는 1/256이고 범위는 약 [-128, 128)이 됩니다. 하지만 이것만으로는 명백히 부족했습니다. 장면에서 바닥으로 사용되는 구체가 평평하게 보이려면 반지름이 r=1000이어야 했기 때문입니다. 그래서 더 비싼 부호 있는 Q16.16 포맷을 사용했습니다. 해상도는 1/2^16이고 범위는 [-2^15, 2^15)로, 이 정도면 충분합니다.
코드를 SSA와 유사한 형식으로 변환하기로 했으며(이 작업이 LLM의 유일한 역할이 될 것이라고 결정했습니다), 재귀 코드는 반복형으로 만들고, 함수 내에서 정의된 변수는 이름 조회 시 충돌을 피하기 위해 헝가리안 표기법 스타일로 접두사를 붙이기로 했습니다. 마찬가지로 파싱과 코드 생성을 분리하는 것이 필요해 보였으며, 복잡도를 나누어 관리하고자 했습니다.
As I was preparing for a systems programming competition in C++, I began to relearn CMake, as Cargo had spoilt me too much in the meantime, and I noticed an interesting claim in the tutorial. Oftentimes the correct answer is to write a tool in a general purpose programming language which solves the problem, and teach CMake how to invoke that tool as part of the build process. Code generation, cryptographic signature utilities, and even ray-tracers have been written in CMake Language, but this is not a recommended practice. CMake Language Fundamentals Having written a raytracer earlier, and re-written it for the GPU, this statement caught my eye and made me wonder what would be an even better language to write a raytracer in. The last re-write involved writing code which had little of a first-principles based approach and mostly depended on a comparatively more complex set of APIs. So I picked the simplest language I knew, BF, because a simple language obviously results in a very simple codebase. In fact, codebases in BF regularly tend to be only a few lines long. Further, Muller’s comment in the README made me want to show a counter example. The code is available at mTvare6/rayfuck . Primer BF is a decidedly simple language, involving only 8 operations and one “data structure”: a one-sided infinite tape of cells, each capable of storing a u8 . On seeing the character > , the data pointer, which points to a cell on the tape, moves rightward, and vice versa on < . I/O is managed through , and . . The first stores the input byte where the data pointer points and the latter prints it out. The only primitives other than I/O which allow changing a value are increment and decrement at the data pointer, through + and - . The limitations should be obvious: there are no n > 1 registers as other machines tend to have, no instruction operating on more than one cell, and no instructions for addition or multiplication. The last ingredient required to make BF Turing-complete is its loop, written using [ and ] . When the token [ is met, the runtime checks the cell at the data pointer: if it is zero, execution jumps past the matching ] , otherwise it enters the loop. At ] , it returns to the matching [ if the cell is non-zero and exits the loop otherwise. A quick exercise would be writing a cat program, try writing one with just 5 characters to get some intuition about the environment. Premeditation Having read about it before starting this, I decided to avoid looking up any result or implementation detail and to write down as much as possible from first principles. To keep the scope minimal, and the program an obvious raytracer, I decided to have it render the exact image rendered through the Metal section of RIW . The C code was a bit too complex regardless, and writing a C parser was clearly out of scope. Writing an unmaintained C parser is something better handled by Anthropic . I decided that every double [and other datatype like bool] would be represented by combining cells, with half the bits representing the fractional part and the other half representing the integer part, effectively placing a fixed binary point between them. I later got to know that this is called a Q format. Going with the cheaper signed Q8.8 would give a resolution of 1/256 and a range of approximately [-128, 128) . But clearly, that wouldn’t be enough, as the sphere used for the ground in the scene had to have r=1000 to appear flat, so I went with the more expensive signed Q16.16 format. It has a resolution of 1/2^16 and a range of [-2^15, 2^15) , which is sufficient. I decided to have the code converted to an SSA-like format [and decided this’ll be the only job for an LLM], where recursive code is made iterative, and variables defined in functions are prefixed in a Hungarian-style notation to avoid name collisions during address lookup for a name. Similarly, separating the parsing and codegen seemed necessary, dividing complexity into two code regions, with an intermediate “DSL” being used as an IR. The DSL contained simple operations such as abs , add , and , call , copy , div , else , end , eq , func , ge , gt , if , int , le , lt , mul , neg , not , or , print2 , print3 , set , sqrt , sub , text , var , and while . The next tricky part was a few library calls. The ones used were sqrt , rand and abs . Initially I planned on using a two-state solution like: A = ( A - B ) % 256 B = ( B + 1 ) % 256 or B = ( B + A + p ) % 256 # for some prime p but most of these variants have a poor period. I decided to go with the simpler A = ( 5 * A + 1 ) % 256 given that it is guaranteed to repeat only after a full sequence of 256 values, which isn’t too bad for this use-case [that is, supersampling anti-aliasing]. sqrt has one obvious candidate, Heron’s formula [of which my memory was refreshed within the same CMake tutorial]. But it was pretty obvious it’d be bad, given it involved division. Repeated subtraction, while producing smaller generated code [which is better, as the interpreter moves less], was still relatively expensive to do. The other candidates were the Taylor series and the “School Method”, which involves long-division. sqrt(1 + x) = 1 + x/2 - x^2/8 y = 2^16*x sqrt(2^16 + y) / 2^8 = (1 + y/2^17 - y^2/2^35 ) sqrt(y) / 2^8 = (1 + (y - 2^16)/2^17 - (y - 2^16)^2/2^35 ) Plotting this on Desmos revealed that the fit was poor below an encoded value of 20k, that is, below roughly 0.305 , which was a pretty important region. This left me with the long-division method, which was pretty simple. If the real value was x , then the represented value was: N = x * 2^16 To represent sqrt(x) , we need: N' = sqrt(x) * 2^16 isqrt(N) = sqrt(x) * 2^8 isqrt(2^16 * N) = sqrt(x) * 2^16 = N' isqrt is justified here, as a difference of one in the encoded result changes the decoded square root by less than 1/2^16 , or approximately 0.00001526 . And finally, the whole variable map and corresponding BF addresses would be maintained with a dictionary. Implementation With the theoretical bits set up, only clearly simple implementation details were left. Two important primitives were move and copy . [a, 0] Move works by continually lowering a value until the cell at the initial data pointer becomes zero, and incrementing the other cell equally every time. [ # start loop - # decrement > + # move right and increment < # come back , this cell is used to control the loop ] as one-liner [ - > + < ] And copy works as below, starting with this array: [a, 0, 0] using the code. [ - > + > + << ] Turning it into: [0, a, a] And now, if needed, the terminal a can be moved inward. Given that addition, and later division, would involve repeated use of temporary values, which have to be near the value to avoid moving the data pointer around too much, every value in the map also has its temporary-variable slots nearby. These also provide carry cells and other useful scratch space, keeping copies contained. Multiplication was similarly straightforward, involving multiplying each cell, storing the results and adding them together later. The multiplication step is taken care of through repeated addition. For multiplying two cells, one of them is copied to a temporary place and used as the outer loop, and the other is copied once for every iteration to act as the inner loop. Every iteration of the inner loop increments the result once. [a, b, a->0, b->0, a + ... + a] Here a runs out every time and b is decremented when a is zeroed, producing b copies of a . For the four-cell values, every cell in one is paired with every cell in the other. A multiplication of the cells at i and j is added at i+j in an eight-cell result. [a0, a1, a2, a3] * [b0, b1, b2, b3] result[i+j] += a_i*b_j Since both inputs already had 2^16 in their representation, the lowest 2 cells are discarded when copying back the result. N_1 = x_1 * 2^16 N_2 = x_2 * 2^16 ( N_1 * N_2 ) / 2^16 = N = (x_1 *