Exercise 4.21 · 习题

Exercise 4.21: Amazingly, Louis’s intuition in
Exercise 4.20 is correct. It is indeed possible to specify recursive
procedures without using letrec (or even define), although the
method for accomplishing this is much more subtle than Louis imagined. The
following expression computes 10 factorial by applying a recursive factorial
procedure:

((lambda (n)
((lambda (fact) (fact fact n))
(lambda (ft k)
(if (= k 1)
1
(* k (ft ft (- k 1)))))))
10)

Check (by evaluating the expression) that this really does compute factorials.
Devise an analogous expression for computing Fibonacci numbers.

Consider the following procedure, which includes mutually recursive internal
definitions:

(define (f x)
(define (even? n)
(if (= n 0)
true
(odd? (- n 1))))
(define (odd? n)
(if (= n 0)
false
(even? (- n 1))))
(even? x))

Fill in the missing expressions to complete an alternative definition of
f, which uses neither internal definitions nor letrec:

(define (f x)

((lambda (even? odd?)

(even? even? odd? x))

(lambda (ev? od? n)

(if (= n 0)

true

(od? ⟨??⟩ ⟨??⟩ ⟨??⟩)))

(lambda (ev? od? n)

(if (= n 0)

false

(ev? ⟨??⟩ ⟨??⟩ ⟨??⟩)))))

练习 4.21：令人惊讶的是，Louis 在练习 4.20 中的直觉是正确的。确实有可能不使用 letrec（甚至不使用 define）来描述递归过程，尽管实现这一点的方法比 Louis 所设想的要微妙得多。以下表达式通过应用一个递归的阶乘过程来计算 10 的阶乘：

((lambda (n)
((lambda (fact) (fact fact n))
(lambda (ft k)
(if (= k 1)
1
(* k (ft ft (- k 1)))))))
10)

请（通过对表达式求值）验证这确实能计算阶乘。构造一个类似的计算 Fibonacci 数的表达式。

考虑以下含有互递归内部定义的过程：

(define (f x)
(define (even? n)
(if (= n 0)
true
(odd? (- n 1))))
(define (odd? n)
(if (= n 0)
false
(even? (- n 1))))
(even? x))

请填入缺失的表达式，完成 f 的另一种定义——该定义既不使用内部定义，也不使用 letrec：

(define (f x)
((lambda (even? odd?)
(even? even? odd? x))
(lambda (ev? od? n)
(if (= n 0)
true
(od? ⟨??⟩ ⟨??⟩ ⟨??⟩)))
(lambda (ev? od? n)
(if (= n 0)
false
(ev? ⟨??⟩ ⟨??⟩ ⟨??⟩)))))