2009.03.13 20:37

The Y Combinator

Recursion의 본질에 해당하는 Y 컴비네이터는

하스켈 커리가 발견했다
영어판 위키백과에 나오는 Y combinator 에는  다음과 같은 내용이 있다. 

One well-known (and perhaps the simplest) fixed point combinator in the untyped lambda calculus is called the Y combinator. It was discovered by Haskell B. Curry, and is defined as

Y = λf·(λx·f (x x)) (λx·f (x x))

We can see that this function acts as a fixed point combinator by expanding it for an example function g:

Y g = (λf . (λx . f (x x)) (λx . f (x x))) g
Y g = (λx . g (x x)) (λx . g (x x)) (β-reduction of λf - applied main function to g)
Y g = (λy . g (y y)) (λx . g (x x)) (α-conversion - renamed bound variable)
Y g = g ((λx . g (x x)) (λx . g (x x))) (β-reduction of λy - applied left function to right function)
Y g = g (Y g) (definition of Y)


Y combinator는  Fixed Point 의 본질에 해당하는 부분으로 설명할 내용이 많다. 
픽스드포인트는 sicp 에도 나오지만 f(x)=x ; f  (f (x)) =f(x) =x ; 
이런 식으로 만들어 낼 수 있는 함수의 성질이다


리스프의 가장 본질적인 재귀처리는 label 함수로 처리한다, 그 본질은 결국 Y 컴비네이터와 같다. 
이 문제는 TAOI에도 나온다.  TAOI의 맨 마지막 페이지에 나온다.

좋은 예제를 찾고 있었으나 최근에 발견한 설명중 가장 좋은 예는 J.Franco라는 UC 교수님의 글이다. 
정말 잘 쓴 예라고 생각한다. 
이 글과 Why of Y 라는 Friedman의 글 그리고 root of lisp을 같이 놓고 생각하면 윤곽을 잡을 수 있을 것이다.  
자기자신에 스스로를 대입하는 함수는 신기한 것 같지만 별다른 것이 아니다.
그 설명이 아래에 있다. 몇일 동안 궁금하던 것을 글을 읽고 바로 이해했다. 정말 기뻤다.

예전의 root of lisp 의 소개글에서 eval (e, a) 는 식 (e) 와  환경(a)를  놓고 계산하는 것인데 (예전의 리스프에 대한 생각들 - 두번째 이야기에 해당한다. )

