Scheme - 手続きとその生成するプロセス(最大公約数)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション)の1(手続きによる抽象の構築)、1.2(手続きとその生成するプロセス)、1.2.5(最大公約数)の問題1.20を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 1.20.

正規順序評価。

(gcd 206 40)

(gcd 40
     (remainder 206 40))

; 1回
(gcd (remainder 206 40)
     (remainder 40
                (remainder 206 40)))

; 2回
(gcd (remainder 40
                (remainder 206 40))
     (remainder (remainder 206 40)
                (remainder 40
                           (remainder 206 40))))

; 4回
(gcd (remainder (remainder 206 40)
                (remainder 40
                           (remainder 206 40)))
     (remainder (remainder 40
                           (remainder 206 40))
                (remainder (remainder 206 40)
                           (remainder 40
                                      (remainder 206 40)))))
; 7回
(remainder (remainder 206 40)
           (remainder 40
                      (remainder 206 40)))

; 2回
(remainder 6
           (remainder 40 6))

; 1回
(remainder 6 4)

; 1回
2

ということで、1 + 2 + 4 + 7 + 2 + 1 + 1 = 18回。

作用的順序評価。

(gcd 206 40)

(gcd 40 (remainder 206 40))

; 1回
(gcd 40 6)

(gcd 6 (remainder 40 6))

; 1回
(gcd 6 4)

(gcd 4 (remainder 6 4))

; 1回
(gcd 4 2)

(gcd 2 (remainder 4 2))

; 1回
2

ということで、4回。