So it seems I understood it correctly.<div>My implementation of a Y-like combinator,</div><div>(define (y f) ((lambda (x) (f (delay (x x)))) (lambda (x) (f (delay (x x))))))</div><div>works well - except that the combinated function needs to call ((force f) ...) instead of (f ...)</div> <div><br></div><div>Guess I just missed the part where Hal mentioned that their y-combinator only works in "normal-order" and not "applicative-order" evaluation.</div><div>(This is from the video lectures, by the way - not the book)<br> <br><div class="gmail_quote">On Wed, Aug 4, 2010 at 17:25, Matthias Felleisen <span dir="ltr"><<a href="mailto:matthias@ccs.neu.edu">matthias@ccs.neu.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"> <br> 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.<br> <br> You have discovered one of the essential problems.<br> <br> 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<br> <br> <a href="http://www.ccs.neu.edu/home/matthias/misc.html" target="_blank">http://www.ccs.neu.edu/home/matthias/misc.html</a><br> <br> and look into Why of Y.<br> <br> hth -- Matthias<br> <div><div></div><div class="h5"><br> <br> <br> <br> On Aug 4, 2010, at 12:20 PM, The Configurator wrote:<br> <br> > I'll hijack the thread since I've been meaning to ask about the Y combinator.<br> > From SICP I've seen that the Y combinator is the function<br> > (define (y f)<br> > ((lambda (x) (f (x x)))<br> > (lambda (x) (f (x x)))))<br> ><br> > This makes mathematical sense, since<br> > (y f)<br> > = ((lambda (x) (f (x x))) (lambda (x) (f (x x))))<br> > = (f ((lambda (x) (f (x x))) (lambda (x) (f (x x)))))<br> > = (f (y f))<br> ><br> > But when actually applying it:<br> > // g improves a function to get a ceiling function. The fixed point would be similar to (lambda (x) (inexact->exact (ceiling x)))<br> > (define (g f)<br> > (lambda (x)<br> > (if (<= x 0)<br> > 0<br> > (+ 1 (f (- x 1))))))<br> ><br> > > ((g (g (g (g (g #f))))) 3.3)<br> > 4<br> ><br> > Now let's step through<br> > ((y g) 3.3)<br> > = (((lambda (x) (g (x x))) (lambda (x) (g (x x)))) 3.3)<br> > = ((g ((lambda (x) (g (x x))) (lambda (x) (g (x x))))) 3.3)<br> > now, to get the (g ...) result we need to apply g to it's operand. For that, we need to evaluate it:<br> > = ((g (g ((lambda (x) (g (x x))) (lambda (x) (g (x x)))))) 3.3)<br> > = ((g (g (g ((lambda (x) (g (x x))) (lambda (x) (g (x x)))))))) 3.3)<br> > = ((g (g (g (g ((lambda (x) (g (x x))) (lambda (x) (g (x x))))))))) 3.3)<br> ><br> > And I just ran out of memory.<br> ><br> > What am I missing here?<br> > 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.<br> </div></div><div><div></div><div class="h5">> _________________________________________________<br> > For list-related administrative tasks:<br> > <a href="http://lists.racket-lang.org/listinfo/dev" target="_blank">http://lists.racket-lang.org/listinfo/dev</a><br> <br> </div></div></blockquote></div><br></div>