Arantium Maestum

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

Concepts, Techniques and Models of Computer Programmingを読みはじめた

過去何回かぱらっとめくったくらいで置いておいたConcepts, Techniques and Models of Computer Programmingという本を去年の終わりあたりに少し真面目に読み始めた。

なぜか時々「ポストSICP」と言われる本で、CSの根幹部分の一つを書き表した大作・名著である。関数型や論理型やオブジェクト指向などのいわゆるプログラミング言語パラダイム、あるいは並行性などの実行モデルなどが、どのような言語機構の組み合わせで可能になり、どのようなより粒度の細かい分類が可能で、どのような特性があり、どのような書き方・問題へのアプローチを可能とするのか、について書かれている。

どこらへんが「ポストSICP」なのかは個人的には謎だが。SICPと扱うテーマの範囲も違うし、プログラミング初心者向けとは到底思えないし、SICPを読み終わった後に必ず読むべき!という順序もあまりぴんとこないし・・・ 別に例えば先にCLRS読んでもいいしPAIP読んでもいいし、CTMCPSICPの次にくるべき理由は思い当たらない・・・

ともあれCTMCPは面白そうな本である。

マルチパラダイム言語Ozとその実行環境Mozartを使って様々なプログラミング概念を提示しているのだが、そのOzというのも

  • 抽象機械によるoperational semanticsが与えられている仕様が小さいOz kernel language
  • Oz kernel languageの上にsyntax sugarを重ねた実用言語

の二層にわかれている。章を追うごとにkernel languageを拡張、あるいはsyntax sugarを追加していくことで新しいパラダイムに対応していく。それによってどのような原子的な言語要素から各言語機構が立ち上がってくるのかを明確にしている。

よっしゃとりあえずまずは実装だ!ということで例によってOCamlでkernel languageを書き始めている。

github.com

今のところ数字と関数定義のところまでできていて、次はレコードの実装。それが済んだら第2章で説明されているもっとも簡単なkernel languageはできあがる。その後はsyntax sugarを載せてみたり、先の章のkernel language extensionを実装したりしてみる。

とりあえずレコードができたら実装内容や言語の特徴についていったん振り返ってまた記事を書きたい。

自作言語Xemono

去年の終わり頃からReason MLよろしくOCamlシンタックスをいじった言語の仕様を考えている。

github.com

今のところ新規性はまったくなく、OCamlと100%互換性がある言語仕様を目指している。(ただし今のところオブジェクト関連の機能についてはまったくノータッチ・・・)semantics的にはOCamlは本当に個人的な理想に近いと感じる。

なので変えているのはガワだけ。

外見的な部分はかなりPythonからとっている。(各方面から嫌がられそうだけど・・・)

その最たる部分は定幅インデントによるブロックわけでスコープが決まって、変数束縛には=、関数定義には:を使う(letはなし)

returnなしでスコープの一番下の式の値がスコープ全体の値になるのはどちらかというとLisp(かRuby)に似ている。関数型言語をブロックで表現しようとすると結構自然とこうなる気がする。

行末の:+インデントによるブロック以外では、主にPEP20の思想に強く影響を受けている。

あとHaskellから$whereをもらってきた。

実装

まだない。OCaml + Menhirでやる。

パースに関しては

と指摘をいただいたように、Context Free Grammarではないのでその依存性をどう解決するかが一つのポイント。

lexerとparserの間にインデントルールの解釈をするコードを挟んで、EOL/INDENT/DEDENTトークンとして挿入していくのが良さそうだと現在は考えている。

ASTにしてしまえばそこから対応するOCamlに変換するのは簡単だと思う。とりあえず当面はOCamlコンパイルすることを目指す。(その次はcmmかな)

近いうちに着手したい。

長期的には「modular implicitsをXemono言語側で実装できたら・・・」という思いがある。その場合は型推論OCaml側に頼れないので、その実装からだが・・・

コード例

仕様をある程度試すために、Real World OCamlのサンプルコードをXemonoでちょこちょこ書いてみた:

github.com

細かいところで気になる点があったり、思わないところで大きな仕様漏れがあったり、となかなか役に立った。OCaml自体の仕様についても少し理解が深まっていくので、それもかなりうれしい。これからも継続してサンプルコードを翻訳してはレポジトリにあげていくつもり。

