5.1.6 · 명령 요약

각 명령에는 데이터와 스택과 제어에 대한 명시적인 계약이 있다.

모든 컨트롤러 명령이 읽고 쓰는 레지스터를 분류한 뒤 지원하는 모든 명령과 소스 형식을 사용하는 예제 컨트롤러를 실행합니다.

생각해 볼 질문

완전한 컨트롤러를 추론하기 전에 명령 하나에 대해 무엇을 알아야 할까요?

명령 태그마다 레지스터 읽기와 쓰기 요약하기
스택 효과와 레지스터 효과 구분하기
다음·조건부·직접·간접·halt 제어 구분하기
상수·레지스터·레이블·연산 소스 알아보기
지원 부분집합의 모든 명령을 포함한 컨트롤러 실행하기

instruction-summary는 컨트롤러 텍스트를 데이터로 다룹니다. 연산 식 안의 레지스터 소스를 재귀적으로 찾고 assign과 restore의 목적지를 기록하며 push와 pop 효과와 pc 변화 종류를 분류합니다. branch는 보통 레지스터가 아니라 flag를 읽고, label goto는 직접 이동이며 register goto는 레지스터에서 대상을 읽습니다.

예제 컨트롤러는 이 참고표를 실제 실행과 맞춥니다. 상수와 연산 결과를 대입하고 val을 저장·복원하며 레이블 위치를 continue에 넣고 간접 이동한 뒤 test와 branch와 perform과 halt를 거칩니다. 이 요약은 유한 시뮬레이터 서브셋의 정확한 참고표입니다.

SICP 코드UTF-8 2,378 / 1,048,576바이트

(begin
  (define (tagged-list? value tag)
    (and (pair? value) (eq? (car value) tag)))
  (define (contains? item items)
    (cond ((null? items) #f)
          ((eq? item (car items)) #t)
          (else (contains? item (cdr items)))))
  (define (adjoin item items)
    (if (contains? item items) items (append items (list item))))
  (define (union left right)
    (if (null? right)
        left
        (union (adjoin (car right) left) (cdr right))))
  (define (source-registers source)
    (cond ((tagged-list? source 'reg)
           (list (cadr source)))
          ((tagged-list? source 'op)
           (collect-registers (cddr source)))
          (else '())))
  (define (collect-registers sources)
    (if (null? sources)
        '()
        (union (source-registers (car sources))
               (collect-registers (cdr sources)))))
  (define (instruction-summary instruction)
    (let ((tag (car instruction)))
      (cond
        ((eq? tag 'assign)
         (list 'assign
               (source-registers (caddr instruction))
               (list (cadr instruction))
               'none
               'next))
        ((eq? tag 'test)
         (list 'test
               (source-registers (cadr instruction))
               '()
               'none
               'next))
        ((eq? tag 'branch)
         (list 'branch '() '() 'none 'conditional))
        ((eq? tag 'goto)
         (list 'goto
               (source-registers (cadr instruction))
               '()
               'none
               (if (tagged-list? (cadr instruction) 'reg)
                   'indirect
                   'direct)))
        ((eq? tag 'save)
         (list 'save (list (cadr instruction)) '() 'push 'next))
        ((eq? tag 'restore)
         (list 'restore '() (list (cadr instruction)) 'pop 'next))
        ((eq? tag 'perform)
         (list 'perform
               (source-registers (cadr instruction))
               '()
               'none
               'next))
        ((eq? tag 'halt)
         (list 'halt '() '() 'none 'halt))
        (else
         (list 'unknown '() '() 'none 'unknown)))))
  (map instruction-summary
       '((assign val (op + (reg a) (const 1)))
         (test (op = (reg val) (const 10)))
         (branch done)
         (goto (reg continue))
         (save val)
         (restore val)
         (perform (op record (reg val)))
         (halt))))

(begin
  (define (tagged-list? value tag)
    (and (pair? value) (eq? (car value) tag)))
  (define (contains? item items)
    (cond ((null? items) #f)
          ((eq? item (car items)) #t)
          (else (contains? item (cdr items)))))
  (define (adjoin item items)
    (if (contains? item items) items (append items (list item))))
  (define (union left right)
    (if (null? right)
        left
        (union (adjoin (car right) left) (cdr right))))
  (define (source-registers source)
    (cond ((tagged-list? source 'reg)
           (list (cadr source)))
          ((tagged-list? source 'op)
           (collect-registers (cddr source)))
          (else '())))
  (define (collect-registers sources)
    (if (null? sources)
        '()
        (union (source-registers (car sources))
               (collect-registers (cdr sources)))))
  (define (instruction-summary instruction)
    (let ((tag (car instruction)))
      (cond
        ((eq? tag 'assign)
         (list 'assign
               (source-registers (caddr instruction))
               (list (cadr instruction))
               'none
               'next))
        ((eq? tag 'test)
         (list 'test
               (source-registers (cadr instruction))
               '()
               'none
               'next))
        ((eq? tag 'branch)
         (list 'branch '() '() 'none 'conditional))
        ((eq? tag 'goto)
         (list 'goto
               (source-registers (cadr instruction))
               '()
               'none
               (if (tagged-list? (cadr instruction) 'reg)
                   'indirect
                   'direct)))
        ((eq? tag 'save)
         (list 'save (list (cadr instruction)) '() 'push 'next))
        ((eq? tag 'restore)
         (list 'restore '() (list (cadr instruction)) 'pop 'next))
        ((eq? tag 'perform)
         (list 'perform
               (source-registers (cadr instruction))
               '()
               'none
               'next))
        ((eq? tag 'halt)
         (list 'halt '() '() 'none 'halt))
        (else
         (list 'unknown '() '() 'none 'unknown)))))
  (map instruction-summary
       '((assign val (op + (reg a) (const 1)))
         (test (op = (reg val) (const 10)))
         (branch done)
         (goto (reg continue))
         (save val)
         (restore val)
         (perform (op record (reg val)))
         (halt))))

예제

결과—

출력: —
값: —
진단: —

실행 추적0 / 0 개 이벤트

예상 결과

첫 프로그램은 assign, test, branch, goto, save, restore, perform, halt의 계약을 차례로 반환합니다. 예제 컨트롤러는 (complete 10 #t 12 (10))을 반환합니다.

실행 추적에서 볼 점

각 정적 계약을 실제 전이와 비교하세요. 특히 마지막 스택에는 보이지 않는 save와 restore, continue에 저장한 레이블 소스, 간접 goto, flag를 만드는 test, -1 대입을 건너뛰는 참 branch를 따라가세요.

직접 해보기

프로그램을 수정하고 결과를 비교해 보세요.

레이블 소스를 사용하는 두 번째 goto와 레지스터 피연산자 두 개를 가진 perform을 추가하세요. 컨트롤러를 실행하기 전에 정적 요약을 갱신하세요.

힌트 보기

직접 label goto는 보통 레지스터를 읽지 않습니다. perform은 연산 소스 안에서 재귀적으로 발견한 모든 레지스터를 읽습니다.

이 수업 완료하기

이 장의 총 23개 수업 중 0개 완료0%