5.1 Thiết kế Register Machine

Để thiết kế một register machine (máy thanh ghi), chúng ta phải thiết kế data paths ("đường dữ liệu" – bao gồm các register và các operation) và controller (bộ điều khiển) để sắp xếp trình tự thực hiện các operation này. Để minh họa việc thiết kế một register machine đơn giản, hãy xem xét Euclid’s Algorithm (thuật toán Euclid), được dùng để tính greatest common divisor (GCD – ước số chung lớn nhất) của hai số nguyên. Như chúng ta đã thấy ở mục 1.2.5, Euclid’s Algorithm có thể được thực hiện bằng một iterative process (quy trình lặp), như được mô tả bởi procedure (thủ tục) sau:

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

Một máy để thực hiện thuật toán này phải theo dõi hai số, $a$ và $b$, vì vậy ta giả sử rằng các số này được lưu trong hai register có cùng tên. Các operation cơ bản cần thiết là kiểm tra xem nội dung của register b có bằng 0 hay không và tính remainder (phần dư) của nội dung register a chia cho nội dung register b. Operation remainder là một quá trình phức tạp, nhưng tạm thời giả sử rằng chúng ta có một thiết bị nguyên thủy có thể tính phần dư. Ở mỗi vòng lặp của thuật toán GCD, nội dung của register a phải được thay thế bằng nội dung của register b, và nội dung của b phải được thay thế bằng phần dư của nội dung cũ của a chia cho nội dung cũ của b. Sẽ thuận tiện hơn nếu các phép thay thế này có thể được thực hiện đồng thời, nhưng trong mô hình register machine của chúng ta, ta giả định rằng chỉ một register có thể được gán giá trị mới tại mỗi bước. Để thực hiện các phép thay thế này, máy của chúng ta sẽ dùng một register “tạm thời” thứ ba, gọi là t. (Trước tiên phần dư sẽ được đặt vào t, sau đó nội dung của b sẽ được đặt vào a, và cuối cùng phần dư lưu trong t sẽ được đặt vào b.)

Chúng ta có thể minh họa các register và operation cần thiết cho máy này bằng cách sử dụng sơ đồ data-path như trong Hình 5.1. Trong sơ đồ này, các register (a, b, và t) được biểu diễn bằng các hình chữ nhật. Mỗi cách gán giá trị cho một register được biểu diễn bằng một mũi tên có ký hiệu X ở đầu, chỉ từ nguồn dữ liệu đến register. Ta có thể coi X như một nút bấm, khi nhấn sẽ cho phép giá trị tại nguồn “chảy” vào register được chỉ định. Nhãn bên cạnh mỗi nút là tên mà chúng ta sẽ dùng để tham chiếu đến nút đó. Các tên này là tùy ý, và có thể được chọn sao cho dễ nhớ (ví dụ, a<-b biểu thị việc nhấn nút gán nội dung của register b vào register a). Nguồn dữ liệu cho một register có thể là một register khác (như trong phép gán a<-b), kết quả của một operation (như trong phép gán t<-r), hoặc một constant (giá trị hằng không thể thay đổi, được biểu diễn trong sơ đồ data-path bằng một hình tam giác chứa giá trị hằng).

Figure 5.1: Data paths for a GCD machine.

Một operation tính toán giá trị từ các constant và nội dung của các register được biểu diễn trong sơ đồ data-path bằng một hình thang chứa tên của operation. Ví dụ, ô được đánh dấu rem trong Hình 5.1 biểu diễn một operation tính phần dư của nội dung các register a và b mà nó kết nối. Các mũi tên (không có nút bấm) chỉ từ các register và constant đầu vào đến ô này, và các mũi tên khác nối giá trị đầu ra của operation đến các register. Một test (kiểm tra) được biểu diễn bằng một hình tròn chứa tên của phép kiểm tra. Ví dụ, máy GCD của chúng ta có một operation kiểm tra xem nội dung của register b có bằng 0 hay không. Một test cũng có các mũi tên từ các register và constant đầu vào, nhưng không có mũi tên đầu ra; giá trị của nó được sử dụng bởi controller thay vì bởi data paths. Nhìn tổng thể, sơ đồ data-path cho thấy các register và operation cần thiết cho máy và cách chúng phải được kết nối. Nếu ta coi các mũi tên như dây dẫn và các nút X như công tắc, thì sơ đồ data-path rất giống với sơ đồ mạch điện của một máy có thể được chế tạo từ các linh kiện điện tử.

