Catlang: ngôn ngữ lập trình biên dịch ra một câu SQL

Một ngôn ngữ lập trình, nhưng đầu ra là một câu SQL

Một bài viết trên blog Reasonably Polymorphic giới thiệu catlang, một ngôn ngữ lập trình nhỏ do chính tác giả phát triển, với trình biên dịch sinh ra đúng một câu SELECT khổng lồ. Khi chạy câu truy vấn đó trên PostgreSQL, bạn nhận được kết quả đầu ra của chương trình.

Điểm thú vị không nằm ở SQL, mà ở ngôn ngữ trung gian (intermediate language — IL) của catlang: nó dựa hoàn toàn trên lý thuyết phạm trù (category theory), một lĩnh vực toán học trừu tượng. Tác giả cho biết mình viết dự án này trong thời gian nghỉ làm, chủ yếu để có một đích biên dịch "vui vẻ" nhằm kiểm thử các tính năng thực sự của ngôn ngữ.

Ví dụ: hàm trả về 100 bằng vòng lặp

Tác giả đưa ra một hàm count nhận đầu vào kiểu Int và trả về 100 bất kể đầu vào là gì — nhưng thực hiện nó bằng cơ chế tương đương một vòng lặp while. Khi biên dịch, hàm này sinh ra một câu SQL dài hàng trăm dòng với các lớp lồng WITH, UNION, CROSS JOIN và một recursive CTE (truy vấn đệ quy).

Chạy trên PostgreSQL 17, câu truy vấn trả về đúng một dòng, một cột với giá trị 100, và thực sự lặp từng bước cho tới 100. Nếu sửa mệnh đề ORDER BY step DESC LIMIT 1 thành ORDER BY step DESC, kết quả sẽ trả về một dòng cho mỗi bước lặp.

Nền tảng lý thuyết: chỉ có mũi tên, không có hàm

Ngôn ngữ trung gian của catlang vận hành trên hai khái niệm: kiểu (type) và mũi tên (arrow) giữa các kiểu. Có hai phép cơ bản:

• id: mũi tên "không làm gì" từ một kiểu về chính nó
• Phép hợp (composition): nối đầu ra của mũi tên này vào đầu vào của mũi tên khác

Khác với Haskell hay hầu hết ngôn ngữ lập trình, catlang không có khái niệm áp dụng hàm (function application) — không tồn tại mũi tên nhận một hàm và một giá trị rồi trả về kết quả. Bạn chỉ có thể hợp các mũi tên, chứ không thể "gọi" chúng. Đó là lý do chúng được gọi là mũi tên thay vì hàm.

Từ đó, tác giả xây dựng thêm các bộ công cụ:

• Product: hai phép chiếu lấy thành phần từ cặp, và phép "fork" (△) tạo ra cặp từ hai mũi tên độc lập — vì không có phụ thuộc dữ liệu giữa hai bên, chúng có thể chạy song song
• Coproduct: phiên bản đối ngẫu của product, biểu diễn kiểu "hoặc a hoặc b, nhưng chắc chắn không phải cả hai và cũng không phải không cái nào", kèm phép "join" (▽) để rẽ nhánh

Chỉ với tám phép toán này, ngôn ngữ đã đủ biểu đạt: hợp để mô tả phụ thuộc dữ liệu, join để rẽ nhánh, fork để tạo cấu trúc dữ liệu và cơ hội song song hóa.

Không có tên biến — lợi thế khi biên dịch

Điều đáng chú ý là ngôn ngữ trung gian không hề có tên biến. Quá trình desugar (hạ cấp) ngôn ngữ nguồn sẽ dựng một stack và thay mọi lần tra cứu biến bằng một chuỗi phép chiếu trên stack để tìm lại giá trị.

Cách làm này khiến IL khó đọc với con người, nhưng lại rất dễ nhắm tới các đích biên dịch khác nhau: nhiều miền bài toán có khái niệm "nhóm" nhưng không có khái niệm "đặt tên". Ví dụ, trong mạch điện tử, một bó 32 dây biểu diễn Int32, và hai bó như vậy có thể nối thành một bó 64 dây cho cặp (Int32, Int32). Loại bỏ tên trước khi vào IL nghĩa là không backend nào phải xử lý tên biến.

Vòng lặp và cách biên dịch sang SQL

