* DONE chapter 4. number games :blog:little_schemer:
:PROPERTIES:
:header-args: :noweb-ref chap-four
:ID:       little-schemer-chapter-four
:CREATED: [2020-12-02 Wed 20:09]
:END:
:LOGBOOK:
- State "DONE"       from              [2020-12-02 Wed 20:09]
:END:

quick note: I'm using =racket scheme= locally because, well, I already had it
installed. Starting at the beginning of the /number games/ chapter and working
through it in a semi-logical order that should make sense if you have the book
in front of you. I hope.

** natural numbers

we're considering only /natural numbers/

we're not dealing with negative or fractional numbers. questions like =(sub1 0)=
are meaningless, because there is no =-1= as far as we're concerned.

** zero?

the =zero?= procedure will return =#t= when given the number =0=, and =#f= when given
/anything else/

#+begin_src racket :noweb-ref other
(zero? 0)
#+end_src

** adding numbers

the =o+= procedure adds two natural numbers. First attempt at implementing it:

#+begin_src racket :noweb-ref other
(define o+
  (lambda (n m)
    (cond
     ((zero? m) n)
     (else (o+ (add1 n) (sub1 n))))))
#+end_src

I made a little mistake here - accidentally used =n= for both of the second
clause, which didn't go too well.

#+begin_src racket :session schemer
(define o+
  (lambda (n m)
    (cond
     ((zero? m) n)
     (else (o+ (add1 n) (sub1 m))))))
#+end_src

this one works just fine - though it doesn't match the version in the book. This
works because for every =m=, we add one to =n= until =m= is =0=. so if $m = 5$ and $n =
1$, then it only takes a single step:

$$
m + n = (m + 1) + (n - 1) = 5 + 1 = (5 + 1) + (1 - 1)
$$

#+begin_src racket :session schemer
(define book-o+
  (lambda (n m)
    (cond
     ((zero? m) n)
     (else (add1 (book-o+ n (sub1 m)))))))
#+end_src

the book version works like this, deferring the =add1= until after the complete
addition is done. Given, say, =(book-o+ 5 2)=, expanding it out:

#+begin_src racket :session schemer :noweb-ref other
(cond
 ((zero? 2) 5
  (else (add1 (book-o+ 5 (sub1 2))))))

;; 2 isn't 0

(add1 (book-o+ 5 1))

(add1
 (cond
  ((zero? 1) 5)
  (else (add1 (book-o+ 5 (sub1 1))))))

;; 1 isn't 0

(add1 (book-o+ 5 0))

(add1
 (add1
  (cond
   ((zero? 0) 5)
   (else #f))))

;; 0 is 0

(add1
 (add1
  5))

7
#+end_src

in comparison to my version, with =(o+ 5 2)=

#+begin_src racket  :session schemer :noweb-ref other
(o+ 5 2)

(cond
 ((zero? 2) 5)
 (else (o+ (add1 5) (sub1 2))))

;; 2 isn't 0

(o+ 6 1)

(cond
 ((zero? 1) 6)
 (else (o+ (add1 6) (sub1 1))))

;; 1 isn't 0

(o+ 7 0)

(cond
 ((zero? 0) 7)
 (else (o+ (add1 7) (sub1 0))))

;; 0 is 0

7
#+end_src

*** tail call recursion

This hasn't been in the book so far, but my definition for =o+= allows for [[https://stackoverflow.com/questions/310974/what-is-tail-call-optimization][tail-call optimisation]]. I really didn't plan that, but it's there.

the book points out here that when we're writing a recursive function, we should
always start with a way to end the recursion (a /base case/). This is effectively
[[*The First Commandment (/preliminary/)][The First Commandment (/preliminary/)]], expanded past /null?/ as the question to tell
if whatever value we're recursing over is at it's /base/ (whatever 'empty' means
for this type)

The book also points out that =add1= is to =number= what =cons= is to a =list=. It adds an
extra value. Our number system starts at =0= and we have =add1=, which is /kind of
like/ the [[https://mathworld.wolfram.com/PeanosAxioms.html][peano numbers]]