the-little-schemer/chapter-09-and-again-and-again-and-again/code.org

Prerequisites

Prerequisites contain code, which is needed to run examples, but is not given in the same chapter.

(define first car)
(define second cadr)
(define build list)

(define pick
  (lambda (one-based-index lst)
    (cond
     [(null? lst)
      (error "index error, index not in list" one-based-index lst)]
     [(= one-based-index 1)
      (car lst)]
     [else
      (pick (- one-based-index 1) (cdr lst))])))

(define atom?
  (lambda (something)
    (and (not (pair? something))
         (not (null? something)))))

(define revpair
  (lambda (pair)
    (build (second pair)
           (first pair))))

(define even?
  (lambda (num)
    (= (remainder num 2) 0)))

Chapter code

looking

<<prerequisites>>

(define looking
  (lambda (elem list-of-atoms)
    (keep-looking elem (pick 1 list-of-atoms) list-of-atoms)))

(define keep-looking
  (lambda (searched-symbol current-list-elem list-of-atoms)
    (cond
     [(number? current-list-elem)
      (keep-looking searched-symbol
                    (pick current-list-elem list-of-atoms)
                    list-of-atoms)]
     [else
      (eq? searched-symbol current-list-elem)])))

Examples where looking finds the symbol:

<<looking>>

(looking 'apple '(2 3 4 5 6 apple))
(looking 'apple '(2 10 5 7 6 4 apple 1 1 3))

#t

Examples where looking does not find the symbol:

<<looking>>

(looking 'apple '(2 3 4 5 6 tea))
(looking 'apple '(2 10 5 7 6 4 orange 1 1 3))

#f

Examples that run forever:

<<looking>>

(looking 'apple '(1))
(looking 'apple '(2 1))

The fact that there are examples, for which looking does not return a value, means, that the function is not total, but is partial instead.

eternity

eternity is an endlessly recursive procedure. Once it is called anywhere, the execution will be trapped in recurring over and over again.

(define eternity
  (lambda (something)
    (eternity something)))

shift

shift changes the structure of sublists in a list.

<<prerequisites>>

(define shift
  (lambda (list-with-sublists)
    (build (first (first list-with-sublists))
           (build (second (first list-with-sublists))
                  (second list-with-sublists)))))

#

<<shift>>

