Racket에서 람다 만 사용하여 재귀를 만드는 방법은 무엇입니까?

샘플 fact구두 프로그램이 주어지면 -

(define fact
  (lambda (n)
    (if (= n 0)
        1
        (* n (fact (- n 1)))))) ;; goal: remove reference to `fact`

(print (fact 7)) ; 5040

위의 내용 fact은 (lambda (n) ...)호출 fact할 때이 람다를 요청하여 새로운 인수로 다시 적용 할 수 있습니다. lambda이름이없고 최상위 define바인딩을 사용할 수없는 경우 변수를 바인딩하는 유일한 방법은 람다의 매개 변수를 사용하는 것 입니다. 다음과 같은 것을 상상해보십시오.

(lambda (r)
  ; ...lambda body...
  ; call (r ...) to recur this lambda
)

우리는해야 할 something우리의 할 (lambda (r) ...)행동하라 이런 식으로 -

(something (lambda (r)
  (print 1)
  (r)))

; 1
; 1
; 1
; ... forever

이것은 결합 자에 something아주 가깝습니다 U-

(define u
  (lambda (f) (f f)))

(define fact
  (lambda (r)     ;; wrap in (lambda (r) ...)
    (lambda (n)
      (if (= n 0)
          1
          (* n ((r r) (- n 1))))))) ;; replace fact with (r r)

(print ((u fact) 7))

; => 5040

그리고 지금 재귀 매개 변수의 사용을 통해 무슨 일이 일어나고 있는지, 우리는 효과적으로 모두 제거 할 수 define바인딩 만 사용하여 쓰기 lambda-

; ((u fact) 7)
(print (((lambda (f) (f f))  ; u
         (lambda (r)         ; fact
           (lambda (n)
             (if (= n 0)
                 1
                 (* n ((r r) (- n 1)))))))
        7))

; => 5040

U-combinator는 간단하지만 ((r r) ...)함수 내에서 호출해야하는 것은 번거 롭습니다. (r ...)직접 재귀 호출 을 할 수 있다면 좋을 것 입니다. 이것이 바로 Y-combinator가하는 일입니다.

(define y
  (lambda (f)
    (f (lambda (x) ((y f) x))))) ;; pass (y f) to user lambda

(define fact
  (lambda (recur)
    (lambda (n)
      (if (= n 0)
          1
          (* n (recur (- n 1))))))) ;; recur directly

(print ((y fact) 7))

; => 5040

그러나 y이름 별 재귀 정의가 어떻게 있는지 보십니까? 를 사용 u하여 이름 별 참조를 제거하고 lambda대신 매개 변수를 사용하여 반복 할 수 있습니다 . 위에서했던 것과 동일합니다.

(define u
  (lambda (f) (f f)))

(define y
  (lambda (r)      ;; wrap in (lambda (r) ...)
    (lambda (f)
      (f (lambda (x) (((r r) f) x)))))) ;; replace y with (r r)

(define fact
  (lambda (recur)
    (lambda (n)
      (if (= n 0)
          1
          (* n (recur (- n 1)))))))

(print (((u y) fact) 7)) ;; replace y with (u y)

; => 5040

우리는 이제 사용하여 쓸 수 있습니다 lambda-

; (((u y) fact) 7)
(print ((((lambda (f) (f f))   ; u
          (lambda (r)          ; y
            (lambda (f)
              (f (lambda (x) (((r r) f) x))))))
         (lambda (recur)       ; fact
           (lambda (n)
             (if (= n 0)
                 1
                 (* n (recur (- n 1)))))))
        7))

; => 5040

커링을 사용하여 필요한 경우 더 많은 매개 변수를 지원하도록 기능을 확장 할 수 있습니다.

(define range
  (lambda (r)
    (lambda (start)
      (lambda (end)
        (if (> start end)
            null
            (cons start ((r (add1 start)) end)))))))

(define map
  (lambda (r)
    (lambda (f)
      (lambda (l)
        (if (null? l)
            null
            (cons (f (car l))
                  ((r f) (cdr l))))))))

(define nums
  ((((u y) range) 3) 9))

(define squares
  ((((u y) map) (lambda (x) (* x x))) nums))

(print squares)
; '(9 16 25 36 49 64 81)

그리고 하나의 lambda표현으로-

; ((((u y) map) (lambda (x) (* x x))) ((((u y) range) 3) 9))
(print (((((lambda (f) (f f)) ; u
           (lambda (r)        ; y
             (lambda (f)
               (f (lambda (x) (((r r) f) x))))))
          (lambda (r)         ; map
            (lambda (f)
              (lambda (l)
                (if (null? l)
                    null
                    (cons (f (car l))
                          ((r f) (cdr l))))))))
         (lambda (x) (* x x))) ; square
        (((((lambda (f) (f f)) ; u
            (lambda (r)        ; y
              (lambda (f)
                (f (lambda (x) (((r r) f) x))))))
           (lambda (r)         ; range
             (lambda (start)
               (lambda (end)
                 (if (> start end)
                     null
                     (cons start ((r (add1 start)) end)))))))
          3)   ; start
         9)))  ; end

; => '(9 16 25 36 49 64 81)

lazy 를 y사용 하는 멋진 구현을 확인하세요.

#lang lazy

(define y
  (lambda (f)
    (f (y f))))

#lang lazy

(define y
  ((lambda (f) (f f)) ; u
   (lambda (r)
     (lambda (f)
       (f ((r r) f))))))

#lang lazy

(define y
  ((lambda (r)
    (lambda (f)
      (f ((r r) f))))
  (lambda (r)
    (lambda (f)
      (f ((r r) f))))))