ZelphirKaltstahl
/
the-seasoned-schemer-notes


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901
							<?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>
<!-- 2023-02-26 So 16:12 -->
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>The Seasoned Schemer Notes</title>
<meta name="author" content="Zelphir Kaltstahl" />
<meta name="generator" content="Org Mode" />
<style>
  #content { max-width: 60em; margin: auto; }
  .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 #e6e6e6;
    border-radius: 3px;
    background-color: #f2f2f2;
    padding: 8pt;
    font-family: monospace;
    overflow: auto;
    margin: 1.2em;
  }
  pre.src {
    position: relative;
    overflow: auto;
  }
  pre.src:before {
    display: none;
    position: absolute;
    top: -8px;
    right: 12px;
    padding: 3px;
    color: #555;
    background-color: #f2f2f299;
  }
  pre.src:hover:before { display: inline; margin-top: 14px;}
  /* Languages per Org manual */
  pre.src-asymptote:before { content: 'Asymptote'; }
  pre.src-awk:before { content: 'Awk'; }
  pre.src-authinfo::before { content: 'Authinfo'; }
  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 { }
</style>
</head>
<body>
<div id="content" class="content">
<h1 class="title">The Seasoned Schemer Notes
<br />
<span class="subtitle">Chapter 13</span>
</h1>
<div id="table-of-contents" role="doc-toc">
<h2>Table of Contents</h2>
<div id="text-table-of-contents" role="doc-toc">
<ul>
<li><a href="#prerequisites">1. Prerequisites</a>
<ul>
<li><a href="#prerequisites-y-combinator">1.1. Y-combinator</a></li>
</ul>
</li>
<li><a href="#chapter-13">2. Chapter 13</a>
<ul>
<li><a href="#chapter-13-example">2.1. Example :: Computing the intersection of multiple sets</a>
<ul>
<li><a href="#chapter-13-example-usage">2.1.1. Usage</a></li>
<li><a href="#chapter-13-example-conclusion">2.1.2. Conclusion</a></li>
<li><a href="#chapter-13-example-attempt-fix">2.1.3. Attempt of fixing the issue</a></li>
<li><a href="#chapter-13-example-continuations">2.1.4. Continuations to the rescue</a></li>
<li><a href="#chapter-13-example-optimizations">2.1.5. Further optimization of <code class="src src-scheme">intersect</code> and <code class="src src-scheme">intersectall</code></a></li>
</ul>
</li>
<li><a href="#chapter-13-example-skipping">2.2. Example :: Skipping computation</a></li>
<li><a href="#chapter-13-example-continuations-notes">2.3. Notes about continuations</a>
<ul>
<li><a href="#chapter-13-example-continuations-notes-languages-specifics">2.3.1. Specific language implementations</a></li>
<li><a href="#chapter-13-example-continuations-notes-other-languages">2.3.2. Other languages</a></li>
<li><a href="#chapter-13-example-continuations-notes-other-concepts">2.3.3. Other concepts</a></li>
</ul>
</li>
</ul>
</li>
</ul>
</div>
</div>

<div id="outline-container-prerequisites" class="outline-2">
<h2 id="prerequisites"><span class="section-number-2">1.</span> Prerequisites</h2>
<div class="outline-text-2" id="text-prerequisites">
<div class="org-src-container">
<pre class="src src-scheme" id="orgb8927a7">(define atom?
  (λ (x)
    (and (not (pair? x))
         (not (null? x)))))
</pre>
</div>

<p>
In theory we could define other things as numbers, for example church numerals.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orga569744">(define one?
  (λ (x)
    (= x 1)))
</pre>
</div>

<div class="org-src-container">
<pre class="src src-scheme" id="org6b7d346">(define pick
  (λ (n lat)
    (cond
     [(one? n) (car lat)]
     [else
      (pick (- n 1) (cdr lat))])))
</pre>
</div>
</div>

