4.2 Các biến thể của Scheme — Lazy Evaluation (đánh giá lười)

Giờ đây, khi chúng ta đã có một evaluator (bộ đánh giá) được biểu diễn dưới dạng một chương trình Lisp, ta có thể thử nghiệm các lựa chọn thay thế trong thiết kế ngôn ngữ chỉ đơn giản bằng cách chỉnh sửa evaluator. Thực tế, các ngôn ngữ mới thường được phát minh bằng cách trước tiên viết một evaluator nhúng ngôn ngữ mới vào trong một ngôn ngữ bậc cao đã tồn tại. Ví dụ, nếu chúng ta muốn thảo luận một khía cạnh nào đó của một đề xuất sửa đổi Lisp với một thành viên khác trong cộng đồng Lisp, ta có thể cung cấp một evaluator thể hiện sự thay đổi đó. Người nhận có thể thử nghiệm với evaluator mới và gửi lại phản hồi dưới dạng các chỉnh sửa tiếp theo. Không chỉ nền tảng triển khai bậc cao giúp việc kiểm thử và gỡ lỗi evaluator dễ dàng hơn; ngoài ra, việc nhúng này còn cho phép nhà thiết kế snarf¹ các đặc tính từ ngôn ngữ nền, giống như evaluator Lisp nhúng của chúng ta sử dụng các primitive (nguyên thủy) và control structure (cấu trúc điều khiển) từ Lisp nền. Chỉ về sau (nếu có) nhà thiết kế mới cần bỏ công xây dựng một bản triển khai hoàn chỉnh bằng ngôn ngữ bậc thấp hoặc bằng phần cứng. Trong phần này và phần tiếp theo, chúng ta sẽ khám phá một số biến thể của Scheme mang lại sức mạnh biểu đạt bổ sung đáng kể.

4.2.1 Normal Order và Applicative Order

Trong mục 1.1, khi bắt đầu thảo luận về các mô hình đánh giá, chúng ta đã lưu ý rằng Scheme là một ngôn ngữ applicative-order (“thứ tự áp dụng”), nghĩa là tất cả các đối số truyền vào procedure (thủ tục) của Scheme đều được đánh giá khi procedure được gọi. Ngược lại, các ngôn ngữ normal-order (“thứ tự chuẩn”) sẽ trì hoãn việc đánh giá các đối số của procedure cho đến khi giá trị thực sự của đối số đó được cần đến. Việc trì hoãn đánh giá các đối số của procedure cho đến thời điểm muộn nhất có thể (ví dụ: cho đến khi chúng được yêu cầu bởi một primitive operation) được gọi là lazy evaluation (“đánh giá lười”).² Xem xét procedure sau:

(define (try a b)
  (if (= a 0) 1 b))

Đánh giá (try 0 (/ 1 0)) sẽ tạo ra lỗi trong Scheme. Với lazy evaluation, sẽ không có lỗi. Việc đánh giá biểu thức này sẽ trả về 1, bởi vì đối số (/ 1 0) sẽ không bao giờ được đánh giá.

Một ví dụ khai thác lazy evaluation là định nghĩa của procedure unless:

(define (unless condition 
                usual-value 
                exceptional-value)
  (if condition 
      exceptional-value 
      usual-value))

có thể được sử dụng trong các biểu thức như:

(unless (= b 0)
        (/ a b)
        (begin 
          (display "exception: returning 0")
          0))

Điều này sẽ không hoạt động trong một ngôn ngữ applicative-order vì cả usual value và exceptional value đều sẽ được đánh giá trước khi unless được gọi (so sánh với Bài tập 1.6). Một ưu điểm của lazy evaluation là một số procedure, như unless, có thể thực hiện tính toán hữu ích ngay cả khi việc đánh giá một số đối số của chúng sẽ gây ra lỗi hoặc không bao giờ kết thúc.

Nếu phần thân của một procedure được thực thi trước khi một đối số được đánh giá, ta nói rằng procedure đó là non-strict (“không nghiêm ngặt”) đối với đối số đó. Nếu đối số được đánh giá trước khi phần thân của procedure được thực thi, ta nói rằng procedure đó là strict (“nghiêm ngặt”) đối với đối số đó.³ Trong một ngôn ngữ thuần applicative-order, tất cả các procedure đều strict với từng đối số. Trong một ngôn ngữ thuần normal-order, tất cả các compound procedure (thủ tục hợp) đều non-strict với từng đối số, và các primitive procedure có thể strict hoặc non-strict. Cũng có những ngôn ngữ (xem Bài tập 4.31) cho phép lập trình viên kiểm soát chi tiết mức độ strict của các procedure mà họ định nghĩa.

