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 <configura...@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 <j...@cs.byu.edu> Assistant Professor / Brigham Young University http://teammccarthy.org/jay "The glory of God is Intelligence" - D&C 93 _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev