Lox như một module ngôn ngữ Racket: Kinh nghiệm và kỹ thuật triển khai

Trong một thời gian dài, tôi luôn muốn xây dựng một module ngôn ngữ trong Racket có cú pháp bề mặt không mang phong cách Lisp. Lox, ngôn ngữ xuất hiện trong cuốn sách nổi tiếng Crafting Interpreters, là một ứng cử viên sáng giá. Tôi không muốn phải sáng tạo ra một cú pháp hay ngữ nghĩa mới, và tôi cũng đã từng chuyển dự án này sang C#. Mục tiêu chính của tôi là khai thác các tiện ích xây dựng ngôn ngữ mạnh mẽ của Racket đồng thời học hỏi về Racket, Scheme và macros.

Tôi đã từng thử thực hiện việc này vài năm trước nhưng không thành công. Lần này, tôi bỏ qua các thư viện yacc và lex, thay vào đó tuân theo cách tiếp cận trong sách chặt chẽ hơn, dựa trên phiên bản C# tôi đã viết trước đó. Kết quả là mã nguồn không quá mang phong cách hàm (functional): scanner và parser khá là mệnh lệnh (imperative) và dựa vào mutation, chủ yếu vì điều đó giúp việc port mã từ các triển khai cũ trở nên dễ dàng hơn. Một sự trợ giúp lớn khác đến từ các LLM; tôi đã sử dụng GitHub Copilot và nó giúp tôi lấp đầy những khoảng trống trong kiến thức cũng như khắc phục các sự cố mà tôi thực sự chưa đủ năng lực để giải quyết.

Tôi không sử dụng tính năng autocomplete của GitHub Copilot vì nó làm mất đi niềm vui khi lập trình, nhưng tôi đã "trò chuyện" rất nhiều với nó và cũng yêu cầu nó tạo ra những phần tôi không特别 quan tâm, chẳng hạn như bộ tô màu (colorer) cú pháp. Mã nguồn đã có sẵn trên GitHub. Trong bài viết này, tôi sẽ đi qua quá trình triển khai, làm nổi bật tất cả các phần mà tôi thấy thú vị hoặc hữu ích.

Chiến lược triển khai

Mục tiêu của dự án là tạo ra một triển khai Lox dưới dạng module ngôn ngữ Racket. Với tôi, điều đó có nghĩa là vượt qua tất cả các bài kiểm thử từ kho lưu trữ Crafting Interpreter đến Chương 13. Kho lưu trữ triển khai gốc cung cấp một script Dart để thực thi bộ kiểm thử đối với bất kỳ trình thông dịch nào:

dart tool/bin/test.dart chap13_inheritance --interpreter racket

Để làm được điều này, tôi đã thêm #lang racket-lox vào đầu mỗi tệp kiểm thử và thay đổi dòng mong đợi bằng cách cộng thêm 1. Cách tiếp cận này hiệu quả khi bạn đã có một module ngôn ngữ "hoạt động" tại chỗ. Vì lý do này, vài bước đầu tiên của việc triển khai đã được thực hiện mà không cần "xác thực". Tôi đã viết một phần giả (stub) của scanner, parser và mở rộng ngôn ngữ. Một khi có thể chạy các bài kiểm thử, vòng lặp phát triển diễn ra khá suôn sẻ. Tôi đã thêm một vài bài kiểm thử đơn vị để xác nhận một số hành vi và lặp lại nhanh hơn trên các phần của triển khai.

Triển khai được xác thực ở nhiều cấp độ:

• Vượt qua bộ kiểm thử chap13_inheritance từ sách.
• Phần lớn triển khai, bao gồm scanner, parser và resolver đều có bài kiểm thử đơn vị.
• Có một vài bài kiểm thử runtime.

Mặc dù triển khai cuối cùng vượt qua tất cả các bài kiểm tra Lox có liên quan và tất cả các bài kiểm tra đơn vị được thêm vào kho lưu trữ, điều đó không nhất thiết có nghĩa là mọi trường hợp biên đều hoàn toàn chính xác. Ví dụ, một bài đánh giá từ Gemini đã phát hiện ra một vấn đề trong việc đánh giá -(-0.0) mà không bài kiểm tra Lox gốc nào hay bài kiểm tra của tôi phát hiện ra.

Định nghĩa ngôn ngữ racket-lox

Là một ngôn ngữ lập trình hướng ngôn ngữ (language-oriented programming), Racket cung cấp tất cả các tiện ích cần thiết để xây dựng các ngôn ngữ lập trình tùy chỉnh. Điều này có nghĩa là phải xây dựng hai phần khác nhau:

• Expander module: Đây là module đầu tiên được nhập và chứa tất cả các ràng buộc sẽ khả dụng. Đặc biệt, có một dạng ngầm định #%module-begin phải được cung cấp.
• Reader module: Module này chịu trách nhiệm đọc văn bản chương trình và chuyển đổi nó thành mã Racket.

Để so sánh giữa các thành phần triển khai Lox và các phần của racket-lox, ta có thể nói:

• Scanner: Cả Lox và racket-lox đều có scanner. Hành vi gần giống nhau, scanner của racket-lox trả về danh sách các token (cộng thêm lỗi nếu có).
• Parser: Cả hai đều có parser. Tuy nhiên, hành vi khác nhau; parser của racket-lox trả về các đối tượng cú pháp (syntax objects) của Racket. Không có AST được định nghĩa trước với các lớp.
• Interpreter: racket-lox không có trình thông dịch. Ngôn ngữ này không được thông dịch; tệp lox.rkt chứa các macros và functions tái tạo hành vi của Lox trong Racket.
• Resolver: Cả hai đều có resolver, nhưng hành vi khác biệt. Resolver của Lox thực thi tại runtime trước khi chuyển AST cho trình thông dịch. Trong racket-lox, resolver thực thi tại thời điểm biên dịch (compile time).