気になっている点

  • 関数定義と分岐条件の見た目が同じでコンテキスト依存
    • 関数定義にdefキーワードを導入するか悩み中
    • 分岐条件やパターンマッチにcaseキーワードを入れるのは文法が重くなる気がする
  • モジュールの最上層でのlet x = y;let x = y in ...の違いがlet/inを使わない分理解しにくくなっている?
    • これはドキュメントで説明するのが大事なだけかも
  • :だと見た目が弱いので、一行でパターンマッチとその結果を記述する時などに条件と結果の境目が一目で判別しにくい
    • 試行錯誤の結果、:の後にスペースを二つ入れると問題がかなり緩和されることがわかった

名前について

便宜上自分の中で言語Xと呼んでいたのだが、Xerxesをクセルクセスと読むことに気づいて、自然と決まった。

今後

とりあえず仕様はある程度固まってきたのでぼちぼち実装をはじめる。近いうちにModern Compiler Implementation in Xemonoみたいな企画ができるといいな。

100 Days of Codeをやってみた

ツイッターで100 Days Of Codeというチャレンジがたまに流れていて、面白そうだったのでやってみた。今年も終わりに近づいているので今更ながら振り返ってみる。

100 Days Of Code概要

ルールは簡単:

  • なるべく毎日1時間以上、業務外のコードを書く
  • githubに載せる
  • twitterで進捗をつぶやく

途中で風邪をひいて寝込んだりいわゆるライフイベントが発生したりして合計で5日ほど空いてしまったが、8月14日にはじめて11月26日に終わった。

積ん読していた本をある程度消費したい、という欲求もあり、100日間基本的に本に載っているコードや演習問題、オンラインのチュートリアルなどをやって過ごした。自前のプロジェクトを立ち上げたりしなかったのですこし寂しい気もする。近いうちに自作言語に手を出したい。

やったこと(というか読んだ本)

Essentials of Programming Languages 第1章〜第7章

Paradigms of Artificial Intelligence 第1章〜第4章

Structure and Interpretation of Computer Programs 第2章

500 Lines or Less - Python Bytecode Interpreter

Types and Programming Languages OCamlでの実装章

Implementing Programming Languages 第2章

Kaleidoscope LLVM Tutorial

MinCaml compiler

Essentials of Programming Languages

github.com

github.com

この本がここ1年ほど一番読みたいと思っていた本だった。ものすごく簡単な言語からはじめて、Racketでインタプリタをいろいろ実装していくという本。

などといったプログラミング言語の基礎概念の多くを実際に自分の手で作っていくのはすごく面白かったし勉強になった。とりあえずRacketで実装していって、その後OCamlで書き直してみたりしたのもよかった。(とくに代数的データ型の便利さを実感できた点で)

まだ章はいくつか残っているので今後もまた戻ってきたい。

Paradigms of Artificial Intelligence

github.com

こちらはちょっと手をつけた程度。Common Lispに没入するに至らず、不完全燃焼気味。絶対に読みたい本の一つなので2019年に持ち越し。

Structure and Interpretation of Computer Programs

github.com

カマイルカさん(@lagenorhynque)とOpt Technologiesの皆様のご好意で読書会にオンライン参加させてもらっていた。ここ二ヶ月ほど事情があって参加できず悲しい。近いうちにまた是非参加したい。

Schemeで問題を解いていって解けた人からコードをSlackにあげていくというなかなか楽しい会。Lispに興味がある人はガンガン参加するといいと思う。進むペースはすこしゆったりめか。

500 Lines or Less

github.com

The Architecture of Open Source Applicationsというシリーズがある。いろんなオープンソースのプログラムの設計思想などをその開発者が解説するというなかなか素敵なもの。その中の500行以下のプログラムをピックアップした刊が500 Lines or Lessだ。

章のひとつがPythonで実装するPython Bytecode Interpreterの解説で、これを追いながら写経していった。スタックマシンの実装の理解やバイトコードに対する慣れなど、得るものは多かったと思う。正直書かれていたコードはそこまで好きなスタイルではなかったが・・・

Types and Programming Languages

github.com

何回か流し読みしたことはあるのと最初の方はるじゃんどるさん(@Lugendre)の読書会でやったことはあるのだが、正直ちゃんと納得できるレベルで読めたとは言えない状態だった。

