SICP Chapter 1

Exercises Chapter 1

Exercise 1.1 Below is a sequence of expressions. What is the result printed by the interpreter in response to each expression? Assume that the sequence is to be evaluated in the order in which it is presented.

Inputs:

```
10
```
```
(+ 5 3 4)
```
```
(- 9 1)
```
```
(/ 6 2)
```
```
(+ (* 2 4) (- 4 6))
```
```
(define a 3)
```
```
(define b (+ a 1))
```
```
(+ a b (* a b))
```
```
(= a b)
```

(if (and (> b a) (< b (* a b)))
    b
    a
)

(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25)
)

```
(+ 2 (if (> b a) b a))
```

    (* (cond ((> a b) a)
         ((< a b) b)
         (else -1)
   )
   (+ a 1)
)

Outputs:

```
10
```
Explanation: The expression with the name “10” evaluate as the actual number 10 represented as an int or something in the computer
```
12
```
Explanation: I’ll use the explanation as notes if I want
```
8
```
Explanation: It’s kind of neat to think of arithmetic in the same with you think of functions with arguments you pass in
```
3
```
Explanation: I get the sense lambda calculus elaborates on this idea, probably I’ll find out later in the book
```
6
```
Explanation: asdasd
Explanation: It doesn’t return anything. The book mentions that the evaluation process it outlines doesn’t apply to define which makes it a “special form”. I could imagine it does return something, like a message letting you know if it succeeded or whatever, but the book doesn’t specify and it makes more sense to assume it doesn’t return anything it just associates the name a with the value 3.
Explanation: Same for this. I have some other cases where you have to make some assumptions about what would happen that the book doesn’t specify exactly.
```
19
```
Explanation: Now that we’re back to non special operators it’s business as usual. (+ a b (* a b)) = (+ 3 4 (* 3 4)) = (+ 3 4 12) = 19
```
#f
```
Explanation: I looked up how true and false are written in Scheme. #t and #f.
```
4
```
Explanation: When you subsitute a and b for their numbers you get
```
(if (and (> 4 3) (< 4 (* 3 4)))
    4 
    3
)
```
```
(if (and #t #t)
    4 
    3
)
```
```
4
```
It’s easier for me to read if I put the closing parentheses at the same column as the open parentheses.

Explanation: Substituting a and b for their numbers again then reducing:

(cond ((= 3 4) 6)
      ((= 4 4) (+ 6 7 3))
      (else 25)
)

