Understanding Computation
p.27-33 文(statement)の途中まで
SIMPLEにおける式 (expression)
構文にある要素(Number, Add, Multiply)ごとにRubyのクラスとして定義
上記クラスのインスタンスからなる木として式を表現する
簡約(reduce)
構文をステップで簡約(ここでの例の場合、演算)することによってプログラムを評価していき最終結果を得る
要素は簡約可能・不可能によって分けることができる(要素ごとにreducible?メソッドを定義)
式が簡約不可能になるまで繰り返し簡約(reduceメソッドを呼び出す)することで式を完全に評価できる
irbで式を保持し、#reducible?と#reduceを繰り返し呼び出すことで式を評価する抽象機会を手作業でシミュレートしてきた
手作業!?→自動化
仮想機械 Machine
クラスを定義して簡約不可能になるまで#runでやってもらう
足し算・掛け算の他に引き算・割り算、ブール値や論理演算なども実装できる
class Boolean < Struct . new ( :value )
class LessThan < Struct . new ( :left , :right )
ここまでの仮想機械の状態は現在の式のみ
振る舞いは状態を変化させる規則の集まりによって記述される
現在の式を記録しつつ、これ以上簡約できなくなるまで状態を更新しつつける機械
値を意味のある名前で示すことができるもの
変数は簡約可能
変数名から値へのマッピングである環境(environment)を保持する必要がある
SIMPLEではRubyのハッシュを使う
変数の簡約は環境から変数名の名前を返すだけ
これまでの#reduceメソッドの引数にenvironmentを渡すように再実装する
仮想機械にも環境を追加して再実装
class Machine < Struct . new ( :expression , :environment )
Machine . new (
Add . new ( Variable . new ( :x ) , Variable . new ( :y ) ) , # expression
{ x : Number . new ( 3 ) , y : Number . new ( 4 ) } # environment
)
文(statement)の目的は評価されることで抽象機械の状態を変更すること
SIMPLEの文は現在の環境を置き換える新たな環境を生成できるようにする
class DoNothing
. ..
def ==( other_statement )
other_statement . instance_of? ( DoNothing )
end
def reducible?
false
end
end
プログラムの実行が完了したことを示すための特別な文として使う
簡約規則がどうあるべきかを決める必要がある
例: 代入(assignment) -> x = x + 1
代入文は変数x
と等号と式x + 1
で構成される
代入文の式が簡約可能であれば簡約規則に従って簡約していく
{ x: Number.new(2) }
であれば x = 2 + 1
に、足し算は簡約できるので x = 3
になる
簡約できなくなったら代入を実行する
代入を実行 = 値をしかるべき変数名に関連付けるように環境を更新する
代入を実行して環境を更新した後は代入文も簡約される必要がある
そうしなければ抽象機械はx
への3の代入を保持し続けなければならない
そのために何もしない文(do-nothing)が必要になる
代入文の式が簡約可能な場合は式を簡約する。結果は簡約された代入文と変更のない環境
代入文の式が簡約不可能な場合は式を代入文の変数と関連付けた新しい環境を更新する。結果はdo-nothing文と新しい環境
式は簡約した式だけを返し、環境を返さない
文は新しい環境を返す
文は環境を変更する = 純粋ではない(impure)