Để các data paths thực sự tính được GCD, các nút bấm phải được nhấn theo đúng trình tự. Chúng ta sẽ mô tả trình tự này bằng sơ đồ controller, như minh họa trong Hình 5.2. Các thành phần của sơ đồ controller cho biết cách các thành phần data-path nên được vận hành. Các ô chữ nhật trong sơ đồ controller xác định các nút data-path cần nhấn, và các mũi tên mô tả trình tự từ bước này sang bước tiếp theo. Hình thoi trong sơ đồ biểu thị một quyết định. Một trong hai mũi tên trình tự sẽ được theo, tùy thuộc vào giá trị của phép test data-path được xác định trong hình thoi. Chúng ta có thể diễn giải controller theo một phép ẩn dụ vật lý: Hãy tưởng tượng sơ đồ như một mê cung trong đó một viên bi đang lăn. Khi viên bi lăn vào một ô, nó nhấn nút data-path được ghi tên trong ô đó. Khi viên bi lăn vào một nút quyết định (chẳng hạn như phép kiểm tra b = 0), nó sẽ rời nút theo hướng được xác định bởi kết quả của phép test. Khi kết hợp lại, data paths và controller mô tả hoàn chỉnh một máy tính GCD. Chúng ta khởi động controller (viên bi lăn) tại vị trí được đánh dấu start, sau khi đã đặt các số vào các register a và b. Khi controller đến done, chúng ta sẽ tìm thấy giá trị GCD trong register a.

Figure 5.2: Controller for a GCD machine.

5.1.1 A Language for Describing Register Machines

Các sơ đồ data-path và controller là đủ để biểu diễn các máy đơn giản như GCD, nhưng chúng trở nên cồng kềnh khi mô tả các máy lớn như một Lisp interpreter (bộ thông dịch Lisp). Để có thể xử lý các máy phức tạp, chúng ta sẽ tạo ra một ngôn ngữ thể hiện, dưới dạng văn bản, toàn bộ thông tin được cung cấp bởi các sơ đồ data-path và controller. Chúng ta sẽ bắt đầu với một ký pháp phản ánh trực tiếp các sơ đồ này.

Chúng ta định nghĩa data paths của một máy bằng cách mô tả các register và các operation. Để mô tả một register, ta đặt cho nó một tên và chỉ ra các nút điều khiển việc gán giá trị cho nó. Chúng ta đặt tên cho mỗi nút này và chỉ ra nguồn dữ liệu đi vào register dưới sự điều khiển của nút. (Nguồn này có thể là một register, một constant, hoặc một operation.) Để mô tả một operation, ta đặt tên cho nó và chỉ ra các đầu vào của nó (các register hoặc constant).

Chúng ta định nghĩa controller của một máy như một dãy instructions (chỉ thị) cùng với labels (nhãn) xác định entry points (điểm vào) trong dãy. Một instruction là một trong các loại sau:

• Tên của một nút data-path cần nhấn để gán giá trị cho một register. (Điều này tương ứng với một ô trong sơ đồ controller.)
• Một instruction test, thực hiện một phép kiểm tra được chỉ định.
• Một conditional branch (instruction branch) đến một vị trí được chỉ ra bởi một label của controller, dựa trên kết quả của phép test trước đó. (Phép test và branch cùng nhau tương ứng với một hình thoi trong sơ đồ controller.) Nếu phép test là false, controller sẽ tiếp tục với instruction tiếp theo trong dãy. Ngược lại, controller sẽ tiếp tục với instruction ngay sau label.
• Một unconditional branch (instruction goto) chỉ định một label của controller tại đó sẽ tiếp tục thực thi.

Máy bắt đầu từ đầu dãy instruction của controller và dừng khi việc thực thi đến cuối dãy. Ngoại trừ khi một branch thay đổi luồng điều khiển, các instruction được thực hiện theo thứ tự liệt kê.

Figure 5.3 cho thấy máy GCD được mô tả theo cách này. Ví dụ này chỉ gợi ý phần nào tính tổng quát của các mô tả này, vì máy GCD là một trường hợp rất đơn giản: Mỗi register chỉ có một nút, và mỗi nút và test chỉ được dùng một lần trong controller

(data-paths (registers ((name a) (buttons ((name a<-b) (source (register b))))) ((name b) (buttons ((name b<-t) (source (register t))))) ((name t) (buttons ((name t<-r) (source (operation rem)))))) (operations ((name rem) (inputs (register a) (register b))) ((name =) (inputs (register b) (constant 0)))))

