Chỉ cần tính 1+1, nhưng lại xây luôn cả một ngôn ngữ lập trình hàm

Đôi khi một bài tập về nhà nhỏ lại trở thành khởi nguồn cho cả một dự án đồ sộ. Đó chính là câu chuyện của một lập trình viên khi nhận đề bài cấu trúc dữ liệu: chuyển một biểu thức số học thành cây nhị phân. Thay vì chỉ dừng ở việc vẽ cây, anh quyết định xây luôn một trình đánh giá biểu thức.

Vài ngày sau, dự án nhỏ bé ấy đã phình to thành một ngôn ngữ lập trình hàm mang tên graphLang, được viết hoàn toàn bằng C, với closure, trình thu gom rác, bộ cấp phát bộ nhớ tùy chỉnh, REPL và cả FFI.

Từ bài tập cấu trúc dữ liệu đến trình đánh giá biểu thức

Đề bài đặt ra khá đơn giản: hãy tính giá trị của biểu thức 1 + 1 + 1 bằng cây nhị phân. Cách tiếp cận cổ điển là đưa toán tử lên làm gốc, còn hai toán hạng trở thành các nút con.

Với biểu thức 1 + 1 + 1, cây sẽ có dạng một phép cộng ở gốc, nhánh trái là một phép cộng khác, nhánh phải là số 1. Để tính được kết quả, trước tiên phải đánh giá nhánh trái — vốn cũng là một biểu thức cộng — và thu gọn nó thành một giá trị duy nhất. Sau đó mới thực hiện phép cộng ở tầng ngoài cùng.

Quá trình đánh giá này chính là nền tảng cho toàn bộ cỗ máy về sau. Thay vì chỉ tính toán một lần rồi kết thúc, anh quyết định biến nó thành một hệ thống có thể mở rộng.

Nhận ra biểu thức chính là một kiểu dữ liệu đại số

Bước ngoặt quan trọng là khi tác giả nhận ra kiểu biểu thức trong chương trình thực chất là một kiểu dữ liệu đại số (Algebraic Data Type). Các biến thể của nó không gì khác ngoài những loại dữ liệu khác nhau: hàm, biến và giá trị hằng.

Đi xa hơn một bước, anh nhận ra biến và hàm thực ra không phải hai thứ tách biệt — suy cho cùng, cả hai đều chỉ là dữ liệu. Từ góc nhìn đó, toàn bộ hệ thống có thể được đối xử thống nhất.

Một loạt thành phần tiếp theo được xây dựng:

• Trình đánh giá dạng đồ thị (graph evaluator), có khả năng biến đổi ngay tại nút hiện tại sau khi đánh giá
• Bảng môi trường (Environment Table) dùng bảng băm tự viết
• Bộ cấp phát bộ nhớ theo khối (chunk allocator) để cấp phát các nút một cách hiệu quả
• Trình thu gom rác mark-and-sweep sau khi nhận ra chương trình đang giữ lại quá nhiều rác

Kết quả là một cỗ máy Graph Reduction hoàn chỉnh — nền tảng lý thuyết đứng sau nhiều ngôn ngữ lập trình hàm hiện đại.

Khi bộ nhớ ổn nhưng tốc độ thì không

Sau khi có trình thu gom rác, vấn đề bộ nhớ tưởng như đã được giải quyết. Nhưng thử thách mới lại xuất hiện.

Khi chạy hàm fib(40), chương trình chỉ tiêu tốn khoảng 1,7 megabyte bộ nhớ — một con số rất ấn tượng. Thế nhưng, để tính xong kết quả, nó mất tới 6 phút.

Nguyên nhân nằm ở hai điểm. Thứ nhất, trình thu gom rác mark-and-sweep là loại stop-the-world, nghĩa là toàn bộ chương trình phải dừng lại trong lúc dọn rác. Thứ hai, bản thân thuật toán Fibonacci đệ quy đã có độ phức tạp tăng theo cấp số nhân.

Đây là minh chứng rõ ràng cho thấy giải quyết được bài toán bộ nhớ chưa chắc đã giải quyết được bài toán hiệu năng.

Hướng giải quyết được tác giả vạch ra gồm hai phần: xây dựng một trình thu gom rác đồng thời (concurrent garbage collector), và cải thiện cách đánh giá hàm Fibonacci — nhiều khả năng bằng kỹ thuật tối ưu hóa đuôi (TCO) cùng cơ chế đánh giá tốt hơn.

Những gì đã đạt được

Tính đến thời điểm hiện tại, dự án graphLang đã bao gồm:

• Bộ lexer và parser hoàn chỉnh
• REPL để thử nghiệm tương tác trực tiếp
• FFI cho phép gọi mã bên ngoài
• Hàm lambda và biến cục bộ
• Chuyển từ việc tham chiếu con trỏ sang mô hình khác
• Cơ chế đóng gói mô phỏng trong C
• Bước chuẩn bị cho Cheney's copying collector — một thuật toán thu gom rác nâng cao

Điều thú vị là tất cả bắt đầu chỉ từ một câu hỏi tưởng chừng ngớ ngẩn: liệu chương trình có tính được 1 + 1 hay không. Và câu trả lời, theo đúng lời tác giả, là: 1 + 1 = 2 theo graphLang.

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

Câu chuyện này mang lại vài bài học đáng suy ngẫm. Thứ nhất, những bài tập nhỏ trên lớp hoàn toàn có thể trở thành dự án học tập nghiêm túc nếu người học chịu đào sâu. Thứ hai, việc tự tay viết trình thu gom rác, bộ cấp phát bộ nhớ hay bảng băm là cách hiểu sâu nhất về cách máy tính thực sự vận hành — điều mà các framework cấp cao thường che giấu.

Với những ai đang học C hoặc muốn nâng cao kỹ năng lập trình hệ thống, việc xây dựng một trình thông dịch nhỏ là bài luyện tập cực kỳ giá trị. Tác giả cho biết toàn bộ mã nguồn còn nhiều phần chưa kể đều đã được đưa lên kho lưu trữ công khai, và series bài viết sẽ tiếp tục ở các phần sau.