Cơ chế lặp dựa trên primitive cochoice, biến một mũi tên trên kiểu "hoặc" thành mũi tên thông thường. Nếu hàm trả về nhánh trái thì dừng và xuất kết quả; nếu trả về nhánh phải thì đưa ngược lại vào chính nó. Cách mô tả này cho phép phân biệt tĩnh giữa lần lặp đầu tiên và các lần sau — hữu ích cho những đoạn mã cần khởi tạo riêng ở lần đầu.

Về phía SQL, tác giả ánh xạ từng phép toán:

• id biên dịch thành SELECT * FROM {}
• Hợp thành một truy vấn lồng nhau
• Phép fork thành CROSS JOIN
• Phép join thành UNION, kèm điều kiện WHERE field IS NOT NULL để đảm bảo đang xét đúng nhánh của coproduct
• cochoice thành recursive CTE

Phần khó nhất là biểu diễn dữ liệu cho coproduct. Tác giả chọn cách "làm phẳng": kiểu (Int, Either Int Int) được biểu diễn bằng ba cột, với ràng buộc là đúng một trong hai cột biến thể có giá trị khác NULL.

Với recursive CTE, do đặc thù ngữ nghĩa bảng của SQL là multiset và cách PostgreSQL chấp nhận cú pháp, tác giả không chèn được cột đếm số lần lặp. Thay vào đó, ông dùng clock_timestamp() làm cột step và sắp xếp theo đó — một giải pháp được chính tác giả thừa nhận là "hack", có thể gây vấn đề nếu sau này thêm primitive sinh nhiều dòng.

Những hướng đi "ngớ ngẩn" trong tương lai

Tác giả đã hết thời gian nghỉ nên khó quay lại dự án, nhưng vẫn phác ra vài hướng:

• Bổ sung primitive xử lý chuỗi, rồi viết trình thông dịch Brainfuck bằng catlang và biên dịch sang SQL — tức chạy Brainfuck trong PostgreSQL. Việc chạy Brainfuck trong Postgres từng được làm thủ công, nhưng theo tác giả thì chưa từng được làm qua biên dịch
• Vì có trình biên dịch C sang Brainfuck và PostgreSQL viết bằng C, về lý thuyết có thể "chạy PostgreSQL trong PostgreSQL"

Tác giả cũng ghi nhận mình không phải người đầu tiên làm việc tương tự: ngôn ngữ nguồn của catlang lấy cảm hứng mạnh từ cú pháp arrow của Haskell, và ý tưởng ngôn ngữ lập trình có ngữ nghĩa phạm trù đã là kiến thức phổ biến từ lâu — lambda calculus tương ứng với phạm trù đóng Cartesian. Ông cũng cho biết chịu ảnh hưởng từ bài báo Compiling to Categories. Toàn bộ mã nguồn có trên GitHub, bao gồm một backend template-haskell có thể sinh mã Haskell.

Góc nhìn

Với lập trình viên Việt Nam, catlang là một ví dụ rất rõ về giá trị của việc hiểu ngôn ngữ trung gian trong thiết kế trình biên dịch. Khi IL đủ trừu tượng — ở đây là chỉ có kiểu và mũi tên — việc thêm một backend mới trở nên gọn gàng hơn nhiều, vì backend đó không phải xử lý tên biến hay cú pháp nguồn. Đây là tư duy đáng tham khảo cho những ai làm DSL (ngôn ngữ chuyên biệt theo miền) hoặc các công cụ sinh mã.

Ở góc độ thực dụng, việc biên dịch logic phức tạp thành SQL — đặc biệt là tận dụng recursive CTE để thay cho vòng lặp ở tầng ứng dụng — là hướng đi mà nhiều đội backend có thể cân nhắc khi muốn giảm số lần qua lại giữa ứng dụng và cơ sở dữ liệu. Tuy vậy, cần lưu ý rằng cách dùng clock_timestamp() để đánh số bước lặp trong bài là giải pháp tình thế, không phù hợp cho hệ thống thật; với dữ liệu lớn, một câu SQL đệ quy khổng lồ cũng đặt ra câu hỏi về khả năng đọc hiểu và bảo trì. Dự án này nên được xem là thí nghiệm về ý tưởng, không phải mẫu thiết kế để sao chép nguyên văn.