Một ví dụ nổi bật về procedure có thể hữu ích khi được làm non-strict là cons (hoặc nói chung, hầu như bất kỳ constructor cho cấu trúc dữ liệu nào). Ta có thể thực hiện tính toán hữu ích, kết hợp các phần tử để tạo thành cấu trúc dữ liệu và thao tác trên cấu trúc dữ liệu kết quả, ngay cả khi giá trị của các phần tử chưa được biết. Ví dụ, hoàn toàn hợp lý khi tính độ dài của một danh sách mà không cần biết giá trị của từng phần tử trong danh sách. Chúng ta sẽ khai thác ý tưởng này trong mục 4.2.3 để triển khai streams của Chương 3 dưới dạng các danh sách được tạo thành từ các cặp cons non-strict.

4.2.2 Một Interpreter với Lazy Evaluation

Trong phần này, chúng ta sẽ triển khai một ngôn ngữ normal-order giống hệt Scheme ngoại trừ việc các compound procedure sẽ non-strict với từng đối số. Các primitive procedure vẫn sẽ strict. Việc chỉnh sửa evaluator ở mục 4.1.1 để ngôn ngữ mà nó thông dịch hoạt động theo cách này không khó. Hầu hết các thay đổi cần thiết tập trung quanh việc áp dụng procedure.

Ý tưởng cơ bản là khi áp dụng một procedure, interpreter phải xác định đối số nào sẽ được đánh giá và đối số nào sẽ bị trì hoãn. Các đối số bị trì hoãn sẽ không được đánh giá; thay vào đó, chúng được biến đổi thành các đối tượng gọi là thunks.⁴ Một thunk phải chứa thông tin cần thiết để tạo ra giá trị của đối số khi cần, như thể nó đã được đánh giá tại thời điểm gọi procedure. Do đó, thunk phải chứa biểu thức đối số và environment (môi trường) trong đó việc gọi procedure đang được đánh giá.

Quá trình đánh giá biểu thức trong một thunk được gọi là forcing.⁵ Nói chung, một thunk sẽ chỉ bị force khi giá trị của nó được cần đến: khi nó được truyền vào một primitive procedure sẽ sử dụng giá trị của thunk; khi nó là giá trị của một predicate trong một câu điều kiện; và khi nó là giá trị của một operator sắp được áp dụng như một procedure. Một lựa chọn thiết kế mà chúng ta có là có nên memoize (ghi nhớ) các thunk hay không, giống như ta đã làm với các đối tượng delayed trong mục 3.5.1. Với memoization, lần đầu tiên một thunk bị force, nó sẽ lưu trữ giá trị đã tính toán. Các lần force tiếp theo chỉ đơn giản trả về giá trị đã lưu mà không lặp lại việc tính toán. Chúng ta sẽ làm cho interpreter của mình memoize, vì điều này hiệu quả hơn cho nhiều ứng dụng. Tuy nhiên, ở đây cũng có những cân nhắc phức tạp.⁶

Modifying the evaluator (Chỉnh sửa evaluator)

Sự khác biệt chính giữa lazy evaluator (bộ đánh giá lười) và bộ ở mục 4.1 nằm ở cách xử lý procedure applications (việc áp dụng thủ tục) trong eval và apply.

Mệnh đề application? của eval trở thành:

((application? exp)
 (apply (actual-value (operator exp) env)
        (operands exp)
        env))

Điều này gần như giống hệt mệnh đề application? của eval trong 4.1.1. Tuy nhiên, đối với lazy evaluation, chúng ta gọi apply với các operand expressions (biểu thức toán hạng), thay vì các đối số được tạo ra bằng cách đánh giá chúng. Vì chúng ta sẽ cần environment (môi trường) để tạo thunks nếu các đối số bị trì hoãn, nên ta cũng phải truyền môi trường này vào. Chúng ta vẫn đánh giá operator, vì apply cần procedure thực sự để áp dụng nhằm phân loại theo kiểu (primitive so với compound) và thực hiện áp dụng.

Bất cứ khi nào cần giá trị thực của một biểu thức, ta sử dụng:

(define (actual-value exp env)
  (force-it (eval exp env)))

thay vì chỉ dùng eval, để nếu giá trị của biểu thức là một thunk, nó sẽ được force.

Phiên bản mới của apply cũng gần giống với phiên bản trong 4.1.1. Khác biệt là eval đã truyền vào các operand expressions chưa được đánh giá: Đối với primitive procedures (vốn strict), ta đánh giá tất cả các đối số trước khi áp dụng primitive; đối với compound procedures (vốn non-strict), ta trì hoãn tất cả các đối số trước khi áp dụng procedure.

