I'll hijack the thread since I've been meaning to ask about the Y combinator.<div>From SICP I've seen that the Y combinator is the function</div><div><font class="Apple-style-span" face="'courier new', monospace">(define (y f)</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> ((lambda (x) (f (x x)))</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> (lambda (x) (f (x x)))))</font></div>
<div><br></div><div>This makes mathematical sense, since</div><div><font class="Apple-style-span" face="'courier new', monospace">(y f)</font></div><div><font class="Apple-style-span" face="'courier new', monospace">= ((lambda (x) (f (x x))) (lambda (x) (f (x x))))</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace">= (f ((lambda (x) (f (x x))) (lambda (x) (f (x x)))))</font></div><div><font class="Apple-style-span" face="'courier new', monospace">= (f (y f))</font></div>
<div><br></div><div>But when actually applying it:</div><div>// g improves a function to get a ceiling function. The fixed point would be similar to (lambda (x) (inexact->exact (ceiling x)))</div><div><div>(define (g f)</div>
<div> (lambda (x)</div><div> (if (<= x 0)</div><div> 0</div><div> (+ 1 (f (- x 1))))))</div></div><div><br></div><div>> ((g (g (g (g (g #f))))) 3.3)</div><div>4</div><div><br></div><div>Now let's step through</div>
<div>((y g) 3.3)</div><div>= (((lambda (x) (g (x x))) (lambda (x) (g (x x)))) 3.3)</div><div>= ((g ((lambda (x) (g (x x))) (lambda (x) (g (x x))))) 3.3)</div><div>now, to get the (g ...) result we need to apply g to it's operand. For that, we need to evaluate it:</div>
<div>= ((g (g ((lambda (x) (g (x x))) (lambda (x) (g (x x)))))) 3.3)</div><div>= ((g (g (g ((lambda (x) (g (x x))) (lambda (x) (g (x x)))))))) 3.3)</div><div>= ((g (g (g (g ((lambda (x) (g (x x))) (lambda (x) (g (x x))))))))) 3.3)</div>
<div><br></div><div>And I just ran out of memory.</div><div><br></div><div>What am I missing here?</div><div>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.</div>