7 dòng code, 3 phút: Triển khai một ngôn ngữ lập trình hoàn chỉnh

Triển khai một ngôn ngữ lập trình là một trải nghiệm mà bất kỳ lập trình viên nào cũng nên thử qua ít nhất một lần. Quá trình này không chỉ giúp nuôi dưỡng sự hiểu biết sâu sắc về tính toán mà còn vô cùng thú vị. Trong bài viết này, chúng ta sẽ chắt lọc toàn bộ quy trình đó để tìm ra cốt lõi của nó: một trình thông dịch (interpreter) chỉ gồm 7 dòng cho một ngôn ngữ lập trình hàm có tính năng tương đương với máy Turing.

Việc triển khai phiên bản rút gọn này chỉ mất khoảng 3 phút. Mặc dù ngắn ngủi, trình thông dịch 7 dòng này lại giới thiệu một kiến trúc có khả năng mở rộng cao, được tìm thấy trong nhiều trình thông dịch hiện đại: đó là mẫu thiết kế eval/apply nổi tiếng từ cuốn sách Structure and Interpretation of Computer Programs.

Sách lập trình kinh điển

Bản chất của Lambda Calculus

Ngôn ngữ lập trình dễ triển khai nhất là một ngôn ngữ lập trình hàm bậc cao tối giản được gọi là phép tính Lambda (Lambda calculus). Trên thực tế, phép tính Lambda sống ở lõi của hầu hết các ngôn ngữ hàm lớn như Haskell, Scheme và ML. Nó thậm chí còn ẩn mình bên trong JavaScript, Python và Ruby, và cả Java nếu bạn biết nơi để tìm kiếm.

Alonzo Church phát triển phép tính Lambda vào năm 1929. Lúc bấy giờ, nó chưa được gọi là ngôn ngữ lập trình vì chưa có máy tính; không có gì để "lập trình" cả. Về cơ bản, nó chỉ là một ký hiệu toán học để suy luận về các hàm.

Điều đáng Remarkable là phép tính Lambda chỉ có ba loại biểu thức:

• Tham chiếu biến (variable references)
• Hàm ẩn danh (anonymous functions)
• Cuộc gọi hàm (function calls)

Hàm ẩn danh được viết bằng ký hiệu "lambda-dot". Ví dụ, (λ v . e) là hàm chấp nhận một đối số v và trả về giá trị của e. Nếu bạn đã lập trình bằng JavaScript, dạng này tương đương với v => e.

Tính tương đương Turing

Nhìn thoáng qua, ngôn ngữ đơn giản này dường như thiếu cả đệ quy và lặp, chưa nói đến các số, boolean, cấu trúc điều kiện, cấu trúc dữ liệu và v.v. Làm thế nào ngôn ngữ này có thể mang tính mục đích chung?

Cách phép tính Lambda đạt được tính tương đương Turing là thông qua hai "thủ thuật" lập trình ngầu nhất: Mã hóa Church (Church encodings) và Y combinator.

Một ví dụ điển hình là chương trình "Omega". Nếu bạn cố gắng thực thi nó, nó sẽ không bao giờ kết thúc (vòng lặp vô hạn), chứng minh sức mạnh tính toán của nó.

Trình thông dịch 7 dòng

Dưới đây là trình thông dịch cho phép tính Lambda trong R5RS Scheme, chỉ gói gọn trong 7 dòng mã (không tính chú thích và dòng trống).

Về mặt kỹ thuật, đây là một trình thông dịch theo nghĩa (denotational interpreter) dựa trên môi trường. Đoạn mã này sẽ đọc một chương trình từ đầu vào tiêu chuẩn (stdin), phân tích cú pháp (parse), đánh giá (evaluate) và in kết quả.

Hàm read của Scheme làm cho việc phân tích từ vựng và cú pháp trở nên đơn giản — miễn là bạn chấp nhận sống trong thế giới cú pháp "dấu ngoặc cân bằng" (s-expression).

Hai hàm tạo nên lõi của trình thông dịch là: eval và apply.

• Hàm eval nhận một biểu thức và một môi trường để tạo ra một giá trị. Biểu thức có thể là biến, lambda term hoặc một ứng dụng.
• Hàm apply nhận một hàm và các đối số để thực thi.

Một closure là mã hóa của một hàm kết hợp một biểu thức lambda (có thể mở) với một môi trường để định nghĩa các biến tự do của nó. Nói cách khác, closure "đóng" một term mở.

Mở rộng quy mô với Racket

Racket là một phương ngữ của Scheme "đủ pin" (batteries-included) giúp hoàn thành công việc nhanh chóng. Racket cung cấp cấu trúc match giúp làm sạch mã trình thông dịch.

Dưới đây là phiên bản Racket của trình thông dịch, dài hơn một chút nhưng sạch hơn và dễ hiểu hơn:

(define (eval exp env)
  (match exp
    [(? symbol? x) (env x)]
    [(list 'lambda (list x) body)
     (closure x body env)]
    [(list rator rand)
     (apply (eval rator env)
            (eval rand env))]))

(define (apply clo arg)
  (match clo
    [(closure x body env)
     (eval body (lambda (y)
                  (if (eq? x y)
                      arg
                      (env y))))]))

Phép tính Lambda là một ngôn ngữ nhỏ bé. Tuy nhiên, thiết kế eval/apply của trình thông dịch của nó có thể mở rộng quy mô lên các ngôn ngữ lớn hơn nhiều. Ví dụ, trong khoảng 100 dòng, chúng ta có thể triển khai một trình thông dịch cho một tập con con đáng kể của chính Scheme.

Bạn có thể nhanh chóng kiểm tra các ý tưởng mới cho ngôn ngữ lập trình bằng cách sửa đổi trình thông dịch cuối cùng. Nếu bạn muốn một ngôn ngữ có cú pháp khác, bạn có thể xây dựng một trình phân tích cú pháp (parser) xuất ra các s-expression. Cách tiếp cận này tách biệt rõ ràng giữa thiết kế cú pháp và thiết kế ngữ nghĩa.