ZelphirKaltstahl
/
the-seasoned-schemer-notes


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795
							<?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-11-26 Sun 11:55 -->
<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 14</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></li>
<li><a href="#chapter-14">2. Chapter 14</a>
<ul>
<li><a href="#chapter-14-attempt-leftmost">2.1. Attempt to write <code class="src src-scheme">leftmost</code></a></li>
<li><a href="#chapter-14-attempt-rember-1-asterisk">2.2. Attempt to write <code class="src src-scheme">rember1*</code></a></li>
<li><a href="#chapter-14-avoid-conditionals">2.3. Using continuations to avoid conditionals</a></li>
<li><a href="#chapter-14-continuations-needed">2.4. When are continuations "needed"?</a>
<ul>
<li><a href="#chapter-14-continuations-needed-success-of-recursive-calls">2.4.1. Unknown success for recursive calls</a></li>
</ul>
</li>
<li><a href="#chapter-14-continuations-for-control-flow">2.5. Using continuations to build other control flow forms</a></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">
<p>
<code class="src src-scheme">atom?</code> checks, whether a thing is a non-compound thing, at least for simple code, that does not make use of vector and such things.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org218a286">(define atom?
  (λ (x)
    (and (not (pair? x))
         (not (null? x)))))
</pre>
</div>
</div>
</div>

<div id="outline-container-chapter-14" class="outline-2">
<h2 id="chapter-14"><span class="section-number-2">2.</span> Chapter 14</h2>
<div class="outline-text-2" id="text-chapter-14">
<ul class="org-ul">
<li>This chapter introduces <code class="src src-scheme">if</code>.</li>
<li>This chapter introduces <code class="src src-scheme">letcc</code> and <code class="src src-scheme">call-with-current-continuation</code>.</li>
<li>This chapter introduces <code class="src src-scheme">try</code>.</li>
<li>This chapter shows more ways of making use of continuations for various purposes.</li>
</ul>
</div>