(controller test-b ; label (test =) ; test (branch (label gcd-done)) ; conditional branch (t<-r) ; button push (a<-b) ; button push (b<-t) ; button push (goto (label test-b)) ; unconditional branch gcd-done) ; label

Figure 5.3: $\downarrow$ A specification of the GCD machine.

Thật không may, thật khó để đọc một mô tả như vậy. Để hiểu được các instruction (chỉ thị) của controller, chúng ta phải liên tục tham chiếu lại các định nghĩa của tên nút bấm và tên operation, và để hiểu các nút bấm thực hiện điều gì, ta có thể phải tham chiếu đến định nghĩa của các operation. Do đó, chúng ta sẽ biến đổi ký pháp của mình để kết hợp thông tin từ phần mô tả data-path và controller sao cho chúng ta thấy tất cả cùng nhau.

Để có được dạng mô tả này, chúng ta sẽ thay thế các tên nút bấm và operation tùy ý bằng định nghĩa về hành vi của chúng. Nghĩa là, thay vì nói (trong controller) “Nhấn nút t<-r” và nói riêng (trong data paths) “Nút t<-r gán giá trị của operation rem vào register t” và “Các đầu vào của operation rem là nội dung của các register a và b”, chúng ta sẽ nói (trong controller) “Nhấn nút gán vào register t giá trị của operation rem trên nội dung của các register a và b.” Tương tự, thay vì nói (trong controller) “Thực hiện phép kiểm tra =” và nói riêng (trong data paths) “Phép kiểm tra = hoạt động trên nội dung của register b và constant 0”, chúng ta sẽ nói “Thực hiện phép kiểm tra = trên nội dung của register b và constant 0.” Chúng ta sẽ lược bỏ phần mô tả data-path, chỉ giữ lại chuỗi controller. Do đó, máy GCD được mô tả như sau:

(controller
 test-b
   (test (op =) (reg b) (const 0))
   (branch (label gcd-done))
   (assign t (op rem) (reg a) (reg b))
   (assign a (reg b))
   (assign b (reg t))
   (goto (label test-b))
 gcd-done)

Dạng mô tả này dễ đọc hơn so với loại minh họa trong Hình 5.3, nhưng nó cũng có những nhược điểm:

• Nó dài dòng hơn đối với các máy lớn, vì mô tả đầy đủ của các phần tử data-path được lặp lại mỗi khi các phần tử này được nhắc đến trong chuỗi instruction của controller. (Điều này không phải là vấn đề trong ví dụ GCD, vì mỗi operation và nút bấm chỉ được dùng một lần.) Hơn nữa, việc lặp lại các mô tả data-path làm che khuất cấu trúc data-path thực sự của máy; đối với một máy lớn, không dễ để thấy có bao nhiêu register, operation và nút bấm, cũng như cách chúng được kết nối.
• Bởi vì các instruction của controller trong định nghĩa máy trông giống như các biểu thức Lisp, nên rất dễ quên rằng chúng không phải là các biểu thức Lisp tùy ý. Chúng chỉ có thể ký hiệu các operation hợp lệ của máy. Ví dụ, các operation chỉ có thể hoạt động trực tiếp trên các constant và nội dung của register, chứ không phải trên kết quả của các operation khác.

Mặc dù có những nhược điểm này, chúng ta sẽ sử dụng ngôn ngữ register-machine này xuyên suốt chương này, vì chúng ta sẽ quan tâm nhiều hơn đến việc hiểu controller hơn là hiểu các phần tử và kết nối trong data paths. Tuy nhiên, chúng ta cần ghi nhớ rằng thiết kế data-path là rất quan trọng trong việc thiết kế các máy thực.

Actions

Hãy sửa đổi máy GCD để chúng ta có thể nhập vào các số mà ta muốn tìm GCD và nhận kết quả được in ra tại terminal. Chúng ta sẽ không bàn về cách tạo ra một máy có thể đọc và in, mà sẽ giả định (giống như khi chúng ta dùng read và display trong Scheme) rằng chúng có sẵn như các primitive operation (phép nguyên thủy)¹.

Read giống như các operation mà chúng ta đã dùng ở chỗ nó tạo ra một giá trị có thể lưu vào một register. Nhưng read không lấy đầu vào từ bất kỳ register nào; giá trị của nó phụ thuộc vào một điều gì đó xảy ra bên ngoài các phần của máy mà chúng ta đang thiết kế. Chúng ta sẽ cho phép các operation của máy có hành vi như vậy, và do đó sẽ vẽ và ký hiệu việc sử dụng read giống như bất kỳ operation nào khác tính toán một giá trị.