(define (apply procedure arguments env)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure
          procedure
          (list-of-arg-values 
           arguments 
           env)))  ; changed
        ((compound-procedure? procedure)
         (eval-sequence
          (procedure-body procedure)
          (extend-environment
           (procedure-parameters procedure)
           (list-of-delayed-args 
            arguments 
            env)   ; changed
           (procedure-environment procedure))))
        (else (error "Unknown procedure 
                      type: APPLY" 
                     procedure))))

Các procedure xử lý đối số này giống như list-of-values trong 4.1.1, ngoại trừ việc list-of-delayed-args trì hoãn các đối số thay vì đánh giá chúng, và list-of-arg-values sử dụng actual-value thay vì eval:

(define (list-of-arg-values exps env)
  (if (no-operands? exps)
      '()
      (cons (actual-value 
             (first-operand exps) 
             env)
            (list-of-arg-values 
             (rest-operands exps)
             env))))

(define (list-of-delayed-args exps env)
  (if (no-operands? exps)
      '()
      (cons (delay-it 
             (first-operand exps) 
             env)
            (list-of-delayed-args 
             (rest-operands exps)
             env))))

Một nơi khác cần thay đổi evaluator là trong xử lý if, nơi ta phải dùng actual-value thay vì eval để lấy giá trị của predicate expression trước khi kiểm tra nó đúng hay sai:

(define (eval-if exp env)
  (if (true? (actual-value (if-predicate exp) 
                           env))
      (eval (if-consequent exp) env)
      (eval (if-alternative exp) env)))

Cuối cùng, ta phải thay đổi procedure driver-loop (4.1.4) để dùng actual-value thay vì eval, nhằm đảm bảo nếu một giá trị bị trì hoãn được trả về vòng lặp read-eval-print, nó sẽ được force trước khi in ra. Ta cũng thay đổi prompts để chỉ ra rằng đây là lazy evaluator:

(define input-prompt  ";;; L-Eval input:")
(define output-prompt ";;; L-Eval value:")

(define (driver-loop)
  (prompt-for-input input-prompt)
  (let ((input (read)))
    (let ((output (actual-value 
                   input 
                   the-global-environment)))
      (announce-output output-prompt)
      (user-print output)))
  (driver-loop))

Với những thay đổi này, ta có thể khởi động evaluator và kiểm thử. Việc đánh giá thành công biểu thức try đã thảo luận ở 4.2.1 cho thấy interpreter đang thực hiện lazy evaluation:

(define the-global-environment 
  (setup-environment))

(driver-loop)

;;; L-Eval input:
(define (try a b) (if (= a 0) 1 b))

;;; L-Eval value:
ok

;;; L-Eval input:
(try 0 (/ 1 0))

;;; L-Eval value:
1

Representing thunks (Biểu diễn thunks)

Evaluator của chúng ta phải sắp xếp để tạo thunks khi procedures được áp dụng cho các đối số và force các thunks này sau đó. Một thunk phải đóng gói một biểu thức cùng với environment, để đối số có thể được tạo ra sau này. Để force thunk, ta chỉ cần trích xuất biểu thức và environment từ thunk và đánh giá biểu thức trong environment. Ta dùng actual-value thay vì eval để nếu giá trị của biểu thức bản thân nó là một thunk, ta sẽ force tiếp, và cứ thế cho đến khi gặp một thứ không phải thunk:

(define (force-it obj)
  (if (thunk? obj)
      (actual-value (thunk-exp obj) 
                    (thunk-env obj))
      obj))

Một cách đơn giản để đóng gói một biểu thức với environment là tạo một danh sách chứa biểu thức và environment. Do đó, ta tạo một thunk như sau:

(define (delay-it exp env)
  (list 'thunk exp env))
(define (thunk? obj) (tagged-list? obj 'thunk))
(define (thunk-exp thunk) (cadr thunk))
(define (thunk-env thunk) (caddr thunk))

Thực tế, điều chúng ta muốn cho interpreter không hoàn toàn như vậy, mà là các thunks đã được memoized. Khi một thunk bị force, ta sẽ biến nó thành một evaluated thunk bằng cách thay thế biểu thức đã lưu bằng giá trị của nó và thay đổi thẻ thunk để có thể nhận diện là đã được đánh giá⁷.

(define (evaluated-thunk? obj)
  (tagged-list? obj 'evaluated-thunk))

(define (thunk-value evaluated-thunk) 
  (cadr evaluated-thunk))

(define (force-it obj)
  (cond ((thunk? obj)
         (let ((result
                (actual-value 
                 (thunk-exp obj)
                 (thunk-env obj))))
           (set-car! obj 'evaluated-thunk)
           ;; replace exp with its value:
           (set-car! (cdr obj) result) 
           ;; forget unneeded env:
           (set-cdr! (cdr obj) '()) 
           result))
        ((evaluated-thunk? obj)
         (thunk-value obj))
        (else obj)))

Lưu ý rằng cùng một procedure delay-it hoạt động được cả khi có và không có memoization.

4.2.3 Streams như Lazy Lists

Trong 3.5.1, chúng ta đã chỉ ra cách triển khai streams (luồng) như các delayed lists (danh sách bị trì hoãn). Chúng ta đã giới thiệu các special forms (dạng đặc biệt) delay và cons-stream, cho phép tạo ra một “promise” (lời hứa) để tính toán cdr của một stream, mà không thực hiện lời hứa đó cho đến sau này. Chúng ta có thể sử dụng kỹ thuật tổng quát này — giới thiệu các special forms bất cứ khi nào cần kiểm soát nhiều hơn quá trình đánh giá — nhưng điều này khá bất tiện. Một lý do là special form không phải là một first-class object (đối tượng hạng nhất) như một procedure, nên ta không thể sử dụng nó cùng với các higher-order procedures (thủ tục bậc cao)⁵. Ngoài ra, chúng ta buộc phải tạo streams như một loại đối tượng dữ liệu mới, tương tự nhưng không hoàn toàn giống lists, và điều này yêu cầu phải triển khai lại nhiều phép toán danh sách thông thường (map, append, v.v.) để dùng với streams.

Với lazy evaluation, streams và lists có thể giống hệt nhau, nên không cần special forms hoặc các phép toán riêng biệt cho list và stream. Tất cả những gì cần làm là sắp xếp để cons là non-strict. Một cách để đạt được điều này là mở rộng lazy evaluator để cho phép các primitive non-strict, và triển khai cons như một trong số đó. Một cách dễ hơn là nhớ lại (2.1.3) rằng không có nhu cầu cơ bản nào phải triển khai cons như một primitive. Thay vào đó, ta có thể biểu diễn pairs (cặp) như các procedures⁴:

(define (cons x y) (lambda (m) (m x y)))
(define (car z) (z (lambda (p q) p)))
(define (cdr z) (z (lambda (p q) q)))

Xét theo các phép toán cơ bản này, các định nghĩa chuẩn của phép toán danh sách sẽ hoạt động với cả infinite lists (danh sách vô hạn — streams) cũng như danh sách hữu hạn, và các phép toán stream có thể được triển khai như các phép toán list. Dưới đây là một số ví dụ:

(define (list-ref items n)
  (if (= n 0)
      (car items)
      (list-ref (cdr items) (- n 1))))

(define (map proc items)
  (if (null? items)
      '()
      (cons (proc (car items))
            (map proc (cdr items)))))

(define (scale-list items factor)
  (map (lambda (x) (* x factor))
       items))

(define (add-lists list1 list2)
  (cond ((null? list1) list2)
        ((null? list2) list1)
        (else (cons (+ (car list1) 
                       (car list2))
                    (add-lists
                     (cdr list1) 
                     (cdr list2))))))

(define ones (cons 1 ones))

(define integers 
  (cons 1 (add-lists ones integers)))

;;; L-Eval input:
(list-ref integers 17)

;;; L-Eval value:
18

Lưu ý rằng các lazy lists này thậm chí còn “lười” hơn các streams của Chương 3: car của danh sách, cũng như cdr, đều bị trì hoãn⁶. Thực tế, ngay cả việc truy cập car hoặc cdr của một lazy pair cũng không nhất thiết phải force giá trị của một phần tử danh sách. Giá trị chỉ bị force khi thật sự cần — ví dụ: khi dùng làm đối số của một primitive, hoặc khi in ra làm kết quả.

Các lazy pairs cũng giúp giải quyết vấn đề đã gặp với streams ở 3.5.4, nơi ta thấy rằng việc xây dựng các mô hình stream của hệ thống có vòng lặp có thể yêu cầu rải rác trong chương trình các phép delay tường minh, ngoài những phép được cung cấp bởi cons-stream. Với lazy evaluation, tất cả các đối số của procedures đều bị trì hoãn một cách đồng nhất. Ví dụ, ta có thể triển khai các procedures để tích phân danh sách và giải phương trình vi phân như dự định ban đầu ở 3.5.4:

(define (integral integrand initial-value dt)
  (define int
    (cons initial-value
          (add-lists (scale-list integrand dt) 
                     int)))
  int)

(define (solve f y0 dt)
  (define y (integral dy y0 dt))
  (define dy (map f y))
  y)

;;; L-Eval input:
(list-ref (solve (lambda (x) x) 1 0.001) 1000)

;;; L-Eval value:
2.716924