3.1 Assignment và Local State

Thông thường, chúng ta nhìn nhận thế giới như được tạo thành từ các đối tượng độc lập, mỗi đối tượng có một trạng thái thay đổi theo thời gian. Một đối tượng được cho là “có state (trạng thái)” nếu hành vi của nó bị ảnh hưởng bởi lịch sử của nó. Ví dụ, một tài khoản ngân hàng có state ở chỗ câu trả lời cho câu hỏi “Tôi có thể rút $100 không?” phụ thuộc vào lịch sử các giao dịch gửi và rút tiền. Chúng ta có thể đặc trưng hóa state của một đối tượng bằng một hoặc nhiều state variables (biến trạng thái), mà giữa chúng lưu giữ đủ thông tin về lịch sử để xác định hành vi hiện tại của đối tượng. Trong một hệ thống ngân hàng đơn giản, chúng ta có thể đặc trưng hóa state của một tài khoản bằng số dư hiện tại thay vì phải ghi nhớ toàn bộ lịch sử giao dịch của tài khoản.

Trong một hệ thống gồm nhiều đối tượng, các đối tượng hiếm khi hoàn toàn độc lập. Mỗi đối tượng có thể ảnh hưởng đến state của các đối tượng khác thông qua các tương tác, vốn liên kết các state variables của một đối tượng với các state variables của đối tượng khác. Thật vậy, quan điểm cho rằng một hệ thống được tạo thành từ các đối tượng riêng biệt là hữu ích nhất khi các state variables của hệ thống có thể được nhóm thành các hệ con liên kết chặt chẽ với nhau nhưng chỉ liên kết lỏng lẻo với các hệ con khác.

Cách nhìn này về một hệ thống có thể là một khuôn khổ mạnh mẽ để tổ chức các mô hình tính toán của hệ thống. Để một mô hình như vậy có tính modular (mô-đun), nó nên được phân tách thành các computational objects (đối tượng tính toán) mô phỏng các đối tượng thực trong hệ thống. Mỗi computational object phải có local state variables (biến trạng thái cục bộ) riêng mô tả state của đối tượng thực. Vì state của các đối tượng trong hệ thống được mô phỏng thay đổi theo thời gian, các state variables của các computational objects tương ứng cũng phải thay đổi. Nếu chúng ta chọn mô phỏng dòng chảy của thời gian trong hệ thống bằng thời gian trôi qua trong máy tính, thì chúng ta phải có cách xây dựng các computational objects có hành vi thay đổi khi chương trình của chúng ta chạy. Đặc biệt, nếu chúng ta muốn mô phỏng các state variables bằng các tên ký hiệu thông thường trong ngôn ngữ lập trình, thì ngôn ngữ đó phải cung cấp một assignment operator (toán tử gán) để cho phép chúng ta thay đổi giá trị gắn với một tên.

3.1.1 Local State Variables

Để minh họa ý nghĩa của việc có một computational object với state thay đổi theo thời gian, hãy mô phỏng tình huống rút tiền từ một tài khoản ngân hàng. Chúng ta sẽ làm điều này bằng cách sử dụng một procedure (thủ tục) withdraw, nhận đối số là một amount cần rút. Nếu trong tài khoản có đủ tiền để đáp ứng yêu cầu rút, thì withdraw sẽ trả về số dư còn lại sau khi rút. Ngược lại, withdraw sẽ trả về thông báo Insufficient funds. Ví dụ, nếu chúng ta bắt đầu với $100 trong tài khoản, chúng ta sẽ nhận được chuỗi phản hồi sau khi dùng withdraw:

(withdraw 25)
75

(withdraw 25)
50

(withdraw 60)
"Insufficient funds"

(withdraw 15)
35

Hãy chú ý rằng biểu thức (withdraw 25), khi được tính hai lần, cho ra các giá trị khác nhau. Đây là một kiểu hành vi mới đối với một procedure. Cho đến nay, tất cả các procedure của chúng ta có thể được xem như các đặc tả để tính toán các hàm toán học. Một lần gọi procedure sẽ tính giá trị của hàm được áp dụng cho các đối số đã cho, và hai lần gọi cùng một procedure với cùng đối số luôn cho cùng một kết quả.¹

