Viết trình dò tia bằng Brainfuck: khi ngôn ngữ đơn giản nhất tạo ra dự án 23MB

Có những dự án ra đời không vì mục đích thực dụng, mà vì một câu hỏi tò mò: điều gì sẽ xảy ra nếu ta ép một bài toán nặng nhất vào ngôn ngữ tối giản nhất? Một lập trình viên đã trả lời câu hỏi đó bằng cách viết trình dò tia (ray tracer) hoàn chỉnh bằng Brainfuck — ngôn ngữ chỉ có 8 lệnh và một dải ô nhớ vô hạn một chiều.

Kết quả: chương trình nặng 23MB, chậm tới mức mỗi phút chỉ tính được một pixel, và bức ảnh thu được méo mó tới mức trông như tranh của Van Gogh.

Hình ảnh render méo mó vì lỗi làm tròn số của chương trình Brainfuck

Xuất phát từ một dòng tài liệu CMake

Trong lúc ôn luyện cho một cuộc thi lập trình hệ thống bằng C++, tác giả đọc lại tài liệu hướng dẫn CMake — vì đã quen với sự tiện lợi của Cargo (trình quản lý gói của Rust) nên anh thấy khá vất vả khi quay lại. Trong tài liệu có một đoạn đáng chú ý:

Đôi khi cách đúng đắn là viết một công cụ bằng ngôn ngữ lập trình đa dụng để giải quyết vấn đề, rồi dạy CMake cách gọi công cụ đó trong quá trình build. Sinh mã, tiện ích chữ ký mã hóa, và cả các trình dò tia từng được viết bằng CMake Language, nhưng đây không phải là cách làm được khuyến nghị.

Câu này khiến anh tự hỏi: nếu CMake làm được, thì ngôn ngữ nào còn "tệ hơn" nữa? Câu trả lời là Brainfuck.

Brainfuck hoạt động thế nào?

Brainfuck (BF) chỉ có 8 phép toán và một cấu trúc dữ liệu duy nhất: một dải ô (cell) vô hạn về một phía, mỗi ô lưu một số nguyên 8 bit không dấu (u8).

• > di chuyển con trỏ dữ liệu sang phải
• < di chuyển con trỏ dữ liệu sang trái
• + và - tăng/giảm giá trị ô hiện tại
• . và , xuất/nhập ký tự
• [ và ] tạo vòng lặp: nếu ô hiện tại bằng 0 thì nhảy qua khớp ], ngược lại thì lặp

Không có thanh ghi, không có lệnh nào thao tác trên nhiều hơn một ô, và không có cả lệnh cộng hay nhân. Vậy mà nhờ vòng lặp [ ], BF vẫn có thể đạt tính Turing-complete — tức về lý thuyết có thể tính được mọi thứ máy tính làm được.

Một bài tập nhỏ để làm quen: viết chương trình "cat" (đọc vào rồi in ra) chỉ với 5 ký tự. Tác giả chọn BF chính vì một ngôn ngữ đơn giản thì phần đếm dòng mã nguồn cũng phải đơn giản — các chương trình BF thường chỉ dài vài dòng.

Minh họa chương trình Brainfuck tối giản

Biểu diễn số thực bằng chuỗi ô nhớ

Việc đầu tiên là biểu diễn số thực. Tác giả quyết định mỗi số thực kiểu double sẽ dùng nhiều ô nhớ kết hợp lại, một nửa biểu diễn phần nguyên, một nửa biểu diễn phần thập phân — thực chất là đặt dấu chấm nhị phân cố định ở giữa. Cách này về sau anh mới biết có tên chính thức là định dạng Q.

Ban đầu anh tính dùng Q8.8 có dấu cho rẻ, với độ phân giải 1/256 và dải giá trị khoảng [-128, 128). Nhưng cảnh báo một quả cầu dùng làm mặt đất cần bán kính r = 1000 mới trông phẳng, nên phải nâng lên Q16.16 có dấu — tốn kém hơn nhưng đủ dùng, với độ phân giải 1/2^16.

Chuyển mã nguồn sang dạng SSA

Tác giả chọn chuyển mã nguồn sang dạng giống SSA (Static Single Assignment) — trong đó mã đệ quy được chuyển thành vòng lặp, và biến định nghĩa trong hàm được đặt tiền tố theo kiểu Hungarian notation để tránh trùng tên khi tra cứu địa chỉ.

Anh tách riêng phần phân tích cú pháp (parsing) và phần sinh mã (codegen), dùng một DSL trung gian làm IR. DSL này chứa các phép toán đơn giản như 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, while.

Đây cũng là chỗ duy nhất tác giả dùng LLM (mô hình ngôn ngữ lớn) hỗ trợ: chuyển mã nguồn sang dạng SSA.

