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

Look up the difference between the call by name and call by value Y combinator.
Jay
On Wed, Aug 4, 2010 at 10:20 AM, The Configurator
<configurator at gmail.com> wrote:
>* 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.
*>* _________________________________________________
*>* For list-related administrative tasks:
*>* http://lists.racket-lang.org/listinfo/dev
*>*
*
--
Jay McCarthy <jay at cs.byu.edu>
Assistant Professor / Brigham Young University
http://teammccarthy.org/jay
"The glory of God is Intelligence" - D&C 93