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 &quot;normal-order&quot; and not &quot;applicative-order&quot; 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">&lt;<a href="mailto:matthias@ccs.neu.edu">matthias@ccs.neu.edu</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<br>
SICP&#39;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&#39;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>
&gt; I&#39;ll hijack the thread since I&#39;ve been meaning to ask about the Y combinator.<br>
&gt; From SICP I&#39;ve seen that the Y combinator is the function<br>
&gt; (define (y f)<br>
&gt;   ((lambda (x) (f (x x)))<br>
&gt;    (lambda (x) (f (x x)))))<br>
&gt;<br>
&gt; This makes mathematical sense, since<br>
&gt; (y f)<br>
&gt; = ((lambda (x) (f (x x))) (lambda (x) (f (x x))))<br>
&gt; = (f ((lambda (x) (f (x x))) (lambda (x) (f (x x)))))<br>
&gt; = (f (y f))<br>
&gt;<br>
&gt; But when actually applying it:<br>
&gt; // g improves a function to get a ceiling function. The fixed point would be similar to (lambda (x) (inexact-&gt;exact (ceiling x)))<br>
&gt; (define (g f)<br>
&gt;   (lambda (x)<br>
&gt;     (if (&lt;= x 0)<br>
&gt;         0<br>
&gt;         (+ 1 (f (- x 1))))))<br>
&gt;<br>
&gt; &gt; ((g (g (g (g (g #f))))) 3.3)<br>
&gt; 4<br>
&gt;<br>
&gt; Now let&#39;s step through<br>
&gt; ((y g) 3.3)<br>
&gt; = (((lambda (x) (g (x x))) (lambda (x) (g (x x)))) 3.3)<br>
&gt; = ((g ((lambda (x) (g (x x))) (lambda (x) (g (x x))))) 3.3)<br>
&gt; now, to get the (g ...) result we need to apply g to it&#39;s operand. For that, we need to evaluate it:<br>
&gt; = ((g (g ((lambda (x) (g (x x))) (lambda (x) (g (x x)))))) 3.3)<br>
&gt; = ((g (g (g ((lambda (x) (g (x x))) (lambda (x) (g (x x)))))))) 3.3)<br>
&gt; = ((g (g (g (g ((lambda (x) (g (x x))) (lambda (x) (g (x x))))))))) 3.3)<br>
&gt;<br>
&gt; And I just ran out of memory.<br>
&gt;<br>
&gt; What am I missing here?<br>
&gt; It seems obvious to me that if we add a delay/force or somesuch thing it solves the problem. But that&#39;s not the y-combinator I was shown.<br>
</div></div><div><div></div><div class="h5">&gt; _________________________________________________<br>
&gt;  For list-related administrative tasks:<br>
&gt;  <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>