(cond (#f 6)
      (#t 16)
      (else 25)
)

```
6
```
Explanation: Substituting a and b for their numbers again then reducing:
```
(+ 2 (if (> 4 3) 4 3))
```
```
(+ 2 (if #t 4 3))
```
```
(+ 2 4)
```
```
6
```

Explanation: Substituting a and b for their numbers again then reducing:

(* (cond ((> 3 4) 3)
         ((< 3 4) 4)
         (else -1)
   )
   (+ 3 1)
)

(* (cond (#f 3)
         (#t 4)
         (else -1)
   )
   4
)

(* 4
   4
)

Exercise 1.2 Translate the following expression into prefix form

$$\frac{5+4+(2-(3-(6+\frac{4}{5})))}{3(6-2)(2-7)}$$

Exercise 1.3 Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.

(define (sum_of_squares_of_two_largest x y z)
        (cond ((and (< x y) (< x z)) (+ (* z z) (* y y)))
              ((and (< y x) (< y z)) (+ (* x x) (* z z)))
              ((and (< z x) (< z y)) (+ (* y y) (* z z)))
         )
)

Exercise 1.4 Observe that our model of evaluation allows for combinations whose operators are compound expressions. Use this observation to describe the behavior of the following procedure:

(define (a-plus-abs-b a b)
        ((if (> b 0) + -) a b)
)
This is still part of the explanation

For clarity I’ll pretend (if (> b 0) + -) is a function named plus_or_minus_depending

We have an expression ((plus_or_minus_depending b) a b), where what plus_or_minus_depending evaluates to (either + or -) is inserted in the operator position of the outer expression.

Because plus_or_minus_depending returns a “+” if b > 0, and a “-” otherwise, the outer expression uses a “-” if b is negative (or zero) and a “+” if b is positive.

This will return a result equivelent to a + abs(b) in a calculator or whatever

Exercise 1.5 Ben Bitdiddle has invented a test to determine whether the interpreter he is faced with is using applicative-order evaluation or normal-order evaluation. He defines the following two procedures:

(define (p) (p))

(define (test x y)
        (if (= x 0)
            0
            y
        )
)

Then he evaluates the expression

(test 0 (p))

So to recap how applicative-order evaluation and normal-order evaluation work:

This alternative “fully expand and then reduce” evaluation method is known as normal-order evaluation, in contrast to the “evaluate the arguments and then apply” method that the interpreter actually uses, which is called applicative-order evaluation.

I have some thoughts on this I’m too lazy to type

Applicative-order evaluation:

(test 0 (p))

The arguments 0 and (p) both get evaluated right away. 0 evaluates to 0, and it’s done. (p) evaluates to (p), which evaluates to (p), and so on and so forth forever. The compiler times out after some time has passed and the evaulation never completes.

Normal-order evaluation: First we expand the test expression into the expressions that make it up, namely an if expression, and pass in the arguments from test to the expanded form made up of if.

(test 0 (p))

(if (= 0 0)
    0
    (p)
)

Now if is a special case where when it gets evaluated, the predicate gets evaluated first. Depending on if the predicate is #t or #f, only the clause or only the else-clause get evaluated. Only one of the clauses gets evaluated! You might think that the “unpacking” stage we’re at in normal-order evaluation doesn’t count as evaluation yet, but I think it’s just part of the evaluation process. Regardless, in the case of if when the interpretter using normal-order evaluation gets to it, the interpretter does not start by continuing to unpack the arguments of if, it just immediately tries to evaluate if the predicate is #t. Then, it only continues to unpack the true-clause or the false-clause. Because (= 0 0) evaluates as #t, we get this:

(if #t
    0
    (p)
)

And the expression finishes evaluating as 0 in this case.

Exercise 1.6 Alyssa P. Hacker doesn’t see why if needs to be provided as a special form. “Why can’t I just define it as an ordinary procedure in terms of cond?” she asks. Alyssa’s friend Eva Lu Ator claims this can indeed be done, and she defines a new version of if:

(define (new-if predicate then-clause else-clause)
        (cond (predicate then-clause)
              (else else-clause)
        )
)

Eva demonstrates the program for Alyssa:

(new-if (= 2 3) 0 5)
5

(new-if (= 1 1) 0 5)
0

Delighted, Alyssa uses new-if to rewrite the square-root program:

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

What happens when Alyssa attempts to use this to compute square roots? Explain.

So in general sqrt-iter calls itself over and over improving it’s guess until good-enough? returns #t, at which it returns the guess. In a normal if (a special form expression), the else-clause never gets evaluated.

However, because new-if is just a normal expression, and the clause and else-clause are both normal arguments, both the arguments get evaluated. If the else clause gets evaluated still even when (good-enough? guess x) evaluates as #t, then there’s nothing to stop sqrt-iter from calling itself over and over again recursively from it’s else-clause, creating a dead loop.

As such, when Alyssa attempts to use new-if to compute square roots the process times out without over finishing.

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?

NOTE FOR CHARLIE: I cheated out of laziness and posted the answer I got the last time we did this. I’ll clean it up later or maybe redo it.

The test is unable to find a square root for a very small number because the good-enough? expression works by checking if the difference between the square of our guess for square root and the original number is greater than some predefined small amount. For example in python:

if (abs(guess^2 - original)) < .0001:
	then return true

If both the guess and the original are much smaller than our threshold (.0001), then the difference between them will not exceed .0001 even if the squared guess and the original answer are still orders of magnitude appart.

I couldn’t actually test this without the interpretter timing out, but if the numbers are so big that they can’t be stored as a float (or whatever format) without losing precision, then you can’t find a precise difference from one guess and another because there’s no small precision at all. For example: 200000000001^2 would just become 4×10^22, the same as 200000000000^2. (square-root 40000000000000000000000) can output 200000000001 without catching that it’s wrong.

Here’s my procedure that works by comparing the change between current and previous guesses with a small fraction of the current guess. (define (square x) (* x x))

(define (good-enough? guess prev_guess x) (< (abs (- guess prev_guess)) (* guess 0.0001)))

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

(define (improve guess x) (average guess (/ x guess)))

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

(define (sqrt x) (sqrt-iter 1.0 0 x))

It does work better for small numbers. It also works better for larger numbers in the sense it doesn’t crash my interpretter. The error can still get arbitrarily large as the numbers get bigger. You can also easily add a feature that scales the tolerance to match the size of the number if you want, which helps things up until the interpretter times out again.

2024/04/28

Exercises Chapter 1