* 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]]