LISP으로 함수형 프로그래밍 맛보기

5.5 ~ 5.7

 

5.5 리스트 탐색을 위한 재귀호출

 

리습 프로그램에 재귀 함수가 중요한 역할을 하기 때문에 재귀 함수 자체를 만드는 유틸리티를 만들어놓는 것도 중요합니다. 이번 장과 다음 장에서 가장 많이 쓰이는 두가지 타입의 재귀 함수를 만들기 위한 유틸리티 함수를 설명합니다. 커먼 리습에서 이 함수들을 사용하는게 어색할 수 있습니다. 매크로에 관해 설명할 때 이런 기능을 좀더 우아하게 만들 수 있는 방법을 알아 볼 것입니다. 재귀 호출을 위한 매크로는 15.2장과 15.3장에 나옵니다.

 

프로그램에서 같은 패턴이 반복되서 나온다면, 그 패턴을 추상화하고, 그 상위에서 추상화된 패턴을 호출해야합니다. 리습 프로그램들을 보면 다음과 같은 패턴들이 공통으로 나타납니다.

 

(defun our-length (lst)
  (if (null lst)
      0
    (1+ (our-length (cdr lst)))))

 

아래와 같은 함수들도 자주 나타납니다.

 

(defun our-every (fn lst)
  (if (null lst)
      t
    (and (funcall fn (car lst))
     (our-every fn (cdr lst)))))

 

위의 두 함수는 구현방식이 매우 유사합니다. 둘다 리스트의 원소들을 접근하기위해 재귀호출을 사용하고, 각 호출때마다 같은 표현식을 실행하고, 고유한 값을 반환하기 위한 바닥상태 처리만 다릅니다. (역자주: 바닥상태란 재귀 호출이 끝나는 조건을 말합니다. 원어는 base case이고, 일반적으로 기정상태나 바닥상태라고 번역이 됩니다.) (역자주: 원문에는 "successive cdrs of a list"라고 써있는데 이것은 리스트의 각 원소들을 리스트에 저장된 순서대로 접근한다는 의미입니다. 리스트를 cdr에 전달하면 리스트에서 두번째 항목이 반환되고, 그걸 반복하면 결국은 리스트의 모든 원소들을 순서대로 접근하는 것과 같기 때문입니다.) 이 패턴은 리습 프로그램에 너무나 자주 나타나기 때문에 숙련된 프로그래머들은 보는 즉시 이해가 되고, 따로 생각하고 고민할 필요없이 자연스럽게 만들 수 있을 정도입니다. 빨리 익숙해지는 것이라서 이런 패턴을 어떻게 추상화할지에 대한 고민도 필요없을 정도입니다.

 

