Cách Viết Trình Thông Dịch Lisp Bằng Python: Bài Học Vỡ Lòng Thanh Lịch 90 Dòng Của Peter Norvig (lis.py) 🧠💡
Peter Norvig, Giám đốc Nghiên cứu nổi tiếng tại Google và là đồng tác giả của cuốn giáo trình kinh điển Trí tuệ Nhân tạo: Phương pháp Hiện đại, đã xuất bản một bài luận mang tính biểu tượng có tựa đề "How to Write a (Lisp) Interpreter (in Python)". Trong đó, ông đã minh họa một sự thật cơ bản của khoa học máy tính: cú pháp và mô hình thực thi của Lisp cực kỳ rõ ràng và mạnh mẽ đến mức một trình thông dịch hoàn chỉnh, hoạt động được có thể được viết chỉ với dưới 90 dòng mã Python tiêu chuẩn.
Bài học masterclass mang tính giáo dục này, thường được gọi là lis.py, triển khai một tập con của Scheme (một biến thể của Lisp). Nó dạy cho các nhà phát triển phần mềm những cơ chế cốt lõi của thiết kế trình biên dịch/thông dịch: Phân tích Từ vựng (Lexical Analysis), Phân tích Cú pháp (Parsing), Môi trường (Environments) và Đánh giá (Evaluation).
---
1. Tại Sao Lisp và Scheme Lại Quan Trọng? 📜🔗
Lisp (được John McCarthy phát minh vào năm 1958) là ngôn ngữ lập trình cấp cao lâu đời thứ hai vẫn còn được sử dụng rộng rãi. Biến thể hiện đại của nó, Scheme, sạch sẽ, tối giản và mang tính giáo dục cao.
Lisp nổi tiếng với cú pháp đồng nhất (uniform syntax): mọi chương trình đều được biểu diễn dưới dạng danh sách các biểu thức được bao quanh bởi dấu ngoặc đơn, ví dụ: (operator arg1 arg2). Cú pháp đồng nhất này đại diện cho mã trực tiếp dưới dạng dữ liệu (một khái niệm được gọi là tự đồng hình - homoiconicity), điều này khiến Lisp cực kỳ dễ phân tích cú pháp (parse) so với các ngôn ngữ như Python, C++ hay JavaScript.
---
2. Các Giai Đoạn Cốt Lõi Của Một Trình Thông Dịch ⚙️🛠️🔍
Để thực thi một chương trình Lisp như (define r 10) (* pi (* r r)), trình thông dịch thực hiện ba bước riêng biệt:
1. Mã hóa (Tokenizing): Chia chuỗi ký tự thô thành một danh sách các từ và dấu ngoặc đơn riêng lẻ. 2. Phân tích cú pháp (Parsing): Chuyển đổi các mã thông báo phẳng đó thành một cấu trúc danh sách phân cấp, lồng nhau, đại diện cho Cây Cú pháp Trừu tượng (Abstract Syntax Tree - AST). 3. Đánh giá (Evaluating): Thực thi đệ quy AST bằng cách sử dụng một bộ lưu trữ trạng thái gọi là Môi trường (Environment).
Giai đoạn A: Phân tích Cú pháp (Phân tích Từ vựng & Tạo AST)
Trong Scheme, việc phân tích cú pháp là điều hiển nhiên vì cấu trúc mã nguồn khớp trực tiếp với cây cú pháp. * Mã hóa (Tokenizing): Sử dụng re.split hoặc thay thế dấu ngoặc đơn bằng khoảng trắng rồi chia tách. * Cây Cú pháp Trừu tượng (AST): Các danh sách Python lồng nhau đại diện cho các danh sách Lisp lồng nhau. Ví dụ, biểu thức Scheme (+ 1 (* 2 3)) được phân tích cú pháp trực tiếp thành danh sách Python lồng nhau: ['+', 1, ['*', 2, 3]].
Giai đoạn B: Lưu trữ Trạng thái (Môi trường - The Environment)
Một Môi trường đơn giản là một từ điển ánh xạ tên biến (Symbol của Lisp) tới các giá trị của chúng. * Môi trường Toàn cục (Global Environment) chứa các hàm tích hợp tiêu chuẩn như phép cộng (+), phép nhân (*), phép trừ (-), phép chia (/), các phép toán danh sách (car, cdr, cons) và các hằng số tiêu chuẩn như pi. * Khi người dùng định nghĩa một biến mới bằng cách sử dụng (define x 5), nó sẽ được thêm vào từ điển này. * Khi người dùng tạo một hàm bằng cách sử dụng lambda, nó sẽ tạo ra một môi trường cục bộ liên kết ngược với môi trường cha của nó (tạo ra phạm vi từ vựng - lexical scope).
Giai đoạn C: Đánh giá Đệ quy (eval)
Hàm đánh giá eval(x, env) là trái tim của trình thông dịch. Nó kiểm tra nút AST x và đánh giá nó dựa trên loại của nó: 1. Tìm kiếm biến: Nếu x là một Symbol (chuỗi), hãy tìm giá trị của nó trong env. 2. Giá trị Hằng số: Nếu x là một Number (số nguyên hoặc số thực), hãy trả về trực tiếp giá trị đó. 3. Các Dạng Đặc biệt (Special Forms): Lisp sử dụng một số từ khóa đặc biệt không tuân theo các quy tắc gọi hàm tiêu chuẩn: * (quote exp): Trả về biểu thức thô exp mà không đánh giá nó. * (if test conseq alt): Đánh giá test. Nếu đúng, đánh giá và trả về conseq; ngược lại, đánh giá và trả về alt. * (define var exp): Đánh giá exp và gán kết quả cho var trong môi trường. * (set! var exp): Cập nhật giá trị của biến var hiện có bằng giá trị của exp. * (lambda parms body): Trả về một đối tượng Procedure có thể gọi được, gói gọn các tham số, phần thân và môi trường hiện tại. 4. Gọi hàm/Thủ tục (Function/Procedure Call): Đối với bất kỳ danh sách nào khác (proc arg1 arg2...), đánh giá đệ quy proc và tất cả args, sau đó gọi thủ tục đã được đánh giá với các đối số đã được đánh giá.
---
3. Mã Nguồn Python 90 Dòng 🐍
Dưới đây là phiên bản hiện đại, đầy đủ của trình thông dịch lis.py của Peter Norvig, được viết bằng Python 3, minh họa cách các kiểu dữ liệu tự nhiên của Python ánh xạ liền mạch với ngữ nghĩa của Scheme:
```python import math import operator as op
Define basic types using Python's native data structures
Symbol = str # A Scheme Symbol is represented as a Python str List = list # A Scheme List is represented as a Python list Number = (int, float) # A Scheme Number is represented as a Python int or float
class Env(dict): "An environment: a dict of {'var': val} with an optional outer parent Env." def init(self, parms=(), args=(), outer=None): self.update(zip(parms, args)) self.outer = outer def find(self, var): "Find the innermost Env where var appears." return self if (var in self) else self.outer.find(var)
def standard_env() -> Env: "An environment with standard Scheme procedures." env = Env() env.update(vars(math)) # Import sin, cos, sqrt, pi, etc. env.update({ '+': op.add, '-': op.sub, '*': op.mul, '/': op.truediv, '>': op.gt, '<': op.lt, '>=': op.ge, '<=': op.le, '=': op.eq, 'append': op.add, 'apply': lambda proc, args: proc(*args), 'begin': lambda *x: x[-1], 'car': lambda x: x[0], 'cdr': lambda x: x[1:], 'cons': lambda x, y: [x] + y, 'eq?': op.is_, 'expt': pow, 'equal?': op.eq, 'length': len, 'list': lambda *x: list(x), 'list?': lambda x: isinstance(x, list), 'map': map, 'max': max, 'min': min, 'not': op.not_, 'null?': lambda x: x == [], 'number?': lambda x: isinstance(x, Number), 'procedure?': callable, 'round': round, 'symbol?': lambda x: isinstance(x, Symbol), }) return env
global_env = standard_env()
def tokenize(chars: str) -> list: "Convert a string of characters into a list of tokens." return chars.replace('(', ' ( ').replace(')', ' ) ').split()
def parse(program: str) -> list: "Read a Scheme expression from a string." return read_from_tokens(tokenize(program))
def read_from_tokens(tokens: list): "Read an expression from a sequence of tokens." if len(tokens) == 0: raise SyntaxError('unexpected EOF while reading') token = tokens.pop(0) if '(' == token: L = [] while tokens[0] != ')': L.append(read_from_tokens(tokens)) tokens.pop(0) # pop off ')' return L elif ')' == token: raise SyntaxError('unexpected )') else: return atom(token)
def atom(token: str): "Numbers become numbers; every other token is a symbol." try: return int(token) except ValueError: try: return float(token) except ValueError: return Symbol(token)
class Procedure(object): "A user-defined Scheme procedure." def init(self, parms, body, env): self.parms, self.body, self.env = parms, body, env def call(self, *args): # Lexical scope evaluation in a new Environment child return eval(self.body, Env(self.parms, args, self.env))
def eval(x, env=global_env): "Evaluate an expression in an environment." if isinstance(x, Symbol): # Variable reference return env.find(x)[x] elif not isinstance(x, List): # Constant literal return x op_symbol = x[0] if op_symbol == 'quote': # quotation: (quote exp) (, exp) = x return exp elif op_symbol == 'if': # conditional: (if test conseq alt) (, test, conseq, alt) = x exp = conseq if eval(test, env) else alt return eval(exp, env) elif op_symbol == 'define': # definition: (define var exp) (, var, exp) = x env[var] = eval(exp, env) elif op_symbol == 'set!': # assignment: (set! var exp) (, var, exp) = x env.find(var)[var] = eval(exp, env) elif op_symbol == 'lambda': # procedure: (lambda (parms...) body) (_, parms, body) = x return Procedure(parms, body, env) else: # procedure call: (proc args...) proc = eval(x[0], env) args = [eval(arg, env) for arg in x[1:]] return proc(*args)
def repl(prompt='lis.py> '): "A prompt-read-eval-print loop." print("Welcome to lis.py Scheme Interpreter!") while True: try: line = input(prompt) if not line.strip(): continue val = eval(parse(line)) if val is not None: print(schemestr(val)) except Exception as e: print(f"Error: {e}")
def schemestr(exp) -> str: "Convert a Python object back into a Scheme-readable string." if isinstance(exp, List): return '(' + ' '.join(map(schemestr, exp)) + ')' else: return str(exp) ```
---
4. Kiểm Tra Trình Thông Dịch ✅🧪
Sau khi chạy, các nhà phát triển có thể mở REPL tương tác và nhập mã Scheme tiêu chuẩn:
```lisp lis.py> (define area (lambda (r) (* pi (* r r)))) lis.py> (area 10) 314.1592653589793
lis.py> (define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1)))))) lis.py> (fact 5) 120
lis.py> (define range (lambda (start end) (if (= start end) (quote ()) (cons start (range (+ start 1) end))))) lis.py> (range 1 10) (1 2 3 4 5 6 7 8 9) ```
---
5. Tại Sao lis.py Là Một Bài Học Khoa Học Máy Tính Tuyệt Vời 🤯🏆
Dự án lis.py của Peter Norvig không chỉ là một dự án nhỏ; nó đại diện cho một triết lý kỹ thuật phần mềm sâu sắc và thanh lịch: 1. Khoảng Cách Ngữ Nghĩa Cực Thấp (Extremely Low Semantic Gap): Từ điển tự nhiên, danh sách lồng nhau và liên kết kiểu động của Python gần như hoàn toàn phù hợp với các yêu cầu của Lisp. Python đóng vai trò như một siêu ngôn ngữ hoàn hảo cho Lisp. 2. Thực Thi Dựa Trên Ngăn Xếp (Stack-Based Execution): Bằng cách dựa vào ngăn xếp thực thi hàm tự nhiên của Python (thông qua các cuộc gọi đệ quy tới eval), lis.py bỏ qua nhu cầu viết quản lý ngăn xếp, hướng dẫn hoặc vòng lặp mã byte tùy chỉnh. 3. Bao Đóng Từ Vựng Miễn Phí (Lexical Closures for Free): Hệ thống con trỏ Env đơn giản đảm bảo thực thi phạm vi từ vựng tiêu chuẩn (nơi các hàm giữ quyền truy cập vào các phạm vi định nghĩa của chúng), một tính năng mà trong lịch sử phải mất nhiều năm nghiên cứu trình biên dịch mới hoàn thiện được.
Đối với bất kỳ kỹ sư phần mềm nào muốn vượt lên trên việc lập trình cấp cao tiêu chuẩn, việc viết một trình thông dịch Lisp vẫn là một cột mốc cuối cùng. lis.py của Peter Norvig chứng minh rằng bạn không cần 10.000 dòng C++ phức tạp hay những cuốn sách về trình biên dịch đồ sộ để hiểu được sự kỳ diệu của các ngôn ngữ lập trình – bạn chỉ cần 90 dòng Python sạch sẽ, có chủ đích.