1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@9_ties(中村 晃一)

機械語手書きから言語処理系をブートストラップする(3)

1
Last updated at Posted at 2026-01-24

第二回の続きです。これまで 機械語 → pforth → plisp → asm → sasm → plisp2と実装してきて、そこそこの速度で動くLISP処理系 plisp2 と、高級アセンブラ sasm を手に入れました。そろそろ複雑なものの実装もできると思うので、作りたい言語の仕様を真面目に考えていきます。また、言語処理系の様々な実装技術にも触れていきたいと思います。

作る言語

作ろうと考えているものは、 記号処理・言語処理に適したインタプリタ言語 です。作った言語で、言語処理・数式処理など記号処理で色々と遊べればと思います。また、この言語処理系の実装の中で、言語処理系の理論や実装技術についても実践的に学べればと思っています。

一番最初に作った PlanckForth という名称に倣って、この言語を Planck と呼ぶことにします。

実装の進め方

Planckを作る為にも色々なものが必要です。以下のようなものが必要だろうと思います。

  • Planck: Planckインタプリタ本体
  • Planck VM: Planckの実行に特化した高性能なVM
  • Planck IR: Planck VMの実装に用いる低級抽象機械語
  • Planck IRからの最適化コンパイラ・アセンブラ・リンカ

Panck IRはLLVM的な低級なやつなので、高級な型付き言語も必要になるかもしれません。その辺は後々考えます。

さて、これらをどのように作っていくかですが、Planckを 言語処理系実装に適した言語 と宣言する以上、全てのツールの実装は Planck で行われるべきでしょう。すると実装の進め方は以下のようになります。

  • sasm と plisp2 でPlanckの初期バージョンを実装(以後 planck0)
  • それを使ってツール群を実装
  • 出来たツール群でPlanckを再実装
    • これで機械語から積み上げてきたことによる負債を切り離す。

Planckの特徴

こだわりのある言語仕様は以下の2つです。(以前、アセンブリ言語からのブートストラッピングをやった際も同様の機能を持つ言語を作りました。)

  • S式ではなく、M式を用いたホモアイコニックな言語 (ただし、構文糖衣を定義できる)
  • 関数引数でのパターンマッチ機能 & 部分関数融合機能を持つ

M式の採用

まず、ブートストラッピングを通してずっとやってきているように、小さな言語コアから自己拡張によって高級な言語になるプロセスが好きですのでLISPの哲学を継承したいです。ただし、S式が好みでは無いためM式というものに変えます。

S式では、例えば x + y という式を表現するのに (+ x y)というリストを用います。これは以下のような二分木ですが、構文木の表現としては自然ではありません。

構文木といったら以下のようなものをイメージすると思います。

これを表現する為にPlanckではConsセルの代わりに Add{x, y} といった シンボル + 引数 という形式を用いることにします。Mathematicaで使われているWolfram Languageが同様の形式を採用しており、M式 (M-expression) と呼ばれます。

また、LISPのようにホモアイコニック性を持たせます。コード上の表記 Add{x, y} と、内部で扱うデータモデルが同一ということです。ただし、 やはり (+ x y) よりも x + y と書きたいですから、Paraserを拡張可能なものとし、構文糖衣が定義できるようにします。

関数引数でのパターンマッチングと部分関数融合

記号処理の為には パターンマッチ機能 が欲しいです。多くの言語でのパターンマッチは switch とか match e of ...式みたいなもので書かれる事が多いですが、私は一つの関数の中に巨大な条件分岐があるのが好きではありません。つまり、以下のようなコードではなく

def compile(e, env) {
    match e of
        Add{x, y} -> ...
        Sub{x, y} -> ...
        ...
}

関数引数でのパターンマッチで書く形式を好みます。

def compile(Add{x, y}, env) {
    ...
}

def compile(Sub{x, y}, env) {
    ...
}

小さいシンプルな部品を合成して複雑な処理を実現する、という形の方が美しいと思っているからですね。そこで重要になってくるのが 部分関数融合機能 です。関数 f と g を水平合成した新しい関数 f | g を作る機能で、呼び出すと、f と g のうち引数が最初にマッチしたもの実行されるというものです。パターン毎に個別に書いた関数をこの機能で融合して一つの関数にする、というわけです。

言語仕様(骨子)

以上の重要な仕様を念頭に置きつつ、仕様を考えていきます。

データモデル

Planckは以下のデータを持つ。atom, mexpは構文と対応するホモアイコニックなデータ、objectは内部的に利用されるデータ。

  • atom: シンボル・整数・多倍長整数・浮動小数点数・文字列
  • mexp (M-expression):
    • atom
    • head{arg0, arg1, ...}
      • head: シンボル
      • arg0, arg1, ...: mexp
  • object: 構造体・配列など

仕様

  • atom/mexpは deep immutable である
  • mexpの同値性の比較は木のサイズに対してO(1)で実行できる
    • (多倍長整数や文字列の比較はその長さNに対してO(N))

deep immutability

  • mexp(atom含む)はimmutableであることが保証される
    • atomの一部を更新する命令は存在しない
    • mexpの引数を更新する命令は存在しない
    • mexpの引数にはobjectを代入できない(←「immutableなobjectならばmexpの引数にできる」という考え方もあります。おいおい考えます)
  • objectはimmutable/mutableかのフラグを持つ
    • immutableなobjectにmutableなobjectは代入できない