Để hiện thực withdraw, chúng ta có thể dùng một biến balance để biểu thị số dư tiền trong tài khoản và định nghĩa withdraw như một procedure truy cập balance. Procedure withdraw kiểm tra xem balance có ít nhất bằng amount yêu cầu hay không. Nếu có, withdraw sẽ giảm balance đi amount và trả về giá trị mới của balance. Ngược lại, withdraw trả về thông báo Insufficient funds. Dưới đây là định nghĩa của balance và withdraw:

(define balance 100)

(define (withdraw amount)
  (if (>= balance amount)
      (begin (set! balance (- balance amount))
             balance)
      "Insufficient funds"))

Việc giảm balance được thực hiện bằng biểu thức:

(set! balance (- balance amount))

Điều này sử dụng special form (dạng đặc biệt) set!, với cú pháp:

(set! ⟨name⟩ ⟨new-value⟩)

Ở đây ⟨name⟩ là một symbol và ⟨new-value⟩ là bất kỳ biểu thức nào. Set! thay đổi ⟨name⟩ sao cho giá trị của nó là kết quả thu được khi tính ⟨new-value⟩. Trong trường hợp này, chúng ta đang thay đổi balance sao cho giá trị mới của nó là kết quả của việc trừ amount khỏi giá trị trước đó của balance.²

Withdraw cũng sử dụng special form begin để khiến hai biểu thức được tính trong trường hợp kiểm tra if là đúng: đầu tiên giảm balance và sau đó trả về giá trị của balance. Nói chung, việc tính biểu thức:

(begin ⟨exp₁⟩ ⟨exp₂⟩ … ⟨expₖ⟩)

sẽ khiến các biểu thức $\langle exp_{1}\rangle$ đến $\langle exp_{k}\rangle$ được tính tuần tự và giá trị của biểu thức cuối cùng $\langle exp_{k}\rangle$ được trả về như giá trị của toàn bộ form begin.³

Mặc dù withdraw hoạt động như mong muốn, biến balance lại gây ra một vấn đề. Như đã nêu ở trên, balance là một tên được định nghĩa trong global environment (môi trường toàn cục) và có thể được tự do truy cập hoặc sửa đổi bởi bất kỳ procedure nào. Sẽ tốt hơn nhiều nếu chúng ta có thể làm cho balance trở thành nội bộ của withdraw, sao cho withdraw là procedure duy nhất có thể truy cập trực tiếp balance và bất kỳ procedure nào khác chỉ có thể truy cập balance một cách gián tiếp (thông qua các lần gọi withdraw). Điều này sẽ mô phỏng chính xác hơn khái niệm rằng balance là một local state variable được withdraw sử dụng để theo dõi state của tài khoản.

Chúng ta có thể làm cho balance trở thành nội bộ của withdraw bằng cách viết lại định nghĩa như sau:

(define new-withdraw
  (let ((balance 100))
    (lambda (amount)
      (if (>= balance amount)
          (begin (set! balance 
                       (- balance amount))
                 balance)
          "Insufficient funds"))))

Những gì chúng ta đã làm ở đây là sử dụng let để thiết lập một environment (môi trường) với một local variable (biến cục bộ) balance, được gán với giá trị khởi tạo 100. Bên trong local environment này, chúng ta dùng lambda để tạo một procedure (thủ tục) nhận amount làm đối số và hoạt động giống như procedure withdraw trước đó. Procedure này — được trả về như kết quả của việc tính toán biểu thức let — là new-withdraw, hoạt động chính xác như withdraw nhưng biến balance của nó không thể được truy cập bởi bất kỳ procedure nào khác.⁴

