-
sicp 4.1 재번역카테고리 없음 2021. 4. 7. 00:02
- 첫날인 2월 3일보다 조금 더 진행되어 4.1.2 가 대충 마무리 진행되고 있다.
용어들에 대해 한번 더 생각해볼 좋은 기회다.
- 4.1.3. 까지 대충 작업이 완료되었다. (2.7)
- 4.1.4. 까지 대충 작업이 완료되었다. (2.8)
- 4.1.5 까지 대충 번역했다. 언어의 혼란에 스스로 조금 지치고 있다. (2.9)
- 4.1.6을 대충 번역했다. 오늘은 머리의 성능이 저하되어 애를 먹었다. 몇문장의 번역은 전혀 마음에 들지 않는다. (2.10)
anatomy of lisp을 재구성하다가 재미있는 구절을 발견했다.
‥‥. I always worked with programming languages because It seemed to me that until you could understand those, you really couldn't understand computers, Understanding them doesn't really mean only being able to use them. A lot of people can use them without understanding them...." Christopher Strachey[Str 74]
4.1 부분 재구성
이 장은 SICP의 완벽한 번역이 아니라 나름대로 적어본 재구성이다. 그것도 필요한 부분만이다. 일단 4.1 에서도 일부만을 적는다.
가끔씩 재갱신 될 것이며 피드백을 원하고 있다.
책의 한글 번역은 강렬하게 한글화 되거나 우리말로 무엇인가를 번역해야 한다는 의식으로 점철되어 있는데 이렇게 진지한 필요는 없다. 아무튼 강렬한 의지에 비해서 한글판의 언어혼동은 상당히 높다. 같은 장에서 서로 다른 몇 개의 호칭이 나타나는 경우도 많다.
그런데 이 작업은 원래 어려운 것이다. 노자에 이르기를 名可名非常名 이라고 했는데 우리는 이름 하나 짓는 것도 어렵고 우리가 지칭하는 것이 반드시 일치하는 것도 아니다. 대충 부르고 사람들끼리 인정하는 것이다. 몇천년전에도 어려웠던 일은 요즘은 더 어려울 것임에 틀림없다.
그래서 여기서 내가 적는 방식이 좋은 방법도 아니며 나의 이름공간세계에서 약간의 절충을 본 것 뿐 이라는 것을 밝힌다. 하지만 적어보는 것이 좋을 것 같고 미래에 다 잊어 먹을 나의 기억을 위해 비망록처럼 적어 본다.
잊어먹지 않기 위한 비망록은 용어부터 시작해야 할 것 같다.
우선 evlauation 을 계산이라고 쓰는데 특별히 다른 말이 떠오르지 않는다. 평가라고 하기도 거시기하다. 그런데 evaluator 는 실행기라고도 한다. 그럼 evaluation을 실행이라고 불러야 하는데 execution 의 이름공간과 충돌하기 쉽다. 그래서 그냥 실행기라고 부르자. 많이들 쓰고 있으니 이밸류에이터라는 아름다운 고유의 외래어는 사용하지 말기로 하자. 예전에 계산기라는 말이 있었는데 이 말은 컴퓨터라는 단어와 충돌한다. 인터프리터를 실행기라고 부르고 컴파일러를 번역기라고도 부른다. 그런데 인터프리터를 번역기라고 부르면 안될 이유도 없는데 나는 헛갈릴 뿐이다. 그래서 인터프리터와 컴파일러는 그냥 쓰기로 한다. 혼란이 줄어든다. evaluator 를 계산기라고 부르면 독자들과 나의 언어공간을 침범하여 충돌한다.
용어의 혼란은 recursion 을 재귀, 순환 , 되돌이 등으로 부르면서 가중되기도 하는데 한때는 기가 막혀서 그럼 recursive 는 무엇이냐고 물었더니 ‘되도는’ 이라는 아름다운 용어가 있다고 한다. 여기에 대해서는 할 말이 없었다. iteration 은 되풀이 라고도 적혀 있는데 iterative 는 “되푸는” 이 되겠다.
combination 은 엮은 식 정도로 해석하자. (조합식도 나쁘지 않지만 엮은식 역시 나쁘지 않다.) compound procedure 는 엮은 프로시저라고 부르자.
special form 은 특별한 형태라고 나와 있다.
이 정도면 지뢰를 밟지 않는 것처럼 용어의 충돌을 피하면서 읽고 번역하는 수 밖에 없다.
막상 시작하려 하니 우선 4장의 제목 자체가 문제가 된다.
언어를 처리하는 기법 이라고 되어 있는 원제는 “Metacircuar Abstraction” 이다. 그냥 들어서는 원래의 용어를 재구성할 방법이 없다, 메타순환적 일반화(추상화도 마찬가지)라고 번역해도 그냥 그렇다. 가역반응이 일어나지 않는 번역이라고 할 수 있다. 그렇다고 메타서큘러 앱스트랙션을 바로 쓰는 것도 어렵다. 일본책에서는 무어라고 했는지 매우 궁금하나 일본책을 입수하지는 못했다. 하지만 일본 사람들의 어려움도 이해는 간다. 번역이 되었으니 절충에 절충을 거듭했을 것이다. 꼭 보고 싶다.
아무튼 이제 푸념이 끝났으니 나의 오역과 오타가 시작된다. (불교식으로 말하면 나는 이렇게 본다 -如是我聞정도가 되겠다.) 물론 악의 없는 오해도 포함된다.
4.1
우리의 리스프 인터프리터는 리스프로 구현한 것이다. 리스프를 계산할 프로그램 자체를 리스프로 만든 실행기(evaluator)는 같은 말을 되풀이 하는 것처럼(circular) 들린다. 그러나 계산이라는 것이 하나의 처리과정이며 , 계산과정을 리스프 ( 결국 리스프는 우리가 처리과정을 설명하는 도구다.)를 사용하여 설명하는 것은 적절한 것이다. 언어실행기가 계산하려는 언어와 같은 언어로 쓰여졌을 때 이를 메타서큘라(metacircular)라고 부른다.
이번에 만들 메타서큘러 실행기는 3.2 절에서 만든 환경모델을 스킴으로 형성한 것이다. 이 환경모델의 두가지 기본요소를 떠올려보자.
1. 특별한 형태(special forms)가 아닌 엮은식을 계산하려면 우선 부분식들을 계산한다. 값을 구한 후 연산자(operator)를 피연산자(operand)들에 적용한다.
2. 엮은 프로시저를 인자세트에 적용하는 것은 프로시저의 몸체를 새로운 환경에서 계산하는 것이다. 이 새로운 환경을 만드는 것은 프로시저 객체의 환경부분에 있던 환경을 확장하는 것이다. 기존의 환경에 프로시저의 매개변수(formal parameter)와 프로시저 적용시의 인자들을 묶은 프레임을 만든다.
이 두 법칙이 계산과정의 진수를 설명한다. 이것은 기본적인 사이클로 식이 환경에서 계산되어 결국 프로시저가 만들어져 인자에 적용된다. 그 다음에 새로운 환경을 만들어지고 식의 계산이 이 환경에서 일어나게 된다. 이 과정은 계속 일어나서 심볼(환경에서 그 값을 알 수 있는 값)이나 프리미티브 연산(바로 적용(계산)될 수 있다)이 나올 때까지 계속된다. 이 런 계산 사이클은 실행기의 핵심 프로시저인 eval 과 apply 의 상호작용으로 4.1.1 섹션에서 설명한다.
계산될 식의 문법을 정의하는 프로시저가 실행기의 구현을 좌우한다. 언어의 표현방식에 얽매이지 않도록 데이터 요약 방식(data abstarction)을 써서 실행기를 만들 것이다. 예를들어 심볼 set!로 시작하는 표현이 아니라 assignment? 라는 술어(prediacte)를 사용하여 그것이 지정(assignment)를 의미하는 것인지 검사한 다음 assignment-variable 와 assignment-value같은 요약 선택자를 지정작업(assign)에 사용하기로 하자. 식의 구현 방법은 4.1.2 에 자세히 설명한다. 4.1.3에는 프로시저와 환경을 나타내는 법을 자세히 설명한다. 예르를면 make-procedure는 엮은 식을 만들고 lookup-variable-value는 변수값을 찾는 것이며 apply-primitive-procedure는 프리미티브 연산을 인자리스트에 적용한다.
(그런데 과연 이 설명만으로 전체를 이해할 천재가 몇명이 되는가?)
(앞에서 말한 두 가지 법칙중에서 우리는 TAOI를 보면서 몇가지 테스트를 했다.
하나는 전혀 확장하지 않고 프로시저만 확장하는 경우와
다이나믹 바인딩처럼 env를 아예 따로 주는 경우
그리고 앞으로 설명항 4.1 처럼 leical 스코프를 제공하는 경우로 클로저를 만드는 경우이다.
)
그림으로 그리자면 이런 모습이 나온다.
음양의 그림처럼 나타난다.
4.1.1 실행기의 코어 (4.1.1 The Core of the Evaluator)
계산(Eval)
Eval 은 식(expression) 과 환경(environment)을 인자로 삼는다. 식을 선별한 후 계산 방향을 지시한다. Eval의 구조는 계산할 식의 문법 타입에 대한 일종의 케이스 분석을 하는 것이다. 프로시저의 일반성을 유지하기 위해 식의 유형에 대한 판별을 간추린(일반적인 , abstract) 형태로 표시해야 한다. 다양한 형태의 식에 대해 특정한 양식을 고집해서는 안된다. 식의 종류마다 그것을 검사하는 조건절(predicates)이 있고 각 부분들을 골라내어 간추리는(요약하는 ) 방법이 있다. 이런 요약된 문법은 같은 실행기를 사용하더라도 문법에 대한 프로시저를 달리하면 언어의 문법을 바꾸는 일을 쉽게 만든다.
-
{ 잠깐 보충 설명을 붙이자.
Eval 은 4.1 장에서 3가지로 나누어 설명하고 있다.
기본식(Primitive expressions) , 특수한 형태(Special forms) , 조합식(Combinations)
그런데 예전에는 Special forms 와 Combinations 두 가지로만 설명하는 경우가 많았다.
코드는 50년 동안 별로 변하지 않았다.
그래서 이렇게 생각하면 될 것 같다. 함수의 적용이냐 아니냐에 따라 달라지는 것이다.
그래서 (+ a b) 는 조합식이다. 다른 말로 하면 함수 + 의 적용이다. 이때 + 는 프리미티브 함수다. (f a b) 도 조합식이다. 함수 f 에 대해 a b를 적용한다. 분명히 조합식으로 f는 엮은식이다. 그 함수몸체를 어디선가 찾아서 적용하는 것이다.
나머지는 모두 특수한 형태(special forms)다.
이제 다시 원문으로 돌아가자.
}
-기본식(primitive expressions)
숫자와 같이 스스로 계산이 되는 식에 대해 eval은 식 차체를 돌려준다.
변수(variables)가 나오면 eval 은 환경(environment) 을 그 값을 찾기 위해 살펴본다(look up).
-특별한 형태(Special forms)
따옴표가 달린 식이 나오면 eval은 따옴표가 달리기전의 식을 돌려준다.
변수의 지정 (또는 정의) 이 일어날 때 변수는 eval 을 재귀적으로 불러서 변수와 관련지을 새로운 값을 찾아야 한다. 환경은 변수의 바인딩을 위해 반드시 변화를 반영하여 고쳐져야 (아니면 만들어지거나) 한다.
(if 식 이전에는 cond 가 있었다. 그런데 나중에 if 로 바뀌었다. 5장에서 컴파일러를 만드는 작업을 하려면 if 가 편하기 때문이다.)
if 식은 몇 부분에 특별한 처리를 필요로 한다. 만약 if 조건절이 참이라면 결과식(consequent) 부분을 그렇지 않다면 다른 결과식(alternative) 부분을 계산해야 한다.
(If P Then C 띠se A 인 경우 C를 consequent , A 를 라고 한다. P는predicate 라고 부른다. SICP는 consequent 를 결과식 , Alternate를 다른 식으로 번역했고 다른 논리학 책들 역시 consequent를 후항 등으로 번역하고 있으나 좋은 답이라고는 생각이 안들어 그냥 둔다. 예전에도 어쩔 수 없이 결과식 다른식으로 번역하긴 했으나 좋은 답을 찾고 있다.
2010.2.5. -->아무래도 답이 나오지 않아 결과식 , 다른식의 표기법을 따르기로 한다.
)
람다식은 식의 람다식 인자와 몸체 그리고 계산당시의 환경을 한데 묶어서 적용가능한 프로시저로 변환해야 한다.
begin 식은 식들이 나타나는 순서대로 차례로 계산해야 한다.
cond 식은 if 식을 겹친 것으로 바꾸어 놓은 후 계산한다.
엮은식 (Combinations)
프로시저 적용을 위해서 eval은 엮은식의 연산자(operator)와 피연산자(operands) 부분을 재귀적으로 계산해야 한다. 그 결과물인 프로시저와 인자가 apply 로 넘겨지며 이것이 바로 프로시저 적용이다.
다음이 eval 의 정의다:
(define (eval exp env)
(cond ((self-evaluating? exp) exp)
((variable? exp) (lookup-variable-value exp env))
((quoted? exp) (text-of-quotation exp))
((assignment? exp) (eval-assignment exp env))
((definition? exp) (eval-definition exp env))
((if? exp) (eval-if exp env))
((lambda? exp)
(make-procedure (lambda-parameters exp)
(lambda-body exp)
env))
((begin? exp)
(eval-sequence (begin-actions exp) env))
((cond? exp) (eval (cond->if exp) env))
((application? exp)
(apply (eval (operator exp) env)
(list-of-values (operands exp) env)))
(else
(error "Unknown expression type -- EVAL" exp))))
명료함을 위해 eval 은 cond 를 사용하여 케이스 분석을 했다. 단점이라면 프로시저가 몇개의 뚜렷한 형태의 식만을 다룰 수 있다는 것이고 새로운 것들은 eval 의 정의를 바꾸지 않고는 정의될 수 없다는 점이다.
대부분의 리스프 구현에서는 식의 종류에 따라 분기하는 것은 데이터 지향 방식으로 이루어진다. 그러면 사용자가 eval 자체의 정의를 바꾸지 않고도 eval 이 구별할 수 있는 새로운 형태의 식을 추가할 수 있다. (See exercise 4.3.)
적용(Apply)
apply 는 2 개의 인자를 갖는다. 프로시저와 프로시저를 적용해야 하는 인자들의 리스트이다. apply는 프로시저를 2 종류로 분류한다: 프리미티브 프로시저가 나오면 apply-primitive-procedure를 부른다. 엮은 프로시저(compound procedures)는 프로시저의 몸을 만드는 식들을 차례로 계산해서 만든다. 몸을 계산하기 위한 환경은 프로시저와 함께 전해진 환경에 새로운 프레임을 포함하는 것이다. 이 프레임은 프로시저의 매개변수와 프로시저 적용시 전해진 인자들을 바인드하는 것으로 만들어진다. 아래에 apppy 의 정의다:
(define (apply procedure arguments)
(cond ((primitive-procedure? procedure)
(apply-primitive-procedure procedure arguments))
((compound-procedure? procedure)
(eval-sequence
(procedure-body procedure)
(extend-environment
(procedure-parameters procedure)
arguments
(procedure-environment procedure))))
(else
(error
"Unknown procedure type -- APPLY" procedure))))
- 주 SICP 번역본은 프레임을 변수 일람표로 번역했다. 그런데 프레임이 나은 것 같다는 생각이다.
프로시저 인자 (Procedure arguments)
eval 이 프로시저 적용을 처리할 때에 list-of-values를 써서 프로시저가 적용될 인자들의 리스트를 만든다. List-of-values는 엮은식의 피연산자로 나타난다. 피연산자들을 각각 계산한 후 해당하는 값으로 리스트를 만든다.
(define (list-of-values exps env)
(if (no-operands? exps)
'()
(cons (eval (first-operand exps) env)
(list-of-values (rest-operands exps) env))))
조건식(Conditionals)
Eval-if 는 주어진 환경에서 if 식의 술어 부분을 계산한다. 결과 참이면 eval-if 는 결과식 (consequent)을 계산하고 , 그렇지 않다면 다른결과식(alternative)을 계산한다:
(define (eval-if exp env)
(if (true? (eval (if-predicate exp) env))
(eval (if-consequent exp) env)
(eval (if-alternative exp) env)))
true? 의 사용법은 구현될 언어와 구현하는 언어 사이의 문제를 명학하게 보여주고 있다. if-predicate는 구현될 언어에서 계산되는 것이므로 그 언어에서의 값을 낸다. 인터프리터의 술어부에 사용된 true?는 그 값을 구현하는 언어에서 사용되는 값으로 바꾼다: 메타서큘러 표현의 참값은 그 밑에 깔린 스킴의 값과 다를 수 있기 때문이다.
시퀀스가 좋은가 잇단식이 좋은 가는 잘 모르겠다. 별 상관이 없다.
그리고 이제 쓸데 없는 것으로 에너지를 빼는 것은 지쳐간다.
시퀀스 (Sequences)
Eval-sequence 는 프로시저 몸체의 식들을 eval을 써서 차례대로 계산한다. 이 식들은 bigin 식 안에 있는 식들이다. 인자는 식들의 시퀀스와 환경이며 식들은 나타나는 순서대로 계산한다. 되돌려주는 값 (value returned)은 마지막식의 값이다.
(define (eval-sequence exps env)
(cond ((last-exp? exps) (eval (first-exp exps) env))
(else (eval (first-exp exps) env)
(eval-sequence (rest-exps exps) env))))
assignment 를 덮어쓰기라고 적지만 지정으로 해도 별 문제가 없을 것 같고 할당은 조금 거리감이 있다.
지정과 정의 (Assignments and definitions)
아래의 프로시저는 변수에 대한 지정을 다룬다. eval 을 불러 지정될 값을 찾아내어 변수와 결과값을 set-variable-value! (지정된 환경에 설치되어 있어야 한다.)로 보낸다.
(define (eval-assignment exp env)
(set-variable-value! (assignment-variable exp)
(eval (assignment-value exp) env)
env)
'ok)
변수의 정의도 비슷한 방법으로 한다:
(define (eval-definition exp env)
(define-variable! (definition-variable exp)
(eval (definition-value exp) env)
env)
'ok)
여기서는 변수의 지정이나 정의을 할 때 돌려주는 값을 ok 로 정하자.
4.1.2 식을 나타내는 방법( Representing Expressions)
실행기는 2.3.2 절에 나온 심볼 미분 프로그램의 흔적을 갖고있다. 두 프로그램 모두 기호로 된 식을 조작한다. 두 프로그램에서 엮은식의 처리 결과는 식의 일부분을 재귀적으로 처리하고 결과를 식의 종류에 따라 묶는 (combining) 것이다. 둘은 데이터 요약을 사용하여 처리의 일반적인 규칙을 식이 표현되는 세세한 부분과 떼어놓고 있다. 이말은 미분 프로그램에서 같은 미분 프로시저가 프리픽스 (prefix) ,인픽스(infix) 아니면 다른 형태의 대수식도 처리할 수 있다는 뜻이다. 실행기에서는 언어의 문법이 식으로부터 부분부분을 분류하고 뽑아내는 프로시저에 의해 결정된다는 것을 뜻한다.
여기에 언어의 문법에 대한 자세한 내용이 있다:
¤스스로 계산되는 (self-evaluating) 것들은 수와 문자열뿐이다.
(define (self-evaluating? exp)
(cond ((number? exp) true)
((string? exp) true)
(else false)))
¤변수는 기호(symbol)로 나타낸다.
(define (variable? exp) (symbol? exp))
¤ 따온 식은 (quote <text-of-quotation>)이다:
(define (quoted? exp)
(tagged-list? exp 'quote))
(define (text-of-quotation exp) (cadr exp))
Quoted? 는 tagged-list? 프로시저로 검사한다. 이 프로시저는 리스트의 앞부분이 지정된 기호로 시작하는 가를 조사한다:
(define (tagged-list? exp tag)
(if (pair? exp)
(eq? (car exp) tag)
false))
¤ 지정(assignment)은 (set! <var> <value>) 의 형태다:
(define (assignment? exp)
(tagged-list? exp 'set!))
(define (assignment-variable exp) (cadr exp))
(define (assignment-value exp) (caddr exp))
¤ 정의(definitions)는
(define <var> <value>)
또는
(define (<var> <parameter1> ... <parametern>)
<body>)
의 형식이다.
나중에 나온 프로시저 정의 표준형은 아래에 나오는 내용의 편한문법(syntactic sugar)이다.
(define <var>
(lambda (<parameter1> ... <parametern>)
<body>))
해당하는 문법 프로시저는 다음과 같다:
(define (definition? exp)
(tagged-list? exp 'define))
(define (definition-variable exp)
(if (symbol? (cadr exp))
(cadr exp)
(caadr exp)))
(define (definition-value exp)
(if (symbol? (cadr exp))
(caddr exp)
(make-lambda (cdadr exp) ; formal parameters
(cddr exp)))) ; body
¤ 람다식은 기호(lambda) 로 시작하는 리스트이다:
(define (lambda? exp) (tagged-list? exp 'lambda))
(define (lambda-parameters exp) (cadr exp))
(define (lambda-body exp) (cddr exp))
람다식의 구성자(constructor)도 있다. 앞서 나온 definition-value가 사용한 바 있다:
(define (make-lambda parameters body)
(cons 'lambda (cons parameters body)))
¤ 조건문은 if 로 시작하고 술어부 (predicate)와 결과식(consequent) 그리고 (선택사항인) 다른 결과식을 갖는다. 다른 결과식 부분이 없을 경우 다른 결과식에 해당하는 값은 false 다.
(define (if? exp) (tagged-list? exp 'if))
(define (if-predicate exp) (cadr exp))
(define (if-consequent exp) (caddr exp))
(define (if-alternative exp)
(if (not (null? (cdddr exp)))
(cadddr exp)
'false))
¤ if 식에 대한 구성자(constructor)도 준비했다. cond->if 는 cond 식을 if 식으로 바꿀때에도 쓴다.
(define (make-if predicate consequent alternative)
(list 'if predicate consequent alternative))
¤ Begin 은 식의 시퀀스를 하나의 식으로 바꾼다. begin의 문법 연산은 begin 식으로부터 실제의 시퀀스를 뽑아낸다. 그리고 첫 번째 식과 나머지 식을 돌려주는 선택자(selector)도 있다.
(define (begin? exp) (tagged-list? exp 'begin))
(define (begin-actions exp) (cdr exp))
(define (last-exp? seq) (null? (cdr seq)))
(define (first-exp seq) (car seq))
(define (rest-exps seq) (cdr seq))
cond->if에서 사용되는 구성자로 sequence->exp 가 있다. 시퀀스를 하나의 식으로 만들며 필요하면 begin 을 사용한다.
We also include a constructor (for use by ) that transforms a sequence into a single expression, using begin if necessary:
(define (sequence->exp seq)
(cond ((null? seq) seq)
((last-exp? seq) (first-exp seq))
(else (make-begin seq))))
(define (make-begin seq) (cons 'begin seq))
¤ 프로시저 적용(procedure application) 앞에서 설명하지 않은 엮은식(compound expression)이다. (A procedure application is any compound expression that is not one of the above expression types. The car of the expression is the operator, and the cdr is the list of operands:)
(엮은식 , 합친식 , 조합식 아직도 어느 것이 제일 좋은가 못정했다. )
식의 car 는 연산자이고 cdr 은 피연산자의 리스트이다.
(define (application? exp) (pair? exp))
(define (operator exp) (car exp))
(define (operands exp) (cdr exp))
(define (no-operands? ops) (null? ops))
(define (first-operand ops) (car ops))
(define (rest-operands ops) (cdr ops))
유도된 식(Derived expressions)
어떤 특별한 형태(special forms)들은 특별히 따로 구현하는 것이 아니라 다른 특별한 형태의 식으로 정의될 수 있는 것들이 있다. 한 예가 cond 로 식을 중첩하여 구현할 수 있다. 다음과 같은 식의 계산문제를 변환하여 :
(cond ((> x 0) x)
((= x 0) (display 'zero) 0)
(else (- x)))
if 와 begin 으로 바꿀 수 있다:
(if (> x 0)
x
(if (= x 0)
(begin (display 'zero)
0)
(- x)))
cond 계산의 구현을 이런 방향으로 처리하면 , 따로 지정해야 하는 계산 프로세스를 위한 특별한 형태가 줄기 때문에 실행기가 간단해진다.
cond 식에서 일부를 뽑아내는 문법 프로시저와 cond 를 if 로 바꾸어주는 cond->if 를 포함시켰다. 케이스분석은 cond 로 시작하고 조건-행위절(predicate-action clauses)의 리스트가 따라오는데 이때 술어위치에 else 가 있으면 else 절이 따라온다.
(define (cond? exp) (tagged-list? exp 'cond))
(define (cond-clauses exp) (cdr exp))
(define (cond-else-clause? clause)
(eq? (cond-predicate clause) 'else))
(define (cond-predicate clause) (car clause))
(define (cond-actions clause) (cdr clause))
(define (cond->if exp)
(expand-clauses (cond-clauses exp)))
(define (expand-clauses clauses)
(if (null? clauses)
'false ; no else clause
(let ((first (car clauses))
(rest (cdr clauses)))
(if (cond-else-clause? first)
(if (null? rest)
(sequence->exp (cond-actions first))
(error "ELSE clause isn't last -- COND->IF"
clauses))
(make-if (cond-predicate first)
(sequence->exp (cond-actions first))
(expand-clauses rest))))))
(cond 처럼 ) 문법의 변환으로 만들어낸 식을 유도된 식 (derived expressions - SICP한글판은 이끌어낸식 이라고 부른다. Let 식 역시 유도된 식이다.
Expressions (such as cond) that we choose to implement as syntactic transformations are called . Let expressions are also derived expressions (see exercise 4.6).13
{용어선정에 있어서 유도된 식과 유도식 이끌어낸 식 모두 고민이다.}
(primitive 를 원시 , 기본원소 , 기본 프로시저라고 할 수도 있으나
프리미티브라고 쓰는 것도 나쁘지 않을 것 같다.
compound procedure 는 엮은 프로시저로 번역했으나 SICP에는 합친 프로시저라고 나온다. SICP 역시 용어통일이 잘 되었다고 생각하지는 않는다.
)
4.1.3 언어실행기의 데이터구조 ( Evaluator Data Structures)
실행기의 구현에서 외부의 문법을 정의하는 것에 더하여 실행기 내부에서 조작을 일으키는 데이터 구조를 정의해야 한다. 프로시저와 환경의 표현방법 그리고 참과 거짓의 표현방법 같은 것들을 예로 들 수 있겟다
술어의 검사(Testing of predicates)
조건식에서 확실하게 거짓(false) 이 아닌 것들은 참(true)이라고 본다.
(define (true? x)
(not (eq? x false)))
(define (false? x)
(eq? x false))
프로시저의 표현(Representing procedures)
프리미티브 프로시저를 다루려면 다음과 같은 프로시저들을 사용할 수 있다고 가정한다.
(apply-primitive-procedure <proc> <args>)
주어진 프리미티브 프로시저를 리스트 <arg> 에 적용하고 적용결과를 돌려준다.
(primitive-procedure? <proc>)
<proc>이 프리미티브 프로시저인지 검사한다.
프리미티브 프로시저를 다루는 이 방법들은 4.1.4. 절에서 더 자세히 설명한다.
엮은 프로시저는 인자 , 프로시저 몸체 그리고 환경을 가지고 생성자(constructor)인 make-procedure로 만들어낸다.
{생성자라는 말은 정말이지 마음에 안든다.}
(define (make-procedure parameters body env)
(list 'procedure parameters body env))
(define (compound-procedure? p)
(tagged-list? p 'procedure))
(define (procedure-parameters p) (cadr p))
(define (procedure-body p) (caddr p))
(define (procedure-environment p) (cadddr p))
환경연산(Operations on Environments)
실행기는 환경을 다루는 연산들이 필요하다. 3.2 절에 설명된 것처럼 환경은 프레임의 시퀀스이고 여기서 각각의 프레임은 변수들과 해당되는 값들을 연관시킨 묶음표이다. 다름의 연산들을 환경연산에 사용한다:
(lookup-variable-value <var> <env>)
환경 <env>에서 기호<var>에 바인드된 값이 있으면 값을 되돌리고 바인드되지 않았으면 에러신호를 낸다.
(extend-environment <variables> <values> <base-env>)
<variables> 리스트에 있는 심볼이 <values>리스트의 해당 원소와 바인드되어 만든 새 프레임으로 기존의 환경 <base-env>를 확장한 새로운 환경을 내놓는다.
(define-variable! <var> <value> <env>)
변수 <var> 와 값 <value>를 바인딩하여 환경 <env> 의 첫 번째 프레임에 덧붙인다.
(set-variable-value! <var> <value> <env>)
환경 <env>에서 변수 <var>의 바인딩을 바꾼다. 그리하여 변수는 값 <value>로 바뀐다. 만약 변수가 바인드되지 않았다면 에러신호를 낸다.
이 연산들을 구현하기 위해 우리는 환경을 프레임의 리스트로 표현한다. 둘러싸는 환경 (기존의 환경)은 그 리스트이 cdr 이다. 빈 환경은 빈리스트로 나타낸다.
(define (enclosing-environment env) (cdr env))
(define (first-frame env) (car env))
(define the-empty-environment '())
환경을 만드는 각각의 프렘은 리스트의 쌍으로 나타낼 수 있다. 프레임에 바인드된 변수의 리스트와 연관된 값들의 리스트다.
(define (make-frame variables values)
(cons variables values))
(define (frame-variables frame) (car frame))
(define (frame-values frame) (cdr frame))
(define (add-binding-to-frame! var val frame)
(set-car! frame (cons var (car frame)))
(set-cdr! frame (cons val (cdr frame))))
변수와 값들을 연관시킨 새 프레임으로 환경을 확장하려면 먼저 변수의 리스트와 값들의 리스트로 만든 프레임을 만들어 환경에다 이어붙이면 도니다. 만약 변수와 값들의 수가 틀리면 에러신호를 낸다.
(define (extend-environment vars vals base-env)
(if (= (length vars) (length vals))
(cons (make-frame vars vals) base-env)
(if (< (length vars) (length vals))
(error "Too many arguments supplied" vars vals)
(error "Too few arguments supplied" vars vals))))
환경에서 변수를 찾으려면(look up) 첫 번째 프레임에서 변수 리스트를 흝어본다. 만약 원하는 변수를 찾으면 값의 리스트에서 해당하는 원소를 돌려준다. 만약 우리가 현재 프레임에서 변수를 찾지 못하면 그 다음의 리스트를 찾는 식으로 계속한다. 만약 비어있는 리스트에 도달하면 `unbound variable 에러신호를 낸다.
(define (lookup-variable-value var env)
(define (env-loop env)
(define (scan vars vals)
(cond ((null? vars)
(env-loop (enclosing-environment env)))
((eq? var (car vars))
(car vals))
(else (scan (cdr vars) (cdr vals)))))
(if (eq? env the-empty-environment)
(error "Unbound variable" var)
(let ((frame (first-frame env)))
(scan (frame-variables frame)
(frame-values frame)))))
(env-loop env))
지저한 환경에서 변수값을 새로운 값으로 지정하려면 lookup-variable-value에서 처럼 변수를 찾아본다, 그리고 찾았으면 해당하는 값을 고친다.
(define (set-variable-value! var val env)
(define (env-loop env)
(define (scan vars vals)
(cond ((null? vars)
(env-loop (enclosing-environment env)))
((eq? var (car vars))
(set-car! vals val))
(else (scan (cdr vars) (cdr vals)))))
(if (eq? env the-empty-environment)
(error "Unbound variable -- SET!" var)
(let ((frame (first-frame env)))
(scan (frame-variables frame)
(frame-values frame)))))
(env-loop env))
변수를 정의하려면 , 첫 번째 프레임에서 바인딩을 찾아본다. 그리고 만약 존재한다면 ( set-variable-value!에서와 같이) 그 바인딩을 고친다. 만약 이런 바인딩이 없다면 첫 번째 프레임에 정의할 내용을 집어넣는다,
(define (define-variable! var val env)
(let ((frame (first-frame env)))
(define (scan vars vals)
(cond ((null? vars)
(add-binding-to-frame! var val frame))
((eq? var (car vars))
(set-car! vals val))
(else (scan (cdr vars) (cdr vals)))))
(scan (frame-variables frame)
(frame-values frame))))
여기서 설명한 방법은 환경을 만들어 낼 수 있는 여러 방법중의 하나일 뿐이다. 데이터요약을사용하여 언어실행기를 세세한 표현방법과 분리시켜 놓았기 때문에 환경 표현은 우리가 원하는 대로 바꿀 수 있다. ( 연습문제 4.11.) 제품으로 생산하는 수준의 리스프 시스템에서는 실행기의 환경연산 속도 -특히 변수찾기- 가 시스템 성능에 큰 영향을 미친다, 여기서 설명한 표현방식은 간결하기는 하나 효율적이지는 않아 제품생산 수준에는 일반적으로 사용하지 않는다.
4.1.3 언어 실행기를 프로그램으로 돌리기(Running the Evaluator as a Program)
언어실행기를 갖게 되어서 , 이제 LISP 식이 계산되는 프로세스에 대한 설명을 (LISP으로 표현된) 손에 넣게 된 셈이다. 실행기를 하나의 프로그램으로 작성하는 일의 장점은 우리가 그 프로그램을 돌릴 수 있다는 점이다. 리스프 안에서 돌릴 수 있다는 것은 리스프 자체가 식을 계산하는 방법을 보여주는 동작모형이 생긴 셈이다. 이는 계산법칙을 실험하는 틀의 역할이며 이번 장의 뒷부분에서 설명할 이야기다.
실행기 프로그램은 식을 마지막까지 줄여서 결국은 프리미티브 프로시저로 구성된 식까지 만들어낸다. 그러므로 실행기를 실행하기 위해 필요한 일은, 현재의 리스프시스템에서 프리미티브 프로시저의 적용을 모델링하는(돌아가는 것을 흉내내는) 메커니즘을 만드는 일이다.
모든 프리미티브 프로시저 이름에는 해당되는 바인딩이 있어야만 한다. eval 이 프리미티브 프로시저의 연산자 적용을 계산 할 때 eval 은 apply 를 위해 적용할 프로시저를 찾는다. 그래서 글로벌 환경에서 식의 계산시 필요할지 모르는 프리미티브 프로시저의 이름과 그 해당하는 객체를 서로 짝을 맟추어 놓아야 한다. 글로벌 환경은 계산할 식에서 변수로서 등장하는 true , false 같은 심벌의 바인딩도 들어있어야 한다.
(역주:여기서는 객체는 프로시저를 말하나 구현에 따라서는 다른 언어의 라이브러리 같은 것이 나올 수도 있다. 또 SICP 번역에는 글로벌 환경이 바탕환경이라고 나온다. 나쁜 이름짓기가 아니지만 나의 머릿속에서는 잘 매칭이 안된다. )
(define (setup-environment)
(let ((initial-env
(extend-environment (primitive-procedure-names)
(primitive-procedure-objects)
the-empty-environment)))
(define-variable! 'true true initial-env)
(define-variable! 'false false initial-env)
initial-env))
(define the-global-environment (setup-environment))
apply가 primitive-procedure?와 apply-primitive-procedure 프로시저로 찾고 적용할 수 있으면 프리미티브 프로시저를 표현하는 방법은 문제되지 않는다. 이번에는 프리미티브 프로시저를 리스트로 나타내자. 이 리스트에는 primitive라는 심벌과 프리미티브를 기존의 리스프로 구현해 놓은 프로시저가 들어 있다.
(define (primitive-procedure? proc)
(tagged-list? proc 'primitive))
(define (primitive-implementation proc) (cadr proc))
setup-environment는 아래 리스트에서 프리미티브의 이름과 구현 프로시저를 얻는다.
(define primitive-procedures
(list (list 'car car)
(list 'cdr cdr)
(list 'cons cons)
(list 'null? null?)
<more primitives>
))
(define (primitive-procedure-names)
(map car
primitive-procedures))
(define (primitive-procedure-objects)
(map (lambda (proc) (list 'primitive (cadr proc)))
primitive-procedures))
프리미티브 프로시저의 적용은 , 기존의 리스프 시스템을 바탕으로 만든 구현 프로시저를 인자에 적용하는 것이다.
(define (apply-primitive-procedure proc args)
(apply-in-underlying-scheme
(primitive-implementation proc) args))
We precede each printed result by an output prompt so as to distinguish the value of the expression from other output that may be printed.18
메타써클러 실행기를 돌려보기 편하도록 , 기존 리스프 시스템의 read-eval-print루프를 본딴 드라이버 루프(driver loop)를 만든다. 프롬프트를 보여주고 식을 읽으며 글로벌 환경에서 식을 계산하고 출력한다. 결과를 출력할 때 앞에 나오는 출력 프롬프트는 식의 값을 다른 출력물들과 구별하기 위해 사용한다.
(define input-prompt ";;; M-Eval input:")
(define output-prompt ";;; M-Eval value:")
(define (driver-loop)
(prompt-for-input input-prompt)
(let ((input (read)))
(let ((output (eval input the-global-environment)))
(announce-output output-prompt)
(user-print output)))
(driver-loop))
(define (prompt-for-input string)
(newline) (newline) (display string) (newline))
(define (announce-output string)
(newline) (display string) (newline))
엮은 프로시저의 환경 부분이 찍혀 나오지 않도록 user-print라는 특별한 프로시저를 사용한다. 환경에는 아주 긴 리스트가 (때로는 cycle )이 들어 있을 수도 있다.
(define (user-print object)
(if (compound-procedure? object)
(display (list 'compound-procedure
(procedure-parameters object)
(procedure-body object)
'<procedure-env>))
(display object)))
이제 계산기를 돌리기 위해 필요한 것은 글로벌 환경을 초기화한 다음 드라이버 루프를 시작하는 것뿐이다. 다음이 그 예다:
(define the-global-environment (setup-environment))
(driver-loop)
;;; M-Eval input:
(define (append x y)
(if (null? x)
y
(cons (car x)
(append (cdr x) y))))
;;; M-Eval value:
ok
;;; M-Eval input:
(append '(a b c) '(d e f))
;;; M-Eval value:
(a b c d e f)
4.1.5 데이터를 프로그램처럼 (Data as Programs)
리스프 식을 계산하는 리스프 프로그램을 볼때 비유가 도움이 될지도 모른다. 프로그램의 의미를 동작 관점에서 보는 관점은 프로그램이 어떤 추상화된 (아마 아주 큰) 기계의 설명이라고 보는 것이다. 많이 접해본 팩토리얼 계산 프로그램을 생각해보자:
(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n)))
이 프로그램을 어떤 기계의 설명이라 보면 그 기계에는 값을 빼는 부품, 곱하는 푸품, 두 값이 같은지 따져보는 부품과 함께 두 자리 스위치 (two-position switch)와 다른 팩토리얼 기계가 들어 있을 것이다. 팩토리얼 기계 속에 다시 팩토리얼 기계가 들어 있으므로, 끝없이 큰 기계가 된다.) 그림 4.2는 이 팩토리얼 기계의 흐름도인데, 여러 부품이 어떻게 맞물려 돌아가는지 나타낸다.
이 프로그램이 빼고 , 곱하고 , 값이 같은가를 검사하는 부품과 두 갈래 스위치(two-position switch) 그리고 또 다른 팩토리얼 기계를 갖는 기계의 설명으로 볼 수 있다. (이 팩토리얼 기계는 무한하다. 왜냐면 다른 팩토리얼 기계가 그 안에 들어있기 때문이다. ) 그림 4.2 는 이 팩토리얼 기계의 흐름도로 부품들이 서로 어떻게 연결되어 있는가를 보여준다.
(두갈래 스위치는 SICP한글판의 용어다. 막상 다른 단어가 떠오르는것이 없다. )
그림 4.2 추상적기계로 본 팩토리얼 기계
예를 들어,그림 4.3의 factorial 정의를 언어실행기에 주면 언어 실행기는 그에 따라 팩토리얼 계산을 할 수 있게 된다.
이와 비슷하게, 언어 실행기도 어떤 기계의 설명을 입력으로 받는 매우 특별한 기계로 볼 수 있다. 입력이 들어오면 언어 실행기는 기계 설명에 따라 스스로 설정(configuration)을 만들어 기계의 움직임을 흉내(emulate)낸다. 예로 , 그림4.3처럼 팩토리얼의 정의를 실행기에 넣어주면 실행기는 팩토리얼을 계산할 수 있게 된다.
Figure 4.3: 팩토리얼 기계를 흉내내는 언어실행기
이런 관점으로 보면, 언어 실행기는 만능기계(universal machine)와 같아서 리스프 프로그램을 설명해 놓은 다른 기계의 움직임을 모방할 수 있다. 놀라운 일이다. 이를테면, 전기 회로에서도 이와 비슷한 실행기가 있다고 치자. 그 실행기는 다른 회로, 예를 들자면 신호를 처리하는 필터 설계를 입력받아 회로로 변한다. 이때 회로의 설명을 입력으로 받은 회로 실행기(circuit evaluator)는 진짜 필터회로처럼 동작할 것이다. 그러나 , 이 같은 만능의 전기 회로는 상상을 초월할 만큼 복잡하다. 반면에 프로그램 실행기(program evaluator)가 상당히 단순한 프로그램이라는 것은 대단한 일이다.
언어 실행기에는 놀라운 모습이 더 있다. 프로그래밍 언어가 조작하는 데이터 물체와 그 프로그래밍 언어 자체를 이어주는 다리 역할을 한다는 사실이다. (Lisp로 구현된)언어 실행기 프로그램이 돌아가고 있을 때, 사용자가 식을 언어실행기에 타이프 한 후 결과를 살펴보고 있다고 하자. 사용자의 관점으로 보면 (* x x) 같은 식은 프로그래밍 언어로 언어실행기가 처리해야 하는 식이다. 그러나, 언어 실행기의 관점은 잘 정의된 법칙 세트에 맞추어 처리해야 할 리스트 (여기서는 세 개의 심벌 * x x 로 된) 일 뿐이다.
사용자 프로그램이 언어 실행기의 데이터라는 것이 혼동의 원인이 될 필요는 없다. 사실 두가지의 구분을 무시하고 eval을 프로그램에서 사용하 수 있게 함으로서 사용자가 명확히 데이터객체를 리스프의 식으로 계산할 수 있게 하는 편이 때로는 더 편하다. 많은 리스프 방언이 식과 환경을 인자로 받아 환경에 따라 식을 계산하는 프리미티브 eval 프로시저를 제공한다. 이런 경우
(eval '(* 5 5) user-initial-environment)
와
(eval (cons '* (list 5 5)) user-initial-environment)
는 둘 다 25를 돌려준다.
4.1.6 안쪽 정의 (internal defintion )
(internal defintion 을 안쪽정의로 생각하는 것도 나쁘지 않을 것 같아 SICP의 번역본 용어를 그대로 써보았다. 이장의 해석은 나와 원래의 번역팀이 조금 다르다.
그리고 이 부분은 http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme-Z-H-8.html#node_chap_6 를 보는 것이
좋다. 실제 스킴에서 사용하는 함수로 설명하고 있다.
)
우리의 환경 계산법과 메타서큘러 실행기에서 , 정의한 내용들은 차례로 실행(execute)되며, 그 환경 프레임은 정의(definition)가 일어나면 하나씩 확장된다. 새로운 프로시저 정의와 프로시저 적용을 자유롭게 섞어 쓸 수 있어서 대화형(Interactive) 프로그램 개발에 매우 편리하다. 하지만 (1.1.8절에서 보았듯이) 블록구조를 만들기 위한 안쪽정의를 조심스레 생각한다면, 환경에 하나씩 이름마다 하나씩 확장하는 방식이 지역변수local vanable를 정의에 제일 좋은 방법은 아닐 수도 있다.
다음처럼 프로시저 안쪽에 여러 정의가 들어 있는 경우를 살펴보자.
(define (f x)
(define (even? n)
(if (= n 0)
true
(odd? (- n 1))))
(define (odd? n)
(if (= n 0)
false
(even? (- n 1))))
< f의 나머지 몸체>)
프로시저의 몸체에서 odd?라는 이름이 even? 다음에 정의되어 있는데도even? 프로시저에서 odd?라는 이름을 쓰려고 한다. odd? 이름의 스코프는 f의 몸 전체이며 f에서 odd?를 define한 곳부터 시작하는 부분이 아니다. 정말로 odd? 자체는 even?에도 정의되어 있어서 even? 과 odd?는 서로 재귀적인 프로시저다. (앞으로는 상호재귀적이라고 억지로 번역해야 할지도 모른다.) 그래서 두 개의 정의에 대한 유일한 만족할 만한 해석은 even? 과 odd? 이름이 환경에 한꺼번에 추가되어야 한다는 것이다.
조금 더 일반적으로 , 블록 구조에서는 프로시저에 지역변수 이름의 스코프는 계산이 일어나는 프로시저 몸체의 모든 부분이다.
In fact, our sequential evaluation mechanism will give the same result as a mechanism that directly implements simultaneous definition for any procedure in which the internal definitions come first in a body and evaluation of the value expressions for the defined variables doesn't actually use any of the defined variables. (For an example of a procedure that doesn't obey these restrictions, so that sequential definition isn't equivalent to simultaneous definition, see exercise 4.19.)24
그런데 , 이번의 실행기에서 f를 불러 써보면 정확히 계산이 된다. 그러나, 이것은 ‘우발적인 이유로’ 그리된 것이다. 안쪽 프로시저(intemal procedure)정의가 먼저 나오기에, 모든 프로시저가 정의되기 전까지는 안쪽 정의된 프로시저가 호출(call)되는 것이 없다. 그래서 even?을 부를 때는 이미 odd?가 정의되어 있다. 사실상 안쪽정의가 먼저 나타나고 정의된 이름의 값을 구하는 식의 계산에서 정의된 이름을 실제로는 사용하지 않는다는 조건이라면 , 여러 프로시저를 순차적으로 정의해 나가는 방식을 따르거나 한 번에 정의하는 방식을 따르거나 결과는 같다. (이 규칙을 지키지 않을 때, 순차적으로 정의하는 방식과 한번에 정의하는 방식이 같은 결과를 내지 않는 경우가 있다. 연습문제 4.19를 보라)
{마지막 문장의 해석은 독자들이 다음의 원문과 비교하였으면 한다. 조금 더 명백한 해석이 있을 것같다.
In fact, our sequential evaluation mechanism will give the same result as a mechanism that directly implements simultaneous definition for any procedure in which the internal definitions come first in a body and evaluation of the value expressions for the defined variables doesn't actually use any of the defined variables. }
그런데, 안쪽에서 정의된 이름들이 진짜로 한번에 정의된 것처럼 처리하는 간단한 방법이 있다. 현재의 환경에서 식의 값을 구하려는 모든 지역변수를 미리 만들고 시작하는 방법이 있다. 이런 방법의 하나는 lambda 식의 문법 변환 방법을 사용하는 것이다. lambda식의 몸체를 계산하기에 전에 몸체 속에 있는 모두 스캔하여 안쪽정의를 없애는 것이다. let 을 사용하여 안쪽에서 정의한 변수(internally defined variables)가 만들어지고 변수들의 값을 지정문을 이용하여 지정(set)한다. 예를들어 다음과 같은 프로시저가 있다고 하자.
(lambda <vars>
(define u <e1>)
(define v <e2>)
<e3>)
위 프로시저의 문법을 고쳐 쓰면 :
(lambda <vars>
(let ((u '*unassigned*)
(v '*unassigned*))
(set! u <e1>)
(set! v <e2>)
<e3>))
*unassigned*는 특별한 심벌로 환경에서 변수 값을 찾아볼 때 값이 아직 정해지지 않은 경우에는 에러신호를 낸다.
연습문제 4.18은 안쪽 변수를 스캔하는 대안적 전략이다. 앞의 변환과는 달리 정의하려는 변수의 값을 이 변수를 사용하지 않고 계산될 수 있어야 한다는 제약이 있다.
{이번 번역의 초벌 번역은 막걸리 두병을 마시고 올리는 중이다. 술을 마셔도 머리는 돌아간다. 음..어쩌면 더 잘 돌아간다.
시간은 정말 잘 간다. 그래서 life is short .. 예전에 이광근 교수님에게 술이 취해서 했던 말이다.
그러나 술이 깨도 이말은 주관적인 진리다.
}
4.1.7 문법분석을 실행과 분리하기(Separating Syntactic Analysis from Execution)
이번에 만든 언어 실행기는 간단하지만 아주 비효율적이다. 식의 문법 분석 과정이 식의 실행하는 과정과 섞여서 나타나기 때문이다. 그래서 한 프로그램을 많이 돌리면 문법 분석을 여러 번 한다. 예로 다음과 같은 factorial 정의로 (factorial 4) 식의 값을 구해보자:
(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n)))
factorial을 부를 때마다 , 언어 실행기는 몸체가 if 식이라고 판정하고 술어(predicate)를 뽑아내야 한다. 그래야 술어 값을 계산한 후 그 값에 따라 분기할 수 있다. (* (factorial (- n 1)) n) 식이나 그 부분식 (factorial (- n 1)) 과 (- n 1)의 값을 구하는 경우에도 언어실행기의 eval은 케이스분석을 해서 식이 적용(application)이라고 판정하고 연산자와 피연산자를 추출해야 한다. 이런 분석은 비용은 비싸다. 같은 일을 되풀이하는 것은 낭비다.
따라서 문법 분석이 한 번만 일어나도록 설정하면 언어 실행기의 효율을 크게 높일 수 있다. 식과 환경을 받는 eval의 처리 과정을 두 부분으로 나눈다. analyze프로시저는 오로지 식을 받아서 문법을 분석하고 실행 프로시저(execution procedure)라고 하는 새 프로시저를 돌려준다. 실행프로시저는 분석이 된 식을 실행(executing)하는 작업을 담고(encapsulates) 있다. 실행프로시저는 환경을 인자로 취하여 계산을 완결한다. 이렇게 하여 작업을 절약한다. 왜냐하면 analyze 는 식에 대해 한번만 수행되지만 실행프로시저는 여러번 불리기 때문이다.
분석과 실행을 분리하였으니 , 이제 eval 은 :
(define (eval exp env)
((analyze exp) env))
analyze를 불러낸 결과는 실행프로시저로 환경(environment) 이 프로시저를 환경에 적용하게 된다. analyze 프로시저는 4.1.1에 나왔던 원래의 eval 과 같은 케이스분석을 한다. 분기하면서 문법만 분석만 하며 모든 계산을 다하는 것이 아니라는 점이 다르다.
(define (analyze exp)
(cond ((self-evaluating? exp)
(analyze-self-evaluating exp))
((quoted? exp) (analyze-quoted exp))
((variable? exp) (analyze-variable exp))
((assignment? exp) (analyze-assignment exp))
((definition? exp) (analyze-definition exp))
((if? exp) (analyze-if exp))
((lambda? exp) (analyze-lambda exp))
((begin? exp) (analyze-sequence (begin-actions exp)))
((cond? exp) (analyze (cond->if exp)))
((application? exp) (analyze-application exp))
(else
(error "Unknown expression type -- ANALYZE" exp))))
가장 간단한 문법 분석 프로시저는 스스로 계산되는 식을 다루는 프로시저다. 환경 인자를 무시하고 식만을 (그대로) 돌려주는 실행 프로시저가 나온다:
(define (analyze-self-evaluating exp)
(lambda (env) exp))
따옴표로 묶은 식에서는 실행 과정이 아니라 분석 과정에서 따옴표속의 식을 뽑아내어 약간의 효율을 높일수 수 있다.
(define (analyze-ouoted exP)(let ((qyal (text-of-quotation exP)))(lambda (env) q-val)) )
변수 값 찾아보기는 실행 과정에서 해야 한다. 이 일은 환경을 아는 것에 좌우된다.
(define (analyze-variable exp)
(lambda (env) (lookup-variable-value exp env)))
analyze-assignment 역시 실제 변수 값을 덮어쓰는 일은 환경을 알 수 있는 실행 때까지 미루어 두어야 한다. 하지만 assignment-value 역시 분석 도중에 (재귀적으로) 분석할 수 있다는 것은 assignment-value 식을 한 번 분석하면 되기 때문에 효율을 끌어올리는 데 중요한 도움이 된다. 이는 정의(definition) 에서도 마찬가지다.
(define (analyze-assignment exp)
(let ((var (assignment-variable exp))
(vproc (analyze (assignment-value exp))))
(lambda (env)
(set-variable-value! var (vproc env) env)
'ok)))
(define (analyze-definition exp)
(let ((var (definition-variable exp))
(vproc (analyze (definition-value exp))))
(lambda (env)
(define-variable! var (vproc env) env)
'ok)))
if 식은 술어, 결과식과 다른 결과식 모두 분석과정에서 뽑아낸다.
(define (analyze-if exp)
(let ((pproc (analyze (if-predicate exp)))
(cproc (analyze (if-consequent exp)))
(aproc (analyze (if-alternative exp))))
(lambda (env)
(if (true? (pproc env))
(cproc env)
(aproc env)))))
lambda식 분석도 효율면에서 상당한 득 을 볼 수 있다. lambda식 프로시저를 여러 번 계산하더라도 lambda의 몸체는 한번만 분석하면 되는 것의 결과다.
(define (analyze-lambda exp)
(let ((vars (lambda-parameters exp))
(bproc (analyze-sequence (lambda-body exp))))
(lambda (env) (make-procedure vars bproc env))))
begin이나 lambda 식의 몸에 나오는 시퀀스(sequence) 식을 분석하는 과정은 좀 더 복잡하다. 먼저 시퀀스의 식을 각각 분석하여 실행 프로시저를 만들어낸다. 이 실행 프로시저들을 엮어서 다시 실행 프로시저 하나를 만든다. 이 실행 프로시저는 환경을 인자로 받으며 그 환경에서 차례대로 개개의 실행프로시저를 불러낸다.
(define (analyze-sequence exps)
(define (sequentially proc1 proc2)
(lambda (env) (proc1 env) (proc2 env)))
(define (loop first-proc rest-procs)
(if (null? rest-procs)
first-proc
(loop (sequentially first-proc (car rest-procs))
(cdr rest-procs))))
(let ((procs (map analyze exps)))
(if (null? procs)
(error "Empty sequence -- ANALYZE"))
(loop (car procs) (cdr procs))))
프로시저 적용 분석에서는, 연산자와 피연산자를 분석하고 그 실행 프로시저 하나를 만든다. 이 프로시저는 (실제로 적용될 프로시저를 얻기 위해) 연산자 실행 프로시저를 부르고,(실제 인자 값을 얻기 위해) 피연산자 실행 프로시저들을 부른다. 그다음에 이들을 execute-application 으로 넘겨준다. execute-application은 4.1.1절의apply와 비슷하다. apply와 다른 점은 execute-application은 엮은 프로시저(compound procedure)의 몸이 이미 분석되었기 때문에 더 이상 분석할 필요가 없다는 것이다. 확장된 환경에서 그저 실행 프로시저를 부른다.
(define (analyze-application exp)
(let ((fproc (analyze (operator exp)))
(aprocs (map analyze (operands exp))))
(lambda (env)
(execute-application (fproc env)
(map (lambda (aproc) (aproc env))
aprocs)))))
(define (execute-application proc args)
(cond ((primitive-procedure? proc)
(apply-primitive-procedure proc args))
((compound-procedure? proc)
((procedure-body proc)
(extend-environment (procedure-parameters proc)
args
(procedure-environment proc))))
(else
(error
"Unknown procedure type -- EXECUTE-APPLICATION"
proc))))
새로 만든 언어 실행기에서 쓰는 데이터 구조, 문법 프로시저, 실행 지원 프로시저run-time support procedure는 4.1.2, 4.1.3, 그리고 4.1.4.절에 나온 것과 같다.