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: > 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 _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
