1.3 Hình thành các trừu tượng với higher-order procedures (thủ tục bậc cao)

Chúng ta đã thấy rằng procedures (thủ tục) thực chất là các trừu tượng mô tả những phép toán phức hợp trên các con số, độc lập với các con số cụ thể. Ví dụ, khi chúng ta

(define (cube x) (* x x x))

chúng ta không nói về lập phương của một số cụ thể, mà là về một phương pháp để lấy lập phương của bất kỳ số nào. Tất nhiên, chúng ta vẫn có thể làm việc mà không bao giờ định nghĩa thủ tục này, bằng cách luôn viết các biểu thức như

(* 3 3 3)
(* x x x)
(* y y y)

và không bao giờ nhắc đến cube một cách tường minh. Điều này sẽ đặt chúng ta vào thế bất lợi nghiêm trọng, buộc chúng ta luôn phải làm việc ở mức các phép toán cụ thể vốn là primitives (nguyên thủy) trong ngôn ngữ (trong trường hợp này là phép nhân), thay vì ở mức các phép toán cấp cao hơn. Chương trình của chúng ta sẽ có thể tính lập phương, nhưng ngôn ngữ của chúng ta sẽ thiếu khả năng diễn đạt khái niệm “lập phương hóa”. Một trong những điều chúng ta nên yêu cầu từ một ngôn ngữ lập trình mạnh mẽ là khả năng xây dựng các trừu tượng bằng cách gán tên cho các mẫu chung, và sau đó làm việc trực tiếp với các trừu tượng đó. Procedures cung cấp khả năng này. Đây là lý do tại sao tất cả các ngôn ngữ lập trình, trừ những ngôn ngữ nguyên thủy nhất, đều bao gồm cơ chế định nghĩa procedures.

Tuy nhiên, ngay cả trong xử lý số học, chúng ta cũng sẽ bị giới hạn nghiêm trọng trong khả năng tạo ra các trừu tượng nếu chúng ta bị ràng buộc vào các procedures mà tham số của chúng phải là số. Thường thì cùng một mẫu lập trình sẽ được sử dụng với nhiều procedures khác nhau. Để diễn đạt những mẫu như vậy thành các khái niệm, chúng ta sẽ cần xây dựng các procedures có thể nhận procedures làm đối số hoặc trả về procedures như giá trị. Các procedures thao tác trên procedures được gọi là higher-order procedures. Phần này sẽ cho thấy cách higher-order procedures có thể đóng vai trò như những cơ chế trừu tượng mạnh mẽ, làm tăng đáng kể sức biểu đạt của ngôn ngữ.

1.3.1 Procedures như đối số

Xét ba procedures sau. Thủ tục đầu tiên tính tổng các số nguyên từ a đến b:

(define (sum-integers a b)
  (if (> a b) 
      0 
      (+ a (sum-integers (+ a 1) b))))

Thủ tục thứ hai tính tổng lập phương của các số nguyên trong khoảng đã cho:

(define (sum-cubes a b)
  (if (> a b) 
      0 
      (+ (cube a) 
         (sum-cubes (+ a 1) b))))

Thủ tục thứ ba tính tổng của một dãy các số hạng trong chuỗi

$$\frac{1}{1 \cdot 3} + \frac{1}{5 \cdot 7} + \frac{1}{9 \cdot 11} + {\ldots,}$$

mà hội tụ về $\pi/8$ (rất chậm):¹

(define (pi-sum a b)
  (if (> a b)
      0
      (+ (/ 1.0 (* a (+ a 2))) 
         (pi-sum (+ a 4) b))))

Ba procedures này rõ ràng chia sẻ một mẫu cơ bản chung. Chúng hầu như giống hệt nhau, chỉ khác ở tên của procedure, hàm của a được dùng để tính số hạng cần cộng, và hàm cung cấp giá trị tiếp theo của a. Chúng ta có thể tạo ra từng procedure bằng cách điền vào các vị trí trống trong cùng một khuôn mẫu:

(define (⟨name⟩ a b)
  (if (> a b)
      0
      (+ (⟨term⟩ a) 
         (⟨name⟩ (⟨next⟩ a) b))))

Sự tồn tại của một mẫu chung như vậy là bằng chứng mạnh mẽ cho thấy có một trừu tượng hữu ích đang chờ được đưa ra ánh sáng. Thật vậy, các nhà toán học từ lâu đã xác định trừu tượng summation of a series (tổng của một chuỗi) và phát minh ra “sigma notation” (ký hiệu sigma), ví dụ như

