"Lisp"는 "List Processing"이라는 유래처럼 list는 lisp의 메인 자료구조이다.
그러나 이 역사설 사실에 현혹되지 말자. Polo셔츠가 Polo를 위한 것이 아닌 것처럼 고도로 최적화된 Common Lisp프로그램에서 리스트는 더이상 볼 수 없다.
적어도 컴파일 타임에는 여전히 리스트일 것이다.
가장 정교한 프로그램(리스트를 런타임에 적게 사용하는 것)은 매크로 확장을 생성할 때 컴파일 시간에 (줄어든 런타임시간에 비례하여) 더 많이 사용한다.
그러므로 비록 현대 방언에서 리스트의 역할이 줄어들지라도, 리스트 연산은 여전히 리습에서 큰 부분을 차지한다.
;; Figure 4.1: Small functions which operate on lists. (proclaim '(inline last1 single append1 conc1 mklist)) (defun last1 (lst) (car (last lst))) (defun single (lst) (and (consp lst) (not (cdr lst)))) (defun append1 (lst obj) (append lst (list obj))) (defun conc1 (lst obj) (nconc lst (list obj))) (defun mklist (obj) (if (listp obj) obj (list obj)))첫번째로 last1, 리스트의 마지막 요소를 반환한다. 빌트인 함수는 마지막 요소가 아니라 목록의 마지막 cons를 반환한다.
대부분의 경우 마지막 요소를 얻기 위해 (car (last ...))를 사용한다. 그런 경우를 위해 새로운 유틸리티를 쓸 가치가 잇는가?
있다!, 빌트인 연산자 중 하나를 효과적으로 대체할 수 있다면 그렇다!
last은 오류 검사를 하지 않는다. 일반적으로 이 책의 코드는 오류검사를 하지 않는다. 부분적으로 이것이 예제를 더 명확하게 만든다.
그리고 짧은 유틸리티의 경우 오류 검사를 하지 않는 것이 합리적이다. 만약 아래와 같은 문제를 만났다 하자.
> (last1 "blub") >>Error: "blub" is not a list. Broken at LAST...에러는 last에서 잡힐 것이다. 유틸리티가 작을 때, 추상화된 레이어가 너무 얇아서 투명 해지기까지 한다.
얇은 얼음층을 통해 그 밑에 일어난 일을 알 수 있듯이, last1같은 유틸리티 또한 그 밑에 있는 함수에서 발생하는 오류를 보는데 문제가 없다.
함수 single은 리스트의 요소가 하나인지 아닌지를 확인한다.
리습 프로그램에선 이 테스트를 꽤 자주 할 필요가 있다. 아래처럼 쓰다보나, 처음에는 영어로 된 자연스러운 벙역으로 바꾸고 싶었을 것이다.
(= (length lst) 1)이런 식으로 쓰여 있으면, 이 테스트는 아주 비효율적일 것이다.
우리는 첫 번째 요소를 지나치자마자 이것이 하나만 있는지 아닌지 알 수 있다. 그런데 length를 쓰다니? 아주 비효율적이다. single이 훨씬 낫다.
다음으로 append1과 conc1이다.
둘다 새로운 요소를 리스트 마지막에 붙인다. conc1는 파괴적으로 (수정한다는 말)
이러한 함수는 아주 작지만 자주 필요하기 때문에 정의할 가치가 있다. 실제로, append1은 이전의 lisp방언에 미리 정의되어 있다.
(적어도) Interlisp에는 미리 정의되어 있는 mklist라는 것도 있다.
이녀석은 어떤 것이 정말로 list인지 확인한다. 많은 리습 함수는 단일 값 또는 리스트로 반환하기 위해 작성된다.
그런데 이 모든 것들을 리스트로 반환하도록 하는 것이다. (괜찮다)
만약에 lookup이라는 함수가 있다고 하자. 데이터라고 불리는 리스트의 모든 요소에 대해 조회를 호출하여 결과를 수집한다고 하자.
우린 다음처럼 쓸 것이다.
(mapcan #'(lambda (d) (mklist (lookup d))) data)이러면 전부 리스트로 반환되서 수집될 것이다.
좀 더 긴 예제를 둘러보자.
;; Figure 4.2: Larger functions that operate on lists.
(defun longer (x y)
(labels ((compare (x y)
(and (consp x)
(or (null y)
(compare (cdr x) (cdr y))))))
(if (and (listp x) (listp y))
(compare x y)
(> (length x) (length y)))))
(defun filter (fn lst)
(let ((acc nil))
(dolist (x lst)
(let ((val (funcall fn x)))
(if val (push val acc))))
(nreverse acc)))
(defun group (source n)
(if (zerop n) (error "zero length"))
(labels ((rec (source acc)
(let ((rest (nthcdr n source)))
(if (consp rest)
(rec rest (cons (subseq source 0 n) acc))
(nreverse (cons source acc))))))
(if source (rec source nil) nil)))
그림 4.2에서는 좀 더 큰 리스트 유틸리티의 예제가 주어졌다.첫 번째는, longer 함수, 추상화뿐만 아니라 효율성의 관점에서도 유용하다.
두 시퀀스를 비교하여 더 길 경우에 참을 리턴한다.
우리가 두 리스트를 비교할 때, 아래처럼 적는 경우가 있다.
(> (length x) (length y))위 코드는 두 리스트의 전체 길이를 전부 순회해야 하기 때문에 비효율적이다.
한 리스트가 다른 리스트보다 훨씬 더 길다면, 그 길이의 차이를 건너는 만큼 그 노력이 낭비가 될 것이다.
병렬로 두개의 리스트가 넘어가면서 비교하는 것이 더 빠르다.
longer 안에는 재귀가 실행되고 있다. compare라는 lambda가 labels로 이름 붙여져 있다.
이녀석으로 하나하나 비교하고 재귀로 그 다음 요소를 비교한다.
longer함수는 길이를 비교하는 함수이기 때문에, 길이를 인수로 줄 수 있는 모든 것에 대해 작동해야 한다.
하지만 길이를 병렬로 비교할 수 있는 녀석은 리스트인 경우에만 적용된다. 내부 함수(internal function)는 두 인수가 모두 목록인 경우에만 호출된다.
다음 함수, filter를 알아보자.
빌트인 remove-if-not은 연속적인 cdrs에서 동일한 기능을 가진 find-if를 호출했을 때 반환될 수 있는 모든 값을 반환하지 않는다.
이와 유사하게 필터는 목록의 연속 cdrs에 대해 일부 반환된 것을 반환한다.
(remove-if-not #'evenp '(1 2 3 4 5 6)) ;; (2 4 6) (filter #'(lambda (x) (if (numberp x) (1+ x))) '(a 1 2 b 3 c d 4)) ; (2 3 4 5)filter함수에게 함수와 리스트를 주면, 매개변수로 받는 함수가 리스트의 요소 하나하나에 적용되면서 그 값이 non-nil이 아닌 것들의 리스트를 리턴받는다.
filter함수는 섹션2.8에서본 "tail-recursive functions"가 사용한 누산기(acccumulator)를 사용하고 있다는 것을 유의하자.
잠깐 2.8을 구경해보자.
;; 2.8 Tail Recursion
(defun our-length (lst)
(labels ((rec (lst acc)
(if (null lst)
acc
(rec (cdr lst) (1+ acc)))))
(rec lst 0)))
사실, tail-recursive한 함수를 작성하는 목적은 컴파일러가 filter 형태의 코드를 생성하도록 하는 것이다.필터의 경우, 간단한 반복 정의는 꼬리 재현보다 더 간단하다.
필터의 정의에서 push와 nreverse의 조합은 리스트를 누적하는(accumulate) 표준 lisp 관용구이다.
코드를 자세히 봐보자. filter 코드에는 신기하게 재귀가 없다.
컴파일러는 이렇게 변경을 시도 한다는 것 같다.
누산기 acc를 정의하고, dolist를 이용하여 lst의 요소들을 순회한다.
funcall을 이용하여 요소(x) 하나하나를 순회하여 실행하여 val로 지정하고,
if 문으로 val이 non-nil인지 확인 하면 누산기 acc에 push한다.
그리고 뒤집는다. nreverse는 값을 파괴적으로 뒤집는다. 꽤나 빠르게
(defun filter (fn lst)
(let ((acc nil))
(dolist (x lst)
(let ((val (funcall fn x)))
(if val (push val acc))))
(nreverse acc)))
Figure 4.2의 마지막 함수를 보자. group함수는 리스트를 그룹핑하여 서브리스트에 넣는것이다.
group함수에게 리스트 l과 숫자n을 보내면, l의 요소가 길이 n의 서브리스트로 분류된 새로운 리스트가 반환된다.
나머지는 마지막 서브리스트에 들어간다.
따라서 두 번째 인수로 2를 지정하면 다음과 같은 목록이 나온다.
> (group '(a b c d e f g) 2) ((A B) (C D) (E F) (G))이 함수는 tail-recursive한 함수를 만들기 위해 다소 복잡한 방식으로 짜졌다.
신속한 프로토타이핑의 원칙은(The principle of rapid prototyping)은 개별 기능뿐만 아니라 전체 프로그램에도 적용된다.
flatten같은 함수를 작성할 때 가장 간단한 구현으로 시작하는 것이 좋다.
그 다음, 간단한 버전이 작동하면 필요에 따라 효율적인 tail-recursive나 iterative 버전으로 바꿀수 있다.
만약 초기 버전으로 충분하다면, 초기 버전은 그것의 행위를 코멘트로 남겨놓아야 하며, 이것이 무엇을 대체하는 행위인지 코멘트를 남겨야 한다.
group의 정의는 하나 이상의 오류를 검사한다는 점에서 일반적이지 않다. 이렇게 체크하지 않으면 두번째 인수에 0이 오면 무한 재귀로 보내버린다.
어떤 면에서, 이 책의 예들은 일반적인 Lisp 예제와 다르다. 각장을 서로 독립적으로 만들기 위해서, 코드의 예들은 가능한 한 원시 Lisp로 쓰여졌다.
group 함수는 매크로를 정의하는데 매우 유용하기 때문에 이후 여러 장에서 다시 나타난다.
나가기전에 group을 파해쳐보자.
(defun group (source n)
(if (zerop n) (error "zero length")) ;; 1. 길이 0이면 끝
(labels ((rec (source acc)
(let ((rest (nthcdr n source))) ;; 자르고 남은 뒷부분을 rest로
(if (consp rest) ;; rest가 cons인지 확인
(rec rest (cons (subseq source 0 n) acc)) ;; acc(누산기)에 앞에 자른 n개의 그룹을 cons로 더한다. 그리고 rest와 acc를 재귀돌린다.
(nreverse (cons source acc)))))) ;; 마지막에 파괴적인 reverse로 반대로 리턴
(if source (rec source nil) nil))) ;; 2. source가 없으면 nil
;; cons와 nreverse를 좀 더 확인해보자.
(cons '(1 2 3) '((a b c)))
; ((1 2 3) (A B C))
(nreverse (cons '(1 2 3) '((a b c))))
; ((A B C) (1 2 3))
댓글 없음:
댓글 쓰기