chapter 4. number games

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.

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.

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

(zero? 0)	  

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

(define o+
  (lambda (n m)
    (cond
     ((zero? m) n)
     (else (o+ (add1 n) (sub1 n))))))	  

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

(define o+
  (lambda (n m)
    (cond
     ((zero? m) n)
     (else (o+ (add1 n) (sub1 m))))))	  

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) $$

(define book-o+
  (lambda (n m)
    (cond
     ((zero? m) n)
     (else (add1 (book-o+ n (sub1 m)))))))	  

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:

(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	  

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

(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	  

This hasn't been in the book so far, but my definition for o+ allows for 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 peano numbers