(eval. '((label firstatom (lambda (x) (cond ((atom x) x)    ('t (firstatom (car x)))))) y) '((y ((a b) (c d))))) ==> (eval. '((lambda (x) (cond ((atom x) x) ('t (firstatom (car x))))) y) '((firstatom (label firstatom (lambda (x) (cond ((atom x) x) ('t (firstatom (car x))))))) (y ((a b) (c d)))))


여기서 중요한 것은 firstatom 이라는 람다식이 그대로 환경에 등록되어 결국은 firstatom 내에서 일종의 텍스트치환이 일어나는 것처럼 동작한다.  초기의 리스프부터  recursion은 이런 식으로 해결되었다. 나중에는 set!을 써서 환경을 직접 고쳤다. 결국 변수문제는 환경문제다.  리스프와 스킴의 변수 문제는 깊은 통찰을 제공한다. 

 

스킴에서는 letrec 이라는 것으로 해결할 수 있는데  letrec이 별다른 것이 아니다. Richard P. Gabriel 의 why of y 에 보면

(define fact
 (lambda (n)
  (if (< n 2) 1 (* n (fact (- n 1))))))

은  다음과 같이 만들 수도 있는데
(letrec
 ((f (lambda (n)
   (if (< n 2) 1 (* n (f (- n 1)))))))
(f 10))

결국 let 과  set! 으로 구현하는 경우가 많다.

(letrec ((f (lambda ...))) ...)

은  다음과 등가이다.

(let ((f <undefined>)) (set! f (lambda ...)) ...)

define은 인터프리터의 구현에서 set! 를 사용하고 letrec도 마찬가지다.
그러나 label 과 letrec을 사용하지 않고 recursion을 구현할 수도 있는데 그것은 Y 컴비네이터를 사용하는 방법이다.  Y는 recursion과 fixed point 의 본질이다. 

따지고 보면 앞의 label은 같은 일을 하는 것으로 볼 수 있다. 
머리가 나쁜  이유로 몇번을 보고서야 이해 비슷한 것을 얻을 수 있었다.


 

 

The Y Combinator

In this file we derive the Y combinator, one of the fundamental results of recursive procedure theory. You already know that in some cases it is not necessary to give a procedure a name. For example,

  ((lambda (x) (+ x 1)) 6)

adds 1 to 6 without naming the procedure that does it. But, what about a recursive procedure? For example,

  (define fact
    (lambda (n)
      (if (zero? n)
          1
          (* n (fact (- n 1))))))

which computes the factorial of a number n, seems to need the name "fact" so that in the last line of the procedure it can recurse on itself. But, we will see this is not necessary and, in the process, will develop a lot of intuition about using Scheme. We proceed step by step, changing "fact" slightly on each step.

------------------------------------------------

영어판 위키백과에 나오는 Y combinator 에는  다음과 같은 내용이 있다. 

Consider the factorial function (under Church encoding). The usual recursive mathematical equation is

fact(n) = if n=0 then 1 else n * fact(n-1)

We can express a "single step" of this recursion in lambda calculus as

F = λf. λx. (ISZERO x) 1 (MULT x (f (PRED x))),

where "f" is a place-holder argument for the factorial function to be passed to itself. The function F performs a single step in the evaluation of the recursive formula. Applying the fix operator gives

fix(F)(n) = F(fix(F))(n)
fix(F)(n) = λx. (ISZERO x) 1 (MULT x (fix(F) (PRED x)))(n)
fix(F)(n) = (ISZERO n) 1 (MULT n (fix(F) (PRED n)))

We can abbreviate fix(F) as fact, and we have

fact(n) = (ISZERO n) 1 (MULT n (fact(PRED n)))

So we see that a fixed-point operator really does turn our non-recursive "factorial step" function into a recursive function satisfying the intended equation.

-------------------------------------------------

Step 1. The first idea is simply to pass "fact" in as an argument in much the same way that we did for

  (define op-maker
    (lambda (op)
      (lambda (x y)
        (op x y))))

The first lambda passes the name of the operation and the second lambda is the nameless operation. Let's try this with "fact". The first attempt is

  (define fact-maker
    (lambda (procedure)
      (lambda (n)
        (if (zero? n)
            1
            (* n (procedure (- n 1)))))))

The idea will be to pass "fact-maker" in through "procedure". Thus, what we would like to do is invoke (fact-maker fact-maker) to produce our nameless (well, almost nameless) factorial procedure. This would allow us to write, for example

  >((fact-maker fact-maker) 5)
  120

But, this doesn't work because "fact-maker" is a procedure which takes as input one argument that is a procedure but "procedure", which is supposed to be identical to "fact", requires a numeric argument. The solution is the following:

  (define fact-maker
    (lambda (procedure)
      (lambda (n)
         (if (zero? n)
             1
             (* n ((procedure procedure) (- n 1)))))))

Try this, for example, with

 >((fact-maker fact-maker) 5)

Well, we got the name out of the body of the procedure but we still have to pass the procedure in and so far we have been using a name to do that. So let's try to get the whole dependence on a name out.

Step 2. Recall we demand that "fact" be identical to (procedure procedure) which in turn must be identical to (fact-maker fact-maker) (recall the example ((fact-maker fact-maker) 5) which gives the same result as (fact 5)). Thus, we can write "fact-maker" in the following way, making use of the result of step 1.

  (define fact
    ((lambda (procedure)
       (lambda (n)
         (if (zero? n)
             1
             (* n ((procedure procedure) (- n 1))))))
     (lambda (procedure)
       (lambda (n)
         (if (zero? n)
             1
             (* n ((procedure procedure) (- n 1))))))))

Try this with >(fact 5)

Consider the following:

  (((lambda (procedure)
      (lambda (n)
        (if (zero? n)
            1
            (* n ((procedure procedure) (- n 1))))))
    (lambda (procedure)
      (lambda (n)
        (if (zero? n)
            1
            (* n ((procedure procedure) (- n 1)))))))
   5)

This produces the factorial of 5 because the procedure which is invoked (the huge mess) is exactly the definition of "fact." But, lo and behold, there is no name for this procedure anywhere!

In what follows, we try to generalize this to all procedures and wind up with the dreaded applicative-order Y-combinator.

Step 3. First, we need to separate out the part that pertains to computing the factorial. The goal is to write this part in one place and when code for other problems is substituted for the factorial code, the result will be a new recursive procedure. This step is a little tricky because we insist on using, with no significant changes, code that was designed assuming a procedure name. The section of factorial code we currently have, from step 2, is

  (define F
    (lambda (n)
      (if (zero? n)
          1
          (* n ((procedure procedure) (- n 1))))))

This is different from what we want because it contains a (procedure procedure) where we would like to see a plain old procedure. So, we use a trick to get it out. In general, isn't

  (f arg)

identical to

  ((lambda (x) (f x)) arg) ?

The second statement is a little strange, though, because it makes you pass "arg" into a procedure so that the procedure which would be applied to it anyway is applied. Why do we want to do such a thing? Watch! This means that

  ((procedure procedure) (- n 1))

is the same as

  ((lambda (arg) ((procedure procedure) arg)) (- n 1))

and we substitute this into our current version of F to get

  (define F
    (lambda (n)
      (if (zero? n)
          1
          (* n ((lambda (arg) ((procedure procedure) arg)) (- n 1))))))

How has this helped? Well, the (lambda (arg)...) is ONE procedure and procedures can be passed as arguments so F can be defined as

  (define F
    ((lambda (func-arg)
       (lambda (n)
         (if (zero? n)
             1
             (* n (func-arg (- n 1))))))
     (lambda (arg) ((procedure procedure) arg))))

Yes, it's the same F but the old definition looked like this:

  (define F (lambda (n) ... < procedure >))

and the new definition looks like this:

  (define F ((lambda (func-arg) (lambda (n) ...)) < procedure >))

where < procedure > is the (lambda (arg) ((procedure... ) ...) ...) expression

Step 4. - Now we are ready to take the result of step 3 and apply it to the result of step 2. Writing out the whole thing, we get:

  (define fact
    ((lambda (procedure)
       ((lambda (func-arg)
          (lambda (n)
            (if (zero? n)
                1
                (* n (func-arg (- n 1))))))
        (lambda (arg) ((procedure procedure) arg))))
     (lambda (procedure)
       ((lambda (func-arg)
          (lambda (n)
            (if (zero? n)
                1
                (* n (func-arg (- n 1))))))
        (lambda (arg) ((procedure procedure) arg))))))

You will probably want to study this carefully. Notice the double left parens in front of ((lambda (func-arg)... This is because we are writing

   ...
   ((lambda (func-arg) < body-using-func-arg >) (lambda (arg) ...))

which has the same form as

  ((lambda (arg) ((procedure procedure) arg)) (- n 1))

but is different in that a procedure is passed as an "arg" instead of an integer.

The two expressions beginning with (lambda (func-arg) ...) are exactly the pieces of code that correspond to the factorial code and they are in exactly the right form. So we can get them out of the definition of fact in the following way:

  (define F*
    (lambda (func-arg)
      (lambda (n)
        (if (zero? n)
            1
            (* n (func-arg (- n 1)))))))

  (define fact
    ((lambda (procedure)
       (F* (lambda (arg) ((procedure procedure) arg))))
     (lambda (procedure)
       (F* (lambda (arg) ((procedure procedure) arg))))))

This is significant because we can now use any procedure in place of F* to change functionality to whatever we want. The only problem is that, as written, we still need to name F*. This is easily remedied in the next step.

-----------------------------------------------------------------------------
영어판 위키백과에 나오는 Y combinator 의 예제는 이번의 예제가  application - order라는 것을 설명하고 있다.

A version of the Y combinator that can be used in call-by-value (applicative-order) evaluation is given by η-expansion of part of the ordinary Y combinator:

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

..

-----------------------------------------------------------------------------


Step 5. Jackpot! Now we write the dreaded applicative-order Y-combinator:

  (define Y
    (lambda (X)
      ((lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg))))
       (lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg)))))))

Notice that the procedure which does our computation is X (we stopped using F* to emphasize this code can be applied to any procedure) and that is passed in as an argument.

Step 6. We can write "fact" in terms of the Y-combinator as follows:

  (define fact (Y F*))

Try >(fact 5) to check the result. For that matter, try >((Y F*) 5). But Y is general and F* is specific to factorial but with no name! If we wrote the whole thing out it would be

  (((lambda (X)
      ((lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg))))
       (lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg))))))
    (lambda (func-arg)
      (lambda (n)
        (if (zero? n)
            1
            (* n (func-arg (- n 1)))))))
   5)