(display
 (simple-format #f "unshifted: ~a\n"
                '((a b) (c d))))

(display
 (simple-format #f "shifted: ~a\n"
                (shift '((a b) (c d)))))

unshifted: ((a b) (c d))
shifted: (a (b (c d)))

align

(define align
  (lambda (pair-or-atom)
    (cond
     [(atom? pair-or-atom)
      pair-or-atom]
     [(pair? (car pair-or-atom))
      (align (shift pair-or-atom))]
     [else
      (build (first pair-or-atom)
             (align (second pair-or-atom)))])))

Weighting function, length* and weight*

This is about defining a procedure to estimate how long a procedure will need for evaluating with a given input. This is called length* in the book.

<<prerequisites>>

(define length*
  (lambda (pair-or-atom)
    (cond
     [(null? pair-or-atom) 0]
     [(atom? pair-or-atom) 1]
     [else
      (+ (length* (car pair-or-atom))
         (length* (cdr pair-or-atom)))])))

<<length-asterisk>>

(display (simple-format #f "~a\n" (length* (cons 1 2))))
(display (simple-format #f "~a\n" (length* (cons (cons 1 2) 3))))
(display (simple-format #f "~a\n" (length* (cons 1 (cons 2 3)))))
(display (simple-format #f "~a\n" (length* (cons (cons 1 2) (cons 3 4)))))

2
3
3
4

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

<<prerequisites>>

(define weight*
  (lambda (pair-or-atom)
    (cond
     [(null? pair-or-atom) 0]
     [(atom? pair-or-atom) 1]
     [else
      (+ (* (weight* (first pair-or-atom)) 2)
         (weight* (second pair-or-atom)))])))

<<weight-asterisk>>

(display (simple-format #f "~a\n" (weight* '(1 2))))
(display (simple-format #f "~a\n" (weight* '((1 2) 3))))
(display (simple-format #f "~a\n" (weight* '(1 (2 3)))))
(display (simple-format #f "~a\n" (weight* '((1 2) (3 4)))))

3
7
5
9

shuffle

<<prerequisites>>

(define shuffle
  (lambda (pair-or-atom)
    (cond
     [(atom? pair-or-atom) pair-or-atom]
     ;; here is the problematic case
     [(pair? (first pair-or-atom))
      ;; still the same amount of atoms in the argument for recurring
      (shuffle (revpair pair-or-atom))]
     [else
      (build (first pair-or-atom)
             (shuffle (second pair-or-atom)))])))

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

Collatz function

<<prerequisites>>

(define C
  (lambda (num)
    (cond
     [(= num 1) 1]
     [(even? num) (C (/ num 2))]
     [else (C (+ (* num 3) 1))])))

<<collatz>>

(display (simple-format #f "C(1) = ~a\n" (C 1)))
(display (simple-format #f "C(27) = ~a\n" (C 27)))

C(1) = 1
C(27) = 1

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

(define collatz-step
  (lambda (num)
    (cond
     [(even? num) (/ num 2)]
     [else (+ (* num 3) 1)])))

(define collatz-count
  (lambda (n)
    (let loop ((num n) (count 0))
      (cond
       [(= num 1) count]
       [else
        (loop (collatz-step num)
              (+ count 1))]))))

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

<<collatz-refactored>>

(define collatz-find
  (lambda (max-iters)
    (let loop ([current-number 1])
      (cond
       [(>= (collatz-count current-number) max-iters) current-number]
       [else (loop (+ current-number 1))]))))

Enough fun with Collatz for now.

Ackermann function

(define zero?
  (lambda (num)
    (= num 0)))

#

<<ackermann-prerequisites>>

(define A
  (lambda (n m)
    (cond
     [(zero? n) (+ m 1)]
     [(zero? m) (A (- n 1) 1)]
     [else
      (A (- n 1)
         (A n (- m 1)))])))

<<ackermann>>

(display (simple-format #f "~a\n" (A 1 2)))
(display (simple-format #f "~a\n" (A 2 2)))
(display (simple-format #f "~a\n" (A 3 2)))
(display (simple-format #f "~a\n" (A 3 4)))
(display (simple-format #f "~a\n" (A 3 5)))
;; do not try: (display (simple-format #f "~a\n" (A 4 3)))
(display (simple-format #f "~a\n" (A 4 0)))

4
7
29
125
253
13

The computation time needed grows very quickly and calculating something like (A 4 3) is already infeasible.

Halting Problem

This part treats the halting problem, without mentioning its name explicitly, but it shows, that it is impossible to define a procedure will-stop?, which tells us for arbitrary procedures and their arbitrary inputs, whether the execution of them will halt.

To show this a procedure is defined:

;; prerequisites start
<<eternity>>
;; prerequisites end

(define weird-proc
  (lambda (anything)
    (and (will-stop? weird-proc)
         (eternity anything))))

The procedure weird-proc calls will-stop? to check, if itself will stop.

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

Let us take a look at the two cases.

Case 1: will-stop? returns false

Let us assume for a moment, that will-stop? will return the value false, stating, that weird-proc will not halt.

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

If false is the wrong result of will-stop? then the correct result must surely be the value true.

Case 2: will-stop? returns true

Let us assume for a moment, that will-stop? will return the value true, stating, that weird-proc will halt.

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

Conclusion

No matter what return value we assume the procedure will-stop? to return, we can construct an example, in which any boolean return value will be incorrect. This means, that we cannot write the procedure will-stop?. This is known as the "Halting Problem". It is not decidable, whether a procedure will halt for all possible inputs, without loss of generality.

Y-combinator

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

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

TODO: make a list of them here.

Org-mode help notexported

https://orgmode.org/manual/Exporting-code-blocks.html https://orgmode.org/manual/Comment-lines.html#Comment-lines https://orgmode.org/manual/Export-settings.html https://emacsclub.github.io/html/org_tutorial.html