2010.01.31 11:53

taoi-part1 -session4

Lexical Scoping

렉시컬 스코프


이번에는 변수 사용 영역이 제한적인 인터프리터를 만들어 보려고 한다. lexical scoping of variables 라는 것으로 (알골60과 그 이후의 많은 언어들이 이 방식을 사용한다. )  lexical 이라는 용어는 지역변수(local variable)에 대한 참조관계가 프로그램에서 명백하게 파악되는 경우를 말한다. 스태틱바인딩 (정적 바인딩 ;static binding) 이라는 말도 사용되는데 변수의 결합과 참조관계가 시간에 따라 변하지 않는 것을 말한다.


어려움은 scale의 바디 (* x l) 이 계산되면서 MAPCAR의 몸체를 계산할 때 apllydpt 전달된 EVAL에서 사용가능한 ENV를 사용한다는 점이다.  그러나 우리는  (* x l)가 SCALE의 몸체를 계산할 때의 ENV를 사용하기를 원한다. 결국 우리는 (* x l)을 계산하기 위해 사용가능한 환경을 만들어야 한다.


적당한 환경의 시점은  람다식이 계산되며 &procedure가 만들어지는 시점이다. 그렇다면 이 시점에 &PR0CEDURE 객체의 뒤에 현재의 환경을 덧붙이면 나중에 프로시저 적용시에 사용할 수 있을 것이다. 사실 이렇게 하는 것이 맞다. MAPCAR 에 넘겨주기를 원하는 객체들은 수행할 계산에 필요한 텍스트만이 아니라 텍스트가 참조하는 자유변수의 의미(meaning)도 포함된다.  둘 다 필요한 것들이다. 


이제 다음의 의미구분을 생각해보자. 매우 중요한 것들이다. 


(1) The program - the text describing a procedure, e.g.in the form of an S-expression; 

(2) The procedure which is executed by thecomputer; 

(3) The mathematical function or other conceptual operationcomputed by the execution of the procedure.


렉시컬 스코프를 우리 인터프리터에 설치하려면 eval에서  람다식을  처리하는 방법을 바꾸어 현재의 환경이 &PR0CEDURE 환경의 env 가 되게 만들어야 한다.  프로시저(procedure)가 현재의 환경에 갇혀(closed)있는 것이며  &PR0CEDURE 객체는 closure 또는 closed procedure 라고 부른다.  apply 역시 변경되어 env를 따로 받아들이는 것이 아니라  &PR0CEDURE에서  변수- 값의 쌍을 새로 만들어 내도록 변경해야 한다. 이제 apply에서 env 를 인자로 사용하지 않는다. 그러니 apply의 정의도 변한다. 람다식의 처리가 조금 복잡해지기는 했으나 env의 처리는 많이 쉬워졌다.  (그림 7)


소스 코드를 보자 :


이번에는 람다에서 한줄이 바뀌었다. 환경이 람다식뒤에 태깅된다.

eval 에서  apply를 부를 때 env를  건네지 않는다. env를 건네는 방법은 람다식 뒤에 태깅하는 수 밖에 없다. 

그리고 당연히 apply에서 env를 받는 방법이 바뀐다.  함수의 몸체인 fun 을 그대로 받되 태깅된 환경에 현재의 인자를 계산한 환경만 덧 붙인다. 


이 구조는 아주 결정적인 것으로 아직도 이 방식을 사용한다. 

펑셔널 프로그래밍에서는 대 사건이 일어난것이다! 리스프 계열의 한 언어가 심각한 수준의 함수 표현과 구성능력을 얻은 것으로 

변수와 함수는 구별할 수 없게 되었다. 

SICP 에서 이야기하는 환경 계산법이라는 것의 핵심인 것이다!


먼저번에도 이야기한 것처럼 사용자들은 '(lambda (..) 대신 (lambda (..)를 사용하도록 요구받는다. 

렉시컬 스코프는 이전의 방법에서 적용하기 어렵다, 대신 새로운 방법에서는 간단한 바꿈질(tweak) 로 해결할 수 있다.

