고정 소수점 결합 자 lisp로

Question

;; compute the max of a list of integers 

(define Y 
    (lambda (w) 
    ((lambda (f) 
     (f f)) 
    (lambda (f) 
     (w (lambda (x) 
      ((f f) x))))))) 

((Y 
    (lambda (max) 
    (lambda (l) 
     (cond ((null? l) -1) 
      ((> (car l) (max (cdr l))) (car l)) 
      (else (max (cdr l))))))) 
'(1 2 3 4 5)) 

이 구성을 이해하고 싶습니다. 누군가이 코드에 대해 명확하고 간단한 설명을 줄 수 있습니까?

예를 들어, 내가 Y의 공식을 잊어 버린다고 가정하면 어떻게 기억하고 그것을 사용하여 오래 재생할 수 있습니까?

Answer 1

여기 (날) 어떤 관련 답이다 : 기본적

• Y combinator discussion in "The Little Schemer"
• Unable to get implementation of Y combinator working
• In Scheme, how do you use lambda to create a recursive function?

, λr.(λh.h h) (λg.r (λx.(g g) x)) 정의 Y, Y r가

으로 감소 애플리케이션과두 번째 먼저 재귀 함수를 나타내는 호출하고, - -

Y r 
(λw.(λh.h h) (λg.w (λx.(g g) x))) r 
(λh.h h) (λg.r (λx.(g g) x)) 
h h 
    ;where 
     h = (λg.r (λx.(g g) x))  <----\ 
              | 
(λg.r (λx.(g g) x)) h      | 
r (λx.(g g) x)    <-------------- | ----------\ 
    ;where         |   | 
     g = h       -----/   | 
     ;so that          | 
     (g g) = (h h) = r (λx.(g g) x)   ------/ 

그래서 r는 두 개의 인수를 기대합니다 실제 인수 :

 r = λf (λx. ....x.....(f y)......) 

은 그래서 (Y r) x은 감소

(r (λx.(g g) x)) x 
(r f) x 
    ;where 
     f = (λx.(g g) x) 
     f y = (λx.(g g) x) y = (g g) y = (r f) y ; f is "fixed point" of r 

definiton로 f = (λx.(g g) x)은 f y이 호출 될 때 (g g) y이 호출 될 때 이라고 말합니다.g은 g 내에서 r "pullled"이며 인수로 호출 된 (r f)의 결과가 자체 적용됩니다. 나는. (r f) 애플리케이션에서 발생하는 람다 표현식의 몸체에있는 임의의 호출 (f y)은 (r f) y으로 다시 변환됩니다. 즉, 새로운 인수 y을 사용하여 동일한 본문을 호출합니다.

중요한 구현상의 세부

그것이 같은 함수 본문, 또는 그 사본, 그러나 의미는 동일 여부 - 우리는 새로운 인수 값과 동일한 기능 본문을 입력 할 수 있습니다.

Y 결합 자의 본질은 참조 및 자체 적용을 통한 복제입니다. 동일한 이름을 통해 동일한 내용을 참조합니다., 두 번; 따라서 을 인수로 받도록을 지정합니다.

이 순수 람다 계산법에서와 같이 어떤 참조가 없습니다 및 매개 변수 인수의 텍스트 사본을받을 때 - 즉, 감소가 텍스트 재 작성하여 수행됩니다 - 동일한 사본 복제 및 인수로 공급되고, 건네받을 때문에 여전히 작동 다음 반복에서 사용할 수 있도록 필요한 경우 자기에게.

하지만 훨씬 더 공유 참조를 사용할 수있을 때 효율적이다는 (같은 이름의 모든 사용은 같은 일 참조).

---

은 사실 답의 정의는 실용적 차 Y 연결자의 즉

(let ((fact #f)) 
    (set! fact 
     (lambda (n) (if (< 2 n) 1 
           (* n (fact (- n 1)))))) 
    fact) 

로 자기 참조 기능의 평가 창조의 환경에서 모델은 간단하다. 정상적인 순서로, ETA 환원은 canonically

Ynorm = (λf.(λx.f (x x)) (λx.f (x x))) 

실제로

Ynorm g 
= (λx.g (x x)) (λx.g (x x)) 
= g ((λx.g (x x)) (λx.g (x x))) 

Answer 2

내가 지금까지 발견 한 가장 좋은 설명은 책 "The Little Schemer"의 9 장에있다. 전체 장에서는 Y-Combinator가 작동하는 방법과 임의의 재귀 적 절차에서 시작하는 결합자를 유도하는 방법을 설명한다. .