SICP. 1.3.2–1.3.4
2023-02-15 Wed

1.3.2 Constructing Procedures Using Lambda

The mystical λ seen on the cover comes on stage. Procedures can be created without giving them a name: 

(lambda (x) (+ x 4)) ;; a procedure that adds 4 to its argument

This allows us, for example, to define integral in this way: 

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

instead of doing it in this way: 

(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b)
     dx))

Notice that saying 

(define (plus4 x) (+ x 4))

is equivalent to say 

(define plus4 (lambda (x) (+ x 4)))

Lambda can be used to bind local variables: 

(define (f x y)
  ((lambda (a b)
     (+ (* x (square a))
        (* y b)
        (* a b)))
   (+ 1 (* x y))
   (- 1 y)))

This is so useful that Scheme provides a special form, let, for achieving the same result: 

(define (f x y)
  (let ((a (+ 1 (* x y)))
        (b (- 1 y)))
    (+ (* x (square a))
       (* y b)
       (* a b))))

Let is nothing more than syntactic sugar.

Exercise 1.34

Exercise:

Suppose we define the procedure 

(define (f g) (g 2))

Then we have 

(f square)
4

(f (lambda (z) (* z (+ z 1))))
6

What happens if we (perversely) ask the interpreter to evaluate the combination (f f)? Explain?

Answer:

According to the substitution model: 

(f f)
(f 2)
(2 2)

In `(2 2)`, `2` is used as if it denoted a procedure. But `2` does not denote a procedure. `2` denotes a number. So, I predict that the interpreter will complain about this.

In fact, when trying to evaluate the combination, DrRacket says:

application: not a procedures; expected a procedures that can be applied to arguments given: 2

1.3.3 Procedures as General Methods

The authors discuss here two examples of how lambda can be used (to write ``procedures used express general methods of computation, independent of the particular functions involved''.).

The exercises are a bit mathematically heavy. I'm skipping them.

1.3.4 Procedures as Returned Values

Procedures can not only take procedures as their arguments, but also return procedures…

Exercise 1.41

Exercise:

Define a procedure double that takes a procedure of one argument as argument and returns a procedure that applies the original procedure twice. For example, if inc is a procedure that adds 1 to its argument, then (double inc) should be a procedure that adds 2. What value is returned by 

(((double (double double)) inc) 5)

Answer: 

;; (((double (double double)) inc) 5)

;; (double inc) => (lambda (x) (inc (inc x)))

;; (double double) => (lambda (x) (double (double x)))

;; (double (double double)) =>
;; (lambda (x) ((lambda (x) (double (double x)))
;;             ((lambda (x) (double (double x))) x)))

;; so:

((double (double double) inc))

;; =>

((lambda (x) (double (double x)))
 (double (double inc)))

;; =>

((lambda (x) (double (double x)))
 (double (lambda (x) (inc (inc x)))))

;; =>

((lambda (x) (double (double x)))
 (lambda (x) ((lambda (x) (inc (inc x)))
              ((lambda (x) (inc (inc x))) x))))

;; =>

(double (double (lambda (x) ((lambda (x) (inc (inc x)))
                             ((lambda (x) (inc (inc x))) x)))))

;; =>

(double (lambda (x)
          ((lambda (x) ((lambda (x) (inc (inc x)))
                        ((lambda (x) (inc (inc x))) x)))
           ((lambda (x) ((lambda (x) (inc (inc x)))
                         ((lambda (x) (inc (inc x))) x))) x))))

;; =>

(lambda (x) ((lambda (x)
               ((lambda (x) ((lambda (x) (inc (inc x)))
                             ((lambda (x) (inc (inc x))) x)))
                ((lambda (x) ((lambda (x) (inc (inc x)))
                              ((lambda (x) (inc (inc x))) x))) x)))
             ((lambda (x)
                ((lambda (x) ((lambda (x) (inc (inc x)))
                              ((lambda (x) (inc (inc x))) x)))
                 ((lambda (x) ((lambda (x) (inc (inc x)))
                               ((lambda (x) (inc (inc x))) x))) x)))
              x)))

;; now let's apply that lambda to 5:
((lambda (x) ((lambda (x)
                ((lambda (x) ((lambda (x) (inc (inc x)))
                              ((lambda (x) (inc (inc x))) x)))
                 ((lambda (x) ((lambda (x) (inc (inc x)))
                               ((lambda (x) (inc (inc x))) x))) x)))
              ((lambda (x)
                 ((lambda (x) ((lambda (x) (inc (inc x)))
                               ((lambda (x) (inc (inc x))) x)))
                  ((lambda (x) ((lambda (x) (inc (inc x)))
                                ((lambda (x) (inc (inc x))) x))) x)))
               x))) 5)

;; =>

((lambda (x)
   ((lambda (x) ((lambda (x) (inc (inc x)))
                 ((lambda (x) (inc (inc x))) x)))
    ((lambda (x) ((lambda (x) (inc (inc x)))
                  ((lambda (x) (inc (inc x))) x))) x)))
 ((lambda (x)
    ((lambda (x) ((lambda (x) (inc (inc x)))
                  ((lambda (x) (inc (inc x))) x)))
     ((lambda (x) ((lambda (x) (inc (inc x)))
                   ((lambda (x) (inc (inc x))) x))) x)))
  5))

