해커 문화의 뿌리를 찾아서 Part 2: 원시 리스프의 재구성

안윤호 mindengine@freechal.com 필자는 아마추어 리눅스 커널 해커였으며 최근에 팹(Fab)이라는 책을 번역 출간했다. 컴퓨터의 여러 분야에 관심이 많고 컴퓨터와 문화의 인터페이스에도 관심이 많다. 2007년 5월 8일

연재순서
1회(2007년 4월): 리스프가 탄생하기까지
2회(2007년 5월): 원시 리스프의 재구성

리스프(LISP) 개발 초기 역사에 대해 중요한 문서는 매카시 자신의 History of LISP이며 다른 하나는 H.Stoyan이 정리해 놓은 리스프의 역사로 둘 다 매카시의 홈페이지(http://www-formal.stanford.edu/jmc/history)에서 찾아볼 수 있다.

History of LISP에서 매카시는 너무 가벼운 마음으로 일을 진행한 것을 한탄하고 있다. 튜링머신보다 리스프가 더 좋으려면 만능 리스프 함수가 있어야 하고 이 함수는 튜링머신으로 적는 것보다 더 깔끔하고 이해하기 쉬워야 했다. 이것이 바로 리스프 함수 eval[e, a]이었다. 여기서 e는 리스프 식이며, a는 변수에 적어 넣을 값을 가지고 있는 리스트다. 매카시는 eval을 만들면서 리스프 함수를 데이터처럼 나타내는 방법을 만들어야 했고 이 표기법은 표기를 위한 목적으로 생각했을 뿐 실제로 리스프 프로그램을 위해 사용되리라고는 생각하지 못했다. 매카시가 함수 eval을 구현하기 위해 그리고 새로운 언어를 위해 할 일은 많았다. 일의 중요한 진척의 하나로 함수가 함수의 인자로서 사용될 수 있는 표기법을 논리적으로 완결하는 일도 필요했다. 매카시가 만든 일들 가운데에는 원래의 람다(lamda) 표기법에 없었던 것들도 있었다. 이를테면 Label 표기법 같은 것들이다.

Stoyan의 문서는 매카시의 리스프 문헌을 중심으로 재구성한 것이다. The Influence of the Designer on the Design -- J.~McCarthy and Lisp(http://www8.informatik.uni-erlangen.de/html/lisp/mcc91.html)라는 제목으로 찾아볼 수 있다.

지난 회에 설명한 리스프의 기본적인 논문은 매카시가 쓴 Recursive Functions of Symbolic Expressions and their Computation by Machine의 Part 1이었다(Part 2는 끝내 나오지 않았다). 이 글은 지금 봐도 참신함을 잃지 않을 정도로 잘 정리된 글이다. 몇 년에 걸쳐 다듬고 매만진 글이기 때문인지도 모른다.

매카시는 이 글과 그 전의 아이디어를 조수에게 보여주었다. 글을 읽던 매카시의 대학원생이었던 스티프 러셀(Steve Russel)은 예상보다 총명했다. 러셀은 eval 함수가 리스프의 인터프리터로 사용될 수 있다는 것을 깨달았다. 결국 리스프를 IBM 704에서 구현했다(나중에 Space War라는 첫 번째 컴퓨터게임을 만들기도 한다).

컴퓨터로 프로그래밍과 디버깅을 거듭하자 무엇인가가 나왔다. 그리고 사람들은 인터프리터로 만든 언어를 갖게 되었다. 갑자기 리스프가 구현된 것이다. 인터프리터가 예상치 못하게 빠르게 나옴에 따라 언어의 형태가 갑작스럽게 초기 상태에서 고정되었고 원래의 논문 ‘Recursive Function...’에서 별생각 없이 만든 결정들이 언어의 요소가 되었다. 그중에는 나중에 별로 좋은 생각이 아니었다는 것으로 밝혀진 것들도 있었으나 대부분은 그대로 살아남았다. 그만큼 리스프는 빠르게 수용되었다. 그리고 매카시 자신이 리스프가 가능한 것이라고 믿었던 것이 아니기 때문에 리스프를 발명한 것이 아니라 발견했다고도 말한다.

매카시는 History of LISP에서 당시 자신이 람다함수에 대해 알기는 했지만 불완전하게 이해하고 있었다는 사실도 인정했다. 처음에 리스프는 람다함수의 불완전한 표기법을 채택하고 있었고 점차 완전한 것으로 변해갔다. 이미 리스프가 만들어진 상태에서 매카시는 몇 가지를 고쳐보려고 했지만 때는 늦었다. 리스프를 실제로 사용하는 사람들과 리스프를 만든 매카시의 생각의 차이가 커져갔고 사용자 그룹의 힘이 더 커져감에 따라 매카시는 언어에 대한 통제를 포기하고 자신의 주제로 돌아가 버렸다. 하지만 리스프를 만든 것은 분명 매카시였다.

위로

리스프 인터프리터의 구현

이번 회의 주제는 ‘Recursive Functions ...’을 폴 그레이엄이 요즘의 리스프로 다시 구성한 것을 설명하는 것이다. 즉 리스프의 재구성이다. 50년이 다 되어가는 옛날 리스프를 다시 구현해 본다는 것이 이상하기는 하지만 인터프리터를 살펴보는 일이 리스프를 이해하는 가장 좋은 방법이며 전통적인 방법이다.

리스프 개발은 사람들이 원시적인 인터프리터를 만들고 그 위에 다른 리스프를 구현하며 발전했다. 사실 리스프의 역사에는 어떤 리스프 인터프리터 위에 다른 리스프가 올라가고 또 다른 것이 그 개량판 위에 올라간 역사가 있다. 얼마나 복잡한 층위를 만들었는지는 아무도 모른다. 이런 방식의 인터프리터를 메타서큘러 인터프리터라고 한다. 처음엔 해커들은 자신의 리스프를 만들었고(라이브러리보다 언어를 만드는 편이 더 빨랐다. 간단했기 때문이다) 이들 중에서 남는 것은 점차 줄어들었다. 아무래도 효과적인 구현들만이 남았기 때문이다. 결국에는 몇 개로 줄어들었다. 하지만 요즘도 리스프 교재에서 메타서큘러 인터프리터를 만드는 일은 중요한 단계로 남아있다. 언어 자체의 이해가 증가하기 때문이다. SICP는 4장 전체를 인터프리터에 바치고 있다.

맨 처음 나온 리스프 인터프리터는 스티브 러셀이 IBM 704에 만든 구현이다. 그 구현은 펀치카드 방식의 IBM 704를 손으로 어셈블하면서 만들어졌고 당시의 자료들 또한 남아있다. 러셀은 나중에 엄청나게 번거로운 작업이었다고 회고했다. 펀치카드로 작업하는 배치 방식 코딩과 디버깅은 쉬운 일이 아니다.

얼마 후 리스프는 DEC의 PDP-1 컴퓨터로 이식되었다. PDP-1의 인터랙티브한 환경에서 리스프가 돌아간다는 것이 알려지자 곧바로 컴퓨터에 빠져 사는 사람들이 나오게 되었다. 이들이 바로 해커들이다. 해커리즘의 근본적인 도구는 매카시의 논문을 스티브 러셀이 작업(해킹)하여 탄생했고 DEC 초기 기계들을 중심으로 MIT에서 해커들이 해킹하는(다듬는) 형태를 통해 발전했다. 스탠포드나 BBN 같은 회사들에서도 중요한 리스프 변종들이 나오기 시작했다.

매카시에게 기계적 지능 구현을 위해 가장 중요한 것은 포멀리즘(형식주의)이었다. 수학의 형식을 빌어 알고리즘으로 문제를 푸는 일은 문제를 기계가 풀 수 있는 형식(표기법)과 기능을 만드는 일이다. 리스프는 중요한 진보였다. 동일하지는 않지만 처치의 람다 계산법을 사용하여 범용의 튜링머신을 만들어 낸 것이기 때문이다. 포멀리즘은 기계가 다룰 수 있는 형태로 표현할 수 있다면 기계가 반복적인 계산을 되풀이하여 정확한 답을 줄 수 있기 때문에 형식과 형식의 체계는 매우 중요하다. 또 이 형식주의는 사람 손으로 문제를 푸는 것보다는 기계에 더 적합한 형태의 연산이라는 것이 매카시의 생각이었다. 정확한 형식으로 표현할 수 있다면 기계가 못 풀 문제도 없다는 것이다.

초기 인공지능은 이렇게 소박한 기반 위에서 출발했다. 물론 기계가 풀 수 있을 정도로 간단한 형식으로 바꾸는 것이 쉽지 않다는 것을 발견하는 과정이 곧 뒤따랐다. 매카시가 차용한 람다 계산법이라는 것은 일종의 일반화된 함수의 치환으로 생각할 수 있다. 그런데 이 간단한 치환으로 많은 것들을 할 수 있다. 기호와 기호 표기의 포멀리즘이 지배하는 곳에서는 더욱 그렇다. 기계적으로 기호를 치환하는 것으로 아주 많은 일을 할 수 있다. 인공지능도 그런 일들 가운데 하나다.

인공지능의 또 다른 개척자 마빈 민스키는 프로그래밍의 다른 측면을 보았다. 앞으로 필요한 인공지능과 관련하여 프로그램들의 개발이 많이 필요할 것이며 이 프로그램들은 컴퓨터에 빠져있는 해커들이 아니면 만들어낼 수 없다는 것을 본 것이다. 민스키는 학자들의 엘리트주의나 권위주의적인 기업의 기술 문화가 아닌 해커 문화의 일면을 보았다. 해커들의 지성의 다른 측면이었다.

민스키는 자유방임적인 놀이터의 주인 역할을 자처했다. MIT의 인공지능 연구소에 투입된 자금과 장비를 이용해 해커들을 고용하고 이들이 마음껏 프로그래밍을 할 수 있는 환경을 만들었다. 해커들은 대학원생 출신이거나 다른 곳에서 들어오기도 했다, 급료는 높지 않았다. 오로지 해킹이라는 일 자체가 목표였고 컴퓨터를 마음대로 쓰는 것으로 동기는 충분히 높았다고 전한다. 이런 것들을 좋아하는 사람들에게 장난감을 던져주고 그들이 원하는 것을 하게 내버려두는 것이 민스키의 아이디어였다. 당시의 인공지능 연구소에는 할 일이 많았다. 이 놀이터에서 해커들은 마법사로 볼 수 있고 착한 놀이터 주인인 민스키가 부탁을 하면 무엇이든지 만들어 주곤 했다.

다만 해커들의 놀이에는 스스로 정한 엄격한 문화와 기준이 있었다. 당시로서는 이런 놀이터는 인공지능 연구소가 유일했다. 이들의 개성과 배경은 모두 달랐다. 이윽고 특이한 문화가 탄생했다. 그 특징의 하나인 강한 개성과 자유, 그리고 이들과 양립하는 고도의 지성이 있었다. 스티븐 레비의 『해커』라는 책은 당시의 분위기를 전한다. 이런 분위기를 유지하는 것이 얼마나 어려운가를 상상하는 것은 오늘날에도 어렵지 않다. 1960년대에는 요즘보다 더 어려운 일이었지만 해커들의 놀이터는 실제로 여러 해 동안 존재했고 고도의 지적 기준과 심미안, 몰입과 창조의 와중에서 프로그램들과 문화가 태동했다. 스티븐 레비에 의하면 이런 일들은 결국은 해커들의 자기 표현이었다. 일종의 창조적 예술이라고 본 것이다.

말이 길어졌지만 그 때 이들이 진지하게 사용했던 언어는 리스프였다. 지금으로 보면 초라한 하드웨어를 가지고 해커들은 이 리스프로 인공지능 연구소에서 원하던 것들을 (거의) 무엇이든지 만들어 주는 마술을 부렸다. 인공지능의 유명한 프로그램들이 빈약한 기계에서 리스프로 만들어졌다. 당시에는 뛰어난 사람들이 리스프에 빠져 있었고 리스프를 바탕으로 만든 언어들도 많으며 리스프에서 많은 영감을 받기도 했다. 리스프는 처음부터 언어라기보다는 수학적 표현이나 알고리즘에 더 가까웠던 것이다.

위로

구현하기 전에 고려할 것들

이번 회의 주제가 매카시의 ‘Recursive Function ...’을 이해하는 것이므로 다시 원래 주제로 돌아가 보자. 지난 글은 7개의 기본 연산자를 만드는 것으로 끝났다. 정말 이 7개의 식으로 인터프리터를 만들 수 있을까? 이것이 이번 주제다. 답은 미리 말했듯이 “만들 수 있다”이다.

문제는 리스프에 접할 기회가 적었기 때문에 관심이 있다고 해도 리스프를 전혀 모르면 설명이 애매하다고 느낄 수 있는 부분이 있어 여기에 대해 약간의 보충 설명이 필요할 수 있다. 보충 설명을 위해 『A Gentle Introduction to Symbolic Computation』(http://www.cs.cmu.edu/~dst/LispBook/index.html)이라는 훌륭한 책이 있다. 책의 앞부분을 읽고 그림을 보고 있으면 보조 자료로 충분하다. 하지만 필자는 가급적 설명을 쉽게 하려고 애쓸 것이다. Peter Siebel의 『Practical Common LISP』(http://www.gigamonkeys.com/book/)도 쉽게 읽을 수 있는 책이다. 이 정도면 역시 충분할 것이다.

그리고 리스프를 실행할 수 있는 적당한 환경이 있어야 한다. 요즘은 LispWorks나 Franz Lisp 같은 곳에서 윈도우와 리눅스용 리스프를 다운로드할 수 있으므로 문제가 될 것이 없다. 그 외에도 많은 리스프 구현이 있으며 소스까지 공개된 것들도 있다. 하지만 이번 설명에서 반드시 리스프가 필요한 것은 아니다. 종이와 연필로도 풀어볼 수 있다.

리스프에서 식(expression)이 리스트일 때 첫 번째 요소가 연산자(operator)이면 나머지 요소들은 인자(argument)로 작용한다. 이를테면 2+3은 (+ 2 3)으로 표시한다. 연산자는 +이고 2와 3은 인자인 것이다. 먼저 지난번에 설명한 7개의 연산자를 다시 적어 보자.

1. (quote x)는 x를 되돌리며 ‘x와 같다.
2. (atom x)는 x가 아톰이라는 기본형의 원소이거나 빈 리스트이면 t를, 아니면 ()를 되돌린다(t는 참을 의미하고 ()는 거짓을 의미하는 값이라고 하자).
3. (eq x y)는 x와 y의 값이 같으면 t를, 아니면 ()를 되돌린다.
4. (car x)는 리스트 x의 첫 값을 되돌린다.
5. (cdr x)는 리스트 x의 첫 값을 제외한 나머지 값을 되돌린다.
6. (cons x y)는 x로 시작하고 리스트 y의 값들이 따라오는 리스트를 돌려준다.
7. (cond (p1 e1) ... (pn en))은 p1부터 시작하여 p로 시작하는 식이 참이 나올 때까지 계산한다. 만약 pi에서 참이 나오면 해당하는 식 ei를 전체 cond의 값으로 되돌려준다. 끝까지 참이 나오지 않으면 빈 리스트를 되돌린다.

먼저 2번의 atom이라는 연산자를 살펴보자. 리스프에서 어떤 식이 atom이라는 것은 리스트가 아니라는 것을 의미한다. 기호 아톰(atomic symbol)은 어떤 기호가 atom의 성질을 갖는다는 것을 의미한다. 또한 리스프의 S-식(S-Expression)을 다음과 같이 정의한다. 우선 S-식의 표현을 리스프에서 의미를 부여한 기호인 ( ).를 사용하여 나타내기로 하자.

1. 기호 아톰은 S-식이다.
2. 만약 e1과 e2가 S-식이라면 (e1 . e2)도 S-식이다.

정의는 A, B, AB와 같은 기호는 당연히 S-식이다. 그러므로 정의 2에 의해 (A . B)도 S-식이며 ((AB . C) . D)도 기호식이다. 그러므로 리스프에서는 기호 아톰과 리스트 두 종류의 S-식 형태만이 존재한다. 따라서 (atom x)가 참이면 x는 리스트가 아닌 S-식, 바로 기호 아톰이다.

이제는 4, 5, 6번을 조금 자세히 살펴보자. 이들은 리스트를 만들고 리스트를 조작하는 핵심적인 기능을 한다. 리스프가 LISt Processing이라는 것을 생각하면 핵심적인 조작이다. 모든 일들은 CONS 셀(Construct Cell)이라는 자료구조를 중심으로 일어난다.

CONS 셀의 왼쪽은 CAR라고 부르며 오른쪽은 CDR이라고 부른다. 리스트 구조와 리스트로 나타내는 식의 의미는 매카시의 ‘Recursive Function...’를 보아야 할 것이나 여기서는 이것으로 충분하다(초기 IBM 704와 그 후속 기종은 36비트로 15비트씩을 CAR와 CDR에 할당했다. CAR와 CDR은 어셈블러의 매크로 함수 이름이었다고 한다).

가장 기본적인 식은 CONS다. CONS는 두 개의 인자를 취해 이들을 연결한다. 그래서 (cons 1 2)는 (1 . 2)를 리턴한다. 앞의 cons 셀에서 car는 1 이고 cdr은 2이다. 따라서 다음과 같은 식이 가능하다.

  

(car (cons 1 2)) ==> 1
(cdr (cons 1 2)) ==> 2

리스트는 다음과 같이 표현된다. 이를테면 3개의 요소로 구성된 리스트 (1 2 3)이 있다고 하자. 그러면 이 리스트의 실제 모양은 아래 그림과 같다.

(1 2 3)을 만들고 조작하는 방법은 재귀적이다.

  

(cons 1 (cons 2 (cons 3 nil))) ==>(1 2 3)

위 식의 car를 구하면 다음과 같다.

  

(car  (cons 1 (cons 2 (cons 3 nil))) ) ==>(car (1 2 3))==> 1 

그림에서 상상할 수 있듯이 리스트 (1 2 3)의 car는 1이다. (1 2 3)의 cdr을 구하면 다음과 같다.

  

(cdr  (cons 1 (cons 2 (cons 3 nil))) ) ==> (cons 2 (cons 3 nil)) ==>(2 3)

첫 번째 박스의 CDR이 가리키는 포인터는 2와 3의 리스트인 것이다. 앞 식의 car를 다시 구한다면 다음과 같다.

  

(car (cdr (cons 1 (cons 2 (cons 3 nil))) )) ==> (car (2 3)) ==> 2 

이런 식으로 문제를 해결한다. 함수형 스타일(functional style)이다. 이보다 더 복잡한 것들도 재귀를 이용한 함수형 방식으로 처리할 수 있고 인터프리터가 만들어내는 복잡한 치환도 마찬가지다. 복사도 할 수 있고 리스트를 뒤집을 수도 있다. 리스트 안의 리스트와 같은 중첩된 표현도 가능하다. 위의 car와 cdr의 조합들은 많이 사용되는 것들이라 아래와 같은 표기법으로 사용되기도 한다.

  

(caar list) === (car (car list))
(cadr list) === (car (cdr list))
(cadadr list) === (car (cdr (car (cdr list))))

Root of LISP에 나오는 리스트 예제들도 간단하다.

  

(car '(a b c)) ==>a 
(cdr '(a b c)) ==>(b c) 
(cons 'a '(b c)) ==>(a b c) 
(cons 'a (cons 'b (cons 'c '()))) ==>(a b c) 
(car (cons 'a '(b c))) ==>a
(cdr (cons 'a '(b c))) ==>(b c) 

마찬가지로 다음과 같다.

  

(cadr '((a b) (c d) e)) ==>(c d) 
(caddr '((a b) (c d) e)) ==>e 
(cdar '((a b) (c d) e)) ==>(b) 

하나 더 남아있다. list라는 연산자를 이용하는 것이다. (list e1 ... en)은 결국 (cons e1 ... (cons en '()) ... )과 같은 형식이다. 예를 들면 아래의 두 식은 같은 값을 되돌려준다.

  

(cons 'a (cons 'b (cons 'c '()))) ==>(a b c) 
(list 'a 'b 'c) ==>(a b c) 

아직까지는 특별히 이해에 어려울 것이 없는 것 같다.
7번의 cond도 간단하다. (cond (p1 e1) ... (pn en))은 p라는 술어(predicate)를 차례로 계산하여 참이 나올 때까지 계산하고 참이 나오면 pi에 대한 ei를 계산하여 되돌린다. 만약 참이 나오지 않으면 ‘()를 되돌린다(빈 리스트 ’()를 일단 false로 생각하자). 매카시의 책에서는 (p1 -> e1, ... , pn -> en)으로 표기했다. 예를 들면 (1 < 2 -> 4, 1 > 2 ->3)은 4를 되돌린다.

리스프에서도 다음과 같은 예제를 보면 별다른 것이 없다. 'a와 ‘b가 같지 않으므로 두 번째 술어부를 계산하고 ’a가 atom이므로 second가 나온 것이다. 만약 ‘a가 atom이 아니었으면 두 번째 술어부도 참이 아니므로 끝에 도달하여 ’()를 리턴하였을 것이다.

  

(cond ((eq 'a 'b) 'first) ((atom 'a) 'second)) 
second 

위의 연산자 중에서 quote와 cond를 제외하고 나머지는 먼저 연산자가 계산되고 나서 인자들이 계산된다. 이런 연산자를 함수(function)라고 부른다. 함수 표기법에 대해 매카시의 의견은 매우 간단했다(요즘은 당연히 여겨지는 것이 당시엔 나름대로 중요한 결정이었다).

사람들이 y2+x와 같은 form을 함수와 구별 없이 사용하는 경향이 있는데 알론조 처치는 앞의 식을 form이라고 불렀고 form이 함수가 되려면 인자들의 값이 form에서 어떤 값과 일치하는지 알 수 있어야 한다는 것이다. 처치가 고안한 표기법은 E가 form이라고 할 때  ((x1 ... xn), E)로 표기하면 인수의 차례는 x1에서 xn까지 일치해야 한다는 것이다. 람다는 일단 이런 표기법이라고 할 수 있다.

리스프에서 함수는 (lambda (p1 ... pn ) e)로 표시하며 p 1 ... pn은 인자(parameters)이고 e는 식이다. 함수 호출(function call)의 일반적 형태는 다음과 같다.

  

((lambda (p1... pn ) e) a1 ... an) 

여기서 a1 ... an의 식들을 모두 계산하고 난 후 식 e를 계산한다. e 식을 계산할 때 pi는 해당하는 계산된 ai의 값과 일치한다. a1부터 an까지를 모두 계산하여 적용시키기 때문에 값을 전하는 것이다(call by value). 이름이나 포인터만을 전하는 것과 다르다(call by name). 이 문제는 나중에 다시 논의하게 되며 일단 CBV 방법만을 사용한다고 가정하자. 그러면 모두 계산을 해서 값만을 e에 전달한다는 의미다. 간단한 예를 들면 다음과 같다.

  

((lambda (x y) (+ (* y y) x) 3 4) ==>19 

여기서 y2+x가 인자에 맞추어 계산되었다.

  

((lambda (x) (cons x '(b))) 'a) ==>(a b) 

위 식에서 인자는 'a이고 리스트 ‘(b)와 함께 cons가 적용되었다. 람다를 설명했으니 이제 label을 설명할 차례다.

(label f (lambda (p1 ... pn) e))로 표기하는 것은 함수 (lambda (p1 ... pn) e)로 표기하는 것에 대해 e 안에 f가 나타나는 경우 f는 label 이하의 식으로 계산된다. 이 방식은 N. Rochester가 고안하고 매카시가 채용한 것이다. 처치의 람다로 계산하는 것보다는 간단했다고 한다. 일반적으로 label보다는 defun으로 더 많이 사용한다. 그러니까 (defun f (p1 ... pn) e)라고 쓰는 일이 더 많은 것이다. 람다 함수에 이름이 붙었다고 생각하면 된다.

이제 앞에 나온 식을 바탕으로 몇 개의 함수를 정의해 보자. 여기서 함수 뒤에 점(null이 아니라 null.처럼)을 붙인 것은 파생된 함수를 나타내기 위해서다. 기본적인 7개의 식은 이미 앞에서 설명했다.

  

1. (null. x)는 x가 빈 리스트인지를 검사한다. 
(defun null. (x) 
(eq x '())) 

 (null. 'a) ==>() 
 (null. '()) ==>t
 
2. (and. x y)는 두 인수가 참이면 t를 아니면 ()를 돌려준다. 
(defun and. (x y) 
(cond (x (cond (y 't) ('t '()))) 
('t '()))) 

(and. (atom 'a) (eq 'a 'a)) ==>t 
(and. (atom 'a) (eq 'a 'b)) ==>()
 
3. (not. x) 만약 인수가 ()를 돌려주면 t를, 인수가 t를 돌려주면 ()를 돌려준다. 
(defun not. (x) 
(cond (x '()) 
('t 't))) 

(not (eq 'a 'a)) ==>() 
(not (eq 'a 'b)) ==>t
 
4. (append. x y)는 두 리스트를 취하고 이들을 연결하여 돌려준다. 
(defun append. (x y) 
(cond ((null. x) y) 
('t (cons (car x) (append. (cdr x) y))))) 

(append. '(a b) '(c d)) ==>(a b c d) 
(append. '() '(c d)) ==>(c d) 

5. (pair. x y)는 길이가 같은 두 리스트를 받아 이들로부터 차례로 리스트의 각 
원소를 취한 쌍의 리스트를 돌려준다.  
(defun pair. (x y) 
(cond ((and. (null. x) (null. y)) '()) 
((and. (not. (atom x)) (not. (atom y))) 
(cons (list (car x) (car y)) 
(pair. (cdr x) (cdr y))))))

복잡해 보이지만 실제의 동작은 간단하다.
 
(pair. '(x y z) '(a b c)) ==>((x a) (y b) (z c))
 
6. (assoc. x y)은 아톰 x와 pair로 만든 리스트 y를 받아 쌍의 첫 원소가 x와 
동일한 리스트의 두 번째 원소를 돌려준다. 
(defun assoc. (x y) 
(cond ((eq (caar y) x) (cadar y)) 
('t (assoc. x (cdr y))))) 

(assoc. 'x '((x a) (y b))) ==>a 
(assoc. 'x '((x new) (x a) (y b))) ==>new 

1부터 6은 매카시의 글에 나오는 식들을 실제의 리스프로 변환한 것들이다.

위로

리스프 인터프리터의 핵심, eval

이제 여기까지 왔으니 eval의 소스를 구경할 차례다. 앞에서 말한 것처럼 eval의 소스 코드는 a4 한 페이지 정도 분량에 지나지 않는다. 리스프 인터프리터에서 eval은 핵심 그 자체로 식을 계산(evaluate)하여 결과를 돌려주는 일을 한다. 식에서 ‘eval.’, ‘evcon.’, ‘evlis.’처럼 점이 붙어있는 함수는 기본 연산자를 바탕으로 파생된 함수라는 것을 알려준다.

  

(defun eval. (e a)
  (cond
    ((atom e) (assoc. e a))
    ((atom (car e))
     (cond
       ((eq (car e) 'quote) (cadr e))
       ((eq (car e) 'atom)  (atom   (eval. (cadr e) a)))
       ((eq (car e) 'eq)    (eq     (eval. (cadr e) a)
                                    (eval. (caddr e) a)))
       ((eq (car e) 'car)   (car    (eval. (cadr e) a)))
       ((eq (car e) 'cdr)   (cdr    (eval. (cadr e) a)))
       ((eq (car e) 'cons)  (cons   (eval. (cadr e) a)
                                    (eval. (caddr e) a)))
       ((eq (car e) 'cond)  (evcon. (cdr e) a))
       ('t (eval. (cons (assoc. (car e) a)
                        (cdr e))
                  a))))
    ((eq (caar e) 'label)
     (eval. (cons (caddar e) (cdr e))
            (cons (list. (cadar e) (car e)) a)))
    ((eq (caar e) 'lambda)
     (eval. (caddar e)
            (append. (pair. (cadar e) (evlis. (cdr e) a))
                     a)))))

(defun evcon. (c a)
  (cond ((eval. (caar c) a)
         (eval. (cadar c) a))
        ('t (evcon. (cdr c) a))))

(defun evlis. (m a)
  (cond ((null. m) '())
        ('t (cons (eval.  (car m) a)
                  (evlis. (cdr m) a)))))

이 식을 돌려보기로 하자. eval 함수는 두 개의 인수를 갖는다. eval. (e a)에서 계산하려는 식 e와 함수 호출에서 atom에 부여할 값을 부여하는 a라는 리스트다. a는 환경(environment)이라고도 부른다. 이 환경은 나중에 나오는 environment model과는 조금 다르다. 환경의 값은 pair를 이용하여 쌍으로 만들어 내며 값을 찾기 위해서는 assoc을 이용한다. eval은 4개의 cond 항목으로 이루어져 있다.

- 우선 식 e가 atom인 경우의 eval.의 동작을 보자. 식 e는 그냥 x이고 환경은 ‘((x a) (y b))다. cond는 assoc.을 이용하여 a를 되돌린다.

  

(eval. 'x '((x a) (y b))) ==>a 

- 두 번째는 e가 (a ...)와 같은 형태의 식으로 a는 atom이다, 그리고 이 경우는 앞에서 설명한 7개의 기본 연산자를 모두 사용하는 경우이며 다시 cond로 각 연산자별로 분기한다.

  

(eval. '(eq 'a 'a) '()) ==> t 
(eval. '(cons x '(b c)) 
'((x a) (y b)))  ==>(a b c) 

quote를 제외한 나머지는 모두 다시 eval을 호출하여 인자의 값을 계산한다.

생각해보면 결국 인자를 모두 계산하여 6개의 기본 연산자에 대입하는 것으로 귀착된다. cond는 조금 더 복잡하다. cond를 계산하려면 evcon이라는 다른 함수를 불러야 한다. 이 함수는 재귀적으로 식의 요소를 평가하여 첫 번째 t가 나오면 술어 다음의 식을 계산한다. t가 나오는 술어가 없다면 ‘()를 리턴한다. evcon 함수는 cond 리스트의 처음부터 eval.하여 참이 나오면 그 술어와 쌍이 되는 식을 eval.하여 돌려준다.

  

(eval. '(cond ((atom x) 'atom) ('t 'list)) '((x '(a b)))) ==> list 

그리고 두 번째 절의 마지막은 매개변수처럼 전달된 함수 호출을 다루는 것으로 아톰을 해당 값으로 치환하는 것이다. 이들은 lambda나 label을 이용하며 그 값이 다시 계산된다.

  

(eval. '(f '(b c)) 
'((f (lambda (x) (cons 'a x))))) 
==> 

(eval. '((lambda (x) (cons 'a x)) '(b c)) 
'((f (lambda (x) (cons 'a x))))) ==> (a b c)

위의 식에서 f는 환경에서 발견되어 (lambda (x) (cons 'a x))로 치환되었다.

- 그 다음은 label이다. label의 식은 매우 복잡하지만 label이 하는 일은 결국 환경 a에 label 함수의 이름과 해당 lambda를 더하는 것이다. 그래서 다음과 같다.

  

(eval. '((label firstatom (lambda (x) 
(cond ((atom x) x) 
('t (firstatom (car x)))))) 
y) 
'((y ((a b) (c d))))) 

==>
 
(eval. '((lambda (x) 
(cond ((atom x) x) 
('t (firstatom (car x))))) 
y) 
'((firstatom 
(label firstatom (lambda (x) 
(cond ((atom x) x) 
('t (firstatom (car x))))))) 
(y ((a b) (c d))))) 

결국 이 식은 환경 a에 firstatom의 람다 식을 추가한 것이다(너무 복잡하게 생각하면 안 된다). 결국 계산이 일어나면 a를 리턴한다.

- 그 다음은 lambda다. ((lambda (p1 … pn ) e) a1 … an)은 evlis를 불러서 a1 ... an의 인자들을 계산한다. 그 다음에 이 계산 값 (v1 ... vn)이 a1 ... an과 쌍을 만들게 되어 (a1 v1) ... (an vn)의 리스트가 환경의 앞에 추가되는 형태가 된다.

  

(eval. '((lambda (x y) (cons x (cdr y))) 
'a 
'(b c d)) 
'()) 
==> 
(eval. '(cons x (cdr y)) 
'((x a) (y (b c d)))) 

위의 식에서 x와 y의 값이 쌍으로 주어졌다. lambda의 인자 리스트는 환경변수로 계산되어 바뀐 것이다(대단히 중요한 결론이다. 리스프 인터프리터는 인자 리스트를 계산하여 환경에 보관한다. 그리고 연산자만 남고 인자 리스트는 없어진다). 결국 계산은 (a c d)를 되돌린다.

위의 eval.은 매카시의 글에 나온 식을 그레이엄이 리스프로 번역한 것들이고 필자는 두 개의 문서를 놓고 비교했다. 그레이엄의 프로그램에서 apply가 보이지 않기 때문에 리스프 인터프리터에 대해 배운 독자들은 이상하다고 생각할지 모른다. 그러나 최초의 리스프 인터프리터 구현은 요즘의 인터프리터와 apply와 eval의 순서가 반대다. 글에서 매카시는 apply를 universal function으로 보았다. 매카시의 리스프에서 apply는 각 인자에 대해 quote를 붙이기 위해 사용되었다. 시작이 되고 나면 모두 eval이 처리한다(일반적으로 apply가 적용되는 곳이 위 식에서 evlis.가 적용되는 부분이다).

역사적인 이유로 매카시가 생각한 용법의 apply도 적어본다.

  

apply[f;args] = eval[cons[f;appq[args]];NIL]
appq[m] = [null[m] -> NIL;
       T -> cons[list[QUOTE;car[m]];appq[cdr[m]]]]

eval [ ]
[...
...
]

위로

끝으로

이게 다인가? 다는 아니지만 핵심이라고 말할 수 있다. 요즘의 리스프에서 몇 개 빠진 부분은 있으나 중요한 부분은 모두 망라한다.

메타서큘러 인터프리터는 상당히 중요하므로 매카시 본인이 만든 인터프리터도 있다. 매카시 자신이 만든 "A Micro-Manual for Lisp -- not the whole Truth"라는 글이 이런 내용으로 2페이지짜리 글을 인터넷에서 다운로드할 수 있다.

이번에 설명한 eval.은 SICP의 강의 비디오 7a에서 서스만이 “모든 언어의 커널(The Kernel of Every Language)” 또는 “The Spirit in the computer”이라고 부르는 것이다. 몇 개의 식만 잘 정의하면 일단 돌아갈 수 있는 인터프리터가 나온다는 것, 이것이 바로 비밀이다. 나중에 이르기까지 인터프리터는 이것보다 조금 더 복잡해졌을 뿐이다. 앞의 프로그램에서 빠진 중요한 문제가 몇 개가 있으며 환경변수의 문제 같은 것이 있다. 이들은 SICP에서 모두 설명된다. The Art of Interpreter의 내용은 당연히 반영되었다.

소셜 북마크
	mar.gar.in
	Digg
	del.icio.us
	Slashdot

이렇게 간신히 돌아가기 시작한 언어를 컴퓨터에 입력하고 종이에 식을 적은 후 검증을 하던 것이 1세대 해커들의 일이었다, 하지만 잘 돌아갔다.

리스프에서 모든 것은 리스트다. 프로그램도 데이터도 리스트이며 이것을 처리하는 인터프리터도 리스트이다. 만약 이런 것들을 일일이 손으로 계산한다면 고역이겠으나 다행히 컴퓨터가 있다.

정신없이 설명하다보니 독자들은 SICP의 4장을 미리 연습한 셈이 되고 말았다. 그리고 리스프가 구현되던 당시의 상황과 리스프라는 언어의 핵심을 한꺼번에 본 셈이다. 기왕 여기까지 왔으니 SICP나 다른 리스프 책을 보아도 좋을 것이다. 만약 리스프의 장점에 대해 조금 더 고무적인 글을 읽고 싶다면 폴 그레이엄의 『해커와 화가』와 같은 책이 있다. 책에서 리스프의 어떤 점이 중요하며 왜 좋은가에 대해 명쾌하게 설명하고 있다.

위로

[지난 Special Issue 보기]