Recursive functions are soimportant in Lisp programs that it would be worth having utilites to build them.
재귀 함수는 lisp에서 매우 중요하기 때문에 이것들을 만들기 위한 유틸리티가 있어야할 가치가 있다.
This section and the next describe functions which build the two most common types.
이 섹션과 다음 섹션에서는 가장 일반적인 두 가지 유형의 재귀함수를 소개한다.
In Common Lisp, these functions are a little awkward to use.
Common Lisp에서 이 함수들을 살짝 어색하게 사용된다.
Once we get into the subject of macros, we will see how to put a more elegant facade on this machinery.
일단 우리가 매크로의 주제로 들어가게 되면, 우리는 이 기계에 좀 더 우아한 외관을 넣는 방법을 알게 될 것이다.
'recursers'를 만드는 매크로는 섹션 15.2, 15.3에서 논의된다.
Repeated patterns in a program are a sign that it could have been written at a higher level of abstraction.
반복되는 패턴은 높은 수준의 추상화로 작성될 수 있다는 신호다.
What pattern is more commonly seen in Lisp programs than a function like this:
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))))
Structurally these two functions have a lot in common.구조적으로 이 두 함수는 공통점이 많다.
They both operate recursively on successive cdrs of a list, evaluating the same expression on each step, except in the base case, where they return a distinct value.
둘 다 리스트에 cdr를 재귀로 반복 연산을 하고, 동일한 표현식을 각 스텝에 실행한다, 고유한 값을 리턴하는 base case만 제외한다.
This pattern appears so frequently in Lisp programs that experienced programmers can read and reproduce it without stopping to think.
이 패턴은 리습에서 자주 보인다. 너무 자주 보여서 경험이 있는 개발자는 개발하는데 끊킴이 없이 읽고 재생산 할 수 있다.
Indeed, the lesson is so quickly learned, that the question of how to package the pattern in a new abstraction does not arise.
실제로, 이런 실습을 너무 빨리 배워 패턴을 새로운 추상화로 패키지하는 방법에 대한 질문이 발생하지 않습니다. (왜냐하면 당연스럽게 이런식으로 개발을 하기 때문)
However, a pattern it is, all the same. Instead of writing these functions out by hand, we should be able to write a function which will generate them for us.
하지만 패턴은 모두 같다. 패턴이 있기 때문에 손으로 쓰는 것보다는 그 패턴을 생성해주는 함수를 만드는 것이 타당하다.
;; Figure 5.5: Function to define flat list recursers.
;; rec 요소별로 실행되어야 할 녀석
;; base 디폴트값.
;; 1. #'self 재귀함수를 생성
;; 2. lst가 없으면 (다 돌았으면)
;; 3. base를 리턴한다.(base가 함수면 실행하고 리턴)
;; 4. lst가 있으면
;; 5. (car lst)로 일단 빼놓고 rec를 재귀로 다시 실행하는 첫번째 매개변수가 되게 한다.
;; 6. (self (cdr lst))를 람다로 묶는다.
;; #'self 함수를 리턴한다.
(defun lrec (rec &optional base) ;; 함수를 리턴한다.
(labels ((self (lst) ;; 1
(if (null lst) ;; 2
(if (functionp base) ;; 3
(funcall base)
base)
(funcall rec (car lst) ;; 5
#'(lambda () ;; 6
(self (cdr lst)))))))
#'self))
Figure 5.5 contains a function-builder called lrec("list recurser") which should be able to generate most functions that recurse on successive cdrs of a list그림5.5에 lrec라는 함수빌더(함수패턴을 만들어주는 녀석)가 있다.
이 빌더는 위 패턴 (리스트의 cdr를 재귀로 실행. 반복연산한다)을 생성할 수 있어야 한다.
The first argument to lrec must be a function of two arguments: the current car of the list, and a function which can be called to continue the recursion.
현재 리스트의 car(초기값)와 재귀로 호출 될 함수이다.
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)재귀케이스가 'our-every'와 같은 함수에서 첫번째 인자가 false를 반환하면 바로 그곳에서 멈추고 싶다. 다돌면 안된다.
즉, 재귀적일 경우에 전달 된 인수는 값이 아니라 함수여야 한다. (호출하면 값을 뱉는) 그러니까 함수의 리스트를 매개변수로 주면 될듯
Figure 5.6은 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))))
댓글 없음:
댓글 쓰기