;; =>

((lambda (x)
   ((lambda (x) ((lambda (x) (inc (inc x)))
                 ((lambda (x) (inc (inc x))) x)))
    ((lambda (x) ((lambda (x) (inc (inc x)))
                  ((lambda (x) (inc (inc x))) x))) x)))
 ((lambda (x) ((lambda (x) (inc (inc x)))
               ((lambda (x) (inc (inc x))) x)))
  ((lambda (x) ((lambda (x) (inc (inc x)))
                ((lambda (x) (inc (inc x))) x))) 5)))

;; =>

((lambda (x)
   ((lambda (x) ((lambda (x) (inc (inc x)))
                 ((lambda (x) (inc (inc x))) x)))
    ((lambda (x) ((lambda (x) (inc (inc x)))
                  ((lambda (x) (inc (inc x))) x))) x)))
 ((lambda (x) ((lambda (x) (inc (inc x)))
               ((lambda (x) (inc (inc x))) x)))
  ((lambda (x) (inc (inc x)))
   ((lambda (x) (inc (inc x))) 5))))

;; =>

((lambda (x)
   ((lambda (x) ((lambda (x) (inc (inc x)))
                 ((lambda (x) (inc (inc x))) x)))
    ((lambda (x) ((lambda (x) (inc (inc x)))
                  ((lambda (x) (inc (inc x))) x))) x)))
 ((lambda (x) ((lambda (x) (inc (inc x)))
               ((lambda (x) (inc (inc x))) x)))
  ((lambda (x) (inc (inc x)))
   (inc (inc 5)))))

;; =>

((lambda (x)
   ((lambda (x) ((lambda (x) (inc (inc x)))
                 ((lambda (x) (inc (inc x))) x)))
    ((lambda (x) ((lambda (x) (inc (inc x)))
                  ((lambda (x) (inc (inc x))) x))) x)))
 ((lambda (x) ((lambda (x) (inc (inc x)))
               ((lambda (x) (inc (inc x))) x)))
  ((lambda (x) (inc (inc x)))
   (inc 6))))

;; =>

((lambda (x)
   ((lambda (x) ((lambda (x) (inc (inc x)))
                 ((lambda (x) (inc (inc x))) x)))
    ((lambda (x) ((lambda (x) (inc (inc x)))
                  ((lambda (x) (inc (inc x))) x))) x)))
 ((lambda (x) ((lambda (x) (inc (inc x)))
               ((lambda (x) (inc (inc x))) x)))
  ((lambda (x) (inc (inc x)))
   7)))

;; =>

((lambda (x)
   ((lambda (x) ((lambda (x) (inc (inc x)))
                 ((lambda (x) (inc (inc x))) x)))
    ((lambda (x) ((lambda (x) (inc (inc x)))
                  ((lambda (x) (inc (inc x))) x))) x)))
 ((lambda (x) ((lambda (x) (inc (inc x)))
               ((lambda (x) (inc (inc x))) x)))
  (inc (inc 7))))

;; =>

((lambda (x)
   ((lambda (x) ((lambda (x) (inc (inc x)))
                 ((lambda (x) (inc (inc x))) x)))
    ((lambda (x) ((lambda (x) (inc (inc x)))
                  ((lambda (x) (inc (inc x))) x))) x)))
 ((lambda (x) ((lambda (x) (inc (inc x)))
               ((lambda (x) (inc (inc x))) x)))
  (inc 8)))

;; =>

((lambda (x)
   ((lambda (x) ((lambda (x) (inc (inc x)))
                 ((lambda (x) (inc (inc x))) x)))
    ((lambda (x) ((lambda (x) (inc (inc x)))
                  ((lambda (x) (inc (inc x))) x))) x)))
 ((lambda (x) ((lambda (x) (inc (inc x)))
               ((lambda (x) (inc (inc x))) x)))
  9))

;; =>

((lambda (x)
   ((lambda (x) ((lambda (x) (inc (inc x)))
                 ((lambda (x) (inc (inc x))) x)))
    ((lambda (x) ((lambda (x) (inc (inc x)))
                  ((lambda (x) (inc (inc x))) x))) x)))
 ((lambda (x) (inc (inc x)))
  ((lambda (x) (inc (inc x))) 9)))

;; =>

((lambda (x)
   ((lambda (x) ((lambda (x) (inc (inc x)))
                 ((lambda (x) (inc (inc x))) x)))
    ((lambda (x) ((lambda (x) (inc (inc x)))
                  ((lambda (x) (inc (inc x))) x))) x)))
 ((lambda (x) (inc (inc x)))
  (inc (inc 9))))

;; =>

((lambda (x)
   ((lambda (x) ((lambda (x) (inc (inc x)))
                 ((lambda (x) (inc (inc x))) x)))
    ((lambda (x) ((lambda (x) (inc (inc x)))
                  ((lambda (x) (inc (inc x))) x))) x)))
 ((lambda (x) (inc (inc x)))
  (inc 10)))

