<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/">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 class="" style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">((</span><span class="" 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 class="" style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">(</span><span class="" 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 class="" style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">)</span>
   <span class="" style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">(</span><span class="" 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 class="" 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 class="" style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">))</span>
 <span class="" style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">(</span><span class="" 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 class="" style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">(</span><span class="" 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 class="" style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">)</span>
   <span class="" style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">(</span><span class="" 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 class="" style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">(</span><span class="" 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 class="" style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">)</span>
     <span class="" style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">(</span><span class="" 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 class="" style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">((</span><span class="" 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 class="" 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 class="" style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">)</span> <span class="" 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 class="" style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">)</span>
       <span class="" style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">(</span><span class="" 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 class="" style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">(</span><span class="" 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 class="" style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">((</span><span class="" 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 class="" 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 class="" style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">)</span> <span class="" style="margin:0px;padding:0px;border:0px;font-weight:inherit;font-style:inherit;font-family:inherit;vertical-align:baseline">(</span><span class="" 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 class="" 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 class="" 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 class=""><span style="font-family:'Courier New',Courier,monospace;font-size:13px;line-height:16.899999618530273px;white-space:pre;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">((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;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><div><br></div><div>mj</div></div>