$${\sum\limits_{n = a}^{b}f(n)}, = ,{f(a)} + \cdots + {f(b),}$$

để diễn đạt khái niệm này. Sức mạnh của ký hiệu sigma là nó cho phép các nhà toán học làm việc với khái niệm tổng quát của phép cộng dồn, thay vì chỉ với các tổng cụ thể — ví dụ, để xây dựng các kết quả tổng quát về tổng mà không phụ thuộc vào chuỗi cụ thể đang được cộng.

Tương tự, với tư cách là những người thiết kế chương trình, chúng ta muốn ngôn ngữ của mình đủ mạnh để có thể viết một procedure diễn đạt khái niệm tổng quát của phép cộng dồn, thay vì chỉ viết các procedures tính những tổng cụ thể. Chúng ta có thể dễ dàng làm điều này trong ngôn ngữ thủ tục của mình bằng cách lấy khuôn mẫu chung ở trên và biến các “vị trí trống” thành các tham số hình thức:

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

Hãy chú ý rằng sum nhận các đối số là cận dưới a và cận trên b cùng với các procedures (thủ tục) term và next. Chúng ta có thể sử dụng sum giống như bất kỳ procedure nào khác. Ví dụ, chúng ta có thể dùng nó (cùng với một procedure inc tăng đối số của nó lên 1) để định nghĩa sum-cubes:

(define (inc n) (+ n 1))

(define (sum-cubes a b)
  (sum cube a inc b))

Sử dụng cách này, chúng ta có thể tính tổng lập phương của các số nguyên từ 1 đến 10:

(sum-cubes 1 10)
3025

Với sự trợ giúp của một identity procedure để tính số hạng, chúng ta có thể định nghĩa sum-integers dựa trên sum:

(define (identity x) x)

(define (sum-integers a b)
  (sum identity a inc b))

Sau đó, chúng ta có thể cộng các số nguyên từ 1 đến 10:

(sum-integers 1 10)
55

Chúng ta cũng có thể định nghĩa pi-sum theo cùng cách này:²

(define (pi-sum a b)
  (define (pi-term x)
    (/ 1.0 (* x (+ x 2))))
  (define (pi-next x)
    (+ x 4))
  (sum pi-term a pi-next b))

Sử dụng các procedures này, chúng ta có thể tính gần đúng giá trị của $\pi$:

(* 8 (pi-sum 1 1000))
3.139592655589783

Khi đã có sum, chúng ta có thể dùng nó như một khối xây dựng để hình thành các khái niệm khác. Chẳng hạn, tích phân xác định của một hàm $f$ trong khoảng từ $a$ đến $b$ có thể được xấp xỉ bằng số học theo công thức

$${\int_{a}^{b}\mspace{-5mu} f}; = ;\left\lbrack ; f\left( a + \frac{dx}{2} \right) \right., + ,{f\left( a + dx + \frac{dx}{2} \right)}, + ,{\left. f\left( a + 2dx + \frac{dx}{2} \right), + ,\ldots; \right\rbrack dx}$$

với giá trị $dx$ nhỏ. Chúng ta có thể diễn đạt trực tiếp điều này thành một procedure:

(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b) 
     dx))

(integral cube 0 1 0.01)
.24998750000000042

(integral cube 0 1 0.001)
.249999875000001

(Giá trị chính xác của tích phân của cube từ 0 đến 1 là 1/4.)

1.3.2 Xây dựng Procedures bằng Lambda

Khi sử dụng sum như trong 1.3.1, việc phải định nghĩa các procedures tầm thường như pi-term và pi-next chỉ để dùng chúng làm đối số cho higher-order procedure thật sự rất bất tiện. Thay vì định nghĩa pi-next và pi-term, sẽ thuận tiện hơn nếu có cách chỉ định trực tiếp “procedure trả về đầu vào của nó cộng thêm 4” và “procedure trả về nghịch đảo của đầu vào nhân với đầu vào cộng 2”. Chúng ta có thể làm điều này bằng cách giới thiệu special form (dạng đặc biệt) lambda, vốn tạo ra procedures. Sử dụng lambda, chúng ta có thể mô tả điều mình muốn như sau:

(lambda (x) (+ x 4))

và

(lambda (x) (/ 1.0 (* x (+ x 2))))

Khi đó, procedure pi-sum của chúng ta có thể được viết mà không cần định nghĩa bất kỳ procedure phụ nào:

(define (pi-sum a b)
  (sum (lambda (x) (/ 1.0 (* x (+ x 2))))
       a
       (lambda (x) (+ x 4))
       b))

