トラックバックが使えないじゃないの・・・

bloggerって、トラックバック使えないのね・・・

というわけで、はてなにお引越し。

ここです。

oicawaでアカウントとろうとしたら、既にいるって。
これ、ひょっとしたらむか～しはてなブックマーク使おうとして過去の俺が取ったやつかもしれんのだが、
パスワードが思い出せないので、
当時のアカウント取得時にはてなから送信されてきたメールは・・・と思ったら、
確か当時のメインで使ってたメールがyahooで、
ソフトバンクがyahooじゃぱん買収してから、
「日本人を逆差別するような企業のサービスなんか使うかボケ」と思って、
やっとの思いで手に入れたGoogleに全てのサービスをお引越ししたので、
パスワードとかさっぱり思い出せん。

諦めて新しいアカウント作った。

「awacio」

－

SchemeShellが普及すればよかったのに。

Windowsのバッチ処理のfor文なるものを初めて見て思ったこと。

こいつはファイルの操作が簡単にできるという意味で、UNIXにけるシェルスクリプトに相当する位置づけだと思う。
（機能的には全く追随できてないと思うけど）

どちらもファイル操作を簡単に済ますための概念があるように見え、
forで取得したモノを取り出すためにはforの構文で何ができるかを知る必要がある。
ま、これは別にbatでもshellscriptでも、他の言語でも多分そうだ。

だけど、Lisp系なら取り出したものは全てS式だ。
Gaucheならリストの中身はインタラクティブに見ることができるから、
ちょっと試してデータ構造を確認することもできる。
あとは「いつものように」carやcdr使って処理できる。

（って、ここまで書いてて、batでも同じようにDOSコマンドでやりゃできんじゃね？と思ったが、
　多分「表示用のフォーマットで出力される」から、for文で取り出した「データ構造」はわからんな。）

で、何が言いたいかというと、基本データ型が、あらゆるデータ構造を表現する万能なデータ型だったら、その問題領域合わせてその言語を適用できるから、楽だろうになぁと思ったということ。

リストなら、ファイルシステムで現在主流のツリー構造を表現するのに何の苦もないし、
それを統括的に処理するcarやcdrを知ってればとりあえず何でもできるわけで。

ま、でもそれ（carとかcdrとかでいちいち記述する手間）が面倒になるから、
WindowsのバッチやUNIXのシェルスクリプトの存在意義があるのか。
（但し、Windowsのバッチ処理＜＜＜＜越えられない壁＜＜＜＜シェルスクリプト）
あと、Lisp/Schemeのカッコだらけのコード。
初見での精神的敷居の高さはどうしても否定できないわなぁ。俺自身そうだったし。

それにしても、MonaOSのひげぽんさんがシェルをSchemeにしたのはこういうことも考えてなのかなぁと思った。
ご本人にお聞きしてみたいなぁ。

－

SICP 練習問題 1.21 （最少序数を求める）

ただ実行するだけ。


【問題】
smallest-divisor 手続きを使い、次の数の最少序数を見つけよ：
199, 1999, 19999


【解答】
まずは、セクションで定義してた関数群を再掲。これを踏まえて。

;最少の序数を求める
(define (smallest-divisor n)
  (find-divisor n 2))

;除数を求める処理
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

;除数かどうかの判別処理
(define (divides? a b)
  (= (remainder b a) 0))

で、実行すると、

gosh> (smallest-divisor 199)
199
gosh> (smallest-divisor 1999)
1999
gosh> (smallest-divisor 19999)
7
gosh> 

こんな感じ。なので、答えは、


199 の最少除数は 199
1999 の最少除数は 1999
19999 の最少除数は 7


となります。


－

SICP § 1.2.6 素数性のテスト（その２）

あんまり数学にかかずらわって本来の目的が遂行されないのもアレなので、
例のmodulo演算の展開は「そういうもの」として進むことにしました。

つーわけでコレです。

;ある数のべき乗を法とする剰余を求める関数
(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

;おまけ
;実行するときに定義されていないと動かないので一応。
(define (square x)
  (* x x))

で、次に

;Fermatテスト関数
(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random-integer (- n 1)))))

更に、