Look Ma! No name! Just to show the generality of all this let's use the Y combinator to define another procedure. Say findmax - finding the largest integer in a list.

  (define findmax
    (lambda (l)
      (if (null? l)
          'no-list
          (if (null? (cdr l))
              (car l)
              (max (car l) (findmax (cdr l)))))))

First, create the analog of F* for fact, call it M for max.

  (define M
    (lambda (func-arg)
      (lambda (l)
        (if (null? l)
            'no-list
            (if (null? (cdr l))
                (car l)
                (max (car l) (func-arg (cdr l))))))))

Now try ((Y M) '(4 5 6 3 4 8 6 2)) to see if it works. If you want to build it out it looks like this:

  (((lambda (X)
      ((lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg))))
       (lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg))))))
    (lambda (func-arg)
      (lambda (l)
        (if (null? l)
            'no-list
            (if (null? (cdr l))
                (car l)
                (max (car l) (func-arg (cdr l))))))))
   '(4 5 6 3 4 8 6 2))

As an assignment for the interested student, write findamx without using the procedure name "max". Just how many of the remaining names in findmax do you think can be disposed of? Talk about a nameless society...


조금 더 유명했던 글로  리처드 가브리엘(Richard P. Gabriel)의 Why of Y 가 있다. 이글 역시 대단한 개념글로  유명한 연구자가 쓴 글이다.  비슷하게 유명한 Daniel Friedman 이 쓴 (Y Y) works! 라는 글도 있으나  Little Lisper 라는 책이  정이 붙지 않는 것과 비슷하게 적응하기 힘들었다.

글의 형태를 간단하게 카피앤페이스트 하기 위해 ddj에 있는 것을 옮겼으나 웹에서는 pdf 문서를 구할 수 있다.
주석만 달겠다. 많은 부분이 겹치기 때문이다. 

The Why of Y

One way to derive Y.

By Richard P. Gabriel,  Dr. Dobb's Journal
4Ô 22, 2007
URL:http://www.ddj.com/architect/199200394

Richard P. Gabriel is a Distinguished Engineer at IBM Research, looking into the architecture, design, and implementation of extraordinarily large, self-sustaining systems. He can be contacted at www.dreamsongs.com.


Did you ever wonder how Y works and how anyone could ever have thought of it? In this article, I explain not only how it works, but how someone could have invented it in the first place. I'll use Scheme notation because when functions passed as arguments are applied, Y is easier to understand.

Y's goal is to provide a mechanism to write self-referential progra ms without any special built-in means. Scheme has several mechanisms for writing such programs, including global function definitions and letrec. One way you can write the factorial function in Scheme is:

(define fact (lambda (n) (if (< n 2) 1 (* n (fact (- n 1))))))

This function works because a global variable, fact, has its value set to the value of the lambda expression. When the variable fact in the body of the function is evaluated to determine which function to invoke, the value is found in the global variable. Using a global variable as a function name can be rather unpleasant because it relies on a global, and thus vulnerable, resource -- that is, the global variable space. The Scheme self-reference form letrec usually is implemented using a side effect; it is easier to reason about programming languages and programs that have no side effects. Therefore, it is of theoretical interest to establish the ability to write recursive functions without using side effects. A program that uses letrec is:

(letrec ((f (lambda (n) (if (< n 2) 1 (* n (f (- n1))))))) (f 10))

This program computes 10!. The reference inside the lambda express ion is to the binding of f, as established by the letrec. You can implement letrec using let and set!:

(letrec ((f (lambda ...))) ...)

which is equivalent to:

(let ((f )) (set! f (lambda ...)) ...)

All references to f in the lambda expression are to the value of the lambda expression. Y takes a function describing another recursive or self-referential function and returns another function that implements the recursive function. Y is used to compute 10! with:

(let ((f (y (lambda (n) (lambda (n) (if (< n 2) 1 (* n (h (- n 1))))) )))))) (f 10))

The function passed as an argument to Y takes a function as an argument and returns a function that looks like the factorial function we want to define. That is, the function passed to Y is (lambda (h) ...). The body of this function looks like the factorial function, except that where we would expect a recursive call to the factorial function, h is called instead. Y arranges for an appropriate value to be supplied as the value of h.

