이 외에도 Common Lisp에는 인스턴스라는 자료 구조도 존재합니다. 이것은 11장에서 CLOS와 함께 다루겠습니다.
배열
Common Lisp에서 배열을 만드려면 make-array 함수를 호출합니다. 함수를 호출할 때에는 첫번째 인수로 차원을 담은 리스트를 넘겨야 합니다. 2x3 배열을 만드려면 이렇게 합니다:
> (setf arr (make-array '(2 3) :initial-element nil))
#<Simple-Array T (2 3) BFC4FE>
Common Lisp의 배열은 최소한 7개의 차원을 가질 수 있도록 되어있습니다. 그리고 각 차원은 최소한 1023개의 요소를 가질 수 있지요.
:initial-element 인수는 옵션입니다. 이 키워드 인수를 넘기게 되면 배열 전체가 지정한 값으로 초기화됩니다. 초기화되지 않은 배열의 요소를 가져오려고 시도할 때 발생하는 일은 정의되어 있지 않습니다.
배열의 특정 요소를 가져오려고 할 때에는 aref 함수를 사용합니다. 일반적인 Common Lisp 접근 함수들처럼 aref도 0부터 시작하는 인덱스를 사용합니다:
(aref arr 0 0)
NIL
배열의 특정 요소를 바꾸려면, setf를 aref와 같이 사용합니다:
> (setf (aref arr 0 0) 'b)
B
> (aref arr 0 0)
B
배열을 문자로 표현할 때에는 #na 문법을 사용합니다. n은 배열의 차원입니다. 예를 들어, 위의 arr과 동등한 배열을 아래와 같이 표기할 수 있습니다:
#2a ((b nil nil) (nil nil nil))
전역 변수 *print-array*가 t인 경우 배열은 이런 형태로 출력될 것입니다
> (setf *print-array* t)
T
> arr
#2A((B NIL NIL) (NIL NIL NIL))
1차원 배열만을 원한다면, make-array의 첫번째 인수에 리스트를 넣는 대신 그냥 정수 하나를 넘겨도 됩니다:
> (setf vec (make-array 4 :initial-element nil))
#(NIL NIL NIL NIL)
1차원 배열은 벡터라고도 불립니다. 길게 쓸 것 없이 vector 함수만 호출하면 한 번에 벡터를 만들어서 주어진 인수로 초기화까지 할 수 있습니다:
> (vector "a" 'b 3)
#("a" B 3)
벡터를 문자로 표현할 때에는 이런 문법으로 표시됩니다. 배열을 문자로 표시할 때 #na를 사용하는 것과 비슷하지요.
벡터의 요소를 접근할 때에도 aref를 사용할 수 있습니다만, 벡터에는 svref 함수를 사용하는 것이 더 빠릅니다.
> (svref vec 0)
NIL
이 함수의 이름에 써있는 "sv"는 "simple vector"의 약자입니다. 모든 벡터는 기본적으로 간단한 벡터(simple vector)에 해당됩니다.
(defun bin-search (obj vec)
(let ((len (length vec)))
(and (not (zerop len))
(finder obj vec 0 (- len 1)))))
(defun finder (obj vec start end)
(let ((range (- end start)))
(if (zerop range)
(if (eql obj (aref vec start))
obj
nil)
(let ((mid (+ start (round (/ range 2)))))
(let ((obj2 (aref vec mid)))
(if (< obj obj2)
(finder obj vec start (- mid 1))
(if (> obj obj2)
(finder obj vec (+ mid 1) end)
obj)))))))
예제: 이진 검색
이 절에서는 정렬된 벡터를 대상으로 특정 객체를 검색하는 함수를 어떻게 작성하는지 보여드리겠습니다. 어떤 벡터가 정렬되어 있기만 하다면, 그냥 앞에서부터 순서대로 뒤지는 것(65쪽 find)보다 훨씬 나은 방법으로 검색할 수 있습니다. 먼저 벡터의 가운데 부분을 찾아봅니다. 딱 찍어서 맞았으면 검색 끝난거죠. 그렇지 않다면 벡터의 왼쪽이나 오른쪽을 찾아야 합니다. 가운데 요소보다 우리가 찾으려는 객체가 작으면 왼쪽, 크면 오른쪽 부분을 찾아나가면 됩니다.
그림 4.1은 이런 방식으로 동작하는 함수를 포함하고 있습니다. bin-search 함수는 검색할 구간을 초기화하고 finder를 호출합니다. finder는 벡터 vec의 start와 end 구간 사이에 있는 obj를 검색합니다.
검색 구간의 길이가 0이 되었을 때, 마지막 요소가 찾는 요소이면 obj를 반환하고 그렇지 않으면 nil을 반환합니다. 검색 구간 내에 요소가 몇 개 있는 경우에는 가운데 지점을 찾아서 (round 함수는 주어진 인수에 가장 가까운 정수를 반환합니다.) 그 위치에 있는 요소를 살펴봅니다. (obj2) 만약 obj가 obj2보다 작으면 검색은 벡터의 왼쪽 절반을 재귀적으로 검색해나갑니다. obj가 obj2보다 큰 경우에는 벡터의 오른쪽 절반을 재귀적으로 검색해나가구요. 남아있는 것은 이제 obj = obj2인 경우인데 이 경우에는 우리가 원하는 것을 찾았으니 그냥 반환해버리면 됩니다.
주석을 쓰는 방법
Common Lisp 코드에서는 세미콜론 뒤에 오는 모든 것이 주석으로 취급됩니다.
Lisp 프로그래머들은 여러 개의 세미콜론을 묶어서 주석을 구조적으로 표시하는데 사용합니다:
네 개의 세미콜론은 제목, 세 개의 세미콜론은 함수나 매크로의 설명,
두 개의 세미콜론은 줄 단위 주석으로 사용하고, 한 개의 세미콜론은 코드와 같은 줄의 끝에 주석을 달 때 사용합니다.
이런 방식대로 그림 4.1에 주석을 달아보자면 이렇게 되겠습니다:
;;;; 정렬된 벡터를 대상으로 연산을 수행하는 유틸리티
;;; 정렬된 벡터에서 특정 요소를 찾는다.
(defun bin-search (obj vec)
(let ((len (length vec)))
;; 진짜 벡터라면 finder에게 넘긴다
(and (not (zerop len)) ; 비어있는 벡터라면 nil을 반환한다
(finder obj vec 0 (- len 1)))))
주석을 아주 많이 써야하는 경우에는 #|...|# read-macro를 사용하는 것이 좋습니다. read는 #|와 |# 사이에 있는 모든 문자를 무시합니다.
finder 시작 부분에 아래의 코드를 한 줄 더 집어넣으면
(format t "~A~%" (subseq vec start (+ end 1)))
각 단계마다 검색 대상이 되는 절반 부분에 속한 숫자들을 볼 수 있습니다:
> (bin-search 3 #(0 1 2 3 4 5 6 7 8 9))
#(0 1 2 3 4 5 6 7 8 9)
#(0 1 2 3)
#(3)
3
문자열과 문자
문자열은 문자로 이루어진 벡터입니다. 상수 문자열을 표기할 때에는 큰 따옴표 안에 문자들을 나열합니다. c라는 문자 하나는 #\c로 표기합니다.
각 문자는 정수와 연관되어 있습니다 - 항상 그렇다고는 할 수 없지만 보통은 아스키 숫자이지요: 대부분의 구현체에서는 char-code 함수가 문자에 연관된 숫자를 반환해줍니다. code-char는 반대로 숫자에 연관된 문자를 되돌려줍니다.
char< (작은), char<= (작거나 같은), char= (같은), char>= (크거나 같은), char> (큰), char/= (같지 않은) 함수들은 문자를 비교합니다. 이들은 146쪽에 설명된 숫자 비교 연산자와 비슷하게 동작하지요.
> (sort "elbow" #'char<)
"below"
문자열이 벡터이기 때문에, 시퀀스 함수들이나 배열 함수들 모두 문자열에 적용할 수 있습니다. 똑같이 aref를 써서 요소를 가져올 수 있습니다. 예를 들면,
> (aref "abc" 1)
#\b
그렇지만 문자열에는 char 함수를 쓰는 것이 더 빠릅니다:
> (char "abc" 1)
#\b
setf 함수와 char (또는 aref)를 같이 사용하면 요소를 바꿔 쓸 수 있습니다:
> (let ((str (copy-seq "Merlin")))
(setf (char str 3) #\k)
str)
"Merkin"
두 개의 문자열을 비교할 때에는 equal을 사용할 수 있습니다. 대소문자를 무시하고 비교하려면 string-equal을 사용하면 됩니다:
> (equal "fred" "fred")
T
> (equal "fred" "Fred")
NIL
> (string-equal "fred" "Fred")
T
Common Lisp는 문자열을 비교하고 조작하는 많은 수의 함수들을 제공하고 있습니다. 전체 목록은 부록 D의 364쪽에서 찾아볼 수 있습니다.
문자열을 만드는 몇 가지 방법이 있는데요. 가장 일반적인 방법은 format을 사용하는 것입니다. 첫번째 인수에 nil을 주고 format을 호출하면 화면에 문자열을 출력하지 않고 반환합니다:
> (format nil "~A or ~A" "truth" "dare")
"truth or dare"
문자열 여러 개를 합치고 싶은 경우라면 concatenate 함수를 사용할 수 있습니다. 이 함수는 반환값의 타입을 나타내는 심볼과 하나 이상의 시퀀스를 받습니다:
> (concatenate 'string "not " "to worry")
"not to worry"
시퀀스
Common Lisp의 sequence 타입은 리스트와 벡터를 포함합니다. (당연히 문자열도 포함됩니다.) 리스트에 사용해왔던 함수들 중 일부는 사실 시퀀스 함수들입니다. remove, length, subseq, reverse, sort, every, some 같은 함수들은 시퀀스 함수입니다. 따라서 46쪽에서 작성했던 함수는 다른 종류의 시퀀스에 대해서도 마찬가지로 동작합니다:
> (mirror? "abba")
T
앞에서 이미 시퀀스 내에서 요소를 꺼내오는 네 가지 함수를 봤습니다: 리스트에는 nth, 벡터에는 aref와 svref, 문자열에는 char를 사용했었지요. Common Lisp는 어떤 종류의 시퀀스에도 사용할 수 있는 elt 함수를 제공합니다:
> (elt '(a b c) 1)
B
특정 타입의 시퀀스에 대해서는, 이미 봤던 것처럼 더 빠른 접근 함수가 있습니다. 따라서 시퀀스를 아주 일반적으로 다루어야 할 코드 외에는 elt 함수를 사용할 일이 별로 없을 것입니다.
elt 함수를 사용해서 벡터에 더 효율적인 mirror? 함수를 만들어 보겠습니다.
(defun mirror? (s)
(let ((len (length s)))
(and (evenp len)
(do ((forward 0 (+ forward 1))
(back (- len 1) (- back 1)))
((or (> forward back)
(not (eql (elt s forward)
(elt s back))))
(> forward back))))))
이 버전은 리스트에도 써먹을 수는 있겠지만 벡터에 더 잘 맞도록 되어있습니다. 리스트는 순차적인 접근 밖에 할 수 없기 때문에, elt를 자주 호출하는 것은 굉장히 비효율적입니다. 벡터는 임의 접근을 지원하므로 아무 요소나 마음대로 접근해도 별 문제가 없습니다.
시퀀스 함수들은 대부분 아래 테이블에 나열된 키워드 인수들을 받아들입니다:
| 매개변수 | 목적 | 기본값 |
| :key | 각 요소에 적용할 함수 | identity |
| :test | 비교 함수 | eql |
| :from-end | 참인 경우 끝에서부터 동작 | nil |
| :start | 시작 위치 | 0 |
| :end | 정지 위치 | nil |
이 모든 것을 받아들이는 함수로는 position이 있습니다. 이 함수는 특정 요소를 찾아서 그 위치를 반환합니다. 찾지 못한 경우에는 nil을 반환하구요. position을 이용해서 위에서 제시한 각 키워드 인수의 역할을 확인해봅시다:
> (position #\a "fantasia")
1
> (position #\a "fantasia" :start 3 :end 5)
4
두번째 예제는 네번째부터 여섯번째 문자 사이에 있는 a의 위치를 찾아달라고 한 것입니다. :start 인수는 고려해야 할 첫번째 요소의 위치입니다. 기본값은 시퀀스의 첫번째 요소입니다. :end 인수는 고려하지 말아야 할 첫번째 요소의 위치입니다.
만약 :from-end 인수를 주게 되면,
> (position #\a "fantasia" :from-end t)
7
끝에 가장 가까운 a의 위치를 얻게 됩니다. 끝에서부터 찾았다고는 하지만 위치는 일반적인 경우처럼 표시됩니다; 즉, 끝에서부터의 거리가 아니라 앞에서부터의 거리이지요.
:key 인수는 시퀀스에서 각 요소를 꺼내 비교하기 전에 적용할 함수입니다. 아래와 같은 경우,
> (position 'a '((c d) (a b)) :key #'car)
1
car를 적용한 결과가 심볼 a인 첫번째 요소의 위치를 찾으라고 하는 것이 됩니다.
:test 인수는 두 개의 인수를 받아서 비교하는 함수를 정의합니다. 기본값은 항상 eql입니다. 만약 리스트를 비교하고자 한다면, equal을 사용해야 합니다:
> (position '(a b) '((a b) (c d)))
NIL
> (position '(a b) '((a b) (c d)) :test #'equal)
0
:test 인수는 두 개의 인수를 받아들이는 어떤 함수라도 가능합니다. 예를 들어 < 함수를 주게 되면 첫번째 인수보다 큰 첫번째 요소의 위치를 얻게됩니다:
> (position 3 '(1 0 7 5) :test #'<)
2
subseq와 position 함수를 사용하면 시퀀스의 일부분을 얻는 함수를 작성할 수 있습니다. 예를 들어 이 함수는
(defun second-word (str)
(let ((p1 (+ (position #\ str) 1)))
(subseq str p1 (position #\ str :start p1))))
공백으로 구분되는 단어 중 두 번째 단어를 문자열로 반환합니다:
> (second-word "Form follows function.")
"follows"
하나의 인수만 받아들이는 술어를 만족시키는 요소를 찾는 경우에는 position-if를 사용합니다. 이 함수는 함수 하나와 시퀀스를 받아서, 함수를 만족시키는 첫번째 요소의 위치를 반환합니다:
> (position-if #'oddp '(2 3 4 5))
1
이 함수는 :test만 제외하고 모든 키워드 인수를 받아들입니다.
이 외에도 member나 member-if와 비슷한 시퀀스 함수들이 있습니다. 바로 find(모든 키워드 인수를 받아들입니다.)와 find-if(:test만 제외하고 모든 키워드 인수를 받아들입니다.) 입니다:
> (find #\a "cat")
#\a
> (find-if #'characterp "ham")
#\h
member나 member-if와는 다르게, 이 함수들은 찾고 있던 객체만 반환합니다.
find-if 대신 find와 :key 인수의 조합으로 바꿔서 쓰는 것이 더 깔끔한 경우가 많습니다. 예를 들어 표현식
(find-if #'(lambda (x)
(eql (car x) 'complete))
lst)
이렇게 쓰는 것보다 아래와 같이 쓰는 편이 훨씬 깔끔하죠.
(find 'complete lst :key #'car)
remove(22쪽)와 remove-if 함수 역시 어떤 종류의 시퀀스에도 동작합니다. 두 함수의 관계는 find와 find-if의 관계와 같습니다. 관련된 함수로는 remove-duplicates가 있는데, 이 함수는 시퀀스 내에서 중복된 요소들을 제거하고 마지막 요소만 남겨둡니다:
> (remove-duplicates "abracadabra")
"cdbra"
이 함수도 표에 나왔던 모든 키워드 인수들을 지원합니다.
reduce 함수는 시퀀스를 하나의 값으로 줄여버립니다. 적어도 함수와 시퀀스, 이렇게 두 개의 인수를 받게 되어 있습니다. 가장 간단한 경우에는 처음 두 개의 요소를 주어진 함수에 넣습니다. 시퀀스의 다음 요소를 두 번째 인수로, 마지막 호출 결과를 첫번째 인수로 함수를 호출하는 과정을 반복합니다. 마지막 함수 호출에서 반환되는 값이 reduce의 값입니다. 따라서 다음과 같은 표현식은,
(reduce #'fn '(a b c d))
아래의 표현식과 동등합니다.
(fn (fn (fn 'a 'b) 'c) 'd)
reduce를 이용하면 두 개의 인수만 받는 함수들을 확장할 수 있습니다. 가령 세 개 이상의 리스트를 대상으로 교집합을 구하려면 이렇게 쓸 수 있습니다.
> (reduce #'intersection '((b r a d 's) (b a d) (c a t)))
(A)
예제: 날짜 파싱
이 절에서는 시퀀스 연산에 대한 한 가지 예로 날짜를 파싱하는 프로그램을 하나 보여드리겠습니다. "16 Aug 1980" 같은 문자열을 받아서 일, 월, 년도를 표현하는 정수의 리스트를 반환하는 프로그램을 작성할 겁니다.
(defun tokens (str test start)
(let ((p1 (position-if test str :start start)))
(if p1
(let ((p2 (position-if #'(lambda (c)
(not (funcall test c)))
str :start p1)))
(cons (subseq str p1 p2)
(if p2
(tokens str test p2)
nil)))
nil)))
(defun constituent (c)
(and (graphic-char-p c)
(not (char= c #\ ))))
그림 4.2: 토큰 인식
그림 4.2는 이 응용 프로그램에서 우리가 필요로 하는 다용도의 파싱 함수를 포함하고 있습니다. 먼저 tokens 함수는 문자열에서 토큰을 추출하기 위해 사용됩니다. 문자열과 테스트 함수를 주면, 주어진 테스트 함수를 만족하는 문자열로 이루어진 부분 문자열로 구성된 리스트를 반환합니다. 예를 들어, 알파벳 문자를 가려내는 alpha-char-p 함수를 테스트 함수로 사용하게 되면:
> (tokens "ab12 3cde.f" #'alpha-char-p 0)
("ab" "cde" "f")
이 함수를 만족시키지 못하는 모든 문자들은 공백으로 취급됩니다 - 토큰을 분리시키는데 이용되지만 토큰의 일부로 포함되지는 않습니다.
constituent 함수는 tokens에 인수로 넘길 용도로 만들어진 것입니다. Common Lisp에서는 그래픽 문자란 우리가 볼 수 있는 모든 문자를 의미합니다. 여기에는 스페이스도 포함됩니다. 따라서 constituent를 테스트 함수로 사용하게 되면,
> (tokens "ab12 3cde.f
gh" #'constituent 0)
("ab12" "3cde.f" "gh")
tokens 함수는 관습적인 개념의 공백(whitespace)을 처리할 수 있게 됩니다.
그림 4.3은 날짜 파싱에 사용되는 함수들을 포함하고 있습니다. parse-date 함수는 정해진 양식의 날짜를 받아서 각 구성 요소를 표현하는 정수의 리스트를 반환합니다:
(defun parse-date (str)
(let ((toks (tokens str #'constituent 0)))
(list (parse-integer (first toks))
(parse-month (second toks))
(parse-integer (third toks)))))
(defconstant month-names
#("jan" "feb" "mar" "apr" "may" "jun"
"jul" "aug" "sep" "oct" "nov" "dec"))
(defun parse-month (str)
(let ((p (position str month-names
:test #'string-equal)))
(if p
(+ p 1)
nil)))
그림 4.3: 날짜 파싱 함수들
> (parse-date "16 Aug 1980:)
(16 8 1980)
이 함수는 tokens 함수를 사용해서 날짜 문자열을 쪼갠 후, 각 요소를 해석하기 위해 parse-month와 parse-integer 함수를 호출합니다. 달을 찾을 때는 parse-month 함수를 호출하는데, 여기서 string-equal 함수를 쓰기 때문에 대소문자를 가리지 않고 달의 이름을 비교하게 됩니다. 일자와 년도를 찾을 때에는 내장 함수인 parse-integer 함수를 사용하는데, 이 함수는 문자열을 받아서 거기에 대응하는 정수를 반환하도록 되어 있습니다.
만약 직접 정수를 파싱하는 함수를 작성해야 한다면 이렇게 쓸 수 있을 것입니다:
(defun read-integer (str)
(if (every #'digit-char-p str)
(let ((accum 0))
(dotimes (pos (length str))
(setf accum (+ (* accum 10)
(digit-char-p (char str pos)))))
accum)
nil))
이 코드는 Common Lisp에서 어떻게 문자를 숫자로 바꾸는지 보여줍니다. digit-char-p 함수는 문자가 숫자에 해당되는지 테스트할 뿐 아니라 문자에 대응하는 정수까지 반환해줍니다.
구조체
구조체는 벡터의 확장판이라고 생각할 수 있습니다. 가령 다수의 네모난 물체를 추적하는 프로그램을 작성한다고 해봅시다. 3개의 요소 - 높이, 너비, 깊이 - 를 가진 벡터를 사용해서 네모난 물체를 표현할 수 있습니다. 그런데 아무래도 svref 함수를 그냥 쓰는 것보다는 아래와 같은 함수를 정의하는 편이 훨씬 읽기 쉬울겁니다.
(defun block-height (b) (svref b 0))
따라서 구조체는 벡터와 함께 이런 함수들이 모두 미리 정의된 상태로 딸려오는 것이라고 생각할 수 있겠습니다.
구조체를 정의할 때는 defstruct를 사용합니다. 가장 간단한 경우에는 그냥 구조체의 이름과 각 필드의 이름만 써주면 됩니다.
(defstruct point
x
y)
이렇게 쓰면 x와 y, 두 개의 필드를 가진 point라는 구조체를 정의한 것이 됩니다. 게다가 암시적으로 make-point, point-p, copy-point, point-x, point-y 함수도 정의한 것이 됩니다.
예전에 2.3절에서 Lisp 프로그램을 만드는 Lisp 프로그램에 대해 언급한 적이 있었는데요. 우리가 지금까지 봤던 것들 중에 이것이 가장 두드러지는 예제라고 할 수 있겠습니다. defstruct를 호출하기만 하면 자동으로 몇몇 함수들을 정의하는 코드를 생성하니까요. 매크로를 사용하면 여러분도 이런 일을 똑같이 해낼 수 있습니다. (원한다면 defstruct를 직접 작성할 수도 있지요.)
make-point를 호출하면 항상 새로운 point를 생성하게 됩니다. 이 때 각 필드를 대응되는 키워드 인수를 이용해서 초기화 하는 것이 가능합니다:
> (setf p (make-point :x 0 :y 0))
#S(POINT X 0 Y 0)
point 접근 함수들은 값을 가져오는 용도 외에 setf를 쓸 때에도 사용할 수 있습니다.
> (point-x p)
0
> (setf (point-y p) 2)
2
> p
#S(POINT X 0 Y 2)
구조체를 정의하면 타입의 이름도 지정하는 것이 됩니다. 각 point는 point 타입이며, 구조체이고, 원자이며, 참입니다. 그렇기 때문에 어떤 것이 point인지 테스트할 때에는 point-p 뿐 아니라 다용도로 쓰이는 함수인 typep를 사용할 수도 있습니다.
> (point-p p)
T
> (typep p 'point)
T
구조체 필드의 기본값을 지정할 때에는 필드 이름과 기본값을 나타내는 표현식을 리스트 안에 집어넣는 형태로 바꾸기만 하면 됩니다.
(defstruct polemic
(type (progn
(format t "What kind of polemic was it? ")
(read)))
(effect nil))
make-polemic을 아무런 초기 값 없이 호출하게 되면 미리 지정한 표현식의 값으로 설정됩니다.
> (make-polemic)
What kind of polemic was it? scathing
#S(POLEMIC TYPE SCATHING EFFECT NIL)
구조체가 화면에 출력되는 방법을 제어할 수도 있습니다. 자동으로 만들어지는 접근 함수들의 접두어를 바꿀 수도 있구요. 이 두 가지를 보여드리기 위해 좀 더 장황하게 point를 정의해봤습니다:
(defstruct (point (:conc-name p)
(:print-function print-point))
(x 0)
(y 0))
(defun print-point (p stream depth)
(format stream "#<~A, ~A>" (px p) (py p)))
:conc-name 인수는 접근 함수를 만들 때 필드 이름 앞에 붙는 문자열을 결정합니다. 기본값이 적용되었을 때는 point-가 앞에 붙었습니다만, 지금은 그냥 단순히 p만 앞에 붙었습니다. 이렇게 쓰면 코드를 읽기가 좀 어려워지긴 하지만, 이런 접근 함수를 자주 사용한다면 함수 이름의 길이를 조금이라도 줄이고 싶을테니까요.
:print-function은 point를 화면에 출력할 때 사용할 함수의 이름을 지정합니다. 이 함수는 반드시 세 개의 인수를 받아야 합니다. 첫번째 인수는 출력될 구조체가 오고, 두번째 인수는 출력될 위치가 옵니다. 세번째 인수는 일반적으로 무시합니다. 나중에 7.1절에서 스트림을 다루게 될텐데요. 지금 당장은 스트림을 받아서 format에 넘기면 된다는 것만 기억해두시면 됩니다.
print-point 함수는 아래와 같이 축약된 형태로 point를 표현하게 됩니다.
> (make-point)
#<0,0>
예제: 이진 검색 트리
sort 함수는 Common Lisp에 내장되어 있기 때문에 직접 정렬 코드를 작성해야 되는 경우는 거의 없습니다. 이 절에서는 당장 가져다가 쓸 것이 없는 문제를 어떻게 풀어내는지 보여드리려고 합니다. 객체를 정렬된 상태로 유지하는 문제인데요. 여기에서 제시하는 코드는 객체를 이진 검색 트리에 저장하게 될겁니다. 이진 검색 트리가 잘 균형이 잡혀있다고 가정하면 요소를 검색, 추가, 삭제하는 시간은 log n에 비례합니다. 여기서 n은 집합의 크기입니다.
이진 검색 트리는 순서를 결정하는 함수 <에 대해 특정 요소보다 작은 요소는 왼쪽 자식 노드에, 특정 요소보다 큰 요소는 오른쪽 자식 노드에 위치하는 이진 트리를 뜻합니다.
(defstruct (node (:print-function
(lambda (n s d)
(format s "#<~A>" (node-elt n)))))
elt (l nil) (r nil))
(defun bst-insert (obj bst <)
(if (null bst)
(make-node :elt obj)
(let ((elt (node-elt bst)))
(if (eql obj elt)
bst
(if (funcall < obj elt)
(make-node
:elt elt
:l (bst-insert obj (node-l bst) <)
:r (node-r bst))
(make-node
:elt elt
:r (bst-insert obj (node-r bst) <)
:l (node-l bst)))))))
(defun bst-find (obj bst <)
(if (null bst)
nil
(let ((elt (node-elt bst)))
(if (eql obj elt)
bst
(if (funcall < obj elt)
(bst-find obj (node-l bst) <)
(bst-find obj (node-r bst) <))))))
(defun bst-min (bst)
(and bst
(or (bst-min (node-l bst)) bst)))
(defun bst-max (bst)
(and bst
(or (bst-max (node-r bst)) bst)))
그림 4.5: 이진 검색 트리: 검색 및 추가
그림 4.5는 이진 검색 트리에 객체를 집어넣거나 찾는 함수를 포함하고 있습니다. 여기에서 가장 간단한 자료 구조는 node인데, 여기에는 세 개의 필드가 포함되어 있습니다. 하나는 노드에 저장된 객체를 위한 것, 나머지 둘은 각각 왼쪽과 오른쪽 자식 노드를 위한 것입니다.
이진 검색 트리는 항상 nil이거나 node입니다. node는 이진 검색 트리의 l 필드이거나 r 필드입니다. cons를 연속으로 호출하여 리스트를 만드는 것처럼, 이진 검색 트리는 bst-insert를 연속으로 호출하여 만들어내게 됩니다. 이 함수는 객체 하나, 이진 검색 트리, 순서 함수를 받아서 주어진 객체를 포함한 이진 검색 트리를 반환합니다. cons처럼 bst-insert도 두 번째 인수로 주어진 이진 검색 트리 자체를 수정하지는 않습니다. 이진 검색 트리를 만드는데 사용한 방법은 아래와 같습니다:
> (setf nums nil)
NIL
> (dolist (x '(5 8 4 2 1 9 6 7 3))
(setf nums (bst-insert x nums #'<)))
NIL
이 시점에서 nums의 구조는 그림 4.4와 같은 트리 모양을 가지게 됩니다.
bst-find도 bst-insert와 같은 인수들을 받습니다. 이 함수를 사용하면 이진 검색 트리에서 객체를 찾는 것이 가능합니다. node 구조체를 들여다보면 두 개의 cdr을 가진 cons cell과 비슷하다는 것을 알 수 있습니다. 예전에 만들었던 our-member 함수 정의와 bst-find 함수 정의를 비교해보면 더 확실하게 알 수 있지요.
bst-find 함수는 member 함수처럼 찾는 요소만 반환하는 것이 아니라 그 노드가 루트인 트리 전체를 반환합니다:
> (bst-find 12 nums #'<)
NIL
> (bst-find 4 nums #'<)
#<4>
이렇게 nil을 이용하여 검색에 성공했는지 실패했는지 구분할 수 있습니다.
이진 검색 트리에서 가장 작은 것과 가장 큰 것을 찾는 것은 쉬운 일입니다. 가장 작은 것을 찾으려면 bst-min에 쓰인대로 그냥 왼쪽 자식 노드만 타고 내려가면 됩니다. 반대로 가장 큰 것을 찾으려면 bst-max와 같이 그냥 오른쪽 자식 노드만 타고 내려가면 됩니다:
> (bst-min nums)
#<1>
> (bst-max nums)
#<9>
이진 검색 트리에서 임의의 요소를 제거하는 것은 매우 빠르지만, 코드가 꽤 많이 필요합니다. 그림 4.6에 삭제를 수행하는 코드가 쓰여있습니다. bst-remove가 삭제하려는 객체와 이진 검색 트리, 정렬 함수를 받으면 해당 객체만 삭제한 형태의 이진 검색 트리를 반환합니다. 이 함수도 remove 함수처럼 두 번째 인수로 받은 이진 검색 트리 자체를 수정하지는 않습니다:
> (setf nums (bst-remove 2 nums #'<))
#<5>
> (bst-find 2 nums #'<)
NIL
이 시점에서 nums는 그림 4.7과 같은 구조를 가지게 될 것입니다. (2가 있던 자리를 3이 차지하는 대신 1이 차지하는 경우도 가능합니다.)
(defun bst-remove (obj bst <)
(if (null bst)
nil
(let ((elt (node-elt bst)))
(if (eql obj elt)
(percolate bst)
(if (funcall < obj elt)
(make-node
:elt elt
:l (bst-remove obj (node-l bst) <)
:r (node-r bst))
(make-node
:elt elt
:r (bst-remove obj (node-r bst) <)
:l (node-l bst)))))))
(defun percolate (bst)
(cond ((null (node-l bst))
(if (null (node-r bst))
nil
(rperc bst)))
((null (node-r bst)) (lperc bst))
(t (if (zerop (random 2))
(lperc bst)
(rperc bst)))))
(defun rperc (bst)
(make-node :elt (node-elt (node-r bst))
:l (node-l bst)
:r (percolate (node-r bst))))
(defun lperc (bst)
(make-node :elt (node-elt (node-l bst))
:l (percolate (node-l bst))
:r (node-r bst)))
그림 4.6: 이진 검색 트리: 삭제
그림 4.7: 요소를 삭제한 후의 이진 검색 트리
가운데에 껴있던 노드를 삭제하려면 빈 자리를 자식 노드로 메워야 하기 때문에 일이 좀 복잡합니다. percolate 함수가 이런 용도로 만들어진 함수인데요. 이 함수는 이진 검색 트리의 최상위 요소를 자식 노드 중 하나로 대체하는 일을 재귀적으로 수행합니다.
percolate 함수는 트리의 균형을 유지하기 위해 2개의 자식 노드 중 하나를 랜덤하게 선택합니다. (random 2) 표현식은 0일 수도 있고 1일 수도 있습니다. 그러니 (zerop (random 2)) 표현식은 대충 절반 정도는 참을 반환하게 될 것입니다.
(defun bst-traverse (fn bst)
(when bst
(bst-traverse fn (node-l bst))
(funcall fn (node-elt bst))
(bst-traverse fn (node-r bst))))
그림 4.8: 이진 검색 트리: 순회
이진 검색 트리에 임의의 순서대로 객체들을 집어넣었더라도, 트리를 중위 순회하면 오름차순으로 정렬된 결과를 얻을 수 있습니다. 그림 4.8의 bst-traverse 함수는 이런 목적으로 만들어진 것입니다:
> (bst-traverse #'princ nums)
13456789
NIL
(princ 함수는 객체를 출력하는 역할만 합니다.)
이 절에서 주어진 코드는 이진 검색 트리의 뼈대만 구현한 것입니다. 여러분의 필요에 따라 여기에 살을 붙일 수 있겠지요. 여기에서는 각 노드에 딱 하나의 elt 필드만 존재하지만, 사실 많은 어플리케이션에서는 key 필드와 value 필드를 가지는 것이 일반적입니다. 그리고, 이 장에서는 이진 검색 트리를 집합처럼 다루었습니다. 같은 요소를 여러번 입력하면 그냥 무시되지요. 그렇지만 약간만 수정하면 중복된 요소들을 처리하도록 할 수 있습니다.
이진 검색 트리가 정렬된 객체 모음을 유지하는 유일한 방법은 아닙니다. 일반적으로 이진 검색 트리는 삽입과 삭제가 거의 비슷하게 발생할 때에 최적으로 동작합니다. 그렇기 때문에 우선순위 큐에 이진 검색 트리를 사용하는 것은 별로 좋지 않습니다. 우선순위 큐에서는 입력이 균형있게 들어올 수 있다고 하더라도, 항상 최소값이나 최대값을 삭제하기 마련입니다. 이렇게 되면 이진 검색 트리의 균형이 깨지게 됩니다. 원래는 삽입과 삭제 모두 O(log n)의 효율을 기대할 수 있어야 하지만, 트리가 한 쪽으로 기울게 되면 O(n)이 되고 맙니다. 이진 검색 트리를 우선순위 큐로 사용할 바에는 그냥 일반적인 리스트를 사용하는 편이 나을 것입니다. 어차피 똑같은 결과를 가져올테니까요.
해시 테이블
3장에서는 리스트를 집합과 매핑을 표현하는데 사용할 수 있음을 보여드렸습니다. 그렇지만 상당한 크기로 데이터가 늘어나면 해시 테이블을 사용하는 것이 더 빠릅니다. make-hash-table을 호출해서 해시 테이블을 생성할 수 있습니다. 이 함수는 필수적으로 넘겨야 할 인수가 없습니다:
> (setf ht (make-hash-table))
#<Hash-Table BF0A96>
해시 테이블은 함수처럼 항상 #<...> 형식으로 표시됩니다.
해시 테이블은 연관 리스트와 같이 객체의 쌍을 표현하는 용도로 사용됩니다. 주어진 키에 대응되는 값을 얻기 위해서는 gethash 함수를 호출하면서 키와 해시 테이블을 넘겨주면 됩니다. gethash는 키에 연관된 값을 찾지 못한 경우 기본적으로 nil을 반환합니다.
> (gethash 'color ht)
NIL
NIL
방금 Common Lisp의 특이한 기능 하나를 처음으로 보셨습니다. 표현식은 여러 개의 값을 반환할 수 있습니다. gethash 함수는 두 개의 값을 반환합니다. 첫번째는 키에 연관된 값입니다. 두번째는 해시 테이블이 그 키에 대응되는 값을 저장하고 있는지 아닌지 알려줍니다. 두번째 값이 nil이기 때문에, 첫번째 값이 명시적으로 color에 연관된 nil이 아니라 기본값으로 반환된 nil이라는 것을 알 수 있습니다.
대부분의 구현체들이 최상위 계층에서 호출한 결과로 나오는 반환값은 전부 다 표시해주지만, 코드는 하나의 반환값만 받으려고 하기 때문에 항상 첫번째 반환값을 얻게 됩니다. 여러 개의 반환값을 받을 수 있도록 코딩하는 방법은 5.5절에서 설명하겠습니다.
키에 연관된 값을 설정하려면 gethash와 함께 setf를 사용하면 됩니다:
> (setf (gethash 'color ht) 'red)
RED
이제 gethash를 다시 호출해보면, 우리가 방금 전에 집어넣은 값을 얻을 수 있습니다:
> (gethash 'color ht)
RED
T
두번째 반환값이 우리가 기본값이 아니라 실제로 저장된 값을 얻어왔다는 사실을 입증해주는군요.
해시 테이블에 저장되는 객체나 키 모두 어떤 타입이든 상관없습니다. 가령 함수에 대한 정보를 유지하고 싶은 경우에는, 함수를 키로 쓰고 문자열을 입력 내용으로 하는 해시 테이블을 사용할 수 있습니다:
> (setf bugs (make-hash-table))
#<Hash-Table BF4C36>
> (push "Doesn't take keyword arguments."
(gethash #'our-member bugs))
("Doesn't take keyword arguments.")
gethash는 기본값으로 nil을 반환하고 push는 setf를 줄여서 사용한 것입니다. 따라서 간단히 새로운 문자열을 push 하는 것으로 함수에 대한 정보를 입력할 수 있습니다. (our-member는 16쪽에서 만든 그것입니다.)
해시 테이블을 리스트 대신 집합을 표시하는데 사용할 수도 있습니다. 집합이 충분히 큰 경우에는 해시 테이블을 사용하는 편이 검색이나 삭제가 훨씬 빠릅니다. 해시 테이블로 표현된 집합에 새로운 요소를 추가할 때는 해당 요소를 gethash한 결과에 t를 설정하면 됩니다:
> (setf fruit (make-hash-table))
#<Hash-Table BFDE76>
> (setf (gethash 'apricot fruit) t)
T
집합에 임의의 요소가 있는지 확인하려면 그냥 gethash를 호출하세요:
> (gethash 'apricot fruit)
T
T
gethash가 기본값으로 nil을 반환하기 때문에, 새로 만들어진 해시 테이블도 마찬가지로 비어있는 집합으로 취급할 수 있습니다.
집합에서 임의의 객체를 제거할 때는 remhash를 호출하게 됩니다. 이 함수는 해시 테이블에서 지정한 항목을 삭제합니다:
> (remhash 'apricot fruit)
T
반환값을 보고 삭제 대상 항목이 존재했었는지 알 수 있습니다. 이 경우에는 삭제할 항목이 들어있었네요.
해시 테이블에 사용할 수 있는 반복 함수도 있습니다. maphash는 두 개의 인수를 받아들이는 함수 하나와 해시 테이블 하나를 인수로 받습니다. 이 함수는 테이블에 존재하는 모든 키/값 쌍을 대상으로 호출됩니다. 특별한 순서는 없구요:
> (setf (gethash 'shape ht) 'spherical
(gethash 'size ht) 'giant)
GIANT
> (maphash #'(lambda (k v)
(format t "~A = ~A~%" k v))
ht)
SHAPE = SPHERICAL
SIZE = GIANT
COLOR = RED
NIL
위의 경우에는 항상 nil을 반환하게 되지만, 리스트에 값을 쌓아놓도록 하는 함수를 넘겨주면 해시 테이블에 있는 값들을 저장할 수도 있습니다.
해시 테이블은 메모리가 고갈될 때까지 무한정 늘어나기 때문에, 아무리 많은 수가 있어도 문제없이 다룰 수 있습니다. 만약 해시 테이블을 처음 만들 때부터 지정한 갯수만큼 미리 공간을 준비해놓기를 원한다면 make-hash-table을 호출할 때 :size 옵션을 주면 됩니다. 여기에는 두 가지 이유가 있습니다. 어차피 커질거라는 사실을 안다면 불필요하게 나중에 테이블 공간을 늘리는 작업을 피하고 싶을겁니다. 그 반대의 경우에는 어차피 몇 개 안 들어갈테니 쓸데없이 메모리 낭비를 할 필요가 없구요. :size 인수는 해시 테이블의 할당 공간량을 지정하는게 아니라 해시 테이블에 들어갈 요소의 수를 뜻하는 것인데요. 더 구체적으로는 확장되기 전에 다룰 수 있는 평균적인 갯수를 의미합니다. 그렇기 때문에:
(make-hash-table :size 5)
이 코드는 5개까지 담을 수 있는 해시 테이블을 반환하게 됩니다.
검색에 관련된 다른 자료 구조들과 마찬가지로 해시 테이블도 반드시 키의 동등성을 비교하는 방법을 가지고 있어야 합니다. 기본적으로는 eql을 사용하지만 여러분이 원한다면 eq, equal, equalp 같은 비교 함수를 사용하도록 :test 인수로 넘길 수 있습니다:
> (setf writers (make-hash-table :test #'equal))
#<Hash-Table C005E6>
> (setf (gethash '(ralph waldo emerson) writers) t)
T
여기에서 보이는 것처럼 해시 테이블의 효율성에는 그에 상응하는 대가가 필요합니다. 리스트를 사용할 때는 member를 호출하는 시점에서 동등성을 비교하는 함수를 지정할 수 있었습니다만, 해시 테이블을 사용할 때는 미리 어떤 비교 함수를 사용할지 결정해두어야 합니다. 해시 테이블을 생성할 때 지정해야 하니까요.
리스프 프로그래밍에서 발생하는 대부분의 트레이드 오프는 이런 속성을 가지고 있습니다. 따라서 초기에는 가능하면 유연한 방식을 취하고, 프로그램이 완성되어가는 시점에 속도를 위해 유연성을 희생하는 것이 좋습니다.
요약
- Common Lisp는 최소 7 차원의 배열을 지원합니다. 1차원 배열은 벡터라고도 불립니다.
- 문자열은 문자의 벡터입니다. 문자는 그 자체로 존재하는 객체입니다.
- 시퀀스는 리스트와 벡터를 포함합니다. 많은 시퀀스 함수는 기본 구성에 해당하는 키워드 인수를 받아들입니다.
- 리스프에는 굉장히 많은 수의 문자열 조작 함수가 존재하기 때문에 파싱이 간단합니다.
- defstruct를 호출하면 명명된 필드로 구성된 구조체를 정의할 수 있습니다. 프로그램을 작성하는 프로그램의 좋은 예라고 할 수 있지요.
- 이진 검색 트리는 정렬된 객체 집합을 유지하는데 유용합니다.
- 해시 테이블은 집합이나 매핑을 표현하는 효율적인 방법을 제공합니다.
연습 문제
- 2차원 배열 (차원이 (n n)인 배열) 을 받아서 시계 방향으로 90도 회전시키는 함수를 정의하세요. 아마 array-dimensions 함수가 필요할겁니다. (361쪽):
> (quarter-turn #2A((a b) (c d)))
#2A((C A) (D B)) - 368쪽에 있는 reduce 함수 설명을 읽고, 이 함수를 활용해서 아래의 함수를 정의해보세요:
(a) copy-list
(b) reverse - 데이터와 세 개의 자식 노드를 지원하는 트리를 표현할 수 있는 구조체와 아래의 함수를 정의하세요.
(a) 트리를 복사하는 함수 (원본에 있는 노드와 eql로 비교했을 때 같은 것이 나오면 안 됩니다.)
(b) 트리를 구성하는 노드의 데이터 필드를 대상으로 주어진 객체를 찾을 수 있는 경우 참을 반환하는 함수. (객체 하나와 트리 하나를 인수로 받습니다.) - 이진 검색 트리를 받아서 내림차순으로 정렬된 리스트를 반환하는 함수를 정의하세요.
- bst-adjoin을 정의하세요. 이 함수는 bst-insert와 동일한 인수를 받지만 트리에서 eql로 비교했을 때 같은 노드가 없는 경우에만 객체를 삽입합니다.
- 모든 해시 테이블의 내용물은 키-값 쌍을 (k . v) 요소로 포함하는 연관 리스트로 표현할 수 있습니다. 아래와 같은 함수를 정의하세요:
(a) 연관 리스트를 받아서 대응되는 해시 테이블을 반환하는 함수
(b) 해시 테이블을 받아서 대응되는 연관 리스트를 반환하는 함수
최근 덧글