;; =>

((lambda (x)
   ((lambda (x) ((lambda (x) (inc (inc x)))
                 ((lambda (x) (inc (inc x))) x)))
    ((lambda (x) ((lambda (x) (inc (inc x)))
                  ((lambda (x) (inc (inc x))) x))) x)))
 ((lambda (x) (inc (inc x)))
  11))

;; =>

((lambda (x)
   ((lambda (x) ((lambda (x) (inc (inc x)))
                 ((lambda (x) (inc (inc x))) x)))
    ((lambda (x) ((lambda (x) (inc (inc x)))
                  ((lambda (x) (inc (inc x))) x))) x)))
 (inc (inc 11)))

;; =>

((lambda (x)
   ((lambda (x) ((lambda (x) (inc (inc x)))
                 ((lambda (x) (inc (inc x))) x)))
    ((lambda (x) ((lambda (x) (inc (inc x)))
                  ((lambda (x) (inc (inc x))) x))) x)))
 (inc 12))

;; =>

((lambda (x)
   ((lambda (x) ((lambda (x) (inc (inc x)))
                 ((lambda (x) (inc (inc x))) x)))
    ((lambda (x) ((lambda (x) (inc (inc x)))
                  ((lambda (x) (inc (inc x))) x))) x)))
 13)

;; =>

((lambda (x) ((lambda (x) (inc (inc x)))
              ((lambda (x) (inc (inc x))) x)))
 ((lambda (x) ((lambda (x) (inc (inc x)))
               ((lambda (x) (inc (inc x))) x))) 13))

;; =>

((lambda (x) ((lambda (x) (inc (inc x)))
              ((lambda (x) (inc (inc x))) x)))
 ((lambda (x) (inc (inc x)))
  ((lambda (x) (inc (inc x))) 13)))


;; =>
((lambda (x) ((lambda (x) (inc (inc x)))
              ((lambda (x) (inc (inc x))) x)))
 ((lambda (x) (inc (inc x)))
  (inc (inc 13))))

;; =>

((lambda (x) ((lambda (x) (inc (inc x)))
              ((lambda (x) (inc (inc x))) x)))
 ((lambda (x) (inc (inc x)))
  (inc 14)))

;; =>

((lambda (x) ((lambda (x) (inc (inc x)))
              ((lambda (x) (inc (inc x))) x)))
 ((lambda (x) (inc (inc x)))
  15))

;; =>

((lambda (x) ((lambda (x) (inc (inc x)))
              ((lambda (x) (inc (inc x))) x)))
 (inc (inc 15)))

;; =>

((lambda (x) ((lambda (x) (inc (inc x)))
              ((lambda (x) (inc (inc x))) x)))
 (inc 16))

;; =>

((lambda (x) ((lambda (x) (inc (inc x)))
              ((lambda (x) (inc (inc x))) x)))
 17)

;; =>

((lambda (x) (inc (inc x)))
 ((lambda (x) (inc (inc x))) 17))

;; =>

((lambda (x) (inc (inc x)))
 (inc (inc 17)))

;; =>

((lambda (x) (inc (inc x)))
 (inc 18))

;; =>

((lambda (x) (inc (inc x)))
 19)

;; =>

(inc (inc 19))

;; =>

(inc 20)

;; =>

21

Exercise 1.42

Exercise:

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)
49

Answer: 

(define (compose f1 f2)
  (lambda (x) (f1 (f2 x))))

Exercise 1.43

Exercise:

If \(f\) is a numerical function and \(n\) is a positive integer, then we can form the \(n^{th}\) 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 \(n^{th}\) repeated application of \(f\) is the function \(x \mapsto x+n\). If \(f\) is the operation of squaring a number, then the \(n^{th}\) repeated application of \(f\) is the function that raises its argument to the \(2^{n}\) -th 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 \(n^{th}\) repeated application of \(f\). Your procedure should be able to be used as follows: 

((repeated square 2) 5)
625

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

Answer: 

(define (repeated f n)
  (cond ((= x 1) f)
        ((= x 2) (compose f f))
        (else (compose f (repeated f (- n 1))))))

Exercise 1.44

Exercise:

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 obtain 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.

Answer: 

(define (smooth f)
  (lambda (x)
    (/ 3
       (+ (f (- x 0.01))
          (f x)
          (f (+ x 0.01))))))

(define (10th-smoothed-f f)
  ((repeated smooth 10) f))

Exercise 1.46

Exercise:

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 1.1.7 and the fixed-point procedure of 1.3.3 in terms of iterative-improve.

Answer: 

(define (iterative-improve good-enough? improve)
  (define (iterative-improve-inner guess)
    (if (good-enough? guess) guess
        (iterative-improve-inner (improve guess))))
  (lambda (x) (iterative-improve-inner x)))

(define (sqrt x)
  ((iterative-improve (lambda (guess)
                        (< (abs (- (square guess) x)) 0.001))
                      (lambda (guess)
                        (average guess (/ x guess))))
   1.0))
←

Please, send me an email if you have any comment.

Created with Emacs 28.2 (Org mode 9.5.5)