Y Combinator implementation Scheme

Question

I am really new to scheme functional programming. I recently came across Y-combinator function in lambda calculus, something like this Y ≡ (λy.(λx.y(xx))(λx.y(xx))). I wanted to implement it in scheme, i searched alot but i didn't find any implementation which exactly matches the above given structure. Some of them i found are given below:

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

and

(define Y
  (lambda (r)
    ((lambda (f) (f f))
     (lambda (y)
       (r (lambda (x) ((y y) x)))))))

As you can see, they dont match with the structure of this Y ≡ (λy.(λx.y(xx))(λx.y(xx))) combinator function. How can I implement it in scheme in exactly same way?

Liquidate

You can't, because the traditional Y combinator doesn't work with applicative order evaluation. – Legrand

The Y ≡ (λy.(λx.y(xx))(λx.y(xx))) version assumes lazy evaluation. One way to delay evaluation of a function is to wrap a function expression e in (lambda (arg) (e arg)), so in this case the function expression (procedure procedure) is re-written as (lambda (arg) ((procedure procedure) arg)). – Eskil

@AlexKnauth So if i have a recursive addition function to add 0 to n numbers like this: (define (REC procedure iterations) ( (ISZERO iterations) 0 (+ iterations (procedure (- iterations 1))) ) ) How would I use this with Y-combinator in scheme.? – Liquidate

That should probably be a separate question (and, I think you're missing an if). But in general, you would define procedure as (Y (lambda (procedure) ....)). – Eskil

Maybe you should read this question: Y combinator discussion in “The Little Schemer”. It shows why just using (procedure procedure) doesn't work. – Stingaree

Answer 1

In a lazy language like Lazy Racket you can use the normal order version, but not in any of the applicative order programming languages like Scheme. They will just go into an infinite loop.

The applicative version of Y is often called a Z combinator:

(define Z
  (lambda (f)
    ((lambda (g) (g g))
     (lambda (g)
       (f (lambda args (apply (g g) args)))))))

Now the first thing that happens when this is applied is (g g) and since you can always substitute a whole application with the expansion of it's body the body of the function can get rewritten to:

(define Z
  (lambda (f)
    ((lambda (g)
       (f (lambda args (apply (g g) args))))
     (lambda (g)
       (f (lambda args (apply (g g) args)))))))

I haven't really changed anything. It's just a little more code that does exactly the same. Notice this version uses apply to support multiple argument functions. Imagine the Ackermann function:

(define ackermann
  (lambda (m n)
    (cond
      ((= m 0) (+ n 1))
      ((= n 0) (ackermann (- m 1) 1))
      (else (ackermann (- m 1) (ackermann m (- n 1)))))))

(ackermann 3 6) ; ==> 509

This can be done with Z like this:

((Z (lambda (ackermann)
      (lambda (m n)
        (cond
        ((= m 0) (+ n 1))
        ((= n 0) (ackermann (- m 1) 1))
        (else (ackermann (- m 1) (ackermann m (- n 1))))))))
 3
 6) ; ==> 509

Notice the implementations is exactly the same and the difference is how the reference to itself is handled.

EDIT

So you are asking how the evaluation gets delayed. Well the normal order version looks like this:

(define Y
  (lambda (f)
    ((lambda (g) (g g))
     (lambda (g) (f (g g))))))

If you look at how this would be applied with an argument you'll notice that Y never returns since before it can apply f in (f (g g)) it needs to evaluate (g g) which in turn evaluates (f (g g)) etc. To salvage that we don't apply (g g) right away. We know (g g) becomes a function so we just give f a function that when applied will generate the actual function and apply it. If you have a function add1 you can make a wrapper (lambda (x) (add1 x)) that you can use instead and it will work. In the same manner (lambda args (apply (g g) args)) is the same as (g g) and you can see that by just applying substitution rules. The clue here is that this effectively stops the computation at each step until it's actually put into use.

Spectral

Can you tell me that How does "converting normal order Y combinator to Z combinator" solve the problem of infinite loop in applicative order language like scheme? – Liquidate

@QandeelAbbasi I've added some more info on how the infinite loop is avoided. – Spectral

@jupiterjelly In DrRacket 8.5 this still works when I use #lang racket as module language and many other supported eager languages. Know that there are student languages that don't support lambda which is a requirement for any combinator logic to work. – Spectral