Print, ngược lại, khác với các operation mà chúng ta đã dùng ở một điểm cơ bản: Nó không tạo ra giá trị đầu ra để lưu vào một register. Mặc dù nó có một tác động, nhưng tác động này không nằm trên phần của máy mà chúng ta đang thiết kế. Chúng ta sẽ gọi loại operation này là một action. Chúng ta sẽ biểu diễn một action trong sơ đồ data-path giống như cách biểu diễn một operation tính toán giá trị — bằng một hình thang chứa tên của action. Các mũi tên chỉ vào ô action từ bất kỳ đầu vào nào (register hoặc constant). Chúng ta cũng gắn một nút bấm với action. Nhấn nút này sẽ làm action xảy ra. Để khiến controller nhấn nút action, chúng ta dùng một loại instruction mới gọi là perform. Do đó, action in nội dung của register a được biểu diễn trong chuỗi controller bằng instruction:

(perform (op print) (reg a))

Figure 5.4 cho thấy data paths và controller cho máy GCD mới. Thay vì để máy dừng lại sau khi in kết quả, chúng ta làm cho nó bắt đầu lại, để nó liên tục đọc một cặp số, tính GCD của chúng và in kết quả. Cấu trúc này giống như các driver loop mà chúng ta đã dùng trong các interpreter ở Chương 4.

Figure 5.4: A GCD machine that reads inputs and prints results.

5.1.2 Abstraction in Machine Design

Chúng ta thường định nghĩa một máy bao gồm các primitive operation thực chất rất phức tạp. Ví dụ, ở mục 5.4 và 5.5, chúng ta sẽ coi các thao tác trên environment của Scheme là primitive. Sự trừu tượng hóa như vậy là hữu ích vì nó cho phép chúng ta bỏ qua chi tiết của một số phần của máy để tập trung vào các khía cạnh khác của thiết kế. Tuy nhiên, việc chúng ta “quét” nhiều phức tạp xuống dưới tấm thảm không có nghĩa là thiết kế máy là phi thực tế. Chúng ta luôn có thể thay thế các “primitive” phức tạp bằng các primitive operation đơn giản hơn.

Xét máy GCD. Máy này có một instruction tính phần dư của nội dung các register a và b và gán kết quả vào register t. Nếu chúng ta muốn xây dựng máy GCD mà không dùng một primitive remainder operation, chúng ta phải chỉ ra cách tính phần dư bằng các operation đơn giản hơn, chẳng hạn như phép trừ. Thật vậy, chúng ta có thể viết một Scheme procedure tìm phần dư theo cách này:

(define (remainder n d)
  (if (< n d) n (remainder (- n d) d)))

Do đó, chúng ta có thể thay thế operation remainder trong data paths của máy GCD bằng một operation trừ và một phép kiểm tra so sánh. Hình 5.5 cho thấy data paths và controller cho máy đã được khai triển. Instruction

(assign t (op rem) (reg a) (reg b))

trong định nghĩa controller của GCD được thay thế bằng một chuỗi instruction chứa một vòng lặp, như minh họa trong Hình 5.6.

Figure 5.5: Data paths and controller for the elaborated GCD machine.

5.1.3 Subroutines

Khi thiết kế một máy để thực hiện một phép tính, chúng ta thường muốn sắp xếp sao cho các thành phần có thể được chia sẻ giữa các phần khác nhau của phép tính thay vì nhân đôi các thành phần đó. Hãy xét một máy bao gồm hai phép tính GCD — một phép tính tìm GCD của nội dung các register a và b và một phép tính tìm GCD của nội dung các register c và d. Chúng ta có thể bắt đầu bằng cách giả định rằng ta có một primitive gcd operation, sau đó khai triển hai lần xuất hiện của gcd này thành các operation nguyên thủy hơn. Hình 5.7 chỉ hiển thị phần data paths của các phép tính GCD trong máy kết quả, mà không cho thấy cách chúng kết nối với phần còn lại của máy. Hình này cũng cho thấy các phần tương ứng trong chuỗi controller của máy.

Figure 5.7: Portions of the data paths and controller sequence for a machine with two GCD computations.