<div id="outline-container-prerequisites-y-combinator" class="outline-3">
<h3 id="prerequisites-y-combinator"><span class="section-number-3">1.1.</span> Y-combinator</h3>
<div class="outline-text-3" id="text-prerequisites-y-combinator">
<p>
In the first book the Y-combinator was derived. It is again:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgb70ef1b">(define Y
  (λ (proc)
    ((λ (f) (f f))
     (λ (f)
       (proc
        (λ (x) ((f f) x)))))))
</pre>
</div>
</div>
</div>
</div>

<div id="outline-container-chapter-13" class="outline-2">
<h2 id="chapter-13"><span class="section-number-2">2.</span> Chapter 13</h2>
<div class="outline-text-2" id="text-chapter-13">
<p>
Chapter 13 deals with continuations. It shows situations, in which they can be useful. Situations, which before were not encountered. A typical situation is a recursive function, that builds up a result in recursive calls, but only after having potentially built up part of the result, notices that previously built up parts are not needed. This makes sense, when the check for some condition, that tells, that the parts are not needed is too expensive to be done in the average case.
</p>
</div>

<div id="outline-container-chapter-13-example" class="outline-3">
<h3 id="chapter-13-example"><span class="section-number-3">2.1.</span> Example :: Computing the intersection of multiple sets</h3>
<div class="outline-text-3" id="text-chapter-13-example">
<p>
One example the book uses is a function which computes the set intersection between multiple sets, represented by lists, given as a list of lists.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgca3199e">(define intersect
  (λ (set1 set2)
    (letrec ([member?
              (λ (elem lst)
                (member elem lst))]
             [intersect-inner
              (λ (set1°)
                (cond
                 [(null? set1°) '()]
                 [(member? (car set1°) set2)
                  (cons (car set1°)
                        (intersect-inner (cdr set1°)))]
                 [else
                  (intersect-inner (cdr set1°))]))])
      (intersect-inner set1))))
</pre>
</div>

<div class="org-src-container">
<pre class="src src-scheme" id="orgc64d883">
(define intersectall
  (λ (lsts)
    (letrec ([intersectall-inner
              (λ (lsts°)
                (cond
                 [(null? (cdr lsts°)) (car lsts°)]
                 [else
                  (intersect (car lsts°)
                             (intersectall-inner (cdr lsts°)))]))])
      (cond
       [(null? lsts) '()]
       [else
        (intersectall-inner lsts)]))))
</pre>
</div>
</div>

<div id="outline-container-chapter-13-example-usage" class="outline-4">
<h4 id="chapter-13-example-usage"><span class="section-number-4">2.1.1.</span> Usage</h4>
<div class="outline-text-4" id="text-chapter-13-example-usage">
<div class="org-src-container">
<pre class="src src-scheme" id="orgd9b039e">
(simple-format
 #t "~a\n"
 (intersect '(a b c) '(c d e)))


(simple-format
 #t "~a\n"
 (intersectall '((a b c)
                 (c d e)
                 (f c))))

(simple-format
 #t "~a\n"
 (intersectall '((a b c)
                 (c d e)
                 ()
                 (f g c))))
</pre>
</div>

<pre class="example" id="org2f8dd34">
(c)
(c)
()
</pre>
</div>
</div>

<div id="outline-container-chapter-13-example-conclusion" class="outline-4">
<h4 id="chapter-13-example-conclusion"><span class="section-number-4">2.1.2.</span> Conclusion</h4>
<div class="outline-text-4" id="text-chapter-13-example-conclusion">
<p>
The problem with this definition of <code>intersectall</code> is, that even if a list in the call:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org7bffcc3">...
(intersect (car lsts°)
           (intersectall-inner (cdr lsts°)))
...
</pre>
</div>

<p>
in <code>intersectall-inner</code> is empty, <code>intersectall-inner</code> in its iterations continues to call <code>intersect</code> with that empty list as a first argument. Continuing to call <code>intersect</code> is unnecessary work. Any intersection with an empty set will result in an empty set, in this case represented by an empty list. Any in previous iterations already computed partial intersection is useless as well. In fact the longer the already computed intersection is, the more work <code>intersect</code> will perform, because it iterates over the set members, checking, whether they are <code>member?</code> of the other set.
</p>

