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

 From: Matthias Felleisen (matthias at ccs.neu.edu) Date: Wed Aug 4 12:25:08 EDT 2010 Previous message: [racket-dev] using the Y combinator to... Next message: [racket-dev] using the Y combinator to... Messages sorted by: [date] [thread] [subject] [author]

```SICP's treatment of the Y combinator is uninformed by existing programming language theory (1960s and 70s stuff) and is therefore wrong. To their credit, they allude to the problem with words such as normal-forms, reduction, and applicative etc. That's wrong too but at least it warns readers of potential problems.

You have discovered one of the essential problems.

For a thorough discussion, though in an unusual style see the discussion The Little Schemer, nee The Little LISPer (also MIT Press). For a very old draft of this material, visit

http://www.ccs.neu.edu/home/matthias/misc.html

and look into Why of Y.

hth -- Matthias

On Aug 4, 2010, at 12:20 PM, The Configurator wrote:

> 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.
> _________________________________________________