ZelphirKaltstahl
/
the-little-schemer


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995
							<?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>
<!-- 2019-09-13 Fri 03:26 -->
<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; }
  .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-2018 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</h1>
<div id="table-of-contents">
<h2>Table of Contents</h2>
<div id="text-table-of-contents">
<ul>
<li><a href="#org480bee2">1. Prerequisites</a></li>
<li><a href="#orgca02e4d">2. Chapter code</a>
<ul>
<li><a href="#orgbdf1635">2.1. looking</a></li>
<li><a href="#org1ee8a71">2.2. eternity</a></li>
<li><a href="#org9b60f0d">2.3. shift</a></li>
<li><a href="#orgfcefeb8">2.4. align</a></li>
<li><a href="#org7adaff1">2.5. Weighting function, length* and weight*</a></li>
<li><a href="#org3bd5465">2.6. shuffle</a></li>
<li><a href="#org3e34d1c">2.7. Collatz function</a></li>
<li><a href="#orgacb1bf1">2.8. Ackermann function</a></li>
<li><a href="#org3e1215e">2.9. Halting Problem</a></li>
<li><a href="#org64aa20f">2.10. Y-combinator</a></li>
</ul>
</li>
</ul>
</div>
</div>

<div id="outline-container-org480bee2" class="outline-2">
<h2 id="org480bee2"><span class="section-number-2">1</span> Prerequisites</h2>
<div class="outline-text-2" id="text-1">
<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="org4be1e6e">(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">first</span> car)
(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">second</span> cadr)
(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">build</span> list)

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">pick</span>
  (<span style="color: #F92672;">lambda</span> (one-based-index lst)
    (<span style="color: #F92672;">cond</span>
     [(null? lst)
      (error <span style="color: #E6DB74;">"index error, index not in list"</span> one-based-index lst)]
     [(= one-based-index 1)
      (car lst)]
     [<span style="color: #F92672;">else</span>
      (pick (- one-based-index 1) (cdr lst))])))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">atom?</span>
  (<span style="color: #F92672;">lambda</span> (something)
    (<span style="color: #F92672;">and</span> (not (pair? something))
         (not (null? something)))))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">revpair</span>
  (<span style="color: #F92672;">lambda</span> (pair)
    (build (second pair)
           (first pair))))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">even?</span>
  (<span style="color: #F92672;">lambda</span> (num)
    (= (remainder num 2) 0)))
</pre>
</div>
</div>
</div>

<div id="outline-container-orgca02e4d" class="outline-2">
<h2 id="orgca02e4d"><span class="section-number-2">2</span> Chapter code</h2>
<div class="outline-text-2" id="text-2">
</div>
<div id="outline-container-orgbdf1635" class="outline-3">
<h3 id="orgbdf1635"><span class="section-number-3">2.1</span> looking</h3>
<div class="outline-text-3" id="text-2-1">
<p>
Examples where <code>looking</code> finds the symbol:
</p>

<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">first</span> car)
(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">second</span> cadr)
(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">build</span> list)

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">pick</span>
  (<span style="color: #F92672;">lambda</span> (one-based-index lst)
    (<span style="color: #F92672;">cond</span>
     [(null? lst)
      (error <span style="color: #E6DB74;">"index error, index not in list"</span> one-based-index lst)]
     [(= one-based-index 1)
      (car lst)]
     [<span style="color: #F92672;">else</span>
      (pick (- one-based-index 1) (cdr lst))])))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">atom?</span>
  (<span style="color: #F92672;">lambda</span> (something)
    (<span style="color: #F92672;">and</span> (not (pair? something))
         (not (null? something)))))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">revpair</span>
  (<span style="color: #F92672;">lambda</span> (pair)
    (build (second pair)
           (first pair))))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">even?</span>
  (<span style="color: #F92672;">lambda</span> (num)
    (= (remainder num 2) 0)))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">looking</span>
  (<span style="color: #F92672;">lambda</span> (elem list-of-atoms)
    (keep-looking elem (pick 1 list-of-atoms) list-of-atoms)))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">keep-looking</span>
  (<span style="color: #F92672;">lambda</span> (searched-symbol current-list-elem list-of-atoms)
    (<span style="color: #F92672;">cond</span>
     [(number? current-list-elem)
      (keep-looking searched-symbol
                    (pick current-list-elem list-of-atoms)
                    list-of-atoms)]
     [<span style="color: #F92672;">else</span>
      (eq? searched-symbol current-list-elem)])))

