mizdra's poem

雑なこと (日記/技術ポエム/メモ/…) を書くブログです. 真に受けないでください.

2019-01-05

インタプリタ

今日もせっせと例のインタプリタを作っていた. 取り組んだのは評価器. まだ一部の式のみしか評価できなくて, 代入文やラムダ式は明日以降取り組む予定.

それとインタプリタ作っていて思ったことを言葉にした.

具体的には以下のような問題に遭遇した.

  • 失敗例1: 無の状態からインタプリタを作る際に, ある1つの言語機能 (例えば数値演算) がREPLで評価できるようにlexer, parser, evaluatorを一気に実装する
    • lexer, parser, evaluatorのそれぞれのドメインで必要とされる知識や概念が多くて詰まる
    • そもそもlexerやparserがlexer+parserではなく個々に分けられているのは, 巨大なために分割統治された結果であるから, 分割された領域ごとに取り組んだほうが良い
    • ドメインの依存関係が最初から多すぎるというのも問題
      • lexerだけ作るならlexerに対する依存関係はlexer->tokenくらいだが, parserも実装するとparser->{lexer, token, ast}の依存関係が発生する*1
      • evaluatorも実装するとevaluator->{parser, object, env, ast}が追加される
      • この状態でlexerのAPIを変更するとparserだけでなくevaluatorなども影響を受ける可能性がある
        • それがAPIの仕様変更が頻発する開発の初期段階で発生する
  • 失敗例2: パーサを作る際に「代入文もreturn文も式が使われているし, 式文を先に実装したら楽なのでは?」と考え式文から実装し始める
    • パーサ設計の中で一番難しいのが式のパース
    • 前置演算子と中置演算子の区別, 制御構文(if式, while式, ...), 演算子の優先順位など扱う要素が沢山ある
    • 途中で辛くなってブランチを放棄した
    • 最終的には書籍と同様に式のパース処理をダミーの処理にして代入文やreturn文を先に実装し, パーサのプロトタイプをある程度作ってから式文に取り組む方式に移行した
  • 失敗3: 評価器を作る際に最初から環境 (変数などのランタイムデータを保持するアレ) を考慮したコードを書く
    • 式文の評価だけ行うなら環境は不要 (なはず) なので, 環境を考慮せず式文からやるのが正解

小さいと思ったドメインが大きいとびっくりするし気が滅入ってしまうので, 正確にドメインの大きさを見定めるのは大事. が, よく分かってない分野では見定めるだけの能力を持っていないので失敗しがち. もうちょっとドメインの調査に時間を割いておけば良かったのかなあ. でも無限に調査する時間があったら手を動かしたほうが良い気もする. 上手くバランスを取っていきたい.

*1:厳密に言うとparserはtokenだけ受け取れればlexerに直接依存する必要はないが, lexerとtokenは強い依存関係にあり, そのtokenと間接的に依存しているので候補に上げている