People call Y the "applicative-order fixed-point operator for functionals." Let's take a closer look at what this means in the factorial example.

Suppose M is the true mathematical factorial function, possibly in Plato's heaven. Let F denote the function:

F = (lambda (h) (lambda (n) (if (< n 2) 1 (* n (h (- n 1))))))

Then:

((F M) n) = (M n).

That is, M is a fixed point of F: F maps (in some sense) M onto M. Y satisfies the property:

((F (Y F)) X) = ((Y F) X)

This property of Y is very important. Another important property is that the least defined fixed point for functionals is unique; therefore, (Y F) and M are in some sense the same. Applicative-order Y is not the same as classical Y, which is a combinator. Some texts refer to Y as Z. To derive Y, I will start with a recursive function example, factorial. In the derivation I will use three techniques:

  • The first one passes an additional argument to avoid using any self-reference primitives from Scheme.
  • The second technique converts multiple-parameter functions to nested single-parameter functions to separate manipulations of the self-reference and ordinary parameters.
  • The third technique introduces functions through abstraction.

All code examples will use the variables n and m to refer to integers, the variable x to refer to an unknown but undistinguished argument, and the variables f, g, h, q, and r to refer to functions. The basic form of the factorial function is:

(lambda (n) (if (< n 2) 1 (* n (h (- n1)))))

The h variable should refer to the function we wish to invoke when a recursive call is made, which is the factorial function itself. Since we have no way to make h refer directly to the correct function, let's pass it in as an argument:

(lambda (h n) (if (< n 2) 1 (* n (h h (- n 1)))))

--------------------------------------------------------------------------

앞의 첫번째 예제가 h,n 을  개별적인 lambda 를 사용한 것과 달리 h 는 함수로 n은
팩토리얼의 인자로 사용했다.

