Exercise 2.5 of SICP

Exercise 2.5: Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair a and b as the integer that is the product 2a3b. Give the corresponding definitions of the procedures cons, car, and cdr.

The discrete log procedure is a cousin of discrete-log from 1.45.

Exercise 2.4 of SICP

Exercise 2.4: Here is an alternative procedural representation of pairs. For this representation, verify that (car (cons x y)) yields x for any objects x and y.

What is the corresponding definition of cdr? (Hint: To verify that this works, make use of the substitution model of section 1.1.5.)

> (car (cons 1 2))
> (cdr (cons 1 2))

The reason this works is because upon execution of cons the function that is returned is used in a clever way by car and cons. Car and cdr pass a function via the m parameter in the cons. That function then receives as arguments x and y. In the case of cdr the second parameter is returned. The thing to note is that x and y get stored in the lambda function when the cons procedure is called.

Exercise 2.3 of SICP

Exercise 2.3: Implement a representation for rectangles in a plane. (Hint: You may want to make use of exercise 2.2.) In terms of your constructors and selectors, create procedures that compute the perimeter and the area of a given rectangle. Now implement a different representation for rectangles. Can you design your system with suitable abstraction barriers, so that the same perimeter and area procedures will work using either representation?

I have decided to use a diagonal segment for representation of make-rectangle and a point with both dimensional magnitudes for make-rectangle2.

Exercise 2.2 of SICP

Exercise 2.2: Consider the problem of representing line segments in a plane. Each segment is represented as a pair of points: a starting point and an ending point. Define a constructor make-segment and selectors start-segment and end-segment that define the representation of segments in terms of points. Furthermore, a point can be represented as a pair of numbers: the x coordinate and the y coordinate. Accordingly, specify a constructor make-point and selectors x-point and y-point that define this representation. Finally, using your selectors and constructors, define a procedure midpoint-segment that takes a line segment as argument and returns its midpoint (the point whose coordinates are the average of the coordinates of the endpoints). To try your procedures, you’ll need a way to print points:

This program takes most of it’s design from the rational number example.




Exercise 2.1 of SICP

Exercise 2.1: Define a better version of make-rat that handles both positive and negative arguments. Make-rat should normalize the sign so that if the rational number is positive, both the numerator and denominator are positive, and if the rational number is negative, only the numerator is negative.

Exercise 1.46 of SICP

Exercise 1.46: Several of the numerical methods described in this chapter are instances of an extremely general computational strategy known as iterative improvement. Iterative improvement says that, to compute something, we start with an initial guess for the answer, test if the guess is good enough, and otherwise improve the guess and continue the process using the improved guess as the new guess. Write a procedure iterative-improve that takes two procedures as arguments: a method for telling whether a guess is good enough and a method for improving a guess. Iterative-improve should return as its value a procedure that takes a guess as argument and keeps improving the guess until it is good enough. Rewrite the sqrt procedure of section 1.1.7 and the fixed-point procedure of section 1.3.3 in terms of iterative-improve.

The first two functions were written in the form of earlier exercises. The -iter functions are implemented with iterative-improve.

Old implementations:
> (sqrt 1.0 2)
> (fixed-point (lambda (y) (* 0.5 (+ (/ 2 y) y))) 1.0)
New implementations:
> (fixed-point-iter (lambda (y) (* 0.5 (+ (/ 2 y) y))))
> (sqrt-iter 2)

Exercise 1.45 of SICP

Exercise 1.45: We saw in section 1.3.3 that attempting to compute square roots by naively finding a fixed point of y \mapsto \frac{x}{y} does not converge, and that this can be fixed by average damping. The same method works for finding cube roots as fixed points of the average-damped y \mapsto \frac{x}{y^2}. Unfortunately, the process does not work for fourth roots — a single average damp is not enough to make a fixed-point search for y \mapsto \frac{x}{y^3} converge. On the other hand, if we average damp twice (i.e., use the average damp of the average damp of y \mapsto \frac{x}{y^3}) the fixed-point search does converge. Do some experiments to determine how many average damps are required to compute nth roots as a fixed-point search based upon repeated average damping of y \mapsto \frac{x}{y^{n-1}}. Use this to implement a simple procedure for computing nth roots using fixed-point, average-damp, and the repeated procedure of exercise 1.43. Assume that any arithmetic operations you need are available as primitives.

Doing experiments on the average number of damps to get the fixed-point procedure to converge seems to be:

Degree of root Power of 2 Number of average damps
2 21 1
4 22 2
8 23 3
16 24 4
32 25 5

Using this basis it makes sense to write a procedure discrete-log that computes the number of powers of 2 in a given number. It’s a bit like a very primitive implementation log2 function hence the name. Discrete-log is \Theta(\log_2 n) because it halves the number of computations every iteration.

> (root 2 0)
> (root 2 1)
> (root 2 2)
> (root (expt 2 50) 50)
> (root 0.00000001 2)

This program summarizes most of Chapter 1. It has lexical scope, passing functions as parameters, functions that construct and return other functions and the square root algorithm with an improved close-enough? procedure from exercise 1.7.
The repeated-compose and discrete-log could be done iteratively instead of recursively like this.

Exercise 1.44 of SICP

Exercise 1.44: The idea of smoothing a function is an important concept in signal processing. If f is a function and dx is some small number, then the smoothed version of f is the function whose value at a point x is the average of f(x – dx), f(x), and f(x + dx). Write a procedure smooth that takes as input a procedure that computes f and returns a procedure that computes the smoothed f. It is sometimes valuable to repeatedly smooth a function (that is, smooth the smoothed function, and so on) to obtained the n-fold smoothed function. Show how to generate the n-fold smoothed function of any given function using smooth and repeated from exercise 1.43.

S is a modified (the argument is not floored) Heaviside step function.
> ((n-fold-smooth S 0) 0)
> ((n-fold-smooth S 1) 0)
> ((n-fold-smooth S 15) 0)

Exercise 1.43 of SICP

Exercise 1.43: If f is a numerical function and n is a positive integer, then we can form the nth repeated application of f, which is defined to be the function whose value at x is f(f(…(f(x))…)). For example, if f is the function x \mapsto  x + 1, then the nth repeated application of f is the function x \mapsto  x + n. If f is the operation of squaring a number, then the nth repeated application of f is the function that raises its argument to the 2nth power. Write a procedure that takes as inputs a procedure that computes f and a positive integer n and returns the procedure that computes the nth repeated application of f. Your procedure should be able to be used as follows:

((repeated square 2) 5)

Hint: You may find it convenient to use compose from exercise 1.42.

> ((repeated square 2) 5)

> ((repeated square 3) 5)

> ((repeated (lambda (x) (+ x 1)) 3) 5)

Exercise 1.42 of SICP

Exercise 1.42: Let f and g be two one-argument functions. The composition f after g is defined to be the function x \mapsto  f(g(x)). Define a procedure compose that implements composition. For example, if inc is a procedure that adds 1 to its argument,

((compose square inc) 6)

> ((compose square inc) 6)