Một lần nữa, sử dụng lambda, chúng ta có thể viết procedure integral mà không cần định nghĩa procedure phụ add-dx:

(define (integral f a b dx)
  (* (sum f (+ a (/ dx 2.0))
            (lambda (x) (+ x dx))
            b)
     dx))

Nói chung, lambda được dùng để tạo procedures giống như define, ngoại trừ việc không chỉ định tên cho procedure:

(lambda (⟨formal-parameters⟩) ⟨body⟩)

Procedure thu được cũng giống như bất kỳ procedure nào được tạo bằng define. Điểm khác biệt duy nhất là nó chưa được gán với bất kỳ tên nào trong môi trường. Thực tế,

(define (plus4 x) (+ x 4))

tương đương với

(define plus4 (lambda (x) (+ x 4)))

Chúng ta có thể đọc một biểu thức lambda như sau:

(lambda                     (x)     (+   x     4))
    |                        |       |   |     |
the procedure of an argument x that adds x and 4

Giống như bất kỳ biểu thức nào có giá trị là một procedure, một biểu thức lambda có thể được dùng làm toán tử trong một tổ hợp như

((lambda (x y z) (+ x y (square z))) 1 2 3)
12

hoặc, nói chung hơn, trong bất kỳ ngữ cảnh nào mà thông thường chúng ta sẽ dùng tên của một procedure.³

Sử dụng let để tạo local variables (biến cục bộ)

Một cách sử dụng khác của lambda là để tạo local variables. Chúng ta thường cần các local variables trong procedures (thủ tục) ngoài những biến đã được ràng buộc như các tham số hình thức. Ví dụ, giả sử chúng ta muốn tính hàm

$${f(x,y)}, = ,{x(1 + xy)^{2}} + {y(1 - y)} + {(1 + xy)(1 - y),}$$

mà chúng ta cũng có thể biểu diễn như

$$\begin{array}{lll} a & = & {1 + xy,} \ {\phantom{(x,y)}b} & = & {1 - y,} \ {f(x,y)} & = & {{xa^{2}} + {yb} + {ab.}} \ \end{array}$$

Khi viết một procedure để tính $f$, chúng ta muốn bao gồm như local variables không chỉ $x$ và $y$ mà còn cả tên của các giá trị trung gian như $a$ và $b$. Một cách để thực hiện điều này là sử dụng một auxiliary procedure (thủ tục phụ) để ràng buộc các local variables:

(define (f x y)
  (define (f-helper a b)
    (+ (* x (square a))
       (* y b)
       (* a b)))
  (f-helper (+ 1 (* x y)) 
            (- 1 y)))

Tất nhiên, chúng ta có thể sử dụng một biểu thức lambda để chỉ định một procedure ẩn danh nhằm ràng buộc các local variables. Phần thân của f khi đó trở thành một lời gọi duy nhất tới procedure đó:

(define (f x y)
  ((lambda (a b)
     (+ (* x (square a)) 
        (* y b) 
        (* a b)))
   (+ 1 (* x y))
   (- 1 y)))

Cấu trúc này hữu ích đến mức có một special form (dạng đặc biệt) gọi là let để giúp việc sử dụng thuận tiện hơn. Sử dụng let, procedure f có thể được viết như sau:

(define (f x y)
  (let ((a (+ 1 (* x y)))
        (b (- 1 y)))
    (+ (* x (square a))
       (* y b)
       (* a b))))

Dạng tổng quát của một biểu thức let là:

(let ((⟨var₁⟩ ⟨exp₁⟩)
      (⟨var₂⟩ ⟨exp₂⟩)
      …
      (⟨varₙ⟩ ⟨expₙ⟩))
  ⟨body⟩)

có thể được hiểu như sau:

let ⟨var₁⟩ have the value ⟨exp₁⟩ and
    ⟨var₂⟩ have the value ⟨exp₂⟩ and
    …
    ⟨varₙ⟩ have the value ⟨expₙ⟩
  in ⟨body⟩

Phần đầu tiên của biểu thức let là một danh sách các cặp tên-biểu thức. Khi let được đánh giá, mỗi tên sẽ được gán với giá trị của biểu thức tương ứng. Phần thân của let được đánh giá với các tên này được ràng buộc như local variables. Cách điều này diễn ra là biểu thức let được diễn giải như một cú pháp thay thế cho:

((lambda (⟨var₁⟩ … ⟨varₙ⟩)
   ⟨body⟩)
 ⟨exp₁⟩
 …
 ⟨expₙ⟩)

