C言語の勉強: 簡易PostScriptインタプリタ編 - 技術の記録

c-lesson第一回を完走しました

本日、karino2さんが公開しているkarino2の暇つぶしプログラム教室 C言語編の第一回「簡易PostScriptインタプリタを作ろう」を完走しました。

こちらのサイトは「C言語の入門書くらいは読んだがその先が良くわからん」という人に向けて、C言語でのプログラミングを各回でソフトウェアを作りながら解説していくというサイトです。第一回ではPostScript処理系を、第二回ではアセンブラとディスアセンブラを、第三回ではリンカについて学び、第一回のインタプリタにJITをつくります。C言語におけるプログラミングの勉強のみならず、なんと低レベルプログラミングも学べてしまうというとてもお得な内容となっています。後半になって実行可能配列 (無名関数的な？) を実装するところや、継続を実装してVMの中で操作するところなど、クライマックスに向かっていくにしたがって胸にこみあげるものがあり、日々の憂鬱が吹き飛んでしまうくらいには最高でした。

この資料の勉強の進めかたは基本的に、gitter.imにあるc-lessonのリポジトリのチャネルで節ごとあるいは困ったときにコードを見てもらったり質問したりして、アドバイスを受けつつ進めていくことが推奨されています。じつは2019年ごろに一度一人でやってたんですが、当時は言語処理系実装したさで気が逸りすぎてインタプリタの途中のところで別のおもちゃ言語 (それは結局頓挫した) をつくりはじめてしまい止まっていました。今回はしっかり取り組むぞということで、gitter.imでコードを見せつつやってみました。C言語の作法から、コードの書き方、テストの書き方、その他さまざまなアドバイスをいただきまして、各回のテーマとは別に、C言語の勉強に留まらない学びを得られました。

今回は、第一回を完走したということで、やってみたとき反省や感想を書いてみようと思います。

挑戦者t-sinの技術レベル

プログラミング教材をやった感想ということで、挑戦者のレベルを付記しておくのはだいじかなと思ったのでぼくのバックグラウンドを書いておきます。

ぼくは言語処理系実装や低レベルプログラミングに興味があるプログラマです。大学は学部も院 (修士) も情報系で、院のころあたりからCommon Lispがだいすきです。ただLisperとして強いというわけでもなく、いちCommon Lispユーザとして書きつつ、おもちゃ言語 (これとかこれ) をぽこぽこ生やして研鑽しようとしている人です。言語処理系実装については、なんとなくおもちゃインタプリタはつくれるけれど、深い機能 (例外とか？) を実装したことはないというくらいです。

つまり言語設計者ワナビです。

C言語については大学で入門書程度のことはやったけれど、ちゃんと大きなものを書いたことはない程度です。具体的にはstaticは「なんか静的に変数を確保するのねー？」くらいの認識しかない感じです。

c-lessonを始めたモチベーション

さて、そんなぼくがなぜc-lessonをやろうと思ったかというと、2019年くらいの一回目の挑戦のときはちょうどForthとPostScriptにハマりだしたころにkarino2さんのツイートで存在を知り、言語処理系実装おもしろそうと思ってやった気がします。記憶があまり定かではないのですが。

なぜ二年が経過して、二回目の挑戦をしようと思ったか。

ずっと言語処理系について挑戦をしていたわけですが、~やる気~ ~~気合い~~ 何かが不足していて本格的な処理系にならないなあと行き詰まりのようなものが漂っているのは感じてました。そんなときこんなツイート

そういえばインタプリタを継続渡しスタイルで書いた結果、評価プロセスを途中で止めるのが簡単になった話、どこでみたんだっけか……。テストのしやすさにも繋がりそうだなと。

-- https://twitter.com/sin_clav/status/1372356469803208704

に対してkarino2さんから以下のような返信をもらい

継続渡しが本質かどうかじゃなく、ホスト言語のコールスタックを使わずに自前のスタックを使って継続をする、というのが本質じゃないですかね。以下の12節からの話かと。 https://karino2.github.io/c-lesson/forth_modoki.html

-- https://twitter.com/karino2012/status/1372382408113233921

やりなおすかと決意したという経緯があります。

というわけでここまでを整理すると、以下のようなモチベーションで始めました:

低レベルプログラミングについて知りたい
C言語をちゃんと知りたい
言語処理系の実装について知りたい
- 特に継続とその実装について知りたい

第一回での学び