다이나믹 스코프에서 렉시컬 스코프로 전환하는  일은 프로그래밍 스타일의  큰 변화를 요한다. 과거에는 다이나믹 스코핑이 기준적인 원칙이었다.  나중에 보게 되지만 다이나믹 스코핑도 모듈성을  만들어 내는 좋은 테크닉의 하나였다.  쿼트붙은 람다를 쓰지 않아도 다이나믹 바인딩을 구현할 수 있다. 


렉시컬 스코프가 참조 투명성의 문제를 풀어주자만 역시 여기에도 치러야 할 대가가 있다.  그것은 런타임 효율성이 아니라 더 근본적인 문제다. (나중에 설명한다.)




이제 이 변경된 프로그램으로 얻은 것이 무엇인가 생각해보자.  그중 하나는 일반화된 MAPCAR 일 것이다. 프로그램 경험이 쌓이면서 MAPCAR 와 유사한 프로그램을 우리는 작성하고 작성한다.  예를들어 함수 F가 언제나 리스트를 출력하되 리스트의 리스트가 아니라 그냥 리스트 연결(concatenation of the lists)을 필요로 하 수도 있다. 또 리스트 요소들의 합이나 곱을 원할 수도 있다. 일반적인 패턴은 리스트의 각 요소를 살피고 무엇인가 조작을 가하고  요소별 조작의 결과를 다시 결합하는 것이다. 다른 것은 리스트의 중복을 체크하는 것이다. 각 요소마다 다른 카피가 따라오는 가를 체크하는 것이다. 이 패턴을 더 일반화해서 리스트를 따라오는 세그멘트의 패턴을 살피는 데 사용할 수 있다.



예전에 보았던 mapcar에 몇개의 프로시저 요소를 추가하여 새로운 함수를 만들 수 있다. 여기서는 편의상 mapx 라고 하자. 

일단은 이 예제들은 인터프리터를 만들 때까지 plt 스킴에서 돌려보자.