Bài toán khó: căn bậc hai và số ngẫu nhiên

Ba hàm thư viện cần dùng là sqrt, rand và abs. Với rand, anh cân nhắc vài cách sinh số giả ngẫu nhiên nhưng chu kỳ quá kém, cuối cùng chọn công thức đơn giản:

A = (5*A + 1) % 256

Công thức này đảm bảo lặp lại chỉ sau trọn vẹn 256 giá trị — đủ tốt cho mục đích lấy mẫu siêu phân giải khử răng cưa.

Với sqrt, anh thử công thức Heron, rồi chuỗi Taylor, nhưng chuỗi Taylor cho kết quả tệ ở vùng giá trị dưới 0,305 — một vùng rất quan trọng. Cuối cùng anh chọn phương pháp chia dài kiểu trường học (School Method):

isqrt(2^16 * N) = sqrt(x) * 2^16

Vì sai lệch một đơn vị ở kết quả mã hóa chỉ làm căn bậc hai giải mã lệch chưa tới 1/2^16 (khoảng 0,00001526), phương pháp này đủ chính xác.

Nhân, chia, so sánh trên chuỗi ô nhớ

Hai nguyên hàm quan trọng là move (di chuyển) và copy (sao chép). Phép copy hoạt động bằng cách liên tục giảm giá trị ô nguồn cho tới 0, mỗi lần giảm thì tăng ô đích tương ứng — tạo ra bản sao.

Phép nhân trên giá trị bốn ô được thực hiện bằng cách nhân từng cặp ô rồi cộng vào vị trí tổng chỉ số của kết quả tám ô:

result[i+j] += a_i * b_j

Phép chia dùng cách chia dài thủ công, đọc số bị chia từ ô quan trọng nhất, mỗi bước chuyển số dư sang ô kế tiếp rồi trừ dần số chia:

while R >= D:
    R -= D
    result += 1

Cách này cần tối đa 255 phép trừ mỗi ô — rất tốn kém, nhưng đúng đắn.

Kết quả: 23MB, một pixel mỗi phút

Chương trình cuối cùng nặng 23MB — còn lớn hơn cả bức ảnh nó tạo ra (khoảng 0,9MB). Tác giả hóm hỉnh nhận xét: đây là một kỹ thuật nén dữ liệu khá tệ.

Về tốc độ, chương trình tính được khoảng 100 phép tính tia mỗi phút, tức một pixel mỗi phút. Với ảnh 400x225, ước tính ban đầu là khoảng 62,5 ngày trên laptop — nhưng vì tia sáng còn phải nảy quanh các quả cầu, thời gian thực tế sẽ lâu hơn nhiều.

Tại thời điểm viết bài, trong số 90.000 pixel thì mới có 1.229 pixel được render, và chỉ 10 pixel khác biệt so với bản tham chiếu — hầu như lệch đúng một đơn vị.

Điều thú vị là bức ảnh render ra trông rất giống tranh Van Gogh, nhiều khả năng do lỗi làm tròn số tích lũy qua hàng loạt phép toán số học nhị phân.

Có thể tối ưu không?

Tác giả cho rằng vẫn còn dư địa tối ưu:

• Giảm độ chính xác để ít ô nhớ bị chạm tới, nếu chấp nhận mặt đất được xấp xỉ thô hơn
• Bỏ bước chuẩn hóa vector ngẫu nhiên, dù cách này làm thay đổi phân bố tán xạ nên không còn tái hiện chính xác đoạn mã gốc

Sau đó, một bình luận trên Reddit hỏi anh có thể cải thiện bằng các nguyên hàm fork/join hay không. Tác giả thấy thú vị nên đã lao vào tối ưu trình thông dịch JIT và đạt được cải thiện hiệu năng đáng kể.

Góc nhìn cho lập trình viên Việt Nam

Câu chuyện này nhắc nhở một điều quen thuộc: đôi khi giới hạn lại là chất xúc tác sáng tạo tốt nhất. Viết một trình dò tia bằng C++ hay Rust có thể mất vài giờ, nhưng viết bằng Brainfuck buộc tác giả phải hiểu tường tận từng bit, từng phép nhân, từng lỗi làm tròn.

Với anh em lập trình viên trong nước, đây cũng là bài học về thiết kế IR và tách tầng: dù mục tiêu là một ngôn ngữ kỳ quặc, kiến trúc parser → IR → codegen vẫn là cách tiếp cận hiệu quả để chia nhỏ độ phức tạp. Và đôi khi, những dự án "vô dụng" nhất lại dạy ta nhiều nhất về chính công cụ mình dùng hằng ngày.

Toàn bộ mã nguồn dự án có tên rayfuck được tác giả công khai trên kho mã nguồn cá nhân.