Máy này có hai ô operation remainder và hai ô để kiểm tra equality. Nếu các thành phần bị nhân đôi là phức tạp, như ô remainder, thì đây sẽ không phải là cách xây dựng máy hiệu quả. Chúng ta có thể tránh việc nhân đôi các thành phần data-path bằng cách sử dụng cùng một thành phần cho cả hai phép tính GCD, miễn là việc này không ảnh hưởng đến phần còn lại của phép tính trong máy lớn hơn. Nếu các giá trị trong register a và b không còn cần thiết khi controller đến gcd-2 (hoặc nếu các giá trị này có thể được chuyển sang các register khác để lưu trữ an toàn), chúng ta có thể thay đổi máy để nó sử dụng register a và b thay vì register c và d trong việc tính GCD thứ hai cũng như GCD thứ nhất. Nếu làm vậy, chúng ta thu được chuỗi controller như trong Hình 5.8.

Figure 5.8: $\downarrow$ Portions of the controller sequence for a machine that uses the same data-path components for two different GCD computations.

gcd-1
(test (op =) (reg b) (const 0))
(branch (label after-gcd-1))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label gcd-1))
after-gcd-1
…
gcd-2
(test (op =) (reg b) (const 0))
(branch (label after-gcd-2))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label gcd-2))
after-gcd-2

Chúng ta đã loại bỏ các thành phần data-path trùng lặp (để data paths trở lại như trong Hình 5.1), nhưng controller giờ có hai chuỗi GCD chỉ khác nhau ở nhãn entry-point. Sẽ tốt hơn nếu thay hai chuỗi này bằng các nhánh đến một chuỗi duy nhất — một gcd subroutine (chương trình con) — và ở cuối subroutine đó, chúng ta nhảy trở lại đúng vị trí trong chuỗi instruction chính. Ta có thể thực hiện điều này như sau: Trước khi nhảy đến gcd, ta đặt một giá trị phân biệt (chẳng hạn 0 hoặc 1) vào một register đặc biệt, continue. Ở cuối subroutine gcd, ta sẽ quay lại after-gcd-1 hoặc after-gcd-2 tùy thuộc vào giá trị của register continue. Hình 5.9 cho thấy phần liên quan của chuỗi controller kết quả, chỉ bao gồm một bản sao của các instruction gcd.

Figure 5.9: $\downarrow$ Using a continue register to avoid the duplicate controller sequence in Figure 5.8.

gcd
(test (op =) (reg b) (const 0))
(branch (label gcd-done))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label gcd))
gcd-done
(test (op =) (reg continue) (const 0))
(branch (label after-gcd-1))
(goto (label after-gcd-2))
…
;; Before branching to gcd from
;; the first place where it is needed,
;; we place 0 in the continue register
(assign continue (const 0))
(goto (label gcd))
after-gcd-1
…
;; Before the second use of gcd, 
;; we place 1 in the continue register
(assign continue (const 1))
(goto (label gcd))
after-gcd-2

Đây là một cách tiếp cận hợp lý cho các bài toán nhỏ, nhưng sẽ trở nên rườm rà nếu có nhiều lần tính GCD trong chuỗi controller. Để quyết định tiếp tục thực thi ở đâu sau subroutine gcd, ta sẽ cần các phép kiểm tra trong data paths và các instruction rẽ nhánh trong controller cho tất cả các vị trí sử dụng gcd. Một phương pháp mạnh mẽ hơn để triển khai subroutine là để register continue giữ nhãn của entry point trong chuỗi controller mà tại đó việc thực thi sẽ tiếp tục khi subroutine kết thúc. Việc triển khai chiến lược này đòi hỏi một kiểu kết nối mới giữa data paths và controller của register machine: Phải có cách gán cho một register một nhãn trong chuỗi controller sao cho giá trị này có thể được lấy từ register và dùng để tiếp tục thực thi tại entry point được chỉ định.

Để phản ánh khả năng này, chúng ta sẽ mở rộng instruction assign của ngôn ngữ register-machine để cho phép một register được gán giá trị là một nhãn từ chuỗi controller (như một loại constant đặc biệt). Chúng ta cũng sẽ mở rộng instruction goto để cho phép thực thi tiếp tục tại entry point được mô tả bởi nội dung của một register thay vì chỉ tại entry point được mô tả bởi một nhãn constant. Sử dụng các cấu trúc mới này, chúng ta có thể kết thúc subroutine gcd bằng một nhánh đến vị trí được lưu trong register continue. Điều này dẫn đến chuỗi controller như trong Hình 5.10.

Figure 5.10: $\downarrow$ Assigning labels to the continue register simplifies and generalizes the strategy shown in Figure 5.9.

