Introduction

Okay, this is the first SICP thread, but I intend it to be serious.

I'd like to start at Section 1.1.7 Example: Square Roots by Newton’s Method.

Section 1.1.7 Example: Square Roots by Newton’s Method.

This section is about implementing Newton’s Method as a program. Newton’s Method for square root is computed by approximating the square root of x by successively averaging a guess, g with x/g.

Basic strategy:

(define (square-iter guess x)
  (if (good-enough? guess x)
      guess
      (square-iter (improve guess x) x)))

where improve averages g and x/g and where good-enough? tests to see if the absolute difference of g² and x is less than 0.001 — basically, a very rough approximation. Good stuff.

Exercise 1.7

> The good-enough? test used in computing square roots will not be very effective for finding the square roots of very small numbers. Also, in real computers, arithmetic operations are almost always performed with limited precision. This makes our test inadequate for very large numbers. Explain these statements, with examples showing how the test fails for small and large numbers. An alternative strategy for implementing good-enough? is to watch how guess changes from one iteration to the next and to stop when the change is a very small fraction of the guess. Design a square-root procedure that uses this kind of end test. Does this work better for small and large numbers?

Okay, consider the following example:

> (sqrt 1.0000013)         ;; proper square root
1.0000006499997889
> (square-root 1.0000013)  ;; our square root
1.0000013

So, for very small numbers, our good-enough? function is not good enough (teehee).

On the other end of the scale, I wasn’t so sure about it. The exercise mentions “in real computers, arithmetic operations are almost always performed with limited precision. This makes our test inadequate for very large numbers.” So this got me thinking about the implementation of decimal values. I had thought for fixed point decimals, the as the number part grows, there is less space in the implementation for the decimal part which would get truncated, but I really do not know. If someone can explain that, I would appreciate it.

Here is the basic implementation:

(define (square n) (* n n))

(define (average x y) (/ (+ x y) 2))

; old good-enough? procedure
; (define (good-enough? g n)
;  (< (abs (- (square g) n)) 0.001))

; new good-enough? procedure
(define (good-enough? g g.)
  (> (/ (min g g.) (max g g.)) 0.999999999))

(define (improve g n) (average g (/ n g)))

(define (square-root n)
  (define (try n g g.)
    (if (good-enough? g g.)
        g
        (try n (improve g n) g)))
  (try n 1.0 0.0))

This implementation works well for small numbers because it tests if the guess has not changed very much i.e. one is 99.9999999% the size of the other.

Did anyone come up with something better than this?

Ah, I found a nicer one by someone else:

(define (close-enough? a b)
  (let ((ratio (/ a b)))
    (and (< ratio 1.001) (> ratio 0.999))))

Rather than specifically handling min/max and then getting the ratio, he is comparing both sides. Is this just another way of writing mine?

i think a lot of people were mystified by the supposed "too big" case. i've never seen a convincing argument about it.

(define (sqrt2 n d)

(sqrt2-help n d 1 0))

(define (sqrt2-help n d guess prevguess)

(if (< (diff guess prevguess) (* d prevguess))
    guess
    (sqrt2-help n d (improve-guess n guess) guess)))

(define (diff a b)

(abs (- a b)))

(define (improve-guess n guess)

(average guess (/ n guess)))

(define (average a b)

(/ (+ a b) 2))

what the hell did it do to my code?

>>4
Add four spaces before your each line in your code...

(define (sqrt2 n d)
    (sqrt2-help n d 1 0))

(define (sqrt2-help n d guess prevguess)
    (if (< (diff guess prevguess) (* d prevguess))
	guess
	(sqrt2-help n d (improve-guess n guess) guess)))

(define (diff a b)
    (abs (- a b)))

(define (improve-guess n guess)
    (average guess (/ n guess)))

(define (average a b)
    (/ (+ a b) 2))

>>7
I presume is precision.

>>8
Er, 'd'.

yeah, i guess. it's d for delta, but it really means that the new guess needs to be less than a dth of the previous one. dunno what to call that.

