小池有话说

Exercise 1.41. 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)

It is simple to write double down.

(define (double f)
  (lambda (x) (f (f x))))

or

(define double
  (lambda (f)
    (lambda (x) (f (f x)))))

than the question is: how to evalute the final result with only your head permitted?

let R0 = (((double (double double)) inc) 5), which is the final result.

let F4 = (double double).

let F16 = (double F4).

then F16 = (lambda (x) (F4 (F4 x)))

then (F16 inc) = (F4 (F4 inc))

as we know

(F4 f) = ((double double) f)
= ((lambda (x) (double (double x))) f)
= (double (double f))

so (F4 inc) = (double (double inc))

let F4-inc = (F4 inc)

then (F4 F4-inc) = (double (double F4-inc)) = (double (double (double (double inc))))

let F2-inc' = (double inc)

then F2-inc' = (lambda (x) (inc (inc x)))

let F4-inc' = (double F2-inc') = (lambda (x) (F2-inc' (F2-inc' x)))

let F8-inc' = (double F4-inc') = (lambda (x) (F4-inc' (F4-inc' x)))

let F16-inc' = (double F8-inc') = (lambda (x) (F8-inc' (F8-inc' x)))

F16-inc' = (double (double (double (double inc)))) = (F4 (F4 inc)) = (F16 inc) = ((dboule F4) inc) = ((double (double double)) inc)

R0 
= (F16-inc' 5) 
= (F8-inc' (F8-inc' 5)) 
= (F8-inc' (F4-inc' (F4-inc' 5))) 
= (F8-inc' (F4-inc' (F2-inc' (F2-inc' 5)))) 
= (F8-inc' (F4-inc' (F2-inc' (inc (inc 5))))) 
= (F8-inc' (F4-inc' (F2-inc' (inc 6)))) 
= (F8-inc' (F4-inc' (F2-inc' 7))) 
= (F8-inc' (F4-inc' (inc (inc 7)))) 
= (F8-inc' (F4-inc' 9)) 
= (F8-inc' (F2-inc' (F2-inc' 9))) 
= (F8-inc' (F2-inc' (inc (inc 9)))) 
= (F8-inc' (F2-inc' 11))
= (F8-inc' (inc (inc 11)))
= (F8-inc' 13)
= (F4-inc' (F4-inc' 13))
= (F4-inc' (F2-inc' (F2-inc' 13)))
= (F4-inc' (F2-inc' (inc (inc 13))))
= (F4-inc' (F2-inc' 15))
= (F4-inc' (inc (inc 15)))
= (F4-inc' 17)
= (F2-inc' (F2-inc' 17)))
= (F2-inc' (inc (inc 17)))
= (F2-inc' 19)
= (inc (inc 19))
= 21