以前読んだ時はそもそもプログラミング言語についての前提知識が不十分だったように思う。Essentials of Programming LanguagesやConcepts, Techniques, and Models of Computer Programmingなどといった「プログラミング言語関連のトピックを俯瞰的に提示する本」を読んだ上で挑戦するのがちょうどいいのではないか。

今回もそこまで真面目に読んだ感じではなく、実装について触れている章を写経するのがメインだった。近いうちにまたちゃんと読み込みたい。

Implementing Programming Languages

github.com

C++のサブセット的な言語をJava Bytecodeやマシン語コンパイルする話が主体になる本。パーサに関する演習問題などを(本が推奨するパーサジェネレータではなく)OCamllexとMenhirで実装していった。

Kaleidoscope LLVM Tutorial

github.com

Kaleidoscopeという小さな言語をLLVMコンパイルするチュートリアルC++OCamlのものがあり、当然OCamlを選んだ、のだが。古いチュートリアルLLVMがどんどん発展している技術ということもあり、サンプルコードの多くが動かない。というかOCamlではLLVMJITコンパイラにアクセスするのがすごく大変そう(チュートリアルが書かれた頃に存在したAPIがごっそりDeprecatedになっていた)。

けっこう機能面でも思い切って削った(主に前述のJIT)コンパイラを実装。はじめてOCamlコードのデバッグやライブラリコードを必死に読むという経験をしたので、結果オーライか。

MinCaml compiler

github.com

東北大学の住井先生のMinCamlというOCamlサブセットをSPARC命令セットにコンパイルするOCamlプログラムを写経。

http://esumii.github.io/min-caml/paper.pdf

K正規化、α変換、β簡約などの関数型言語らしいコンパイラ最適化に触れつつそれなりの分量のOCamlコードを理解しながら写経していくというのは大変勉強になった。残念だったのはそもそも私がSPARCの命令セットを全く知らないので、最後の方の工程があまり理解できていない点・・・ 実はMinCamlのさらに限定的なサブセットからはじめて、少しずつ言語機能を追加していく感じでMinCamlコンパイラまで戻っていく、というような過程もやってみたいと思ってはじめたのだが前述の問題で失速してしまった。アセンブリ力が高まったら再度挑戦してみたい。

総括

というわけで、興味の赴くままにいろいろと触っていったらだんだん言語処理系沼にはまり込んでいった感がある。使う言語としては最初はLisp系やPythonだったのだが、後半はほぼOCaml。セマンティクス的にはかなり自分にとってしっくりくる言語だった(でもmodular implicitsはほしい・・・)のでこれからも積極的に使っていきたい。

100 Days of Codeという試みはなかなか面白かった。毎日なるべくちょこっとでも本を読んではPCに向かってコードを書く、さらには書いたコードはなるべくgithubにあげる、という習慣は、無駄に草を生やしているだけのように見えてこれでなかなか蓄積になっている、気がする。なんだかんだいって100日終わった後も継続的に趣味コード書いてはあげてるし。

コードはそれなりの量を書き散らかしたがプロダクト開発ではなく自分の知識獲得のためのものばかりだった。予想どうりだったとは言え今見返すとちょっと極端だったように思う。2019年は趣味でもすこしプロダクト的なものも書いていきたい。どこかのタイミングでまた100 days of codeやるかも。

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の終わりに挙げられている参考文献の9つのうち4つは数学・論理学のもの、2つはDijkstraのもの、そして3つはLisp関係(うち2つは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万用意している)

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

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) withlet 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の22個。

特筆すべきものをいくつかピックアップすると: * 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化などの話題も載っている。そしてさらにLispLisp 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

PythonでForth処理系を書く! その7(繰り返し処理 DO-LOOP)

繰り返し処理を実装する。

PythonでForth処理系を書く! その2(実装する機能) - Arantium Maestumでも書いた通り、この構文の要素は3つあって:

  • DOでスタックに乗っている二つの整数を分岐のために使う

    • スタックから得たはじめの整数がループカウンタの開始値
    • スタックから得た次の整数がループカウンタの終了値
  • LOOPでループカウンタをインクリメントする

    • ループカウンタが終了値未満の場合はDO直後のコマンドまで後方ジャンプ
    • ループカウンタが終了値に達した場合はLOOP以降のコマンドを実行
  • DOとLOOPの間で使われるIは現在のループカウンタの値をスタックに乗せる

