Tags SICP

`lambda` is a very important tool in our quest for meaningful abstractions to make programming easier. Some procedures are inherently simple and one-time, and it’s a shame to spend the extra time writing out their full definitions and making up names for them. So anonymous procedures, created with `lambda`, are the answer.

Here is some of the code from the previous sections rewritten with `lambda` instead of explicitly defined auxiliary functions:

```(defun sum (term a next b)
(if (> a b)
0
(+  (funcall term a)
(sum term (funcall next a) next b))))

(defun pi-sum (a b)
(sum  (lambda (x)
(/ 1.0 (* x (+ x 2))))
a
(lambda (x) (+ x 4))
b))

(defun integral (f a b dx)
(*  (sum f
(+ a (/ dx 2.0))
(lambda (x) (+ x dx))
b)
dx))
```

The authors also presented `let` for defining temporary variables. I’ve been using `let` in some of the code already written for the previous sections, so there is no need to reintroduce it here.

#### Exercise 1.34

Here is the perverse invocation the authors refer to:

```(defun f (g)
(funcall g 2))

(f #'f)
```

Since `f` is passed as an argument to `f`, it will be called with 2 as the argument. But what is `f`, again ? A function that calls its argument as a function on 2. So, the second call will attempt to call 2 as a function (on 2), which is an error. CLISP complains:

```
*** - FUNCALL: 2 is not a function name; try using a symbol instead

```

#### Section 1.3.3

Here is the CL implementation of the fixed point search and finding the square root of 2 using it:

```(defvar tolerance 0.00001)

(defun fixed-point (f first-guess)
(labels (
(close-enough? (v1 v2)
(< (abs (- v1 v2)) tolerance))
(try (guess)
(let ((next (funcall f guess)))
(if (close-enough? guess next)
next
(try next)))))

(try first-guess)))

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

(defun dampen-sqrt (x)
(fixed-point
(lambda (y)
(average y (/ x y)))
1.0))
```

I’m using here the `labels` form of CL instead of an internal `defun`, following a good advice given in the comments to the previous SICP post. In CL, unlike in Scheme, an internal `defun` creates a function with global scope, so it doesn’t really do what we want it to do – which is define a localized function that is seen only inside the function definition it appears in. `labels` is the correct way to do this in CL. There are other forms that can achieve this goal, like `flet` – for differences between them turn to the Common Lisp Hyperspec

Note that the authors define `close-enough?` as an explicit function with a name, instead of using a `lambda`. This makes sense in this case, because the name `close-enough?` is meaningful and using the explicit function makes the code more readable. On the other hand, in the definition of `dampen-sort` the authors choose to represent the function computing the average of y and x/y as a `lambda`, because it doesn’t harm readability and there is no point in making up a special function name for this singular case. There are no hard rules set in stone about when to use `lambda` and when to use an explicit function. In some cases one is better, in some the other. My rule of thumb in such situations is to go with the intuition – whatever feels more natural and readable in any specific case. This intuition improves with experience.

#### Exercise 1.35

First let’s prove that phi is a fixed point of `x -> 1 + 1/x`. It’s quite simple, since:

```phi^2 = phi + 1   (1)
```

So substituting phi into the transformation:

```1 + 1/phi =
(phi + 1)/phi =   / Applying (1)
(phi^2)/phi =
phi
```

So, indeed phi is a fixed point of `x -> 1 + 1/x`. Now, the code that computes it:

```(fixed-point (lambda (x) (1+ (/ 1 x))) 1.0)
=>
1.618
```

#### Exercise 1.36

Here is the code:

```(defvar tolerance 0.00001)

(defun fixed-point (f first-guess)
(labels (
(close-enough? (v1 v2)
(< (abs (- v1 v2)) tolerance))
(try (guess)
(format t "Trying ~F~%" guess)
(let ((next (funcall f guess)))
(if (close-enough? guess next)
next
(try next)))))

(try first-guess)))

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

(defun xx (x)
(/ (log 1000) (log x)))

(defun dampen-xx (x)
(average x (xx x)))
```

Running without dampening:

```(print (fixed-point #'xx 2.0))
=>
Trying 2.0
Trying 9.965784
Trying 3.0044723
Trying 6.279196
Trying 3.7598507
Trying 5.215844
Trying 4.182207
Trying 4.827765
Trying 4.3875937
Trying 4.67125
Trying 4.481404
Trying 4.6053658
Trying 4.523085
Trying 4.5771146
Trying 4.541383
Trying 4.5649033
Trying 4.5493727
Trying 4.5596066
Trying 4.552854
Trying 4.5573053
Trying 4.5543694
Trying 4.5563054
Trying 4.5550284
Trying 4.5558705
Trying 4.555315
Trying 4.555681
Trying 4.55544
Trying 4.5555987
Trying 4.5554943
Trying 4.555563
Trying 4.5555177
Trying 4.5555477
Trying 4.555528
Trying 4.555541

4.5555325
```

34 steps. Now, with dampening:

```(print (fixed-point #'dampen-xx 2.0))
=>
Trying 2.0
Trying 5.982892
Trying 4.9221687
Trying 4.6282244
Trying 4.5683465
Trying 4.5577307
Trying 4.55591
Trying 4.555599
Trying 4.5555468

4.5555377
```

9 steps. Dampening certainly makes the computation converge much quicker in this case.

#### Exercise 1.37

Here is the implementation:

```(defun cont-frac (n d k)
(labels (
(frac (i)
(/  (funcall n i)
(+  (funcall d i)
(if (= i k)
0
(frac (1+ i)))))))

(frac 1)))
```

This is a recursive process, of course. It takes k = 11 to reach 4-digit accuracy in the computation of 1/phi:

```(print (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 11))
=>
0.6180556
```

And this is the iterative version:

```(defun cont-frac-iter (n d k)
(labels (
(frac-iter (i result)
(if (= i 0)
result
(frac-iter
(1- i)
(/  (funcall n i)
(+ (funcall d i) result))))))

(frac-iter k 0)))
```

As usual, it is a bit less elegant and obvious. I wonder if anyone first produces the iterative version for these exercises, and only then the recursive one. Somehow, resursive functions often greatly simplify matters. In the case of `cont-frac`, for instance, the recursive function is almost a transcription of the formula into a program. The iterative version, on the other hand, takes somewhat more thought to understand – because it has to generate the result from the bottom up (note that it counts down while the recursive function counts up).

#### Exercise 1.38

The only trick here is to realize the rule by which the elements of `Di` are generated, and this isn’t too hard if you notice that the non-1s are all 3 elements away from each other and are successive multiples of 2.

```(print
(cont-frac
(lambda (i) 1.0)
(lambda (i)
(let ((i+1 (1+ i)))
(if (= (rem i+1 3) 0)
(* 2.0 (/ i+1 3))
1.0)))
10))
=>
0.7182817
```

Which is `e - 2`!

#### Exercise 1.39

Again, transforming the fraction into a recursive process is very straightforward:

```(defun tan-cf (x k)
(labels ((tan-step (i)
(/  (if (= i 1)
x
(square x))
(-  (1- (* i 2))
(if (= i k)
0
(tan-step (1+ i)))))))

(tan-step 1)))
```