SICP 問題 1.20 （最大公約数算出で使用されているremainderの正規評価順序と作用評価順序について）
【問題】
手続きが生成するプロセスはもちろん解釈系が使う規則に依存する。
例えば、上で述べた反復的 gcd 手続きを考え、1.1.5節で論じた正規順序評価を使って解釈したとする。
（if の正規順序評価規則は問題1.5に書いてある。）
（正規順序の）置き換え法を使い、(gcd 206 40) の評価で生成されるプロセスを図示し、
実際に実行されるremainder演算を指示せよ。
(gcd 206 40) の正規順序評価で、remainder演算は実際に何回実行されるか。
作用的順序ではどうか。
【解答】
問題が一体何をおっしゃってるのかさっぱりわかりません。。
で、とりあえず1.1.5節をもう一度読み直してみたら少し理解できた。
ここ、多分華麗にスルーしたところですよ。（Schemeやらせろーっ！って思ってすっ飛ばしたところ。）
問題文中にでてくる、正規順序評価とか作用的順序(評価）というのは、
ということらしい。
○正規順序評価
基本的演算子だけを持つ式が出てくるまでパラメタへの被演算子の式の置き換えを繰り返し、
基本的演算子が出現してから初めて評価を行う方式。
○作用的順序評価
引数を評価してから作用させる方式。
ここらへん、多分SICPの後半で効いてきそうな気がするぜ。
もっとイメージしやすいお話が、ここで行われている。。
すげーなぁ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)) (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))
(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に関する記述があるんじゃん。問題 1.5・・・既に通って来た道なのに。。
（if の正規順序評価規則は問題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が評価されているので
合計４回呼ばれたことになる。
これであってんのかなぁ。。。