(looking 'apple '(2 3 4 5 6 apple))
(looking 'apple '(2 10 5 7 6 4 apple 1 1 3))
</pre>
</div>

<pre class="example">
#t

</pre>

<p>
Examples where <code>looking</code> does not find the symbol:
</p>

<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">first</span> car)
(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">second</span> cadr)
(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">build</span> list)

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">pick</span>
  (<span style="color: #F92672;">lambda</span> (one-based-index lst)
    (<span style="color: #F92672;">cond</span>
     [(null? lst)
      (error <span style="color: #E6DB74;">"index error, index not in list"</span> one-based-index lst)]
     [(= one-based-index 1)
      (car lst)]
     [<span style="color: #F92672;">else</span>
      (pick (- one-based-index 1) (cdr lst))])))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">atom?</span>
  (<span style="color: #F92672;">lambda</span> (something)
    (<span style="color: #F92672;">and</span> (not (pair? something))
         (not (null? something)))))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">revpair</span>
  (<span style="color: #F92672;">lambda</span> (pair)
    (build (second pair)
           (first pair))))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">even?</span>
  (<span style="color: #F92672;">lambda</span> (num)
    (= (remainder num 2) 0)))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">looking</span>
  (<span style="color: #F92672;">lambda</span> (elem list-of-atoms)
    (keep-looking elem (pick 1 list-of-atoms) list-of-atoms)))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">keep-looking</span>
  (<span style="color: #F92672;">lambda</span> (searched-symbol current-list-elem list-of-atoms)
    (<span style="color: #F92672;">cond</span>
     [(number? current-list-elem)
      (keep-looking searched-symbol
                    (pick current-list-elem list-of-atoms)
                    list-of-atoms)]
     [<span style="color: #F92672;">else</span>
      (eq? searched-symbol current-list-elem)])))

(looking 'apple '(2 3 4 5 6 tea))
(looking 'apple '(2 10 5 7 6 4 orange 1 1 3))
</pre>
</div>

<pre class="example">
#f

</pre>

<p>
Examples that run forever:
</p>

<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">first</span> car)
(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">second</span> cadr)
(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">build</span> list)

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">pick</span>
  (<span style="color: #F92672;">lambda</span> (one-based-index lst)
    (<span style="color: #F92672;">cond</span>
     [(null? lst)
      (error <span style="color: #E6DB74;">"index error, index not in list"</span> one-based-index lst)]
     [(= one-based-index 1)
      (car lst)]
     [<span style="color: #F92672;">else</span>
      (pick (- one-based-index 1) (cdr lst))])))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">atom?</span>
  (<span style="color: #F92672;">lambda</span> (something)
    (<span style="color: #F92672;">and</span> (not (pair? something))
         (not (null? something)))))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">revpair</span>
  (<span style="color: #F92672;">lambda</span> (pair)
    (build (second pair)
           (first pair))))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">even?</span>
  (<span style="color: #F92672;">lambda</span> (num)
    (= (remainder num 2) 0)))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">looking</span>
  (<span style="color: #F92672;">lambda</span> (elem list-of-atoms)
    (keep-looking elem (pick 1 list-of-atoms) list-of-atoms)))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">keep-looking</span>
  (<span style="color: #F92672;">lambda</span> (searched-symbol current-list-elem list-of-atoms)
    (<span style="color: #F92672;">cond</span>
     [(number? current-list-elem)
      (keep-looking searched-symbol
                    (pick current-list-elem list-of-atoms)
                    list-of-atoms)]
     [<span style="color: #F92672;">else</span>
      (eq? searched-symbol current-list-elem)])))