Xác minh resolver chạy tại thời điểm biên dịch

Thực thi mã sau:

#lang racket-lox
print "before";
this;

Kết quả đầu ra sẽ là:

[line 3] Error at 'this': Can't use 'this' outside of a class.

Vì không có thông báo "before" nào được in ra, chúng ta biết rằng resolver được thực thi trước mã từ tệp nguồn.

Hỗ trợ tái định nghĩa biến

Lox hỗ trợ tái định nghĩa biến trong phạm vi cấp cao nhất (top-level scope). Để hỗ trợ điều này, tôi đã định nghĩa một hàm thực thi tại thời điểm mở rộng là resolve-redefinitions. Hàm này đi qua tất cả các câu lệnh cấp cao nhất nhận được từ parser và thay thế lox-var-declaration bằng lox-assign bất cứ khi nào chúng ta tái định nghĩa một biến hiện có.

Scanner và Parser

Scanner

Scanner chủ yếu暴露 hàm scan-tokens và một vài struct tùy chỉnh. Nó nhận một cổng đầu vào (input port) và duyệt qua mã nguồn. Do phong cách mệnh lệnh của việc triển khai, tôi cũng định nghĩa một macro while để sử dụng trong các vòng lặp và mô phỏng sát triển khai trong sách. Một điểm thú vị là sử dụng for/list kết hợp với in-producer để xây dựng danh sách, giúp mã gọn gàng hơn so với việc dùng cons và reverse thủ công.

Parser

Parser không có cây cú pháp (AST) với các kiểu được định nghĩa trước mà tạo ra phiên bản "kiểu Lisp" của cú pháp Lox. Nhờ hỗ trợ macro, tôi đã có thể trích xuất một số logic lặp đi lặp lại khi phân tích các biểu thức nhị phân. Ví dụ, việc xử lý gán (assignment) sử dụng syntax-parse để kiểm tra hình dạng của cú pháp thay vì kiểm tra kiểu đối tượng như trong C# hay Java, giúp chuyển đổi đúng sang cú pháp gán của Lox.

Xử lý ngữ nghĩa: Nil, Truthiness và Return

Việc chuyển đổi cú pháp Lox sang Racket gặp phải nhiều khác biệt về ngữ nghĩa cần xử lý thủ công.

Nil và Truthiness

Nil của Lox được đại diện bởi liên kết lox-nil. Để hỗ trợ khái niệm "đúng" (truthiness) của Lox, một hàm trợ giúp lox-truthy? được định nghĩa để đảm bảo các giá trị như false hoặc nil được coi là sai, trong khi các giá trị khác là đúng.

Câu lệnh Return

Racket không có câu lệnh return tích hợp cho thân hàm, nhưng cung cấp cơ chế để thực hiện nó. Về mặt runtime, let/ec (escape continuation) được sử dụng. Về mặt macro, một tham số cú pháp (syntax parameter) được dùng để đảm bảo rằng return bên trong một hàm lồng nhau sẽ thoát khỏi hàm bên trong đó chứ không phải hàm bên ngoài.

Hệ thống Class và Kế thừa

Định nghĩa Class là phần phức tạp nhất. Thay vì sử dụng hệ thống class sẵn có của Racket (và quá phức tạp để mở rộng), tác giả đã định nghĩa hai struct tùy chỉnh: lox-class-constructor và lox-class-instance.

• lox-class-constructor: Tương tự như LoxClass trong sách, có thể gọi được để tạo ra instance.
• lox-class-instance: Đại diện cho một thể hiện của class, chứa tham chiếu đến class của nó và các trường (fields).

Các từ khóa this và super được xử lý thông qua các syntax parameters. Khi một phương thức được gọi, this được ràng buộc với đối tượng nhận (receiver) tại runtime, trong khi super được ràng buộc với giá trị lớp cha tại thời điểm biên dịch.

Các vấn đề tương thích khác

In ấn (Printing)

Việc in ấn trong Lox có những yêu cầu đặc biệt, ví dụ in số nguyên không có dấu .0 hoặc xử lý số âm -0. Hàm lox-print đã được tùy chỉnh để kiểm tra kiểu dữ liệu và định dạng chuỗi đầu ra đúng theo quy cách của Lox, sử dụng các struct tùy chỉnh để hiển thị tên class và instance rõ ràng.

Số học (Numbers)

Racket và Lox xử lý số hơi khác nhau. Việc chia trong Lox giống như chia số thực double của Java. Do đó, việc chia được triển khai bằng cách chuyển đổi sang số inexact. Việc so sánh sự bằng nhau của các số cũng cần xử lý riêng biệt, đặc biệt là với giá trị NaN.

Kết luận

Việc triển khai Lox như một module ngôn ngữ trong Racket là một bài tập thú vị để khám phá sức mạnh của macros và hệ thống module của Racket. Dù gặp nhiều thách thức về sự khác biệt ngữ nghĩa giữa hai ngôn ngữ, sự kết hợp giữa chiến lược triển khai cẩn thận và sự hỗ trợ từ các công cụ AI hiện đại như GitHub Copilot đã giúp hoàn thành dự án thành công. Mã nguồn hoàn chỉnh có sẵn trên GitHub cho những ai muốn tìm hiểu sâu hơn về kỹ thuật biên dịch và thiết kế ngôn ngữ.