<div dir="ltr"><div>We need more animations for this kind of stuff:</div><div><br></div> <a href="http://yinwang0.wordpress.com/2012/04/09/reinvent-y">http://yinwang0.wordpress.com/2012/04/09/reinvent-y</a><br><div><br></div>
<div><br></div><div><br></div></div><div class="gmail_extra"><br clear="all"><div>-- Yin<br></div>
<br><br><div class="gmail_quote">On Thu, Feb 6, 2014 at 7:24 AM, Matthew Johnson <span dir="ltr"><<a href="mailto:mcooganj@gmail.com" target="_blank">mcooganj@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">Hi scheme experts, <div><br></div><div>My question is really a plea for someone to fill in the gaps in a derivation of the Y combinator. <br><div><br></div><div>With some effort i've (mostly) understood the explanation of how an anonymous function might call itself in the following post:<br>
</div><div><br></div><div><a href="http://www.catonmat.net/blog/derivation-of-ycombinator/" target="_blank">http://www.catonmat.net/blog/derivation-of-ycombinator/</a><br></div><div><br></div><div>At this point, i understand how </div>
<div>
<br></div><div><pre style="font-size:13px;margin-right:1em;margin-left:1em;padding:1em;border:1px solid rgb(204,204,204);font-family:'Courier New',Courier,monospace;vertical-align:baseline;background-color:rgb(255,247,240);line-height:1.3em;overflow:auto">
<span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">((</span><span style="margin:0px;padding:0px;border:0px;font-weight:bold;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(0,136,0)">lambda </span><span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">(</span><span style="margin:0px;padding:0px;border:0px;font-weight:bold;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(0,102,187)">mk-length</span><span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">)</span>
<span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">(</span><span style="margin:0px;padding:0px;border:0px;font-weight:bold;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(0,102,187)">mk-length</span> <span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(51,102,153)">mk-length</span><span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">))</span>
<span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">(</span><span style="margin:0px;padding:0px;border:0px;font-weight:bold;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(0,136,0)">lambda </span><span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">(</span><span style="margin:0px;padding:0px;border:0px;font-weight:bold;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(0,102,187)">mk-length</span><span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">)</span>
<span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">(</span><span style="margin:0px;padding:0px;border:0px;font-weight:bold;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(0,136,0)">lambda </span><span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">(</span><span style="margin:0px;padding:0px;border:0px;font-weight:bold;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(0,102,187)">list</span><span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">)</span>
<span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">(</span><span style="margin:0px;padding:0px;border:0px;font-weight:bold;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(0,102,187)">cond</span>
<span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">((</span><span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(0,51,136)">null? </span><span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(51,102,153)">list</span><span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">)</span> <span style="margin:0px;padding:0px;border:0px;font-weight:bold;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(0,0,221)">0</span><span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">)</span>
<span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">(</span><span style="margin:0px;padding:0px;border:0px;font-weight:bold;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(0,102,187)">else</span>
<span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">(</span><span style="margin:0px;padding:0px;border:0px;font-weight:bold;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(0,102,187)">add1</span> <span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">((</span><span style="margin:0px;padding:0px;border:0px;font-weight:bold;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(0,102,187)">mk-length</span> <span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(51,102,153)">mk-length</span><span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">)</span> <span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">(</span><span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(0,51,136)">cdr </span><span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline;color:rgb(51,102,153)">list</span><span style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">))))))))</span></pre>
</div><div><br></div><div>generates the naive lambda length function with a re-generator (kernel?) as a result of (mk-length mk-length) being in the function place in the recursion. <br></div></div><div><br></div><div>However once we step toward the derivation of the Y-combinator, i get lost. There are two changes that just appear (without motivation or explanation). </div>
<div><br></div><div>Foremost, the below seems to be missing a paren -- and as i'm not sure what problem it's supposed to solve, i'm not sure where it ought to be placed? Also, i'm not sure why length has re-appeared, after we replaced them all with mk-length (with some effort) in a prior step? </div>
<div><br><span style="font-family:'Courier New',Courier,monospace;font-size:13px;line-height:16.899999618530273px;white-space:pre-wrap;background-color:rgb(255,247,240)">((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
</span><strong style="font-family:'Courier New',Courier,monospace;font-size:13px;line-height:16.899999618530273px;white-space:pre-wrap">((lambda (length)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (length (cdr list)))))))</strong><span style="font-family:'Courier New',Courier,monospace;font-size:13px;line-height:16.899999618530273px;white-space:pre-wrap;background-color:rgb(255,247,240)">
(lambda (x)
((mk-length mk-length) x)))))</span><br></div><div><br></div><div>My guess is that `lambda(x) ((mk-length mk-length) x)` is supposed to go in the length position in `(add1 (length (cdr list)))` -- is this correct? </div>
<div><br></div><div>Finally, as i don't understand the prior step, i'm struggling with the appearance of (lambda (le) ... in the subsequent step</div><div><br></div><div><pre style="margin-right:1em;margin-left:1em;padding:1em;border:1px solid rgb(204,204,204);font-size:13px;font-family:'Courier New',Courier,monospace;vertical-align:baseline;background-color:rgb(255,247,240);line-height:1.3em;overflow:auto">
((lambda (le)
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(le (lambda (x)
((mk-length mk-length) x))))))
<strong>(lambda (length)
(lambda (list)
(cond
((null? list) 0)
(else
(add1 (length (cdr list))))))))</strong></pre></div><div>The fact that i cannot see where the paren goes shows that i don't yet _really_ get it yet -- hopefully with some help i'll make the final steps. </div>
<div><br></div><div>thanks in anticipation. </div><span class="HOEnZb"><font color="#888888"><div><br></div><div>mj</div></font></span></div>
<br>____________________<br>
Racket Users list:<br>
<a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a><br>
<br></blockquote></div><br></div>