(defun lrec (rec &optional base)
  (labels ((self (lst)
    	 (if (null lst)
		     (if (functionp base)
			 (funcall base)
		       base)
		   (funcall rec (car lst)
			    #'(lambda ()
				(self (cdr lst)))))))
    #'self))

그림 5.5: 일차원 리스트를 재귀호출하는 함수

 

그런데 이 패턴은 항상 똑같습니다. 이런 함수들을 매번 손으로 쓸 필요없이, 이 패턴을 생성해주는 함수를 만들 수 있습니다. 그림 5.5는 lrec ("list recurser"의 약자)라는 함수를 보여주는데, 리스트의 각 원소에 접근하는 재귀함수를 생성해주는 함수입니다. lrec의 첫번째 인자는 함수입니다. 이 함수는 두개의 인자를 받는데, 첫번째는 재귀 호출단계에서 새로 전달된 리스트의 car이고, 두번째 인자는 재귀를 계속하게해주는 함수가 됩니다. lrec를 이용해서 our-length를 표현해보면 다음과 같습니다.

 

(lrec #’(lambda (x f) (1+ (funcall f))) 0)

(역자주: 이대로 호출하면 반환되는 것은 함수입니다. 따라서 리스트의 길이를 알아내는 전체 코드는 다음과 같이 됩니다.)

(funcall (lrec #’(lambda (x f) (1+ (funcall f))) 0) '(1 2 3))

 

(저자주3: 어떤 리습 구현체에서는 functionp가 t나 nil에 대해서도 참을 반환합니다. 그런 경우에는 lrec의 두번째 인자로 t나 nil 둘다 적합하지 않습니다.) (역자주: sbcl을 실행해보니 (functionp t)나 (functionp nil) 모두 nil을 반환합니다.)

 

(lrec #’(lambda (x f) (and (oddp x) (funcall f))) t)

 

lrec의 구현을 보면 lrec함수 내부에 재귀 함수를 정의하기 위해 labels를 써서 self라는 함수를 만듭니다. 재귀 호출을 할 때 rec 함수에는 두개의 인자가 전달되는데, 리스트의 첫번째 원소와 (역자주: 원문에는 "the current car of the list"라고 써있는데, 리스트의 첫번째 원소라고 번역했습니다.) 재귀 호출로 실행될 함수입니다. our-every처럼 재귀 호출이 실행될 조건을 and로 처리하면 첫번째 인자가 거짓을 반환할 때 재귀 호출을 멈출 수 있습니다. 재귀 호출이 실행될 때 전달되는 인자가 반드시 값일 필요는 없습니다. 함수도 될 수 있습니다. 그 함수를 호출해서 값을 얻을 수 있으니까요. (역자주: x가 함수이거나 클로저일 수도 있습니다. 어쨌든 값만 반환하면 최종적으로 리스트를 만들 수 있으니까요.) 

 

; copy-list 리스트 복사
(lrec #’(lambda (x f) (cons x (funcall f))))
; remove-duplicates 중복 원소 제거
(lrec #’(lambda (x f) (adjoin x (funcall f))))
; find-if, for some function fn 함수 fn으로 원하는 원소만 찾기
(lrec #’(lambda (x f) (if (fn x) x (funcall f))))
; some, for some function fn
(lrec #’(lambda (x f) (or (fn x) (funcall f))))

그림 5.6: lrec로 구현된 함수들

 

그림 5.6은 커먼 리습에 있는 함수들 몇가지를 lrec로 구현한 예제입니다.(저자주4) lrec을 쓰는게 항상 최적의 성능을 내지는 않습니다. 사실 이번 장에 있는 lrec와 다른 재귀 함수 생성 코드들은 꼬리재귀를 사용하는 방법을 보여주기 위한 것들입니다. 그러므로 프로그램의 초기 버전이나 성능이 중요하지 않은 쪽에만 사용하는게 좋습니다. (저자주4: 어떤 구현체들은 이 함수들을 쓰기 전에 *print-circle* 변수를 t로 설정해야될 수도 있습니다.)

5.6 트리탐색을 위한 재귀호출

 

(a . b) (a b c) (a b (c d))

그림 5.7: 리스트로 표현된 트리

 

리습 프로그램에서 흔하게 발견되는 재귀 호출이 또 있습니다. 하위 트리를 재귀 호출로 탐색하는 것입니다. 이 패턴은 중첩된 리스트에서 리스트의 car과 cdr을 재귀 호출로 탐색하려고할 때 나타납니다.

리습의 리스트는 여러 용도로 사용할 수 있습니다. 리스트로 시퀀스나 집합, 맵핑, 배열, 트리를 표현할 수 있습니다. 리스트로 트리를 표현하는 여러가지 방법이 있습니다. 가장 흔한 방법은 리스트를 이진 트리로 생각하는 것입니다. 리스트의 car을 왼쪽 가지로 생각하고, cdr은 오른쪽 가지로 생각하면 됩니다. (사실 이게 리스트의 일반적인 내부 구현이기도 합니다.) (역자주: 리스트의 일반적인 구현이라는게 뭔지 이상하게 생각되실 분들이 많으실겁니다. "COMMON LISP: A Gentle Introduction to Symbolic Computation"라는 pdf로 공개된 책이 있는데 이 책의 2장 Lisps를 읽어보시면 리스트가 일반적으로 생각하는 한 줄로 연결된 형태가 아님을 알 수 있습니다. 그림으로 리습의 기본 지식을 아주 쉽게 설명하는 좋은 책입니다.) 그림 5.7은 리스트로 표현된 트리의 3가지 예제를 보여줍니다. 리스트의 원소들을 점으로 구분되도록 표현하면 점이 트리의 노드의 연결에 해당되는걸 알 수 있습니다. 따라서 리스트를 다음과 같은 형태로 생각할 때 더 쉽게 트리로 해석할 수 있습니다.

 

(a b c) = (a . (b . (c . nil)))
(a b (c d)) = (a . (b . ((c . (d . nil)) . nil)))

 

어떤 리스트던지 다 이진 트리로 해석될 수 있습니다. 하지만 copy-list와 copy-tree같이 리스트와 트리에 적용되는 함수들을 보면 서로 다르게 동작합니다. copy-list는 리스트를 시퀀스로 생각하고 복사합니다. 리스트 내부에 중첩된 리스트가 있으면, 시퀀스의 한 원소로 생각되서 복사가 안됩니다.

 

> (setq x ’(a b) listx (list x 1))

((A B) 1)

> (eq x (car (copy-list listx)))

T

 

(역자주: 위의 코드를 실행하면 x는 '(a b)가 되고, listx는 (x 1)=('(a b) 1)이 됩니다. 여기서 listx의 첫번째 원소 '(a b)는 별도의 리스트가 아니라 메모리 상에 존재하는 x를 다시 사용한 것입니다. 그리고 (copy-list listx)를 실행하면 (x 1)을 복사하는데 x를 복사하지않고, x를 그대로 사용합니다. 따라서 (car (copy-list listx))가 실행되면 x가 그대로 반환되고 eq로 검사해보면 참이 되는 것입니다.)

 

반대로 copy-tree는 리스트를 트리로 생각하고 복사하므로 하위 리스트를 하위 트리로 생각합니다. 따라서 하위 리스트도 복사가됩니다.

 

> (eq x (car (copy-tree listx)))

NIL

(역자주: copy-tree가 listx의 내부에 있는 x를 복사해서 반환하므로 x와는 다른 객체가 되고 eq는 nil을 반환합니다.)

 

다음처럼 우리 나름의 copy-tree를 만들 수 있습니다.

 

(defun our-copy-tree (tree)
  (if (atom tree)
      tree
    (cons (our-copy-tree (car tree))
      (if (cdr tree) (our-copy-tree (cdr tree))))))

 

copy-tree 함수는 많이 사용되는 패턴 하나를 활용한 것입니다. (다음에 나오는 함수들 중 몇가지는 이 패턴을 잘 보여주기 위해서 약간 특이하게 구현했습니다.) 트리에서 단말 노드가 몇개인지 세는 유틸리티를 한번 보겠습니다.

 

(defun count-leaves (tree)
  (if (atom tree)
      1
    (+ (count-leaves (car tree))
       (or (if (cdr tree) (count-leaves (cdr tree)))
       1))))

 

리스트로 표현했을 때 보이는 아톰보다 더 많은 원소가 트리에 있는 것을 알 수 있습니다. (역자주: 리습의 데이터 타입 atom을 아톰이라고 번역하겠습니다. 적당한 한글 용어도 생각나지 않고, 이미 많은 분들이 "아톰"이라고 문서화하고 계셔서요.)

 

> (count-leaves ’((a b (c d)) (e) f))

10

 

트리의 단말 노드의 갯수를 알려면, 트리를 점과 nil로 표현되도록 한다음 나타나는 아톰들의 갯수를 세야합니다. 그렇게 점과 nil까지 표현하면 ((a b (c d)) (e) f) 트리에는 눈에 보이지는 않는 네개의 nil이 있다는걸 알게됩니다. 따라서 단말 노드의 갯수는 총 10개가 됩니다. 곧이어 트리를 처리하는 여러 유틸리티를 만들게됩니다. flatten함수는 트리를 인자로 받아서 트리에 있는 모든 아톰을 하나의 리스트로 만들어서 반환합니다. flatten에 중첩된 리스트를 전달하면, 마치 중간에 있는 괄호들을 다 없앤것 같은 리스트를 반환받게 됩니다.

 

> (flatten ’((a b (c d)) (e) f ()))

(A B C D E F)

 

다음과 같이 정의할 수 있습니다.(약간 비효율적이긴 합니다.)

    

(defun flatten (tree)
  (if (atom tree)
      (mklist tree)
    (nconc (flatten (car tree))
       (if (cdr tree) (flatten (cdr tree))))))

 

 

마지막으로 rfind-if를 보겠습니다. find-if의 재귀 버전인데, 중첩이 없는 리스트나 트리에서 동작합니다.

     

(defun rfind-if (fn tree)
  (if (atom tree)
      (and (funcall fn tree) tree)
    (or (rfind-if fn (car tree))
    (if (cdr tree) (rfind-if fn (cdr tree))))))

 

find-if를 트리에 적용하려면 트리의 단말 노드만 검색할 것인지 하위 트리 전체를 검색할 것인지를 선택해야합니다. 위의 rfind-if는 첫번째 인자로 함수를 전달받고 단말 노드만 검색합니다. 따라서 트리에 있는 아톰만 인자로 받은 함수에 전달됩니다.

 

> (rfind-if (fint #’numberp #’oddp) ’(2 (3 4) 5))

3

 

위에서 본 네개의 함수들 copy-tree, count-leaves, flatten, rfind-if가 모두 매우 형태가 비슷함을 알 수 있습니다. 네개의 함수가 모두 하위 트리를 재귀 호출로 탐색하는 방법에 대한 전형적인 예제들입니다. "리스트 탐색을 위한 재귀호출"에서 했던 것처럼 트리를 탐색할 수 있는 함수를 생성하는 함수를 만들 수 있습니다.

 

이 함수들을 관통하는 원리가 뭔지 알아보려면 이 함수들에서 공통적인 패턴이 아닌게 뭔지를 봐야합니다. our-copy-tree는 2개의 요소를 가집니다. 1. 바닥 상태가 되면, 그 상태에서 가지고 있는 인자를 반환합니다. 2. 재귀 호출을 할 경우에는 cons를 호출하는데, 첫번째 인자는 car을 써서 왼쪽 하위트리로 내려가는 것이고, 두번째 인자는 cdr을 써서 오른쪽 하위트리로 내려가는 것입니다. 그러므로 함수 생성기가 2개의 인자를 가진 것으로 생각할 수 있습니다.

 

(ttrav #’cons #’identity)

 

ttrav ("tree traverser"트리 탐색기)의 정의는 그림 5.8에 있습니다. 재귀 호출을 할 때 한개의 값을 전달하지않고 2개를 전달합니다. 하나는 왼쪽 하위트리를 위한것이고 다른 하나는 오른쪽 하위트리를 위한 것입니다. base인자는 만나는 노드마다 호출되는 함수입니다. 리스트를 평탄화하기 위한 재귀 호출에서 바닥 상태는 항상 nil을 반환합니다. 트리를 위한 재귀호출에서 바닥 상태의 반환값은 좀더 의미있는 값일 경우가 많으므로 그 값을 사용할 가능성이 높습니다.

 

위의 함수들 중에 rfind-if를 제외한 나머지 함수들은 ttrav로 구현할 수 있습니다. (그림 5.9에 있습니다.) rfind-if를 만들기 위해서는 언제 어떤 상황에서 재귀호출을 해야할지도 제어할 수 있는 좀더 범용적인 트리용 재귀호출 생성기를 만들어야합니다. ttrav의 첫번째 인자는 재귀호출의 결과를 받아서 처리하는 함수입니다. 재귀 호출을 할때 함수에 2개의 클로저를 전달합니다. 이 클로저는 ttrav안에 구현된 자기 자신을 호출하는 함수입니다. 이렇게 트리가 허용하는 만큼 재귀 호출을 실행하는 함수를 만들게됩니다.

 

(defun ttrav (rec &optional (base #'identity))
  (labels ((self (tree)
    	 (if (atom tree)
		     (if (functionp base)
			 (funcall base tree)
		       base)
		   (funcall rec (self (car tree))
			    (if (cdr tree)
				(self (cdr tree)))))))
    #'self))

그림 5.8: 트리 탐색을 위한 재귀호출 생성기

 

 

; our-copy-tree
(ttrav #’cons)

; count-leaves

(ttrav #’(lambda (l r) (+ l (or r 1))) 1)

; flatten
(ttrav #’nconc #’mklist)

그림 5.9: ttrav로 다시 구현된 함수들

 

ttrav는 항상 트리 전체를 탐색합니다. count-leaves나 flatten같이 전체 트리를 탐색해야하는 함수에는 적합합니다. 하지만 rfind-if는 트리에서 원하는 원소를 찾으면 멈춰야 합니다. 따라서 rfind-if는 좀더 범용적인 함수 trec으로 구현해야합니다. 그림 5.10에 있습니다. trec의 두번째 인자(역자주: 제 생각에는 원서의 오타같습니다. 첫번째 인자가 맞는것 같은데 책에는 second라고 돼있습니다.)는 세개의 인자를 받는 함수입니다. 세개의 인자는 각각, 현재 탐색하는 트리 객체와 두개의 재귀 호출입니다. 두개의 재귀 호출은 각각 왼쪽과 오른쪽의 하위 트리를 탐색하기위한 클로저입니다. trec을 이용하면 flatten을 다음과 같이 구현할 수 있습니다.

 

(trec #’(lambda (o l r) (nconc (funcall l) (funcall r)))
      #’mklist)

 

rfind-if도 다음과 같이 trec과 oddp를 이용해서 구현할 수 있습니다.

 

(defun trec (rec &optional (base #'identity))
  (labels
      ((self (tree)
         (if (atom tree)
		 (if (functionp base)
		     (funcall base tree)
		   base)
	       (funcall rec tree
			#'(lambda ()
			    (self (car tree)))
			#'(lambda ()
			    (if (cdr tree)
				(self (cdr tree))))))))
    #'self))

그림 5.10:  트리 탐색을 위한 재귀호출 생성기

 

5.7 언제 함수 생성기를 써야할까

 

#'와 람다표현식 대신에 생성기를 써서 함수를 표현하면 런타임에 불필요한 부하가 생깁니다. #'과 람다표현식을 쓰면 상수표현식이 되지만 생성기를 호출하는 일은 런타임에 해석되는 일입니다. 만약 함수를 꼭 런타임에 만들어야할 상황이라도 생성기를 쓸 필요가 없을 수 있습니다. 또 간혹 생성기함수를 미리 호출해서 미리부터 함수를 만들어놔야하는 경우가 있습니다. 그럴때는 샤프-점 (#.) 읽기 매크로를 써서 런타임에 새로운 함수를 만들 수 있습니다. 예를 들면 아래의 표현이 REPL에서 읽혀질 때 compose와 compose의 인자로 전달된 함수들이 이미 정의되어있다면 #.을 쓸 수 있습니다.

 

(find-if #.(compose #’oddp #’truncate) lst)

 

위의 표현식에서 compose 호출은 REPL의 Read단계에서 평가되고, 평가된 후의 함수는 고정된 코드가 되서 우리가 만든 코드에 삽입이 됩니다. oddp와 truncate 둘다 빌트인 함수이기 때문에 compose만 이미 정의되서 로드된 상황이라면 위의 compose 호출이 Read단계에서 평가되는데 문제가 없을 것입니다. 일반적으로 함수를 만들거나 결합하는 일에 매크로를 활용하는게 더 쉽고 효율적입니다. 커먼 리습이 함수를 위한 별도의 네임스페이스를 가지고 있기 때문입니다. 매크로에 대한 소개를 끝낸 후에 15장에서 더 자세히 이야기하겠습니다.

댓글

댓글 본문
작성자
비밀번호
graphittie 자세히 보기