Arantium Maestum

プログラミング、囲碁、読書の話題

SECDマシンとLispあれこれ

書籍 言語処理系

時には昔の話をしようか、ということでPeter LandinのSECDマシンについて。Lisp Advent Calendar 2018 23日目の記事。

はじめに

最近、長らく積読してたThe Architecture of Symbolic Computersという本を読んでいる。

There is a revolution looming in computer science … the basic von Neumann model of computing, which has ruled unchallenged for the last 40 years, is encountering not one but several potentially heavy weight challengers. … Achieving ... (the book's) ... goals should give the reader the ability to follow, or better yet participate in, construction of the languages and computing systems that will become the everyday computational tools of tomorrow.

と序文冒頭からかなり熱く語る本で、関数型言語と論理型言語の計算モデルのoperational semanticsを与えうる抽象機械の説明にかなりの分量を割いている。

HaskellのようなCall-by-Needな遅延評価戦略をとる関数型言語の抽象機械であるG machine（グラフ簡約マシン？）やPrologなどの論理型言語の抽象機械であるWarren machineなどにまじって、ラムダ計算とS式のための抽象機械、SECD machineについての解説がある。

このSECD machineがLispといろいろと関係深いのと、実装が比較的簡単だった上に言語処理系を開発してみたい人には面白い題材になりそうだったので紹介したい。

SECDの歴史的背景とLisp

SECDは前述のようにラムダ計算を実行できる抽象機械である。Peter Landinの論文Mechanical Evaluation of Expressionsでラムダ計算と実際的なプログラミングを直接結びつけるためのモデルとして提唱されている。この論文が出たのは1964年。

McCarthyがRecursive Functions of Symbolic Expressions and their Evaluation by MachineでLispを世に出した4年後で、当然LandinはLispを相当意識していた。

Mechanical Evaluation of Expressionsの終わりに挙げられている参考文献の９つのうち４つは数学・論理学のもの、２つはDijkstraのもの、そして３つはLisp関係（うち２つはMcCarthyのもの）である。ただ、その時期のLispがかなり実装を反映した「機械寄り」のものだった（そもそもContents of Address Register, Contents of Decrement Registerというワードからして機械寄りだ）のに対して、より抽象的なモデルを提唱する意味があったのであろう。

その後Landinはさらに有名なThe Next 700 Languagesという論文で、Lispよりも数学的記述に近い記法が使える関数型言語ISWIMを打ち出した。ISWIMは実用のための実装はされなかったものの、その後の関数型言語（Lisp系やML系）の発展に大きく寄与したことで知られている。

WikipediaによるとこのISWIMのoperational semanticsをSECDマシンで定義しているとあるのだが、The Next 700 Languages自体にはSECDはでてこない・・・　ただThe Mechanical Evaluation of Expressionsで重要な概念であるApplicative ExpressionがISWIMのさらに下にあるものとして紹介されているので、ISWIMを作り上げた時にSECDマシンのことも念頭にあったのはたしかだろう。ちなみにNext 700 LanguagesにはLispの話もたくさん出てくる。あとlet式の初出。

その後1980年にPeter HendersonがSECDマシンを実際のインタプリタとしてLispKit Lispを作成、配布する。その頃大抵の大学のマシンに載っていたPascalで書かれたSECDマシンと純LISPからそのマシンの命令セットへのコンパイラで、純粋関数型言語でいろいろな言語仕様の研究などができたようだ。

LispKit LispについてはHenderson自身の書いた「Functional Programming Application and Implementation」が詳しい。（こちらの本も今回の記事のネタ本の一つなのだが、つい先週入手したばかりなのでまだちゃんと読み込めていない・・・）

SECDマシンの特徴と実装

とりあえずThe Architecture of Symbolic Computersの記述をベースに、抽象機械そのものと「純LISPに近いもののASTからSECDマシン命令へのコンパイラ」を実装してみた。

github.com

ただしLisp Advent Calendarなのに実装言語はOCamlである・・・　（最近自分が勉強中という理由） まあRich Hickeyも「静的型付き関数型言語は言語実装するときにはぴったり」と言っていたことだし大目に見てほしい。ちなみにSchemeやCでの実装はこちらに詳しい。QiitaにはHaskellでの実装もあった。

軽く実装を見ていきながらSECDマシンの特徴を追っていきたい。

SECDマシンのメモリモデルは以下二つのデータタイプで表現できる：

type t =
  | Int of int
  | Cons of int * int

「なんらかの値を表す整数」、「ポインタを表す整数を二つ持つConsセル」の二つだけ。これでプログラムもデータもすべて表現できる。このミニマルさがLispっぽい。

その簡単な二種類のデータがずらっと並んでいる配列がSECDマシンのメモリのすべてだ：

let cells = Array.make 100000 (Int 0)

（ここではとりあえずInt 0で初期化したものを10万用意している）

そしてそのメモリ配列のインデックスをもつ５つのレジスタ；

let s = ref 0;
let e = ref 0;
let c = ref 0;
let d = ref 0;
let f = ref 1;

これらはすべてメモリセルのどこかを指している。SECDマシンの名前ははじめの四つのレジスタから来ている。Fレジスタかわいそう・・・

SレジスタはStack。SECDはスタックマシンで、Sレジスタが指しているリストの先頭からデータをとってプロセスしてまたそのリストの先頭に載せる、という挙動でデータが変更されていく。

EレジスタはEnvironment。変数の値を保持する環境を表すリストを指している。ちなみに環境はrib cage representationな連想リストをde Bruijn index化したもの。

CレジスタはControl。プログラムがSECDマシン命令にコンパイルされたあと、Consリスト化されメモリにロードされる。そのロードされたプログラム上で次実行するべき命令が載っているメモリセルを指すのがCレジスタだ。

DレジスタはDump。条件分岐や関数呼び出しがある場合、スタックや環境、コントロールをいったん別のものに変え、分岐や呼び出しが終了した時点で現在の場所に戻ってきたい。そのための「現在のS、E、Cレジスタの値を一時退避させておくリスト」をDレジスタが指す。

FレジスタはFree Cellから（多分）。未使用のメモリセルの位置を指している。新しいセルを使いたい時にはFレジスタの指す位置を使い、レジスタの数値はインクリメントする。多分一番仕様頻度は高いレジスタなのだがマシンの名前には入れてもらえなかった。Fレジスタかわいそう・・・

ただ、Fレジスタはよく使われるが、コード上で現れることは珍しい。すぐに関数によって隠蔽されてしまうからだ：

let makeInt i =
  let n = !f in
  (cells.(n) <- Int i; f := n + 1; n)

let makeCons i j =
  let n = !f in
  (cells.(n) <- Cons (i, j); f := n + 1; n)

新しい値やコンスセルを作る場合、かならずFree Cellから作るのでそのロジックを隠蔽する。そしてこれ以外でFree Cellを直接参照する必要がない。さらばFレジスタ。

他のレジスタの指すリストの先頭から値を取ったり、逆に値を追加したりする関数：

let popR r = match cells.(!r) with
  | Cons (i, j) -> (r := j; i)
  | _ -> failwith "Register points to a non-cons cell"

let pushR r i =
  r := makeCons i !r

こういったヘルパー関数を使って、コントロールから一つずつ命令をとってきて実行していく（停止命令に遭遇するまで再帰でループ）：

let runOneStep () = match cells.(popR c) with
…

let rec run () =
  if !c = 0 then ()
  else (runOneStep (); run ())

私が実装したこのSECDマシンを走らせるキモとなるのはrunOneStep関数で、Cレジスタの指すリストの先頭のConsセルのCARの指すIntの値を命令として認識して場合分けして実行する：

let runOneStep () = match cells.(popR c) with
  | Int 0 (* STOP *) -> c := 0
  | Int 1 (* NIL *) -> pushR s 0

例えばCレジスタの先頭（おもいっきり略した表現）がInt 0であるならば停止命令STOPとして認識し、Cレジスタを0番地（NILとして扱う）を指すようにする。

Int 1ならNILとして認識し、sスタックの先頭がNILへのポインタになるようにする（スタックをNILにするのではないことに注意）。

SECDにはSTOPやNILのような命令がいくつかある。資料によってその数字がまちまちなのはご愛嬌だ。（そもそもLandinの論文ではPrimitiveが存在することは明言してあってもそのPrimitiveが何かは書いていないので・・・） The Architecture of Symbolic Computersも実はすべてのPrimitiveを提示してくれないので、他をあたる必要がある。

私のSECDの場合は命令セットはSTOP, NIL, LDC, LD, CAR, CDR, ATOM, CONS, EQ, LEQ, ADD, SUB, MUL, DIV, REM, SEL, JOIN, LDF, AP, RTN, DUM, RAPの２２個。

特筆すべきものをいくつかピックアップすると： * LDCで定数を、LDで変数をスタックにロードする * SELとJOINで条件分岐と分岐終了 * LDFで関数をその環境と一緒にスタックにロード、APでその関数を実行 * RAPで再帰関数の実行（DUMでその再帰関数のための「書き換え用の環境」を作って、LDFで再帰関数とその環境をスタックに乗せ、そしてRAPで実行する）

一番実装がややこしいのはRAPで、すでに何かが書き込まれたセル（Fレジスタからとってこなかったセル）に破壊的代入をするのはここだけ。他の命令の実装はすべて純粋関数でも書けるはず（書いている言語のメモリマネジメントにただのりする前提であれば）。

  | Int 21 (* RAP *) ->
      let fe = popR s in
      let func = car fe in
      let nenv = cdr fe in
      let arg = popR s in
      begin
        pushR d !c;
        c := func;
        pushR d (cdr !e);
        e := rplaca nenv arg;
        pushR d !s;
        s := 0;
      end; ()

C、E、Sレジスタの順番にDレジスタに値を移してから変更していく様が伝わると嬉しい。rplaca関数でnenvの先頭にargへのポインタを破壊的代入する。

個々の命令やLispから命令へのコンパイラの説明はまた別の機会に。

ちなみに実装中に使った文献はThe Architecture of Symbolic Computersだったのだが、この本はどちらかというと思想を含めたアイディアと背景を語ってくれる本で、実装のための情報はちょっと薄かった。ある程度想像を働かせてコードに変換していく必要がある。さらにRAP命令の説明に関しては間違いがあって、その部分では半日実装せずに悩んでしまった。（SECDマシンの状態遷移表のRAPの項目で、Eレジスタの内容の結果がrplaca((nil.e),v)になるはずがrplaca((nil.e),v).eになっている。一番ややこしいところで表記ミスがあるのはつらい・・・）

実装のための資料としてはHendersonのFunctional Programming Application and Implementationのほうがすぐれていそうだ。前述の通り、こちらはLispKit Lispという純粋関数型LispをSECDマシンで実装する詳細が載っている。

AoSCにはそれ以外の部分で価値が十分すぎるほどあるが。例えば今回話せなかった最適化やガベージコレクション各種、Call-by-Need化などの話題も載っている。そしてさらにLispとLisp Machineへと話が続いていく。

Lisp Machine

古のLispの話をする場合大抵ノスタルジアとともに語られるトピックが「Lispマシン」だ。有名どころで言えばTexas Instruments社やXerox社、専業だとSymbolics社とLMI社が出していた、ハードウエアレベルでLispをサポートするコンピュータ。今でもインターネットの隅で「そのIDEの『新機能』、80年代にLisp MachineのSymbolics Generaで使ってたよ」的なコメントがつくのを散見することがある。Lispの強力さと先進性のひとつの現れだろう（そしてもしかすると弱点も、かも）

その源流はLisp発祥の地であるマサチューセッツ工科大学の人工知能研で開発されたCONSマシンとその後継機であるCADRマシン（「次に来るもの」の意）にある。ちなみにCONSマシンは開発者Thomas Knightの修士論文の題材だったようだ。楽しい修士論文だな・・・

The Architecture of Symbolic ComputersではこのCADRマシンについてある程度詳しく解説している（といっても実装の雰囲気くらいまでだが）。実は個人的にはこれが最大の目的で読んでいた。

CADRのアーキテクチャはSECDマシンに非常に近いようだ。IntやConsといったデータタグのついたメモリと、そのタグごとひとつのワードとして処理できるだけの容量をもったプロセッサチップ。SECDマシンをハードウエア化するとこのような形になるだろうか、と思わせるところがある。

いくつかの顕著な違いとしては

  • タグの種類が多い。さすがにIntとConsだけというのは現実的には難しく、ハードウェアサポートとともにFloatだとか「文字列へのポインタ」とかのタグが多数用意されていた
  • すべてのデータをメインメモリに持つモデルではなく、スタックやコントロールなどの上位にあるデータを置くキャッシュ的な機構、Push Down Listというものが用意されていた
  • Consだけではなく、連続したメモリ空間にデータを載せることもでき、「あるデータが連続したメモリに載っている」という情報をタグで持たせることでデータアクセスの効率化（上記のSECDマシン実装だといたるところでデータアクセスがLinear timeになってしまう）

といったものがあるようだ。

命令セットについてもmicrocode、macrocodeそしてMacLispでプログラムが書けるようになっており、microcodeやmacrocodeとSECD命令セットの関係はAoSCではあまりはっきりとは書いていない（macrocodeがより一般的なスタックマシンの命令セットに近いものである、という記述はある）。

さらにCADRマシンの開発レポートであるMIT AI Memo 528 - CADRではSECDマシンへの言及がない。実際どの程度この仮想マシンを意識してCONSマシン、CADRマシンが開発されたのかは残念ながら不明なようだ。

AoSCはLisp machineの実装のおおまかな雰囲気を追うには十分だが、もしある日あなたが天啓を受けてLisp machineを現代に蘇らせようと思った時はこれ以外の文献も多分必要になると思う。

最後に

抽象機械SECDは実装も比較的簡単なうえ、純LispやISWIMなどの関数型言語のコンパイル先として楽なので、言語実装で遊んでみたい人にはオススメだと思う。さらにLispや計算機科学の歴史に浸った気分になれるというボーナス付き。

またThe Architecture of Symbolic ComputersにはSECDマシン以外にもCall-by-NeedなGraph ReductionベースのGマシン、論理型プログラミングと推論をサポートするWarrenマシンなど、von Neumannモデルとは一線を画す実行モデルを持った抽象機械がいくつも紹介されている。機会があったら是非（大学図書館などで）手に取ってみてほしい。

参考文献

The Architecture of Symbolic Computers Peter M. Kogge

Functional Programming Application and Implementation Peter Henderson

The Mechanical Evaluation of Expressions - Peter J. Landin

The Next 700 Languages - Peter J. Landin

AI Memo 528 - CADR Thomas F. Knight, Jr., David Moon, Jack Holloway, Guy L. Steele, Jr.

LispKit Lisp - Think Stitch - PRINCIPIA

SECDマシン - Qiita

SECD machine - Wikipedia