기계는 컨트롤러가 수행한 일을 직접 보고할 수 있다.
명시적인 레지스터 기계 실행기는 결과와 마지막 스택 상태를 보존하면서 가져온 명령 수와 전체 push 수와 최대 스택 깊이를 셀 수 있습니다.
마지막 레지스터 값만으로는 알 수 없는 어떤 일을 컨트롤러 수준 계수기가 보여 줄까요?
- 명시적인 규약으로 가져온 모든 명령 세기
- 전체 save 수와 현재 스택 깊이 구분하기
- restore 뒤에도 최대 스택 깊이 보존하기
- 같은 factorial 컨트롤러의 기본 경로와 재귀 경로 비교하기
- 컨트롤러 계측값과 실제 시간·하드웨어 프로파일링 구분하기
The controller is the same finite recursive factorial machine for every run. Its explicit register vector holds n, val, continue, flag, and pc. A separate list represents the stack. The executor increments instruction-count as soon as it fetches an instruction, including halt. push! increments total-pushes and updates max-depth from the current list length; pop! shortens the live stack but does not erase the historical push count.
With n equal to 1, the branch jumps directly to the base assignment and reaches halt after five fetched instructions with no stack use. With n equal to 3, the controller saves continue and n at two recursive levels, so it performs four pushes, reaches depth four, and fetches 27 instructions before halting with value 6 and an empty stack. These numbers describe this exact controller, input, and counting convention. They are not elapsed time, CPU instructions, allocation cost, or a general profiler.
(begin
(define controller
(vector
'(test base? n)
'(branch 11)
'(save continue)
'(save n)
'(assign n sub1 n)
'(assign continue constant 7)
'(goto 0)
'(restore n)
'(restore continue)
'(assign val multiply n val)
'(goto-register continue)
'(assign val constant 1)
'(goto-register continue)
'(halt)))
(define (register-index name)
(cond ((eq? name 'n) 0)
((eq? name 'val) 1)
((eq? name 'continue) 2)
((eq? name 'flag) 3)
((eq? name 'pc) 4)))
(define (run-factorial start)
(let ((registers (vector start 0 13 #f 0))
(stack '())
(instruction-count 0)
(total-pushes 0)
(max-depth 0))
(define (get-register name)
(vector-ref registers (register-index name)))
(define (set-register! name value)
(vector-set! registers (register-index name) value))
(define (advance!)
(set-register! 'pc (+ (get-register 'pc) 1)))
(define (push! value)
(set! stack (cons value stack))
(set! total-pushes (+ total-pushes 1))
(set! max-depth (max max-depth (length stack))))
(define (pop!)
(let ((value (car stack)))
(set! stack (cdr stack))
value))
(define (assign-value instruction)
(let ((operation (caddr instruction)))
(cond ((eq? operation 'constant)
(cadddr instruction))
((eq? operation 'sub1)
(- (get-register (cadddr instruction)) 1))
((eq? operation 'multiply)
(* (get-register (cadddr instruction))
(get-register (list-ref instruction 4)))))))
(define (execute remaining-steps)
(if (= remaining-steps 0)
'step-limit
(let* ((instruction
(vector-ref controller (get-register 'pc)))
(operation (car instruction)))
(set! instruction-count (+ instruction-count 1))
(cond
((eq? operation 'halt)
(list (get-register 'val)
instruction-count
total-pushes
max-depth
(length stack)))
((eq? operation 'test)
(set-register!
'flag
(= (get-register (caddr instruction)) 1))
(advance!)
(execute (- remaining-steps 1)))
((eq? operation 'branch)
(set-register!
'pc
(if (get-register 'flag)
(cadr instruction)
(+ (get-register 'pc) 1)))
(execute (- remaining-steps 1)))
((eq? operation 'save)
(push! (get-register (cadr instruction)))
(advance!)
(execute (- remaining-steps 1)))
((eq? operation 'restore)
(set-register! (cadr instruction) (pop!))
(advance!)
(execute (- remaining-steps 1)))
((eq? operation 'assign)
(set-register! (cadr instruction)
(assign-value instruction))
(advance!)
(execute (- remaining-steps 1)))
((eq? operation 'goto)
(set-register! 'pc (cadr instruction))
(execute (- remaining-steps 1)))
((eq? operation 'goto-register)
(set-register! 'pc
(get-register (cadr instruction)))
(execute (- remaining-steps 1)))))))
(execute 200)))
; value, fetched instructions, pushes, max depth, final depth
(run-factorial 3))- 출력
- —
- 값
- —
- 진단
- —
The first program returns (6 27 4 4 0). The second returns ((1 1 5 0 0) (2 2 16 2 2) (4 24 38 6 6)).
Follow instruction-count immediately after each vector fetch, including halt. Compare each save with a push increment and a possible max-depth update, then watch restore shorten the current stack without reducing total-pushes. The base path jumps directly to instruction 11, while each additional recursive level contributes two saves and later two restores.
힌트를 보기 전에 프로그램을 바꿔 보세요.
Predict the report for input 3 without running it. Then change the counting convention so halt is not included and explain exactly which field changes.
힌트 하나 보기
Input 3 creates two recursive levels. Each level pushes continue and n. Excluding halt subtracts one only from the fetched-instruction count.