2019년 1월 15일 화요일

[on lisp] 5.5 Recursion on Cdrs 재귀함수

5.5 Recursion on Cdrs
재귀 함수는 lisp에서 매우 중요하기 때문에 이것들 빌드하는 유틸리티가 있어야할 가치가 있다.
이 섹션과 다음 섹션에서는 가장 일반적인 두 가지 유형을 작성하는 함수에 대해 알아보자.
Common Lisp에서 이 함수들을 살짝 어색하게 사용된다.
일단 우리가 매크로의 주제로 들어가게 되면, 우리는 이 기계에 좀 더 우아한 면을 넣는 방법을 알게 될 것이다.
'recursers'를 만드는 매크로는 섹션 15.2, 15.3에서 논의된다.

프로그램에서 반복되는 패턴은 높은 수준의 추상화로 작성될 수 있다는 신호다.
반복되는 패턴은 높은 수준의 추상화로 작성되었을 수 있었다는 신호다.
Lisp에서 일반적으로 이와 같은 함수보다 일반적으로 보이는 패턴은 아래와 같다.
(defun our-length (lst)
    (if (null lst)
        0
        (1+ (our-length (cdr lst)))))
;; or this
(defun our-every (fn lst)
    (if (null lst)
        t
        (and funcall fn (car lst))
        (our-every fn (cdr lst))))
구조적으로 이 두 함수는 공통점이 많다.
둘 다 리스트에 cdr를 재귀로 반복 연산을 하고, 동일한 표현식을 각 스텝에 실행한다.
;; Figure 5.5: Function to define flat list recursers.
;; rec 요소별로 실행되어야 할 녀석
;; base 디폴트값.
(defun lrec (rec &optional base)  ;; 함수를 리턴한다.
    (labels ((self (lst)  ;; 재귀함수 이름 self
                   (if (null lst)  ;; lst가 없으면
                       (if (functionp base)  ;; 함수인지 확인하고 실행 후 리턴한다.
                           (funcall base)  ;; 함수실행
                           base)  ;; 그냥 리턴
                           (funcall rec (car lst)  ;; lst의 첫번째를 가져오고 rec를 실행
                                    #'(lambda () ;; 그다음 내용을 함수에 감싼다.
                                              (self (cdr lst)))))))
            #'self))                     
이 패턴은 경험 많은 프로그래머가 생각하기를 멈추지 않고 읽고 사용할 수 있게하는 리스프 프로그램에서 자주보임(?)
패턴을 새로운 추상화에 묶는 방법에 문자는 발생하지 않는다.
하지만 패턴은 모두 동일하다. 이러한 함수를 직접 작성하는 대신 우리를 위해 생성해줄 함수를 작성할 수 있어야 한다.
Figure 5.5는 함수빌더(function-builder)가 있다. lrec("list recurser")
이 빌더는 리스트에서 연속적으로 cdrs를 사용하는데 이렇게 반복되는 부분을 생성할 수 있어야 한다.

lec의 첫번째 인수는 현재 리스트의 car와 두번째 인수는 재귀로 계속 호출 될 수 있는 함수이다.
lrec를 사용하여 our-length를 다음처럼 표현할 수 있다.
(lrec #’(lambda (x f) (1+ (funcall f))) 0)
리스트의 길이를 찾는데 요소를 확인할 필요나 중간에 멈출 필요가 없으므로 x는 항상 무시되고 f는 항상 호출된다.
그러나 our-every함수를 표현할 수 잇는 두 가지를 모두 가능성을 모두 표현해야 한다.
예를 들어 oddp
(lrec #’(lambda (x f) (and (oddp x) (funcall f))) t)
lrec의 정의에서는 label를 사용하여 self라는 로컬 재귀 함수를 작성한다.
재귀적일 경우 함수 rec에 두개의 매개변수가 전달된다. 리스트의 현재 car와 재귀 호출을 구현하는 함수를 전달한다.

재귀케이스가 'our-every'와 같은 함수에서 첫번째 인자가 false를 반환하면 바로 그곳에서 멈추고 싶다.
즉, 재귀적일 경우에 전달 된 인수는 값이 아니라 값이어야 하는 함수여야 한다.(값을 원하는 경우)

Figure 4.5는 lrec로 정의된 기존의 Common Lisp함수를 보여준다.
lrec를 호출하면 주어진 함수를 가장 효율적으로 구현할 수 있는 것은 아니다.
사실 이 장에서 정의된 lrec와 다른 재발생(재귀) 생성기(recurser generators)는 꼬리 재귀랑은 다르다.
이러한 이유로 그들은 초기 버전의 프로그램이나 속도가 중요하지 않은 부분에서 사용하기에 가장 적합하다.
Figure 5.6: Functions expressed with lrec.
; 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
(lrec #’(lambda (x f) (if (fn x) x (funcall f))))
; some, for some function fn
(lrec #’(lambda (x f) (or (fn x) (funcall f))))

댓글 없음 :

댓글 쓰기