그 결과 (h h (- n 1)) 은  (lambda (h n) 에서 인자로 받은 h 에 h와 n-1 을 다시 적용하는
(* n (h h (- n 1))) 형태가 된다. (h h (- n 1))  은 새로운 recursion 을 일으킨다.

-------------------------------------------------------------------------

In the recursive call to h, the first argument will also be h because we want to pass on the correct function to use in the recursive situation for later invocations of the function. Therefore, to compute 10! we would write:

(let ((g (lambda (h n) (if (< n 2) 1 (* n (h h (- n 1))))))) (g g 10) )


-------------------------------------------------------------------------------------
앞의 식을 g 로 만들고  (g g 10) 을 대입한다.
실제로 이 코드를 돌려보면 3628800 이  나온다.
-------------------------------------------------------------------------------------

During the evaluation of the body of g, h's value is the same as the value of g established by let; that is, during execution of g, h refers to the executing function. When the function call (h h (- n 1)) happens, the same value is passed along as an argument to h; h passes itself to itself. We want to split the management of the function's self-reference fr om the management of other arguments. In this particular case, we want to separate the management of h from that of n. A technique called "currying" is the standard way to handle this separation. Before we curry this example, let's look at another example of currying. Here is a program that also computes 10!, but in a slightly more clever way:

(letrec ((f (lambda (n m) (if (< n 2) m (f (- n 1) (* m n)))))) (f 10 1))

The trick is to use an accumulator, m, to compute the result. Let's curry the definition of f:

(letrec ((f (lambda (n) (lambda (m) (if (< n 2) m ((f (- n 1)) (* m n ))))))) ((f 10) 1))

-------------------------------------------------------
아래의 몇줄의 문항은 closure 와 currying 을 적용하겠다는 것이다.
currying은  영어판 위키 백과에도 나온다.
-----------------------------------------------------

The idea of currying is that every function has one argument. Passing multiple arguments is accomplished with nested function application: the first application returns a function that takes the second argument and completes the computation of the value. In the previous piece of code, the recursive call:

((f (- n 1)) (* m n))

has two steps: the proper function to apply is computed and applied to the right argument. We can use this idea to curry the other factorial program:

(let ((g (lambda (h) (lambda (n) (if (< n 2) 1 (* n ((h h) (- n 1)))) ))) ((g g) 10))


----------------------------------------------------------------------------------
let 이 lambda 의 syntactic sugar 라는 말은 sicp 에 여러 번 나온다,
결국 (labmda (g)  ( (g g) 10 ) (lambda (h) (....))
----------------------------------------------------------------------------------

In this piece of code, the recursive call also computes and applies the proper function. But that proper function is computed by applying a function to itself. Applying a function to itself is the process by which we get the basic functionality of a self-reference. The self-application (g g) in the last line of the program calls g with g itself as an argument. This returns a closure in which the variable h is bound to the outside g. This closure takes a number and does the basic factorial comput ation. If the computation needs to perform a recursive call, it invokes the closed-over h with the closed-over has an argument, but all the hs are bound to the function g as defined by the let. To summarize this technique, suppose we have a self-referential function using letrec as in the following code skeleton:

(letrec ((f (lambda (x) ... f ...))) ... f ...)

This skeleton can be turned into a self-referential function that uses let where r is a fresh identifier:

(let ((f (lambda (r) (lambda (x) ... (r r) ...)))) ... (f f) 


----------------------------------------------------------------------------------------
위의 letrec과 let 의 차이를 설명하는 결정적인 커멘트는 매우 중요한 것인데 썰렁하게 설명하고 있다,
앞의 label 함수 부분을 다시 한번 살펴 보라!
----------------------------------------------------------------------------------------


For the next step, let's examine how to separate further the management of h in our factorial function from the management of n. Recall that the factorial program looks like:


(let ((g (lambda (h)
    (lambda (n)
     (if (< n 2) 1 (* n ((h h) (- n 1))))))))
  ((g g) 10))

 

Our plan of attack is to abstract the if expression over (h h) and n, which will accomplish two things: the resulting function will become independent of its surrounding bindings and the management of the control argument will become separated from the numeric argument. The result of the abstraction is:

(let ((g (lambda (h) 
   (lambda (n) 
      (let ((f (lambda (q n) 
         (if (< n 2) 1 (* n (q (- n 1))))))) (f (h h) n)))))) 
((g g) 10))

We can curry the definition of f, which also changes its call:

(let ((g (lambda (h) 
       (lambda (n) 
          (let ((f (lambda (q) 
            (lambda (n) 
               (if (< n 2) 1 (* n (q (- n 1)))))))) ((f (h h)) n)))))) 
((g g) 10))

Notice that the definition of the function f need not be deeply embedded in the function g. Therefore, we can extract the main part of the function -- the part that computes factorial -- from the rest of the code.

(let ((f (lambda (q) (lambda (n) (if (< n 2) 1 (* n (q (- n 1)))))))) 
  (let ((g (lambda (h) (lambda (n) ((f (h h)) n))))) 
     ((g g) 10)))

The form of f is once again the parameterized form of factorial, and we can abstract this expression over f, which produces Y as follows:

(define Y (lambda (f) 
           (let ((g (lambda (h) 
                     (lambda (x) ((f (h h)) x)) ))) 
                      (g g))))

This is one way to derive Y.


------------------------------------------------------
결론은 둘다  같다.
그리고 전체 다시 한두번 더 읽어 보기를 권한다.
머리 속에도 다시 한 번 이 내용을 apply 해서 계산을 일으킬 필요가 있다. 

두 글의 결론은?
람다 함수는 치환으로 모든 것을 해결한다는 것이다.

이렇게 끝난다. 
조만간 한글로된 정리판을 만들 예정이지만 
그때까지는 이 정도로 참는 수 밖에 없겠다.


-------------------------------------------------------

추가:)

람다를  쓰다보니 형식은 자유롭다. 그중에는

http://www.rosettacode.org/wiki/Y_combinator#Scheme

> (define (Y f) ((lambda (x) (x x)) (lambda (y) (f (lambda args (apply (y y) args))))))
> (define (fac f) (lambda (n) (if (= n 0) 1 (* n (f (- n 1))))))
> ((Y fac) 5)
120
> (define (fib f)

(lambda (n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (f (- n 1)) (f (- n 2)))))))





>
((Y fib) 8)
21




(lambda  args (apply ..) ...) 의 형태는 괄호가 없는데 r5rs 9 페이지에 나오는 설명이 있다.
args 는 임의의 숫자로 정할 수 있다.

The procedure takes any number of arguments;
when the procedure is called, the sequence
of actual arguments is converted into a newly allocated
list, and the list is stored in the binding of the
variable.

Trackback 2 Comment 0