こんな使い方をする:

0 11 1 DO I + LOOP . CR

上記のコードは1以上11未満の整数をループ足し合わせて55を出力して改行する。

コード

github.com

IF-ELSE-THENと同じようにcompilerとinterpreterに変更を加える。

compiler.py

コンパイラにDO、LOOP、Iトークンに対応する関数を追加する。

DO:

def run_do(state):
    state['branch'].append(len(state['codes']) + 1)
    state['codes'].append('DO')

codesにはDOだけ載せ、branchスタックにそのあとの位置を載せる。(ループする場合に戻るべきジャンプ先)

LOOP:

def run_loop(state):
    do_pos = state['branch'].pop()
    state['codes'].extend(('LOOP', do_pos))

DOのコンパイルでbranchスタックに載せられた「ジャンプ先」をとり、LOOPコードと一緒にcodesに載せる。

I:

def run_i(state):
    state['codes'].append('I')

Iはそのままcodesに載せるだけ。

このとおり、compilerへの変更は非常に簡単。ループ条件はメインスタック上で管理されるので、処理のロジックはinterpreter側で実装されている。

interpreter.py

まずインタプリタの内部状態に新しくbranchスタックを追加する:

def init_state():
    return {
            'codes': [],
            'pos': 0,
            'stack': [],
            'branch': [], #新しく追加
            'end': False,
            }

IF-ELSE-THENの時にコンパイラには追加したが、今回はインタプリタにも必要。

ループカウンタの現在の値と終了値を保持するために使う。この二つをメインスタックにいれておくと、ループ中にスタックに値を追加するなどの処理と競合してしまう恐れがある。

DOの処理:

def run_do(state):
    a, b = state['stack'].pop(), state['stack'].pop()
    state['branch'].extend((b, a))
    state['pos'] += 1

スタックから二つの数字を取り、片方を開始時のループカウンタ、もう片方をループの終了値としてbranchスタックに入れる。

LOOPの処理:

def run_loop(state):
    a, b = state['branch'].pop(), state['branch'].pop()
    a += 1
    if a < b:
        state['branch'].extend((b, a))
        state['pos'] = state['codes'][state['pos']+1]
    else:
        state['pos'] += 2

branchスタックからループカウンタと終了値をとり、ループカウンタをインクリメントしてから比較。

  • ループカウンタが終了値以上なら終了
  • それ以外なら
    • ループカウンタ・終了値をbranchスタックに戻す
    • コンパイルされているループ元の位置にジャンプ

Iの処理:

def run_i(state):
    state['stack'].append(state['branch'][-1])
    state['pos'] += 1

branchスタックにあるループカウンタをメインスタックにも載せる(branchスタック側の値は載せたままで消費しない)。これでカウンタの値を利用した計算などができる。

使ってみる

まずはDOとLOOPだけで試してみる:

Starting Forth REPL...
> 5 0 DO 1 . LOOP CR
11111
> 0 5 DO 1 . LOOP CR
1

DO-LOOPは必ず一回は処理が走るので、0 5 DO 1 . LOOP CRのようにカウンタの開始値が終了値よりも大きい場合でも1 .の部分が一回実行されているのがわかる。

次にIも使ってみる:

> 5 0 DO I . CR LOOP
0
1
2
3
4
> 0 11 1 DO I + LOOP . CR
55
> 0 10 0 DO I 1 + + LOOP . CR
55

ループカウンタの値がちゃんと計算に使われている。

ちなみに0 10 0 DO I 1 + + LOOP . CRはループカウンタが0からはじまり10未満までループするなか、カウンタの値Iをインクリメントしてからこれまでの合計に足し合わせている。

次回は変数定義。

PythonでForth処理系を書く! その6(条件分岐 IF-ELSE-THEN)

条件分岐を実装する。

PythonでForth処理系を書く! その2(実装する機能) - Arantium Maestumでも言ったとおり、Forthの条件分岐構文は他の言語を知る人には多分だいぶ奇妙に見えるはず。

上記の記事からの再掲になるが、このような構文で:

1 IF 2 ELSE 3 THEN . CR

このような処理になる:

IFコマンドの時点でスタックの上が0以外ならELSEまで実行してからTHENにジャンプ、0ならELSEまでジャンプしてから実行を続ける