(looking 'apple '(1))
(looking 'apple '(2 1))
</pre>
</div>

<p>
The fact that there are examples, for which <code>looking</code> does not return a value, means, that the function is not <i>total</i>, but is <i>partial</i> instead.
</p>
</div>
</div>

<div id="outline-container-org1ee8a71" class="outline-3">
<h3 id="org1ee8a71"><span class="section-number-3">2.2</span> eternity</h3>
<div class="outline-text-3" id="text-2-2">
<p>
<code>eternity</code> is an endlessly recursive procedure. Once it is called anywhere, the execution will be trapped in recurring over and over again.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org8e5814d">(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">eternity</span>
  (<span style="color: #F92672;">lambda</span> (something)
    (eternity something)))
</pre>
</div>
</div>
</div>

<div id="outline-container-org9b60f0d" class="outline-3">
<h3 id="org9b60f0d"><span class="section-number-3">2.3</span> shift</h3>
<div class="outline-text-3" id="text-2-3">
<p>
<code>shift</code> changes the structure of sublists in a list.
</p>

<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">first</span> car)
(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">second</span> cadr)
(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">build</span> list)

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">pick</span>
  (<span style="color: #F92672;">lambda</span> (one-based-index lst)
    (<span style="color: #F92672;">cond</span>
     [(null? lst)
      (error <span style="color: #E6DB74;">"index error, index not in list"</span> one-based-index lst)]
     [(= one-based-index 1)
      (car lst)]
     [<span style="color: #F92672;">else</span>
      (pick (- one-based-index 1) (cdr lst))])))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">atom?</span>
  (<span style="color: #F92672;">lambda</span> (something)
    (<span style="color: #F92672;">and</span> (not (pair? something))
         (not (null? something)))))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">revpair</span>
  (<span style="color: #F92672;">lambda</span> (pair)
    (build (second pair)
           (first pair))))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">even?</span>
  (<span style="color: #F92672;">lambda</span> (num)
    (= (remainder num 2) 0)))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">shift</span>
  (<span style="color: #F92672;">lambda</span> (list-with-sublists)
    (build (first (first list-with-sublists))
           (build (second (first list-with-sublists))
                  (second list-with-sublists)))))