(DEFINE (MAPX F OP ID L)

          (COND ((NULL? L) ID)(#T (OP (F L)(MAPX F OP ID (CDR L))))))


리스트 L을 단순히 복사하는 용도로 사용할 수 있다. 


(MAPX CAR CONS '() '(1 2 3 4))

-->(1 2 3 4)


(MAPCAR F L) 을 흉내낼 수도 있다.


(define (f x) x)

(MAPx (LAMBDA (X) (F (CAR X))) CONS '() '(1 2 3 4))

-->(1 2 3 4)


(define (f x) (* x x))


(MAPX (LAMBDA (X) (F (CAR X))) CONS '() '(1 2 3 4))

-->(1 4 9 16)


그렇다면 다음같이 정의하는 일도 가능하다. 


 (DEFINE (MAPCAR F L)(MAPX (LAMBDA (X) (F (CAR X))) CONS '() L))


> (MAPCAR F '(1 2 3 4))

(1 4 9 16)


(MAPX CAR * 1 L)의 형태도 가능하다. 
 
(MAPX CAR * 1 '(1 2 3 4))
-->      24
 (MAPX CAR + 0 '(1 2 3 4))
-->      10

중복되는 요소를 세는 것도 가능하다. 
(MAPx (LAMBDA (X) X)(LAMBDA (Y N) (COND ((MEMBER (CAR Y) (CDR Y))(+ N 1))(#T N))) 0 '(1 2 3 4 3 ))

(member를 정의하면 이번에 만든 인터프리터에서도 가능하다. 숙제로 ^^)
 
이제 "리스트의 합을 내는" 함수를 만들어보자.  CAR + 0 을 항상 만드는 것보다는 다음과 같은 방식이 나을 것이다.

(DEFINE (MAPGEN F OP ID)(LAMBDA (L) (MAPX F OP ID L)))

((MAPGEN CAR + 0) '(1 2 4))
7
물론 같은 일을 다음과 같이 할 수도 있다. 

(DEFINE (SUM L)(MAPX CAR + 0 L))
> (sum '(1 2 3))
6

그러나 MAPGEN은  이런 프로시저들에 대한 일반적인 구성자로 재미있는 일반화나 추상화의 본질을 보여준다.  (MAPGEN CAR * 1)은 곱셈의 일반화이며 나머지도 마찬가지다.  즁요한 점은 이제 다른 프로시저를 구성하는 프로시저를 만들 수 있다는 것이다. 

예를 들어  미분이나 차분을 구하는 함수를 만들어보자. (고등학교때 배운 내용이다.)




아직 인터프리터를 다 손보지 않았으므로 그냥 plt스킴에서 돌려보자.

(define (derivative f dx)  (lambda (x) (/ (- (f (+ x dx)) (f x)) dx)))
(derivative sqrt .001)
#[closure arglist=(x) 1472de0]

이 클로저는 x를 기다린다. 이를테면 7에 대한 계산 값은 다음과 같다.
((derivative sqrt .001) 7)==0.188975487620979

한 줄짜리 코드로 이 정도 일을 할 수 있다는 것은 놀랍다. 
람다의 사용때문에 다이나믹 스코프를 사용하는 인터프리터에서는 이런 방식으로 프로시저를 만들어 낼 수 없다. 

당시에는 따로 FUNARG 디바이스스라는 것을 만들어서 사용했다.
이 이야기는 매카시의 History of LISP에 나오며 알골류의 언어가 렉시컬 스코프를 구현할 때 ,
리스프의 구현자였던 스티브 러셀이 또 한번 작업을 해주었다고 적고 있다.
그러나 오랜동안 구현이 거의 20년이 다 되어 갈때까지 이 문제를 집요하게 추적한 팀은 없었고 
스킴에서 성과가 나왔다.  

요체는 람다에 현재의 환경을 덧 붙이는것이 문제 였던 것이다. 
결국 이 문제는 오랜 고민끝에 환경을 해석하는 시점이 언제인가에 대한 답변이고 했다.

문제를 지적한 사람은 무척 많으며 그 중에 유명한 글은 Joel Mose의 글이다.
The function of FUNCTION in LISP or why the FUNARG problem should be called the environment problem


프로시저는 이제  데이타 객체처럼 사용할 수 있다. (요즘은 당연한 말이지만 당시로서는 참신했던 아이디어다.)
CONS 를 예로들면 CONS의 유일한 규정은 다음과 같은 성질이다. 

(CAR (CONS  A  B))= A 이고 (CDR (CONS A B))= B 이다. 

CONS 는 Hewitt 같은 사람의 아이디어를 따르자면 필요에 따라 값을 내놓는 프로시저로 볼 수 있겠다. 

(DEFINE (CONS A D)
       (LAMBDA (M) 
          (COND ((= M 0) A)((= M 1) D))))


(DEFINE (CAR X) (X 0))
(DEFINE (COR X) (X 1))

이 프로시저는  동작한다. 


그러나 프리미티브 = 가 쓰였다, 보다 더 근원적인 코드는 

(DEFINE (CONS A D) (LAMBDA (M) (M A D)))
(DEFINE (CAR X) (X (LAMBDA (A D) A)))
(DEFINE (CDR X)(X (LAMBDA (A D) D)))

(LAMBDA (A D) A) 와  (LAMBDA (A D ) D)는 데이터셀렉터처럼 사용되었다. 이 람다 프로시저들이 M으로 치환되며 계산된다.)

CONS는 새로운 프로시저를 위한 하나의 프로토타입처럼 쓰였다. 
아직 코드로 구현하지는 않았지만 이번에 사용한 방식은 모든 문제를 다 해결한 것처럼 보인다. 

스틸과 서스만의 논평은 이 번의 구현에서 실제로 얻은 것은 참조투명성이지만  표현력은 약한 언어라는 것이다. 

다음번에는 이런 문제를 다룰 것이다.
Trackback 0 Comment 0


티스토리 툴바