<p>
Ideally, even though the result computed by <code>intersectall</code> is correct, one would want to avoid this extra work being performed.
</p>

<p>
However, since the unnecessary expense of the computation is not noticed by any conditional in the code, it is not avoided.
</p>
</div>
</div>

<div id="outline-container-chapter-13-example-attempt-fix" class="outline-4">
<h4 id="chapter-13-example-attempt-fix"><span class="section-number-4">2.1.3.</span> Attempt of fixing the issue</h4>
<div class="outline-text-4" id="text-chapter-13-example-attempt-fix">
<p>
It is also not simple to rewrite <code>intersectall-inner</code> to perform such a check. For example the following does not eliminate all redundant work:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgd8a6cd1">
(define intersectall
  (λ (lsts)
    (letrec ([intersectall-inner
              (λ (lsts°)
                (cond
                 [(null? (car lsts°)) '()]  ; added check
                 [(null? (cdr lsts°)) (car lsts°)]
                 [else
                  (intersect (car lsts°)
                             (intersectall-inner (cdr lsts°)))]))])
      (cond
       [(null? lsts) '()]
       [else
        (intersectall-inner lsts)]))))
</pre>
</div>

<p>
Why does this not eliminate all redundant work? Because the return value of the check <code class="src src-scheme">[(null? (car lsts°)) '()]</code>, the empty list, will still be used as an argument in calls of <code>intersect</code> in the <code>else</code> branch of the <code>cond</code> in earlier iterations of <code>intersectall-inner</code>. Ideally one would avoid even calling <code>intersect</code> with any empty lists resulting from calls to <code>intersectall-inner</code>.
</p>
</div>
</div>

<div id="outline-container-chapter-13-example-continuations" class="outline-4">
<h4 id="chapter-13-example-continuations"><span class="section-number-4">2.1.4.</span> Continuations to the rescue</h4>
<div class="outline-text-4" id="text-chapter-13-example-continuations">
<p>
Fortunately, there is a good way to do so! Enter continuations.
</p>

<p>
We can store a continuation of the program before <code>intersectall-inner</code> is ever called. That continuation takes an argument, which is the result of <code>intersectall-inner</code>. This way the continuation acts as means to do an early exit, no matter where the execution of <code>intersectall-inner</code> is, when it notices, that there is an empty list as return value of an <code>intersectall-inner</code> call. This is called an exit<sup><a id="fnr.1" class="footref" href="#fn.1" role="doc-backlink">1</a></sup> continuation.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org062f828">
(define intersectall
  (λ (lsts)
    (call-with-current-continuation
     (λ (exit)
       (letrec ([intersectall-inner
                 (λ (lsts°)
                   (cond
                    [(null? (car lsts°)) (exit '())]  ; exit continuation call
                    [(null? (cdr lsts°)) (car lsts°)]
                    [else
                     (intersect (car lsts°)
                                (intersectall-inner (cdr lsts°)))]))])
         (cond
          [(null? lsts) '()]
          [else
           (intersectall-inner lsts)]))))))
</pre>
</div>

<p>
<code>intersectall-inner</code> can be used just like before.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org7a04a78">
(simple-format
 #t "~a\n"
 (intersect '(a b c) '(c d e)))


(simple-format
 #t "~a\n"
 (intersectall '((a b c)
                 (c d e)
                 (f c))))

(simple-format
 #t "~a\n"
 (intersectall '((a b c)
                 (c d e)
                 ()
                 (f g c))))
</pre>
</div>

<pre class="example" id="orgdd28c15">
(c)
(c)
()
</pre>
</div>
</div>

<div id="outline-container-chapter-13-example-optimizations" class="outline-4">
<h4 id="chapter-13-example-optimizations"><span class="section-number-4">2.1.5.</span> Further optimization of <code class="src src-scheme">intersect</code> and <code class="src src-scheme">intersectall</code></h4>
<div class="outline-text-4" id="text-chapter-13-example-optimizations">
<p>
However, there is still an issue with the definition of <code class="src src-scheme">intersect</code> as defined above:
</p>

<div class="org-src-container">
<pre class="src src-scheme">(define intersect
  (λ (set1 set2)
    (letrec ([member?
              (λ (elem lst)
                (member elem lst))]
             [intersect-inner
              (λ (set1°)
                (cond
                 [(null? set1°) '()]
                 [(member? (car set1°) set2)
                  (cons (car set1°)
                        (intersect-inner (cdr set1°)))]
                 [else
                  (intersect-inner (cdr set1°))]))])
      (intersect-inner set1))))
</pre>
</div>

<p>
When <code class="src src-scheme">intersect</code> receives an empty list as a second argument. <code class="src src-scheme">intersect-inner</code> will still go through all of the elements of the first argument and check, whether they are <code class="src src-scheme">member?</code> of the second argument. Inside <code class="src src-scheme">intersect-inner</code> the conditional never asks any questions about the second argument. It only ever asks things about the first argument. So the implementation cannot detect, that it is doing unnecessary work. Ideally we would not do any unnecessary work, of course.
</p>

<p>
We can easily add a check for an empty list as second argument:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org1c47de9">(define intersect
  (λ (set1 set2)
    (letrec ([member?
              (λ (elem lst)
                (member elem lst))]
             [intersect-inner
              (λ (set1°)
                (cond
                 [(null? set1°) '()]
                 [(member? (car set1°) set2)
                  (cons (car set1°)
                        (intersect-inner (cdr set1°)))]
                 [else
                  (intersect-inner (cdr set1°))]))])
      ;; added conditional
      (cond
       [(null? set2) '()]
       [else
        ;; still same call to intersect-inner
        (intersect-inner set1)]))))
</pre>
</div>

<p>
Lets try it. Define <code class="src src-scheme">intersectall</code> in terms of the new <code class="src src-scheme">intersect</code>:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgda6dbc4">(define intersect
  (λ (set1 set2)
    (letrec ([member?
              (λ (elem lst)
                (member elem lst))]
             [intersect-inner
              (λ (set1°)
                (cond
                 [(null? set1°) '()]
                 [(member? (car set1°) set2)
                  (cons (car set1°)
                        (intersect-inner (cdr set1°)))]
                 [else
                  (intersect-inner (cdr set1°))]))])
      ;; added conditional
      (cond
       [(null? set2) '()]
       [else
        ;; still same call to intersect-inner
        (intersect-inner set1)]))))


(define intersectall
  (λ (lsts)
    (call-with-current-continuation
     (λ (exit)
       (letrec ([intersectall-inner
                 (λ (lsts°)
                   (cond
                    [(null? (car lsts°)) (exit '())]  ; exit continuation call
                    [(null? (cdr lsts°)) (car lsts°)]
                    [else
                     (intersect (car lsts°)
                                (intersectall-inner (cdr lsts°)))]))])
         (cond
          [(null? lsts) '()]
          [else
           (intersectall-inner lsts)]))))))
</pre>
</div>

<p>
<code>intersectall-inner</code> can be used just like before.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org1b9ce6b">
(simple-format
 #t "~a\n"
 (intersect '(a b c) '(c d e)))


(simple-format
 #t "~a\n"
 (intersectall '((a b c)
                 (c d e)
                 (f c))))

(simple-format
 #t "~a\n"
 (intersectall '((a b c)
                 (c d e)
                 ()
                 (f g c))))
</pre>
</div>

<pre class="example" id="orgfdf2113">
(c)
(c)
()
</pre>

<p>
That is nice. However we are not checking in <code class="src src-scheme">intersectall</code>, whether <code class="src src-scheme">intersect</code> gives an empty list as a return value, which will be the return value of <code class="src src-scheme">intersectall</code> and so we might call <code class="src src-scheme">intersect</code> unnecessarily with an empty list as second argument in iterations further up the stack. Instead, we could check for the result being the empty list. However, then we would check the same fact twice: Once inside <code class="src src-scheme">intersect</code> and then again when <code class="src src-scheme">intersect</code> returns in <code class="src src-scheme">intersectall</code>. Again unnecessary work.
</p>

<p>
What we could do instead, is to let <code class="src src-scheme">intersect</code> use the continuation created in <code class="src src-scheme">intersectall</code>, once <code class="src src-scheme">intersect</code> finds, that one of its arguments is an empty list.
</p>

<p>
There are at least 2 ways we can do this:
</p>

<ol class="org-ol">
<li>passing the continuation<sup><a id="fnr.2" class="footref" href="#fn.2" role="doc-backlink">2</a></sup> to <code class="src src-scheme">intersect</code></li>
<li>moving <code class="src src-scheme">intersect</code> into <code class="src src-scheme">intersectall</code>, so that the continuation is accessible for <code class="src src-scheme">intersect</code></li>
</ol>

<p>
Option 1 is maybe not so great, since it requires <code class="src src-scheme">intersect</code> to have an additional argument, which the caller might need to be aware of, or use optional arguments.
</p>

<p>
Option 2 is used in the book, but it also comes with a problem: <code class="src src-scheme">intersect</code> is a useful function in itself. Moving it into <code class="src src-scheme">intersectall</code> will make it impossible to use merely <code class="src src-scheme">intersect</code>, instead of <code class="src src-scheme">intersectall</code>. It will also make it impossible to write a unit test for <code class="src src-scheme">intersect</code>. Perhaps the idea of the book is to simply always use <code class="src src-scheme">intersectall</code> and wrap 2 arguments in a list, if one only needs the intersection of 2 sets. Or the idea is merely to have a case to show what continuations are and how they can be used to great effect.
</p>

<p>
So lets roll with option 2:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org30ee72f">(define intersectall
  (λ (lsts)
    (call-with-current-continuation
     (λ (exit)
       (letrec ([intersect
                 ;; added internal definition of intersect
                 (λ (set1 set2)
                   (letrec ([member?
                             (λ (elem lst)
                               (member elem lst))]
                            [intersect-inner
                             (λ (set1°)
                               (cond
                                [(null? set1°) '()]
                                [(member? (car set1°) set2)
                                 (cons (car set1°)
                                       (intersect-inner (cdr set1°)))]
                                [else
                                 (intersect-inner (cdr set1°))]))])
                     (cond
                      ;; now calling the exit continuation
                      [(null? set2) (exit '())]
                      [else
                       (intersect-inner set1)])))]
                [intersectall-inner
                 (λ (lsts°)
                   (cond
                    [(null? (car lsts°)) (exit '())]
                    [(null? (cdr lsts°)) (car lsts°)]
                    [else
                     (intersect (car lsts°)
                                (intersectall-inner (cdr lsts°)))]))])
         (cond
          [(null? lsts) '()]
          [else
           (intersectall-inner lsts)]))))))
</pre>
</div>

<p>
Lets try it:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org14c816e">
(simple-format
 #t "~a\n"
 (intersectall '((a b c)
                 (c d e)
                 (f c))))

(simple-format
 #t "~a\n"
 (intersectall '((a b c)
                 (c d e)
                 ()
                 (f g c))))
</pre>
</div>

<pre class="example" id="org003a3d8">
(c)
()
</pre>

<p>
Still works!
</p>
</div>
</div>
</div>

<div id="outline-container-chapter-13-example-skipping" class="outline-3">
<h3 id="chapter-13-example-skipping"><span class="section-number-3">2.2.</span> Example :: Skipping computation</h3>
<div class="outline-text-3" id="text-chapter-13-example-skipping">
<p>
Another example for how continuations can be useful is skipping of computation or restarting computation with different state and thereby intentionally forgetting computation, that happened after the continuation was created. The example used in the book is the removal of all elements of a list up to and including the last occurrence of an element, that satisfies some predicate. The problem is, that in only 1 linear pass through the list, one does not know, whether one is removing too much of the list, because no later occurrence of such an element exists.
</p>

<p>
Here is a more flexible version of the code in the book, which also makes the predicate specifiable:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org46b4711">(define rember-up-to-last
  (λ (lst pred)
    (call-with-current-continuation
     (λ (restart)
       (letrec ([rember-inner
                 (λ (lst°)
                   (cond
                    [(null? lst°) '()]
                    [(pred (car lst°))
                     (restart (rember-inner (cdr lst°)))]
                    [else
                     (cons (car lst°)
                           (rember-inner (cdr lst°)))]))])
         (rember-inner lst))))))
</pre>
</div>

<p>
We want to forget, what we accumulated in the <code class="src src-scheme">else</code> branch, if we find another predicate satisfying list element. For that we use the continuation named <code class="src src-scheme">restart</code>. We restart the accumulation of the result by using <code class="src src-scheme">(rember-inner (cdr lst°))</code> in place of previous stack frames, that memorized accumulating other elements into a result.
</p>

<p>
Lets use it:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgb165748">
(simple-format
 #t "~a\n"
 (rember-up-to-last '(8 5 6 0 3 4 9 3 1)
                    (λ (num) (even? num))))
</pre>
</div>

<pre class="example" id="org1c918c8">
(9 3 1)
</pre>
</div>
</div>

<div id="outline-container-chapter-13-example-continuations-notes" class="outline-3">
<h3 id="chapter-13-example-continuations-notes"><span class="section-number-3">2.3.</span> Notes about continuations</h3>
<div class="outline-text-3" id="text-chapter-13-example-continuations-notes">
</div>

<div id="outline-container-chapter-13-example-continuations-notes-languages-specifics" class="outline-4">
<h4 id="chapter-13-example-continuations-notes-languages-specifics"><span class="section-number-4">2.3.1.</span> Specific language implementations</h4>
<div class="outline-text-4" id="text-chapter-13-example-continuations-notes-languages-specifics">
<p>
The implementation using continuations is conceptually neat. However, in practice one needs to look out for language implementation specifics. For example GNU Guile's documentation mentions:
</p>

<blockquote>
<p>
Continuations are a powerful mechanism, and can be used to implement almost any sort of control structure, such as loops, coroutines, or exception handlers.
</p>

<p>
However the implementation of continuations in Guile is not as efficient as one might hope, because Guile is designed to cooperate with programs written in other languages, such as C, which do not know about continuations. Basically continuations are captured by a block copy of the stack, and resumed by copying back.
</p>

<p>
For this reason, continuations captured by call/cc should be used only when there is no other simple way to achieve the desired result, or when the elegance of the continuation mechanism outweighs the need for performance.
</p>

<p>
Escapes upwards from loops or nested functions are generally best handled with prompts (see Prompts). Coroutines can be efficiently implemented with cooperating threads (a thread holds a full program stack but doesn’t copy it around the way continuations do).
</p>

<p>
&#x2013; <a href="https://www.gnu.org/software/guile/manual/html_node/Continuations.html">https://www.gnu.org/software/guile/manual/html_node/Continuations.html</a> (2023-02-22)
</p>
</blockquote>

<p>
So in a specific Scheme dialect like GNU Guile, one should weigh the costs of the elegance of an implementation using continuations against desired performance and consider other concepts like exceptions and prompts.
</p>
</div>
</div>

<div id="outline-container-chapter-13-example-continuations-notes-other-languages" class="outline-4">
<h4 id="chapter-13-example-continuations-notes-other-languages"><span class="section-number-4">2.3.2.</span> Other languages</h4>
<div class="outline-text-4" id="text-chapter-13-example-continuations-notes-other-languages">
<p>
Another language, that is so nice to offer continuations, is Standard ML. See <a href="https://www.smlnj.org/doc/SMLofNJ/pages/cont.html">https://www.smlnj.org/doc/SMLofNJ/pages/cont.html</a>.
</p>
</div>
</div>

<div id="outline-container-chapter-13-example-continuations-notes-other-concepts" class="outline-4">
<h4 id="chapter-13-example-continuations-notes-other-concepts"><span class="section-number-4">2.3.3.</span> Other concepts</h4>
<div class="outline-text-4" id="text-chapter-13-example-continuations-notes-other-concepts">
<p>
This section discusses other language concepts, that one could employ to get the same result.
</p>
</div>

<div id="outline-container-chapter-13-example-continuations-notes-other-concepts-return-statement" class="outline-5">
<h5 id="chapter-13-example-continuations-notes-other-concepts-return-statement"><span class="section-number-5">2.3.3.1.</span> Return statement</h5>
<div class="outline-text-5" id="text-chapter-13-example-continuations-notes-other-concepts-return-statement">
<p>
In many languages a <code>return</code> statement might be used to return early. However, this requires there to be a <code>return</code> <i>statement</i> in the language. For functional languages having statements like <code>return</code> does not make much sense, because everything or almost everything is an expression. Furthermore a <code>return</code> keyword is unnecessary to have in the language, as we have shown by effectively creating our own exit function using a continuation. A <code>return</code> statement can be seen as clutter in a language's syntax definition. Even some languages which do not prioritize functional programming have opted to not have a <code>return</code> statement. See Rust for example.
</p>

<p>
Having all things be expressions has loads of advantages. Everything can be expected to return some value. Everything can be moved around in the code and placed in other places, without for example worrying about things like it being correct or incorrect syntax to use a conditional inside another expression. Expressions make code more flexible. When languages mix expressions and statements, it can mean a much more complicated language and grammar of the language's syntax in the end. Look for example at Python and its <code>if</code> constructs. It has many special cases and inline syntax, that needs to be explicitly added to the language's syntax. For languages which handle these things as expressions there is no surprise, that one can use conditionals wherever one wants to. There is simply nothing special about conditionals.
</p>
</div>
</div>

<div id="outline-container-chapter-13-example-continuations-notes-other-concepts-exceptions" class="outline-5">
<h5 id="chapter-13-example-continuations-notes-other-concepts-exceptions"><span class="section-number-5">2.3.3.2.</span> Exceptions</h5>
<div class="outline-text-5" id="text-chapter-13-example-continuations-notes-other-concepts-exceptions">
<p>
If not a <code>return</code> statement, then maybe an exception could be used to the same result? It could, but exceptions are actually meant to be used for exceptional circumstances and not for regular control flow. Using them for regular control flow is usually making it harder to read the code. If an exception is raised, it should be caught somewhere else in the code. That is more code. Also an exception type needs to be defined or an appropriate one already needs to exist. Also note, that using continuations one can implement exceptions in ones language. Using a continuation is using a more fundamental building block, a more basic concept.
</p>
</div>
</div>

<div id="outline-container-chapter-13-example-continuations-notes-other-concepts-prompts" class="outline-5">
<h5 id="chapter-13-example-continuations-notes-other-concepts-prompts"><span class="section-number-5">2.3.3.3.</span> Prompts</h5>
<div class="outline-text-5" id="text-chapter-13-example-continuations-notes-other-concepts-prompts">
<p>
I do not yet know enough about prompts and their semantics to judge, whether they are conceptually fitting for being used instead of continuations. Them being mentioned in the GNU Guile manual makes me hopeful though, that they are indeed an appropriate concept to use in place of continuations.
</p>
</div>
</div>
</div>
</div>
</div>
<div id="footnotes">
<h2 class="footnotes">Footnotes: </h2>
<div id="text-footnotes">

<div class="footdef"><sup><a id="fn.1" class="footnum" href="#fnr.1" role="doc-backlink">1</a></sup> <div class="footpara" role="doc-footnote"><p class="footpara">or "escape"?</p></div></div>

<div class="footdef"><sup><a id="fn.2" class="footnum" href="#fnr.2" role="doc-backlink">2</a></sup> <div class="footpara" role="doc-footnote"><p class="footpara">Uh oh! Continuation Passing Style lurking!</p></div></div>


</div>
</div></div>
<div id="postamble" class="status">
<p class="date">Date: 2023-02-26 So 00:00</p>
<p class="author">Author: Zelphir Kaltstahl</p>
<p class="date">Created: 2023-02-26 So 16:12</p>
<p class="validation"><a href="https://validator.w3.org/check?uri=referer">Validate</a></p>
</div>
</body>
</html>