SICP問題4.21

再帰手続きをletrec(やdefineさえ)使わずに指定する。次の式は再帰的な階乗手続きを作用させ、10の階乗を計算する

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

a. (式を評価することで)これが実際に階乗を計算することを調べよ。Fibonacci数を計算する類似の式を考えよ

実際に実行してみる

;;; M-Eval input:
((lambda (n)
   ((lambda (fact)
      (fact fact n))
    (lambda (ft k)
      (if (= k 1)
          1
          (* k (ft ft (- k 1)))))))
 10)

;;; M-Eval value:
3628800

;;; M-Eval input:

確かに実行できている

fibonacciバージョン
元のfibonacci

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

lambdaのみでの実装

((lambda (n)
   ((lambda (fib)
      (fib fib n))
    (lambda (fb k)
      (cond ((= k 0) 0)
            ((= k 1) 1)
            (else (+ (fb fb (- k 1))
                     (fb fb (- k 2))))))))
 10)

b. 相互に再帰的な内部手続きを持つ次の手続きを書き換える

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

内部定義もletrecも使わないfの別の定義

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