Không cần cơ chế mới trong interpreter để cung cấp local variables. Một biểu thức let đơn giản chỉ là syntactic sugar (cú pháp rút gọn) cho việc áp dụng lambda bên dưới.

Từ sự tương đương này, chúng ta thấy rằng phạm vi (scope) của một biến được chỉ định bởi một biểu thức let là phần thân của let. Điều này ngụ ý rằng:

• Let cho phép ràng buộc biến một cách cục bộ nhất có thể tại nơi chúng được sử dụng. Ví dụ, nếu giá trị của x là 5, giá trị của biểu thức

  (+ (let ((x 3))
       (+ x (* x 10)))
     x)
  

  là 38. Ở đây, x trong phần thân của let là 3, nên giá trị của biểu thức let là 33. Mặt khác, x là đối số thứ hai của phép cộng ngoài cùng vẫn là 5.

• Giá trị của các biến được tính toán bên ngoài let. Điều này quan trọng khi các biểu thức cung cấp giá trị cho local variables phụ thuộc vào các biến có cùng tên với chính local variables đó. Ví dụ, nếu giá trị của x là 2, biểu thức

  (let ((x 3)
        (y (+ x 2)))
    (* x y))
  

  sẽ có giá trị 12 vì bên trong phần thân của let, x sẽ là 3 và y sẽ là 4 (là giá trị của x bên ngoài cộng 2).

Đôi khi chúng ta có thể sử dụng internal definitions (định nghĩa bên trong) để đạt cùng hiệu quả như với let. Ví dụ, chúng ta có thể định nghĩa procedure f ở trên như sau:

(define (f x y)
  (define a 
    (+ 1 (* x y)))
  (define b (- 1 y))
  (+ (* x (square a))
     (* y b)
     (* a b)))

Tuy nhiên, chúng ta thích sử dụng let trong những tình huống như thế này và chỉ dùng define bên trong cho các internal procedures.⁴

1.3.3 Procedures như các phương pháp tổng quát

Chúng ta đã giới thiệu compound procedures (thủ tục phức hợp) trong 1.1.4 như một cơ chế để trừu tượng hóa các mẫu của các phép toán số học, nhằm làm cho chúng độc lập với các con số cụ thể liên quan. Với higher-order procedures, chẳng hạn như procedure integral trong 1.3.1, chúng ta bắt đầu thấy một dạng trừu tượng mạnh mẽ hơn: các procedures được sử dụng để diễn đạt các phương pháp tính toán tổng quát, độc lập với các hàm cụ thể liên quan. Trong phần này, chúng ta sẽ thảo luận hai ví dụ phức tạp hơn — các phương pháp tổng quát để tìm zeros (nghiệm) và fixed points (điểm bất động) của hàm — và chỉ ra cách các phương pháp này có thể được diễn đạt trực tiếp dưới dạng procedures.

Tìm nghiệm của phương trình bằng half-interval method (phương pháp nửa khoảng)

Half-interval method là một kỹ thuật đơn giản nhưng mạnh mẽ để tìm nghiệm của phương trình $f(x) = 0$, trong đó $f$ là một hàm liên tục. Ý tưởng là, nếu chúng ta có các điểm $a$ và $b$ sao cho $f(a) < 0 < f(b)$, thì $f$ phải có ít nhất một nghiệm nằm giữa $a$ và $b$. Để xác định một nghiệm, đặt $x$ là trung bình cộng của $a$ và $b$, và tính $f(x)$. Nếu $f(x) > 0$, thì $f$ phải có một nghiệm giữa $a$ và $x$. Nếu $f(x) < 0$, thì $f$ phải có một nghiệm giữa $x$ và $b$. Tiếp tục theo cách này, chúng ta có thể xác định các khoảng ngày càng nhỏ hơn mà trên đó $f$ chắc chắn có một nghiệm. Khi đạt đến một điểm mà khoảng này đủ nhỏ, quá trình dừng lại. Vì khoảng không chắc chắn được giảm một nửa ở mỗi bước, số bước cần thiết tăng theo $\Theta(\log(L,/, T))$, trong đó $L$ là độ dài của khoảng ban đầu và $T$ là sai số cho phép (tức là kích thước của khoảng mà ta coi là “đủ nhỏ”). Dưới đây là một procedure (thủ tục) hiện thực hóa chiến lược này:

(define (search f neg-point pos-point)
  (let ((midpoint 
         (average neg-point pos-point)))
    (if (close-enough? neg-point pos-point)
        midpoint
        (let ((test-value (f midpoint)))
          (cond 
           ((positive? test-value)
            (search f neg-point midpoint))
           ((negative? test-value)
            (search f midpoint pos-point))
           (else midpoint))))))

Chúng ta giả định rằng ban đầu được cho hàm $f$ cùng với các điểm mà giá trị của nó là âm và dương. Trước tiên, chúng ta tính trung điểm của hai điểm đã cho. Tiếp theo, kiểm tra xem khoảng đã cho có đủ nhỏ hay chưa, nếu có thì trả về trung điểm như kết quả. Nếu không, chúng ta tính giá trị kiểm tra là giá trị của $f$ tại trung điểm. Nếu giá trị kiểm tra là dương, thì tiếp tục quá trình với khoảng mới từ điểm âm ban đầu đến trung điểm. Nếu giá trị kiểm tra là âm, tiếp tục với khoảng từ trung điểm đến điểm dương. Cuối cùng, có khả năng giá trị kiểm tra bằng 0, khi đó trung điểm chính là nghiệm cần tìm.

Để kiểm tra xem các điểm đầu mút có “đủ gần” nhau hay không, chúng ta có thể dùng một procedure tương tự như trong 1.1.7 để tính căn bậc hai:⁵

(define (close-enough? x y) 
  (< (abs (- x y)) 0.001))

Search khá bất tiện khi dùng trực tiếp, vì chúng ta có thể vô tình đưa vào các điểm mà giá trị của $f$ không có dấu như yêu cầu, dẫn đến kết quả sai. Thay vào đó, chúng ta sẽ dùng search thông qua procedure sau, procedure này kiểm tra xem đầu mút nào có giá trị âm và đầu mút nào có giá trị dương, rồi gọi search tương ứng. Nếu hàm có cùng dấu tại hai điểm đã cho, half-interval method không thể áp dụng, khi đó procedure sẽ báo lỗi.⁶

