Maestumプログラミング、囲碁、読書の話題この広告は、90日以上更新していないブログに表示しています。LandinのSECDマシンについて。Computersという本を読んでいる。semanticsを与えうる抽象機械の説明にかなりの分量を割いている。machineについての解説がある。machineがLispといろいろと関係深いのと、実装が比較的簡単だった上に言語処理系を開発してみたい人には面白い題材になりそうだったので紹介したい。SECDの歴史的背景とLispSECDは前述のようにラムダ計算を実行できる抽象機械である。Expressionsでラムダ計算と実際的なプログラミングを直接結びつけるためのモデルとして提唱されている。この論文が出たのは1964年。MachineでLispを世に出した4年後で、当然LandinはLispを相当意識していた。Expressionsの終わりに挙げられている参考文献の9つのうち4つは数学・論理学のもの、2つはDijkstraのもの、そして3つはLisp関係(うち2つはMcCarthyのもの)である。Registerというワードからして機械寄りだ)のに対して、より抽象的なモデルを提唱する意味があったのであろう。Languagesという論文で、Lispよりも数学的記述に近い記法が使える関数型言語ISWIMを打ち出した。ISWIMは実用のための実装はされなかったものの、その後の関数型言語(Lisp系やML系)の発展に大きく寄与したことで知られている。ExpressionがISWIMのさらに下にあるものとして紹介されているので、ISWIMを作り上げた時にSECDマシンのことも念頭にあったのはたしかだろう。LanguagesにはLispの話もたくさん出てくる。Lispを作成、配布する。その頃大抵の大学のマシンに載っていたPascalで書かれたSECDマシンと純LISPからそのマシンの命令セットへのコンパイラで、純粋関数型言語でいろいろな言語仕様の研究などができたようだ。Implementation」が詳しい。Computersの記述をベースに、抽象機械そのものと「純LISPに近いもののASTからSECDマシン命令へのコンパイラ」を実装してみた。Hickeyも「静的型付き関数型言語は言語実装するときにはぴったり」と言っていたことだし大目に見てほしい。ちなみにSchemeやCでの実装はこちらに詳しい。QiitaにはHaskellでの実装もあった。軽く実装を見ていきながらSECDマシンの特徴を追っていきたい。int「なんらかの値を表す整数」、「ポインタを表す整数を二つ持つConsセル」の二つだけ。これでプログラムもデータもすべて表現できる。このミニマルさがLispっぽい。1;これらはすべてメモリセルのどこかを指している。SECDマシンの名前ははじめの四つのレジスタから来ている。Fレジスタかわいそう・・・SレジスタはStack。SECDはスタックマシンで、Sレジスタが指しているリストの先頭からデータをとってプロセスしてまたそのリストの先頭に載せる、という挙動でデータが変更されていく。EレジスタはEnvironment。変数の値を保持する環境を表すリストを指している。index化したもの。CレジスタはControl。プログラムがSECDマシン命令にコンパイルされたあと、Consリスト化されメモリにロードされる。そのロードされたプログラム上で次実行するべき命令が載っているメモリセルを指すのがCレジスタだ。DレジスタはDump。条件分岐や関数呼び出しがある場合、スタックや環境、コントロールをいったん別のものに変え、分岐や呼び出しが終了した時点で現在の場所に戻ってきたい。そのための「現在のS、E、Cレジスタの値を一時退避させておくリスト」をDレジスタが指す。Cellから(多分)。未使用のメモリセルの位置を指している。は高いレジスタなのだがマシンの名前には入れてもらえなかった。Fレジスタかわいそう・・・ただ、Fレジスタはよく使われるが、コード上で現れることは珍しい。Cellから作るのでそのロジックを隠蔽する。Cellを直接参照する必要がない。0であるならば停止命令STOPとして認識し、Cレジスタを0番地(NILとして扱う)を指すようにする。1ならNILとして認識し、sスタックの先頭がNILへのポインタになるようにする(スタックをNILにするのではないことに注意)。SECDにはSTOPやNILのような命令がいくつかある。資料によってその数字がまちまちなのはご愛嬌だ。Computersも実はすべてのPrimitiveを提示してくれないので、他をあたる必要がある。RAPで再帰関数の実行(DUMでその再帰関数のための「書き換え用の環境」を作って、LDFで再帰関数とその環境をスタックに乗せ、そしてRAPで実行する)一番実装がややこしいのはRAPで、すでに何かが書き込まれたセル(Fレジスタからとってこなかったセル)に破壊的代入をするのはここだけ。他の命令の実装はすべて純粋関数でも書けるはず(書いている言語のメモリマネジメントにただのりする前提であれば)。()C、E、Sレジスタの順番にDレジスタに値を移してから変更していく様が伝わると嬉しい。rplaca関数でnenvの先頭にargへのポインタを破壊的代入する。個々の命令やLispから命令へのコンパイラの説明はまた別の機会に。Computersだったのだが、この本はどちらかというと思想を含めたアイディアと背景を語ってくれる本で、実装のための情報はちょっと薄かった。ある程度想像を働かせてコードに変換していく必要がある。RAP命令の説明に関しては間違いがあって、その部分では半日実装せずに悩んでしまった。(SECDマシンの状態遷移表のRAPの項目で、Eレジスタの内容の結果がrplaca((nil.e),v)になるはずがrplaca((nil.e),v).eになっている。Implementationのほうがすぐれていそうだ。Lispという純粋関数型LispをSECDマシンで実装する詳細が載っている。AoSCにはそれ以外の部分で価値が十分すぎるほどあるが。今回話せなかった最適化やガベージコレクション各種、Call-by-Need化などの話題も載っている。Machineへと話が続いていく。Machine古のLispの話をする場合大抵ノスタルジアとともに語られるトピックが「Lispマシン」だ。Instruments社やXerox社、専業だとSymbolics社とLMI社が出していた、ハードウエアレベルでLispをサポートするコンピュータ。Generaで使ってたよ」的なコメントがつくのを散見することがある。Lispの強力さと先進性のひとつの現れだろう(そしてもしかすると弱点も、かも)その源流はLisp発祥の地であるマサチューセッツ工科大学の人工知能研で開発されたCONSマシンとその後継機であるCADRマシン(「次に来るもの」の意)にある。Knightの修士論文の題材だったようだ。ComputersではこのCADRマシンについてある程度詳しく解説している(といっても実装の雰囲気くらいまでだが)。実は個人的にはこれが最大の目的で読んでいた。CADRのアーキテクチャはSECDマシンに非常に近いようだ。IntやConsといったデータタグのついたメモリと、そのタグごとひとつのワードとして処理できるだけの容量をもったプロセッサチップ。SECDマシンをハードウエア化するとこのような形になるだろうか、と思わせるところがある。いくつかの顕著な違いとしてはタグの種類が多い。timeになってしまう)といったものがあるようだ。命令セットについてもmicrocode、macrocodeそしてMacLispでプログラムが書けるようになっており、microcodeやmacrocodeとSECD命令セットの関係はAoSCではあまりはっきりとは書いていない(macrocodeがより一般的なスタックマシンの命令セットに近いものである、という記述はある)。CADRではSECDマシンへの言及がない。実際どの程度この仮想マシンを意識してCONSマシン、CADRマシンが開発されたのかは残念ながら不明なようだ。machineを現代に蘇らせようと思った時はこれ以外の文献も多分必要になると思う。最後に抽象機械SECDは実装も比較的簡単なうえ、純LispやISWIMなどの関数型言語のコンパイル先として楽なので、言語実装で遊んでみたい人にはオススメだと思う。Lispや計算機科学の歴史に浸った気分になれるというボーナス付き。Neumannモデルとは一線を画す実行モデルを持った抽象機械がいくつも紹介されている。機会があったら是非(大学図書館などで)手に取ってみてほしい。)はてなブログをはじめよう!zehnpaardさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。