ZelphirKaltstahl
/
the-little-schemer


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659
							<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="English" xml:lang="English">
<head>
<!-- 2020-08-23 So 13:46 -->
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>The Little Schemer Notes</title>
<meta name="generator" content="Org mode" />
<meta name="author" content="Zelphir Kaltstahl" />
<style type="text/css">
 <!--/*--><![CDATA[/*><!--*/
  .title  { text-align: center;
             margin-bottom: .2em; }
  .subtitle { text-align: center;
              font-size: medium;
              font-weight: bold;
              margin-top:0; }
  .todo   { font-family: monospace; color: red; }
  .done   { font-family: monospace; color: green; }
  .priority { font-family: monospace; color: orange; }
  .tag    { background-color: #eee; font-family: monospace;
            padding: 2px; font-size: 80%; font-weight: normal; }
  .timestamp { color: #bebebe; }
  .timestamp-kwd { color: #5f9ea0; }
  .org-right  { margin-left: auto; margin-right: 0px;  text-align: right; }
  .org-left   { margin-left: 0px;  margin-right: auto; text-align: left; }
  .org-center { margin-left: auto; margin-right: auto; text-align: center; }
  .underline { text-decoration: underline; }
  #postamble p, #preamble p { font-size: 90%; margin: .2em; }
  p.verse { margin-left: 3%; }
  pre {
    border: 1px solid #ccc;
    box-shadow: 3px 3px 3px #eee;
    padding: 8pt;
    font-family: monospace;
    overflow: auto;
    margin: 1.2em;
  }
  pre.src {
    position: relative;
    overflow: visible;
    padding-top: 1.2em;
  }
  pre.src:before {
    display: none;
    position: absolute;
    background-color: white;
    top: -10px;
    right: 10px;
    padding: 3px;
    border: 1px solid black;
  }
  pre.src:hover:before { display: inline;}
  /* Languages per Org manual */
  pre.src-asymptote:before { content: 'Asymptote'; }
  pre.src-awk:before { content: 'Awk'; }
  pre.src-C:before { content: 'C'; }
  /* pre.src-C++ doesn't work in CSS */
  pre.src-clojure:before { content: 'Clojure'; }
  pre.src-css:before { content: 'CSS'; }
  pre.src-D:before { content: 'D'; }
  pre.src-ditaa:before { content: 'ditaa'; }
  pre.src-dot:before { content: 'Graphviz'; }
  pre.src-calc:before { content: 'Emacs Calc'; }
  pre.src-emacs-lisp:before { content: 'Emacs Lisp'; }
  pre.src-fortran:before { content: 'Fortran'; }
  pre.src-gnuplot:before { content: 'gnuplot'; }
  pre.src-haskell:before { content: 'Haskell'; }
  pre.src-hledger:before { content: 'hledger'; }
  pre.src-java:before { content: 'Java'; }
  pre.src-js:before { content: 'Javascript'; }
  pre.src-latex:before { content: 'LaTeX'; }
  pre.src-ledger:before { content: 'Ledger'; }
  pre.src-lisp:before { content: 'Lisp'; }
  pre.src-lilypond:before { content: 'Lilypond'; }
  pre.src-lua:before { content: 'Lua'; }
  pre.src-matlab:before { content: 'MATLAB'; }
  pre.src-mscgen:before { content: 'Mscgen'; }
  pre.src-ocaml:before { content: 'Objective Caml'; }
  pre.src-octave:before { content: 'Octave'; }
  pre.src-org:before { content: 'Org mode'; }
  pre.src-oz:before { content: 'OZ'; }
  pre.src-plantuml:before { content: 'Plantuml'; }
  pre.src-processing:before { content: 'Processing.js'; }
  pre.src-python:before { content: 'Python'; }
  pre.src-R:before { content: 'R'; }
  pre.src-ruby:before { content: 'Ruby'; }
  pre.src-sass:before { content: 'Sass'; }
  pre.src-scheme:before { content: 'Scheme'; }
  pre.src-screen:before { content: 'Gnu Screen'; }
  pre.src-sed:before { content: 'Sed'; }
  pre.src-sh:before { content: 'shell'; }
  pre.src-sql:before { content: 'SQL'; }
  pre.src-sqlite:before { content: 'SQLite'; }
  /* additional languages in org.el's org-babel-load-languages alist */
  pre.src-forth:before { content: 'Forth'; }
  pre.src-io:before { content: 'IO'; }
  pre.src-J:before { content: 'J'; }
  pre.src-makefile:before { content: 'Makefile'; }
  pre.src-maxima:before { content: 'Maxima'; }
  pre.src-perl:before { content: 'Perl'; }
  pre.src-picolisp:before { content: 'Pico Lisp'; }
  pre.src-scala:before { content: 'Scala'; }
  pre.src-shell:before { content: 'Shell Script'; }
  pre.src-ebnf2ps:before { content: 'ebfn2ps'; }
  /* additional language identifiers per "defun org-babel-execute"
       in ob-*.el */
  pre.src-cpp:before  { content: 'C++'; }
  pre.src-abc:before  { content: 'ABC'; }
  pre.src-coq:before  { content: 'Coq'; }
  pre.src-groovy:before  { content: 'Groovy'; }
  /* additional language identifiers from org-babel-shell-names in
     ob-shell.el: ob-shell is the only babel language using a lambda to put
     the execution function name together. */
  pre.src-bash:before  { content: 'bash'; }
  pre.src-csh:before  { content: 'csh'; }
  pre.src-ash:before  { content: 'ash'; }
  pre.src-dash:before  { content: 'dash'; }
  pre.src-ksh:before  { content: 'ksh'; }
  pre.src-mksh:before  { content: 'mksh'; }
  pre.src-posh:before  { content: 'posh'; }
  /* Additional Emacs modes also supported by the LaTeX listings package */
  pre.src-ada:before { content: 'Ada'; }
  pre.src-asm:before { content: 'Assembler'; }
  pre.src-caml:before { content: 'Caml'; }
  pre.src-delphi:before { content: 'Delphi'; }
  pre.src-html:before { content: 'HTML'; }
  pre.src-idl:before { content: 'IDL'; }
  pre.src-mercury:before { content: 'Mercury'; }
  pre.src-metapost:before { content: 'MetaPost'; }
  pre.src-modula-2:before { content: 'Modula-2'; }
  pre.src-pascal:before { content: 'Pascal'; }
  pre.src-ps:before { content: 'PostScript'; }
  pre.src-prolog:before { content: 'Prolog'; }
  pre.src-simula:before { content: 'Simula'; }
  pre.src-tcl:before { content: 'tcl'; }
  pre.src-tex:before { content: 'TeX'; }
  pre.src-plain-tex:before { content: 'Plain TeX'; }
  pre.src-verilog:before { content: 'Verilog'; }
  pre.src-vhdl:before { content: 'VHDL'; }
  pre.src-xml:before { content: 'XML'; }
  pre.src-nxml:before { content: 'XML'; }
  /* add a generic configuration mode; LaTeX export needs an additional
     (add-to-list 'org-latex-listings-langs '(conf " ")) in .emacs */
  pre.src-conf:before { content: 'Configuration File'; }

  table { border-collapse:collapse; }
  caption.t-above { caption-side: top; }
  caption.t-bottom { caption-side: bottom; }
  td, th { vertical-align:top;  }
  th.org-right  { text-align: center;  }
  th.org-left   { text-align: center;   }
  th.org-center { text-align: center; }
  td.org-right  { text-align: right;  }
  td.org-left   { text-align: left;   }
  td.org-center { text-align: center; }
  dt { font-weight: bold; }
  .footpara { display: inline; }
  .footdef  { margin-bottom: 1em; }
  .figure { padding: 1em; }
  .figure p { text-align: center; }
  .equation-container {
    display: table;
    text-align: center;
    width: 100%;
  }
  .equation {
    vertical-align: middle;
  }
  .equation-label {
    display: table-cell;
    text-align: right;
    vertical-align: middle;
  }
  .inlinetask {
    padding: 10px;
    border: 2px solid gray;
    margin: 10px;
    background: #ffffcc;
  }
  #org-div-home-and-up
   { text-align: right; font-size: 70%; white-space: nowrap; }
  textarea { overflow-x: auto; }
  .linenr { font-size: smaller }
  .code-highlighted { background-color: #ffff00; }
  .org-info-js_info-navigation { border-style: none; }
  #org-info-js_console-label
    { font-size: 10px; font-weight: bold; white-space: nowrap; }
  .org-info-js_search-highlight
    { background-color: #ffff00; color: #000000; font-weight: bold; }
  .org-svg { width: 90%; }
  /*]]>*/-->
</style>
<script type="text/javascript">
/*
@licstart  The following is the entire license notice for the
JavaScript code in this tag.

Copyright (C) 2012-2020 Free Software Foundation, Inc.

The JavaScript code in this tag is free software: you can
redistribute it and/or modify it under the terms of the GNU
General Public License (GNU GPL) as published by the Free Software
Foundation, either version 3 of the License, or (at your option)
any later version.  The code is distributed WITHOUT ANY WARRANTY;
without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE.  See the GNU GPL for more details.

As additional permission under GNU GPL version 3 section 7, you
may distribute non-source (e.g., minimized or compacted) forms of
that code without the copy of the GNU GPL normally required by
section 4, provided you include this license notice and a URL
through which recipients can access the Corresponding Source.


@licend  The above is the entire license notice
for the JavaScript code in this tag.
*/
<!--/*--><![CDATA[/*><!--*/
 function CodeHighlightOn(elem, id)
 {
   var target = document.getElementById(id);
   if(null != target) {
     elem.cacheClassElem = elem.className;
     elem.cacheClassTarget = target.className;
     target.className = "code-highlighted";
     elem.className   = "code-highlighted";
   }
 }
 function CodeHighlightOff(elem, id)
 {
   var target = document.getElementById(id);
   if(elem.cacheClassElem)
     elem.className = elem.cacheClassElem;
   if(elem.cacheClassTarget)
     target.className = elem.cacheClassTarget;
 }
/*]]>*///-->
</script>
</head>
<body>
<div id="content">
<h1 class="title">The Little Schemer Notes
<br />
<span class="subtitle">The Y-combinator</span>
</h1>
<div id="table-of-contents">
<h2>Table of Contents</h2>
<div id="text-table-of-contents">
<ul>
<li><a href="#orga967236">1. Y-combinator</a></li>
<li><a href="#orga4b2d59">2. Prerequisites</a></li>
<li><a href="#org8fb4a52">3. Code</a>
<ul>
<li><a href="#orgc9f88ae">3.1. Writing <code>length-0</code></a></li>
<li><a href="#org3ad5eb7">3.2. Endless inlining of <code>length-0</code></a></li>
<li><a href="#orgf016cff">3.3. Creating <code>length-0</code></a></li>
<li><a href="#orgafbe3a5">3.4. Creating <code>length-1</code> and <code>length-2</code></a></li>
<li><a href="#org50da4be">3.5. Refactoring out the repeating part - making <code>length</code></a></li>
<li><a href="#orgb7ac798">3.6. Making all kinds of recursive procedures</a></li>
<li><a href="#org6e74d52">3.7. Separating the Y-combinator</a></li>
</ul>
</li>
<li><a href="#orgede3d6b">4. Final words</a></li>
</ul>
</div>
</div>

<div id="outline-container-orga967236" class="outline-2">
<h2 id="orga967236"><span class="section-number-2">1</span> Y-combinator</h2>
<div class="outline-text-2" id="text-1">
<p>
The following is a way to get to the so called Y-combinator. It is a thought experiment assuming, that we have no <code>define</code> form available and are trying to implement the function <code>length</code> for lists without making use of <code>define</code>. In the end a way will be found. This way is the Y-combinator, a function, which can turn a function <i>f</i> into a function <i>f-wrap</i>, which applies <i>f</i> again and again, as required by the nature of its input to recursively consume all of the input. Since no <code>define</code> form is used anywhere to write the Y-combinator, the body of the Y-combinator cannot refer to any definitions, except for names of values in respective scopes. This property enables the Y-combinator to implement recursion in a programming language, which does not support recursion natively, as long as it has lambda expressions, function application and (not 100% sure it is required) lexical scope. If a language forbids calling a procedure from within itself, then the Y-combinator is still valid code, as it does not do so. It in turn can produce an <i>f-wrap</i>, which will apply an <i>f</i> over and over again, creating the same effect, as if <i>f</i> was recursive itself. To deny the use of the <code>define</code> form actually is intentionally done in the book, because then only the Y-combinator or something with the properties of the Y-combinator can help us solve the problem.
</p>

<p>
On the way there, a few common refactoring steps or equivalent transformations for code are applied. Those are the following:
</p>

<ol class="org-ol">
<li>inlining an implementation of a function where the call to it is made</li>
<li>lambda wrapping of lambda expressions (explained when used)
<ol class="org-ol">
<li>for pulling out parts of the code and making them arguments</li>
<li>for delaying evaluation of expressions</li>
</ol></li>
</ol>

<p>
Furthermore we make use of:
</p>

<ol class="org-ol">
<li>immeditately invoked functions</li>
</ol>
</div>
</div>

<div id="outline-container-orga4b2d59" class="outline-2">
<h2 id="orga4b2d59"><span class="section-number-2">2</span> Prerequisites</h2>
<div class="outline-text-2" id="text-2">
<p>
Prerequisites contain code, which is needed to run examples, but is not given in the same chapter.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org4aa79f7">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">length</span>
  (<span style="color: #9FCA56;">lambda</span> (lst)
    (<span style="color: #9FCA56;">cond</span>
     [(null? lst) 0]
     [<span style="color: #9FCA56;">else</span> (+ (length (cdr lst)) 1)])))

(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">eternity</span>
  (<span style="color: #9FCA56;">lambda</span> (something)
    (eternity something)))
</pre>
</div>
</div>
</div>

<div id="outline-container-org8fb4a52" class="outline-2">
<h2 id="org8fb4a52"><span class="section-number-2">3</span> Code</h2>
<div class="outline-text-2" id="text-3">
<p>
The whole example works with the length function, so to start, here is the length function as usually defined for lists:
</p>

<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">length</span>
  (<span style="color: #9FCA56;">lambda</span> (lst)
    (<span style="color: #9FCA56;">cond</span>
     [(null? lst) 0]
     [<span style="color: #9FCA56;">else</span> (+ (length (cdr lst)) 1)])))
</pre>
</div>

<p>
We can try it out:
</p>

<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">length</span>
  (<span style="color: #9FCA56;">lambda</span> (lst)
    (<span style="color: #9FCA56;">cond</span>
     [(null? lst) 0]
     [<span style="color: #9FCA56;">else</span> (+ (length (cdr lst)) 1)])))

(display (simple-format #f <span style="color: #55B5DB;">"~a\n"</span> (length '(1 2 3 4 5 6))))
(display (simple-format #f <span style="color: #55B5DB;">"~a\n"</span> (length '(1 2 3 4 5 (6)))))
</pre>
</div>

<pre class="example">
6
6
</pre>


<p>
There is a problem however. <code>length</code> refers to itself in its definition. In a programming language, which does not support recursion, this would not be possible. If we do not make use of <code>define</code>, then there is no way for length to directly refer to itself, as it is not bound to a name. So how could we write <code>length</code>, without referring to itself?
</p>
</div>

<div id="outline-container-orgc9f88ae" class="outline-3">
<h3 id="orgc9f88ae"><span class="section-number-3">3.1</span> Writing <code>length-0</code></h3>
<div class="outline-text-3" id="text-3-1">
<p>
To start figuring out the solution, we write <code>length-0</code>, which calculates the length of the empty list, but does not return a value (gets stuck) for any list that contains elements:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgc2e8854">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">eternity</span>
  (<span style="color: #9FCA56;">lambda</span> (something)
    (eternity something)))

(<span style="color: #9FCA56;">lambda</span> (lst)
  (<span style="color: #9FCA56;">cond</span>
   [(null? lst) 0]
   [<span style="color: #9FCA56;">else</span> (+ 1 (eternity (cdr lst)))]))
</pre>
</div>

<p>
This does not recur on itself. It does not call itself in the body.
</p>

<p>
Using this as a starting point, we then try to get back our original <code>length</code> functionality.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgb28defa">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">eternity</span>
  (<span style="color: #9FCA56;">lambda</span> (something)
    (eternity something)))

(<span style="color: #9FCA56;">lambda</span> (lst)
  (<span style="color: #9FCA56;">cond</span>
   [(null? lst) 0]
   [<span style="color: #9FCA56;">else</span> (+ 1 (eternity (cdr lst)))]))

<span style="color: #75715E;">;; </span><span style="color: #41535B;">do not try for non-empty lists</span>
<span style="color: #75715E;">;; </span><span style="color: #41535B;">(display</span>
<span style="color: #75715E;">;;  </span><span style="color: #41535B;">(simple-format</span>
<span style="color: #75715E;">;;   </span><span style="color: #41535B;">#f "~a\n"</span>
<span style="color: #75715E;">;;   </span><span style="color: #41535B;">((lambda (lst)</span>
<span style="color: #75715E;">;;      </span><span style="color: #41535B;">(cond</span>
<span style="color: #75715E;">;;       </span><span style="color: #41535B;">[(null? lst) 0]</span>
<span style="color: #75715E;">;;       </span><span style="color: #41535B;">[else (+ 1 (eternity (cdr lst)))]))</span>
<span style="color: #75715E;">;;    </span><span style="color: #41535B;">'(1 2 3))))</span>

(display
 (simple-format
  #f <span style="color: #55B5DB;">"~a\n"</span>
  ((<span style="color: #9FCA56;">lambda</span> (lst)
     (<span style="color: #9FCA56;">cond</span>
      [(null? lst) 0]
      [<span style="color: #9FCA56;">else</span> (+ 1 (eternity (cdr lst)))]))
   '())))
</pre>
</div>

<pre class="example">
0
</pre>


<p>
OK, this works for the empty list.
</p>
</div>
</div>

<div id="outline-container-org3ad5eb7" class="outline-3">
<h3 id="org3ad5eb7"><span class="section-number-3">3.2</span> Endless inlining of <code>length-0</code></h3>
<div class="outline-text-3" id="text-3-2">
<p>
From <code>length-0</code>, we can create a function for calculating the length of a list with 1 element or the empty list by replacing the <code>else</code> branch with <code>length-0</code> itself. As the case of the empty list is handled in the first branch, the else branch would then handle the case of the list having one element. This works because we give the <code>cdr</code> of the list, which will be the empty list again, as an argument to the <code>length-0</code> in the <code>else</code> branch:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org7f3bd33">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">eternity</span>
  (<span style="color: #9FCA56;">lambda</span> (something)
    (eternity something)))

(<span style="color: #9FCA56;">lambda</span> (lst)
  (<span style="color: #9FCA56;">cond</span>
   [(null? lst) 0]
   [<span style="color: #9FCA56;">else</span> (+ 1
            <span style="color: #75715E;">;; </span><span style="color: #41535B;">We insert length-0 here.</span>
            ((<span style="color: #9FCA56;">lambda</span> (lst)
               (<span style="color: #9FCA56;">cond</span>
                [(null? lst) 0]
                <span style="color: #75715E;">;; </span><span style="color: #41535B;">If there are more elements then 1, the function will still not return a value.</span>
                [<span style="color: #9FCA56;">else</span> (+ 1 (eternity (cdr lst)))]))
             <span style="color: #75715E;">;; </span><span style="color: #41535B;">length-0 will be applied to the cdr of the list</span>
             (cdr lst)))]))
</pre>
</div>

<p>
Let's try it out:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgc9adfbf">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">eternity</span>
  (<span style="color: #9FCA56;">lambda</span> (something)
    (eternity something)))

<span style="color: #75715E;">;; </span><span style="color: #41535B;">do not try this</span>
<span style="color: #41535B;">#;(display</span>
<span style="color: #41535B;"> (simple-format</span>
<span style="color: #41535B;">  #f "~a\n"</span>
<span style="color: #41535B;">  ((lambda (lst)</span>
<span style="color: #41535B;">     (cond</span>
<span style="color: #41535B;">      [(null? lst) 0]</span>
<span style="color: #41535B;">      [else (+ 1</span>
<span style="color: #41535B;">               ((lambda (lst)</span>
<span style="color: #41535B;">                  (cond</span>
<span style="color: #41535B;">                   [(null? lst) 0]</span>
<span style="color: #41535B;">                   [else (+ 1 (eternity (cdr lst)))]))</span>
<span style="color: #41535B;">                (cdr lst)))]))</span>
<span style="color: #41535B;">   '(a b))))</span>

(display
 (simple-format
  #f <span style="color: #55B5DB;">"~a\n"</span>
  ((<span style="color: #9FCA56;">lambda</span> (lst)
     (<span style="color: #9FCA56;">cond</span>
      [(null? lst) 0]
      [<span style="color: #9FCA56;">else</span> (+ 1
               ((<span style="color: #9FCA56;">lambda</span> (lst)
                  (<span style="color: #9FCA56;">cond</span>
                   [(null? lst) 0]
                   [<span style="color: #9FCA56;">else</span> (+ 1 (eternity (cdr lst)))]))
                (cdr lst)))]))
   '())))

(display
 (simple-format
  #f <span style="color: #55B5DB;">"~a\n"</span>
  ((<span style="color: #9FCA56;">lambda</span> (lst)
     (<span style="color: #9FCA56;">cond</span>
      [(null? lst) 0]
      [<span style="color: #9FCA56;">else</span> (+ 1
               ((<span style="color: #9FCA56;">lambda</span> (lst)
                  (<span style="color: #9FCA56;">cond</span>
                   [(null? lst) 0]
                   [<span style="color: #9FCA56;">else</span> (+ 1 (eternity (cdr lst)))]))
                (cdr lst)))]))
   '(a))))
</pre>
</div>

<p>
Our function now works for the list lenghts 0 and 1. Great. We can continue nesting deeper, to get to any length we want. For example we can replace the call to <code>eternity</code> again, in order to achieve a function, which can deal with lists up to length 2 as follows:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org3d5043e">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">eternity</span>
  (<span style="color: #9FCA56;">lambda</span> (something)
    (eternity something)))

(<span style="color: #9FCA56;">lambda</span> (lst)
  (<span style="color: #9FCA56;">cond</span>
   [(null? lst) 0]
   [<span style="color: #9FCA56;">else</span> (+ 1
            ((<span style="color: #9FCA56;">lambda</span> (lst)
               (<span style="color: #9FCA56;">cond</span>
                [(null? lst) 0]
                [<span style="color: #9FCA56;">else</span> (+ 1
                         <span style="color: #75715E;">;; </span><span style="color: #41535B;">We insert length-0 here.</span>
                         ((<span style="color: #9FCA56;">lambda</span> (lst)
                            (<span style="color: #9FCA56;">cond</span>
                             [(null? lst) 0]
                             [<span style="color: #9FCA56;">else</span> (+ 1 (eternity (cdr lst)))]))
                          (cdr lst)))]))
             (cdr lst)))]))
</pre>
</div>

<p>
And a little test:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org5225ea2">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">eternity</span>
  (<span style="color: #9FCA56;">lambda</span> (something)
    (eternity something)))

(display
 (simple-format
  #f <span style="color: #55B5DB;">"~a\n"</span>
  ((<span style="color: #9FCA56;">lambda</span> (lst)
     (<span style="color: #9FCA56;">cond</span>
      [(null? lst) 0]
      [<span style="color: #9FCA56;">else</span> (+ 1
               ((<span style="color: #9FCA56;">lambda</span> (lst)
                  (<span style="color: #9FCA56;">cond</span>
                   [(null? lst) 0]
                   [<span style="color: #9FCA56;">else</span> (+ 1
                            ((<span style="color: #9FCA56;">lambda</span> (lst)
                               (<span style="color: #9FCA56;">cond</span>
                                [(null? lst) 0]
                                [<span style="color: #9FCA56;">else</span> (+ 1 (eternity (cdr lst)))]))
                             (cdr lst)))]))
                (cdr lst)))]))
   '(a b))))
</pre>
</div>

<pre class="example">
2
</pre>


<p>
Yep, it still works.
</p>

<p>
This way of proceeding by inlining <code>length-0</code> over and over again, although working correctly, seems not practical at all. We cannot anticipate at all times, what length a list we have to deal with will have and in consequence cannot know how to write our <code>length</code> function. Furthermore, this makes for very unreadable and very long code, only to have a function <code>length</code>. Using this is not feasible.
</p>

<p>
We have to ask ourselves, how we could avoid having to inline the code of <code>length-0</code> manually. This will involve multiple steps.
</p>
</div>
</div>

<div id="outline-container-orgf016cff" class="outline-3">
<h3 id="orgf016cff"><span class="section-number-3">3.3</span> Creating <code>length-0</code></h3>
<div class="outline-text-3" id="text-3-3">
<p>
First, we can write a procedure, which creates <code>length-0</code> for us:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgb4186dd">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">eternity</span>
  (<span style="color: #9FCA56;">lambda</span> (something)
    (eternity something)))

((<span style="color: #9FCA56;">lambda</span> (length)
   (<span style="color: #9FCA56;">lambda</span> (lst)
     (<span style="color: #9FCA56;">cond</span>
      [(null? lst) 0]
      [<span style="color: #9FCA56;">else</span> (+ 1 (length (cdr lst)))])))
 eternity)
</pre>
</div>

<p>
All we did here is to wrap <code>length-0</code> with a lambda and make that lambda take one argument, a procedure, which is used in place of the call to <code>eternity</code>. To get back <code>length-0</code>, we need to pass in <code>eternity</code>, so that it gets back inside <code>length-0</code>, where it will be called. (In foresight the argument is named <code>length</code>, but it could really have any name.)
</p>

<p>
Let us call this equivalent transformation <i>lambda wrapping</i>. To generalize, it is always possible to wrap one lambda with another lambda this way, making one or more bindings come from the outer scope, where they are passed in, to get an equivalent lambda. This is formulated in the following code:
</p>

<div class="org-src-container">
<label class="org-src-name"><span class="listing-number">Listing 1: </span>equivalent transformation: lambda wrapping</label><pre class="src src-scheme" id="org3f368e2">(<span style="color: #9FCA56;">&#955;</span> (sth) (proc sth))

<span style="color: #75715E;">;; </span><span style="color: #41535B;">is equivalent to</span>

((<span style="color: #9FCA56;">&#955;</span> (arg)
   (<span style="color: #9FCA56;">&#955;</span> (sth) (arg sth)))
 proc)
</pre>
</div>

<p>
This is how we can create <code>length-0</code>. Let us try to create <code>length-1</code> and <code>length-2</code> the same way and a pattern will emerge.
</p>
</div>
</div>

<div id="outline-container-orgafbe3a5" class="outline-3">
<h3 id="orgafbe3a5"><span class="section-number-3">3.4</span> Creating <code>length-1</code> and <code>length-2</code></h3>
<div class="outline-text-3" id="text-3-4">
<p>
Instead of giving the argument <code>eternity</code> to the function, which creates <code>length-0</code>, which will then be called in the <code>else</code> branch, causing the produced <code>length-0</code> to fail, if the list is not empty, we could give <code>length-0</code> as an argument, so that we will have it called in the else branch. This in effect will create <code>length-1</code>, as the function produced will only fail, when it enters the <code>else</code> branch of the argument <code>length-0</code>, as it has a call to <code>eternity</code> there.
</p>

<p>
Let us see this in the following code.
</p>
</div>

<div id="outline-container-org816cc6c" class="outline-4">
<h4 id="org816cc6c"><span class="section-number-4">3.4.1</span> Creating <code>length-1</code></h4>
<div class="outline-text-4" id="text-3-4-1">
<p>
This is the code before giving <code>length-0</code> as an argument, still giving <code>eternity</code> as an argument:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org9548e2a">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">eternity</span>
  (<span style="color: #9FCA56;">lambda</span> (something)
    (eternity something)))

((<span style="color: #9FCA56;">lambda</span> (length)
   (<span style="color: #9FCA56;">lambda</span> (lst)
     (<span style="color: #9FCA56;">cond</span>
      [(null? lst) 0]
      [<span style="color: #9FCA56;">else</span> (+ 1 (length (cdr lst)))])))
 <span style="color: #75715E;">;; </span><span style="color: #41535B;">notice how we give eternity as an argument to produce length-0</span>
 eternity)
</pre>
</div>

<p>
Now we will replace <code>eternity</code> by <code>length-0</code>:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org61703c0">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">eternity</span>
  (<span style="color: #9FCA56;">lambda</span> (something)
    (eternity something)))

((<span style="color: #9FCA56;">lambda</span> (length)
   (<span style="color: #9FCA56;">lambda</span> (lst)
     (<span style="color: #9FCA56;">cond</span>
      [(null? lst) 0]
      [<span style="color: #9FCA56;">else</span> (+ 1 (length (cdr lst)))])))
 <span style="color: #75715E;">;; </span><span style="color: #41535B;">Now we give length-0, as produced by the lambda expression.</span>
 ((<span style="color: #9FCA56;">lambda</span> (length)
    (<span style="color: #9FCA56;">lambda</span> (lst)
      (<span style="color: #9FCA56;">cond</span>
       [(null? lst) 0]
       [<span style="color: #9FCA56;">else</span> (+ 1 (length (cdr lst)))])))
  <span style="color: #75715E;">;; </span><span style="color: #41535B;">eternity will be given to create the argument length-0.</span>
  eternity))
</pre>
</div>

<p>
Instead of giving <code>eternity</code> immediately, <code>eternity</code> is now given as an argument for creating <code>length-0</code>, which in turn will be given as an argument, in order to create <code>length-1</code>.
</p>

<p>
Notice, that we used the identifier <code>length</code> in both lambda expressions. They are however different, separated by scope.
</p>

<p>
Let us try to use this <code>length-1</code> function.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgcb10d23">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">eternity</span>
  (<span style="color: #9FCA56;">lambda</span> (something)
    (eternity something)))

(display
 (simple-format
  #f <span style="color: #55B5DB;">"~a\n"</span>
  <span style="color: #75715E;">;; </span><span style="color: #41535B;">make length-1 and immediately apply it</span>
  (((<span style="color: #9FCA56;">lambda</span> (length)
      (<span style="color: #9FCA56;">lambda</span> (lst)
        (<span style="color: #9FCA56;">cond</span>
         [(null? lst) 0]
         [<span style="color: #9FCA56;">else</span> (+ 1 (length (cdr lst)))])))
    <span style="color: #75715E;">;; </span><span style="color: #41535B;">Now we give length-0, as produced by the lambda expression.</span>
    ((<span style="color: #9FCA56;">lambda</span> (length)
       (<span style="color: #9FCA56;">lambda</span> (lst)
         (<span style="color: #9FCA56;">cond</span>
          [(null? lst) 0]
          [<span style="color: #9FCA56;">else</span> (+ 1 (length (cdr lst)))])))
     <span style="color: #75715E;">;; </span><span style="color: #41535B;">eternity will be given to create the argument length-0.</span>
     eternity))
   '())))

(display
 (simple-format
  #f <span style="color: #55B5DB;">"~a\n"</span>
  <span style="color: #75715E;">;; </span><span style="color: #41535B;">make length-1 and immediately apply it</span>
  (((<span style="color: #9FCA56;">lambda</span> (length)
      (<span style="color: #9FCA56;">lambda</span> (lst)
        (<span style="color: #9FCA56;">cond</span>
         [(null? lst) 0]
         [<span style="color: #9FCA56;">else</span> (+ 1 (length (cdr lst)))])))
    <span style="color: #75715E;">;; </span><span style="color: #41535B;">Now we give length-0, as produced by the lambda expression.</span>
    ((<span style="color: #9FCA56;">lambda</span> (length)
       (<span style="color: #9FCA56;">lambda</span> (lst)
         (<span style="color: #9FCA56;">cond</span>
          [(null? lst) 0]
          [<span style="color: #9FCA56;">else</span> (+ 1 (length (cdr lst)))])))
     <span style="color: #75715E;">;; </span><span style="color: #41535B;">eternity will be given to create the argument length-0.</span>
     eternity))
   '(a))))
</pre>
</div>

<pre class="example">
0
1
</pre>


<p>
It gives the expected result.
</p>
</div>
</div>

<div id="outline-container-org8781102" class="outline-4">
<h4 id="org8781102"><span class="section-number-4">3.4.2</span> Creating <code>length-2</code></h4>
<div class="outline-text-4" id="text-3-4-2">
<p>
Just like we created <code>length-1</code> by giving an on-the-fly produced <code>length-0</code> to the function which originally created <code>length-0</code>, we create <code>length-2</code>, by again replacing the call to <code>eternity</code>, by another <code>length-0</code>, increasing the possible iteration depth of the whole created function again by 1, as the <code>eternity</code> call will happen only in the innermost function, which is produced by creating <code>length-0</code> using <code>eternity</code>.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgfe68f42">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">eternity</span>
  (<span style="color: #9FCA56;">lambda</span> (something)
    (eternity something)))

((<span style="color: #9FCA56;">lambda</span> (length)
   (<span style="color: #9FCA56;">lambda</span> (lst)
     (<span style="color: #9FCA56;">cond</span>
      [(null? lst) 0]
      [<span style="color: #9FCA56;">else</span> (+ 1 (length (cdr lst)))])))
 ((<span style="color: #9FCA56;">lambda</span> (length)
    (<span style="color: #9FCA56;">lambda</span> (lst)
      (<span style="color: #9FCA56;">cond</span>
       [(null? lst) 0]
       [<span style="color: #9FCA56;">else</span> (+ 1 (length (cdr lst)))])))
  <span style="color: #75715E;">;; </span><span style="color: #41535B;">Now we give length-0, as produced by the lambda expression.</span>
  ((<span style="color: #9FCA56;">lambda</span> (length)
     (<span style="color: #9FCA56;">lambda</span> (lst)
       (<span style="color: #9FCA56;">cond</span>
        [(null? lst) 0]
        [<span style="color: #9FCA56;">else</span> (+ 1 (length (cdr lst)))])))
   <span style="color: #75715E;">;; </span><span style="color: #41535B;">eternity will be given to create the argument length-0.</span>
   eternity)))
</pre>
</div>

<p>
We delayed the call of <code>eternity</code> even more, by replacing <code>eternity</code> with another creation of <code>length-0</code>, which in turn does the call to <code>eternity</code>.
</p>

<p>
While the code is not indented as much any longer, there are still repetitions, which are needed for each depth of recursion, so the problem is not yet solved.
</p>
</div>
</div>
</div>

<div id="outline-container-org50da4be" class="outline-3">
<h3 id="org50da4be"><span class="section-number-3">3.5</span> Refactoring out the repeating part - making <code>length</code></h3>
<div class="outline-text-3" id="text-3-5">
<p>
If we could give a name to the repeating part, we could shorten the code a lot. We cannot use <code>define</code> to give a name, but what we <i>can</i> do is to <i>lambda wrap</i> the whole code and give the repeating part as an argument, enabling us to give it a name inside the wrap. We will call it <code>make-length</code> inside the wrap.
</p>

<p>
For <code>length-0</code> we can do it as follows:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org4d3afd6">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">eternity</span>
  (<span style="color: #9FCA56;">lambda</span> (something)
    (eternity something)))

<span style="color: #75715E;">;; </span><span style="color: #41535B;">The wrapping lambda internally applies the given argument (the repeating part) to eternity.</span>
((<span style="color: #9FCA56;">lambda</span> (make-length)
   (make-length eternity))
 <span style="color: #75715E;">;; </span><span style="color: #41535B;">The wrapping lambda is immediately applied to the repeating part,</span>
 (<span style="color: #9FCA56;">lambda</span> (something)
   (<span style="color: #9FCA56;">lambda</span> (lst)
     (<span style="color: #9FCA56;">cond</span>
      [(null? lst) 0]
      <span style="color: #75715E;">;; </span><span style="color: #41535B;">Notice how the repeating part applies `something` to the cdr of the list. `something` will</span>
      <span style="color: #75715E;">;; </span><span style="color: #41535B;">be `eternity` in this case.</span>
      [<span style="color: #9FCA56;">else</span> (+ 1 (something (cdr lst)))]))))
</pre>
</div>

<p>
If this is still <code>length-0</code>, we should be able to use it as such:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org27bddd4">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">eternity</span>
  (<span style="color: #9FCA56;">lambda</span> (something)
    (eternity something)))

(display
 (simple-format
  #f <span style="color: #55B5DB;">"~a\n"</span>
  (((<span style="color: #9FCA56;">lambda</span> (make-length)
      (make-length eternity))
    (<span style="color: #9FCA56;">lambda</span> (something)
      (<span style="color: #9FCA56;">lambda</span> (lst)
        (<span style="color: #9FCA56;">cond</span>
         [(null? lst) 0]
         [<span style="color: #9FCA56;">else</span> (+ 1 (something (cdr lst)))]))))
   <span style="color: #75715E;">;; </span><span style="color: #41535B;">Apply it to the empty list.</span>
   '())))
</pre>
</div>

<p>
As we can see, this still works.
</p>

<p>
Previously, we applied the repreating part to itself. We named it <code>make-length</code> here, so we can implement <code>length-1</code> and <code>length-2</code> by applying <code>make-length</code> to <code>make-length</code> inside the wrap as follows:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgda9a684">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">eternity</span>
  (<span style="color: #9FCA56;">lambda</span> (something)
    (eternity something)))

((<span style="color: #9FCA56;">lambda</span> (make-length)
   (make-length
    <span style="color: #75715E;">;; </span><span style="color: #41535B;">Apply make-length to make-length.</span>
    (make-length eternity)))
 (<span style="color: #9FCA56;">lambda</span> (something)
   (<span style="color: #9FCA56;">lambda</span> (lst)
     (<span style="color: #9FCA56;">cond</span>
      [(null? lst) 0]
      [<span style="color: #9FCA56;">else</span> (+ 1 (something (cdr lst)))]))))
</pre>
</div>

<div class="org-src-container">
<pre class="src src-scheme" id="org9c9e340">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">eternity</span>
  (<span style="color: #9FCA56;">lambda</span> (something)
    (eternity something)))

((<span style="color: #9FCA56;">lambda</span> (make-length)
   <span style="color: #75715E;">;; </span><span style="color: #41535B;">This is length-2.</span>
   (make-length
    <span style="color: #75715E;">;; </span><span style="color: #41535B;">Apply make-length to make-length applied to make-length applied to eternity, which is length-1.</span>
    (make-length
     <span style="color: #75715E;">;; </span><span style="color: #41535B;">Apply make-length to make-length applied to eternity, which is length-0.</span>
     (make-length eternity))))
 (<span style="color: #9FCA56;">lambda</span> (something)
   (<span style="color: #9FCA56;">lambda</span> (lst)
     (<span style="color: #9FCA56;">cond</span>
      [(null? lst) 0]
      [<span style="color: #9FCA56;">else</span> (+ 1 (something (cdr lst)))]))))
</pre>
</div>

<p>
Let us try <code>length-2</code> defined like this:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org9acde36">(<span style="color: #9FCA56;">define</span> <span style="color: #55B5DB;">eternity</span>
  (<span style="color: #9FCA56;">lambda</span> (something)
    (eternity something)))

(display
 (simple-format
  #f <span style="color: #55B5DB;">"~a\n"</span>
  (((<span style="color: #9FCA56;">lambda</span> (make-length)
      (make-length
       (make-length
        (make-length eternity))))
    (<span style="color: #9FCA56;">lambda</span> (something)
      (<span style="color: #9FCA56;">lambda</span> (lst)
        (<span style="color: #9FCA56;">cond</span>
         [(null? lst) 0]
         [<span style="color: #9FCA56;">else</span> (+ 1 (something (cdr lst)))]))))
   <span style="color: #75715E;">;; </span><span style="color: #41535B;">Apply it to the empty list.</span>
   '())))

(display
 (simple-format
  #f <span style="color: #55B5DB;">"~a\n"</span>
  (((<span style="color: #9FCA56;">lambda</span> (make-length)
      (make-length
       (make-length
        (make-length eternity))))
    (<span style="color: #9FCA56;">lambda</span> (something)
      (<span style="color: #9FCA56;">lambda</span> (lst)
        (<span style="color: #9FCA56;">cond</span>
         [(null? lst) 0]
         [<span style="color: #9FCA56;">else</span> (+ 1 (something (cdr lst)))]))))
   <span style="color: #75715E;">;; </span><span style="color: #41535B;">Apply it to the list with 1 element.</span>
   '(a))))

(display
 (simple-format
  #f <span style="color: #55B5DB;">"~a\n"</span>
  (((<span style="color: #9FCA56;">lambda</span> (make-length)
      (make-length
       (make-length
        (make-length eternity))))
    (<span style="color: #9FCA56;">lambda</span> (something)
      (<span style="color: #9FCA56;">lambda</span> (lst)
        (<span style="color: #9FCA56;">cond</span>
         [(null? lst) 0]
         [<span style="color: #9FCA56;">else</span> (+ 1 (something (cdr lst)))]))))
   <span style="color: #75715E;">;; </span><span style="color: #41535B;">Apply it to the list with 2 elements.</span>
   '(a b))))
</pre>
</div>

<p>
It gives the correct results.
</p>

<p>
At this point it seems like recursion actually is a conditionally infinite tower of applications of a procedure. Notice the multiple nested applications of <code>make-length</code> in the code above.
</p>

<p>
The problem is still, that the <code>make-length</code> is repeated once per iteration though. We notice however, that we apply <code>eternity</code>, when we do not have sufficient applications of the procedure any longer to process the list given. This means there will be no error, but also no result. Instead we will have infinite useless recursion going on. This is kind of like an error, even if no error or exception is raised. We will have to stop the recursion at some point to be able to do something more useful. However, this only happens in the bad case, where the list is too long to be processed by our number of applications of the procedure. This means, that we actually do not really care about how it goes wrong there. We do not ever want to get to the case, where we do not have sufficient applications. This means we could use any other procedure instead of <code>eternity</code>. That would only change the error case. Let us try to raise an error, when the list has too many elements to process, by giving a lambda, which raises an error, instead of giving eternity:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org827386c">(catch
  'list-too-deep
  <span style="color: #75715E;">;; </span><span style="color: #41535B;">thunk (procedure that takes 0 arguments) producing the exception</span>
  (<span style="color: #9FCA56;">lambda</span> ()
    (((<span style="color: #9FCA56;">lambda</span> (make-length)
        (make-length
         (make-length
          (make-length
           <span style="color: #75715E;">;; </span><span style="color: #41535B;">here we use an error raising procedure instead of eternity</span>
           (<span style="color: #9FCA56;">lambda</span> (rest-of-list)
             (throw 'list-too-deep rest-of-list))))))
      (<span style="color: #9FCA56;">lambda</span> (something)
        (<span style="color: #9FCA56;">lambda</span> (lst)
          (<span style="color: #9FCA56;">cond</span>
           [(null? lst) 0]
           [<span style="color: #9FCA56;">else</span> (+ 1 (something (cdr lst)))]))))
     <span style="color: #75715E;">;; </span><span style="color: #41535B;">Apply it to the list with 3 (1 too many) elements.</span>
     '(a b c)))
  <span style="color: #75715E;">;; </span><span style="color: #41535B;">handler</span>
  (<span style="color: #9FCA56;">lambda</span> (key . args)
    (display
     (simple-format #f <span style="color: #55B5DB;">"~a args: ~a\n"</span> <span style="color: #55B5DB;">"The list is too deep."</span> args))))
</pre>
</div>

<p>
(The above code uses GNU Guile Scheme speciifc exception handling.)
</p>

<p>
As we can see a useful error message is output, because that is the behavior in the bad case, that the list is too long.
</p>

<p>
The idea now is, that we can use the fact, that it does not matter which procedure we give as an argument. Instead of giving <code>eternity</code> or a procedure for error handling, we can give a procedure, which in the bad case creates another application of <code>length-0</code>, so that we never run out of applications of <code>length-0</code>! We already know a procedure creating <code>length-0</code>: <code>make-length</code> applied to any procedure.
</p>

<p>
Here is how we are going to do it:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org288f20f">((<span style="color: #9FCA56;">lambda</span> (make-length)
   <span style="color: #75715E;">;; </span><span style="color: #41535B;">apply make-length to itself</span>
   (make-length make-length))
 (<span style="color: #9FCA56;">lambda</span> (proc)
   (<span style="color: #9FCA56;">lambda</span> (lst)
     (<span style="color: #9FCA56;">cond</span>
      [(null? lst) 0]
      [<span style="color: #9FCA56;">else</span>
       (+ 1
          <span style="color: #75715E;">;; </span><span style="color: #41535B;">apply the given procedure (make-length in this case) to itself</span>
          ((proc proc)
           (cdr lst)))]))))
</pre>
</div>

<p>
We apply <code>make-length</code> to itself, in order to get another procedure, which we can use for the recursive call in the case, that the list has more elements. We already know, that <code>make-length</code> will create another <code>length-0</code>, which has had a bad <code>else</code> case, which would have led to no result or an error. Previously we solved this issue in a bad way, by writing more and more calls to <code>make-length</code> which we wrapped around an innermost <code>length-0</code>, which made use of <code>eternity</code> or raised an error. Now we produce an ad-hoc <code>length-0</code>, only in case the list has more elements, to apply it to the rest of the list. It can in turn produce another <code>length-0</code>, if it needs to do so. This way, the list can have arbitrary length and our <code>length</code> function will still work.
</p>

<p>
We can demonstrate, that the above code works:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgbf6b2c3">(display
 (simple-format
  #f <span style="color: #55B5DB;">"~a\n"</span>
  (((<span style="color: #9FCA56;">lambda</span> (make-length)
      (make-length make-length))
    (<span style="color: #9FCA56;">lambda</span> (proc)
      (<span style="color: #9FCA56;">lambda</span> (lst)
        (<span style="color: #9FCA56;">cond</span>
         [(null? lst) 0]
         [<span style="color: #9FCA56;">else</span>
          (+ 1
             ((proc proc)
              (cdr lst)))]))))
   '(a b c d))))

(display
 (simple-format
  #f <span style="color: #55B5DB;">"~a\n"</span>
  (((<span style="color: #9FCA56;">lambda</span> (make-length)
      (make-length make-length))
    (<span style="color: #9FCA56;">lambda</span> (proc)
      (<span style="color: #9FCA56;">lambda</span> (lst)
        (<span style="color: #9FCA56;">cond</span>
         [(null? lst) 0]
         [<span style="color: #9FCA56;">else</span>
          (+ 1
             ((proc proc)
              (cdr lst)))]))))
   '(a b c d e f g h))))
</pre>
</div>

<pre class="example">
4
8
</pre>


<p>
This is an implementation of <code>length</code>, without using its name anywhere.
</p>

<p>
What happened here is actually the following: We could not use the name <code>length</code> anywhere in the definition, because we cannot use any <code>define</code> form and furthermore we want to get to some other construct, which can implement recursion in programming languages, which do not support calling a procedure within its own body. What we did instead is to have the name in another scope, another lambda receiving the logic of <code>length</code> as an argument, to give a name to this argument. That argument <code>make-length</code> is the logic of <code>length</code>, but with one difference. It takes a procedure too (<code>proc</code>) and gives it a name (<code>proc</code>), so that it can call that procedure wih the same procedure <code>proc</code> as an argument. The procedure <code>proc</code> however, is nothing else than what the other lambda gives as an argument, which in turn is the logic of <code>length</code> again. This way the recursive call does not need a binding defined using a <code>define</code> form and can work completely anonymously.
</p>

<p>
Another way to describe it is the following: <code>make-length</code> gets a procedure <code>proc</code> as argument, only to be able to have it named inside the inner lambda expression. This way the inner lambda expression can make use of the given procedure. The given procedure then is <code>make-length</code> itself, given by the sibling lambda expression, which will allow creating ad-hoc procedures, lambdas, which to use in case there are more elements in the list. All of the parts are necessary:
</p>

<ol class="org-ol">
<li><p>
application of <code>make-length</code> to itself:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org5cec9b8">  ((<span style="color: #9FCA56;">lambda</span> (make-length)
     (make-length make-length))
   ...)
</pre>
</div>

<p>
The application to itself is only possible by wrapping with a lambda, to give an argument a name <code>make-length</code>.
</p></li>

<li><p>
<code>make-length</code>, taking a procedure as an argument:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org707b458">  (...
   (<span style="color: #9FCA56;">lambda</span> (proc)
     (<span style="color: #9FCA56;">lambda</span> (lst)
       (<span style="color: #9FCA56;">cond</span>
        [(null? lst) 0]
        [<span style="color: #9FCA56;">else</span>
         (+ 1
            ((proc proc)
             (cdr lst)))]))))
</pre>
</div>

<p>
This contains the logic of <code>length</code> in it, as well as the production of new lambdas in the <code>else</code> branch.
</p></li>

<li><p>
The outer application of the 1. part to the 2. part:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org3e08bad">  (...
   ...)
</pre>
</div>

<p>
This part is necessary for actually creating the function <code>length</code> by application of the 1. part to the 2. part.
</p></li>
</ol>

<p>
After the function <code>length</code> is made, <code>length</code> can be applied to any list.
</p>
</div>
</div>

<div id="outline-container-orgb7ac798" class="outline-3">
<h3 id="orgb7ac798"><span class="section-number-3">3.6</span> Making all kinds of recursive procedures</h3>
<div class="outline-text-3" id="text-3-6">
<p>
Now that <code>length</code> has been implemented, we would like to have the whole concept of how that was done generalized, so that we can use it for any procedure. In order to achieve that, one last problem needs to be addressed. In order to use the concept for any procedure, we need to be able to give any procedure as an argument at some point. Currently however, the logic of <code>length</code> is somewhere inside and not given as a parameter.
</p>

<p>
To get to a version, where we give the logic of <code>length</code> as an argument let us look at the current definition again:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org8a6ab45">((<span style="color: #9FCA56;">lambda</span> (make-length)
   (make-length make-length))
 <span style="color: #75715E;">;; </span><span style="color: #41535B;">lambda wrapping around the logic of length -- make-length</span>
 (<span style="color: #9FCA56;">lambda</span> (proc)
   (<span style="color: #9FCA56;">lambda</span> (lst)
     (<span style="color: #9FCA56;">cond</span>
      [(null? lst) 0]
      [<span style="color: #9FCA56;">else</span>
       (+ 1
          <span style="color: #75715E;">;; </span><span style="color: #41535B;">usage of proc, argument to outer lambda</span>
          ((proc proc)
           (cdr lst)))]))))
</pre>
</div>

<p>
As we can see, the logic of <code>length</code> is wrapped in something we called <code>make-length</code> before. Inside the logic of <code>length</code> the argument <code>proc</code> is used, so the logic depends on the wrapper. If we managed to pull out the usage of <code>proc</code>, the logic of <code>length</code> would not depend on the wrap any longer. Then it can be imagined, that we could even give this logic as argument, in effect giving <code>length</code> as argument, allowing us to give any other procedure as well. So let us try to pull it out.
</p>

<p>
First we can try to naively pull it out by <i>lambda wrapping</i> as follows:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgaab9989">((<span style="color: #9FCA56;">lambda</span> (make-length)
   (make-length make-length))

 (<span style="color: #9FCA56;">lambda</span> (proc)
   <span style="color: #75715E;">;; </span><span style="color: #41535B;">We need acces to the given procedure proc, so the lambda wrapping needs to</span>
   <span style="color: #75715E;">;; </span><span style="color: #41535B;">be inside the wrapper. We name the argument length, because it is really</span>
   <span style="color: #75715E;">;; </span><span style="color: #41535B;">the simple definition of length, with an external binding of length by a</span>
   <span style="color: #75715E;">;; </span><span style="color: #41535B;">wrapping lambda expression now.</span>
   (<span style="color: #9FCA56;">lambda</span> (length)
     (<span style="color: #9FCA56;">lambda</span> (lst)
       (<span style="color: #9FCA56;">cond</span>
        [(null? lst) 0]
        [<span style="color: #9FCA56;">else</span>
         (+ 1
            <span style="color: #75715E;">;; </span><span style="color: #41535B;">usage of length</span>
            (length (cdr lst)))]))
     <span style="color: #75715E;">;; </span><span style="color: #41535B;">Here we produce the lambdas for usage in the else branch of length ...</span>
     (proc proc))))
</pre>
</div>

<p>
However, there is a problem with this code. It does not work. While previously the application of <code>proc</code> to <code>proc</code> was inside the <code>else</code> branch and only evaluated, when that branch was entered. Now however, it is evaluated when the call <code>(make-length make-length)</code> is made. That means in order to evaluate the whole thing, one needs to know what <code>(proc proc)</code> is. But <code>proc</code> is the argument given to <code>make-length</code>, which is the same lambda expression, for whose evaluation we need to know what <code>(proc proc)</code> is. This will result in an endless expansion of code.
</p>

<p>
Previously, the call <code>(proc proc)</code> was inside the <code>else</code> branch. Evaluating it would still need to know what <code>(proc proc)</code> is and evaluate it. However, since in the evaluation of a <code>(proc proc)</code> is inside the <code>else</code> branch and in its evaluation the <code>proc</code> appears again in the <code>else</code> branch, it would not get evaluated over and over again. The code in an <code>else</code> branch of <code>cond</code> is only evaluated, when <code>else</code> is the case that is entered. This is because <code>cond</code> is a macro, not a procedure! This is what actually prevents endless code execution.
</p>

<p>
What can be done about this? We cannot put the call back into the <code>else</code> branch again, as we wanted to extract it. Instead, we need make use of <i>delayed evaluation</i> of the application of <code>proc</code> to itself to delay creating endless expansion of expressions, until the <code>else</code> branch is entered. Delayed evaluation of the application of <code>proc</code> to itself can be done using <i>lambda wrapping</i> again. Note, that <code>length</code> in the <code>else</code> branch takes 1 argument, which is the rest of the list. The delayed evaluation thus done as follows:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgf283b5d">((<span style="color: #9FCA56;">lambda</span> (make-length)
   (make-length make-length))

 (<span style="color: #9FCA56;">lambda</span> (proc)
   ((<span style="color: #9FCA56;">lambda</span> (length)
     (<span style="color: #9FCA56;">lambda</span> (lst)
       (<span style="color: #9FCA56;">cond</span>
        [(null? lst) 0]
        [<span style="color: #9FCA56;">else</span>
         <span style="color: #75715E;">;; </span><span style="color: #41535B;">usage of length, just like before, using 2 argument</span>
         (+ 1 (length (cdr lst)))])))
    <span style="color: #75715E;">;; </span><span style="color: #41535B;">lambda wrapping -- delayed evaluation of (proc proc)</span>
    (<span style="color: #9FCA56;">lambda</span> (rest-of-list)
      <span style="color: #75715E;">;; </span><span style="color: #41535B;">(proc proc) is not evaluated, until the wrapping lambda is called</span>
      ((proc proc) rest-of-list)))))
</pre>
</div>

<p>
Let us try to use it:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgf644730">(display
 (simple-format
  #f <span style="color: #55B5DB;">"~a\n"</span>
  (((<span style="color: #9FCA56;">lambda</span> (make-length)
      (make-length make-length))

    (<span style="color: #9FCA56;">lambda</span> (proc)
      ((<span style="color: #9FCA56;">lambda</span> (length)
         (<span style="color: #9FCA56;">lambda</span> (lst)
           (<span style="color: #9FCA56;">cond</span>
            [(null? lst) 0]
            [<span style="color: #9FCA56;">else</span>
             <span style="color: #75715E;">;; </span><span style="color: #41535B;">usage of length, just like before, using 2 argument</span>
             (+ 1 (length (cdr lst)))])))
       <span style="color: #75715E;">;; </span><span style="color: #41535B;">lambda wrapping -- delayed evaluation of (proc proc)</span>
       (<span style="color: #9FCA56;">lambda</span> (rest-of-list)
         <span style="color: #75715E;">;; </span><span style="color: #41535B;">(proc proc) is not evaluated, until the wrapping lambda is called</span>
         ((proc proc) rest-of-list)))))
   <span style="color: #75715E;">;; </span><span style="color: #41535B;">apply to a list of 3 elements</span>
   '(a b c))))

(display
 (simple-format
  #f <span style="color: #55B5DB;">"~a\n"</span>
  (((<span style="color: #9FCA56;">lambda</span> (make-length)
      (make-length make-length))

    (<span style="color: #9FCA56;">lambda</span> (proc)
      ((<span style="color: #9FCA56;">lambda</span> (length)
         (<span style="color: #9FCA56;">lambda</span> (lst)
           (<span style="color: #9FCA56;">cond</span>
            [(null? lst) 0]
            [<span style="color: #9FCA56;">else</span>
             <span style="color: #75715E;">;; </span><span style="color: #41535B;">usage of length, just like before, using 2 argument</span>
             (+ 1 (length (cdr lst)))])))
       <span style="color: #75715E;">;; </span><span style="color: #41535B;">lambda wrapping -- delayed evaluation of (proc proc)</span>
       (<span style="color: #9FCA56;">lambda</span> (rest-of-list)
         <span style="color: #75715E;">;; </span><span style="color: #41535B;">(proc proc) is not evaluated, until the wrapping lambda is called</span>
         ((proc proc) rest-of-list)))))
   <span style="color: #75715E;">;; </span><span style="color: #41535B;">apply to a list of more elements</span>
   '(a b c d e f))))
</pre>
</div>

<pre class="example">
3
6
</pre>


<p>
That is the correct and expected result.
</p>

<p>
We have managed to pull the call of <code>proc</code> to itself out of the <code>length</code> logic. Now we can extract that as well, as it does not depend on the wrapping lambda expression, which we call <code>make-length</code> any longer. Let us do that, in order to make this part interchangable with other procedures. To be clear about what shall be pulled out, here is the part of the code:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org207428b">(<span style="color: #9FCA56;">lambda</span> (length)
  (<span style="color: #9FCA56;">lambda</span> (lst)
    (<span style="color: #9FCA56;">cond</span>
     [(null? lst) 0]
     [<span style="color: #9FCA56;">else</span>
      (+ 1 (length (cdr lst)))])))
</pre>
</div>

<p>
We want to give this part of the code as an argument to the other part of the code, so that it can come from the outside. This means, that we need to wrap the other part of the code on the outermost level as follows:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orga15fad5"><span style="color: #75715E;">;; </span><span style="color: #41535B;">Here is the wrapping lambda expression at the outermost level.</span>
((<span style="color: #9FCA56;">lambda</span> (extracted-proc)
   ((<span style="color: #9FCA56;">lambda</span> (make-length)
      (make-length make-length))
    (<span style="color: #9FCA56;">lambda</span> (proc)
      (extracted-proc
       <span style="color: #75715E;">;; </span><span style="color: #41535B;">Here is the lambda that shall be applied to the rest of the list.</span>
       (<span style="color: #9FCA56;">lambda</span> (rest-of-list)
         ((proc proc) rest-of-list))))))
 <span style="color: #75715E;">;; </span><span style="color: #41535B;">Here is the extracted logic of length. As an argument it requires the</span>
 <span style="color: #75715E;">;; </span><span style="color: #41535B;">lambda that shall be applied to the rest of the list.</span>
 (<span style="color: #9FCA56;">lambda</span> (length)
   (<span style="color: #9FCA56;">lambda</span> (lst)
     (<span style="color: #9FCA56;">cond</span>
      [(null? lst) 0]
      [<span style="color: #9FCA56;">else</span>
       (+ 1 (length (cdr lst)))]))))
</pre>
</div>

<p>
Let us test this code again with a few examples:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org9062564">(display
 (simple-format
  #f <span style="color: #55B5DB;">"~a\n"</span>
  (((<span style="color: #9FCA56;">lambda</span> (extracted-proc)
      ((<span style="color: #9FCA56;">lambda</span> (make-length)
         (make-length make-length))
       (<span style="color: #9FCA56;">lambda</span> (proc)
         (extracted-proc
          (<span style="color: #9FCA56;">lambda</span> (rest-of-list)
            ((proc proc) rest-of-list))))))
    (<span style="color: #9FCA56;">lambda</span> (length)
      (<span style="color: #9FCA56;">lambda</span> (lst)
        (<span style="color: #9FCA56;">cond</span>
         [(null? lst) 0]
         [<span style="color: #9FCA56;">else</span>
          (+ 1 (length (cdr lst)))]))))
   <span style="color: #75715E;">;; </span><span style="color: #41535B;">apply to a list of 3 elements</span>
   '(a b c))))

(display
 (simple-format
  #f <span style="color: #55B5DB;">"~a\n"</span>
  (((<span style="color: #9FCA56;">lambda</span> (extracted-proc)
      ((<span style="color: #9FCA56;">lambda</span> (make-length)
         (make-length make-length))
       (<span style="color: #9FCA56;">lambda</span> (proc)
         (extracted-proc
          (<span style="color: #9FCA56;">lambda</span> (rest-of-list)
            ((proc proc) rest-of-list))))))
    (<span style="color: #9FCA56;">lambda</span> (length)
      (<span style="color: #9FCA56;">lambda</span> (lst)
        (<span style="color: #9FCA56;">cond</span>
         [(null? lst) 0]
         [<span style="color: #9FCA56;">else</span>
          (+ 1 (length (cdr lst)))]))))
   <span style="color: #75715E;">;; </span><span style="color: #41535B;">apply to a list of more elements</span>
   '(a b c d e f))))
</pre>
</div>

<pre class="example">
3
6
</pre>


<p>
Still working.
</p>

<p>
If we go back to the first formulation of <code>make-length</code>, which is able to create <code>length-0</code>, we will see, that this is exactly, what we extracted.
</p>

<p>
We can now go ahead and give other procedures as arguments. For example we can give a procedure, which sums up all the numbers in a simple, not nested list as follows:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org8365e2f">((<span style="color: #9FCA56;">lambda</span> (extracted-proc)
   ((<span style="color: #9FCA56;">lambda</span> (make-length)
      (make-length make-length))
    (<span style="color: #9FCA56;">lambda</span> (proc)
      (extracted-proc
       (<span style="color: #9FCA56;">lambda</span> (rest-of-list)
         ((proc proc) rest-of-list))))))
 <span style="color: #75715E;">;; </span><span style="color: #41535B;">the procedure make-sum</span>
 (<span style="color: #9FCA56;">lambda</span> (sum)
   (<span style="color: #9FCA56;">lambda</span> (lst)
     (<span style="color: #9FCA56;">cond</span>
      [(null? lst) 0]
      [<span style="color: #9FCA56;">else</span>
       (+ (car lst)
          (sum (cdr lst)))]))))
</pre>
</div>

<p>
Let us check, whether that works:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org95f32e1">(display
 (simple-format
  #f <span style="color: #55B5DB;">"~a\n"</span>
  (((<span style="color: #9FCA56;">lambda</span> (extracted-proc)
      ((<span style="color: #9FCA56;">lambda</span> (make-length)
         (make-length make-length))
       (<span style="color: #9FCA56;">lambda</span> (proc)
         (extracted-proc
          (<span style="color: #9FCA56;">lambda</span> (rest-of-list)
            ((proc proc) rest-of-list))))))
    <span style="color: #75715E;">;; </span><span style="color: #41535B;">the procedure make-sum</span>
    (<span style="color: #9FCA56;">lambda</span> (sum)
      (<span style="color: #9FCA56;">lambda</span> (lst)
        (<span style="color: #9FCA56;">cond</span>
         [(null? lst) 0]
         [<span style="color: #9FCA56;">else</span>
          (+ (car lst)
             (sum (cdr lst)))]))))
   '(1 2 3))))
</pre>
</div>

<pre class="example">
6
</pre>


<p>
Yes, we got the correct result! Let us make one for nested lists containing numbers:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org17bdfd4">(display
 (simple-format
  #f <span style="color: #55B5DB;">"~a\n"</span>
  (((<span style="color: #9FCA56;">lambda</span> (extracted-proc)
      ((<span style="color: #9FCA56;">lambda</span> (make-length)
         (make-length make-length))
       (<span style="color: #9FCA56;">lambda</span> (proc)
         (extracted-proc
          (<span style="color: #9FCA56;">lambda</span> (rest-of-list)
            ((proc proc) rest-of-list))))))
    <span style="color: #75715E;">;; </span><span style="color: #41535B;">the procedure make-sum</span>
    (<span style="color: #9FCA56;">lambda</span> (sum)
      (<span style="color: #9FCA56;">lambda</span> (lst)
        (<span style="color: #9FCA56;">cond</span>
         [(null? lst) 0]
         [(pair? (car lst))
          (+ (sum (car lst))
             (sum (cdr lst)))]
         [<span style="color: #9FCA56;">else</span>
          (+ (car lst)
             (sum (cdr lst)))]))))
   '(1 2 (3 4 5) 6))))
</pre>
</div>

<pre class="example">
21
</pre>


<p>
The result is correct as well. We see, that we can define procedures for arbitrarily structured lists or other data structures, if we create the procedures accordingly and use them like this.
</p>
</div>
</div>

<div id="outline-container-org6e74d52" class="outline-3">
<h3 id="org6e74d52"><span class="section-number-3">3.7</span> Separating the Y-combinator</h3>
<div class="outline-text-3" id="text-3-7">
<p>
There is a question however. What is this other part of the code, which we do not change, when we adapt the lambda expression for length of a list or sum of all numbers in a list? This part seems to do all the magic, that allows us to write <code>length</code>, <code>sum</code> and <code>sum*</code> without creating a binding using a <code>define</code> form. It seems special, so let us write it down:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org7efba7f">(<span style="color: #9FCA56;">lambda</span> (extracted-proc)
  ((<span style="color: #9FCA56;">lambda</span> (make-length)
     (make-length make-length))
   (<span style="color: #9FCA56;">lambda</span> (proc)
     (extracted-proc
      (<span style="color: #9FCA56;">lambda</span> (rest-of-list)
        ((proc proc) rest-of-list))))))
</pre>
</div>

<p>
This is the so called Y-combinator!
</p>
</div>

<div id="outline-container-org5e025f1" class="outline-4">
<h4 id="org5e025f1"><span class="section-number-4">3.7.1</span> Renaming arguments</h4>
<div class="outline-text-4" id="text-3-7-1">
<p>
In topic specific literature, the arguments in the lambda expressions of the Y-combinator are usually named differently. In order to get the same naming let us consider a few things:
</p>

<ol class="org-ol">
<li><p>
The argument <code>proc</code> can actually be called <code>make-length</code>, because it only ever will be <code>make-length</code>, as that lambda expression it is called as follows: <code>(make-length make-length)</code>. So let us write down a changed version:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgf3367df">  (<span style="color: #9FCA56;">lambda</span> (extracted-proc)
    ((<span style="color: #9FCA56;">lambda</span> (make-length)
       (make-length make-length))
     (<span style="color: #9FCA56;">lambda</span> (make-length)
       (extracted-proc
        (<span style="color: #9FCA56;">lambda</span> (rest-of-list)
          ((make-length make-length) rest-of-list))))))
</pre>
</div></li>

<li><p>
As we may work with other data structures than lists and accordingly adapted procedures we give to the Y-combinator, let us not use <code>rest-of-list</code> any longer as an argument name and instead use <code>x</code>, because it can really be anything:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgdbf5f98">  (<span style="color: #9FCA56;">lambda</span> (extracted-proc)
    ((<span style="color: #9FCA56;">lambda</span> (make-length)
       (make-length make-length))
     (<span style="color: #9FCA56;">lambda</span> (make-length)
       (extracted-proc
        (<span style="color: #9FCA56;">lambda</span> (x)
          ((make-length make-length) x))))))
</pre>
</div></li>

<li><p>
The argument name <code>extracted-proc</code> does not help, when seeing the Y-combinator in this form, as it is not clear, what the procedure given was extracted from. We might as well simply name it <code>proc</code> only:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgaa7bf58">  (<span style="color: #9FCA56;">lambda</span> (proc)
    ((<span style="color: #9FCA56;">lambda</span> (make-length)
       (make-length make-length))
     (<span style="color: #9FCA56;">lambda</span> (make-length)
       (proc
        (<span style="color: #9FCA56;">lambda</span> (x)
          ((make-length make-length) x))))))
</pre>
</div></li>

<li><p>
Lastly, the name <code>make-length</code> is no longer appropriate, since we can make all kinds of recursive procedures, not only <code>length</code>, using the Y-combinator. So let us name it <code>f</code>, as it can be any recursive procedure or function:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgfc211c7">  (<span style="color: #9FCA56;">lambda</span> (proc)
    ((<span style="color: #9FCA56;">lambda</span> (f)
       (f f))
     (<span style="color: #9FCA56;">lambda</span> (f)
       (proc
        (<span style="color: #9FCA56;">lambda</span> (x)
          ((f f) x))))))
</pre>
</div>

<p>
Or with different line-breaking:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org31d76b2">  (<span style="color: #9FCA56;">lambda</span> (proc)
    ((<span style="color: #9FCA56;">lambda</span> (f) (f f))
     (<span style="color: #9FCA56;">lambda</span> (f)
       (proc
        (<span style="color: #9FCA56;">lambda</span> (x) ((f f) x))))))
</pre>
</div></li>
</ol>

<p>
To be precise, literature calls this form of the Y-combinator the <i>applicative-order Y-combinator</i>.
</p>

<p>
Let us see it in action one more time using a standard example:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org1481843">(display
 (simple-format
  #f <span style="color: #55B5DB;">"Fibonacci of 10: ~a\n"</span>
  (((<span style="color: #9FCA56;">lambda</span> (proc)
      ((<span style="color: #9FCA56;">lambda</span> (f) (f f))
       (<span style="color: #9FCA56;">lambda</span> (f)
         (proc
          (<span style="color: #9FCA56;">lambda</span> (x) ((f f) x))))))
    (<span style="color: #9FCA56;">lambda</span> (fibonacci)
      (<span style="color: #9FCA56;">lambda</span> (num)
        (<span style="color: #9FCA56;">cond</span>
         [(&lt;= num 2) 1]
         [<span style="color: #9FCA56;">else</span>
          (+ (fibonacci (- num 1))
             (fibonacci (- num 2)))]))))
   10)))
</pre>
</div>

<pre class="example">
Fibonacci of 10: 55
</pre>


<p>
One can see, this also works on numbers. Basically it works on any data structure and how it works with a data structure depends only on the implementation of the procedure, which we give to the Y-combinator.
</p>
</div>
</div>
</div>
</div>

<div id="outline-container-orgede3d6b" class="outline-2">
<h2 id="orgede3d6b"><span class="section-number-2">4</span> Final words</h2>
<div class="outline-text-2" id="text-4">
<p>
Without the help of the book "The Little Schemer", I would most likely not have been able to derive the Y-combinator on my own. I had to think long and hard about some of the steps, why one would perform the equivalent transformations and how to describe these steps, so that there is more description than in the book. The book however, with its rather rare way of asking questions, making me think about the content a lot, helped me being able to write about the Y-combinator and how it can be derived.
</p>

<p>
I encourage everyone, who is a software developer to read "The Little Schemer". It can be an enormously insightful and enlightening read. It may take a lot of time to work through it and understand all or at least most of the content, but you really owe it to your computer science education.
</p>
</div>
</div>
</div>
<div id="postamble" class="status">
<p class="author">Author: Zelphir Kaltstahl</p>
<p class="date">Created: 2020-08-23 So 13:46</p>
<p class="validation"><a href="http://validator.w3.org/check?uri=referer">Validate</a></p>
</div>
</body>
</html>