;Fermatテスト関数を指定回数実行する関数
(define (fast-prime? n times)
  (cond ((= times 0) #t)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else #f)))

実行結果はコレ。

gosh> (map (lambda (x) (cons x (fast-prime? x 10))) (iota 100 2))
((2 . #t) (3 . #t) (4 . #f) (5 . #t) (6 . #t) (7 . #t) (8 . #f) (9 . #f) (10 . #f)
(11 . #t) (12 . #f) (13 . #t) (14 . #f) (15 . #f) (16 . #f) (17 . #t) (18 . #f) (19 . #t) (20 . #f) 
(21 . #f) (22 . #f) (23 . #t) (24 . #f) (25 . #f) (26 . #f) (27 . #f) (28 . #f) (29 . #t) (30 . #f) 
(31 . #t) (32 . #f) (33 . #f) (34 . #f) (35 . #f) (36 . #f) (37 . #t) (38 . #f) (39 . #f) (40 . #f) 
(41 . #t) (42 . #f) (43 . #t) (44 . #f) (45 . #f) (46 . #f) (47 . #t) (48 . #f) (49 . #f) (50 . #f) 
(51 . #f) (52 . #f) (53 . #t) (54 . #f) (55 . #f) (56 . #f) (57 . #f) (58 . #f) (59 . #t) (60 . #f) 
(61 . #t) (62 . #f) (63 . #f) (64 . #f) (65 . #f) (66 . #f) (67 . #t) (68 . #f) (69 . #f) (70 . #f) 
(71 . #t) (72 . #f) (73 . #t) (74 . #f) (75 . #f) (76 . #f) (77 . #f) (78 . #f) (79 . #t) (80 . #f) 
(81 . #f) (82 . #f) (83 . #t) (84 . #f) (85 . #f) (86 . #f) (87 . #f) (88 . #f) (89 . #t) (90 . #f) 
(91 . #f) (92 . #f) (93 . #f) (94 . #f) (95 . #f) (96 . #f) (97 . #t) (98 . #f) (99 . #f) (100 . #f) (101 . #t))
gosh> 

・・・消化不良ですよ。


－

SICP § 1.2.6 素数性のテスト

いや～、わからねぇwww
まだこのセクション理解しきれてないので、以下、途中経過だけ書いておきます。



■除数の探索

覚えていますか素因数分解。「素数^n」の表記を使って自然数を分解していくアレです。
割ることができる素数が見つからない場合、その数は素数って言えるとか言えないとか。（どっちだよ。）

さて、この素因数分解してるときどうやって「これ以上割りきれる数はない」と判断していたか覚えてます？

例えば 131 という数字。

　
 2・・・ 2 × 65 +  1　ダメ。
 3・・・ 3 × 43 +  2　ダメ。
 5・・・ 5 × 26 +  1　ダメ。
 7・・・ 7 × 18 +  5　ダメ。
11・・・11 × 11 + 10　ダメ。
13・・・13 × 10 +  1　ダメ。

13でそれ以上計算するのやめますよね。
なんでここでやめることができるかというと、これ以上大きな値で探査しても、そのペアになる値はそれまで探査してきた小さい値、2 ～ 11 の範囲の数の再評価になってしまい、意味がないから。

だから、探査する値の２乗が、素数かどうか調べている数よりも大きくなった時点で打ちきることができるわけです。

11^2 = 121 < 131
13^2 = 169 > 131

それを踏まえて、この条件を終了条件とすると、素数を求める処理は次のように記述できます。

;呼び出すだけ
(define (smallest-divisor n)
  (find-divisor n 2))

;除数を求める処理
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n) ;これが上の終了条件。
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

;除数かどうかの判別処理
(define (divides? a b)
  (= (remainder b a) 0))

;素数かどうか判別する処理
(define (prime? n)
  (= n (smallest-divisor n)))

これはものすご～く素直な素数チェックのロジックなので得に問題なく理解できました。



■Fermatテスト

このセクション、読んだだけではさっぱり理解できないので、写経しながら自分の理解度を記述しながら進めてみます。

『Fermatの小定理』
n を素数、a を n より小さい任意の正の整数とすると、a の n 乗は n を法として a と合同である。

いや～、読むだけだとさっぱりわからん。一つ一つ順番に見ていきます。
まず登場人物の関係を表してみます。
実際の定理の文言を整理すると、こんな感じ？

n: 素数
a: a < n な自然数
a^n ≡ a (※nを法とする）

で、「法」ってなによ？という部分が、その次のカッコ内の記述にある感じ？

（二つの数は、両者を n で割った時、同じ剰余を持てば、n を法として合同という。
　数 a を n で割った剰余を、「n を法とした a の剰余」あるいは単に、
　「n を法とした a」（a modulo n)と言う。）

この部分はFermatの小定理とは無関係で、あくまで「○○を法とした△△」という表現についての説明だと思います。
だから、文中で出てくる n は、「Fermatの小定理の n」とは全然無関係な数だと考えるべきでしょう。
「○○を法とした△△」という表現を自分の脳内で道具として利用できるようにするには、この表現を見たときにすぐにイメージができるようにしておく必要があります。
なので、実はこの部分を理解するのが最優先事項だと思います。俺的には。
というわけで噛み砕いてみますね。

二つの数をそれぞれ a, b、この２つの数を割る値を n、それぞれの剰余を m_a, m_b、そして、（＋とか－とか×とか÷と同じように）剰余を求める数学的演算子として、modulo とすれば、次の関係式が成り立ちます。

a modulo n = m_a
b modulo n = m_b

で、もし、

m_a = m_b

ならば、

a と b は、n を法として合同

と表現すると。ようするに、

「a modulo n = b modulo n」ならば、「a と b は n を法として合同」と言える。

ということですね。 ここまで来るともう一つの重要な表現である、『数 a を n で割った剰余を、「n を法とした a」』 っていうのは、もはやなんてことなくて、単にその数の剰余を求めてますよ、ということになりますね。
今後、「n を法とした a」という文言を発見したら、脳内で「a modulo n の結果のこと」に即変換してやればいいわけです。
その上で、改めてFermatの小定理をもう一度みてみます。

n: 素数
a: a < n な自然数
a^n ≡ a (※nを法とする）

１行目、２行目はまぁいいとして、３行目！ これは次のように書き換えられますね。

n: 素数
a: a < n な自然数
a^n modulo n = a modulo n

やっと理解できた。。では続きを写経。
あ、その前に、「俺が」混乱しないように今やろうとしていることを整理しておきます。
今議論している内容は、

～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～
「Fermatの小定理を証明すること」ではなく、
「Fermatの小定理を利用して素数を求めるにはどうするか」
～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～

です。あぶねー。勘違いして時間を無駄にするところだったぜ。。

n が素数でない時、一般に a < n なる殆どの数について上の関係は成り立たない。
このことから次の素数性テストのアルゴリズムができる。

与えられた数 n に対し、 a < n なるランダムな数の n を法とした a^n の剰余を計算する。
結果が a でなければ、n は確実に素数ではない。
結果が a ならば、n が素数である確率は高い。
別の数 a をランダムにとり、同じようにテストする。
また等式が成り立つなら、n が素数であることに更に確信が持てる。
更にいろいろな a の値で確かめることで結果の確信度が増す。

このアルゴリズムはFermatテストとして知られている。

ここで話題にしてるのは、Fermatの小定理を使った、「Fermatテスト」なるものについて。 「法」の概念がわかりゃ、上の分かりにくい文章もすっきり整理できるっしょ。

主役： n
脇役： a (< n)
脚本： a^n modulo n
結末： m (= a^n modulo n)
       ① m ≠ a　→ n は素数ではない。
       ② m ＝ a　→ n は「素数である確率が高い」。
          この場合、ランダムに a を選んで同じ評価を繰り替えしていけば、
　　　　　より素数である確率が高くなる。

ここまでくれば、次のschemeの実装も理解できるかも？

Fermatテストを実装するには、ある数のべき乗の別の数を法とした剰余を計算する手続きがいる。

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

「ある数のべき乗の別の数を法とした剰余を計算する手続き」という表現に、文字変数も一緒に記述して欲しいなぁ。。
この定義式のアルゴリズムが理解できないが、定義式中の登場人物、base, exp, m の役割を推測してみると、こんな感じでしょうか。

base ： ある数（べき乗される数）？
exp  ： べき乗（する数）？
m    ： 別の数？

さて、この定義式のアルゴリズムについてですが・・・悲しくなる程理解できません。。
普通に考えたら再帰して「べき乗演算」を実施してからその結果に対して剰余算するのが素直なやり方だと思うんですが、この定義式は、自身を呼び出して、remainderまで含めて再帰している。。

・・・根本的に何かを見落としていそうだなぁ。 ちょっと数式で考えて行ってみましょう。

　
  base^exp modulo m
= (base * base * ... * base) modulo m  (※ (base * base * ... * base)は exp 回繰り返し）

modulo演算は四則演算と同じような位置づけだが、各種演算子に対してどういう法則（分配法則とか結合法則とか）が成り立つかどうかがミソっぽいですね。
ようするに、

= base * ((base * base * ... * base) modulo m)      (※ (base * base * ... * base)は exp-1 回繰り返し)
= base * base * ((base * base * ... * base) modulo m)  (※ (base * base * ... * base)は exp-2 回繰り返し)
　　・
　　・
　　・
= base * base * ... (base modulo m)              (※ base * base * ... は exp-1 回繰り返し)

のように変換ができると何となく再帰で処理できそうな・・・っていやいやいや、これは違うなwww
答えの数字がどんどんデカくなってっちゃうもの。

仕方ない、自分の脳みそで予想できないなら、定義式のアルゴリズムから何をしているかを解析してみましょう。
元の定義式の逐次平方を削除して簡略化して、正規順序評価してみます。
簡略化するとこんな感じ。

(define (expmod base exp m)
  (if (= exp 0)
      1
      (remainder (* base (expmod base (- exp 1) m))
                 m)))

で、例としてこんなパラメータでやってみます。

base = 7
exp  = 5
m    = 3

if構文は逐次評価してやると、こんなツリー構造になる。

(remainder
 (* 7 
    (remainder
     (* 7 
        (remainder
         (* 7 
            (remainder
             (* 7
                (remainder
                 (* 7 
                    1)
                 3))
             3))
         3))
     3))
 3)

こいつを数式にするとこんな風に記述できます。

((7 * ((7 * ((7 * ((7 * ((* 7 1) modulo 3)) modulo 3)) modulo 3)) modulo 3)) modulo 3)

え！？modulo演算てこんな風に展開されるの？？マジで？

シラネーヨw

ギブギブ！！これはもうそういうモンだと解釈して話を進めようw

と思ってたらこんなんありました。

冪剰余（Wikipedia）

この中の「途中で剰余を取る」って項目。
これ、証明できるんだろうなぁ。どうしようか。。


－

SICP 練習問題 1.20 （最大公約数算出で使用されているremainderの正規評価順序と作用評価順序について）

【問題】
手続きが生成するプロセスはもちろん解釈系が使う規則に依存する。
例えば、上で述べた反復的 gcd 手続きを考え、1.1.5節で論じた正規順序評価を使って解釈したとする。（if の正規順序評価規則は問題1.5に書いてある。）
（正規順序の）置き換え法を使い、(gcd 206 40) の評価で生成されるプロセスを図示し、実際に実行されるremainder演算を指示せよ。

(gcd 206 40) の正規順序評価で、remainder演算は実際に何回実行されるか。作用的順序ではどうか。


【解答】

問題が一体何をおっしゃってるのかさっぱりわかりません。。

で、とりあえず1.1.5節をもう一度読み直してみたら少し理解できた。
ここ、多分華麗にスルーしたところですよ。（Schemeやらせろーっ！って思ってすっ飛ばしたところ。）

問題文中にでてくる、正規順序評価とか作用的順序(評価）というのは、

○正規順序評価
　　　基本的演算子だけを持つ式が出てくるまでパラメタへの被演算子の式の置き換えを繰り返し、
　　　基本的演算子が出現してから初めて評価を行う方式。

○作用的順序評価
　　　引数を評価してから作用させる方式。

ということらしい。ここらへん、多分SICPの後半で効いてきそうな気がするぜ。

もっとイメージしやすいお話が、ここで行われている。。
http://www.bookshelf.jp/2ch/tech/1002584344.html#725

すげーなぁ2ch。集合知だよねぇ。

ここ読んでて、以前俺様言語インタプリタを実装してた頃の事を思い出した。
「普通、関数に渡す引数って、その関数の中に入る前に評価するよね～」と、
まったく疑問にも思わず実装したことを思い出したぜ。
これが作用的順序評価に相当し、評価する前に関数に渡してしまうのが正規順序評価なわけだ。
正規順序評価なんて、どーやって実装すんだよ脳みそ溶けちまうわ。

んでは早速この問題を解いてみよう。


まずは正規順序評価から。

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))


(gcd 206 40)
(gcd 40 (remainder ...

まて、remainderって基本演算子？てか、基本演算子の定義って何よ？
まぁいいや。remainderは基本演算子じゃないと考えてみるか。

(if (= 40 0)
    206
    (if (= (remainder 206 40) 0)
        40
        (if (= (remainder 40 (remainder 206 40)) 0)
            (remainder 206 40)
            (if (= (remainder (remainder 206 40) 
                              (remainder 40 (remainder 206 40))) 0)
                (remainder 40 (remainder 206 40))
                (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)))))
                (if (= (remainder (remainder 40 (remainder 206 40)) 
                                  (remainder (remainder 206 40)
                                             (remainder 40 (remainder 206 40)))) 0)
                    (remainder (remainder 206 40) 
                               (remainder 40 (remainder 206 40)))
                    (gcd (remainder (remainder 40 (remainder 206 40)) 
                                    (remainder (remainder 206 40)
                                               (remainder 40 (remainder 206 40))))
                         (remainder (remainder (remainder 206 40)
                                               (remainder 40 (remainder 206 40)))
                                    (remainder (remainder 40 (remainder 206 40)) 
                                               (remainder (remainder 206 40)
                                                          (remainder 40
                                                                     (remainder 206 40)))))))))))

最後の if で、条件式が #t になる。とりあえず動くかどうかやってみる。

gosh> (if (= 40 0)
    206
    (if (= (remainder 206 40) 0)
        40
        (if (= (remainder 40 (remainder 206 40)) 0)
            (remainder 206 40)
            (if (= (remainder (remainder 206 40) 
                              (remainder 40 (remainder 206 40))) 0)
                (remainder 40 (remainder 206 40))
                (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)))))
                (if (= (remainder (remainder 40 (remainder 206 40)) 
                                  (remainder (remainder 206 40)
                                             (remainder 40 (remainder 206 40)))) 0)
                    (remainder (remainder 206 40) 
                               (remainder 40 (remainder 206 40)))
                    (gcd (remainder (remainder 40 (remainder 206 40)) 
                                    (remainder (remainder 206 40)
                                               (remainder 40 (remainder 206 40))))
                         (remainder (remainder (remainder 206 40)
                                               (remainder 40 (remainder 206 40)))
                                    (remainder (remainder 40 (remainder 206 40)) 
                                               (remainder (remainder 206 40)
                                                          (remainder 40
                                                                     (remainder 206 40)))))))))))
*** ERROR: Compile Error: syntax-error: malformed if: (if (= (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) 0) (remainder 40 (remainder 206 40)) (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))))) (if (= (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) 0) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) (gcd (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) (remainder (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))))))
"(stdin)":65:(if (= 40 0) 206 (if (= (remainder 2 ...

Stack Trace:
_______________________________________
gosh> 

うげ。あ、ちょっとまてよ？ifは構文オブジェクトだからなんか特殊な評価をするんだっけ？
問題文にifに関する記述があるんじゃん。

（if の正規順序評価規則は問題1.5に書いてある。）

問題 1.5・・・既に通って来た道なのに。。とりあえず引用してみる。



特殊形式ifの評価規則は、解釈系が正規順序と作用的順序のどちらを使うかに無関係に同じとする。
述語式を最初に評価し、その結果が帰結式と代替式のいずれを評価するかを決める。


おおっと。つまりifが出てきた時点で評価が一発走るわけですね？
（この解釈であってんのか？）

つまり・・・


■１回目

(if (= 40 0)
    206
    (gcd 40 (remainder 206 40)))

は、述語式(= 40 0)が #f になるので、次に評価するのは代替式の

(gcd 40 (remainder 206 40))

■２回目
１回目の引数を評価せずにそのまま使用すると、

(if (= (remainder 206 40) 0)
    40
    (gcd (remainder 206 40) (remainder 40 (remainder 206 40))))

１回目と同じく述語式を評価するとまだ #f 。


■３回目
繰り返して、

(if (= (remainder 40 (remainder 206 40)) 0)
    (remainder 206 40)
    (gcd (remainder 40 (remainder 206 40))
         (remainder (remainder 206 40) 
                    (remainder 40 (remainder 206 40)))))

述語式を評価するとまだ #f 。


■４回目
繰り返して、

(if (= (remainder (remainder 206 40) 
                  (remainder 40 (remainder 206 40))) 0)
    (remainder 40 (remainder 206 40))
    (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))))))

述語式を評価するとまだ #f 。

■５回目
繰り返して、

(if (= (remainder (remainder 40 (remainder 206 40)) 
                  (remainder (remainder 206 40) 
                             (remainder 40 (remainder 206 40)))) 0)
    ; 帰結式（ここから）
    (remainder (remainder 206 40) 
               (remainder 40 (remainder 206 40)))
    ; （ここまで）
    (gcd (remainder (remainder 40 (remainder 206 40)) 
                    (remainder (remainder 206 40) 
                               (remainder 40 (remainder 206 40))))
         (remainder (remainder (remainder 206 40) 
                               (remainder 40 (remainder 206 40))) 
                    (remainder (remainder 40 (remainder 206 40)) 
                               (remainder (remainder 206 40) 
                                          (remainder 40 (remainder 206 40)))))))

述語式を評価するとやっと #t 。
ここに至るまでに、remainder演算子はif（条件式）で次のように呼ばれている。

１回目：０回
２回目：１回
３回目：２回
４回目：４回
５回目：７回

なので、if中では合計14回。


んで、全て置き換え完了後は、帰結式側が評価されるので、合計４回。


疲れた。。






さて次。作用的評価順序だ。

これは簡単だろう。

(gcd 206 40)


(if (= b 0)
    a
    (gcd b (remainder a b)))

■１回目

(if (= 40 0)
    206
    (gcd 40 (remainder 206 40)))

条件式が#fなので、代替式が評価される。
作用的評価順序の場合は演算子より先に被演算子が評価されるので、
このタイミングでremainderが評価され、

(gcd 40 6)

となる。

■２回目

(if (= 6 0)
    40
    (gcd 6 (remainder 40 6)))

条件式が#fなので、代替式が評価される。
１回目と同じくこのタイミングでremainderが評価され、

(gcd 6 4)

■３回目

(if (= 4 0)
    6
    (gcd 4 (remainder 6 4)))

条件式が#fなので、代替式が評価される。
２回目と同じくこのタイミングでremainderが評価され、

(gcd 4 2)

■４回目

(if (= 2 0)
    4
    (gcd 2 (remainder 4 2)))

条件式が#fなので、代替式が評価される。
３回目と同じくこのタイミングでremainderが評価され、

(gcd 2 0)

■５回目

(if (= 0 0)
    2
    (gcd 0 (remainder 2 0)))

条件式が#tなので、帰結式が評価される。
故に答えは 2 。



１～４回目まで、一回ずつremainderが評価されているので
合計４回呼ばれたことになる。



これであってんのかなぁ。。。


－

SICP § 1.2.5 最大公約数 （Euclidのアルゴリズム）

Euclidのアルゴリズム

最大公約数について。

２つの整数 a, b の最大公約数を求める場合、普通は両方の数を素因数分解して、
共通因子を取り出して乗算するけど、もっと効率のいい、すげーアルゴリズムがあるみたい。

このアルゴリズムは、

「a を b で割った剰余を r とすると、
　a と b の公約数は b と r の公約数とまったく同じである」

という考え方に基づいているとのこと。


どういう事かというと、最大公約数を求める関数を GCD とすると、

GCD(a, b) = GCD(b, r)

具体的には、

GCD(206, 40) = GCD(40, 6)   ・・・ 6 = 206 % 40
             = GCD(6, 4)
             = GCD(4, 2)
             = GCD(2, 0)
             = 2

で、204 と 40 の最大公約数は 2 になるそうだ。
お～って思ったんだけど、
な～んかどっかで聞いたような話なんだが、どこで聞いたか思い出せない。。

Schemeで実装するとこんな感じ。
remainder関数は２つの引数の剰余を求める関数です。

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

ほほう。


－