# [racket-dev] using the Y combinator to...

 From: The Configurator (configurator at gmail.com) Date: Wed Aug 4 12:20:14 EDT 2010 Previous message: [racket-dev] Tech links with custom text Next message: [racket-dev] using the Y combinator to... Messages sorted by: [date] [thread] [subject] [author]

```I'll hijack the thread since I've been meaning to ask about the Y
combinator.
>From SICP I've seen that the Y combinator is the function
(define (y f)
((lambda (x) (f (x x)))
(lambda (x) (f (x x)))))

This makes mathematical sense, since
(y f)
= ((lambda (x) (f (x x))) (lambda (x) (f (x x))))
= (f ((lambda (x) (f (x x))) (lambda (x) (f (x x)))))
= (f (y f))

But when actually applying it:
// g improves a function to get a ceiling function. The fixed point would be
similar to (lambda (x) (inexact->exact (ceiling x)))
(define (g f)
(lambda (x)
(if (<= x 0)
0
(+ 1 (f (- x 1))))))

> ((g (g (g (g (g #f))))) 3.3)
4

Now let's step through
((y g) 3.3)
= (((lambda (x) (g (x x))) (lambda (x) (g (x x)))) 3.3)
= ((g ((lambda (x) (g (x x))) (lambda (x) (g (x x))))) 3.3)
now, to get the (g ...) result we need to apply g to it's operand. For that,
we need to evaluate it:
= ((g (g ((lambda (x) (g (x x))) (lambda (x) (g (x x)))))) 3.3)
= ((g (g (g ((lambda (x) (g (x x))) (lambda (x) (g (x x)))))))) 3.3)
= ((g (g (g (g ((lambda (x) (g (x x))) (lambda (x) (g (x x))))))))) 3.3)

And I just ran out of memory.

What am I missing here?
It seems obvious to me that if we add a delay/force or somesuch thing it
solves the problem. But that's not the y-combinator I was shown.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/dev/archive/attachments/20100804/38467f02/attachment.html>
```

 Posted on the dev mailing list. Previous message: [racket-dev] Tech links with custom text Next message: [racket-dev] using the Y combinator to... Messages sorted by: [date] [thread] [subject] [author]