(display
 (simple-format #f <span style="color: #E6DB74;">"unshifted: ~a\n"</span>
                '((a b) (c d))))

(display
 (simple-format #f <span style="color: #E6DB74;">"shifted: ~a\n"</span>
                (shift '((a b) (c d)))))
</pre>
</div>

<pre class="example">
unshifted: ((a b) (c d))
shifted: (a (b (c d)))

</pre>
</div>
</div>

<div id="outline-container-orgfcefeb8" class="outline-3">
<h3 id="orgfcefeb8"><span class="section-number-3">2.4</span> align</h3>
<div class="outline-text-3" id="text-2-4">
<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">align</span>
  (<span style="color: #F92672;">lambda</span> (pair-or-atom)
    (<span style="color: #F92672;">cond</span>
     [(atom? pair-or-atom)
      pair-or-atom]
     [(pair? (car pair-or-atom))
      (align (shift pair-or-atom))]
     [<span style="color: #F92672;">else</span>
      (build (first pair-or-atom)
             (align (second pair-or-atom)))])))
</pre>
</div>
</div>
</div>

<div id="outline-container-org7adaff1" class="outline-3">
<h3 id="org7adaff1"><span class="section-number-3">2.5</span> Weighting function, length* and weight*</h3>
<div class="outline-text-3" id="text-2-5">
<p>
This is about defining a procedure to estimate how long a procedure will need for evaluating with a given input.
This is called <code>length*</code> in the book.
</p>

<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">first</span> car)
(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">second</span> cadr)
(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">build</span> list)

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">pick</span>
  (<span style="color: #F92672;">lambda</span> (one-based-index lst)
    (<span style="color: #F92672;">cond</span>
     [(null? lst)
      (error <span style="color: #E6DB74;">"index error, index not in list"</span> one-based-index lst)]
     [(= one-based-index 1)
      (car lst)]
     [<span style="color: #F92672;">else</span>
      (pick (- one-based-index 1) (cdr lst))])))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">atom?</span>
  (<span style="color: #F92672;">lambda</span> (something)
    (<span style="color: #F92672;">and</span> (not (pair? something))
         (not (null? something)))))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">revpair</span>
  (<span style="color: #F92672;">lambda</span> (pair)
    (build (second pair)
           (first pair))))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">even?</span>
  (<span style="color: #F92672;">lambda</span> (num)
    (= (remainder num 2) 0)))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">length*</span>
  (<span style="color: #F92672;">lambda</span> (pair-or-atom)
    (<span style="color: #F92672;">cond</span>
     [(null? pair-or-atom) 0]
     [(atom? pair-or-atom) 1]
     [<span style="color: #F92672;">else</span>
      (+ (length* (car pair-or-atom))
         (length* (cdr pair-or-atom)))])))

(display (simple-format #f <span style="color: #E6DB74;">"~a\n"</span> (length* (cons 1 2))))
(display (simple-format #f <span style="color: #E6DB74;">"~a\n"</span> (length* (cons (cons 1 2) 3))))
(display (simple-format #f <span style="color: #E6DB74;">"~a\n"</span> (length* (cons 1 (cons 2 3)))))
(display (simple-format #f <span style="color: #E6DB74;">"~a\n"</span> (length* (cons (cons 1 2) (cons 3 4)))))
</pre>
</div>

<pre class="example">
2
3
3
4

</pre>

<p>
Pairs in the first part of the <code>pair-or-atom</code> are treated specially and the pair is <code>shift</code>-ed. This means, that if there are more (nested) pairs in the first part of the pair, the whole thing will require more time to compute. This means, that <code>length*</code> might not be a good measure for how much time the computation will take. The book argues, that a procedure weighing the first part more than the second part would be more appropriate and gives the following procedure:
</p>

<div class="org-src-container">
<pre class="src src-scheme">(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">first</span> car)
(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">second</span> cadr)
(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">build</span> list)

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">pick</span>
  (<span style="color: #F92672;">lambda</span> (one-based-index lst)
    (<span style="color: #F92672;">cond</span>
     [(null? lst)
      (error <span style="color: #E6DB74;">"index error, index not in list"</span> one-based-index lst)]
     [(= one-based-index 1)
      (car lst)]
     [<span style="color: #F92672;">else</span>
      (pick (- one-based-index 1) (cdr lst))])))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">atom?</span>
  (<span style="color: #F92672;">lambda</span> (something)
    (<span style="color: #F92672;">and</span> (not (pair? something))
         (not (null? something)))))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">revpair</span>
  (<span style="color: #F92672;">lambda</span> (pair)
    (build (second pair)
           (first pair))))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">even?</span>
  (<span style="color: #F92672;">lambda</span> (num)
    (= (remainder num 2) 0)))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">weight*</span>
  (<span style="color: #F92672;">lambda</span> (pair-or-atom)
    (<span style="color: #F92672;">cond</span>
     [(null? pair-or-atom) 0]
     [(atom? pair-or-atom) 1]
     [<span style="color: #F92672;">else</span>
      (+ (* (weight* (first pair-or-atom)) 2)
         (weight* (second pair-or-atom)))])))

(display (simple-format #f <span style="color: #E6DB74;">"~a\n"</span> (weight* '(1 2))))
(display (simple-format #f <span style="color: #E6DB74;">"~a\n"</span> (weight* '((1 2) 3))))
(display (simple-format #f <span style="color: #E6DB74;">"~a\n"</span> (weight* '(1 (2 3)))))
(display (simple-format #f <span style="color: #E6DB74;">"~a\n"</span> (weight* '((1 2) (3 4)))))
</pre>
</div>

<pre class="example">
3
7
5
9

</pre>
</div>
</div>

<div id="outline-container-org3bd5465" class="outline-3">
<h3 id="org3bd5465"><span class="section-number-3">2.6</span> shuffle</h3>
<div class="outline-text-3" id="text-2-6">
<div class="org-src-container">
<pre class="src src-scheme" id="org319c6a0">(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">first</span> car)
(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">second</span> cadr)
(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">build</span> list)

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">pick</span>
  (<span style="color: #F92672;">lambda</span> (one-based-index lst)
    (<span style="color: #F92672;">cond</span>
     [(null? lst)
      (error <span style="color: #E6DB74;">"index error, index not in list"</span> one-based-index lst)]
     [(= one-based-index 1)
      (car lst)]
     [<span style="color: #F92672;">else</span>
      (pick (- one-based-index 1) (cdr lst))])))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">atom?</span>
  (<span style="color: #F92672;">lambda</span> (something)
    (<span style="color: #F92672;">and</span> (not (pair? something))
         (not (null? something)))))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">revpair</span>
  (<span style="color: #F92672;">lambda</span> (pair)
    (build (second pair)
           (first pair))))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">even?</span>
  (<span style="color: #F92672;">lambda</span> (num)
    (= (remainder num 2) 0)))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">shuffle</span>
  (<span style="color: #F92672;">lambda</span> (pair-or-atom)
    (<span style="color: #F92672;">cond</span>
     [(atom? pair-or-atom) pair-or-atom]
     <span style="color: #75715E;">;; </span><span style="color: #75715E;">here is the problematic case</span>
     [(pair? (first pair-or-atom))
      <span style="color: #75715E;">;; </span><span style="color: #75715E;">still the same amount of atoms in the argument for recurring</span>
      (shuffle (revpair pair-or-atom))]
     [<span style="color: #F92672;">else</span>
      (build (first pair-or-atom)
             (shuffle (second pair-or-atom)))])))
</pre>
</div>

<p>
<code>shuffle</code> is shown to be a partial function, as it recurs indefinitely for some inputs and thus does not return a value for every input. It recurs indefinitely for pairs, where the first part and the seconf part are pairs.
</p>
</div>
</div>

<div id="outline-container-org3e34d1c" class="outline-3">
<h3 id="org3e34d1c"><span class="section-number-3">2.7</span> Collatz function</h3>
<div class="outline-text-3" id="text-2-7">
<div class="org-src-container">
<pre class="src src-scheme" id="org5e3d44d">(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">first</span> car)
(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">second</span> cadr)
(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">build</span> list)

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">pick</span>
  (<span style="color: #F92672;">lambda</span> (one-based-index lst)
    (<span style="color: #F92672;">cond</span>
     [(null? lst)
      (error <span style="color: #E6DB74;">"index error, index not in list"</span> one-based-index lst)]
     [(= one-based-index 1)
      (car lst)]
     [<span style="color: #F92672;">else</span>
      (pick (- one-based-index 1) (cdr lst))])))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">atom?</span>
  (<span style="color: #F92672;">lambda</span> (something)
    (<span style="color: #F92672;">and</span> (not (pair? something))
         (not (null? something)))))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">revpair</span>
  (<span style="color: #F92672;">lambda</span> (pair)
    (build (second pair)
           (first pair))))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">even?</span>
  (<span style="color: #F92672;">lambda</span> (num)
    (= (remainder num 2) 0)))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">C</span>
  (<span style="color: #F92672;">lambda</span> (num)
    (<span style="color: #F92672;">cond</span>
     [(= num 1) 1]
     [(even? num) (C (/ num 2))]
     [<span style="color: #F92672;">else</span> (C (+ (* num 3) 1))])))

(display (simple-format #f <span style="color: #E6DB74;">"C(1) = ~a\n"</span> (C 1)))
(display (simple-format #f <span style="color: #E6DB74;">"C(27) = ~a\n"</span> (C 27)))
</pre>
</div>

<pre class="example">
C(1) = 1
C(27) = 1

</pre>

<p>
We can refactor <code>C</code> into a <code>collatz-step</code>, which calculates the next value passed to C and <code>collatz</code>, which calls itself. Then we can output the number of iterations easily by counting:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgb411e8a">(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">collatz-step</span>
  (<span style="color: #F92672;">lambda</span> (num)
    (<span style="color: #F92672;">cond</span>
     [(even? num) (/ num 2)]
     [<span style="color: #F92672;">else</span> (+ (* num 3) 1)])))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">collatz-count</span>
  (<span style="color: #F92672;">lambda</span> (n)
    (<span style="color: #F92672;">let</span> <span style="color: #A6E22E;">loop</span> ((num n) (count 0))
      (<span style="color: #F92672;">cond</span>
       [(= num 1) count]
       [<span style="color: #F92672;">else</span>
        (loop (collatz-step num)
              (+ count 1))]))))
</pre>
</div>

<p>
Then we can easily write a procedure, which tries numbers, until a given number of iterations is exeeced and give us back the number, for which that was the case:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org56d34d1">(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">collatz-step</span>
  (<span style="color: #F92672;">lambda</span> (num)
    (<span style="color: #F92672;">cond</span>
     [(even? num) (/ num 2)]
     [<span style="color: #F92672;">else</span> (+ (* num 3) 1)])))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">collatz-count</span>
  (<span style="color: #F92672;">lambda</span> (n)
    (<span style="color: #F92672;">let</span> <span style="color: #A6E22E;">loop</span> ((num n) (count 0))
      (<span style="color: #F92672;">cond</span>
       [(= num 1) count]
       [<span style="color: #F92672;">else</span>
        (loop (collatz-step num)
              (+ count 1))]))))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">collatz-find</span>
  (<span style="color: #F92672;">lambda</span> (max-iters)
    (<span style="color: #F92672;">let</span> <span style="color: #A6E22E;">loop</span> ([current-number 1])
      (<span style="color: #F92672;">cond</span>
       [(&gt;= (collatz-count current-number) max-iters) current-number]
       [<span style="color: #F92672;">else</span> (loop (+ current-number 1))]))))
</pre>
</div>

<p>
Enough fun with Collatz for now.
</p>
</div>
</div>

<div id="outline-container-orgacb1bf1" class="outline-3">
<h3 id="orgacb1bf1"><span class="section-number-3">2.8</span> Ackermann function</h3>
<div class="outline-text-3" id="text-2-8">
<div class="org-src-container">
<pre class="src src-scheme" id="orge8e0c93">(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">zero?</span>
  (<span style="color: #F92672;">lambda</span> (num)
    (= num 0)))

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">A</span>
  (<span style="color: #F92672;">lambda</span> (n m)
    (<span style="color: #F92672;">cond</span>
     [(zero? n) (+ m 1)]
     [(zero? m) (A (- n 1) 1)]
     [<span style="color: #F92672;">else</span>
      (A (- n 1)
         (A n (- m 1)))])))

(display (simple-format #f <span style="color: #E6DB74;">"~a\n"</span> (A 1 2)))
(display (simple-format #f <span style="color: #E6DB74;">"~a\n"</span> (A 2 2)))
(display (simple-format #f <span style="color: #E6DB74;">"~a\n"</span> (A 3 2)))
(display (simple-format #f <span style="color: #E6DB74;">"~a\n"</span> (A 3 4)))
(display (simple-format #f <span style="color: #E6DB74;">"~a\n"</span> (A 3 5)))
<span style="color: #75715E;">;; </span><span style="color: #75715E;">do not try: (display (simple-format #f "~a\n" (A 4 3)))</span>
(display (simple-format #f <span style="color: #E6DB74;">"~a\n"</span> (A 4 0)))
</pre>
</div>

<pre class="example">
4
7
29
125
253
13

</pre>

<p>
The numbers grow very quickly and calculating something like <code>(A 4 3)</code> is already infeasible.
</p>
</div>
</div>

<div id="outline-container-org3e1215e" class="outline-3">
<h3 id="org3e1215e"><span class="section-number-3">2.9</span> Halting Problem</h3>
<div class="outline-text-3" id="text-2-9">
<p>
This part treats the halting problem, without mentioning its name explicitly, but it shows, that it is impossible to define a procedure <code>will-stop?</code>, which tells us for arbitrary procedures and their arbitrary inputs, whether the execution of them will halt.
</p>

<p>
To show this a procedure is defined:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org0eb7712"><span style="color: #75715E;">;; </span><span style="color: #75715E;">prerequisites start</span>
(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">eternity</span>
  (<span style="color: #F92672;">lambda</span> (something)
    (eternity something)))
<span style="color: #75715E;">;; </span><span style="color: #75715E;">prerequisites end</span>

(<span style="color: #F92672;">define</span> <span style="color: #A6E22E;">weird-proc</span>
  (<span style="color: #F92672;">lambda</span> (anything)
    (<span style="color: #F92672;">and</span> (will-stop? weird-proc)
         (eternity anything))))
</pre>
</div>

<p>
The procedure <code>weird-proc</code> calls <code>will-stop?</code> to check, if itself will stop.
</p>

<p>
There are 2 cases for a predicate such as <code>will-stop?</code>. Either it returns true or it returns false, stating that either <code>weird-proc</code> will halt or that it will not.
</p>

<p>
Let us take a look at the two cases.
</p>
</div>

<div id="outline-container-org9ddc4de" class="outline-4">
<h4 id="org9ddc4de"><span class="section-number-4">2.9.1</span> Case 1: <code>will-stop?</code> returns false</h4>
<div class="outline-text-4" id="text-2-9-1">
<p>
Let us assume for a moment, that <code>will-stop?</code> will return the value false, stating, that <code>weird-proc</code> will not halt.
</p>

<p>
In this case the the first argument to <code>and</code> will be false. This means, that logically the whole <code>and</code> expression will be false. If that is the case however, <code>weird-proc</code> will have finished, as all the expressions in its body have been evaluated and the return value of <code>weird-proc</code> is false. This means, that the call to <code>will-stop?</code> in the body of <code>weird-proc</code> gave the wrong result.
</p>

<p>
If false is the wrong result of <code>will-stop?</code> then the correct result must surely be the value true.
</p>
</div>
</div>

<div id="outline-container-org0436c47" class="outline-4">
<h4 id="org0436c47"><span class="section-number-4">2.9.2</span> Case 2: <code>will-stop?</code> returns true</h4>
<div class="outline-text-4" id="text-2-9-2">
<p>
Let us assume for a moment, that <code>will-stop?</code> will return the value true, stating, that <code>weird-proc</code> will halt.
</p>

<p>
In this case the first argument to <code>and</code> will be the value true. This means, that for <code>and</code> to decide its result, it needs to consider the second argument. This however, means that <code>eternity</code> needs to be evaluated at some point to get its return value. This is not possible though, because <code>eternity</code> recurs infinitely and will never return a value. This means, that the execution of <code>weird-proc</code>, will never end, because the call to <code>eternity</code> is in its body. The procedure <code>will-stop?</code> lied to us again.
</p>
</div>
</div>

<div id="outline-container-orgd2749df" class="outline-4">
<h4 id="orgd2749df"><span class="section-number-4">2.9.3</span> Conclusion</h4>
<div class="outline-text-4" id="text-2-9-3">
<p>
No matter what return value we assume the procedure <code>will-stop?</code> to return, we can construct an example, in which any boolean return value will be incorrect. This means, that we cannot write the procedure <code>will-stop?</code>. This is known as the "Halting Problem". It is not decidable, whether a procedure will halt for all possible inputs, without loss of generality.
</p>
</div>
</div>
</div>

<div id="outline-container-org64aa20f" class="outline-3">
<h3 id="org64aa20f"><span class="section-number-3">2.10</span> Y-combinator</h3>
<div class="outline-text-3" id="text-2-10">
<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>

<p>
TODO: make a list of them here.
</p>
</div>
</div>
</div>
</div>
<div id="postamble" class="status">
<p class="author">Author: Zelphir Kaltstahl</p>
<p class="date">Created: 2019-09-13 Fri 03:26</p>
<p class="validation"><a href="http://validator.w3.org/check?uri=referer">Validate</a></p>
</div>
</body>
</html>