마무리 과제 · 실행 파이프라인

추상 데이터에서 명시적인 기계 상태까지 생각 하나를 이어 가세요.

한 프로그램이 표현식 데이터를 만들고 환경에서 해석하고 컴파일하고 pc와 스택으로 실행하며 파이프라인 실행 횟수까지 기억합니다.

생각해 볼 질문

각 층이 표현을 바꾸면서도 학습자가 보는 값을 보존하는지 설명할 수 있나요?

생성자로 표현식 데이터 만들기
선택자로 표현 읽기
명시적인 환경에서 이름 평가하기
표현식을 스택 명령으로 컴파일하기
pc와 stack을 실행하면서 closure 상태 유지하기

make-sum은 추상 표현식을 만들고 evaluate와 compile은 같은 선택자를 따라 서로 다른 일을 합니다.

run은 pc와 stack을 상태로 들고 step을 반복합니다. make-pipeline은 컴파일한 코드와 실행 횟수를 함께 캡처합니다.

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

(begin
  (define (make-sum left right) (list 'sum left right))
  (define (left-operand expression) (cadr expression))
  (define (right-operand expression) (caddr expression))
  (define (lookup name environment) (cdr (assoc name environment)))
  (define (evaluate expression environment)
    (if (symbol? expression)
        (lookup expression environment)
        (+ (evaluate (left-operand expression) environment)
           (evaluate (right-operand expression) environment))))
  (define (compile expression)
    (if (symbol? expression)
        (list (list 'load expression))
        (append (compile (left-operand expression))
                (append (compile (right-operand expression)) '(add)))))
  (define (step code environment state)
    (let ((pc (car state)) (stack (cadr state)))
      (let ((instruction (list-ref code pc)))
        (if (pair? instruction)
            (list (+ pc 1) (cons (lookup (cadr instruction) environment) stack))
            (list (+ pc 1) (cons (+ (cadr stack) (car stack)) (cddr stack)))))))
  (define (run code environment state)
    (if (= (car state) (length code)) state
        (run code environment (step code environment state))))
  (define (make-pipeline expression)
    (let ((code (compile expression)) (runs 0))
      (lambda (environment)
        (set! runs (+ runs 1))
        (list (evaluate expression environment)
              (run code environment (list 0 '())) runs))))
  (let ((pipeline (make-pipeline (make-sum 'x 'y))))
    (list (pipeline '((x . 4) (y . 5)))
          (pipeline '((x . 2) (y . 10))))))

(begin
  (define (make-sum left right) (list 'sum left right))
  (define (left-operand expression) (cadr expression))
  (define (right-operand expression) (caddr expression))
  (define (lookup name environment) (cdr (assoc name environment)))
  (define (evaluate expression environment)
    (if (symbol? expression)
        (lookup expression environment)
        (+ (evaluate (left-operand expression) environment)
           (evaluate (right-operand expression) environment))))
  (define (compile expression)
    (if (symbol? expression)
        (list (list 'load expression))
        (append (compile (left-operand expression))
                (append (compile (right-operand expression)) '(add)))))
  (define (step code environment state)
    (let ((pc (car state)) (stack (cadr state)))
      (let ((instruction (list-ref code pc)))
        (if (pair? instruction)
            (list (+ pc 1) (cons (lookup (cadr instruction) environment) stack))
            (list (+ pc 1) (cons (+ (cadr stack) (car stack)) (cddr stack)))))))
  (define (run code environment state)
    (if (= (car state) (length code)) state
        (run code environment (step code environment state))))
  (define (make-pipeline expression)
    (let ((code (compile expression)) (runs 0))
      (lambda (environment)
        (set! runs (+ runs 1))
        (list (evaluate expression environment)
              (run code environment (list 0 '())) runs))))
  (let ((pipeline (make-pipeline (make-sum 'x 'y))))
    (list (pipeline '((x . 4) (y . 5)))
          (pipeline '((x . 2) (y . 10))))))

예제

결과—

출력: —
값: —
진단: —

실행 추적0 / 0 개 이벤트

예상 결과

프로그램은 ((9 (3 (9)) 1) (12 (3 (12)) 2))를 반환합니다. 직접 평가한 값과 마지막 기계 스택 값이 일치합니다.

실행 추적에서 볼 점

생성자와 선택자, 환경 조회, 실행 전 compile, pc 0부터 3까지의 변화, 스택 갱신, runs 대입을 찾으세요.

복습

전체 파이프라인을 확인하는 질문 다섯 개

표현 방식은 어디에 숨겨져 있나요?

정답 make-sum이 만들고 evaluate와 compile은 선택자를 통해 읽습니다.

두 직접 평가값이 다른 이유는 무엇인가요?

정답 같은 표현식에 x와 y의 값이 다른 두 환경을 주었기 때문입니다.

마지막 pc가 3인 이유는 무엇인가요?

정답 load 두 개와 add 하나, 모두 세 명령을 실행했기 때문입니다.

두 호출 사이에 남는 상태는 무엇인가요?

정답 클로저가 컴파일한 코드와 가변 runs 바인딩을 유지합니다.

이 실행이 확정하는 것은 무엇인가요?

정답 화면에 나온 표현식과 환경과 기계 상태와 두 파이프라인 호출의 정확한 일치를 기록합니다.