code.org 23 KB
Prerequisites
(define atom?
(λ (x)
(and (not (pair? x))
(not (null? x)))))
#+end_src
In theory we could define other things as numbers, for example church numerals.
#+NAME: defonep
#+BEGIN_SRC scheme :noweb strip-export :results none :exports code :eval never-export
(define one?
(λ (x)
(= x 1)))
#+end_src
#+NAME: defpick
#+BEGIN_SRC scheme :noweb strip-export :results none :exports code :eval never-export
(define pick
(λ (n lat)
(cond
[(one? n) (car lat)]
[else
(pick (- n 1) (cdr lat))])))
#+end_src
** Y-combinator
:CUSTOM_ID: prerequisites-y-combinator
:END:
In the first book the Y-combinator was derived. It is again:
#+NAME: y-combinator-def
#+begin_src scheme :noweb strip-export :results none :exports code :eval never-export :language guile
(define Y
(λ (proc)
((λ (f) (f f))
(λ (f)
(proc
(λ (x) ((f f) x)))))))
#+end_src
** All prerequisites :noexport:
:CUSTOM_ID: prerequisites-all
:END:
#+NAME: prereq
#+BEGIN_SRC scheme :noweb strip-export :results none :exports none :eval never-export
<<defatom>>
<<defonep>>
<<defpick>>
<<y-combinator-def>>
Chapter 13
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.
Example
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.
(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))))
<> (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)]))))
Usage
<> (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))))
(c) (c) ()
Conclusion
The problem with this definition of intersectall is, that even if a list in the call:
... (intersect (car lsts°) (intersectall-inner (cdr lsts°))) ...
in intersectall-inner is empty, intersectall-inner in its iterations continues to call intersect with that empty list as a first argument. Continuing to call intersect 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 intersect will perform, because it iterates over the set members, checking, whether they are member? of the other set.
Ideally, even though the result computed by intersectall is correct, one would want to avoid this extra work being performed.
However, since the unnecessary expense of the computation is not noticed by any conditional in the code, it is not avoided.
Attempt of fixing the issue
It is also not simple to rewrite intersectall-inner to perform such a check. For example the following does not eliminate all redundant work:
<> (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)]))))
Why does this not eliminate all redundant work? Because the return value of the check src_scheme[:exports code]{[(null? (car lsts°)) '()]}, the empty list, will still be used as an argument in calls of intersect in the else branch of the cond in earlier iterations of intersectall-inner. Ideally one would avoid even calling intersect with any empty lists resulting from calls to intersectall-inner.
Continuations to the rescue
Fortunately, there is a good way to do so! Enter continuations.
We can store a continuation of the program before intersectall-inner is ever called. That continuation takes an argument, which is the result of intersectall-inner. This way the continuation acts as means to do an early exit, no matter where the execution of intersectall-inner is, when it notices, that there is an empty list as return value of an intersectall-inner call. This is called an exit1 continuation.
<> (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)]))))))
intersectall-inner can be used just like before.
<> (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))))
(c) (c) ()
Further optimization of src_scheme[:exports code]{intersect} and src_scheme[:exports code]{intersectall}
However, there is still an issue with the definition of src_scheme[:exports code]{intersect} as defined above:
<>
When src_scheme[:exports code]{intersect} receives an empty list as a second argument. src_scheme[:exports code]{intersect-inner} will still go through all of the elements of the first argument and check, whether they are src_scheme[:exports code]{member?} of the second argument. Inside src_scheme[:exports code]{intersect-inner} 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.
We can easily add a check for an empty list as second argument:
(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)]))))
Lets try it. Define src_scheme[:exports code]{intersectall} in terms of the new src_scheme[:exports code]{intersect}:
<>
(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)]))))))
intersectall-inner can be used just like before.
<> (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))))
(c) (c) ()
That is nice. However we are not checking in src_scheme[:exports code]{intersectall}, whether src_scheme[:exports code]{intersect} gives an empty list as a return value, which will be the return value of src_scheme[:exports code]{intersectall} and so we might call src_scheme[:exports code]{intersect} 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 src_scheme[:exports code]{intersect} and then again when src_scheme[:exports code]{intersect} returns in src_scheme[:exports code]{intersectall}. Again unnecessary work.
What we could do instead, is to let src_scheme[:exports code]{intersect} use the continuation created in src_scheme[:exports code]{intersectall}, once src_scheme[:exports code]{intersect} finds, that one of its arguments is an empty list.
There are at least 2 ways we can do this:
- passing the continuation2 to src_scheme[:exports code]{intersect}
- moving src_scheme[:exports code]{intersect} into src_scheme[:exports code]{intersectall}, so that the continuation is accessible for src_scheme[:exports code]{intersect}
Option 1 is maybe not so great, since it requires src_scheme[:exports code]{intersect} to have an additional argument, which the caller might need to be aware of, or use optional arguments.
Option 2 is used in the book, but it also comes with a problem: src_scheme[:exports code]{intersect} is a useful function in itself. Moving it into src_scheme[:exports code]{intersectall} will make it impossible to use merely src_scheme[:exports code]{intersect}, instead of src_scheme[:exports code]{intersectall}. It will also make it impossible to write a unit test for src_scheme[:exports code]{intersect}. Perhaps the idea of the book is to simply always use src_scheme[:exports code]{intersectall} 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.
So lets roll with option 2:
(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)]))))))
Lets try it:
<> (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))))
(c) ()
Still works!
Example
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.
Here is a more flexible version of the code in the book, which also makes the predicate specifiable:
(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))))))
We want to forget, what we accumulated in the src_scheme[:exports code]{else} branch, if we find another predicate satisfying list element. For that we use the continuation named src_scheme[:exports code]{restart}. We restart the accumulation of the result by using src_scheme[:exports code]{(rember-inner (cdr lst°))} in place of previous stack frames, that memorized accumulating other elements into a result.
Lets use it:
<> (simple-format #t "~a\n" (rember-up-to-last '(8 5 6 0 3 4 9 3 1) (λ (num) (even? num))))
(9 3 1)
Notes about continuations
Specific language implementations
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:
Continuations are a powerful mechanism, and can be used to implement almost any sort of control structure, such as loops, coroutines, or exception handlers.
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.
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.
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).
-- https://www.gnu.org/software/guile/manual/html_node/Continuations.html (2023-02-22)
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.
Other languages
Another language, that is so nice to offer continuations, is Standard ML. See https://www.smlnj.org/doc/SMLofNJ/pages/cont.html.
Other concepts
This section discusses other language concepts, that one could employ to get the same result.
Return statement
In many languages a return statement might be used to return early. However, this requires there to be a return statement in the language. For functional languages having statements like return does not make much sense, because everything or almost everything is an expression. Furthermore a return keyword is unnecessary to have in the language, as we have shown by effectively creating our own exit function using a continuation. A return 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 return statement. See Rust for example.
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 if 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.
Exceptions
If not a return 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.
Prompts
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.
- DEFINITION NOT FOUND
- DEFINITION NOT FOUND