今ちょうどプログラミング言語作ってみたかったんだよね〜、と言うときに見る資料

上からレスを見てメモしてくだけ。

Ask HN: Resources for building a programming language? | Hacker News

ちなみに私はbrainf*ckとlispもどきしか作ったことしかないミジンコです。

スレを読む限り、ドラゴン本なんて読んでられないよ、という気持ちがあるのだと思う。

Racketで作るプログラミング言語

Beautiful Racket by Matthew Butterick

Beautiful Racketプログラミング言語を作るチュートリアル集である。Racketは、Lisp方言のScheme実装の一つであり、関数型プログラミングしやすい的なアレである。Lispと聞くとやや身構えてしまうのだが、このRacketという言語けっこう面白いですよ。Pythonと同じ標語 “Batteries Included” が謳われており、プログラミングをするなら欲しいと思われるライブラリ一式(GUI, ネットワーク, ウェブサーバー, 数学, etc…)が、インタプリタをダウンロードすると漏れなく付いてくる。またDrRacketというIDEがこれまた面白くて、対話的にお絵かきプログラミングをすることができる(動きはないが、方向性がProcessingに似通っている)。言語自体も開発期間が長く、おもちゃではないようだ。

Beautiful Racketに話を戻すと、まず簡単なスタックベース計算機の実装から始め、brainf*ck, JSONコンパイルされるDSL, 論理ゲートを表現するDSLの実装を経て, 最後にBASIC風の言語を作る。言語実装としてはかなり初歩的だが、課題に独自性があり興味を持って取り組みやすそうな印象をもった。

F*dging up a Racket

これもBrainf*ckインタプリタの実装チュートリアルだが、最適化の手法にも触れられているようだ。

Essentials of Programming Languages: 3rd edition

これは書籍である。頭字語を取ってEoPL。(値段が)高い。継続渡しスタイルによる実装や、型推論などconciseだがかなり実践的な話題を扱っている。ちなみにスレでは第3版より1版のほうが内容が「授業向けでなく」深くておもしろい、と言う意見が述べられていた。

Amazon.co.jp: Essentials of Programming Languages: Daniel P. Friedman, Mitchell Wand, Christopher T. Haynes: 洋書

Racketのドキュメントに、この書籍で扱われている言語に関するガイドがある。

Essentials of Programming Languages Language

Crafting Interpreters

これは現在オンライン上で執筆中の本である。筆者はGoogleに所属しており、様々な言語を自作したり(wren, magpie, finch, vigil, jasic, lark)、携わった経験(http://dartlang.org/)があるとのこと。

これには詳しいレビューが寄せられている。要約すると、

  1. 面倒な話題を避けている。構文解析の理論的側面、正規表現をテーブル駆動DFAに変換する方法、LR(1)パーサーを構築する方法など、興味深いが言語を作って見たい人には煩雑な話題を省いている。
  2. 深い議論を避けている(「深さ優先」ではなく「幅優先」)。教科書的に、実装前に長々とした口上を述べることを避け、可能な限り早い段階で実行可能なプログラムを書き始めている。最初の実装をし、それに継ぎ足していく形で議論を進めていく。この本では2種類のインタプリタを作っている。単にASTを走査するもの(実装が簡単)と、バイトコードVMを持つものである。
  3. まずJavaで書き、次にCで書いている。Javaは便利なライブラリを使えるが、二度目に実装するときはこれに頼らず作るので実力がつく。
  4. 完全な実装がある。よくあるコンパイラの教科書のように疑似コードを使わず、汚い実装の細部までを読者が発見できるよう案内している。

リソースというより私は言語を作るときこう考えるよ派

コメントより

  1. まず言語のプロトタイプから始める。型システムやその実行時の性質を考える。
  2. バックエンドを選択する。個人的にはzetavmllvm推している。zetavmは動的型付けあるいはJITコンパイル言語向けのVMで、LLVMは多くの低レベル言語(C, C++, Rust)がターゲットとしている。
  3. フロントエンドを作る。これはソースコードの字句解析・構文解析、必要とあらば型チェックや中間表現の生成を含む。個人的にはパーサージェネレーターよりパーサーコンビネーターを使って手書きの再帰的降下パーサーを書くのが好みである(https://github.com/Geal/nom)。型チェックのような追加的な処理を加えるために、一般的な一枚岩的なアプローチと、nanopass的なアプローチがある。Alex Aiken教授による次の動画シリーズも参考になる。

著者降臨派

コメント

Have a look at http://t3x.org

There are lots of small, comprehensible compilers and interpreters there, and there is an interpreter and runtime construction kit, look for “S9 core” in http://t3x.org/s9fes/. You can also order books explaining all the stuff. And yes, I’m the author! :)

http://t3x.orgをご覧ください。

ここにはたくさんの小さな、理解しやすいコンパイラインタプリタがあり、インタプリタとランタイムを構築するための一式が揃っています。http://t3x.org/s9fes/で"S9 core"を探して読んでみてください。またこれを解説した本を注文することもできます。ええそうです。私は著者です :)

OMeta (or Ohm) で覚えよう派

OMetaはPEGに基づくメタ言語である。PEGに対してオブジェクト指向的な何かが入っているらしいが、よくわからない。これが発展してOhmというパーサージェネレーターになっている。PEG風の文法で構文を定義するとすぐ言語がつくれる。ohm editorを眺めただけだが、面白い。

Create Your Own Programming Language

ググれば日本語のレビュー出てくるので略。販促サイトの印象が強烈で“Buy Now”とうるさい本。Rubyの作者が“The book I want to read.”という推薦文を出しているのも味わい深い。(販促の印象しかないので販促の話しかしない人)。

Writing An Interpreter In Go | Thorsten Ball

Monkey言語という独自言語を作る本。C言語風の文法で、変数束縛、前置および中置演算子、関数がfirst-classかつ高階で、クロージャーを持つ。ビルトインのデータ型として整数型、ブール型、配列とハッシュを実装する。

はぐれHaskell純情派

Write Yourself a Scheme in 48 Hours - Wikibooks, open books for an open world

48時間でSchemeを書こう - Wikibooks

self-containedなテキストであるので他の知識を要求しない(ただしHaskellの知識は必要)。

所感

以下レスはまだまだ続いているがここまで。まだ執筆中だが、個人的にはcrafting interpretersを読みたい。というか今やってるkiloの読解が終わったら読む。しかしこの記事面白いだの興味深いだの言い過ぎだな、資料漁りって生産性がなくて楽しいんすよ(小並感)