ここでいうimmutableは、deep immutableのことで、リンクを辿って到達できるデータの全てがimmutableであるという意味。また、shallow immutabilityはPlanckでは表現できない。

mexpのO(1)での比較

  • Planckではシンボル及びmexpのinterningが行われ、同一のmexpは式のサイズによらずO(1)で比較が可能である
    • ※ 整数・多倍長整数・浮動小数点数・文字列のinterningが行われるかは実装依存とする

interningとは、シンボル・mexpを作成する際に、ハッシュテーブル(等)を参照して、既に作られているデータと一致する場合にはそれを返すという手法です。LISPでは hash consing と呼ばれることもあります。この仕様を採用すると

  • パターンマッチが高速になる
  • 式をキーとした検索が高速になる

などのメリットがあります。メモリ使用量が減るというメリットもあります。デメリットはシンボル/mexpの作成コストが上がるのと、テーブルが並列化の阻害要因になるなどです。

Planckはパターンマッチを多用する言語なので比較が高速であるメリットを取りました。また、共通部分式の検索であるとか、式をキーとした検索が速い特徴が生きる場面が色々ありそうだと考えています。

並列化に関しては気になるポイントですが、ロックフリーハッシュテーブルにするとか、グローバルとスレッドローカルで階層的なテーブルにするとか後々やりようはあるかなと思いますので後で考えます。

Algebraic Effect

以上がこだわりのある仕様で、その他はあまり重要ではないのですが、Algebraic Effectをプリミティブとして入れとこうかなと思います。以下エフェクトと呼びます。言語処理系の実装において、継続や限定継続的なものが欲しい場面は多々あります。

  • 非決定的計算
  • エラーからの復帰(パーサーで文法エラーが起きたときに、適当に処理して続きから再開みたいなやつ)
  • 木を辿っている最中に処理を挟んで続きから再開
  • デバッガ
  • A正規化を美しく書く
  • 部分評価器におけるLet-Insertionを美しく書く

みたいな「途中で止めたのを再開」とか「局所的な処理と大域的な処理を行ったり来たり」とか制御フローを操る系ですね。

継続(call/cc)はちょっと強すぎるのでなしとして、shift/reset限定継続かalgebraic effectを入れようかなと思います。ここは強い拘りがあるわけではないのですが、shift/resetはシンプルな反面分かりにくく、algebraic effectの方が直感的にコードが書けるかなということでこちらをプリミティブとして採用することにしました。パターンマッチとの相性も良さそうです。

性能への影響は気になりますが、one-shot継続の最適化とハンドラーのインライン展開を入れれば気にならないでしょう。(仮実装である planck0 ではやらないです。)

末尾呼び出し最適化

再起的な構文木の変換では、再帰関数呼び出しを多用しますので、Tail Call Optimization (TCO) が行われることを仕様として保証しときます。(planck0ではやらないです。)

スペシャルフォームとマクロについて

Planckでは、関数引数でのパターンマッチが使えますので、eval に新しいM-exprの評価規則を後から追加するということが可能です。

eval(env, Def{x, e}) { ... }
eval(env, Set{x, e}) { ... }
eval(env, NewSyntax{...}) { ...　}

そうすると、スペシャルフォームやマクロのような概念は不要になります。
とはいえ、あらかじめ評価規則の定められた組み込み構文のセットは必要で、以下のようなものを用意しようと思います。

  • Def{x, e}: 変数定義
  • Set{x, e}: 代入
  • Call{f,arg}: 関数呼び出し
  • Do{e0,e1,...}: 逐次実行
  • If{cond, ifthen, ifelse}: 条件分岐
  • While{cond, body}: ループ
  • Lambda{param, body}: ラムダ抽象
  • Fusion{f0, f1}: 部分関数融合
  • Quote{e}、QuasiQuote{e}、UnQuote{e}: クオート
  • Handle{body, f}、Perform{e}: エフェクト
  • Tuple{e0, e1, ...}: タプル

関数呼び出しとラムダ抽象の引数の表現は悩みポイントでしたが、単一引数とし Tuple式で無引数・2個以上の引数を表現することとしました。以下のように長ったらしい書き方となりますが、内部表現としてはこの方が自然です。構文糖衣導入で書きやすくします。

Apply{f, Tuple{e0, e1, ..}}

また、TCOがあるならwhileは要らないという指摘がありそうですが、木やリストなど再帰的なデータを処理するなら再帰関数を使いたいですし、配列など直線的なデータを処理するならループを使いたいですし、メンタルモデルに合わせた表現を用いないと(私は)気持ちが悪いためこうしています。

Planck0の実装

言語のコアは大体こんなところかなと思いますので実装に移ります。Planck0は sasm (型なしC言語風言語) で作りますので、できるだけ簡単な割り切った実装にしますが、Algebraic EffectをシンプルなAST Traversalで実装するのは大変です。

継続を取り出しやすいように一旦、CPS形式(Continuation Passing Style)か、バイトコード列に変換するのが定石ですが、実装の楽な後者を選択し非常に単純なバイトコードインタプリタを用意することにします。

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?