やってみて、またコードを見てもらったときのアドバイスの中で、さまざまな学びがありました。第一回のテーマに関するものから普遍的なものまで、ほんとにたくさんあり忘れたくないのでここに記しておきます。

C言語の基本的な書き方

まずはC言語の基本的な部分について。

C言語のそこそこ大きなプログラムを書くとソースコードとヘッダファイルとに分けて書く必要に迫られますが、まずはヘッダファイルになにを書くべき・書かないべきなのかというところが学びでした。ヘッダファイルはそのソースコードを利用する側の人間が読むものなので、そこに書かれていることから「どう利用されることを想定しているか」を読み取れます。APIのプロトタイプ宣言から「そのオブジェクトはいくつインスタンスを持てるか」がわかったり、#defineマクロの値の再定義など許すかどうかなどです。

変数や関数のstatic有無による違いも今回の学びです。調べたらでてくることですが、staticをファイルのトップレベルの名前につけると、その名前はそのファイル内からしか触れなくなるのでいわゆるprivateな名前になるわけです。ぼくは関数内のローカル変数にstaticをつけると静的に確保されることしか知らなかったので、具体例でいうとユニットテスト関数の名前がファイル間で被ったときにリネームしましたが、staticをつければその必要はないのでした。

C言語のデバッグ技法

デバッグは、gdbについてはこれまでもたまに使っていたので再度復習すればよい程度でした。どちらかというとASAN (AddressSanitizer) の存在を知れたのは大きかった。ASANはコンパイラのオプションで有効にすると、メモリの不正なアクセスを検出してくれるコードを埋め込んでくれ、へんなアクセスをした瞬間に怒ってくれるというものです。辞書のmallocのサイズが間違っていたバグ (sizeof(strlen(key) + 1)とかしてた) をデバッグしていたとき、ぼくは「不正なメモリアクセスをするとプログラムは即座にSIGSEGVする」と思い込んでいたため、プログラムがわりと後のほうまで壊れずに動くという想定がありませんでした。「誤ったプログラムは誤ってるがゆえに動くことも想定するべき」なんですが、まだまだ未熟ですね。この話のなかでASANのことを知るのですが、便利ですね。後半ではとってもお世話になりました。

ただgccだとASAN有効にするとLeakSanitizerも有効になるため、mallocしっぱなしにしてる部分がずらっと指摘されてごめんよぉ！と言ってました。でも慣れたのでもうだいじょうぶ。

本格的な言語処理系のつくりかた

第一回のメインテーマですね。

バイトコードインタプリタはつくったことがなかったので、独立にやろうとしたら試行錯誤と失敗と挫折を何回かくりかえすことになっただろうなと思うのですが、ていねいに解説されているので導かれながら体感できてよかったです。なにより第一回のPostScript処理系は、Forthのテキストインタプリタと似たような構造になっているので「Forthでもこういうふうにやるんだろうな」と前に転んだ処理系のことを思い返したりなんかします。

c-lessonを再開するきっかけでもある継続はオプショナルの節ですが一気にやってしまいました。継続、概念としては理解が訪れつつあるけれど実装できない程度にはふんわりしている感じだったのですが、いまなら「完全理解に理解した！！！」と言う権利を得たでしょう。この継続をデータとして扱えるようにする (スタックに積んだり操作したりする) とcall/cc的なことができるでしょうし、陽に扱えなくても適当な構文やオペレータを追加すればJavaの例外のような非局所脱出が実現できるでしょう。また、これはなんとなく前から理解しつつあったのですが、ホスト言語のコールスタックに依存していないのでプログラムの実行を止めることができるので、並行処理の実現 (一定期間実行したら継続をとって実行を止め、別の継続を再開させ、を繰り返す) や、その応用としてFFI (Foreign Function Interface、外部からゲスト言語の処理を呼ぶときなど、並行処理のように処理を止めてコンテキストを切り替える必要がある) の実現ができるでしょう。継続を実現することで本格的な言語にあるさまざまな機能の実現が視野に入ってきます。これで言語設計者への道が拓けたというわけなのです！

C言語らしさについて

ここからはテーマ外ながらとても大事な学びたちについて、まずはC言語らしさから。

辞書を実装するあたり時点のぼくのコードはkarino2さんによればJavaっぽいというかオブジェクト指向っぽいコードだったそうです。辞書もスタックも、インスタンスが必要になったらmallocするという感じで、まるでクラスをnewするかのようだったからでしょう。C言語においては、メモリはわりと早めにまとめて確保しておいたり、あるいはグローバル変数などで静的にまとめて確保しておくものだということなのでした。Cを覚えたい理由の1つは (いろんな言語を見るのがすきなので) Cの雰囲気を知りたいというのがあり、この指摘はとても重要でした。以降Cで何かするときはこの点を意識して書いていきたいところです。

また、実体コピーという概念を知りました。これはまだ完全に理解したわけではないんですが、オブジェクトをコピーするとき内容をコピーしたオブジェクトを新しくつくって返す、ではなく、既存のオブジェクト間でフィールドの値を陽にコピーすることのようです。……なんか違う気もしますが。ポインタ渡し (参照渡し) との対比かしら……。まだまだ無知ですね。こんど訊いてみることにします。

よいプログラムの書き方

これについてはたくさん教えていただきました。

まず、最初から過度な抽象化をしてはいけないこと、いわゆるYAGNIです。継続スタックの実装前くらいに「スタックを継続でも利用するのでジェネリクス的なものを扱えるスタックに改修すべきですかねー」と言ったところ「そこまで過度な抽象化は必要ないと思う」と言われてはっとしました。プログラムの要素を適切に分割しておくと可読性があがりデバッグがしやすくなるので、結果速く開発できるというのも第一回の中で体感しました。

よいプログラムとデバッグの関係も改めて実感しました。ASANの話のところでデバッグに苦労した旨書いたと思いますが、デバッグをしやすい・原因調査がしやすいようにプログラムを書くのも大事です。適切な分割もそうですし、壊れているときassertで早めに落とすのも原因切り分けに役立ちます。

また、そもそもプログラムを書くときにバグをつくり込みにくいようにする、という視点を教えてもらいました。第一回の中だと、スタックからpopした要素の順番を勘違いしていたせいで盛大に壊れて苦労したところがあったのですが、こういう場合、コメントにそこで想定されるスタックの中身を書いておき、その上でassertしておくとよかったのかなと考えています。ほかにもやれることは (まだ思い付いてないけど) あると思うので、今後もずっと考えていきたいところです。

わかりやすいテストの書き方

ユニットテストがしっかり書かれていると、改造していくなかで壊れたポイントがすぐわかるのでバグの調査がすごく楽になります。なので、バグったときに失敗したユニットテストがなにをテストしているのか、パッと見でわかりやすくなっている必要があるわけです。書いたのは自分ですが、実装が進んでいくにつれテストコードの記憶は薄れていくので実質別人のコードとなるので、ユニットテストの関数名と、そのテストの入力と期待する出力が何であるかすぐわかることはとても重要です。

以下はインタプリタの実際のテストコードです。

// https://github.com/t-sin/c-lesson/blob/14_local_variables_and_loops/sources/forth_modoki/interpreter/eval.c#L1472
static void test_eval_exec_array_jmp_forward() {
    char *input = "{10 2 jmp 20 30} exec";
    int expected_stack[] = {10, 30};

    eval_with_init(input);

    int expected_length = sizeof(expected_stack) / sizeof(expected_stack[0]);
    assert_stack_integer_contents(expected_stack, expected_length);
}

このコードを書いたときの記憶がなくても、とりあえず関数名を読むと

何に対してテストしているか
ざっくりどのようなテストをしているか

がわかります。先頭にはinputとexpected_stackと、あきらかにテストでの入力と期待される出力が書かれています。脳が空っぽになっていても下の細部は無視してとりあえず先頭だけ読めばなにをテストしているのか理解でき、直前の改修でなにが壊れたのかがわかるというわけです。

感想

ぼくはc-lessonを今年の4月ごろから、別のリポジトリを進めながらぽつぽつやりはじめ、節の後半で加速度的にのめり込んでいって今月くらいで終わりました。いまでは言語処理系のなんたるかが前よりも理解できた感じがあるので、本格的な言語処理系を実装できそうな気がしています。わくわくですね。

このまま第二回のアセンブラ・逆アセンブラづくりに進んでいって、感想を目指してみるつもりです。

おまけ

あ、そうそう、継続の実装のところをやってたときに閃いて、「入力が不完全なとき停止して、完全な入力になったときに結果を返すパーサー」を実装してみました (Gistのこれ)。これを実現するのに継続が関係してそうとはわかってたんですが、c-lessonのおかげで実装言語のコールスタックに依存してるとパーサを止められないことが本質だとわかったので実装できました。これについてはおいおい記事を書くかもしれません。