# SICP Solutions: Sections 2.1.3 and 2.1.4

### Section 2.1.3 - What Is Meant by Data?

#### Exercise 2.4

As the writers tell us, we can use the substitution model to verify that this works:

So it essentially creates an anonymous procedure that accepts two arguments and returns the first. This means that we can implement cdr as:

#### Exercise 2.5

We create a helper procedure contains and use it to implement both car and cdr:

#### Exercise 2.6

We will first use substitution to evaluate (add-1 zero) as the authors advise:

So this means that zero applies zero times its argument procedure f. Each time we add 1 though, we apply the argument procedure one more time. Essentially the Church numeral is the function itself, composed $n$ times. So this means that we can define one as:

and two as:

We can then define addition as applying the composition $m + n$ times:

We get our hint for the above from the way add-1 is implemented. Observe the (f ((n f) x)) part. What it essentially does is apply f once (add-1, remember?) to the result of passing consecutively f and x to the supplied function. In the case of zero, the result is x. In the case of one the result would be:

and so on and so forth.

### Section 2.1.4 - Extended Exercise: Interval Arithmetic

#### Exercise 2.7

The selectors are simple to implement:

#### Exercise 2.8

The ordering will not change here:

#### Exercise 2.9

Assume we have intervals $x$ and $y$. Assume also we prefix by $\mathrm{lb-}$ and $\mathrm{ub-}$ the lower and upper bound respectively. The width of the sum $x + y$ will be:

\begin{align*} \mathrm{width}(x + y) &= \mathrm{width}([\mathrm{lb-}x + \mathrm{lb-}y, \mathrm{ub-}x + \mathrm{ub-}y])\\ &= \frac{\mathrm{ub-}x + \mathrm{ub-}y - \mathrm{lb-}x - \mathrm{lb-}y}{2}\\ &= \frac{\mathrm{ub-}x - \mathrm{lb-}x}{2} + \frac{\mathrm{ub-}y - \mathrm{lb-}y}{2}\\ &= \mathrm{width}(x) + \mathrm{width}(y) \end{align*}

So the width of the sum (and similarly, the difference) of two intervals is a function only of the widths of the intevals being added.

Consider multiplication. Assume we have two intervals $a = (1, 3)$ and $b = (-3, -1)$. Their widths are $\mathrm{width}(a) = 1$ and $\mathrm{width}(b) = 1$. However, their multiplication yields the interval $a \times b = (-9, -1)$ and $\mathrm{width}(a \times b) = 4$. Now if instead of $b$ we use an other interval of width 1, e.g. $d = (5, 7)$ we would have $a \times d = (5, 21)$ and $\mathrm{width}(a \times c) = 8$. So width is not a function only of the widths of the intervals beeing multiplied. Division is exactly similar.

#### Exercise 2.11

In my mind this is one case where the programmer has to choose between optimization and readable code. So, if you’re starving for resources then by all means, do this.

Each interval can have its numbers both negative, one negative and one positive, or both positive. Hence three times three are the nine cases we need to examine. In each case but the one where both intervals span zero, we do not need to compare anything to arrive at the solution. Finally, in the case where both intervals span zero, we can at least use less arguments in |min| and |max| by observing that each time only two numbers will be positive and two will be negative. Here goes:

#### Exercise 2.13

Assume for intervals $a = (x, p_1)$ and $b = (y, p_2)$, where $p_i$ is the tolerance of the interval. We could rewrite $a$ in terms of bounds as:

\begin{align*} (x - p_1x, x + p_1)\\ (x(1 - p_1), x(1 + p_1)) \end{align*}

and similarly $b$ is $(y(1 - p_2), y(1 + p_2))$. Since all numbers are positive, the lower bound of their product will be the multiplication of their lower bounds and similarly for the upper bounds. Let’s work it out:

\begin{align*} (x(1 - p_1)y(1 - p_2), x(1 + p_1)y(1 + p_2))\\ (xy(1 - (p_1 + p_2 - p_1p_2)), xy(1 + (p_1 + p_2 + p_1p_2))) \end{align*}

Assuming small percentage tolerances, e.g. $10^{-2}$, their products will be very small (e.g. $10^{-4}$) and can be ignored. So we can assume that the approximate percentage tolerance of the product of two intervals would be $p_1 + p_2$.

#### Exercise 2.14

We can demonstrate that Lem is right by choosing intervals $R_1 = (1, 3)$ and $R_2 = (3, 6)$. We have:

The issue here is that for algrebraic operations to work correctly (and thus for the two formulas to be equivalent), some equations such as $A/A = 1$ must be respected in our system. However, this is not true for intervals where width is of the same order of magnitude as the center value. As this changes, the value gets closer to one. Observe:

Using center-percent form, we can at least make sure that as the percentage is small, the operations get closer to correctness. Keep in mind, that we designed our system as a way to specify ranges of values, representing error (or tolerance). This value is supposed to be small. But even in real world scenarios such as the resistor of 6.8ohms with 10\% tolerance, our system does not work correctly:

#### Exercises 2.15 & 2.16

Eva Lu Ator has a point. When a variable introduces uncertainty, our system by design transfers this uncertainty to any other variable with which it operates. If we push uncertainty to the edges (i.e. have as few operations as possible) then we should get better results.

Having said that, an interval-arithmetic package should provide general operations. One option would be to limit operations to variables with small error percentages. However, as we saw with the capacitors, a 10\% error is pretty common. This would render our package useless.

In order for our package to be generic enough so it can be useful, it should respect algebraic axioms such as $0a = 0$, $a/a = 1$, $a(b + c) = ab + ac$, etc. This is what makes the problem difficult.

Updated: