-
The Function of FUNCTION in LISP or Why the FUNARG Problem Should be Calledthe Environment Problem카테고리 없음 2021. 4. 7. 01:04
funarg backup
2010-02-28 (일) 10:22
보낸사람안윤호<mindengine@naver.com>받는사람<mindengine@naver.com>
The Function of FUNCTION in LISP or Why the FUNARG Problem Should be Called
the Environment Problem
by
Joel Moses*
워낙 고전인지라 이 문헌도 정리하지 않을 수 없다. 거의 풀번역인데 번역의 질은 높지 않다.
별로 어렵지 않은 글이지만 사람들에게 많은 영감을 주었고 스킴을 만든 팀에게도 마찬가지였다.
스킴은 최초로 이 문제를 어느 정도 해결했다.
나중에 시간이 되면 이 문제에 주석을 달아 비교할 것이다.
taoi를 만지작거리고 있는지라 예전보다는 문제 집중에 대한 포스가 강해졌다.
연휴를 이용하여 정리하기로 .. 컨티뉴에이션 문제에 대해서는 조금 더 정리가 되고 있다.
그 다음의 작업은 John Allen의 Anatomy of Lisp에서 필요한 부분을 조금 따오는 일일 것이다.
요약
여러 강력한 프로그래밍 언어들이 함수안의 자유변수에 어떤 값을 지정해야하는 결정해야 하는 공통적인 문제가 떠오른다. 이 문제를 풀기위한 다른 구현방법이 고려될 것이다. 논의는 리스프구현에 집중될 것이며 많은 리스프 구현이 원형의 리스프 1.5 보다 일반적이지 않은지에 대해서도 지적할 것이다. 리스프에 대해 친숙하지 않은 독자들도 이 글을 읽는데 어려움이 없을 것이다. 왜냐면 우리는 가능한 알골과 비슷한 용어로 접근할 것이기 때문이다.
대부분의 컴퓨터 프로그래머들은 인자와 로컬변수의 값을 유지하기 위해 스택을 사용하는 일에 익숙하다. 스택에는 스택의 끝을 가리키는 스택포인터라고 부르는 인덱스 레지스터가 있다. 스택의 변수 값과 다른 정보들은 (구현에 따라) 스택포인터의 값들을 가감하면서 접근할 수 있다. 우리는 함수에 진입할 때 스택이 아래쪽으로 자라난다고 가정한다. 그래서 그림1에서는 함수 f 로 진입하기전 , 인자 x를 가지고 f 에 바로 진입한 후와 f 가 값을 돌려준 후의 스택포인터를 보여주고 있다.
스택의 기전을 이용하면 앞서 말한 것처럼 인자와 지역변수의 값을 쉽게 얻을 수 있다. 그러나 자유변수(free variables)의 경우에는 아주 복잡해진다. 자유변수는 함수의 인자나 지역변수가 아니다. 예를 들어 함수 f가 다음과 같이 주어진다고 하자.
define f(x) =
begin;
if a>0 then return x
else return -x;
end;
a 는 자유변수로 사용되었다. 물론 이 함수가 의미가 있으려면 변수 a 는 바운드되어 있아야 한다. f 를 부르거나 f 를 부르는 함수 g 를 부르는 것과 같은 함수나 블록에 바운드 되어 있어야 한다
자유변수의 사용은 아주 강력한 컴퓨테이션 아이디어다. (The use of free variables is a very powerful computational idea.) 많은 경우 자유변수를 사용하지 않고 추가적인 인자를 부여하는 것으로 문제를 피할 수 있다. 어색한 해결책이다. 그리고 서브루틴 콜이 수많은 인자를 저장해야 하는 이유로 비효율적이다. 함수안에서 변수의 값을 치환하는 생각역시 아주 비효율적이다. 왜냐면 자유변수와 그렇지 않은 변수를 구분해야만 하기 때문이다. 두 가지 방법 모두 자유변수의 값을 변경하지도 못하고 원하는 효과를 얻지도 못한다.
함수가 자유변수를 갖거나 자유변수를 사용하는 함수를 부를 때 함수 값은 인자(argument) 에 의해 전적으로 결정되지 않는다 그 이유는 자유변수의 영향을 받기 때문이다. 그래서 계산( computation) 을 완전하게 설명하려면 함수와 그 인자 그리고 함수의 자유변수가 결정되는 환경 역시 설명해야 한다. (외부로부터의 입력도 계산 결과에 영향을 주니 입력도 환경의 일부로 생각해야 한다.) 스택은 환경을 관리하는 한 방법이다. 이 글의 목적은 환경을 관리하는 일에 무척 조심해야 함을 보이는 것이다.
계산을 더 진행하기 위해 필요한 적당한 환경을 유지하는 일이 점점 어려운 일이라는 것을 알게 될 것이다. 아마도 가장 간단한 상황은 자유변수가 블록구조의 프로그램안에 나타나는 것이다. (Algol 식의 )블록 하나를 가정하고 그 안에 하나 또는 그 이상의 블록이 있다고 하자. 내부의 블록에 나타나는 자유변수는 접근과 변경이 모두 쉽다. 그 이유는 컴파일러가 스택의 자유변수의 위치를 쉽게 알 수 있기 때문이다. 그래서 아래의 토막 프로그램의 자유변수 a 는 쉽게 접근할 수 있다. 바인딩이 일어나는 장소에서 렉시컬 의미에서 가까운 곳에 위치하기 때문이다. (because it is used lexically near the place where it is bound.)
이제 자유변수가 재귀함수 안에서 사용되는 경우를 고려해보자. 이제 스택 안의 어디에 있는지를 알기 어려워졌다. 변수는 렉시컬 의미에서 함수 호출과 가까운 곳에 바인딩이 일어났는데도 그렇다.
위에서 언급한 경우들을 다루기 위해 자유변수의 값을 유지하는 방법은 여러 가지다. (계산 환경도 마찬가지) 사용된 방법들은 시간을 더 많이 요하는 문제가 있다. 어떤 접근법은 자유변수에 접근하기는 쉬우나 변수가 들어있는 블록을 들어가고 나오는데 시간적 비용이 많이 들어간다. 요즘의 리스프 구현자들이 좋아하는 방법이다. 우리는 이 방법은 “얕은 접근(shallow access)”이라고 불러야 한다.
다른 접근법은 자유변수가 바인드된 블록을 들어가고 나오기는 쉬우나 변수를 찾는 일은 상대적으로 비싸다. 리스프의 고전적인 "alist" 구현에 사용되고 상당히 많은 Algol 시스템도 비슷한 방법을 썼다. 이를 “깊은접근” 방법이라고 부를 것이다. 둘다 자유변수에 접근하고 변경을 일으킬 수 있다. 두 방법 모두 접근시간과 변경시간은 대략 비슷하다.
이제 “얕은접근”을 먼저 생각해보자. 이 방법에서는 자유변수의 값이 메모리를 한번 접근에서 구해진다. 자유변수의 현재의 값은 스택에서 판정하기 어려운 위치 (difficult-to-determine)에 있을 수 있으므로 현재 값을 위한 특별한 셀(special cell)이 사용된다. 요즘의 많은 리스프 구현에서 이 특별한 셀은 아톰구조의 특성(property of the atom structure)처럼 저장되며 자유변수에 대해서 특별한 구조다. 이 특별한 셀들의 적절한 값을 유지하기 위해 변수나 인자들이 지역적(local)인 함수나 블록에 진입할 때마다 추가적인 작업이 반드시 필요하다. 이런 블록에 진입할 때마다 스택에 있는 스페셜 셀들의 오래된 값이 어디서부터 연유했는가에 대해 알수 있을 충분한 정보와 함께 저장되어야 한다. 이런 함수나 블록을 떠날 때에는 스페셜셀의 값들을 다시 스택에 저장하는 일을 잊지 말아야 한다.
“깊은 접근“ 방법은 자유변수의 가장 최근의 값을 찾기 위해 스택의 윗방향으로 찾아 올라간다. 이런 탐색은 자유변수가 아주 멀리 위에 있으면 아주 깊고 느릴 수가 있다. 그러나 이 방법은 추가적인 스페셜 셀이 필요치 않다는 장점이 있다. 또 이 방법은 나중에 알게 되겠지만 ”얕은 접근“보다 훨씬 편하고 유연하게 자유변수를 사용하도록 허용한다.
리스프의 "alist" 구현은 앞에서 이야기한 것 처럼 “깊은접근”의 한 예이다. "alist"는 바인딩이 일어난 이전의 모든 변수의 이름과 값에 대한 포인터를 갖고 있다. 변수의 이름은 리스트 쌍의 왼쪽에 값은 오른쪽에 있다. 따라서 아래에서 처음 만나는 값은 a 이며 값은 5이다.
어떤 Algol 구현에서는 블록에 대한 지역변수는 선형 스택에서 연속적인 위치에 바인딩된다. 또한 스택안에는 어떤 포인터가 있어 블록에 대한 지역적 값에서부터 더 상위의 블록들에서까지 (결국 자유변수가 바인딩된 블록에 이를 때까지 ) 값들을 가져올 수 있도록 해준다.
(공사중)