gcd
(test (op =) (reg b) (const 0))
(branch (label gcd-done))
(assign t (op rem) (reg a) (reg b))
(assign a (reg b))
(assign b (reg t))
(goto (label gcd))
gcd-done
(goto (reg continue))
…
;; Before calling gcd, 
;; we assign to continue the label
;; to which gcd should return.
(assign continue (label after-gcd-1))
(goto (label gcd))
after-gcd-1
…
;; Here is the second call to gcd,
;; with a different continuation.
(assign continue (label after-gcd-2))
(goto (label gcd))
after-gcd-2

Một máy có nhiều hơn một subroutine có thể sử dụng nhiều continuation register (ví dụ: gcd-continue, factorial-continue) hoặc tất cả các subroutine có thể dùng chung một register continue. Việc chia sẻ sẽ tiết kiệm hơn, nhưng chúng ta phải cẩn thận nếu có một subroutine (sub1) gọi một subroutine khác (sub2). Trừ khi sub1 lưu nội dung của continue vào một register khác trước khi thiết lập continue cho lời gọi sub2, sub1 sẽ không biết phải đi đâu khi nó kết thúc. Cơ chế được phát triển trong phần tiếp theo để xử lý recursion cũng cung cấp một giải pháp tốt hơn cho vấn đề gọi lồng nhau giữa các subroutine.

5.1.4 Using a Stack to Implement Recursion

Với các ý tưởng đã minh họa cho đến nay, chúng ta có thể triển khai bất kỳ iterative process nào bằng cách chỉ định một register machine có một register tương ứng với mỗi state variable của quá trình. Máy sẽ lặp lại việc thực thi một vòng lặp controller, thay đổi nội dung của các register, cho đến khi một điều kiện kết thúc nào đó được thỏa mãn. Tại mỗi điểm trong chuỗi controller, trạng thái của máy (đại diện cho trạng thái của iterative process) được xác định hoàn toàn bởi nội dung của các register (giá trị của các state variable).

Tuy nhiên, việc triển khai recursive process đòi hỏi một cơ chế bổ sung. Hãy xét phương pháp đệ quy sau để tính giai thừa, mà chúng ta đã xem lần đầu ở mục 1.2.1:

(define (factorial n)
  (if (= n 1) 
      1
      (* (factorial (- n 1)) n)))

Như chúng ta thấy từ procedure (thủ tục), việc tính $n!$ đòi hỏi phải tính $(n - 1)!$. Máy GCD của chúng ta, được mô phỏng theo procedure

(define (gcd a b)
  (if (= b 0) 
      a
      (gcd b (remainder a b))))

tương tự cũng phải tính một GCD khác. Nhưng có một sự khác biệt quan trọng giữa procedure gcd, vốn rút gọn phép tính ban đầu thành một phép tính GCD mới, và factorial, vốn đòi hỏi tính một giai thừa khác như một bài toán con. Trong GCD, đáp án của phép tính GCD mới chính là đáp án của bài toán ban đầu. Để tính GCD tiếp theo, chúng ta chỉ cần đặt các đối số mới vào các register đầu vào của máy GCD và tái sử dụng data paths của máy bằng cách thực thi cùng một chuỗi controller. Khi máy hoàn tất việc giải quyết bài toán GCD cuối cùng, nó đã hoàn thành toàn bộ phép tính.

Trong trường hợp factorial (hoặc bất kỳ recursive process nào), đáp án của bài toán con factorial mới không phải là đáp án của bài toán ban đầu. Giá trị thu được cho $(n - 1)!$ phải được nhân với $n$ để có đáp án cuối cùng. Nếu chúng ta cố bắt chước thiết kế của GCD và giải bài toán con factorial bằng cách giảm giá trị trong register n rồi chạy lại máy factorial, chúng ta sẽ không còn giá trị cũ của n để nhân với kết quả. Do đó, chúng ta cần một máy factorial thứ hai để xử lý bài toán con. Phép tính factorial thứ hai này lại có một bài toán con factorial khác, đòi hỏi một máy factorial thứ ba, và cứ thế tiếp diễn. Vì mỗi máy factorial lại chứa một máy factorial khác bên trong, tổng thể máy sẽ chứa một chuỗi lồng vô hạn các máy tương tự và do đó không thể được xây dựng từ một số lượng bộ phận cố định, hữu hạn.