<div id="outline-container-chapter-14-attempt-leftmost" class="outline-3">
<h3 id="chapter-14-attempt-leftmost"><span class="section-number-3">2.1.</span> Attempt to write <code class="src src-scheme">leftmost</code></h3>
<div class="outline-text-3" id="text-chapter-14-attempt-leftmost">
<p>
<code class="src src-scheme">leftmost</code> returns the leftmost atom of a nested list or tree.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgdfd105b">
(define leftmost
  (λ (lst)
    (cond
     [(null? lst) '()]
     [(atom? (car lst))
      (car lst)]
     ;; We know car of lst is not an atom and it is not null?, so
     ;; it must be at least a pair. We have to try to find the
     ;; leftmost element in that pair.
     [else
      (leftmost (car lst))])))
</pre>
</div>

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

<pre class="example" id="org723727f">
()
</pre>

<p>
But this is not correct. The leftmost element should be <code class="src src-scheme">'c</code>. Maybe we can try to find the leftmost element in the <code class="src src-scheme">car</code> of <code class="src src-scheme">lst</code> and if we do not find it, search in the <code class="src src-scheme">cdr</code> of <code class="src src-scheme">lst</code>:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org09859b6">
(define leftmost
  (λ (lst)
    (cond
     [(null? lst) '()]
     [(atom? (car lst))
      (car lst)]
     [else
      (let ([leftmost-of-car (leftmost (car lst))])
        (cond
         [(null? leftmost-of-car) (leftmost (cdr lst))]
         [else leftmost-of-car]))])))
</pre>
</div>

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

<pre class="example" id="org2fbff11">
c
f
</pre>

<p>
This seems to work. No continuations needed so far.
</p>

<p>
The book has a slightly better solution, which asks <code class="src src-scheme">atom?</code> instead of <code class="src src-scheme">null?</code> about the <code class="src src-scheme">leftmost</code> of the <code class="src src-scheme">car</code> of a list. This is clearer, since we are actually interested in getting the <code class="src src-scheme">leftmost</code> atom, and not the <code class="src src-scheme">leftmost</code> <code class="src src-scheme">null?</code> and as such do not need to invert the thinking. My solution also works, but only because it has the convention of returning <code class="src src-scheme">'()</code> when <code class="src src-scheme">(null? lst)</code> is <code class="src src-scheme">#t</code>. The book's solution does not rely on the returned thing being exactly <code class="src src-scheme">'()</code>, so it has fewer conventions backed in and is more flexible than my solution.
</p>
</div>
</div>

<div id="outline-container-chapter-14-attempt-rember-1-asterisk" class="outline-3">
<h3 id="chapter-14-attempt-rember-1-asterisk"><span class="section-number-3">2.2.</span> Attempt to write <code class="src src-scheme">rember1*</code></h3>
<div class="outline-text-3" id="text-chapter-14-attempt-rember-1-asterisk">
<p>
<code class="src src-scheme">rember1*</code> removes the leftmost occurrence of an element satisfying a predicate from an arbitrarily nested list. The version in the book works with atoms. My version here should work even with compound values.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org79a14e9">(import (srfi srfi-11))


(define rember1*
  (λ (lst pred)
    (letrec ([rember-inner
              (λ (lst)
                (cond
                 [(null? lst) (values #f '())]
                 [(pred (car lst)) (values #t (cdr lst))]
                 [(atom? (car lst))
                  (let-values ([(changed-flag result-of-cdr)
                                (rember-inner (cdr lst))])
                    (values changed-flag
                            (cons (car lst)
                                  result-of-cdr)))]
                 [else
                  (let-values ([(changed-flag result-of-car)
                                (rember-inner (car lst))])
                    (cond
                     [changed-flag
                      (values changed-flag
                              (cons result-of-car (cdr lst)))]
                     [else
                      (let-values ([(changed-flag result-of-cdr)
                                    (rember-inner (cdr lst))])
                        (values changed-flag
                                (cons (car lst)
                                      result-of-cdr)))]))]))])
      (let-values ([(changed-flag result)
                    (rember-inner lst)])
        result))))
</pre>
</div>

<div class="org-src-container">
<pre class="src src-scheme" id="org549a651">
(simple-format
 #t "~a\n"
 (rember1* '(a (e f g) b (d e f) c d)
           (λ (elem) (eq? elem 'e))))

(simple-format
 #t "~a\n"
 (rember1* '(a (f g) b (d e f) c d)
           (λ (elem) (eq? elem 'e))))

(simple-format
 #t "~a\n"
 (rember1* '(a (f g) b (d f) c d)
           (λ (elem) (eq? elem 'e))))

(simple-format
 #t "~a\n"
 (rember1* '(a (e f g) b (d e f) c d)
           (λ (elem) (equal? elem '(e f g)))))
</pre>
</div>

<pre class="example" id="org66b2cb5">
(a (f g) b (d e f) c d)
(a (f g) b (d f) c d)
(a (f g) b (d f) c d)
(a b (d e f) c d)
</pre>

<p>
This works, but the whole <code class="src src-scheme">let-values</code> thing is a bit cumbersome. Furthermore <code class="src src-scheme">let-values</code> has not been introduced in the book at that point. One could of course use a pair or list as a result type as well. Maybe the book has a better solution? Maybe some clever idea with a continuation?
</p>

<p>
The book solves it with an equality function <code class="src src-scheme">eqlist?</code>, which is used to compare the <code class="src src-scheme">car</code> of the list, with the <code class="src src-scheme">car</code> of the list, that potentially has an element removed. Depending on the result of that comparison, it decides to also apply <code class="src src-scheme">rember1*</code> whether to the <code class="src src-scheme">cdr</code> of the list or not. There is an inefficiency in that solution though: We already know, whether we changed something by removing an element of the list in the <code class="src src-scheme">car</code> of the list. If we could return that information, we would not need to do any comparison. This is done in my solution using <code class="src src-scheme">let-values</code>, but could also be done using a pair or list, if one wanted to avoid <code class="src src-scheme">let-values</code>.
</p>
</div>
</div>

<div id="outline-container-chapter-14-avoid-conditionals" class="outline-3">
<h3 id="chapter-14-avoid-conditionals"><span class="section-number-3">2.3.</span> Using continuations to avoid conditionals</h3>
<div class="outline-text-3" id="text-chapter-14-avoid-conditionals">
<p>
The idea is, that often one already knows some fact deeper in recursive calls, but loses that knowledge, when returning values to earlier recursive calls, so one should make use of the knowledge at deeper levels of recursion.
</p>

<p>
Sometimes it takes multiple levels of recursive calls to get to the decisive facts or knowledge. One does not always know ahead of time how to process the return value of recursive calls. It can for example happen, that there is a success case and a failure case. In the success case one might want to put the result values in some kind of data structure (say a list by using cons for example) and in the failure case one might not want to do anything at all with the return values. But one cannot know at this level of recursion whether it will be a success or failure case. Optimistically adding the return values to a data structure might lead to a wrong result. Discarding the return values pessimistically might overlook correct or relevant return values and also lead to a wrong result.
</p>

<p>
There are a few ideas how this can be handled in general:
</p>

<ol class="org-ol">
<li>Run checks on the returned values of recursive calls. Possibly performing redundant checks that already ran as part of deeper levels of recursive calls.</li>
<li>Return all required knowledge in return values up to earlier recursive calls, not merely returning the usual return value, but also knowledge or facts. For example by returning a list or multiple values. The returned knowledge should have a representation, which allows for low-cost checks by the level of the recursion, that needs to run checks on that knowledge. For example the additionally returned facts could be booleans and a check could be, whether some boolean is true or false.</li>
<li>Create a kind of entrypoint to further execution, a continuation, and pass it along with in recursive calls, so that deeper levels of the recursion can decide whether or not to make use of that continuation, depending on their knowledge.</li>
<li>The ugly one: Use an exception, even though no actually exceptional situation is encountered, to jump back to where that exception is handled. This can be seen as a special case of using a continuation though.</li>
<li>Use an other kind of concept that the language used offers. For example GNU Guile offers something called "prompts".</li>
</ol>

<p>
Here we take a look at option 3, using continuations to avoid redundant checks.
</p>

<p>
The following function shows a way to avoid checking the result of a recursive call.
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgd04bad3">
(define leftmost
  (λ (lst)
    (call-with-current-continuation
     (λ (return)
       (define inner
         (λ (lst°)
           (cond
            [(null? lst°) '()]
            [(atom? (car lst°)) (return (car lst°))]
            [else
             (inner (car lst°))
             (inner (cdr lst°))])))
       (inner lst)))))
</pre>
</div>

<p>
What happens here?
</p>

<p>
The first call to <code class="src src-scheme">inner</code> inside the <code class="src src-scheme">else</code> branch of the <code class="src src-scheme">cond</code> may or may not find an <code class="src src-scheme">atom?</code> in the <code class="src src-scheme">car</code>. If it finds an <code class="src src-scheme">atom?</code>, it will call the continuation <code class="src src-scheme">return</code> to return it and we forget about running all other memorized calls to <code class="src src-scheme">inner</code>. If it does not find an <code class="src src-scheme">atom?</code>, it will return the empty list <code class="src src-scheme">'()</code>. Nothing is done with that return value and the second call to <code class="src src-scheme">inner</code> with the <code class="src src-scheme">cdr</code> of the list is performed.
</p>

<p>
We could have checked the return value instead, to see whether it is an <code class="src src-scheme">atom?</code> or the empty list and based on that decide to search for a <code class="src src-scheme">leftmost</code> <code class="src src-scheme">atom?</code> in the <code class="src src-scheme">cdr</code>, but that check would have been redundant, since we already know, whether it is an <code class="src src-scheme">atom?</code> in a deeper recursion.
</p>

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

(simple-format
 #t "~a\n"
 (leftmost '((()) b (c))))

(simple-format
 #t "~a\n"
 (leftmost '(((c a)) b (c))))

(simple-format
 #t "~a\n"
 (leftmost '(())))

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

<pre class="example" id="orgc5a5ebe">
a
b
c
()
a
</pre>
</div>
</div>

<div id="outline-container-chapter-14-continuations-needed" class="outline-3">
<h3 id="chapter-14-continuations-needed"><span class="section-number-3">2.4.</span> When are continuations "needed"?</h3>
<div class="outline-text-3" id="text-chapter-14-continuations-needed">
</div>

<div id="outline-container-chapter-14-continuations-needed-success-of-recursive-calls" class="outline-4">
<h4 id="chapter-14-continuations-needed-success-of-recursive-calls"><span class="section-number-4">2.4.1.</span> Unknown success for recursive calls</h4>
<div class="outline-text-4" id="text-chapter-14-continuations-needed-success-of-recursive-calls">
<p>
One scenario in which continuations or another concept that replaces them are needed, when it is not clear at the time of a recursive call, whether the call will achieve the overall goal of the function. For example the book gives code for a function, that removes an element fulfilling a test from an arbitrarily nested list, similar to the following:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org46662cb">
(define rm
  (λ (elem lst back-out)
    (cond
     [(null? lst)
      ;; If the element cannot be found in the list, call the
      ;; continuation back-out, to return to the recursive call and
      ;; forget already accumulated conses.
      (back-out 'no)]
     ;; The next branch checks, whether the car of the list is an atom
     ;; and that atom fulfills the predicate we choose. In this case
     ;; the predicate is, that it needs to be an atom? and that it
     ;; must be eq? to the element we are searching for. But any other
     ;; test would be possible as well.
     [(atom? (car lst))
      (if (eq? (car lst) elem)
          ;; If the car is the element we are looking for, simply drop
          ;; it.
          (cdr lst)
          ;; Otherwise keep the car, but look at the cdr of the list.
          (cons (car lst)
                (rm elem
                    (cdr lst)
                    ;; Keep using the same continuation. There is no
                    ;; need to create a new continuation here. If the
                    ;; element cannot be found in the cdr of the list
                    ;; at all, we want to jump back out to the level
                    ;; above, not back here.
                    back-out)))]
     [else
      (let ([new-car
             ;; Try to remove the element from the car of the list. It
             ;; might or might not exist there. If it exists a
             ;; resulting car will be returned, otherwise rm should
             ;; call the continuation with an atom as an argument.

             ;; Note, that the continuation is created at each point,
             ;; where there is a car and a cdr of the list, and that
             ;; we only jump back out by 1 level. Depending on the
             ;; result of the expression for new-car, we continue from
             ;; that level, potentially having to look at the cdr of
             ;; the list for removing the searched element. Jumping
             ;; back out does not jump all the way up the function
             ;; call stack.
             (call-with-current-continuation
              (λ (back-out)
                (rm elem
                    (car lst)
                    back-out)))])
        ;; Check, whether new-car is an atom?, as in the case, that
        ;; the continuation to back out was called.
        (if (atom? new-car)
            ;; When the element cannot be found in the car of the
            ;; list, the continuation back-out is called using an atom
            ;; 'no. Otherwise it is not called and the result of the
            ;; expression for new-car will be the car of the list with
            ;; that one element being removed. If the new-car is an
            ;; atom, then the element was not removed from it. That
            ;; means the car should stay as is and we need to check
            ;; the cdr of the list for the element to remove.
            (cons (car lst)
                  (rm elem
                      (cdr lst)
                      back-out))
            ;; Otherwise we are done, because the element was already
            ;; removed in new-car. We only need to construct the list
            ;; as a result.
            (cons new-car
                  (cdr lst))))])))
</pre>
</div>

<p>
This function already expects a continuation as an argument. The idea is, that, if element cannot be found in the whole list, the list stays the same. So instead of backing out and trying to remove it from the cdr of the list, a different logic is required: Keep the whole list.:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgb4bc8b5">

(define rember1*
  (λ (elem lst)
    (let ([new-list
           (call-with-current-continuation
            (λ (back-out)
              (rm elem lst back-out)))])
      ;; Here comes the different logic to handle the result of the
      ;; call-with-current-continuation.
      (if (atom? new-list)
          lst
          new-list))))
</pre>
</div>

<p>
We can use it as follows:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org6a7b661">
(simple-format
 #t "~a\n"
 (rember1* 'a '(b c (d (a) e) f g h a)))
</pre>
</div>

<pre class="example" id="org4997e1c">
(b c (d () e) f g h a)
</pre>

<p>
Now contrast this with a function, that is recursive as well, but which does not need continuations. For example the function <code class="src src-scheme">alist-set*</code>, which functionally updates an arbitrarily nested association list:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org842a6e5">

(define alist-set*
  (lambda* (alst keys val #:key (equal-test equal?))
    "Set value VAL inside the alist ALST navigating through its
keys using KEYS to get to the place where VAL shall be the
new value."
    (define traverse
      (λ (alst keys)
        (cond
         [(null? keys) val]
         [(not (alist?-shallow alst))
          (raise-exception
           (make-exception (make-non-continuable-error)
                           (make-exception-with-message "key not found")
                           (make-exception-with-irritants keys)
                           (make-exception-with-origin 'alist-set*)))]
         [(null? alst) (cons (cons (first keys)
                                   val)
                             '())]
         [else
          (let ([current-assoc (first alst)]
                [item-key (car (first alst))])
            (cond
             [(equal-test item-key (first keys))
              ;; Change the value and cons the rest of the list.
              (cons (cons item-key
                          (traverse (cdr current-assoc)
                                    (drop keys 1)))
                    (drop alst 1))]
             [else
              (cons current-assoc
                    (traverse (drop alst 1) keys))]))])))
    (traverse alst keys)))
</pre>
</div>

<p>
Usage:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org0204b2c">
(define myalist '((a . 1)
                  (b .
                     ((d . 4)
                      (e . 5)))
                  (c . 3)))

(simple-format
 #t "~a\n"
 (alist-set* myalist '(c) (list (cons 'f 10)) #:equal-test eq?))
</pre>
</div>

<pre class="example" id="org9c80b05">
((a . 1) (b (d . 4) (e . 5)) (c (f . 10)))
</pre>

<p>
In <code class="src src-scheme">alist-set*</code> we can build up conses correctly without ever building up conses, that we later need to discard, because we get a list of keys, which indicate which association we need to follow, in order to get to the item we are interested in. If such an item does not exist or its keys do not exist, an exception is raised (which could be implemented using continuations, but that would be using continuations for another purpose than <code class="src src-scheme">rm</code> does). If such an item is found, all the conses up to that point are correct and needed. The keys allow us to be sure, that we do not need to back out and look at other associations.
</p>

<p>
We also would not need continuations for <code class="src src-scheme">rm</code>, if it did not only remove one occurrence of the searched element, but all of them. Such a function would not need to forget about conses, but could always check the car and the cdr of a list for occurrences and return for both a potentially updated version. Both branches, the one for the car and the one for the cdr, would always succeed.
</p>
</div>
</div>
</div>

<div id="outline-container-chapter-14-continuations-for-control-flow" class="outline-3">
<h3 id="chapter-14-continuations-for-control-flow"><span class="section-number-3">2.5.</span> Using continuations to build other control flow forms</h3>
<div class="outline-text-3" id="text-chapter-14-continuations-for-control-flow">
<p>
The book shows an intersting control flow form named <code class="src src-scheme">try</code>, which is implemented using continuations. The book uses <code class="src src-scheme">letcc</code>, but here is a slightly different form using <code class="src src-scheme">call-with-current-continuation</code>:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="org4219f7e">(define try
  (λ (proc alternative-proc)
    ;; Remember a continuation, which can be used to return a result
    ;; for try, if proc succeeds. A success continuation.
    (call-with-current-continuation
     (λ (success)
       ;; Create a continuation, which is used in case of failure of
       ;; the given proc.
       (call-with-current-continuation
        (λ (failure)
          ;; The procedure `proc' receives the failure
          ;; continuation. If it ever calls the continuation with any
          ;; value, there will be a result to the
          ;; call-with-current-continuation expression for the failure
          ;; case. The failure case continuation is one expression
          ;; inside the body of a lambda. This means, that after the
          ;; expression is evaluated (has a result), the next
          ;; expression will be evaluated, which is the call to
          ;; `alternative-proc'.

          ;; If instead the call to `proc' returns, without ever
          ;; calling `failure', then `success' is instead called,
          ;; which jumps out of the lambda and forgets/ignores the
          ;; call to `alternative-proc'.

          ;; The result of the call to `success' will be the result of
          ;; the whole expression `try'.
          (success (proc failure))))
       (alternative-proc)))))
</pre>
</div>

<p>
Using this <code class="src src-scheme">try</code> definition, we can rewrite <code class="src src-scheme">rember1*</code>:
</p>

<div class="org-src-container">
<pre class="src src-scheme" id="orgcb78f24">


(define rember1*
  (λ (elem lst)
    (try (λ (failure-cont)
           (rm elem lst failure-cont))
         (λ () lst))))


(simple-format
 #t "success case: removing 'a: ~a\n"
 (rember1* 'a
           '(b c (d (a) e) f g h a)))

(simple-format
 #t "failure case: remaining as is: ~a\n"
 (rember1* 'a
           '(b c (d (x) e) f g h x)))
</pre>
</div>

<pre class="example" id="org75f3195">
success case: removing 'a: (b c (d () e) f g h a)
failure case: remaining as is: (b c (d (x) e) f g h x)
</pre>

<p>
Of course, defining <code class="src src-scheme">try</code> as a macro could even get rid of the need to write the lambdas in the call of <code class="src src-scheme">try</code>, to make it even more natural.
</p>

<p>
This is also a great example of how continuation passing style (CPS) is very powerful and can make special language constructs unnecessary, even if difficult to read to the untrained eye.
</p>
</div>
</div>
</div>
</div>
<div id="postamble" class="status">
<p class="date">Date: 2023-11-26 Sun 00:00</p>
<p class="author">Author: Zelphir Kaltstahl</p>
<p class="date">Created: 2023-11-26 Sun 11:55</p>
<p class="validation"><a href="https://validator.w3.org/check?uri=referer">Validate</a></p>
</div>
</body>
</html>