自作言語Xemono
去年の終わり頃からReason MLよろしくOCamlのシンタックスをいじった言語の仕様を考えている。
今のところ新規性はまったくなく、OCamlと100%互換性がある言語仕様を目指している。（ただし今のところオブジェクト関連の機能についてはまったくノータッチ・・・）semantics的にはOCamlは本当に個人的な理想に近いと感じる。
なので変えているのはガワだけ。
外見的な部分はかなりPythonからとっている。（各方面から嫌がられそうだけど・・・）
その最たる部分は定幅インデントによるブロックわけでスコープが決まって、変数束縛には=、関数定義には:を使う（letはなし）
returnなしでスコープの一番下の式の値がスコープ全体の値になるのはどちらかというとLisp（かRuby）に似ている。関数型言語をブロックで表現しようとすると結構自然とこうなる気がする。
行末の:＋インデントによるブロック以外では、主にPEP20の思想に強く影響を受けている。
あとHaskellから$とwhereをもらってきた。
実装
まだない。OCaml + Menhirでやる。
パースに関しては
そもそも文脈自由言語じゃないから書けなくないですか
— research-by-need (@fetburner) 2018年12月18日
と指摘をいただいたように、Context Free Grammarではないのでその依存性をどう解決するかが一つのポイント。
lexerとparserの間にインデントルールの解釈をするコードを挟んで、EOL/INDENT/DEDENTをトークンとして挿入していくのが良さそうだと現在は考えている。
ASTにしてしまえばそこから対応するOCamlに変換するのは簡単だと思う。とりあえず当面はOCamlにコンパイルすることを目指す。（その次はcmmかな）
近いうちに着手したい。
長期的には「modular implicitsをXemono言語側で実装できたら・・・」という思いがある。その場合は型推論もOCaml側に頼れないので、その実装からだが・・・
コード例
仕様をある程度試すために、Real World OCamlのサンプルコードをXemonoでちょこちょこ書いてみた：
細かいところで気になる点があったり、思わないところで大きな仕様漏れがあったり、となかなか役に立った。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概要
ルールは簡単：
途中で風邪をひいて寝込んだりいわゆるライフイベントが発生したりして合計で５日ほど空いてしまったが、８月１４日にはじめて１１月２６日に終わった。
積ん読していた本をある程度消費したい、という欲求もあり、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
この本がここ1年ほど一番読みたいと思っていた本だった。ものすごく簡単な言語からはじめて、Racketでインタプリタをいろいろ実装していくという本。
などといったプログラミング言語の基礎概念の多くを実際に自分の手で作っていくのはすごく面白かったし勉強になった。とりあえずRacketで実装していって、その後OCamlで書き直してみたりしたのもよかった。（とくに代数的データ型の便利さを実感できた点で）
まだ章はいくつか残っているので今後もまた戻ってきたい。
Paradigms of Artificial Intelligence
こちらはちょっと手をつけた程度。Common Lispに没入するに至らず、不完全燃焼気味。絶対に読みたい本の一つなので2019年に持ち越し。
Structure and Interpretation of Computer Programs
カマイルカさん（@lagenorhynque）とOpt Technologiesの皆様のご好意で読書会にオンライン参加させてもらっていた。ここ二ヶ月ほど事情があって参加できず悲しい。近いうちにまた是非参加したい。
Schemeで問題を解いていって解けた人からコードをSlackにあげていくというなかなか楽しい会。Lispに興味がある人はガンガン参加するといいと思う。進むペースはすこしゆったりめか。
500 Lines or Less
The Architecture of Open Source Applicationsというシリーズがある。いろんなオープンソースのプログラムの設計思想などをその開発者が解説するというなかなか素敵なもの。その中の500行以下のプログラムをピックアップした刊が500 Lines or Lessだ。
章のひとつがPythonで実装するPython Bytecode Interpreterの解説で、これを追いながら写経していった。スタックマシンの実装の理解やバイトコードに対する慣れなど、得るものは多かったと思う。正直書かれていたコードはそこまで好きなスタイルではなかったが・・・
Types and Programming Languages
何回か流し読みしたことはあるのと最初の方はるじゃんどるさん（@Lugendre）の読書会でやったことはあるのだが、正直ちゃんと納得できるレベルで読めたとは言えない状態だった。
以前読んだ時はそもそもプログラミング言語についての前提知識が不十分だったように思う。Essentials of Programming LanguagesやConcepts, Techniques, and Models of Computer Programmingなどといった「プログラミング言語関連のトピックを俯瞰的に提示する本」を読んだ上で挑戦するのがちょうどいいのではないか。
今回もそこまで真面目に読んだ感じではなく、実装について触れている章を写経するのがメインだった。近いうちにまたちゃんと読み込みたい。
Implementing Programming Languages
C++のサブセット的な言語をJava Bytecodeやマシン語にコンパイルする話が主体になる本。パーサに関する演習問題などを（本が推奨するパーサジェネレータではなく）OCamllexとMenhirで実装していった。
Kaleidoscope LLVM Tutorial
Kaleidoscopeという小さな言語をLLVMにコンパイルするチュートリアル。C++とOCamlのものがあり、当然OCamlを選んだ、のだが。古いチュートリアルでLLVMがどんどん発展している技術ということもあり、サンプルコードの多くが動かない。というかOCamlではLLVMのJITコンパイラにアクセスするのがすごく大変そう（チュートリアルが書かれた頃に存在したAPIがごっそりDeprecatedになっていた）。
けっこう機能面でも思い切って削った（主に前述のJIT)コンパイラを実装。はじめてOCamlコードのデバッグやライブラリコードを必死に読むという経験をしたので、結果オーライか。
MinCaml compiler
東北大学の住井先生の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の終わりに挙げられている参考文献の９つのうち４つは数学・論理学のもの、２つは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マシン命令へのコンパイラ」を実装してみた。
ただし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.
PythonでForth処理系を書く！ その７（繰り返し処理 DO-LOOP）
繰り返し処理を実装する。
PythonでForth処理系を書く！ その２（実装する機能） - Arantium Maestumでも書いた通り、この構文の要素は３つあって：
DOでスタックに乗っている二つの整数を分岐のために使う
- スタックから得たはじめの整数がループカウンタの開始値
- スタックから得た次の整数がループカウンタの終了値
LOOPでループカウンタをインクリメントする
- ループカウンタが終了値未満の場合はDO直後のコマンドまで後方ジャンプ
- ループカウンタが終了値に達した場合はLOOP以降のコマンドを実行
DOとLOOPの間で使われるIは現在のループカウンタの値をスタックに乗せる
こんな使い方をする：
0 11 1 DO I + LOOP . CR
上記のコードは1以上11未満の整数をループ足し合わせて55を出力して改行する。
コード
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処理系を書く！ その６（条件分岐 IF-ELSE-THEN）
条件分岐を実装する。
PythonでForth処理系を書く！ その２（実装する機能） - Arantium Maestumでも言ったとおり、Forthの条件分岐構文は他の言語を知る人には多分だいぶ奇妙に見えるはず。
上記の記事からの再掲になるが、このような構文で：
1 IF 2 ELSE 3 THEN . CR
このような処理になる：
IFコマンドの時点でスタックの上が0以外ならELSEまで実行してからTHENにジャンプ、0ならELSEまでジャンプしてから実行を続ける
THENが「IFが満たされた場合に実行される処理」ではなく、「IF-ELSE分岐が終わって実行パスが合流するポイント」を表しているのがForthの特徴。THENではなくENDIFのほうがいいのではないかという意見も読んだことがあり、一理あると思う。
実装としてはこう：
ついでにこう（バグの修正）：
変更している箇所は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処理系を書く！ その５（Read-Eval-Print-Loop）
REPL機能を実装する。
main.pyに引数がなければREPLを実行するようにする（引数としてファイル名が渡されていればそのファイルを実行）。REPLは一行ずつユーザからForthコードを受け取り、今まで受け取ったコードの環境を引き継ぎつつ実行する。
変更はcompiler、interpreter、そしてmainの三箇所。
compiler.py
compile関数が複数回呼ばれることを前提に以下の変更を加える：
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を追加する。
PythonでForth処理系を書く！ その４（内部状態をPython Dictionaryに保存）
前回の終わりで書いたように、Forth処理系の内部状態、とくにコンパイラ部分とインタプリタ部分のものをデータ構造として抜き出して、保存・出力できるようにしたい。
その変更がこれ：
主要な変更は二点：
- 内部状態をPythonのDictionaryで表し、compileやinterpretにそのState dictionaryを渡している
- コンパイラ・インタプリタのどちらにも存在したif-elif-elseの分岐処理を、個別にState dictionaryを受け取ってひとつの処理を行う複数の小さい関数に分割する
state dictionaryの導入
とくにREPLを実装するのに役にたつと考えての変更。
一つのプログラムを最初から最後まで一気に読み込んで処理を行う場合は、こういう状態が関数内で完結していて問題ないのだが、ユーザから一行ずつプログラムを与えられて、その都度「トークン化・コンパイル・実行」するとなると、過去の状態も含めて保持する必要がある。
その方法としては
あたりが考えられると思う。
一番素直なのはオブジェクト化してしまって状態をそのままメンバ変数にいれてしまうことだろう。あるいはPythonだとyieldキーワードを使ったgeneratorで関数に状態を手軽に持たせることもできる。ただ、デバッグなどの関係もあって、できれば状態を簡単なデータ構造に入れて外部からアクセスできるようにしたかった。（もちろんオブジェクトでもメソッドを定義するなどして実現できるが少し手間だ・・・）
グローバル変数は宗教上の理由でアウト。イミュータブルなStateを引数・戻り値にするのは好みにかなっているのだが、Pythonのデータ構造はそもそもmutationを前提としていてイミュータブルに使うにはコピーコストが大きい。
というわけでcompileやinterpretに引数としてStateを与えて、それに対して破壊的変更を加えていく形のコードになった。
if-elif-elseの分割
Stateをデータ構造につめこんだので、一つの関数内で処理が完結する必要はなくなった。
- 分岐で行っていた各処理を個別の関数にわけて
- 現在位置にあるトークン・コードによってディスパッチ
- Stateも引数として与えて変更がかかる
という流れにする。このような実装にすることで今後機能を追加していくときに「一つのでかい条件分岐にelifを追加してどんどん長くしていく」という地獄を避けられるはず。
次回は今回の変更を踏まえてインタプリタにREPL機能をつける。