(define (half-interval-method f a b)
  (let ((a-value (f a))
        (b-value (f b)))
    (cond ((and (negative? a-value) 
                (positive? b-value))
           (search f a b))
          ((and (negative? b-value) 
                (positive? a-value))
           (search f b a))
          (else
           (error "Values are not of 
                   opposite sign" a b)))))

Ví dụ sau sử dụng half-interval method để xấp xỉ $\pi$ như nghiệm giữa 2 và 4 của $\sin x = 0$:

(half-interval-method sin 2.0 4.0)
3.14111328125

Một ví dụ khác, dùng half-interval method để tìm nghiệm của phương trình $x^{3} - 2x - 3 = 0$ giữa 1 và 2:

(half-interval-method 
 (lambda (x) (- (* x x x) (* 2 x) 3))
 1.0
 2.0)
1.89306640625

Tìm fixed points (điểm bất động) của hàm

Một số $x$ được gọi là fixed point của một hàm $f$ nếu $x$ thỏa mãn phương trình $f(x) = x$. Với một số hàm $f$, chúng ta có thể tìm fixed point bằng cách bắt đầu với một giá trị đoán ban đầu và áp dụng $f$ lặp đi lặp lại,

$${f(x),}\quad{f(f(x)),}\quad{f(f(f(x))),}\quad{\ldots,}$$

cho đến khi giá trị không thay đổi nhiều. Dựa trên ý tưởng này, chúng ta có thể xây dựng procedure fixed-point nhận đầu vào là một hàm và một giá trị đoán ban đầu, và trả về một xấp xỉ của fixed point của hàm. Chúng ta áp dụng hàm lặp lại cho đến khi tìm được hai giá trị liên tiếp có hiệu nhỏ hơn một sai số cho phép:

(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) 
       tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

Ví dụ, chúng ta có thể dùng phương pháp này để xấp xỉ fixed point của hàm cosine, bắt đầu với 1 làm giá trị xấp xỉ ban đầu:⁷

(fixed-point cos 1.0)
.7390822985224023

Tương tự, chúng ta có thể tìm nghiệm của phương trình $y = \sin y + \cos y$:

(fixed-point (lambda (y) (+ (sin y) (cos y)))
             1.0)
1.2587315962971173

Quá trình tìm fixed point gợi nhớ đến quá trình tìm căn bậc hai trong 1.1.7. Cả hai đều dựa trên ý tưởng liên tục cải thiện giá trị đoán cho đến khi kết quả thỏa mãn một tiêu chí nào đó. Thực tế, chúng ta có thể dễ dàng diễn đạt việc tính căn bậc hai như một tìm kiếm fixed point. Tính căn bậc hai của một số $x$ yêu cầu tìm $y$ sao cho $y^{2} = x$. Viết lại phương trình này dưới dạng tương đương $y = x/y$, ta nhận ra rằng chúng ta đang tìm fixed point của hàm⁸ $y\mapsto x/y$, và do đó có thể thử tính căn bậc hai như sau:

(define (sqrt x)
  (fixed-point (lambda (y) (/ x y))
               1.0))

Đáng tiếc, tìm kiếm fixed point này không hội tụ. Xét một giá trị đoán ban đầu $y_{1}$. Giá trị đoán tiếp theo là $y_{2} = x/y_{1}$ và giá trị tiếp theo nữa là $y_{3} = {x/y_{2}} = {x/(x/y_{1})} = y_{1}$. Điều này dẫn đến một vòng lặp vô hạn trong đó hai giá trị đoán $y_{1}$ và $y_{2}$ lặp lại liên tục, dao động quanh đáp án.

Một cách để kiểm soát dao động như vậy là ngăn các giá trị đoán thay đổi quá nhiều. Vì đáp án luôn nằm giữa giá trị đoán $y$ và $x/y$, chúng ta có thể tạo một giá trị đoán mới không cách xa $y$ như $x/y$ bằng cách lấy trung bình cộng của $y$ và $x/y$, sao cho giá trị đoán tiếp theo sau $y$ là $\frac{1}{2}(y + x/y)$ thay vì $x/y$. Quá trình tạo ra một dãy giá trị đoán như vậy chính là quá trình tìm fixed point của $y\mapsto{\frac{1}{2}(y + x/y)}$:

(define (sqrt x)
  (fixed-point 
   (lambda (y) (average y (/ x y)))
   1.0))

(Lưu ý rằng $y = {\frac{1}{2}(y + x/y)}$ là một phép biến đổi đơn giản của phương trình $y = x/y$; để suy ra nó, cộng $y$ vào cả hai vế của phương trình và chia cho 2.)

(Note that $y = {\frac{1}{2}(y + x/y)}$ is a simple transformation of the equation $y = x/y;$ to derive it, add $y$ to both sides of the equation and divide by 2.)

(TODO)

With this modification, the square-root procedure works. In fact, if we unravel the definitions, we can see that the sequence of approximations to the square root generated here is precisely the same as the one generated by our original square-root procedure of 1.1.7. This approach of averaging successive approximations to a solution, a technique that we call average damping, often aids the convergence of fixed-point searches.

1.3.4 Procedures như các giá trị trả về

Các ví dụ ở trên cho thấy khả năng truyền procedures (thủ tục) như đối số đã làm tăng đáng kể sức biểu đạt của ngôn ngữ lập trình. Chúng ta còn có thể đạt được sức biểu đạt mạnh mẽ hơn nữa bằng cách tạo ra các procedures mà giá trị trả về của chúng lại chính là các procedures.

Chúng ta có thể minh họa ý tưởng này bằng cách xem lại ví dụ fixed-point (điểm bất động) được mô tả ở cuối mục 1.3.3. Chúng ta đã xây dựng một phiên bản mới của procedure tính căn bậc hai như một tìm kiếm fixed-point, bắt đầu từ nhận xét rằng $\sqrt{x}$ là một fixed-point của hàm $y\mapsto x/y$. Sau đó, chúng ta dùng average damping (làm trơn trung bình) để làm cho các giá trị xấp xỉ hội tụ. Average damping tự nó là một kỹ thuật tổng quát hữu ích. Cụ thể, với một hàm $f$, ta xét hàm có giá trị tại $x$ bằng trung bình cộng của $x$ và $f(x)$.

Chúng ta có thể diễn đạt ý tưởng average damping bằng procedure sau:

(define (average-damp f)
  (lambda (x) 
    (average x (f x))))

Average-damp là một procedure nhận đối số là một procedure f và trả về một procedure (được tạo bởi lambda) mà khi áp dụng cho một số x, sẽ trả về trung bình cộng của x và (f x). Ví dụ, áp dụng average-damp cho procedure square sẽ tạo ra một procedure có giá trị tại một số $x$ là trung bình cộng của $x$ và $x^{2}$. Áp dụng procedure này cho 10 sẽ trả về trung bình cộng của 10 và 100, tức là 55:⁹

((average-damp square) 10)
55

Sử dụng average-damp, chúng ta có thể viết lại procedure tính căn bậc hai như sau:

(define (sqrt x)
  (fixed-point 
   (average-damp 
    (lambda (y) (/ x y)))
   1.0))

Hãy chú ý cách viết này làm rõ ràng ba ý tưởng trong phương pháp: tìm kiếm fixed-point, average damping, và hàm $y\mapsto x/y$. Thật bổ ích khi so sánh cách viết này của phương pháp tính căn bậc hai với phiên bản gốc trong 1.1.7. Hãy nhớ rằng các procedures này diễn đạt cùng một quá trình, và nhận thấy ý tưởng trở nên rõ ràng hơn nhiều khi chúng ta diễn đạt quá trình bằng các trừu tượng này. Nói chung, có nhiều cách để xây dựng một quá trình thành một procedure. Những lập trình viên giàu kinh nghiệm biết cách chọn các cách viết thủ tục đặc biệt sáng sủa, trong đó các thành phần hữu ích của quá trình được tách ra thành các thực thể riêng biệt có thể tái sử dụng trong các ứng dụng khác. Một ví dụ đơn giản về tái sử dụng: căn bậc ba của $x$ là một fixed-point của hàm $y\mapsto x/y^{2}$, vì vậy chúng ta có thể ngay lập tức tổng quát hóa procedure tính căn bậc hai thành một procedure trích xuất căn bậc ba:¹⁰

(define (cube-root x)
  (fixed-point 
   (average-damp 
    (lambda (y) 
      (/ x (square y))))
   1.0))

Newton’s method

Khi lần đầu giới thiệu procedure tính căn bậc hai trong 1.1.7, chúng ta đã đề cập rằng đây là một trường hợp đặc biệt của Newton’s method (phương pháp Newton). Nếu $x\mapsto g(x)$ là một hàm khả vi, thì nghiệm của phương trình $g(x) = 0$ là một fixed-point của hàm $x\mapsto f(x)$, trong đó

$${f(x)}, = , x - \frac{g(x)}{Dg(x)}$$

và $Dg(x)$ là đạo hàm của $g$ tại $x$. Newton’s method là việc sử dụng phương pháp fixed-point mà chúng ta đã thấy ở trên để xấp xỉ nghiệm của phương trình bằng cách tìm fixed-point của hàm $f$.¹¹

Với nhiều hàm $g$ và giá trị đoán ban đầu đủ tốt cho $x$, Newton’s method hội tụ rất nhanh đến nghiệm của $g(x) = 0$.¹²

Để hiện thực Newton’s method như một procedure, trước tiên chúng ta phải diễn đạt ý tưởng đạo hàm. Lưu ý rằng “derivative” (đạo hàm), giống như average damping, là một thứ biến đổi một hàm thành một hàm khác. Ví dụ, đạo hàm của hàm $x\mapsto x^{3}$ là hàm $x\mapsto 3x^{2}$. Nói chung, nếu $g$ là một hàm và $dx$ là một số nhỏ, thì đạo hàm $Dg$ của $g$ là hàm có giá trị tại bất kỳ số $x$ nào được cho bởi (trong giới hạn $dx$ nhỏ)

$$Dg(x), = ,{\frac{g(x + dx) - g(x)}{dx}.}$$

Do đó, chúng ta có thể diễn đạt ý tưởng đạo hàm (lấy $dx$ chẳng hạn là 0.00001) thành procedure:

(define (deriv g)
  (lambda (x)
    (/ (- (g (+ x dx)) (g x))
       dx)))

cùng với định nghĩa:

(define dx 0.00001)

Giống như average-damp, deriv là một procedure nhận một procedure làm đối số và trả về một procedure làm giá trị. Ví dụ, để xấp xỉ đạo hàm của $x\mapsto x^{3}$ tại 5 (giá trị chính xác là 75) chúng ta có thể tính:

(define (cube x) (* x x x))

((deriv cube) 5)
75.00014999664018

Với sự trợ giúp của deriv, chúng ta có thể diễn đạt Newton’s method như một quá trình fixed-point:

(define (newton-transform g)
  (lambda (x)
    (- x (/ (g x) 
            ((deriv g) x)))))

(define (newtons-method g guess)
  (fixed-point (newton-transform g) 
               guess))

Procedure newton-transform diễn đạt công thức ở đầu mục này, và newtons-method được định nghĩa trực tiếp dựa trên đó. Nó nhận đối số là một procedure tính hàm mà ta muốn tìm nghiệm, cùng với một giá trị đoán ban đầu. Ví dụ, để tìm căn bậc hai của $x$, chúng ta có thể dùng Newton’s method để tìm nghiệm của hàm $y\mapsto y^{2} - x$ bắt đầu với giá trị đoán ban đầu là 1.¹³

Điều này mang lại một dạng khác của procedure tính căn bậc hai:

(define (sqrt x)
  (newtons-method 
   (lambda (y) 
     (- (square y) x)) 
   1.0))

Các trừu tượng và first-class procedures (thủ tục hạng nhất)

Chúng ta đã thấy hai cách để diễn đạt việc tính căn bậc hai như một trường hợp của một phương pháp tổng quát hơn: một lần như một tìm kiếm fixed-point (điểm bất động) và một lần sử dụng Newton’s method (phương pháp Newton). Vì Newton’s method tự nó được diễn đạt như một quá trình fixed-point, nên thực tế chúng ta đã thấy hai cách để tính căn bậc hai như các fixed points. Mỗi phương pháp bắt đầu với một hàm và tìm một fixed point của một phép biến đổi nào đó của hàm đó. Chúng ta có thể diễn đạt ý tưởng tổng quát này thành một procedure (thủ tục):

(define (fixed-point-of-transform 
         g transform guess)
  (fixed-point (transform g) guess))

Procedure tổng quát này nhận các đối số là một procedure g tính một hàm nào đó, một procedure biến đổi g, và một giá trị đoán ban đầu. Kết quả trả về là một fixed point của hàm đã được biến đổi.

Sử dụng trừu tượng này, chúng ta có thể viết lại phép tính căn bậc hai đầu tiên trong phần này (nơi chúng ta tìm một fixed point của phiên bản average-damped của $y\mapsto x/y$) như một trường hợp của phương pháp tổng quát này:

(define (sqrt x)
  (fixed-point-of-transform 
   (lambda (y) (/ x y))
   average-damp
   1.0))

Tương tự, chúng ta có thể diễn đạt phép tính căn bậc hai thứ hai trong phần này (một trường hợp của Newton’s method tìm một fixed point của Newton transform của $y\mapsto y^{2} - x$) như sau:

(define (sqrt x)
  (fixed-point-of-transform 
   (lambda (y) (- (square y) x))
   newton-transform
   1.0))

Chúng ta bắt đầu mục 1.3 với nhận xét rằng compound procedures (thủ tục phức hợp) là một cơ chế trừu tượng quan trọng, vì chúng cho phép chúng ta diễn đạt các phương pháp tính toán tổng quát như những phần tử tường minh trong ngôn ngữ lập trình. Giờ đây, chúng ta đã thấy cách higher-order procedures cho phép thao tác với các phương pháp tổng quát này để tạo ra các trừu tượng mới.

Với tư cách lập trình viên, chúng ta nên luôn cảnh giác với các cơ hội nhận diện những trừu tượng cơ bản trong chương trình của mình, xây dựng và khái quát hóa chúng để tạo ra các trừu tượng mạnh mẽ hơn. Điều này không có nghĩa là lúc nào cũng phải viết chương trình theo cách trừu tượng nhất có thể; lập trình viên giỏi biết cách chọn mức độ trừu tượng phù hợp với nhiệm vụ. Nhưng điều quan trọng là phải có khả năng tư duy theo các trừu tượng này, để sẵn sàng áp dụng chúng trong các ngữ cảnh mới. Ý nghĩa của higher-order procedures là chúng cho phép chúng ta biểu diễn các trừu tượng này một cách tường minh như các phần tử trong ngôn ngữ lập trình, để chúng có thể được xử lý giống như các phần tử tính toán khác.

Nói chung, các ngôn ngữ lập trình áp đặt những hạn chế về cách các phần tử tính toán có thể được thao tác. Các phần tử có ít hạn chế nhất được gọi là có trạng thái first-class (hạng nhất). Một số “quyền và đặc quyền” của các phần tử first-class là:¹⁴

• Chúng có thể được đặt tên bởi các biến.
• Chúng có thể được truyền làm đối số cho procedures.
• Chúng có thể được trả về như kết quả của procedures.
• Chúng có thể được bao gồm trong data structures (cấu trúc dữ liệu).¹⁵

Lisp, không giống như các ngôn ngữ lập trình phổ biến khác, trao cho procedures trạng thái first-class đầy đủ. Điều này đặt ra những thách thức cho việc hiện thực hiệu quả, nhưng lợi ích về sức biểu đạt thu được là rất lớn.¹⁶