THENが「IFが満たされた場合に実行される処理」ではなく、「IF-ELSE分岐が終わって実行パスが合流するポイント」を表しているのがForthの特徴。THENではなくENDIFのほうがいいのではないかという意見も読んだことがあり、一理あると思う。

実装としてはこう:

github.com

ついでにこう(バグの修正):

github.com

変更している箇所はcompilerとinterpreter。ここでようやく中間言語コンパイルすることの利点が活きてくる。

compiler.py

まずはコンパイラの内部状態にあたらしく分岐に関連する情報を維持するスタックを用意:

def init_state():
    return {
            'tokens': [],
            'pos': 0,
            'codes': [],
            'branch': [],  #これを追加
            'end': False
            }

そのbranchスタックを使ってIF、ELSE、THENのトークンをコンパイルする各関数を定義する。

まずIF:

def run_if(state):
    state['branch'].append(len(state['codes']) + 1)
    state['codes'].extend(('IF', None))

出力するcodesにIFとNoneを載せる。

コンパイルが進んで対応するELSE(あるいはELSEがない場合はTHEN)に遭遇したときに、NoneをそのELSE/THENのコードの位置の値に書き換える。あとで書き換えられるようbranchスタックにNoneの位置(len(state['codes']) + 1)を載せておく。

次にELSE:

def run_else(state):
    if_pos = state['branch'].pop()
    state['codes'][if_pos] = len(state['codes']) + 2

    state['branch'].append(len(state['codes']) + 1)
    state['codes'].extend(('ELSE', None))

まずはbranchスタックから対応するIFのNoneの位置を取り出す。そのNoneをELSE以降のコードの位置(len(state['codes']) + 2)に書き換える。

ELSEで追加されるコードはIFと似たようなもの。ELSEとNoneで、NoneはELSEと対応するTHENのコードにジャンプするための位置情報。

最後にTHEN:

def run_then(state):
    else_pos = state['branch'].pop()
    state['codes'][else_pos] = len(state['codes'])

ELSEの前半部分とほぼ同一。branchスタックに載っているのが対応するELSEのNoneの位置(あるいはELSE部分がなくIF-THENだった場合はIFのNoneの位置)。

THENの場合はそこに到達した時点で分岐は終了しており、ジャンプする必要がないのでcodesにはなにも追加されない。

最後に定義した関数をprimitivesとして追加:

primitives = {
        '+': run_plus,
        '.': run_print,
        'CR': run_cr,
        'IF': run_if,
        'ELSE': run_else,
        'THEN': run_then,
        }

IF/ELSE/THENトークンに遭遇したらrun_if/run_else/run_then関数が呼び出されるようになる。

実はここでバグをいれて放置してしまった。「THENがコード追加しない」ということから何故か「primitivesに追加しなくてもオッケー」と思い込んでいて、最初のbranch mergeでは'THEN': run_thenの部分が抜けていた。不覚・・・

このコンパイラ

1 IF 2 ELSE 3 THEN . CR

このコードをコンパイルすると

['PUSH', 1, 'IF', 8, 'PUSH', 2, 'ELSE', 10, 'PUSH', 3, '.', 'CR', 'END']

こんな感じの中間言語に変換される。あるいはコード位置も追加でつけるなら:

 0 PUSH
 1 1
 2 IF
 3 8
 4 PUSH
 5 2
 6 ELSE
 7 10
 8 PUSH
 9 3
10 .
11 CR
12 END

PUSHの後の数字はスタックに載せるための数字、IFやELSEの後の数字はジャンプ先の位置だ。

ちなみにTHENトークンの情報はELSEのジャンプ先の数字になるので、THENというコード自体はコンパイル結果には現れないことがわかる。

次にこれをインタプリタが実行できるようにする。

interpreter.py

IFとELSEのコードを処理できるようにinterpreterに関数を追加する。

まずはIF:

def run_if(state):
    a = state['stack'].pop()
    if a == 0:
        state['pos'] = state['codes'][state['pos']+1]
    else:
        state['pos'] += 2

スタックの一番上をとり、その数が0であればジャンプ、そうでなければそのまま次のコードを処理していく。

IFのすぐあとはジャンプ先の位置情報なので、もしジャンプしない場合はそのコードも飛ばす必要があるのでstate['pos'] += 2になる。

ELSEの処理:

def run_else(state):
    state['pos'] = state['codes'][state['pos']+1]

