Lisp 프로그램 개발을 하다보면 Lisp 언어의 개발 역사를 그대로 반영하게 되는 경우가 많습니다. Lisp 프로그램을 처음 작성할 때에는 보통 리스트만 엄청나게 써서 코딩하게 됩니다. 그러다가 차츰 버전을 올리면서 리스트를 더 빠르고 특화된 자료 구조로 대체하게 됩니다. 이 장에서는 리스트를 가지고 할 수 있는 다양한 것들을 살펴보는 동시에, 리스트를 이용하여 몇 가지 일반적인 Lisp 개념들을 설명하겠습니다.
Cons
2.4절에서는 cons, car, cdr과 같은 기본적인 리스트 조작 함수를 배웠습니다. cons가 실제로 하는 일은 두 개의 객체를 두 부분으로 나뉘어진 cons라 불리는 객체에 결합하는 것입니다. 개념적으로 cons는 한 쌍의 포인터입니다. 앞쪽은 car이고 뒷쪽은 cdr에 해당됩니다.
cons는 어떤 타입의 쌍을 표현할 때에도 유용하게 사용할 수 있습니다. cons의 각 부분은 어떤 종류의 객체의 위치라도 가리킬 수 있습니다. 물론 또다른 cons를 가리킬 수도 있지요. 리스트를 만들 때는 cons가 다른 cons를 가리키도록 해서 줄줄이 연결하는 방법을 사용합니다.
리스트를 여러 개의 쌍으로 바꿔서 생각하는 것이 쉽진 않겠지만, 어찌되었든 이런 방식으로 정의하는 것이 가능합니다. 비어있지 않은 모든 리스트는 첫번째 요소와 리스트의 나머지 부분으로 구성된 한 쌍으로 간주할 수 있습니다. Lisp의 리스트는 이런 개념을 구체화한 것입니다. cons의 앞 부분은 리스트의 첫번째 요소를 가리키고, 뒷 부분은 리스트의 나머지 부분을 가리킵니다. 나머지 부분은 또다른 cons이거나 nil일 수 있겠지요. Lisp는 관습적으로 첫번째 요소를 가져올 때 car를, 리스트의 나머지 부분을 가져올 때 cdr을 사용해왔습니다. 그래서 지금은 리스트의 첫 번째 요소를 car라고 하고, 리스트의 나머지 부분을 cdr이라고 부르게 되었습니다. 리스트는 특별한 종류의 객체가 아닙니다. 그냥 이런 식으로 cons 여러 개가 묶여있을 뿐입니다.
무엇인가를 nil에 cons 하게 되면,
> (setf x (cons 'a nil))
(A)
그림 3.1처럼 하나의 cons로 구성된 리스트가 만들어집니다. 각각의 cons가 car와 cdr을 가리키는 화살표를 가진 상자로 보이기 때문에, 이렇게 cons를 표현하는 방법을 상자 표기법이라고 부릅니다. car와 cdr를 호출하면 이 화살표들이 가리키는 대상을 가져올 수 있습니다:
> (car x)
A
> (cdr x)
NIL
여러 개의 요소를 가진 리스트를 만든다면 여러 개의 cons가 사슬처럼 연결된 모양을 얻게 됩니다:
> (setf y (list 'a 'b 'c))
(A B C)
이 사슬 모양의 구조가 그림 3.2에 그려져 있습니다. 이제 이 리스트의 cdr은 2개의 요소가 들어있는 리스트입니다.
> (cdr y)
(B C)
여러 개의 요소가 들어있는 리스트에서는 car를 이용해서 각 요소들을 가져올 수 있고, cdr을 이용해서 리스트의 나머지 부분을 가져올 수 있습니다.
리스트는 어떤 종류의 객체라도 저장할 수 있기 때문에, 다른 리스트를 저장할 수도 있습니다:
> (setf z (list 'a (list 'b 'c) 'd))
(A (B C) D)
이런 상황에서는 그림 3.3에 표시된 내부 구조를 가지게 됩니다. 두번째 cons의 car 포인터는 리스트를 가리키게 되는 것이지요:
> (car (cdr z))
(B C)
앞에서 봤던 리스트 y와 지금 보고 계신 리스트 z는 모두 3개의 요소를 가지고 있습니다. 단지 z의 두번째 요소가 리스트인 것 뿐이죠. 이런 리스트를 중첩된 리스트라고 부르고, 다른 리스트를 요소로 포함하지 않는 y 같은 리스트는 평평한 리스트라고 부릅니다.
consp 함수는 주어진 인수가 cons인 경우에만 참을 반환합니다. 그러므로 listp는 아래와 같이 정의될 수 있습니다:
(defun our-listp (x)
(or (null x) (consp x)))
cons가 아닌 것은 모두 원자이기 때문에 술어 atom은 아래와 같이 정의할 수 있습니다:
(defun our-atom (x) (not (consp x)))
nil이 원자이면서 리스트라는 점을 주의하세요.
동등성
Lisp는 cons를 호출할 때마다 두 개의 포인터를 담을 공간을 메모리에 할당합니다. 그렇기 때문에 같은 인수를 주고 cons를 두 번 호출하더라도, 겉으로는 같은 값을 가지고 있는 것처럼 보이지만 별개의 객체로 존재합니다:
> (eql (cons 'a nil) (cons 'a nil))
NIL
만약 두 개의 리스트가 같은 요소들을 가지고 있는지 확인할 수 있다면 편리할텐데요. 이런 경우를 위해 Common Lisp는 동등성을 비교할 때 쓸 수 있는 술어를 내장하고 있습니다. eql은 두 객체가 같은 경우에만 참을 반환하지만,
> (setf x (cons 'a nil))
(A)
> (eql x x)
T
equal은 인수들이 본질적으로 동일한 내용을 출력하면 참을 반환합니다:
> (equal x (cons 'a nil))
T
이 술어는 리스트 외의 다른 자료 구조에도 사용할 수 있지만, 리스트의 동등성만 판별하는 버전은 이렇게 작성할 수 있을겁니다:
(defun our-equal (x y)
(of (eql x y)
(and (consp x)
(consp y)
(our-equal (car x) (car y))
(our-equal (cdr x) (cdr y)))))
이 정의를 보면 알 수 있듯이, 어떤 x와 y를 인수로 넣었을 때 eql이 참이면, equal도 참이라고 말할 수 있습니다.
왜 리스프는 포인터가 없나요
리스프의 비밀 중 하나는, 변수 또한 리스트가 각 요소를 가지고 있는 것과 동일한 방식으로 값을 가진다는 것입니다. cons가 각 요소를 가리키는 포인터를 가지고 있는 것처럼 변수도 값을 가리키는 포인터를 가지고 있습니다.
여러분은 아마도 포인터가 명시적으로 관리되는 언어를 지금껏 써왔을텐데요. 리스프에서는 언어가 포인터를 처리해주기 때문에 명시적으로 포인터를 관리할 일이 없습니다. 이전에 리스트에서 포인터가 어떻게 사용되는지 살펴봤는데요. 변수도 비슷합니다. 두 개의 변수에 같은 리스트를 설정한다고 생각해봅시다:
> (setf x '(a b c))
(A B C)
> (setf y x)
(A B C)
y에 x의 값을 설정하면 무슨 일이 일어날까요? 사실 변수 x가 리스트 자체를 포함하고 있지는 않습니다. 단지 리스트를 가리키는 포인터를 메모리에 저장하고 있는 것 뿐입니다. 그래서 같은 값을 y에 배정하게 되면, 리스트를 복사하는 것이 아니라 포인터를 복사하게 됩니다. (그림 3.4가 그 결과를 보여주고 있습니다.) 따라서 두 개의 변수 모두 같은 객체를 가리키게 됩니다:
> (eql x y)
T
리스프가 포인터를 따로 가지고 있지 않은 이유는, 모든 값이 개념적으로 포인터이기 때문입니다. 어떤 값을 변수에 배정하거나, 자료 구조에 저장한다고 할지라도 실제로 저장되는 것이라곤 그 값을 가리키는 포인터 뿐입니다. 자료 구조에게 내용을 꺼내도록 하거나 변수의 값을 가져오게 하면 리스프는 포인터가 가리키는 객체를 반환합니다. 그렇지만 이 모든 일이 수면 아래에서 일어나지요. 아무 생각 없이 그냥 자료 구조나 변수에 값을 집어넣으면 됩니다.
리스프는 효율 때문에 가끔 포인터 대신 값 자체를 선택할 때가 있습니다. 예를 들면, 작은 정수를 저장하는 경우에는 포인터보다 더 큰 메모리 공간을 쓸 필요가 없습니다. 그래서 리스프 구현체는 포인터를 만들고 이 값을 가리키도록 하는 대신 작은 정수 표현을 그냥 사용합니다. 그렇지만 내부적으로야 어떻게 돌아가든 프로그래머는 귀찮게 생각할 필요없이 무엇이든 아무데나 집어넣을 수 있습니다. 완전히 모순적인 선언을 만들어내지 않는 한 어떤 종류의 객체를 어떤 종류의 자료 구조에 넣는 것도 가능합니다. 특정한 구조를 만들어 낸 다음, 그 안에 같은 구조를 넣어버리는 것도 가능하지요.
리스트 만들기
copy-list 함수는 리스트를 받아서 복사본을 반환합니다. 새 리스트는 같은 요소들을 가지고 있지만, 새로운 cons 안에 담겨있다는 점에서 다릅니다:
> (setf x '(a b c)
y (copy-list x))
(A B C)
그림 3.5를 보면 같은 승객들을 새로운 버스에 태운 것 같은 구조입니다. copy-list는 아래와 같이 정의되었다고 생각할 수 있습니다:
(defun our-copy-list (lst)
(if (atom lst)
lst
(cons (car lst) (our-copy-list (cdr lst)))))
x와 (copy-list x)이 가지고 있는 요소가 같으므로 equal은 참이 되겠지만, x가 nil이 아닌 이상 같은 객체는 아니므로 eql은 거짓이 됩니다.
마지막으로, append 함수는 리스트 여러 개를 받아서 하나의 리스트로 만들어줍니다:
> (append '(a b) '(c d) '(e))
(A B C D E)
append는 여러 개의 리스트를 하나로 합친 새로운 리스트로 만들어 내는 과정에서 마지막 리스트를 제외한 모든 리스트들을 복사합니다. (역주: 부록 B의 append 구현을 참고하세요)
예제: 압축
이 절에서는 리스트를 압축할 때 쓸 수 있는 가장 간단한 기법을 보여드리겠습니다. 이 알고리즘은 Run Length Encoding으로 불립니다. 레스토랑의 예를 생각하면 이 알고리즘의 동작 방식을 알 수 있는데요. 웨이트리스가 주문을 받으러 손님 4명이 앉아있는 식탁으로 왔다고 상상해보지요.
웨이트리스: "뭘 드시겠습니까?"
첫번째 손님: "난 스페셜"
두번째 손님: "어 나도"
세번째 손님: "그게 좋겠네"
모두가 네번째 손님을 돌아보는 찰나, "난 실란트로 수플레 먹을래"라고 들릴락 말락한 작은 목소리로 말합니다.
웨이트리스가 돌아서서 카운터로 또각또각 걸어갑니다. 그러고는 주방에 대고 큰 소리로 주문을 넣죠. "여기 스페셜 세 개랑 실란트로 수플레 하나요!"
그림 3.6: Run-length encoding: Compression
(defun compress (x)
(if (consp x)
(compr (car x) 1 (cdr x))
x))
(defun compr (elt n lst)
(if (null lst)
(list (n-elts elt n))
(let ((next (car lst)))
(if (eql next elt)
(compr elt (+ n 1) (cdr lst))
(cons (n-elts elt n)
(compr next 1 (cdr lst)))))))
(defun n-elts (elt n)
(if (> n 1)
(list n elt)
elt))
그림 3.6을 보시면 이런 압축 기법을 구현한 코드가 있습니다. compress 함수는 원자들로만 이루어진 리스트를 하나 받아서 압축된 형태로 결과를 반환합니다:
> (compress '(1 1 1 0 1 0 0 0 0 1))
((3 1) 0 1 (4 0) 1)
같은 요소가 연속으로 나오게 되면, 이것을 (갯수 요소) 형태의 리스트로 바꿔버립니다.
대부분의 일은 compr 함수가 해결하는데요. 이 함수는 3개의 인수를 받습니다. elt는 우리가 마지막으로 봤던 요소, n은 elt가 연속으로 몇 번 나왔는지, 그리고 lst는 압축할 나머지 부분을 의미합니다. 처리할 것이 더 없으면 n-elts 함수를 호출해서 n개의 elt를 특정한 방식으로 표현하도록 합니다. lst의 첫번째 요소가 여전히 elt이면 그냥 n을 하나 증가시켜서 재귀 호출하면 됩니다. 만약 elt와 같지 않으면 지금까지 봤던 요소들을 압축합니다. 그리고 compr이 나머지 부분들을 처리해서 계속 붙여나가도록 합니다.
그림 3.7: Run-length encoding: Expansion.
(defun uncompress (lst)
(if (null lst)
nil
(let ((elt (car lst))
(rest (uncompress (cdr lst))))
(if (consp elt)
(append (apply #'list-of elt)
rest)
(cons elt rest)))))
(defun list-of (n elt)
(if (zerop n)
nil
(cons elt (list-of (- n 1) elt))))
압축된 리스트를 원래대로 되돌리려면, 그림 3.7에 있는 uncompress 함수를 호출하면 됩니다.
> (uncompress '((3 1) 0 1 (4 0) 1))
(1 1 1 0 1 0 0 0 0 1)
uncompress 함수도 압축된 리스트를 재귀적인 방식으로 처리합니다. 각 묶음의 압축을 풀어서 원래 모양으로 만들어 놓을 때는 list-of 함수를 호출합니다:
> (list-of 3 'ho)
(HO HO HO)
사실 list-of 함수를 만들 필요는 없었습니다. 내장 함수 중에 make-list가 같은 일을 하니까요 - 그렇지만 그 함수는 키워드 인수를 사용하는데, 아직 키워드 인수가 뭔지 설명을 안 했기 때문에 어쩔 수 없이 하나 만들어서 보여드린겁니다.
그나저나 숙련된 Lisp 프로그래머라면 그림 3.6이나 3.7처럼 코딩하지는 않았을겁니다. 비효율적이기도 하고, 압축도 할 수 있는만큼 최대로 한 것이 아니거든요. 게다가 원자로 구성된 리스트만 처리할 수 있다는 것이 문제입니다. 몇 장만 더 넘어가면 지금 언급한 문제들을 모두 해결할 수 있는 기법들을 배울 수 있습니다. 일단 넘어가지요.
프로그램 로드하기
이 절에서 처음으로 실질적인 프로그램을 하나 작성했는데요. 코드가 좀 길어지면 파일에 써넣고 Lisp로 이 파일을 읽어들이는 편이 더 편할 수도 있습니다. 가령 그림 3.6과 3.7에 있는 코드를 "compress.lisp" 파일에 저장했다면, 최상위 계층에서 이렇게 입력하세요:
(load "compress.lisp")
이렇게 하면 최상위 계층에서 입력한 것과 차이가 전혀 없습니다.
주의: 어떤 구현체에서는 Lisp 파일의 확장자로 ".lisp" 대신 ".lsp"를 쓰기도 합니다.
접근
Common Lisp는 car와 cdr 외에 추가적인 접근 함수를 가지고 있습니다. 리스트의 특정 위치에 있는 요소를 찾으려면 nth 함수를 호출하면 됩니다:
> (nth 0 '(a b c))
A
만약 cdr을 n번 적용한 결과를 원한다면 nthcdr 함수를 호출하면 됩니다:
> (nthcdr 2 '(a b c))
(C)
nth 함수나 nthcdr 함수 모두 인덱스가 0부터 시작합니다. 즉, 각 요소에 번호를 매길 때 1부터 시작하는 것이 아니라 0부터 시작하게 됩니다. Common Lisp에서 숫자를 이용하여 자료 구조 안에 있는 요소를 참조하는 경우에는 항상 0부터 시작하는 인덱스를 사용하게 됩니다.
앞에서 본 두 함수는 하는 일이 거의 동일합니다. nth는 nthcdr에 car를 적용한 함수와 같습니다. 오류 처리를 다 빼고 생각해본다면 nthcdr을 이렇게 정의할 수 있습니다:
(defun our-nthcdr (n lst)
(if (zerop n)
lst
(our-nthcdr (- n 1) (cdr lst))))
zerop는 인수가 0인 경우 참을 반환하는 간단한 함수입니다.
last 함수는 리스트를 구성하는 가장 마지막 cons를 반환합니다:
> (last '(a b c))
(C)
이 결과에서 주의해야 할 것은 반환값이 마지막 요소 자체가 아니라는 점입니다. 마지막 요소를 얻어내고 싶다면, last 함수를 호출해서 나온 결과를 car에 넘겨주세요.
Common Lisp는 first부터 tenth까지 함수를 정의해놓고 있는데, 각각 리스트에서 대응되는 위치에 있는 요소를 가져옵니다. 이 함수들은 인덱스가 0부터 시작하지 않습니다. 따라서 (second x)는 (nth 1 x)와 같습니다.
이 외에도 Common Lisp는 caddr 같은 함수들을 정의하고 있는데요. caddr은 (car (cdr (cdr )))을 축약해놓은 함수입니다. 이렇게 cxr 형태로 만들어진 함수 이름들이 있는데, x에는 a나 d가 4개까지 들어갈 수 있도록 미리 내장 함수들이 만들어져 있습니다. 그렇지만 cadr 같은 간단한 경우를 제외하고는 이런 함수를 쓰지 않는 편이 좋습니다. 그런 이름은 아무도 읽고 싶지 않을테니까요.
매핑 함수
Common Lisp는 리스트 안에 있는 요소를 대상으로 함수를 호출할 수 있도록 해주는 여러가지 함수를 내장하고 있습니다. 가장 자주 사용되는 것은 mapcar인데요, 함수 하나와 한 개 이상의 리스트를 받아서, 각 리스트의 요소들을 대상으로 함수를 호출한 결과를 반환합니다. 두 개 이상의 리스트가 인수로 주어지는 경우 가장 길이가 짧은 리스트에 맞춰서 동작하게 됩니다:
> (mapcar #'(lambda (x) (+ x 10))
'(1 2 3))
(11 12 13)
> (mapcar #'list
'(a b c)
'(1 2 3 4)
((A 1) (B 2) (C 3))
maplist 함수는 똑같은 형식으로 인수를 받긴 하지만, 리스트에 cdr을 연속적으로 적용하면서 함수를 호출한다는 점에서 다릅니다:
> (maplist #'(lambda (x) x)
'(a b c))
((A B C) (B C) (C))
다른 매핑 함수로는 mapc가 있는데요, 88쪽에서 설명드리겠습니다. mapcan도 있는데 이것은 202쪽에서 다루도록 하겠습니다.
트리
Cons를 이진 트리로 생각할 수도 있습니다. car를 왼쪽 하위 트리로 생각하고 cdr을 오른쪽 하위 트리로 생각하는거죠. 예를 들어 리스트 (a (b c) d)는 그림 3.8 같은 트리로 표현될 수 있습니다. (책을 -45도로 돌려보면 그림 3.3과 같은 것을 알 수 있습니다.)
Common Lisp는 트리를 다루는 내장 함수를 몇 개 가지고 있습니다. 예를 들어, copy-tree 함수는 트리 하나를 받아서 복사본을 반환합니다. 이것은 아래와 같이 정의될 수 있습니다:
(defun our-copy-tree (tr)
(if (atom tr)
tr
(cons (our-copy-tree (car tr))
(our-copy-tree (cdr tr)))))
36쪽의 copy-list와 이 코드를 비교해보면, copy-tree는 cdr만 복사하는 것이 아니라 car도 복사한다는 점이 다르다는 것을 알 수 있습니다.
그런데 사실 트리 노드에 값을 쓸 수 없으면 이진 트리로서 별 가치가 없습니다. Common Lisp에 내장된 트리를 대상으로 동작하는 함수들은 트리가 아니라 중첩된 리스트를 다루기 위해서 존재하는 것이랍니다. 예를 들어 아래와 같은 리스트를 하나 가지고 있다고 합시다:
(and (integerp x) (zerop (mod x 2)))
이걸 x 대신 y로 고치고 싶은데요. 순차열에 있는 요소를 치환하는데 쓰는 substitute를 여기에 대고 호출해봐야 제대로 동작하지 않습니다:
> (substitute 'y 'x '(and (integerp x) (zerop (mod x 2))))
(AND (INTEGERP X) (ZEROP (MOD X 2)))
왜냐하면 이 리스트는 3개의 요소를 가지고 있는데 이 중 어느 것도 x가 아니기 때문입니다. 중첩된 리스트 속에 박혀있는 x를 치환하려면 트리에 있는 요소를 대체할 때 사용하는 subst를 써야합니다:
> (subst 'y 'x (and (integerp x) (zerop (mod x 2))))
(AND (INTEGER Y) (ZEROP (MOD Y 2)))
직접 subst를 구현해보면 copy-tree와 모양이 거의 비슷하다는 것을 알 수 있습니다:
(defun our-subst (new old tree)
(if (eql tree old)
new
(if (atom tree)
tree
(cons (our-subst new old (car tree))
(our-subst new old (car tree))))))
트리를 대상으로 동작하는 함수는 대체로 다 이런 모양을 가지고 있습니다. car와 cdr 양쪽으로 타고 내려가죠. 이런 함수를 가리켜 이중 재귀적이라고 합니다.
재귀 이해하기
학생들에게 재귀를 가르칠 때, 재귀 함수의 모든 호출 과정을 종이에 써보라고 하는 경우를 종종 보는데요. (재귀 함수의 호출 과정을 추적하는 방법은 288쪽에서 다룹니다.) 이렇게 가르치면 안 됩니다. 프로그래머가 그렇게 모든 함수 호출 과정과 반환값을 따져가면서 재귀 함수를 정의하는 것은 아니니까요.
만약 그런 식으로 생각해야 한다면 재귀를 사용하는 것이 도움이 되는게 아니라 오히려 부담만 되겠죠. 사실 재귀의 장점이 알고리즘을 좀 더 추상적인 차원에서 볼 수 있도록 해주는 것이니까요. 함수를 호출했을 때 발생하는 모든 재귀 호출을 따져보지 않아도 이것이 제대로 만들어진 재귀 함수인지 아닌지 충분히 판단할 수 있습니다.
어떤 재귀 함수가 제대로 동작하는지 알고 싶다면 그냥 모든 경우의 수를 처리하는지 확인하기만 하면 됩니다. 가령 리스트의 길이를 구하는 함수가 있으면:
(defun len (lst)
(if (null lst)
0
(+ (len (cdr lst)) 1)))
두 가지만 확인해보면 이 함수가 올바르게 동작하는지 알 수 있습니다:
- 리스트의 길이가 0일 때 동작
- 길이가 n인 리스트에 대해서 동작하면, 길이가 n+1인 리스트에 대해서도 동작
두 가지 조건이 성립되면 모든 리스트에 대해서 동작한다는 것을 알 수 있지요.
이 함수의 정의는 확실히 첫번째 조건을 만족합니다: lst가 nil인 경우, 함수는 즉각 0을 반환합니다. 자 이제, 길이가 n인 리스트인 경우에 동작한다고 가정하구요. 길이가 n+1인 리스트를 넘겨봅시다. 이 함수의 정의는 리스트의 cdr에 대해 len을 호출한 결과와 1을 더하여 반환합니다. 여기서는 cdr이 길이가 n인 리스트라고 할 수 있겠네요. 처음 가정한 바에 의하면 길이가 n인 리스트를 len에 넘기면 결과가 n입니다. 따라서 리스트의 전체 길이는 n+1이라고 할 수 있지요.
이게 전부입니다. 재귀를 이해하는 방법이 괄호를 다루는 방법과 많이 닮았다는 생각이 들지 않습니까? 아니 어떻게 그 많은 괄호의 쌍이 제대로 맞는지 확인할 수 있습니까? 그럴 필요가 없습니다. 대체 어떻게 재귀 함수의 모든 호출 과정을 머리 속으로 그려낼 수 있죠? 그럴 필요가 없다니까요.
더 복잡한 재귀함수라면 더 많은 경우의 수가 있을테지만 어디까지나 기본 원리는 같습니다. 가령 41쪽의 our-copy-tree는 원자, cons가 1개인 경우, n+1개의 cons로 이루어진 트리의 경우, 이렇게 세 가지 경우를 고려해야 했습니다.
첫번째 경우 (여기서는 길이가 0인 리스트이지요)는 기초 단계라고 부릅니다. 의도한대로 재귀 함수가 동작하지 않는 것은 기초 단계가 잘못되어서 그런 경우가 많습니다. 아예 기초 단계를 생략해버리는게 가장 흔한 실수인데요. member를 잘못 구현한 정의를 한 번 보시죠:
(defun our-member (obj lst) ; wrong
(if (eql (car lst) obj)
lst
(our-member obj (cdr lst))))
끝까지 못 찾고 리스트의 마지막에 도달했을 때 재귀 호출을 멈추려면 null 테스트가 필요합니다. 이 버전은 원하는 객체를 리스트에서 찾지 못한 경우에 무한 루프에 빠져버립니다. 이런 종류의 문제를 더 자세히 살펴보려면 부록 A를 보세요.
어떤 재귀 함수가 올바르게 구현되었는지 아닌지 판단할 수 있게 되었다고 해도 그건 재귀의 절반을 이해한 것에 불과합니다. 나머지 절반을 이해하려면 여러분이 원하는 것을 재귀 함수로 만들어 낼 수 있어야 합니다. 그 내용은 6.9절에서 다루겠습니다.
집합
리스트는 작은 집합을 표현하는데 쓰기에도 좋습니다. 리스트의 모든 요소는 그 집합의 원소이기도 합니다:
> (member 'b '(a b c))
(B C)
member가 참을 반환할 때는 심볼 t를 반환하는 대신 리스트에서 우리가 찾는 객체로 시작하는 부분을 반환합니다. 논리적으로는 cons가 t와 똑같이 취급되니까 이런 방식으로 추가적인 정보를 전달하는 것이지요.
기본적으로 member는 eql을 이용해서 객체를 비교합니다. 그렇지만 키워드 인수를 쓰면 기본값을 덮어 쓸 수 있습니다. 많은 Common Lisp 함수들은 하나 이상의 키워드 인수를 받도록 되어있습니다. 이 키워드 인수는 위치에 대응되지 않고 키워드라고 불리는 특별한 태그에 대응된다는 점에서 좀 다릅니다. 키워드는 콜론이 앞에 붙은 심볼을 말합니다.
member가 받아들이는 키워드 인수 중 하나는 :test인데요. member를 호출할 때 :test 인수에 함수를 넘기면 동등성을 테스트할 때 eql 대신 그 함수를 사용합니다. 따라서 리스트에서 어떤 요소를 찾을 때 eql 대신 equal을 사용하고 싶은 경우 이렇게 쓸 수 있습니다:
> (member '(a) '((a) (z)) :test #'equal)
((A) (Z))
키워드 인수는 항상 옵션입니다. 키워드 인수가 하나라도 호출에 포함되는 경우에는 끝부분에 써야 합니다. 키워드 인수를 여러 개 쓸 때에는 키워드 인수끼리 순서를 마음대로 바꿔도 상관없습니다.
member가 받는 또다른 키워드 인수로는 :key 인수가 있는데요. 이것으로 각 인수를 비교하기 전에 적용할 함수를 지정할 수 있습니다:
> (member 'a '((a b) (c d)) :key #'car)
((A B) (C D))
이 예제는 car를 적용한 결과가 a인 요소를 검색하는 방법을 보인 것입니다.
키워드 인수를 둘 다 전달할 때에는 어떤 순서라도 가능합니다. 아래의 두 호출은 동등한 것입니다:
> (member 2 '((1) (2)) :key #'car :test #'equal)
((2))
> (member 2 '((1) (2)) :test #'equal :key #'car)
((2))
둘 다 car를 적용한 결과가 2인 요소를 찾아냅니다.
임의의 술어를 만족하는 요소를 찾고 싶을 때 - 홀수인 경우에만 참을 반환하는 oddp 같은 것들 - 사용할 수 있는 비슷한 함수로는 member-if가 있습니다:
> (member-if #'oddp '(2 3 4))
(3 4)
member-if가 이런 식으로 쓰여있다고 생각하면 됩니다:
(defun our-member-if (fn lst)
(and (consp lst)
(if (funcall fn (car lst))
lst
(our-member-if fn (cdr lst)))))
함수 adjoin은 조건부 cons 함수라고 할 수 있습니다. 객체 하나와 리스트 하나를 받아서, 이 객체가 리스트에 없는 경우에만 붙여넣습니다:
> (adjoin 'b '(a b c))
(A B C)
> (adjoin 'z '(a b c))
(Z A B C)
일반적인 경우에는 member와 동일한 키워드 인수를 받아들입니다.
합집합, 교집합, 차집합 연산은 각각 union, intersection, set-difference 함수로 구현되어 있습니다. 이 함수들은 정확히 두 개의 리스트만 받아들입니다. (그렇지만 이 함수들 또한 member와 동일한 키워드 인수를 받을 수 있습니다.)
> (union '(a b c) '(c b a))
(A C B S)
> (intersection '(a b c) '(b b c))
(B C)
> (set-difference '(a b c d e) '(b e))
(A C D)
원래 집합에는 순서라는 개념이 없기 때문에 이 함수들은 연산할 때 원본 리스트에 들어있는 요소들의 순서를 보존하지 않습니다. set-difference 함수를 호출한 결과는 세부 구현에 따라 (d c a)가 될 수도 있다는 뜻입니다.
시퀀스
리스트를 특정한 순서를 지닌 객체들의 나열이라고 생각할 수도 있습니다. Common Lisp에서는 리스트와 벡터, 둘 다 시퀀스에 포함됩니다. 이 절에서는 시퀀스 함수 몇 개를 소개할텐데요, 특히 리스트에 적용 가능한 것들을 알아보겠습니다. 시퀀스에 적용할 수 있는 연산들은 4.4절에서 더 자세하게 다루겠습니다.
length 함수는 시퀀스에 포함된 요소들의 갯수를 반환합니다:
> (length '(a b c))
3
리스트 전용 함수이긴 헀지만 이미 24쪽에서 이 함수를 작성한 적이 있었죠.
시퀀스의 일부분을 복사할 때에는 subseq를 사용합니다. 두번째 인수(필수)는 어디부터 복사할 것인지 지정하구요. 세번째 인수(옵션)는 어느 지점에서 복사를 멈출 것인지 지정합니다.
> (subseq '(a b c d) 1 2)
(B)
> (subseq '(a b c d) 1)
(B C D)
세번째 인수가 생략되면 지정한 시작 위치부터 원본 시퀀스의 끝까지 복사해버립니다.
reverse 함수는 시퀀스를 인수로 받아서 똑같은 요소를 가진 시퀀스를 내놓기는 하는데, 순서를 뒤집어 버립니다:
> (reverse '(a b c))
(C B A)
(a b b a)처럼 앞에서부터 읽어도, 뒤에서부터 읽어도 똑같은 시퀀스를 회문이라고 부르는데요. 만약 회문이 짝수 개의 요소들을 가지고 있다면, 나머지 절반은 앞 부분을 거울로 비춘 모양이 될 것입니다. length, subseq, reverse 함수를 가지고 아래와 같이 함수를 정의할 수 있습니다:
(defun mirror? (s)
(let ((len (length s)))
(and (evenp len)
(let ((mid (/ len 2)))
(equal (subseq s 0 mid)
(reverse (subseq s mid)))))))
이 함수를 이용해서 아래와 같은 회문을 찾아낼 수 있습니다:
> (mirror? '(a b b a))
T
Common Lisp는 sort라는 정렬 함수를 내장하고 있습니다. 시퀀스 하나와 두 인수를 비교하는 함수를 하나 받습니다. 그 다음, 이 비교 함수를 기준으로 정렬한 시퀀스를 반환합니다:
> (sort '(0 2 1 3 8) #'>)
(8 3 2 1 0)
sort 함수를 사용할 때는 조심해야 합니다. 파괴적이니까요. 효율을 끌어올리기 위해 sort 함수는 인수로 주어진 시퀀스를 임의로 변경할 수 있습니다. 그러므로 원본이 손상되는 것을 원하지 않는다면 복사본을 넘겨줘야 합니다.
sort와 nth를 이용하면 정수 n을 인수로 받아서 리스트에 있는 요소 중 n번째로 큰 요소를 반환하는 함수를 작성할 수 있습니다:
(defun nthmost (n lst)
(nth (- n 1)
(sort (copy-list lst) #'>)))
n번째로 큰 수를 찾으려고 하는데, 순서를 셀 때 0부터 시작하면 직관적이지 않기 때문에 nth를 호출할 때 1을 빼도록 만들었습니다.
> (nthmost 2 '(0 2 1 3 8))
3
조금 더 노력을 기울이면 이보다 효율적인 버전의 함수를 만들어낼 수도 있습니다.
every 함수와 some 함수는 술어와 하나 이상의 시퀀스를 받아들입니다. 단 하나의 시퀀스만 넘겨주는 경우에는 시퀀스의 각 요소가 술어를 만족하는지 테스트합니다:
> (every #'oddp '(1 3 5))
T
> (some #'evenp '(1 2 3))
T
두 개 이상의 시퀀스가 주어지는 경우라면, 테스트하는데 사용되는 술어 또한 주어지는 시퀀스의 갯수만큼 인수를 받아들일 수 있어야 합니다. 테스트를 수행할 때마다 각 시퀀스에서 뽑아낸 요소를 한 번에 여러 개의 인수로 던져넣으니까요:
> (every #'> '(1 3 5) '(0 2 4))
T
길이가 서로 다른 시퀀스가 주어지면, 가장 길이가 짧은 쪽에 맞춰서 테스트를 수행하게 됩니다.
스택
리스트는 여러 개의 cons가 연결된 것으로 표현되는데요. 이것을 그대로 스택처럼 사용할 수도 있습니다. Common Lisp에 보면 이런 목적으로 사용하기 위한 매크로가 두 개 있습니다: (push x y)는 x를 리스트 y의 앞에 밀어넣고, (pop x)는 리스트 x의 첫번째 요소를 제거하고 반환합니다.
둘 다 setf를 써서 정의되어 있습니다. 인수가 상수나 변수라면 호출을 변환하는 것이 매우 간단합니다. 표현식
(push obj lst)
은
(setf lst (cons obj lst))
와 동등하고, 표현식
(pop lst)
은 아래와 동등합니다.
(let ((x (car lst)))
(setf lst (cdr lst))
x)
아래의 예를 보세요:
> (setf x '(b))
(B)
> (push 'a x)
(A B)
> x
(A B)
> (setf y x)
(A B)
> (pop x)
A
> x
(B)
> y
(A B)
각 표현식의 실행 결과는 이렇습니다. 그림 3.9는 이 표현식들이 모두 수행되고 난 후의 구조입니다.
reverse 함수를 반복적인 버전으로 정의한다면 이런 식으로 push를 활용할 수 있습니다:
(defun our-reverse (lst)
(let ((acc nil))
(dolist (elt lst)
(push elt acc))
acc))
이 버전에서는 빈 리스트를 하나 준비해놓고 lst의 각 요소들을 계속 밀어넣습니다. 다 끝나면 lst의 마지막 요소가 제일 앞에 위치하게 됩니다.
pushnew 매크로는 push의 변종인데요. cons 대신 adjoin을 사용합니다:
> (let ((x '(a b)))
(pushnew 'c x)
(pushnew 'a x)
x)
(C A B)
이 결과를 보면, c는 리스트에 새로 추가되었지만 a는 이미 들어있었기 때문에 추가되지 않은 것을 알 수 있습니다.
점 찍힌 리스트
list 함수를 호출해서 만든 리스트를 좀 더 정확하게는 완전한 리스트라고 부릅니다. 완전한 리스트는 nil이거나 cdr을 취한 결과가 완전한 리스트인 cons로 정의됩니다. 즉, 완전한 리스트인 경우에만 참을 반환하는 술어는 이렇게 정의할 수 있습니다:
(defun proper-list? (x)
(or (null x)
(and (consp x)
(proper-list? (cdr x)))))
지금까지 우리가 만들어왔던 리스트는 모두 완전한 리스트입니다.
그렇지만 cons는 리스트 만드는데만 쓰라고 있는 것은 아닙니다. 딱 두 개의 필드가 필요한 경우에도 cons를 사용할 수 있습니다. car를 첫번째 필드를 가리키는데 사용하고, cdr를 두번째 필드를 가리키는데 사용하면 됩니다.
> (setf pair (cons 'a 'b))
(A . B)
이 cons는 완전한 리스트가 아닙니다. 이런 것은 점 표기법을 이용하여 표시됩니다. 점 표기법에서는 각 cons의 car와 cdr를 점으로 분리하여 표시합니다. 그림 3.10에 이 cons의 구조가 그려져 있습니다.
완전한 리스트가 아닌 cons는 점 찍힌 리스트라 불립니다. 사실 이런 명칭이 썩 좋다고 할 수는 없습니다. 완전한 리스트가 아닌 cons라고 해서 항상 리스트를 표현하는 것은 아니니까요. 예를 들어 (a . b)는 그냥 두 부분으로 나눠진 자료 구조를 의도한 것 뿐이죠.
완전한 리스트를 점 표기법으로 표현하는 것도 가능합니다. 그렇지만 리스프가 완전한 리스트를 표시할 때에는 항상 정규 리스트 표기법을 사용합니다:
> '(a . (b . (c . nil)))
(A B C)
얼핏 보면 그림 3.2에서 봤던 상자 표기법과 점 표기법으로 쓰여진 리스트가 비슷하다는 생각이 들겁니다.
정규 리스트 표기법과 점 찍힌 리스트 표기법 사이에 위치한 어중간한 형태의 표기법도 존재합니다.
> (cons 'a (cons 'b (cons 'c 'd)))
(A B C . D)
여기서 앞부분은 완전한 리스트 형태로 표시되었지만, 점이 찍힌 다음 마지막 cdr이 표시되어 있습니다. 그림 3.11이 이 리스트의 구조를 보여주고 있는데요. 그림 3.2와 이 그림을 비교해보면, 마지막 칸에 nil이 들어있다는 것만 제외하고 똑같다는 것을 알 수 있습니다.
결론적으로 리스트 (a b)를 표시하는데 쓸 수 있는 방법은 사실상 4가지입니다.
(a . (b . nil))
(a . (b))
(a b . nil)
(a b)
그렇지만 리스프가 이 리스트를 표시할 때는 항상 가장 마지막 형태를 사용합니다.
연관 리스트
cons를 연관 관계 표현에 사용할 수도 있습니다. 이런 cons의 리스트를 연관 리스트라고 합니다. 번역문의 집합을 표현할 때를 예로 들어보겠습니다:
> (setf trans '((+ . "add") (- . "subtract")))
((+ . "add") (- . "subtract"))
연관 리스트는 느리지만 프로그램을 처음 작성하는 단계에서 사용하기 매우 편하다는 장점이 있습니다. 게다가 Common Lisp는 키에 연관된 값을 꺼내는데 사용할 수 있는 assoc 함수를 내장하고 있습니다:
> (assoc '+ trans)
(+ . "add)
> (assoc '* trans)
NIL
assoc 함수가 검색에 실패하는 경우에는 nil을 반환합니다.
assoc 함수를 직접 간단하게 만들어본다면 이렇게 쓸 수 있겠죠:
(defun our-assoc (key alist)
(and (consp alist)
(let ((pair (car alist)))
(if (eql key (car pair))
pair
(our-assoc key (cdr alist))))))
member 함수처럼 assoc 함수도 :test나 :key 같은 키워드 인수를 받습니다. Common Lisp는 assoc-if 함수도 내장하고 있는데, 이 함수는 member 대신 member-if를 썼던 것과 동일한 용도로 사용됩니다.
예제: 최단 거리
그림 3.12
(defun shortest-path (start end net)
(bfs end (list (list start)) net))
(defun bfs (end queue net)
(if (null queue)
nil
(let ((path (car queue)))
(let ((node (car path)))
(if (eql node end)
(reverse path)
(bfs end
(append (cdr queue)
(new-paths path node net))
net))))))
(defun new-paths (path node net)
(mapcar #'(lambda (n)
(cons n path))
(cdr (assoc node net))))
그림 3.12의 코드는 네트워크에서 최단 거리를 찾는 프로그램입니다. shortest-path 함수는 시작 노드, 목표 노드, 네트워크를 입력으로 받아서 최단 경로를 반환합니다.
이 예제에서는 각 노드는 심볼로, 네트워크는 연관 리스트의 형태로 표현하고 있습니다. 리스트의 각 요소는 아래와 같은 형식을 사용합니다.
(노드 . 인접 노드들)
따라서 그림 3.13의 네트워크는 아래와 같이 표현됩니다.
(setf min '((a b c) (b c) (c d)))
그리고 어떤 노드에서 도달 가능한 노드를 찾으려면 이렇게 해야겠지요:
> (cdr (assoc 'a min))
(B C)
그림 3.12의 프로그램은 네트워크를 넓이 우선 탐색 알고리즘으로 검색합니다. 넓이 우선 탐색을 수행하기 위해서는 아직 지나가지 않은 노드의 목록을 담는 큐를 하나 유지해야 합니다. 노드를 하나 지나갈 때마다, 이 노드가 목적지인지 확인합니다. 만약 목적지가 아니면 이 노드에서 갈 수 있는 다른 노드들의 목록을 큐의 끝에 추가합니다. 다시 큐의 맨 앞에서 노드를 하나 꺼낸 다음에 검색을 계속 진행합니다. 항상 가장 멀리 있는 위치의 노드를 큐의 끝에 집어넣기 때문에, 네트워크를 한꺼풀씩 벗겨내면서 검색한다는 것을 확신할 수 있습니다.
그림 3.12의 코드는 위에서 말한 아이디어보다 약간 더 복잡한데요. 목적지만 찾는 것이 아니라, 어떻게 목적지까지 도달했는지 기록하기 때문입니다. 따라서 단순히 노드를 담는 큐만 유지하는 것이 아니라, 지나온 길을 담는 큐를 유지하는 것도 필요합니다. 검색을 계속할 때 큐에서 꺼내는 요소는 노드가 아니라 리스트입니다. 이 리스트의 맨 앞에 다음으로 검색할 노드가 있습니다.
bfs 함수는 검색을 수행합니다. 처음에는 큐 안에 단 하나의 요소만 존재합니다. 아직 시작도 안 했기 때문에 지나온 길은 시작 노드만 포함하고 있어야 할 것입니다. 따라서 shortest-path가 bfs를 호출할 때 (list (list start))를 초기 큐로 넘기게 됩니다.
bfs 내에서 제일 먼저 하는 일은 탐색할 노드가 더 남아있느냐를 확인하는 것입니다. 만약 큐가 비어있다면, bfs는 nil을 반환하여 경로를 찾지 못했다는 것을 알려줍니다. 아직 탐색할 노드가 남아있는 경우에는, 큐의 맨 앞에 있는 요소를 하나 꺼내옵니다. 맨 앞에 있는 요소가 목적지이면, 최단 경로를 찾은겁니다. 이걸 그냥 순서를 뒤집어서 반환하면 됩니다. 목적지가 아닌 경우에는 이 노드에서 도달할 수 있는 다른 노드들을 큐에 집어넣어야 합니다. 따라서 현재까지의 경로에 이웃 노드를 추가해서 큐의 끝에 집어넣습니다. 이렇게 bfs를 재귀적으로 호출하면서 큐를 끝까지 검색합니다.
bfs가 넓이 우선으로 검색하기 때문에, 가장 먼저 찾은 경로가 최단 경로이거나, 최단 경로 중 하나입니다:
> (shortest-path 'a 'd min)
(A C D)
bfs를 재귀적으로 호출하면서 큐는 아래와 같이 변화합니다:
((A))
((B A) (C A))
((C A) (C B A))
((C B A) (D C A))
((D C A) (D C B A))
여기에서 주기가 반복될 때마다 큐에서 두번째에 위치한 요소가 앞으로 이동하고, 첫번째 요소는 앞에 노드가 추가된 채로 큐의 끝에 추가된다는 것을 알 수 있습니다.
그림 3.12의 코드가 네트워크를 검색하는 가장 빠른 방법은 아닙니다. 그렇지만 이 예제를 통해 리스트를 얼마나 다양한 방법으로 사용할 수 있는지 깨달았을 것입니다. 이 간단한 프로그램에서는 리스트를 3가지 용도로 사용했습니다. 첫번째, 경로를 표현하기 위해 심볼의 리스트를 사용했습니다. 두번째, 넓이 우선 검색을 수행할 때 큐를 표현하기 위해 경로의 리스트를 사용했습니다. 세번째, 네트워크 자체를 표현하기 위해 연관 리스트를 사용했습니다.
쓰레기
리스트는 여러가지 이유로 느릴 수 있습니다. 리스트는 임의의 위치로 접근하는 것을 지원하지 않습니다. 오직 처음부터 순차적으로 읽는 것만 가능합니다. 따라서 어떤 요소를 가져올 때에는 배열보다 리스트가 더 오래 걸립니다. 디스크보다 테이프에서 뭔가 검색하는 것이 더 오래 걸리는 것과 똑같은 이유이지요. 내부적으로 cons는 보통 포인터로 표현되기 때문에, 리스트를 순회한다는 것은 배열에서처럼 단순히 인덱스만 증가시키면 되는 것이 아니라 일련의 포인터를 타고 내려간다는 것을 의미합니다. 그렇지만 이런 비용은 cons 여러 개를 할당하고 해제하는 것에 비하면 작은 것입니다.
자동 메모리 관리는 리스프의 가장 훌륭한 기능 중 하나입니다. 리스프 시스템은 힙이라고 불리는 메모리 덩어리를 관리합니다. 시스템은 힙에서 사용되지 않고 있는 메모리들을 유지하고 있다가, 새로운 객체가 만들어지면 메모리를 나눠줍니다. 예를 들어 cons 함수는 새로 할당된 cons를 반환합니다. 힙에서 메모리를 할당하는 것은 일반적으로 consing이라고 알려져 있습니다.
이런 메모리들은 리스프가 새로운 객체에게 할당해 줄 메모리가 모자라거나, 리스프 시스템을 종료하는 경우가 아니면 절대로 해제되지 않습니다. 그러므로 시스템은 반드시 주기적으로 힙을 검사하면서 더 이상 사용되지 않는 메모리를 찾아내야 합니다. 더 이상 사용되지 않는 메모리를 쓰레기라고 부릅니다. 그리고 이렇게 쓰레기를 찾아다니는 연산 과정을 쓰레기 수집(garbage collection) 또는 GC라고 부릅니다.
이런 쓰레기는 언제 발생하는 것일까요? 한 번 쓰레기를 만들어봅시다:
> (setf lst (list 'a 'b 'c))
(A B C)
> (setf lst nil)
NIL
초기에 우리는 list를 호출했습니다. list는 힙에 새로 cons를 할당하는 cons 함수를 호출하게 되어있구요. 이 경우에는 cons가 세 개 만들어집니다. lst를 nil로 설정하게 되면, 우리는 더 이상 어떤 방법으로도 lst의 예전 값인 리스트 (a b c)를 참조할 방법이 없습니다.
이 리스트에 더 이상 접근할 수 있는 방법이 없기 때문에, 아예 존재하지 않는 것으로 취급할 수 있습니다. 어떤 방법으로도 도달 불가능한 객체는 쓰레기입니다. 시스템은 이런 cons들을 안전하게 재활용할 수 있습니다.
메모리 관리가 자동으로 되기 때문에 프로그래머 입장에서는 굉장히 편합니다. 명시적으로 메모리를 할당하거나 해제할 필요가 전혀 없으니까요. 게다가 이것은 메모리 할당과 해제에 관련된 버그를 완전히 잊어버려도 된다는 말입니다. 메모리가 샌다든지 연결이 끊어진 포인터가 존재한다는 것은 리스프에서 아예 불가능한 일입니다.
그렇지만 어떤 기술적인 진보에 있어서도 마찬가지로, 여러분이 부주의할 경우 자동 메모리 관리가 해가 될 수도 있습니다. 일반적으로 힙 공간을 사용하고 재활용하는데 관련된 비용은 간단히 cons를 만드는 비용이라고 생각할 수 있습니다. 어차피 프로그램이 아무 것도 버리지 않는 경우가 아니라면, 만들어진 cons의 대부분은 언젠가 쓰레기가 되기 때문에 이런 생각은 합리적입니다. cons를 만드는데 있어서의 문제는 메모리 공간을 할당하고 찾아다니는 것이, 프로그램의 일반적인 연산을 수행하는 것보다 훨씬 비싼 댓가를 치루는 일이라는 것입니다. 최근의 연구를 통해 쓰레기 수집 알고리즘을 극적으로 개선하기는 했지만, cons를 만들어내는 것은 여전히 비용이 드는 일이고, 게다가 현존하는 몇몇 리스프 시스템에서는 이것이 정말 큰 비용을 수반합니다.
여러분이 주의하지 않는다면 과도하게 cons를 생성하는 프로그램이 나오기 쉽습니다. 예를 들어 remove는 원하는 요소가 배제된 리스트를 새로 만들어 내는 과정에서 cons를 모두 복사하게 됩니다. 이렇게 불필요하게 cons를 만들지 않으려면 파괴적인 함수를 사용하는 방법을 쓸 수 있습니다. 파괴적인 함수들은 인수로 넘긴 리스트의 구조의 대부분을 재사용합니다. 파괴적인 함수들은 12.4절에서 소개됩니다.
cons를 매우 많이 만들어내는 프로그램을 작성하는 것이 쉬운 반면에, cons를 전혀 사용하지 않는 프로그램을 작성하는 것도 역시 가능합니다. 전형적인 접근법은 일단 프로그램의 초기 버전을 순수하게 함수형 스타일로 리스트를 아주 많이 사용해서 작성하는 것입니다. 그 다음 프로그램을 키워나가면서 코드의 핵심적인 부분을 파괴적인 연산이나 다른 자료 구조로 대체합니다. 그렇지만 consing에 대해 일반적인 조언을 하기는 좀 어렵습니다. 어떤 리스프 구현체에서는 메모리 관리를 아주 잘 하기 때문에, cons를 쓰는 것이 그렇지 않은 코드보다 더 빠른 경우도 있습니다. 이 모든 문제들은 13.2절에서 설명하겠습니다.
어쨌든 실험작이나 프로토타입을 만들 때에 한해서는 부담없이 cons를 만들어도 됩니다. 프로그램의 초기 단계에서 리스트가 주는 유연함을 취한다면 시간이 흘러도 살아남는 코드를 만들 수 있을 것입니다.
요약
- cons는 두 부분으로 나누어진 자료 구조입니다. 리스트는 cons 여러 개를 연결해서 만들어집니다.
- equal은 eql보다 느슨한 기준을 가지고 있습니다. 간단하게 말하자면 equal은 주어진 인수들이 서로 같은 것을 출력하면 참을 반환합니다.
- 모든 리스프 객체는 포인터처럼 행동합니다. 포인터들을 명시적으로 조작하는 것은 불가능합니다.
- 리스트를 복사할 때에는 copy-list 함수를 사용할 수 있고, 리스트에 다른 요소를 붙이려면 append 함수를 사용할 수 있습니다.
- Run-length encoding은 레스토랑에서 사용하는 간단한 압축 알고리즘입니다.
- Common Lisp는 car와 cdr의 조합으로 구현된 다양한 접근 함수를 지원합니다.
- 매핑 함수들은 함수를 리스트의 각 요소에, 혹은 각 꼬리 부분에 적용합니다.
- 중첩된 리스트에 대한 연산은 가끔 트리에 행하는 연산처럼 취급됩니다.
- 재귀적인 함수가 올바른지 판단하려면 그냥 모든 경우의 수를 처리하는지 확인하세요.
- 리스트로 집합을 표현할 수 있습니다. 몇몇 내장 함수가 리스트를 집합의 관점에서 다룹니다.
- 키워드 인수는 옵션입니다. 그리고 위치에 의해서 인식되는 대신 앞에 붙은 심볼 태그로 인식됩니다.
- 리스트는 시퀀스의 하위 타입입니다. Common Lisp는 아주 많은 수의 시퀀스 처리 함수를 가지고 있습니다.
- 완전한 리스트가 아닌 cons는 점 찍힌 리스트라 불립니다.
- cons들을 요소로 가지는 리스트는 매핑을 표현하는데 사용될 수 있습니다. 이런 리스트들은 연관 리스트라 불립니다.
- 자동 메모리 관리 기능이 있어서 메모리 할당에 관련된 일을 하지 않아도 되지만, 과도하게 쓰레기를 만들어내면 프로그램이 느려집니다.
연습 문제
- 아래에 주어진 리스트들을 상자 표기법으로 써보세요:
(a) (a b (c d))
(b) (a (b (c (d))))
(c) (((a b) c) d)
(d) (a (b . c) . d) - 각 원본 리스트에 들어있는 요소들의 순서를 그대로 보존하는 union 함수를 작성해보세요:
> (new-union '(a b c) '(b a d))
(A B C D) - 리스트를 하나 받아서 그 리스트에 같은(eql) 객체가 몇 번 나왔는지 리스트로 반환하는 함수를 작성하세요. 반환하는 리스트는 가장 많이 나온 요소가 앞으로 나오도록 정렬되어 있어야 합니다:
> (occurrences '(a b a d a c d c a))
((A . 4) (C . 2) (D . 2) (B . 1)) - 왜 (member '(a) '((a) (b)))가 nil을 반환할까요?
- pos+ 함수는 하나의 리스트를 받아서 각 요소에 해당 요소의 인덱스만큼 더한 리스트를 반환합니다. 아래 함수를 (a) 재귀적으로 (b) 반복적으로 (c) mapcar를 써서 다시 작성해보세요:
> (pos+ '(7 5 1 4))
(7 6 3 7) - 몇 년의 고심 끝에 정부 위원회는 리스트의 car와 cdr이 바뀌어야 한다고 결정했습니다. 이제 cdr가 첫번째 요소를 가리켜야 하고, car가 리스트의 나머지 부분을 가리켜야 합니다. 아래 함수들을 정부 버전으로 다시 정의해보세요:
(a) cons
(b) list
(c) length (리스트 용)
(d) member (리스트 용, 키워드 인수 없음) - 그림 3.6의 프로그램을 수정해서 cons를 덜 사용하도록 바꿔보세요. (힌트: 점 찍힌 리스트를 사용하세요)
- 리스트를 하나 받아서 점 표기법으로 출력하는 함수를 정의하세요.
> (showdots '(a b c))
(A . (B . (C . NIL)))
NIL - 3.15절에서 표현된 네트워크에서 가장 긴 유한 경로를 찾는 프로그램을 작성하세요. 네트워크는 순환 고리를 포함할 수도 있습니다.
덧글