>>7,10
I don't that the delta would work. Let's say you are working with 32-bit integers. You want the root of 1e9 to 0.0001 precision (meaning abs(guess - prevguess) < 0.0001). Then your delta would have to be 1e13, wouldn't it?

So simply putting d = 0.0001 would work I think. You don't need to multiply d with guess.

Also, you sqrt2-help function can be like:

`(define (sqrt2-help n d guess)
(define nextguess (improve-guess n guess))

(if (< (diff nextguess guess) (* d guess))
guess
(sqrt2-help n d nextguess)))`

I meant that it should be like:

`(define (sqrt2-help n d guess)
(define nextguess (improve-guess n guess))

(if (< (diff nextguess guess) d)
guess
(sqrt2-help n d nextguess)))`

Let's go to the counting change problem in Section 1.2.2

Question: How many different ways can we make change of $1.00, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a procedure to compute the number of ways to change any given amount of money?

I realized that this problem is the same as this:

Given A >= 0 and d_k > 0, k being integers 1 to n.
Find x_k such that
x_1*d_k + x_2*d_2 + ... + x_n*d_n = A
where x_k are non-negative integers.

A is supposed to be the total amount of money. d_k are the denominations and x_k are the number of coins and n is the number of denominations.

I am pretty sure this is an exponential problem. Something like A^n/prod(d_k). What do you think?

>>12
Oops, that should be:

Given A >= 0 and d_k > 0, k being integers 1 to n.
Find x_k such that
x_1*d_1 + x_2*d_2 + ... + x_n*d_n = A
where x_k are non-negative integers.

>>13
Or rather, the question is how many solutions are there to this equation? But you can easily find x_k while finding the number of solutions; maybe there is an easier way?

