5.2 Trình mô phỏng Register-Machine
Để có được sự hiểu biết tốt về thiết kế của các register machine (máy thanh ghi), chúng ta phải kiểm tra các máy mà mình thiết kế để xem chúng có hoạt động như mong đợi hay không. Một cách để kiểm tra thiết kế là mô phỏng thủ công hoạt động của controller (bộ điều khiển), như trong Bài tập 5.5. Tuy nhiên, điều này cực kỳ tẻ nhạt đối với tất cả trừ những máy đơn giản nhất. Trong phần này, chúng ta sẽ xây dựng một trình mô phỏng cho các máy được mô tả bằng ngôn ngữ register-machine. Trình mô phỏng này là một chương trình Scheme với bốn procedure (thủ tục) giao diện. Procedure đầu tiên sử dụng mô tả của một register machine để xây dựng một mô hình của máy (một cấu trúc dữ liệu mà các thành phần của nó tương ứng với các thành phần của máy cần mô phỏng), và ba procedure còn lại cho phép chúng ta mô phỏng máy bằng cách thao tác trên mô hình:
(make-machine ⟨register-names⟩ ⟨operations⟩ ⟨controller⟩)tạo và trả về một mô hình của máy với các register, operation và controller đã cho.
(set-register-contents! ⟨machine-model⟩ ⟨register-name⟩ ⟨value⟩)
> lưu một giá trị vào một register được mô phỏng trong máy đã cho. > ``` {.scheme} (get-register-contents ⟨machine-model⟩ ⟨register-name⟩)trả về nội dung của một register được mô phỏng trong máy đã cho.
(start ⟨machine-model⟩)
> mô phỏng việc thực thi của máy đã cho, bắt đầu từ đầu chuỗi lệnh của controller và dừng lại khi đến cuối chuỗi.
Ví dụ về cách sử dụng các procedure này, chúng ta có thể định nghĩa gcd-machine là một mô hình của máy GCD trong 5.1.1 như sau:
(define gcd-machine
(make-machine
'(a b t)
(list (list 'rem remainder) (list '= =))
'(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)))
Đối số đầu tiên của make-machine là một danh sách các tên register. Đối số tiếp theo là một bảng (danh sách các danh sách hai phần tử) ghép mỗi tên operation với một procedure Scheme thực hiện operation đó (nghĩa là, tạo ra cùng giá trị đầu ra khi nhận cùng giá trị đầu vào). Đối số cuối cùng chỉ định controller dưới dạng một danh sách các nhãn và lệnh máy, như trong 5.1.
Để tính GCD với máy này, chúng ta đặt các register đầu vào, khởi động máy, và kiểm tra kết quả khi mô phỏng kết thúc:
(set-register-contents! gcd-machine 'a 206)
done
(set-register-contents! gcd-machine 'b 40)
done
(start gcd-machine)
done
(get-register-contents gcd-machine 'a)
2
Việc tính toán này sẽ chạy chậm hơn nhiều so với một procedure gcd viết bằng Scheme, bởi vì chúng ta sẽ mô phỏng các lệnh máy mức thấp, chẳng hạn như assign, bằng những thao tác phức tạp hơn nhiều.
5.2.1 Mô hình máy
Mô hình máy được tạo bởi make-machine được biểu diễn dưới dạng một procedure với trạng thái cục bộ, sử dụng kỹ thuật message-passing (truyền thông điệp) được phát triển trong Chương 3. Để xây dựng mô hình này, make-machine bắt đầu bằng cách gọi procedure make-new-machine để tạo ra các thành phần của mô hình máy chung cho tất cả các register machine. Mô hình máy cơ bản này, được tạo bởi make-new-machine, về cơ bản là một bộ chứa cho một số register và một stack, cùng với một cơ chế thực thi xử lý các lệnh của controller từng cái một.
Make-machine sau đó mở rộng mô hình cơ bản này (bằng cách gửi thông điệp cho nó) để bao gồm các register, operation và controller của máy cụ thể đang được định nghĩa. Trước tiên, nó cấp phát một register trong máy mới cho mỗi tên register được cung cấp và cài đặt các operation đã chỉ định vào máy. Sau đó, nó sử dụng một assembler (bộ hợp dịch) (được mô tả bên dưới trong 5.2.2) để biến đổi danh sách controller thành các lệnh cho máy mới và cài đặt chúng như chuỗi lệnh của máy. Make-machine trả về mô hình máy đã được chỉnh sửa này như giá trị của nó.
(define (make-machine register-names
ops
controller-text)
(let ((machine (make-new-machine)))
(for-each (lambda (register-name)
((machine 'allocate-register)
register-name))
register-names)
((machine 'install-operations) ops)
((machine 'install-instruction-sequence)
(assemble controller-text machine))
machine))
Registers
Chúng ta sẽ biểu diễn một register như một procedure với trạng thái cục bộ, như trong Chương 3. Procedure make-register tạo ra một register giữ một giá trị có thể được truy cập hoặc thay đổi:
(define (make-register name)
(let ((contents '*unassigned*))
(define (dispatch message)
(cond ((eq? message 'get) contents)
((eq? message 'set)
(lambda (value)
(set! contents value)))
(else
(error "Unknown request:
REGISTER"
message))))
dispatch))
Các procedure sau được dùng để truy cập register:
(define (get-contents register)
(register 'get))
(define (set-contents! register value)
((register 'set) value))
Stack
Chúng ta cũng có thể biểu diễn một stack như một procedure với trạng thái cục bộ. Procedure make-stack tạo ra một stack có trạng thái cục bộ là một danh sách các phần tử trên stack. Một stack chấp nhận các yêu cầu push một phần tử vào stack, pop phần tử trên cùng ra khỏi stack và trả về nó, và initialize stack về rỗng.
(define (make-stack)
(let ((s '()))
(define (push x)
(set! s (cons x s)))
(define (pop)
(if (null? s)
(error "Empty stack: POP")
(let ((top (car s)))
(set! s (cdr s))
top)))
(define (initialize)
(set! s '())
'done)
(define (dispatch message)
(cond ((eq? message 'push) push)
((eq? message 'pop) (pop))
((eq? message 'initialize)
(initialize))
(else
(error "Unknown request: STACK"
message))))
dispatch))
Các procedure sau được dùng để truy cập stack:
(define (pop stack) (stack 'pop))
(define (push stack value)
((stack 'push) value))
Máy cơ bản
Procedure (thủ tục) make-new-machine, được minh họa trong Hình 5.13, tạo ra một đối tượng có trạng thái cục bộ bao gồm một stack, một instruction sequence (chuỗi lệnh) ban đầu rỗng, một danh sách các operation ban đầu chứa một operation để khởi tạo stack, và một register table (bảng thanh ghi) ban đầu chứa hai register, tên là flag và pc (viết tắt của “program counter” – bộ đếm chương trình). Procedure nội bộ allocate-register thêm các mục mới vào register table, và procedure nội bộ lookup-register tra cứu các register trong bảng.
Figure 5.13: $\downarrow$ The make-new-machine procedure, which implements the basic machine model.
(define (make-new-machine)
(let ((pc (make-register 'pc))
(flag (make-register 'flag))
(stack (make-stack))
(the-instruction-sequence '()))
(let ((the-ops
(list
(list 'initialize-stack
(lambda ()
(stack 'initialize)))))
(register-table
(list (list 'pc pc)
(list 'flag flag))))
(define (allocate-register name)
(if (assoc name register-table)
(error
"Multiply defined register: "
name)
(set! register-table
(cons
(list name
(make-register name))
register-table)))
'register-allocated)
(define (lookup-register name)
(let ((val
(assoc name register-table)))
(if val
(cadr val)
(error "Unknown register:"
name))))
(define (execute)
(let ((insts (get-contents pc)))
(if (null? insts)
'done
(begin
((instruction-execution-proc
(car insts)))
(execute)))))
(define (dispatch message)
(cond ((eq? message 'start)
(set-contents!
pc
the-instruction-sequence)
(execute))
((eq?
message
'install-instruction-sequence)
(lambda (seq)
(set!
the-instruction-sequence
seq)))
((eq? message
'allocate-register)
allocate-register)
((eq? message 'get-register)
lookup-register)
((eq? message
'install-operations)
(lambda (ops)
(set! the-ops
(append the-ops ops))))
((eq? message 'stack) stack)
((eq? message 'operations)
the-ops)
(else (error "Unknown request:
MACHINE"
message))))
dispatch)))
Register flag được dùng để điều khiển việc rẽ nhánh trong máy mô phỏng. Các lệnh test đặt nội dung của flag thành kết quả của phép kiểm tra (đúng hoặc sai). Các lệnh branch quyết định có rẽ nhánh hay không bằng cách kiểm tra nội dung của flag.
Register pc quyết định trình tự thực thi các lệnh khi máy chạy. Trình tự này được thực hiện bởi procedure nội bộ execute. Trong mô hình mô phỏng, mỗi lệnh máy là một cấu trúc dữ liệu bao gồm một procedure không có đối số, gọi là instruction execution procedure (thủ tục thực thi lệnh), sao cho việc gọi procedure này sẽ mô phỏng việc thực thi lệnh. Khi mô phỏng chạy, pc trỏ đến vị trí trong instruction sequence bắt đầu từ lệnh tiếp theo cần thực thi. Execute lấy lệnh đó, thực thi nó bằng cách gọi instruction execution procedure, và lặp lại chu trình này cho đến khi không còn lệnh nào để thực thi (tức là khi pc trỏ đến cuối instruction sequence).
Trong quá trình hoạt động, mỗi instruction execution procedure sẽ thay đổi pc để chỉ ra lệnh tiếp theo cần thực thi. Các lệnh branch và goto thay đổi pc để trỏ đến đích mới. Tất cả các lệnh khác chỉ đơn giản tiến pc đến lệnh tiếp theo trong chuỗi. Lưu ý rằng mỗi lần gọi execute lại gọi execute một lần nữa, nhưng điều này không tạo ra vòng lặp vô hạn vì việc chạy instruction execution procedure sẽ thay đổi nội dung của pc.
Make-new-machine trả về một procedure dispatch thực hiện việc truy cập trạng thái nội bộ thông qua message-passing (truyền thông điệp). Lưu ý rằng việc khởi động máy được thực hiện bằng cách đặt pc về đầu của instruction sequence và gọi execute.
Để thuận tiện, chúng tôi cung cấp một giao diện procedural thay thế cho operation start của máy, cũng như các procedure để đặt và kiểm tra nội dung register, như đã nêu ở đầu mục 5.2:
(define (start machine)
(machine 'start))
(define (get-register-contents
machine register-name)
(get-contents
(get-register machine register-name)))
(define (set-register-contents!
machine register-name value)
(set-contents!
(get-register machine register-name)
value)
'done)
Các procedure này (và nhiều procedure trong 5.2.2 và 5.2.3) sử dụng đoạn sau để tra cứu register với tên đã cho trong một máy đã cho:
(define (get-register machine reg-name)
((machine 'get-register) reg-name))
5.2.2 Bộ hợp dịch (Assembler)
Assembler biến đổi chuỗi các biểu thức controller của một máy thành một danh sách tương ứng các lệnh máy, mỗi lệnh có execution procedure của riêng nó. Nhìn tổng thể, assembler khá giống với các evaluator mà chúng ta đã nghiên cứu trong Chương 4 — có một ngôn ngữ đầu vào (trong trường hợp này là register-machine language) và chúng ta phải thực hiện hành động thích hợp cho từng loại biểu thức trong ngôn ngữ đó.
Kỹ thuật tạo ra một execution procedure cho mỗi lệnh chính là kỹ thuật chúng ta đã dùng trong 4.1.7 để tăng tốc evaluator bằng cách tách biệt phân tích và thực thi tại thời gian chạy. Như chúng ta đã thấy trong Chương 4, nhiều phân tích hữu ích của các biểu thức Scheme có thể được thực hiện mà không cần biết giá trị thực của các biến. Ở đây, tương tự, nhiều phân tích hữu ích của các biểu thức register-machine language có thể được thực hiện mà không cần biết nội dung thực của các register trong máy. Ví dụ, chúng ta có thể thay thế các tham chiếu đến register bằng các con trỏ đến đối tượng register, và có thể thay thế các tham chiếu đến label bằng các con trỏ đến vị trí trong instruction sequence mà label đó chỉ định.
Trước khi có thể tạo ra các instruction execution procedure, assembler phải biết tất cả các label tham chiếu đến đâu, vì vậy nó bắt đầu bằng cách quét controller text để tách các label ra khỏi các lệnh. Khi quét văn bản, nó đồng thời xây dựng một danh sách các lệnh và một bảng liên kết mỗi label với một con trỏ vào danh sách đó. Sau đó assembler bổ sung danh sách lệnh bằng cách chèn execution procedure cho mỗi lệnh.
Procedure assemble là điểm vào chính của assembler. Nó nhận controller text và mô hình máy làm đối số, và trả về instruction sequence để lưu vào mô hình. Assemble gọi extract-labels để xây dựng danh sách lệnh ban đầu và bảng label từ controller text được cung cấp. Đối số thứ hai của extract-labels là một procedure sẽ được gọi để xử lý các kết quả này: Procedure này sử dụng update-insts! để tạo ra các instruction execution procedure và chèn chúng vào danh sách lệnh, rồi trả về danh sách đã được chỉnh sửa.
(define (assemble controller-text machine)
(extract-labels controller-text
(lambda (insts labels)
(update-insts! insts labels machine)
insts)))
Extract-labels nhận vào một danh sách text (chuỗi các biểu thức lệnh controller) và một procedure receive. Receive sẽ được gọi với hai giá trị: (1) một danh sách insts gồm các cấu trúc dữ liệu lệnh, mỗi cấu trúc chứa một lệnh từ text; và (2) một bảng gọi là labels, liên kết mỗi label từ text với vị trí trong danh sách insts mà label đó chỉ định.
(define (extract-labels text receive)
(if (null? text)
(receive '() '())
(extract-labels
(cdr text)
(lambda (insts labels)
(let ((next-inst (car text)))
(if (symbol? next-inst)
(receive
insts
(cons
(make-label-entry
next-inst
insts)
labels))
(receive
(cons (make-instruction
next-inst)
insts)
labels)))))))
Extract-labels hoạt động bằng cách quét tuần tự các phần tử của text và tích lũy insts và labels. Nếu một phần tử là một symbol (và do đó là một label) thì một mục thích hợp sẽ được thêm vào bảng labels. Nếu không, phần tử đó sẽ được thêm vào danh sách insts1.
Update-insts! chỉnh sửa danh sách lệnh, vốn ban đầu chỉ chứa phần văn bản của các lệnh, để bao gồm cả execution procedure tương ứng:
(define (update-insts! insts labels machine)
(let ((pc (get-register machine 'pc))
(flag (get-register machine 'flag))
(stack (machine 'stack))
(ops (machine 'operations)))
(for-each
(lambda (inst)
(set-instruction-execution-proc!
inst
(make-execution-procedure
(instruction-text inst)
labels
machine
pc
flag
stack
ops)))
insts)))
Cấu trúc dữ liệu lệnh máy đơn giản chỉ là cặp giữa phần văn bản lệnh và execution procedure tương ứng. Execution procedure chưa có sẵn khi extract-labels tạo lệnh, và sẽ được chèn vào sau bởi update-insts!.
(define (make-instruction text)
(cons text '()))
(define (instruction-text inst) (car inst))
(define (instruction-execution-proc inst)
(cdr inst))
(define (set-instruction-execution-proc!
inst
proc)
(set-cdr! inst proc))
Phần văn bản lệnh không được sử dụng bởi trình mô phỏng của chúng ta, nhưng giữ lại nó sẽ hữu ích cho việc gỡ lỗi (xem Bài tập 5.16).
Các phần tử của bảng label là các cặp:
(define (make-label-entry label-name insts)
(cons label-name insts))
Các mục sẽ được tra cứu trong bảng bằng:
(define (lookup-label labels label-name)
(let ((val (assoc label-name labels)))
(if val
(cdr val)
(error "Undefined label: ASSEMBLE"
label-name))))
5.2.3 Sinh Execution Procedure cho các lệnh
Assembler gọi make-execution-procedure để sinh execution procedure (thủ tục thực thi) cho một lệnh. Giống như procedure analyze trong evaluator ở mục 4.1.7, procedure này phân nhánh (dispatch) dựa trên loại lệnh để tạo ra execution procedure thích hợp.
(define (make-execution-procedure
inst labels machine pc flag stack ops)
(cond ((eq? (car inst) 'assign)
(make-assign
inst machine labels ops pc))
((eq? (car inst) 'test)
(make-test
inst machine labels ops flag pc))
((eq? (car inst) 'branch)
(make-branch
inst machine labels flag pc))
((eq? (car inst) 'goto)
(make-goto inst machine labels pc))
((eq? (car inst) 'save)
(make-save inst machine stack pc))
((eq? (car inst) 'restore)
(make-restore inst machine stack pc))
((eq? (car inst) 'perform)
(make-perform
inst machine labels ops pc))
(else (error "Unknown instruction
type: ASSEMBLE"
inst))))
Với mỗi loại lệnh trong register-machine language, có một generator (bộ sinh) tạo ra execution procedure phù hợp. Chi tiết của các procedure này quyết định cả cú pháp và ngữ nghĩa của từng lệnh riêng lẻ trong register-machine language. Chúng ta sử dụng data abstraction (trừu tượng hóa dữ liệu) để tách biệt cú pháp chi tiết của các biểu thức register-machine khỏi cơ chế thực thi tổng quát, giống như cách chúng ta đã làm với evaluator trong 4.1.2, bằng cách sử dụng các syntax procedure để trích xuất và phân loại các thành phần của một lệnh.
Lệnh Assign
Procedure make-assign xử lý các lệnh assign:
(define (make-assign
inst machine labels operations pc)
(let ((target
(get-register
machine
(assign-reg-name inst)))
(value-exp (assign-value-exp inst)))
(let ((value-proc
(if (operation-exp? value-exp)
(make-operation-exp
value-exp
machine
labels
operations)
(make-primitive-exp
(car value-exp)
machine
labels))))
(lambda () ; execution procedure
; for assign
(set-contents! target (value-proc))
(advance-pc pc)))))
Make-assign trích xuất tên register đích (phần tử thứ hai của lệnh) và value expression (biểu thức giá trị – phần còn lại của danh sách tạo thành lệnh) từ lệnh assign bằng cách sử dụng các selector:
(define (assign-reg-name assign-instruction)
(cadr assign-instruction))
(define (assign-value-exp assign-instruction)
(cddr assign-instruction))
Tên register được tra cứu bằng get-register để tạo ra đối tượng register đích. Value expression được truyền cho make-operation-exp nếu giá trị là kết quả của một operation, và cho make-primitive-exp nếu không phải. Các procedure này (được trình bày bên dưới) phân tích value expression và tạo ra một execution procedure cho giá trị đó. Đây là một procedure không có đối số, gọi là value-proc, sẽ được thực thi trong quá trình mô phỏng để tạo ra giá trị thực tế cần gán cho register. Lưu ý rằng công việc tra cứu tên register và phân tích value expression chỉ được thực hiện một lần tại thời điểm assembly, chứ không phải mỗi lần lệnh được mô phỏng. Việc tiết kiệm công việc này là lý do chúng ta sử dụng execution procedure, và điều này tương ứng trực tiếp với việc tiết kiệm công việc mà chúng ta đạt được khi tách biệt phân tích chương trình khỏi thực thi trong evaluator ở 4.1.7.
Kết quả trả về từ make-assign là execution procedure cho lệnh assign. Khi procedure này được gọi (bởi procedure execute của mô hình máy), nó sẽ đặt nội dung của register đích thành kết quả thu được từ việc thực thi value-proc. Sau đó, nó tiến pc đến lệnh tiếp theo bằng cách chạy procedure:
(define (advance-pc pc)
(set-contents! pc (cdr (get-contents pc))))
Advance-pc là cách kết thúc bình thường cho tất cả các lệnh ngoại trừ branch và goto.
Lệnh Test, branch, và goto
Make-test xử lý các lệnh test theo cách tương tự. Nó trích xuất biểu thức chỉ định điều kiện cần kiểm tra và tạo ra execution procedure cho điều kiện đó. Tại thời điểm mô phỏng, procedure cho điều kiện được gọi, kết quả được gán vào register flag, và pc được tiến:
(define
(make-test
inst machine labels operations flag pc)
(let ((condition (test-condition inst)))
(if (operation-exp? condition)
(let ((condition-proc
(make-operation-exp
condition
machine
labels
operations)))
(lambda ()
(set-contents!
flag (condition-proc))
(advance-pc pc)))
(error "Bad TEST instruction:
ASSEMBLE" inst))))
(define (test-condition test-instruction)
(cdr test-instruction))
Execution procedure cho một lệnh branch kiểm tra nội dung của register flag và hoặc là đặt nội dung của pc thành đích rẽ nhánh (nếu rẽ nhánh được thực hiện) hoặc chỉ tiến pc (nếu không rẽ nhánh). Lưu ý rằng đích được chỉ định trong một lệnh branch phải là một label, và procedure make-branch đảm bảo điều này. Cũng lưu ý rằng label được tra cứu tại thời điểm assembly, chứ không phải mỗi lần lệnh branch được mô phỏng.
(define
(make-branch
inst machine labels flag pc)
(let ((dest (branch-dest inst)))
(if (label-exp? dest)
(let ((insts
(lookup-label
labels
(label-exp-label dest))))
(lambda ()
(if (get-contents flag)
(set-contents! pc insts)
(advance-pc pc))))
(error "Bad BRANCH instruction:
ASSEMBLE"
inst))))
(define (branch-dest branch-instruction)
(cadr branch-instruction))
Một lệnh goto tương tự như branch, ngoại trừ việc đích đến có thể được chỉ định hoặc là một label hoặc là một register, và không có điều kiện nào cần kiểm tra — pc luôn được đặt đến đích mới.
(define (make-goto inst machine labels pc)
(let ((dest (goto-dest inst)))
(cond ((label-exp? dest)
(let ((insts
(lookup-label
labels
(label-exp-label dest))))
(lambda ()
(set-contents! pc insts))))
((register-exp? dest)
(let ((reg
(get-register
machine
(register-exp-reg dest))))
(lambda ()
(set-contents!
pc
(get-contents reg)))))
(else (error "Bad GOTO instruction:
ASSEMBLE"
inst)))))
(define (goto-dest goto-instruction)
(cadr goto-instruction))
Các lệnh khác
Các lệnh stack save và restore đơn giản là sử dụng stack với register được chỉ định và tiến pc:
(define (make-save inst machine stack pc)
(let ((reg (get-register
machine
(stack-inst-reg-name inst))))
(lambda ()
(push stack (get-contents reg))
(advance-pc pc))))
(define (make-restore inst machine stack pc)
(let ((reg (get-register
machine
(stack-inst-reg-name inst))))
(lambda ()
(set-contents! reg (pop stack))
(advance-pc pc))))
(define (stack-inst-reg-name
stack-instruction)
(cadr stack-instruction))
Loại lệnh cuối cùng, được xử lý bởi make-perform, tạo ra một execution procedure cho hành động cần thực hiện. Tại thời điểm mô phỏng, action procedure được thực thi và pc được tiến.
(define (make-perform
inst machine labels operations pc)
(let ((action (perform-action inst)))
(if (operation-exp? action)
(let ((action-proc
(make-operation-exp
action
machine
labels
operations)))
(lambda ()
(action-proc)
(advance-pc pc)))
(error "Bad PERFORM instruction:
ASSEMBLE"
inst))))
(define (perform-action inst) (cdr inst))
Execution procedure cho các biểu thức con
Giá trị của một biểu thức reg, label, hoặc const có thể cần thiết để gán vào một register (make-assign) hoặc để làm đầu vào cho một operation (make-operation-exp, bên dưới). Procedure sau đây tạo ra execution procedure để sinh giá trị cho các biểu thức này trong quá trình mô phỏng:
(define (make-primitive-exp exp machine labels)
(cond ((constant-exp? exp)
(let ((c (constant-exp-value exp)))
(lambda () c)))
((label-exp? exp)
(let ((insts
(lookup-label
labels
(label-exp-label exp))))
(lambda () insts)))
((register-exp? exp)
(let ((r (get-register
machine
(register-exp-reg exp))))
(lambda () (get-contents r))))
(else (error "Unknown expression type:
ASSEMBLE"
exp))))
Cú pháp của các biểu thức reg, label, và const được xác định bởi:
(define (register-exp? exp)
(tagged-list? exp 'reg))
(define (register-exp-reg exp)
(cadr exp))
(define (constant-exp? exp)
(tagged-list? exp 'const))
(define (constant-exp-value exp)
(cadr exp))
(define (label-exp? exp)
(tagged-list? exp 'label))
(define (label-exp-label exp)
(cadr exp))
Các lệnh assign, perform, và test có thể bao gồm việc áp dụng một machine operation (được chỉ định bởi một biểu thức op) lên một số toán hạng (được chỉ định bởi các biểu thức reg và const). Procedure sau đây tạo ra một execution procedure cho một “operation expression” — một danh sách chứa operation và các biểu thức toán hạng từ lệnh:
(define (make-operation-exp
exp machine labels operations)
(let ((op (lookup-prim
(operation-exp-op exp)
operations))
(aprocs
(map (lambda (e)
(make-primitive-exp
e machine labels))
(operation-exp-operands exp))))
(lambda () (apply op (map (lambda (p) (p))
aprocs)))))
Cú pháp của operation expression được xác định bởi:
(define (operation-exp? exp)
(and (pair? exp)
(tagged-list? (car exp) 'op)))
(define (operation-exp-op operation-exp)
(cadr (car operation-exp)))
(define (operation-exp-operands operation-exp)
(cdr operation-exp))
Lưu ý rằng cách xử lý operation expression rất giống với cách xử lý procedure application bởi procedure analyze-application trong evaluator ở 4.1.7, ở chỗ chúng ta tạo ra một execution procedure cho mỗi toán hạng. Tại thời điểm mô phỏng, chúng ta gọi các operand procedure và áp dụng procedure Scheme mô phỏng operation lên các giá trị thu được. Procedure mô phỏng được tìm bằng cách tra cứu tên operation trong operation table của máy:
(define (lookup-prim symbol operations)
(let ((val (assoc symbol operations)))
(if val
(cadr val)
(error "Unknown operation: ASSEMBLE"
symbol))))
5.2.4 Giám sát hiệu năng của máy
Simulation (mô phỏng) hữu ích không chỉ để kiểm tra tính đúng đắn của một thiết kế máy được đề xuất mà còn để đo lường hiệu năng của máy. Ví dụ, chúng ta có thể cài đặt trong chương trình mô phỏng của mình một “meter” (bộ đo) để đếm số lượng thao tác stack được sử dụng trong một phép tính.
Để làm điều này, chúng ta chỉnh sửa stack mô phỏng để theo dõi số lần các register được lưu (saved) vào stack và độ sâu tối đa mà stack đạt được, đồng thời thêm một thông điệp vào interface của stack để in ra các thống kê, như minh họa bên dưới.
Chúng ta cũng thêm một operation vào mô hình máy cơ bản để in thống kê stack, bằng cách khởi tạo the-ops trong make-new-machine như sau:
(list (list 'initialize-stack
(lambda ()
(stack 'initialize)))
(list 'print-stack-statistics
(lambda ()
(stack 'print-statistics))))
Dưới đây là phiên bản mới của make-stack:
(define (make-stack)
(let ((s '())
(number-pushes 0)
(max-depth 0)
(current-depth 0))
(define (push x)
(set! s (cons x s))
(set! number-pushes (+ 1 number-pushes))
(set! current-depth (+ 1 current-depth))
(set! max-depth
(max current-depth max-depth)))
(define (pop)
(if (null? s)
(error "Empty stack: POP")
(let ((top (car s)))
(set! s (cdr s))
(set! current-depth
(- current-depth 1))
top)))
(define (initialize)
(set! s '())
(set! number-pushes 0)
(set! max-depth 0)
(set! current-depth 0)
'done)
(define (print-statistics)
(newline)
(display (list 'total-pushes
'=
number-pushes
'maximum-depth
'=
max-depth)))
(define (dispatch message)
(cond ((eq? message 'push) push)
((eq? message 'pop) (pop))
((eq? message 'initialize)
(initialize))
((eq? message 'print-statistics)
(print-statistics))
(else
(error "Unknown request: STACK"
message))))
dispatch))
... Chưa dịch