IFの条件が0だった場合はELSEの先にジャンプするので、ELSEコードに到達したということはすでにIFからELSEの間のコードが走ったということ。なので、ELSEからTHENまでのトークンがコンパイルされた「ELSEブロック」を飛ばしてその先にジャンプする。

使ってみる

前回実装したREPLでいろいろといじっていみる:

Starting Forth REPL...
> 1 IF 2 ELSE 3 THEN . CR
2
> 0 IF 2 ELSE 3 THEN . CR
3
> 1 1 IF 2 THEN . CR
2
> 1 0 IF 2 THEN . CR
1
> 1 -1 + IF 0 ELSE 2 THEN . CR
2

ELSEが存在する場合、存在しない場合どちらでもうまく作動している。

IF-ELSE-THENのネスト:

> 0 1 IF IF 2 ELSE 3 THEN ELSE 4 THEN . CR
3
> 1 1 IF IF 2 ELSE 3 THEN ELSE 4 THEN . CR
2
> 0 0 IF IF 2 ELSE 3 THEN ELSE 4 THEN . CR
4

ややこしいが正しい挙動になっている。

IF-ELSE-THENの順序が間違っていたりするとエラー:

> 1 IF 5 THEN 3 ELSE 2 . CR
Traceback (most recent call last):
  File "main.py", line 36, in <module>
    run_repl()
....
    if_pos = state['branch'].pop()
IndexError: pop from empty list

異常系でどんな挙動になるかはまったく保証できない。今回はコンパイルエラー(ELSEが書き換えるべきIFのジャンプ先がbranchスタックに乗っていなかった)。今のところエラーハンドリングは改善の予定はない。めんどくさそう。

次回はDO-LOOP構文を追加して「繰り返し」処理を可能にする。

PythonでForth処理系を書く! その5(Read-Eval-Print-Loop)

REPL機能を実装する。

main.pyに引数がなければREPLを実行するようにする(引数としてファイル名が渡されていればそのファイルを実行)。REPLは一行ずつユーザからForthコードを受け取り、今まで受け取ったコードの環境を引き継ぎつつ実行する。

github.com

変更はcompiler、interpreter、そしてmainの三箇所。

compiler.py

compile関数が複数回呼ばれることを前提に以下の変更を加える:

  • 中間言語に変換するtokensを初期化せずに追加するようにする
  • 中間言語のcodesから'end'コードを取り除く
  • 'end'フラグをFalseにセットする
def compile(state, tokens):
    state['tokens'].extend(tokens)
    if state['codes']:
        state['codes'].pop()
    state['end'] = False

    while not state['end']:
        run(state)
    return state['codes']

どのトークンまで変換したかを表す'pos'値は以前の最後のトークンの一つ先を指しているので、ちょうど新たに追加したトークンの先頭を指すことになる。

なのでこれでcompile関数が走れば追加分のトークンだけ中間言語に変換してくれる。

interpreter.py

変更はinterpret関数のstate['end']をFalseにセットするだけ。

def interpret(state, codes):
    state['codes'] = codes
    state['end'] = False #ここだけ変更

    while not state['end']:
        run(state)

main.py

  • 今までのmain部分をrun_fileという関数に
  • run_repl関数を別途定義
  • main部分ではスクリプトが呼ばれたときにargvに引数が渡されたかどうかでrun_fileかrun_replにディスパッチ

今回追加したrun_repl関数はこんな感じ:

def run_repl():
    compiler_state = compiler.init_state()
    interpreter_state = interpreter.init_state()

    print("Starting Forth REPL...")

    while True:
        s = input('> ')
        if s == 'QUIT': break

        tokens = tokenizer.tokenize(s)
        codes = compiler.compile(compiler_state, tokens)
        interpreter.interpret(interpreter_state, codes)

まずは内部状態を初期化して、ループ内で新しくユーザから受け取った文字列をトークン化し、内部状態と一緒に引数としてcompile/interpretに渡して処理している。

実行

これで単にpython main.pyと呼び出せば:

Starting Forth REPL...
> 3 4 +
> 5 6 +
> + . CR
18

というような感じで対話的にForthを書ける。行の間で環境(とくにスタックの状態)が引き継がれているのがわかる。

これで機能を追加したときにチェック・デバッグしやすくなった。

次回はI分岐構文のIF-THEN-ELSEを追加する。