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