Search code examples
schemey-combinator

Understanding extra arguments in the Y Combinator in Scheme

According to RosettaCode, the Y Combinator in Scheme is implemented as 

(define Y
  (λ (h)
    ((λ (x) (x x))
     (λ (g)
       (h (λ args (apply (g g) args)))))))

Of course, the traditional Y Combinator is λf.(λx. f(x x))(λx. f(x x))

My question, then, is about h and args, which don't appear in the mathematical definition, and about apply, which seems like it should either be in both halves of the Combinator or in neither.

Can someone help me understand what is going on here?

Solution

  • Lets start off with the lambda calculus version traslated to Scheme:

    (λ (f) 
 ((λ (x) (f (x x)))
  (λ (x) (f (x x)))))

    I'd like to simplify this since I see (λ (x) (f x x)) is repeated twice. You can substitute the beginning there to this:

    (λ (f) 
 ((λ (b) (b b))
  (λ (x) (f (x x)))))

    Scheme is an eager language so it will go into an infinite loop. In order to avoid that we make a proxy.. Imagine you have + that takes two numbers, you can substitute it with (λ (a b) (+ a b)) without the result being changed. Lets do that with the code:

    (λ (f) 
 ((λ (b) (b b))
  (λ (x) (f (λ (p) ((x x) p))))))

    Actully this has its own name. It's called the Z combinator. (x x) is not done when f is applied only when the supplied proxy is applied. Delayed one step. It might look strange but I know (x x) becomes a function so this is exactly the same as my + substitution above.

    In Lambda calculus all functions takes one argument. If you see f x y it's actually the same as ((f x) y) in Scheme. If you want it to work with functions of all arities your substitution needs to reflect that. In Scheme we have rest arguments and apply to do this. 

    (λ (f) 
 ((λ (b) (b b))
  (λ (x) (f (λ p (apply (x x) p))))))

    This isn't neede if you only are going to use one arity functions as in lambda calculus.

    Notice that in your code you use h instead of f. It doesn't really matter what you call the variables. This is the same code with different names. So this is the same:

    (λ (rec-fun) 
 ((λ (yfun) (yfun yfun))
  (λ (self) (rec-fun (λ args (apply (self self) args))))))

    Needless to say (yfun yfun) and (self self) does the same thing.