Tuy nhiên, chúng ta vẫn có thể triển khai quá trình factorial như một register machine nếu có thể sắp xếp để sử dụng cùng một tập hợp thành phần cho mỗi lần lặp lồng nhau của máy. Cụ thể, máy tính $n!$ nên sử dụng cùng các thành phần để xử lý bài toán con tính $(n - 1)!$, bài toán con tính $(n - 2)!$, và cứ thế tiếp tục. Điều này là hợp lý vì, mặc dù quá trình factorial yêu cầu một số lượng không giới hạn các bản sao của cùng một máy để thực hiện phép tính, nhưng tại bất kỳ thời điểm nào chỉ cần một bản sao hoạt động. Khi máy gặp một bài toán con đệ quy, nó có thể tạm dừng công việc trên bài toán chính, tái sử dụng cùng các bộ phận vật lý để xử lý bài toán con, rồi tiếp tục phép tính đang tạm dừng.

Trong bài toán con, nội dung của các register sẽ khác so với trong bài toán chính. (Trong trường hợp này, register n bị giảm giá trị.) Để có thể tiếp tục phép tính đang tạm dừng, máy phải lưu nội dung của bất kỳ register nào sẽ cần đến sau khi bài toán con được giải, để có thể khôi phục chúng và tiếp tục phép tính đang tạm dừng. Trong trường hợp factorial, chúng ta sẽ lưu giá trị cũ của n, để khôi phục khi hoàn tất việc tính giai thừa của register n đã bị giảm giá trị.²

Vì không có giới hạn a priori về độ sâu của các lời gọi đệ quy lồng nhau, chúng ta có thể cần lưu một số lượng tùy ý các giá trị register. Các giá trị này phải được khôi phục theo thứ tự ngược lại với thứ tự đã lưu, vì trong một chuỗi đệ quy lồng nhau, bài toán con được vào sau cùng sẽ hoàn thành trước tiên. Điều này đòi hỏi sử dụng một stack (ngăn xếp), hay cấu trúc dữ liệu “vào sau, ra trước” để lưu giá trị register. Chúng ta có thể mở rộng ngôn ngữ register-machine để bao gồm stack bằng cách thêm hai loại instruction: Giá trị được đặt lên stack bằng instruction save và được khôi phục từ stack bằng instruction restore. Sau khi một chuỗi giá trị đã được save trên stack, một chuỗi restore sẽ lấy lại các giá trị này theo thứ tự ngược lại.³

Với sự hỗ trợ của stack, chúng ta có thể tái sử dụng một bản sao duy nhất của data paths của máy factorial cho mỗi bài toán con factorial. Có một vấn đề thiết kế tương tự trong việc tái sử dụng chuỗi controller điều khiển data paths. Để thực hiện lại phép tính factorial, controller không thể đơn giản quay lại đầu như với một iterative process, vì sau khi giải bài toán con $(n - 1)!$, máy vẫn phải nhân kết quả với $n$. Controller phải tạm dừng việc tính $n!$, giải bài toán con $(n - 1)!$, rồi tiếp tục việc tính $n!$. Cách nhìn này về phép tính factorial gợi ý việc sử dụng cơ chế subroutine được mô tả ở 5.1.3, trong đó controller sử dụng register continue để chuyển đến phần của chuỗi giải bài toán con, rồi tiếp tục từ nơi nó đã dừng trong bài toán chính. Do đó, chúng ta có thể tạo một subroutine factorial trả về entry point được lưu trong register continue. Xung quanh mỗi lời gọi subroutine, chúng ta lưu và khôi phục continue giống như với register n, vì mỗi “cấp” của phép tính factorial sẽ sử dụng cùng một register continue. Nghĩa là, subroutine factorial phải đặt một giá trị mới vào continue khi nó tự gọi cho một bài toán con, nhưng nó sẽ cần giá trị cũ để quay lại vị trí đã gọi nó để giải bài toán con.

Figure 5.11 cho thấy data paths và controller cho một máy triển khai procedure factorial đệ quy. Máy có một stack và ba register, gọi là n, val, và continue. Để đơn giản hóa sơ đồ data-path, chúng ta không đặt tên cho các nút gán register, chỉ đặt tên cho các nút thao tác stack (sc và sn để lưu register, rc và rn để khôi phục register). Để vận hành máy, chúng ta đặt vào register n số mà ta muốn tính giai thừa và khởi động máy. Khi máy đạt đến fact-done, phép tính hoàn tất và đáp án sẽ nằm trong register val. Trong chuỗi controller, n và continue được lưu trước mỗi lời gọi đệ quy và được khôi phục khi quay lại từ lời gọi. Việc quay lại từ một lời gọi được thực hiện bằng cách nhảy đến vị trí được lưu trong continue. Continue được khởi tạo khi máy bắt đầu để lần quay lại cuối cùng sẽ đi đến fact-done. Register val, chứa kết quả của phép tính factorial, không được lưu trước lời gọi đệ quy, vì nội dung cũ của val không còn hữu ích sau khi subroutine trả về. Chỉ giá trị mới, là giá trị được tạo ra bởi phép tính con, mới cần thiết.