Kết hợp set! với local variables là kỹ thuật lập trình tổng quát mà chúng ta sẽ sử dụng để xây dựng các computational objects (đối tượng tính toán) với local state (trạng thái cục bộ). Thật không may, việc sử dụng kỹ thuật này lại nảy sinh một vấn đề nghiêm trọng: Khi lần đầu tiên giới thiệu về procedures, chúng ta cũng đã giới thiệu substitution model of evaluation (mô hình thay thế trong tính toán) (1.1.5) để cung cấp một cách diễn giải ý nghĩa của việc áp dụng procedure. Chúng ta đã nói rằng việc áp dụng một procedure nên được hiểu là tính toán phần thân của procedure với các tham số hình thức được thay thế bằng giá trị của chúng. Vấn đề là, ngay khi chúng ta đưa assignment (gán) vào ngôn ngữ, substitution model không còn là một mô hình đầy đủ cho việc áp dụng procedure nữa. (Chúng ta sẽ thấy lý do tại sao trong 3.1.3.) Do đó, về mặt kỹ thuật, tại thời điểm này chúng ta chưa có cách nào để hiểu tại sao procedure new-withdraw lại hoạt động như đã mô tả ở trên. Để thực sự hiểu một procedure như new-withdraw, chúng ta sẽ cần phát triển một mô hình mới cho việc áp dụng procedure. Trong 3.2, chúng ta sẽ giới thiệu mô hình đó, cùng với lời giải thích về set! và local variables. Tuy nhiên, trước tiên, chúng ta sẽ xem xét một số biến thể dựa trên ý tưởng của new-withdraw.

Procedure sau đây, make-withdraw, tạo ra các “withdrawal processors” (bộ xử lý rút tiền). Tham số hình thức balance trong make-withdraw chỉ định số tiền ban đầu trong tài khoản.⁵

(define (make-withdraw balance)
  (lambda (amount)
    (if (>= balance amount)
        (begin (set! balance 
                     (- balance amount))
               balance)
        "Insufficient funds")))

Make-withdraw có thể được sử dụng như sau để tạo ra hai đối tượng W1 và W2:

(define W1 (make-withdraw 100))
(define W2 (make-withdraw 100))

(W1 50)
50

(W2 70)
30

(W2 40)
"Insufficient funds"

(W1 40)
10

Hãy chú ý rằng W1 và W2 là hai đối tượng hoàn toàn độc lập, mỗi đối tượng có local state variable balance riêng. Việc rút tiền từ một đối tượng không ảnh hưởng đến đối tượng kia.

Chúng ta cũng có thể tạo ra các đối tượng xử lý cả việc gửi tiền (deposit) lẫn rút tiền (withdraw), và do đó có thể biểu diễn các tài khoản ngân hàng đơn giản. Dưới đây là một procedure trả về một “bank-account object” (đối tượng tài khoản ngân hàng) với số dư khởi tạo được chỉ định:

