Một bài đánh giá gần đây về cuốn sách có ảnh hưởng lớn Compiling with Continuations năm 1992 của Andrew Appel đã khơi dậy những cuộc thảo luận sôi nổi trong cộng đồng ngôn ngữ lập trình về sự phát triển của các biểu diễn trung gian trong trình biên dịch và liệu phong cách truyền tiếp continuation ( CPS ) có còn phù hợp trong thiết kế trình biên dịch hiện đại hay không.
Cuốn sách này, chi tiết cách xây dựng trình biên dịch sử dụng continuation làm biểu diễn trung gian, đã mang tính đột phá trong thời đại của nó. Nó cho thấy cách các chương trình Standard ML có thể được chuyển đổi qua nhiều giai đoạn - từ MiniML đến Lambda đến CPS - trước khi được biên dịch thành mã máy. Phương pháp này hứa hẹn những giải pháp tinh tế cho các vấn đề phức tạp của trình biên dịch như chuyển đổi closure và phân bổ thanh ghi.
Cấu trúc sách và ngôn ngữ
- Sách gốc: " Compiling with Continuations " của Andrew Appel (1992)
- Pipeline biên dịch: MiniML → Lambda → CPS → Abstract Machine Code
- Ngôn ngữ đích: Standard ML ( SML )
- Các chương chính:
- Chương 2-3: Ngôn ngữ CPS và ngữ nghĩa
- Chương 4: Triển khai MiniML
- Chương 5: Biên dịch từ Lambda sang CPS
- Chương 10-11: Chuyển đổi closure và register spilling
Cuộc tranh luận lớn về IR: CPS so với SSA
Cuộc tranh luận gay gắt nhất tập trung vào việc liệu CPS có bị thay thế bởi dạng Static Single Assignment ( SSA ), vốn đã trở thành biểu diễn trung gian thống trị trong các trình biên dịch hiện đại. Các thành viên cộng đồng chia rẽ về câu hỏi cơ bản này. Một số cho rằng CPS đã hoàn toàn chết như một IR và SSA đã thắng, chỉ ra rằng ngay cả trình biên dịch SML/NJ cuối cùng cũng từ bỏ CPS để chuyển sang MLRISC và sau đó là LLVM .
Tuy nhiên, những người khác bảo vệ tính liên quan tiếp tục của CPS , đặc biệt đối với các ngôn ngữ hàm và các trường hợp sử dụng cụ thể. Các nhà phát triển game đã thấy các phép biến đổi CPS đặc biệt hữu ích để triển khai các cấu trúc lập trình bất đồng bộ mà không cần độ phức tạp của việc hỗ trợ call/cc (call-with-current-continuation) đầy đủ.
Lưu ý: CPS (Continuation-Passing Style) là một phong cách lập trình trong đó các hàm không bao giờ trả về giá trị trực tiếp mà thay vào đó truyền kết quả cho các hàm continuation. SSA (Static Single Assignment) là một biểu diễn trung gian trong đó mỗi biến được gán chính xác một lần.
Sự Phát Triển của Compiler Hiện Đại
- Đường Đi Compiler SML/NJ: CPS → MLRISC → LLVM
- Các Phương Pháp Thay Thế:
- SSA (Static Single Assignment) - IR hiện đại chiếm ưu thế
- ANF (Administrative Normal Form) - phương pháp tiếp cận trung gian
- IR dựa trên sequent calculus - nghiên cứu tiên tiến
- Các Yếu Tố Hiệu Suất: Dự đoán nhánh ưu tiên call/return hơn là indirect jumps
Tác động học thuật so với triển khai thực tế
Cuộc thảo luận tiết lộ một sự căng thẳng thú vị giữa ảnh hưởng học thuật và việc áp dụng thực tế. Trong khi cuốn sách đã sinh ra nhiều bài báo tiếp theo với số lần trích dẫn ấn tượng - bao gồm The Essence of Compiling with Continuations được trích dẫn 806 lần - các nhà phát triển gặp khó khăn trong việc tìm kiếm các triển khai hoạt động hoặc ứng dụng hiện đại của những kỹ thuật này.
Sự ngắt kết nối này làm nổi bật một vấn đề rộng lớn hơn trong tài liệu khoa học máy tính: công trình học thuật được trích dẫn nhiều không luôn chuyển đổi thành việc sử dụng thực tế rộng rãi. Việc thiếu các kho lưu trữ GitHub , bài viết blog, hoặc triển khai hiện đại cho thấy rằng mặc dù các ý tưởng có ảnh hưởng về mặt trí tuệ, chúng có thể chưa tìm được đường vào việc xây dựng trình biên dịch hàng ngày.
Các bài báo nghiên cứu tiếp theo
- "The Essence of Compiling with Continuations" (1993) - 806 lần trích dẫn
- "Compiling with Continuations, Continued" (2007) - 154 lần trích dẫn
- "Compiling with continuations, or without? whatever." (2019) - 34 lần trích dẫn
Các lựa chọn thay thế hiện đại và sự phát triển
Cộng đồng trình biên dịch phần lớn đã chuyển sang các phương pháp khác nhau. Administrative Normal Form ( ANF ) đã trở nên phổ biến như một giải pháp trung gian, cung cấp một số lợi ích của CPS mà không có độ phức tạp của nó. Trong khi đó, nghiên cứu tiên tiến khám phá các biểu diễn trung gian dựa trên sequent calculus, có thể biểu đạt continuation một cách tự nhiên hơn so với CPS truyền thống.
Các mối quan tâm về dự đoán nhánh cũng ủng hộ các mẫu lệnh call/return truyền thống hơn là các lệnh nhảy gián tiếp mà biên dịch CPS thường tạo ra, khiến CPS kém hấp dẫn hơn đối với các ứng dụng quan trọng về hiệu suất trên các bộ xử lý hiện đại.
Phán quyết về tính liên quan
Bất chấp những lời chỉ trích, nhiều nhà phát triển đã làm việc với cuốn sách đã tìm thấy giá trị thực sự trong việc hiểu các khái niệm của nó. Các kỹ thuật cho chuyển đổi closure, register spilling và tối ưu hóa vẫn có tính giáo dục, ngay cả khi phương pháp CPS cụ thể đã không còn được ưa chuộng.
Cuộc tranh luận cuối cùng phản ánh sự phát triển nhanh chóng của công nghệ trình biên dịch trong ba thập kỷ qua. Những gì có vẻ mang tính cách mạng năm 1992 có thể xuất hiện lỗi thời ngày nay, nhưng những hiểu biết cơ bản về chuyển đổi chương trình và biểu diễn trung gian tiếp tục ảnh hưởng đến thiết kế trình biên dịch hiện đại, ngay cả khi được thể hiện thông qua các phương pháp kỹ thuật khác nhau.
Tham khảo: Compiling with Continuations