kci =: (<@:(+ >)"0 0) (<@;\.)

cc =: 4 : 0
s =. <"0 x
k =. 0
while. (+/ #@> s) > 0 do.
k =. k + (+/ y(=!.0) ;s)
s =. x kci ((#~ <!.0&y)&.>) s
end.
k
)

Iterative solution to that counting change problem in the [spoiler]SICP[/spoiler] written in J lawl. Same space complexity probably. It builds up the combinations from the bottom counting and filtering. kci returns the n+1 combination given the n-combination (summed). cc goes like: 1 5 10 25 cc 67 gives the number of ways the left numbers can be summed to get 67. I have a function that outputs the actual ways it combines instead of just the number if anyone would possibly want it.

Why are people so hot and bothered about that giving change problem? It's probably the least interesting problem I have ever heard of.

;Excerse 2.20
(define (same-parity first-value . other-values)
    (let ((match-parity (lambda (a b) (equal? (even? a) (even? b)))))
    (if (null? other-values) '()
      (if (match-parity first-value (car other-values))
        (cons (car other-values) (same-parity first-value (cdr other-values))
        (same-parity first-value other-values)))))

is giving me a bunch of weird errors about trying to use lists as integers in the match-parity helper function. I guess this is more of a misunderstanding of the implementation of lists in Scheme than the list concept, but in 2.2 those are mostly equivalent. Help?

>>17
Here's the exercise in common lisp

(defun ex2.20 (a &rest b)
  (cons a (remove-if-not ((lambda (x) (if (oddp x) #'oddp #'evenp)) a) b)))

&rest is equal to '.'
scheme doesn't have remove-if-not so you can try to implement that

You must not return '() if other-values is an empty list. You must return the results or a.

For example,

(same-parity 1) ==> (1)
(same-parity 1 2 3) ==> (1 3)

Don't know how to use spoilers but here is same-parity in scheme:
.
.
.
.
.
.
.
.
.
.

(define (same-parity a . b)
  (define (same-parity-help f a b)
    (if (null? b) a
    (same-parity-help f (if (f (car b)) (cons (car b) a) a) (cdr b))))
  (cons a (reverse (same-parity-help (if (odd? a) odd? even?) '() b))))

>>18 here

(defun ex2.20 (a &rest b)
  (cons a (remove-if-not ((lambda (x) (if (oddp x) #'oddp #'evenp)) a) b)))

Works but I just realized how dumb that lambda is,

(defun ex2.20 (a &rest b)
  (cons a (remove-if-not (if (oddp a) #'oddp #'evenp) b)))

Need some rest.

Looking at the scheme solution with the helper function which does the body of the work, I think I figured out my problem. The dotted-tail notation takes whatever arguments follow the preceding fixed arguments and makes a list out of them. If one were to throw a list at it, it would make a list out of that.

(define (f a . b) b)
(f 1 2 3)→(2 3)
(f 1 '(2 3))→((2 3))

and when one has lists of lists, car and cdr do weird things. i suppose this makes recursion with functions using dotted-tail notation problematic without a helper function.

Also, thank you for catching that I was returning empty lists rather than the list containing the first value. God only knows how long it would have taken me to figure out what was going wrong there on my own.

I finally came up with this. It probably isn't very idiomatic, but it seems to work.

; Exercise 2.20
(define (same-parity first-value . other-values)
  (let ((match-parity (lambda (a b) (equal? (even? a) (even? b)))))
    (letrec ((same-parity-helper (lambda (values) 
      (if (null? values) '()
        (if (match-parity first-value (car values))
          (cons (car values) (same-parity-helper (cdr values)))
          (same-parity-helper (cdr values)))))))
      (cons first-value (same-parity-helper other-values)))))

>>20
It's kinda ugly.
The key here is not to write it in pure scheme with a helper function.
The key is to find the pattern, and factor the code.
What you want to do is keep all the elements of a sequence that satisfy a condition.

It's easy to write this as:

(define (filter cond lst)
  (define (filter-help old new)
    (if (null? old) new
        (filter-help (cdr old) (if (cond (car old)) (cons (car old) new) new))))
  (reverse (filter-help lst '())))

some examples:

(filter (lambda (x) x) '(1 2 () 3 () 4 5)) ==> (1 2 3 4 5)
(filter (lambda (x) (odd? x)) '(1 2 3 4 5)) ==> (1 3 5)
(filter (lambda (x) (not (null? x))) '( () () (1 2 3) () (4 5))) ==> ((1 2 3) (4 5)

then it's easy to write same-parity as

(define (same-parity fst . rest)
  (cons fst (filter (if (odd? fst) odd? even?) rest)))

A lot of SICP's beginning exercises are easy to write with common lisp. That's because common lisp provides the functions to do it. Because scheme is used in the book, there isn't an obvious function to use, so the book expects you to find the patterns and write the appropriate function.
That's how experts write maintainable and portable code, and that's how they design protocols. By finding the key patterns.
Imagine patterns as the stairway to the new level of abstraction.
Have you ever played pokemon? Remember that fucking house in blue/red that you get the masterball? Remember how frustrating it was to take the wrong stairway?
That's how it feels when you spot the wrong pattern, so you better find them right patterns.

>>21
damn my stupidity is astonishing.
the second filter example can be written as:

(filter odd? '(1 2 3 4 5))

without the lambda.

>>20

> and when one has lists of lists, car and cdr do weird things. i suppose this makes recursion with functions using dotted-tail notation problematic without a helper function.

No, it's still possible to use recursion, and apply.

Example:

(let ((lst '(1 2 3 4 5)))
  (apply + lst)) ; (+ 1 2 3 4 5)

Here's how to write it without a helper function:

(define (same-parity fst . rest)
  (if (null? rest) (list fst)
      (if  (equal? (even? fst) (even? (car rest)))
          (cons (car rest) (apply same-parity fst (cdr rest)))
          (apply same-parity fst (cdr rest)))))

There's just one thing wrong with this:

(same-parity 1 2 3 4 5) will return (3 5 1) and not (1 3 5)

If you don't care about order this is acceptable.

>>21
yeah, 've just started reading 2.2.3 Sequences as Conventional Interfaces, where A&S really start to hammer in the process of recognizing the problem as discrete parts. It's really impressive how it's practically universal.