컨트롤러 구간 하나가 여러 호출자로 돌아갈 수 있다.
공유 기계 서브루틴은 continue 레지스터로 복귀 주소를 받습니다. 서브루틴이 다른 서브루틴을 부를 때는 이전 continuation을 저장하고 복원해 원래 호출자를 보존합니다.
레지스터 기계는 명령을 복사하지 않고 공유하거나 중첩한 서브루틴에서 어떻게 돌아올까요?
- 호출자마다 다른 복귀 주소를 continue 레지스터에 저장하기
- 두 호출 지점에서 같은 컨트롤러 구간으로 이동하기
- 고정 레이블 대신 goto-register로 복귀하기
- 중첩 서브루틴 호출 전에 바깥 continuation 저장하기
- 첫 호출자로 돌아가기 전에 원래 continuation 복원하기
첫 컨트롤러는 double 서브루틴 하나를 두 번 부릅니다. 각 goto 전에 호출자는 다른 pc 값을 continue에 씁니다. 공유 서브루틴은 val을 바꾸고 goto-register continue를 실행하므로 같은 두 명령이 첫 번째에는 왼쪽 결과를 저장하는 곳으로, 두 번째에는 두 배 값을 더하는 곳으로 돌아갑니다. 기록된 pc 경로에는 9번과 10번 명령이 복사 없이 두 번 나타납니다.
두 번째 컨트롤러는 double-then-add-one 서브루틴을 부르고 그 서브루틴이 다시 double을 부릅니다. 안쪽 호출도 continue를 써야 하므로 바깥 서브루틴은 원래 호출자의 값을 먼저 저장합니다. double이 돌아오면 restore로 원래 주소를 복원하고 add1을 끝낸 뒤 main으로 복귀합니다. 이 유한 실행기는 명시적인 연결과 스택 한 칸을 모형화할 뿐 일반 조립기나 호출 규약 또는 하드웨어 서브루틴의 증명은 아닙니다.
(begin
(define controller
(vector
'(assign val constant 3)
'(assign continue constant 3)
'(goto 9)
'(assign left copy val)
'(assign val constant 5)
'(assign continue constant 7)
'(goto 9)
'(assign result add left val)
'(halt)
'(assign val double val)
'(goto-register continue)))
(define (register-index name)
(cond ((eq? name 'val) 0)
((eq? name 'left) 1)
((eq? name 'result) 2)
((eq? name 'continue) 3)
((eq? name 'pc) 4)))
(define (run-machine)
(let ((registers (vector 0 0 0 0 0))
(path '())
(return-addresses '()))
(define (get name)
(vector-ref registers (register-index name)))
(define (put! name value)
(vector-set! registers (register-index name) value))
(define (advance!) (put! 'pc (+ (get 'pc) 1)))
(define (assignment instruction)
(let ((operation (caddr instruction)))
(cond ((eq? operation 'constant)
(cadddr instruction))
((eq? operation 'copy)
(get (cadddr instruction)))
((eq? operation 'double)
(* 2 (get (cadddr instruction))))
((eq? operation 'add)
(+ (get (cadddr instruction))
(get (list-ref instruction 4)))))))
(define (execute remaining-steps)
(if (= remaining-steps 0)
'step-limit
(let* ((pc (get 'pc))
(instruction (vector-ref controller pc))
(operation (car instruction)))
(set! path (cons pc path))
(cond
((eq? operation 'halt)
(list (get 'result)
(reverse return-addresses)
(reverse path)))
((eq? operation 'assign)
(let ((target (cadr instruction))
(value (assignment instruction)))
(put! target value)
(if (eq? target 'continue)
(set! return-addresses
(cons value return-addresses)))
(advance!)
(execute (- remaining-steps 1))))
((eq? operation 'goto)
(put! 'pc (cadr instruction))
(execute (- remaining-steps 1)))
((eq? operation 'goto-register)
(put! 'pc (get (cadr instruction)))
(execute (- remaining-steps 1)))))))
(execute 100)))
(run-machine))- 출력
- —
- 값
- —
- 진단
- —
공유 서브루틴 프로그램은 (16 (3 7) (0 1 2 9 10 3 4 5 6 9 10 7 8))을 반환합니다. 중첩 호출 프로그램은 (9 1 0 (3 8) (0 1 2 5 6 7 11 12 8 9 10 3 4))를 반환합니다.
첫 실행에서는 continue에 값을 쓰는 두 곳과 같은 서브루틴 pc로 가는 두 이동, 서로 다른 호출자로 돌아오는 goto-register를 찾으세요. 두 번째 실행에서는 중첩 continue 대입 전 save, 안쪽 pc 8 복귀, 원래 pc 3 복원, main으로 돌아오는 마지막 이동을 따라가세요.
힌트를 보기 전에 프로그램을 바꿔 보세요.
7을 두 배로 만드는 세 번째 호출자를 추가하고 마지막 합에 포함하세요. 실행하기 전에 새 복귀 주소와 pc 경로를 예상하세요.
힌트 하나 보기
공유 서브루틴은 계속 pc 9에서 시작합니다. 새 호출자는 goto 바로 다음에 자기 후속 명령을 두고 그 pc를 continue에 써야 합니다.