Figure 5.11: A recursive factorial machine.

Mặc dù về nguyên tắc, phép tính factorial đòi hỏi một máy vô hạn, nhưng máy trong Hình 5.11 thực tế là hữu hạn, ngoại trừ stack, vốn có thể không bị giới hạn. Tuy nhiên, bất kỳ hiện thực vật lý cụ thể nào của stack cũng sẽ có kích thước hữu hạn, và điều này sẽ giới hạn độ sâu của các lời gọi đệ quy mà máy có thể xử lý. Việc triển khai factorial này minh họa chiến lược tổng quát để hiện thực hóa các thuật toán đệ quy như những register machine thông thường được bổ sung thêm stack. Khi gặp một bài toán con đệ quy, chúng ta lưu trên stack các register có giá trị hiện tại sẽ cần đến sau khi bài toán con được giải, giải quyết bài toán con đệ quy, sau đó khôi phục các register đã lưu và tiếp tục thực thi bài toán chính. Register continue luôn phải được lưu lại. Việc có cần lưu các register khác hay không phụ thuộc vào từng máy cụ thể, vì không phải mọi phép tính đệ quy đều cần giá trị gốc của các register bị thay đổi trong quá trình giải bài toán con (xem Bài tập 5.4).

A double recursion

Hãy xem xét một quá trình đệ quy phức tạp hơn — phép tính tree-recursive (đệ quy dạng cây) của các số Fibonacci, mà chúng ta đã giới thiệu ở mục 1.2.2:

(define (fib n)
  (if (< n 2) 
      n 
      (+ (fib (- n 1)) (fib (- n 2)))))

Cũng giống như với factorial, chúng ta có thể triển khai phép tính Fibonacci đệ quy như một register machine với các register n, val, và continue. Máy này phức tạp hơn máy factorial, vì có hai vị trí trong chuỗi controller mà chúng ta cần thực hiện lời gọi đệ quy — một lần để tính $\text{Fib}(n - 1)$ và một lần để tính $\text{Fib}(n - 2)$. Để chuẩn bị cho mỗi lời gọi này, chúng ta lưu các register có giá trị sẽ cần dùng sau này, đặt register n thành số mà ta cần tính Fib một cách đệ quy ($n - 1$ hoặc $n - 2$), và gán cho continue entry point trong chuỗi chính mà ta sẽ quay lại (afterfib-n-1 hoặc afterfib-n-2, tương ứng). Sau đó, ta chuyển đến fib-loop. Khi quay lại từ lời gọi đệ quy, đáp án sẽ nằm trong val. Hình 5.12 cho thấy chuỗi controller cho máy này.

Figure 5.12: $\downarrow$ Controller for a machine to compute Fibonacci numbers.

(controller (assign continue (label fib-done)) fib-loop (test (op <) (reg n) (const 2)) (branch (label immediate-answer)) ;; set up to compute Fib(n − 1) (save continue) (assign continue (label afterfib-n-1)) (save n) ; save old value of n (assign n (op -) (reg n) (const 1)) ; clobber n to n-1 (goto (label fib-loop)) ; perform recursive call afterfib-n-1 ; upon return, val contains Fib(n − 1) (restore n) (restore continue) ;; set up to compute Fib(n − 2) (assign n (op -) (reg n) (const 2)) (save continue) (assign continue (label afterfib-n-2)) (save val) ; save Fib(n − 1) (goto (label fib-loop)) afterfib-n-2 ; upon return, val contains Fib(n − 2) (assign n (reg val)) ; n now contains Fib(n − 2) (restore val) ; val now contains Fib(n − 1) (restore continue) (assign val ; Fib(n − 1) + Fib(n − 2) (op +) (reg val) (reg n)) (goto ; return to caller, (reg continue)) ; answer is in val immediate-answer (assign val (reg n)) ; base case: Fib(n) = n (goto (reg continue)) fib-done)