생각해 볼 질문
식 트리는 어떻게 선형 명령열이 될까요?
- 문법 데이터에서 상수와 산술 명령 내보내기
- 스택 코드에서 피연산자 순서 보존하기
- 컴파일과 기계 실행 분리하기
compile은 왼쪽 피연산자 코드, 이어서 오른쪽 피연산자 코드, 마지막으로 산술 명령 하나를 내보냅니다. 재귀는 중첩된 식을 선형 리스트로 펼칩니다.
execute는 상수를 push합니다. 산술 명령은 오른쪽 값과 왼쪽 값을 pop하고 둘을 결합하여 결과를 push합니다. 남은 코드가 없으면 스택 맨 위의 값이 프로그램 값입니다.
SICP 코드UTF-8 1,088 / 1,048,576바이트
(begin
(define (operator-instruction operator)
(cond ((eq? operator '+) 'add)
((eq? operator '-) 'sub)
((eq? operator '*) 'mul)))
(define (compile expression)
(if (number? expression)
(list (list 'const expression))
(append (compile (cadr expression))
(append (compile (caddr expression))
(list (operator-instruction (car expression)))))))
(define (execute code stack)
(if (null? code)
(car stack)
(let ((instruction (car code)))
(if (pair? instruction)
(execute (cdr code) (cons (cadr instruction) stack))
(let ((right (car stack)) (left (cadr stack)))
(execute
(cdr code)
(cons (cond ((eq? instruction 'add) (+ left right))
((eq? instruction 'sub) (- left right))
((eq? instruction 'mul) (* left right)))
(cddr stack))))))))
(let ((code (compile '(+ (* 3 4) 5))))
(list code (execute code '()))))
예제
첫 프로그램은 내보낸 명령 다섯 개와 실행된 값 17을 반환합니다.
실행 추적에서 볼 점재귀적인 compile 호출을 이후의 execute 호출과 분리하세요. 실행하는 동안 각 명령은 스택을 바꾸면서 코드를 소비합니다.
직접 해보기프로그램을 수정하고 결과를 비교해 보세요.
(+ 1 (* 2 (+ 3 4)))를 컴파일하세요. 실행하기 전에 명령 리스트를 적으세요.
힌트 보기
각 수는 const를 내보냅니다. 각 복합 식은 두 피연산자 뒤에 연산자를 내보냅니다.