(define (make-account balance)
  (define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance 
                     (- balance amount))
               balance)
        "Insufficient funds"))
  (define (deposit amount)
    (set! balance (+ balance amount))
    balance)
  (define (dispatch m)
    (cond ((eq? m 'withdraw) withdraw)
          ((eq? m 'deposit) deposit)
          (else (error "Unknown request: 
                 MAKE-ACCOUNT" m))))
  dispatch)

Mỗi lần gọi make-account sẽ thiết lập một environment với một local state variable balance. Bên trong environment này, make-account định nghĩa các procedure deposit và withdraw để truy cập balance, cùng một procedure bổ sung dispatch nhận một “message” (thông điệp) làm đầu vào và trả về một trong hai procedure cục bộ đó. Procedure dispatch này được trả về như giá trị đại diện cho bank-account object. Đây chính là phong cách lập trình message-passing (truyền thông điệp) mà chúng ta đã thấy trong 2.4.3, mặc dù ở đây chúng ta sử dụng nó kết hợp với khả năng thay đổi local variables.

Make-account có thể được sử dụng như sau:

(define acc (make-account 100))

((acc 'withdraw) 50)
50

((acc 'withdraw) 60)
"Insufficient funds"

((acc 'deposit) 40)
90

((acc 'withdraw) 60)
30

Mỗi lần gọi acc sẽ trả về procedure deposit hoặc withdraw được định nghĩa cục bộ, sau đó procedure này được áp dụng cho amount đã chỉ định. Giống như với make-withdraw, một lần gọi khác tới make-account:

(define acc2 (make-account 100))

sẽ tạo ra một account object hoàn toàn riêng biệt, duy trì local balance của riêng nó.

3.1.2 Lợi ích của việc đưa Assignment vào

Như chúng ta sẽ thấy, việc đưa assignment (gán) vào ngôn ngữ lập trình sẽ dẫn chúng ta vào một “bụi rậm” của những vấn đề khái niệm phức tạp. Tuy nhiên, việc nhìn nhận các hệ thống như tập hợp các đối tượng với local state (trạng thái cục bộ) là một kỹ thuật mạnh mẽ để duy trì thiết kế mang tính modular (mô-đun). Như một ví dụ đơn giản, hãy xem xét thiết kế của một procedure (thủ tục) rand mà mỗi khi được gọi sẽ trả về một số nguyên được chọn ngẫu nhiên.

Không hề rõ ràng “được chọn ngẫu nhiên” nghĩa là gì. Điều mà chúng ta mong muốn là các lần gọi liên tiếp tới rand sẽ tạo ra một dãy số có các đặc tính thống kê của phân phối đều. Chúng ta sẽ không bàn về các phương pháp tạo ra các dãy phù hợp ở đây. Thay vào đó, giả sử rằng chúng ta có một procedure rand-update với tính chất là nếu bắt đầu với một số $x_{1}$ và tạo ra

x₂ = (rand-update x₁)
x₃ = (rand-update x₂)

thì dãy giá trị $x_{1}$, $x_{2}$, $x_{3}$, … sẽ có các đặc tính thống kê mong muốn.⁶

Chúng ta có thể hiện thực rand như một procedure với một local state variable x được khởi tạo bằng một giá trị cố định random-init. Mỗi lần gọi rand sẽ tính rand-update của giá trị hiện tại của x, trả về giá trị này như số ngẫu nhiên, đồng thời lưu giá trị này làm giá trị mới của x.

(define rand
  (let ((x random-init))
    (lambda () (set! x (rand-update x)) x)))

Tất nhiên, chúng ta có thể tạo ra cùng một dãy số ngẫu nhiên mà không cần dùng assignment, chỉ bằng cách gọi trực tiếp rand-update. Tuy nhiên, điều này sẽ có nghĩa là bất kỳ phần nào của chương trình sử dụng số ngẫu nhiên đều phải ghi nhớ rõ giá trị hiện tại của x để truyền làm đối số cho rand-update. Để thấy điều này phiền toái thế nào, hãy xem xét việc sử dụng số ngẫu nhiên để hiện thực một kỹ thuật gọi là Monte Carlo simulation (mô phỏng Monte Carlo).

Phương pháp Monte Carlo bao gồm việc chọn ngẫu nhiên các thí nghiệm mẫu từ một tập hợp lớn, sau đó rút ra kết luận dựa trên các xác suất ước lượng từ việc thống kê kết quả của các thí nghiệm đó. Ví dụ, chúng ta có thể xấp xỉ $\pi$ bằng cách sử dụng thực tế rằng $6/\pi^{2}$ là xác suất để hai số nguyên được chọn ngẫu nhiên không có ước số chung; nghĩa là, ước số chung lớn nhất của chúng bằng 1.⁷ Để thu được giá trị xấp xỉ của $\pi$, chúng ta thực hiện một số lượng lớn thí nghiệm. Trong mỗi thí nghiệm, chúng ta chọn hai số nguyên ngẫu nhiên và kiểm tra xem GCD của chúng có bằng 1 hay không. Tỷ lệ số lần kiểm tra thành công sẽ cho chúng ta ước lượng của $6/\pi^{2}$, và từ đó suy ra giá trị xấp xỉ của $\pi$.

Trọng tâm của chương trình là một procedure monte-carlo, nhận vào số lần thử nghiệm và một thí nghiệm, được biểu diễn dưới dạng một procedure không đối số, mỗi lần chạy sẽ trả về true hoặc false. Monte-carlo chạy thí nghiệm số lần đã định và trả về một số biểu thị tỷ lệ các lần thí nghiệm cho kết quả true.

(define (estimate-pi trials)
  (sqrt (/ 6 (monte-carlo trials 
                          cesaro-test))))
(define (cesaro-test)
   (= (gcd (rand) (rand)) 1))

(define (monte-carlo trials experiment)
  (define (iter trials-remaining trials-passed)
    (cond ((= trials-remaining 0)
           (/ trials-passed trials))
          ((experiment)
           (iter (- trials-remaining 1) 
                 (+ trials-passed 1)))
          (else
           (iter (- trials-remaining 1) 
                 trials-passed))))
  (iter trials 0))

Bây giờ, hãy thử thực hiện cùng phép tính đó nhưng dùng trực tiếp rand-update thay vì rand, theo cách mà chúng ta buộc phải làm nếu không dùng assignment để mô hình hóa local state:

(define (estimate-pi trials)
  (sqrt (/ 6 (random-gcd-test trials 
                              random-init))))

(define (random-gcd-test trials initial-x)
  (define (iter trials-remaining 
                trials-passed 
                x)
    (let ((x1 (rand-update x)))
      (let ((x2 (rand-update x1)))
        (cond ((= trials-remaining 0)
               (/ trials-passed trials))
              ((= (gcd x1 x2) 1)
               (iter (- trials-remaining 1)
                     (+ trials-passed 1)
                     x2))
              (else
               (iter (- trials-remaining 1)
                     trials-passed
                     x2))))))
  (iter trials 0 initial-x))

Mặc dù chương trình vẫn đơn giản, nhưng nó bộc lộ một số vi phạm khó chịu đối với tính modular. Trong phiên bản đầu tiên của chương trình, sử dụng rand, chúng ta có thể diễn đạt phương pháp Monte Carlo trực tiếp như một procedure tổng quát monte-carlo nhận vào một procedure experiment bất kỳ. Trong phiên bản thứ hai, khi không có local state cho bộ sinh số ngẫu nhiên, random-gcd-test phải thao tác tường minh với các số ngẫu nhiên x1 và x2, đồng thời truyền lại x2 qua vòng lặp lặp lại như đầu vào mới cho rand-update. Việc xử lý tường minh các số ngẫu nhiên này làm đan xen cấu trúc tích lũy kết quả kiểm tra với thực tế rằng thí nghiệm cụ thể của chúng ta sử dụng hai số ngẫu nhiên, trong khi các thí nghiệm Monte Carlo khác có thể dùng một hoặc ba số ngẫu nhiên. Ngay cả procedure cấp cao nhất estimate-pi cũng phải quan tâm đến việc cung cấp một số ngẫu nhiên ban đầu. Việc “ruột” của bộ sinh số ngẫu nhiên bị lộ ra các phần khác của chương trình khiến chúng ta khó cô lập ý tưởng Monte Carlo để áp dụng cho các tác vụ khác. Trong phiên bản đầu tiên của chương trình, assignment đã encapsulate (đóng gói) state của bộ sinh số ngẫu nhiên bên trong procedure rand, nhờ đó chi tiết về việc sinh số ngẫu nhiên vẫn độc lập với phần còn lại của chương trình.

Hiện tượng tổng quát được minh họa qua ví dụ Monte Carlo là: từ góc nhìn của một phần trong một quá trình phức tạp, các phần khác dường như thay đổi theo thời gian. Chúng có local state ẩn và thay đổi theo thời gian. Nếu chúng ta muốn viết các chương trình máy tính có cấu trúc phản ánh sự phân tách này, chúng ta tạo ra các computational objects (như tài khoản ngân hàng và bộ sinh số ngẫu nhiên) có hành vi thay đổi theo thời gian. Chúng ta mô hình hóa state bằng local state variables, và mô hình hóa sự thay đổi state bằng các assignment tới những biến đó.

Thật dễ bị cám dỗ để kết thúc phần thảo luận này bằng cách nói rằng, bằng việc đưa assignment và kỹ thuật ẩn state trong local variables, chúng ta có thể cấu trúc hệ thống theo cách modular hơn so với việc phải thao tác tường minh toàn bộ state bằng cách truyền thêm các tham số. Tuy nhiên, như chúng ta sẽ thấy, câu chuyện không đơn giản như vậy.

3.1.3 The Costs of Introducing Assignment

Như chúng ta đã thấy, thao tác set! cho phép chúng ta mô hình hóa các đối tượng có local state (trạng thái cục bộ). Tuy nhiên, lợi thế này đi kèm một cái giá. Ngôn ngữ lập trình của chúng ta không còn có thể được diễn giải theo substitution model of procedure application đã giới thiệu ở 1.1.5. Hơn nữa, không có một mô hình đơn giản nào với các tính chất toán học “đẹp” lại có thể làm khung khái niệm đầy đủ để xử lý các đối tượng và assignment (gán) trong ngôn ngữ lập trình.

Chừng nào chúng ta chưa dùng assignment, hai lần tính cùng một procedure với cùng các đối số sẽ cho cùng một kết quả, nhờ đó các procedure có thể được xem là đang tính các hàm toán học. Lập trình không sử dụng bất kỳ assignment nào, như chúng ta đã làm xuyên suốt hai chương đầu của cuốn sách, vì thế được gọi là functional programming (lập trình hàm).

Để hiểu assignment làm phức tạp vấn đề như thế nào, hãy xem xét một phiên bản đơn giản hóa của procedure make-withdraw trong 3.1.1, bỏ qua việc kiểm tra thiếu số dư:

(define (make-simplified-withdraw balance)
  (lambda (amount)
    (set! balance (- balance amount))
    balance))

(define W (make-simplified-withdraw 25))

(W 20)
5

(W 10)
-5

So sánh procedure này với procedure make-decrementer sau, vốn không dùng set!:

(define (make-decrementer balance)
  (lambda (amount)
    (- balance amount)))

Make-decrementer trả về một procedure trừ đầu vào của nó khỏi một lượng xác định balance, nhưng không có hiệu ứng tích lũy qua các lần gọi liên tiếp như với make-simplified-withdraw:

(define D (make-decrementer 25))

(D 20)
5

(D 10)
15

Chúng ta có thể dùng substitution model để giải thích make-decrementer hoạt động ra sao. Chẳng hạn, hãy phân tích việc tính biểu thức

((make-decrementer 25) 20)

Trước hết, ta đơn giản hóa toán tử của phép kết hợp bằng cách thay 25 cho balance trong thân của make-decrementer. Điều này rút gọn biểu thức thành

((lambda (amount) (- 25 amount)) 20)

Bây giờ ta áp dụng toán tử bằng cách thay 20 cho amount trong thân của biểu thức lambda:

(- 25 20)

Kết quả cuối cùng là 5.

Tuy nhiên, hãy để ý điều gì xảy ra nếu chúng ta cố gắng phân tích thay thế tương tự với make-simplified-withdraw:

((make-simplified-withdraw 25) 20)

Trước hết, ta đơn giản hóa toán tử bằng cách thay 25 cho balance trong thân của make-simplified-withdraw. Điều này rút gọn biểu thức thành⁸

((lambda (amount) 
   (set! balance (- 25 amount)) 25)
 20)

Bây giờ ta áp dụng toán tử bằng cách thay 20 cho amount trong thân của biểu thức lambda:

(set! balance (- 25 20)) 25

Nếu tuân thủ substitution model, chúng ta sẽ phải nói rằng ý nghĩa của việc áp dụng procedure là trước tiên đặt balance thành 5 rồi trả về 25 như giá trị của biểu thức. Điều này cho ra đáp án sai. Để có được đáp án đúng, chúng ta sẽ phải bằng cách nào đó phân biệt lần xuất hiện thứ nhất của balance (trước hiệu ứng của set!) với lần xuất hiện thứ hai của balance (sau hiệu ứng của set!), và substitution model không thể làm điều này.

Vấn đề ở đây là substitution rốt cuộc dựa trên quan niệm rằng các symbol trong ngôn ngữ của chúng ta về bản chất là tên gọi cho các giá trị. Nhưng ngay khi chúng ta đưa vào set! và ý tưởng rằng giá trị của một biến có thể thay đổi, một biến không còn đơn giản chỉ là một cái tên. Giờ đây một biến bằng cách nào đó tham chiếu đến một nơi (place) mà tại đó một giá trị có thể được lưu trữ, và giá trị được lưu tại nơi này có thể thay đổi. Trong 3.2, chúng ta sẽ thấy environments đóng vai trò “place” này trong mô hình tính toán của chúng ta như thế nào.

Sameness và change

Vấn đề xuất hiện ở đây sâu sắc hơn nhiều so với việc chỉ đơn thuần là sự sụp đổ của một mô hình tính toán cụ thể. Ngay khi chúng ta đưa khái niệm change (thay đổi) vào các mô hình tính toán, nhiều khái niệm vốn trước đây đơn giản trở nên khó xử lý. Hãy xem xét khái niệm hai thứ “giống nhau” (the same).

Giả sử chúng ta gọi make-decrementer hai lần với cùng một đối số để tạo ra hai procedures (thủ tục):

(define D1 (make-decrementer 25))
(define D2 (make-decrementer 25))

D1 và D2 có giống nhau không? Một câu trả lời chấp nhận được là có, bởi vì D1 và D2 có cùng computational behavior (hành vi tính toán) — mỗi cái là một procedure trừ đầu vào của nó khỏi 25. Thực tế, D1 có thể được thay thế cho D2 trong bất kỳ phép tính nào mà không làm thay đổi kết quả.

Hãy so sánh điều này với việc gọi make-simplified-withdraw hai lần:

(define W1 (make-simplified-withdraw 25))
(define W2 (make-simplified-withdraw 25))

W1 và W2 có giống nhau không? Chắc chắn là không, bởi vì các lần gọi W1 và W2 tạo ra các hiệu ứng khác nhau, như được thể hiện qua chuỗi tương tác sau:

(W1 20)
5

(W1 20)
-15

(W2 20)
5

Mặc dù W1 và W2 “bằng nhau” theo nghĩa là cả hai đều được tạo ra bằng cách tính cùng một biểu thức (make-simplified-withdraw 25), nhưng không đúng khi nói rằng W1 có thể được thay thế cho W2 trong bất kỳ biểu thức nào mà không làm thay đổi kết quả của việc tính biểu thức đó.

Một ngôn ngữ hỗ trợ khái niệm “equals can be substituted for equals” (các giá trị bằng nhau có thể thay thế cho nhau) trong một biểu thức mà không làm thay đổi giá trị của biểu thức đó được gọi là referentially transparent (trong suốt tham chiếu). Referential transparency bị vi phạm khi chúng ta đưa set! vào ngôn ngữ lập trình. Điều này khiến cho việc xác định khi nào có thể đơn giản hóa các biểu thức bằng cách thay thế các biểu thức tương đương trở nên phức tạp. Do đó, việc lập luận về các chương trình sử dụng assignment trở nên khó khăn hơn rất nhiều.

Khi từ bỏ referential transparency, khái niệm “giống nhau” đối với các computational objects trở nên khó nắm bắt một cách hình thức. Thật vậy, ý nghĩa của “giống nhau” trong thế giới thực mà các chương trình của chúng ta mô phỏng vốn dĩ cũng không rõ ràng. Nói chung, chúng ta chỉ có thể xác định rằng hai đối tượng trông giống hệt nhau thực sự là “cùng một đối tượng” bằng cách thay đổi một đối tượng và sau đó quan sát xem đối tượng còn lại có thay đổi theo cùng cách hay không. Nhưng làm sao chúng ta biết một đối tượng đã “thay đổi” nếu không phải bằng cách quan sát “cùng một” đối tượng hai lần và xem liệu một thuộc tính nào đó của đối tượng có khác nhau giữa hai lần quan sát hay không? Như vậy, chúng ta không thể xác định “thay đổi” nếu không có một khái niệm a priori (tiên nghiệm) về “giống nhau”, và cũng không thể xác định “giống nhau” nếu không quan sát các hiệu ứng của thay đổi.

Ví dụ về cách vấn đề này nảy sinh trong lập trình: giả sử Peter và Paul có một tài khoản ngân hàng với $100. Có một sự khác biệt đáng kể giữa việc mô hình hóa tình huống này như sau:

(define peter-acc (make-account 100))
(define paul-acc (make-account 100))

và mô hình hóa như sau:

(define peter-acc (make-account 100))
(define paul-acc peter-acc)

Trong tình huống đầu tiên, hai tài khoản ngân hàng là riêng biệt. Các giao dịch của Peter sẽ không ảnh hưởng đến tài khoản của Paul, và ngược lại. Trong tình huống thứ hai, tuy nhiên, chúng ta đã định nghĩa paul-acc là the same thing (cùng một thứ) với peter-acc. Thực tế, Peter và Paul giờ đây có một tài khoản ngân hàng chung, và nếu Peter rút tiền từ peter-acc thì Paul sẽ thấy số dư trong paul-acc giảm xuống. Hai tình huống tương tự nhưng khác biệt này có thể gây nhầm lẫn khi xây dựng các mô hình tính toán. Với tài khoản chung, đặc biệt dễ gây nhầm lẫn khi chỉ có một đối tượng (tài khoản ngân hàng) nhưng lại có hai tên khác nhau (peter-acc và paul-acc); nếu chúng ta đang tìm tất cả các vị trí trong chương trình nơi paul-acc có thể bị thay đổi, chúng ta phải nhớ kiểm tra cả những chỗ thay đổi peter-acc nữa.⁹

Liên hệ với những nhận xét ở trên về “sameness” và “change”, hãy để ý rằng nếu Peter và Paul chỉ có thể xem số dư tài khoản của họ, và không thể thực hiện các thao tác thay đổi số dư, thì vấn đề liệu hai tài khoản có khác nhau hay không sẽ trở nên vô nghĩa. Nói chung, miễn là chúng ta không bao giờ thay đổi các data objects, chúng ta có thể coi một compound data object (đối tượng dữ liệu phức hợp) chính xác là tổng thể các thành phần của nó. Ví dụ, một số hữu tỉ được xác định bằng cách cho tử số và mẫu số của nó. Nhưng cách nhìn này không còn đúng khi có sự thay đổi, nơi một compound data object có một “identity” (danh tính) khác với các thành phần cấu thành nó. Một tài khoản ngân hàng vẫn là “cùng một” tài khoản ngân hàng ngay cả khi chúng ta thay đổi số dư bằng cách rút tiền; ngược lại, chúng ta có thể có hai tài khoản ngân hàng khác nhau với cùng thông tin trạng thái. Sự phức tạp này là hệ quả, không phải của ngôn ngữ lập trình, mà là của cách chúng ta nhìn nhận một tài khoản ngân hàng như một đối tượng. Chúng ta, chẳng hạn, không coi một số hữu tỉ là một đối tượng có thể thay đổi với identity, sao cho chúng ta có thể thay đổi tử số mà vẫn có “cùng một” số hữu tỉ.

Pitfalls of imperative programming

Trái ngược với functional programming (lập trình hàm), lập trình sử dụng nhiều assignment (gán) được gọi là imperative programming (lập trình mệnh lệnh). Bên cạnh việc làm phức tạp các mô hình tính toán, các chương trình viết theo phong cách imperative còn dễ mắc phải những lỗi mà functional programs không thể gặp. Ví dụ, hãy nhớ lại chương trình tính giai thừa dạng lặp trong 1.2.1:

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

Thay vì truyền các đối số trong vòng lặp lặp lại bên trong, chúng ta có thể áp dụng phong cách imperative hơn bằng cách sử dụng assignment tường minh để cập nhật giá trị của các biến product và counter:

(define (factorial n)
  (let ((product 1)
        (counter 1))
    (define (iter)
      (if (> counter n)
          product
          (begin (set! product (* counter 
                                  product))
                 (set! counter (+ counter 1))
                 (iter))))
    (iter)))

Điều này không làm thay đổi kết quả mà chương trình tạo ra, nhưng lại đưa vào một cái bẫy tinh vi. Làm thế nào để chúng ta quyết định thứ tự của các phép gán? Trong trường hợp này, chương trình đúng như đã viết. Nhưng nếu viết các phép gán theo thứ tự ngược lại:

(set! counter (+ counter 1))
(set! product (* counter product))

thì sẽ tạo ra một kết quả khác, sai. Nói chung, lập trình với assignment buộc chúng ta phải cân nhắc cẩn thận thứ tự tương đối của các phép gán để đảm bảo rằng mỗi câu lệnh đang sử dụng đúng phiên bản của các biến đã được thay đổi. Vấn đề này đơn giản là không xuất hiện trong functional programs.¹⁰

Độ phức tạp của các chương trình imperative còn trở nên tồi tệ hơn nếu chúng ta xét đến các ứng dụng trong đó nhiều tiến trình được thực thi đồng thời. Chúng ta sẽ quay lại vấn đề này trong 3.4. Tuy nhiên, trước tiên, chúng ta sẽ giải quyết vấn đề cung cấp một computational model (mô hình tính toán) cho các biểu thức có liên quan đến assignment, và khám phá việc sử dụng các objects (đối tượng) với local state trong thiết kế các mô phỏng.