ちゃんとテストしてませんが、だいたいこれで行けると思います。

strings $(BIN_FILE_PATH) | grep -oP '(?<=rt0_).+(?=\.s)'

解説

Goの実行ファイルにはビルド時に使用したソースファイルへのパスが含まれており、さらに Go をビルドする際には必ず GOOS と GOARCH に対応した runtime/rt0_XXX.s が使用されるため、この方法が使えます。

補足

Windows 環境には strings も grep もデフォルトでは入っていないので、busybox を使いましょう。

tl;dr

• Windows Subsystem for Linuxにてapt経由でGoをインストールすると 1.10 が最新としてインストールされて困った
  • (現時点でのGoの最新バージョンは1.12 (2019年8月現在))
• Goenvを導入することで最新版をインストール

環境

• Windows Subsystem for Linux (Ubuntu 18.04)

apt経由でGoをインストール

$ apt-get install golang

ちなみにバージョン指定する事も可能
$ apt-get install golang-1.xx
尚、1.12 を指定してみると下記メッセージが出力される

E: Unable to locate package golang-1.12
E: Couldn't find any package by glob 'golang-1.12'
E: Couldn't find any package by regex 'golang-1.12'

Goenv

Goenvについて

• Goのバージョン管理ツール
• プロジェクト管理でバージョンを変えたりできるので便利。
• 他の言語のXXXenvも存在する。 ex.) Pyenv Rbenv などなど

導入手順

• インストール　　
  $ git clone https://github.com/syndbg/goenv.git ~/.goenv 　　
  or
  URL: https://github.com/syndbg/goenv

• 環境変数を追加する 　
  下記を .bash_profileなどに下記を追加する

~/.bash_profile

export GOENV_ROOT=$HOME/.goenv
export PATH=$GOENV_ROOT/bin:$PATH
eval "$(goenv init -)"

• 変更を反映させる
  $ source ~/.bash_profile

Goenv経由でGoをインストールする

• インストール可能バージョンを確認する
  $ goenv install -l

1.2.2
.
.
1.12.9
1.13beta1

• 今回は 1.12 をインストールします。 　　
  $ goenv install 1.12.9

• インストール済バージョンを確認する 　
  $ goenv versions

* 1.12.9 (set by /path/to/.goenv/version)

• Goの任意のバージョンを設定する 　
  $ goenv global 1.12.9

• バージョンの確認してみる　　
  $ go version

go version go1.12.9 linux/amd64

無事に最新版になっています。

おまけ

• Proxy環境下でのGoenv経由のGoインストール 　
  $ https_proxy=http://proxy.example.com:PORT goenv install 1.12.9

• 任意のプロジェクトのみバージョンを変更する 　
  $ goenv local 1.x.x

• goenv global したのにバージョンが変わらない！　　
  $ goenv rehash

参考

Ubuntuにapt-getで最新のGolangをインストールする方法
goenvでgoをインストール 〜初心者向け〜

Goで 「Weighted Random Selection」 をしたくなる時があります。しかし、Goでは Pythonの numpyのように便利な関数が提供されていないので自分で作るしかありません。今回は Go で 「Weighted Random Selection」 の実装方法を紹介します。

Weighted Random Selection とは

とある重み(確率分布)を元に要素をランダムに選択するやつです。numpyで言うと numpy.random.choice に当たります。下記は第一引数 ５([0,1,2,3,4]) から3つを確率分布pでランダムに選択する関数です。

>>> np.random.choice(5, 3, p=[0.1, 0, 0.3, 0.6, 0])
array([3, 3, 0])

ランダムな選択に重複を許可しない場合は引数に replace=False を指定します。

>>> np.random.choice(5, 3, replace=False, p=[0.1, 0, 0.3, 0.6, 0])
array([2, 3, 0])

今回はGoでこの処理を行う際の実装を紹介します。

Go による Weighted Random Selection

今回は最もシンプルな Linear Scan アルゴリズムで実装します。やることは[０~weightの合計値]の間でランダムに基準となる値を選び、基準からweightを順に引いていき、０以下になったらそれが選択されます。

早速実装していきます。下記はvの中からwの確率分布に従って1つだけ値を取得する関数です。

// 0 ~ max までの範囲でランダムに値を返す
var randGenerator = func(max float64) float64 {
    rand.Seed(time.Now().UnixNano())
    r := rand.Float64() * max
    return r
}

func weightedChoiceOne(v int, w []float64) float64 {
    // v を slice　に変換
    // ex) 5 -> [0, 1, 2, 3, 4]
    vs := make([]int, 0, v)
    for i := 0; i < v; i++ {
        vs = append(vs, i)
    }

    // weightの合計値を計算
    var sum float64
    for _, v := range w {
        sum += v
    }

    // weightの合計から基準値をランダムに選ぶ
    r := randGenerator(sum)

    // weightを基準値から順に引いていき、0以下になったらそれを選ぶ
    for j, v := range vs {
        r -= w[j]
        if r < 0 {
            return v
        }
    }
    // should return error...
    return 0
}

最後のreturn 0 はたまたま１つも選ばれなかった(基準がweightの合計と丁度一致した時など)場合に到達します。確率的にほとんどありませんが、ここはこの関数を使う状況によってエラーハンドリングや空で返すなどの対策が考えられます。

上記のコードを少し変更すれば選ぶ数の指定 & 重複排除も実装できます。ポイントは選ばれた物をスライスから排除しておくことです。

func weightedChoice(v, size int, w []float64) ([]float64, error) {
    // v を slice　に変換
    // ex) 5 -> [0, 1, 2, 3, 4]
    vs := make([]int, 0, v)
    for i := 0; i < v; i++ {
        vs = append(vs, i)
    }

    // weightの合計値を計算
    var sum float64
    for _, v := range w {
        sum += v
    }

    result := make([]float64, 0, size)
    for i := 0; i < size; i++ {
        r := randGenerator(sum)

        for j, v := range vs {
            r -= w[j]
            if r < 0 {
                result = append(result, float64(v))

                // weightの合計値から選ばれたアイテムのweightを引く
                sum -= w[j]

                // 選択されたアイテムと重みを排除
                w = append(w[:j], w[j+1:]...)
                vs = append(vs[:j], vs[j+1:]...)

                break
            }
        }
    }
    return result, nil
}

選択されたアイテムと重みの削除のコードが少し特殊に見えますが、下記の公式Wikiを参考に実装しています。
https://github.com/golang/go/wiki/SliceTricks#delete

これを使えば与えられたweightにしtがってランダムに値を返します。

func main() {
    r1 := weightedChoiceOne(5, []float64{0.1, 0.1, 0.2, 0.9, 0.1})
    r2, _ := weightedChoice(5, 4, []float64{0.1, 0.9, 0.2, 0.3, 0.1})
    fmt.Println(r1) // 3
    fmt.Println(r2) // [1 3 2 0]
}

これで Weighted Random Selection が実装できました！ 今回は最もシンプルな Linear Scan での実装を紹介しましたが、そのほかのアルゴリズムはこのサイトが勉強になります。https://blog.bruce-hill.com/a-faster-weighted-random-choice

コードは Go Playground にあげておきます。
https://play.golang.org/p/-vqQEvwCi44

環境

• Windows 10
• Golang(go1.12.9)
• VS Code
• Git

実装

Golangのダウンロード

https://golang.org/dl/
上記からDLしていく。

• Featured downloads
  • Microsoft Windows go1.12.9.windows-amd64.msi

を選択する。

インストーラの進め方

ダウンロードが完了したら、インストーラが起動する。
今回はすべてチェックを変えずに、そのまま進めた。
(インストール場所もC:\Go)

環境変数の設定

環境変数を編集する。
PowerShellを管理者で開き、以下のコマンド。

Start C:\Windows\system32\rundll32.exe sysdm.cpl, EditEnvironmentVariables

GOPATHとGOROOTがあることを確認したら、
ユーザー環境変数のPathを変数値:%GOPATH%\binに設定する。
また、GitのPathが通っているか確認し、通っていない場合はPathを通しておく。

次に、PowerShellを再起動させ、GoとGitのPathが通っていることを確認する。

go version
git --version

Golangのデバッガをインストール

VS Code上でGolangのデバッグができるようにする。

go get -u -v github.com/derekparker/delve/cmd/dlv

Golangの開発に必要な外部パッケージをインストールする。

VS Codeを開き、拡張機能のGoをインストールする。
VS Code上で、Ctrl+Shift+pでコマンドパレットを開き、GO: Install/Update toolsで検索する。
全てのツールを選択し、OKボタンをクリックしてインストールする。

正常にインストールに成功した場合、以下の表示がでる。

All tools successfully installed. You're ready to Go :).

終わりに

以上で、Go言語の開発環境を構築することができました。
自分がつまったところを以下に記載しましたので、よかったら参考にしてください。
VS Code上でGolangのパッケージをインストールする時にでたエラーを解決した

環境

• windows 10
• Golang 1.12.9
• VS Code # 問題 VS Code上でGolangのパッケージをインストールする時に、表示されたエラーは以下。

//一部分のみ記載
Installing 16 tools at C:\Users\~\go\bin


  gocode

Installing github.com/mdempsky/gocode FAILED

16 tools failed to install.

gocode:
Error: Command failed: C:\Program Files\Go\bin\go.exe get -u -v github.com/mdempsky/gocode
github.com/mdempsky/gocode (download)
go: missing Git command. See https://golang.org/s/gogetcmd
package github.com/mdempsky/gocode: exec: "git": executable file not found in %PATH%
github.com/mdempsky/gocode (download)
go: missing Git command. See https://golang.org/s/gogetcmd
package github.com/mdempsky/gocode: exec: "git": executable file not found in %PATH%

解決策

エラーメッセージを読むと、

• Gitがインストールされていない
• GitのPATHが通っていない

いずれかが問題であるらしいので、コマンドプロンプトを開いて確認。

git --version

gitはインストールしてあるが認識しなかったので、PATHを通す。

Golangのパッケージのインストールを再度試し、以下の表示がでた。

All tools successfully installed. You're ready to Go :).

以上で、正常にインストールが完了した。

はじめに

コンパイラ本の影響か最近巷ではコンパイラ自作がブームになっていますが、GoでCのコンパイラを書くというののN番煎じをやりました。その際に「Goの持つ表現能力を限界まで引き出す」というのをやってみたかったので、専用のDSLを作りならコンパイラを書いてみました。また、単体テストしやすい設計を採用しています。

今回作ったコンパイラの内部DSLや設計の特徴は以下のようになります。

型安全なアセンブリコード生成DSL

有効なインストラクション/アセンブリコードかどうかをコンパイル時にチェックするようなDSLを作りました。

パーサーコンビネータをベースとしたコンパイラ生成DSL

パーサーコンビネータは大きなパーサーを小さなパーサーから合成していくのに使われる高階関数ですが、これを使ってコンパイラを定義したり合成したりするDSLを作りました。

単体テスト可能な"小さなコンパイラ"を組み合わせていく設計

特定の構文に対応するパーサーとコードジェネレーターが一体化されたモジュール(=小さなコンパイラ)を作り、それを単体テストで動作検証した上でコンパイラ本体へとDSLを使って合成していくような設計にしました。

コンパイラのリポジトリ

コンパイラの能力

現状のコンパイラの能力ですが、例えばクイックソートの実装をコンパイルして実行することができます。

クイックソートの例

int main(){
  int size; size = 30;
  int array[30]; int mem[30];

  setInputArray(array, size);

  printArray(array, size);

  qsort(array, 0, size, mem);

  printArray(array, size);

  return 0;
}

int qsort(int* array, int head, int tail, int* mem){
  int size; size = tail - head;
  if(size < 2){ return 0; }

  int i;
  for(i=0; i<size; i=i+1){ mem[head+i]=array[head+i]; }

  int cmp; cmp = array[head];
  int leftTail; leftTail = head;
  int rightHead; rightHead = tail;

  for(i=1; i<size; i=i+1){
    int val; val = mem[head+i];
    if(val<cmp) {
      array[leftTail] = val;
      leftTail = leftTail+1;
    }
    if(cmp<val+1) {
      array[rightHead-1] = val;
      rightHead = rightHead-1;
    }
  }

  array[leftTail] = cmp;
  qsort(array, head, leftTail, mem);
  qsort(array, rightHead, tail, mem);

  return 0;
}

int setInputArray(int* array, int size){
  int x; x = 1; int i;
  for(i = 0; i<size; i=i+1){
    x = x * 20021 + 1; x = x - (x/65536)*65536;
    array[i] = x - (x/size)*size;
  }
  return 0;
}

int printArray(int* array, int size){
  int i; int v;
  for(i=0;i<size;i=i+1){
    v = *(array + i);
    printInt(v); put(32);
  }
  put(10);
  return 0;
}

int printInt(int n){
  int div; int rem;
  div = n / 10; rem = n - div*10;
  if(div != 0){ printInt(div); }
  put(48 + rem);
  return 0;
}

int put(int c) {
  syscall 1 1 &c 1;
  return 0;
}

コンパイル対象のコード

コンパイル&実行

$ make exec-qsort
SRC_PATH=./examples/quick_sort.c make exec
docker-compose exec main /bin/bash -c "go run ./src < ./examples/quick_sort.c > ./tmp/out.s; gcc -o ./tmp/out.o ./tmp/out.s; ./tmp/out.o"
12 17 20 11 28 19 0 23 16 9 6 25 28 13 2 5 16 13 16 1 24 29 20 27 26 5 4 21 14 27
0 1 2 4 5 5 6 9 11 12 13 13 14 16 16 16 17 19 20 20 21 23 24 25 26 27 27 28 28 29

実装済みの機能としては、四則演算/変数宣言・呼び出し/関数定義・呼び出し/制御構文(if/for/while/return)/ポインター/ポインターの加算/配列などです。まだまだ未実装の機能も多いのですが、特に目的もない(セルフホスト出来ない)ので、一旦このへんで区切りとしました。

DSLとモジュール設計の概要

DSLを使ってモジュールを書き、単体テストを行い、それをコンパイラ本体へと合成する様子を紹介します。

(1) DSLでモジュールを書く

特定の構文、例えばif文に対応するモジュールはDSLを使って以下のように定義できます。

if文のモジュールiferの定義

// 構文: "if" "(" <condition> ")" "{" <body> "}" に対応するコンパイラモジュール
func ifer(condition, body *Compiler) Compiler {
    // パーサーコンビネータDSLを使ってコンパイラ/パーサーの組み立てる
    return ai().Seq(If, LPar).And(condition).Seq(RPar, LBrc).And(body).Seq(RBrc).
        // アセンブリコード生成ルールをアタッチする
        SetEval(func(nodes []*ast.AST, code asm.Code) {
            nodes[0].Eval(code)
            label := fmt.Sprintf("iflabel_%d", ifcount)

            // アセンブリコード生成DSLでコードを書き出す
            code.Ins(
                i().Pop().Rax(),
                i().Cmp().Rax().Val(0),
                i().Je(label))

            nodes[1].Eval(code)
            code.Ins(i().Label(label))
            ifcount++
        })
}

パーサーコンビネータDSLとアセンブリコード生成DSLが使用されており、またパーサーとコードジェネレータが一体化されたモジュールとなっています。

(2) モジュールを単体テストする

各モジュールは単体テスト用に適当にインスタンス化して構文解析やコード生成を行うことができます。
単体テストは、生成されたコードをassertしたり、生成されたコードを実行することで行います。

`ifer`をインスタンス化して実行

ifCompiler := ifer(&numInt, &numInt) // "if" "(" <Int> ")" "{" <Int> "}" としてインスタンス化
ast, _ := ifCompiler.Call(tokenize("if(888){999}")) // パースしてコードジェネレータ付きASTを返す
ast.Eval(insts) // コード生成を実行
fmt.Print(insts.Show()) // コードを表示
// =>
//         push 888
//         pop rax
//         cmp rax, 0
//         je iflabel_0
//         push 999
// iflabel_0:

(3) モジュールをコンパイラ本体へと組み込む

モジュールをコンパイラ本体へとパーサーコンビネータDSLを使って組み込みます。

コンパイラ本体へのモジュールの合成

bodies = ai().Rep(oi().Or(
    ifer(&expr, &bodies).P(), forer(&expr, &bodies).P(), // ここでiferを合成
    whiler(&expr, &bodies).P(), returner(&semi).P(),
    ai().And(arrayDeclarer(varDeclarer(st).P(), st).P()).Seq(Semi).P(),
    ai().And(&semi, &popRax).P()).P())

この記事の構成

まずこれらのDSL/設計の仕様を紹介し、次に実装方法について紹介します。

• 仕様紹介
  • 型安全なアセンブリコード生成DSL
  • パーサーコンビネータをベースにしたコンパイラ生成DSL
  • コンパイラを単体テスト可能なモジュールを合成して作る
• 実装方法紹介
  • 型安全なアセンブリコード生成DSLの実装方法
  • パーサーコンビネータDSLの実装方法
  • ASTからコードを生成するまでの流れ

型安全なアセンブリコード生成DSL

アセンブリコードを生成する際に、専用のDSLを介することでコンパイル時に有効なインストラクションかどうかチェックできるようにしました。

例えば以下のようなアセンブリコードを生成する場合

pop rdi
pop rax
add rax, rdi
push rax

以下のようなDSLで書けます。

code.Ins(
    i().Pop().Rdi(),
    i().Pop().Rax(),
    i().Add().Rax().Rdi(),
    i().Push().Rax())

このDSLでは有効なインストラクションが書かれた時のみコンパイルが通り、それ以外はエラーになります。

code.Ins(i().Add().Rax().Rdi()) // OK
code.Ins(i().Rax().Add().Rdi()) // エラー
code.Ins(i().Rax().Rdi().Add()) // エラー
code.Ins(i().Add().Rax())       // エラー
code.Ins(i().Add())             // エラー
code.Ins(i().Rax())             // エラー

パーサーコンビネータをベースにしたコンパイラ生成DSL

コンパイラを定義したり合成するのにパーサーコンビネータを使用しています。

例えば"if" "(" <condition> ")" "{" <body> "}"という構文のパーサーは以下のように組み立てられます。

combinedPsr := ai().Seq(If, LPar).And(condition).Seq(RPar, LBrc).And(body).Seq(RBrc)

ここでfunc (Compiler) Andとfunc (Compiler) Seqはパーサーを連結するコンビネータで、前者はASTへ構文木を追加し、後者は追加をスキップします。

他のコンビネータとしては、パースに成功するパーサーを選択するfunc (Compiler) Orや

oi().Or(xxx, yyy, zzz) // <xxx> | <yyy> | <zzz>

パーサーの繰り返しからなるパーサーを作るfunc (Compiler) Repがあります。

ai().Rep(x) // ε | <x> | <x> <x> | <x> <x> <x> | ...

これらのコンビネータを使い、以下のような感じでコンパイラを組み立てることができます。

bodies = ai().Rep(oi().Or(
    ifer(&expr, &bodies).P(), forer(&expr, &bodies).P(),
    whiler(&expr, &bodies).P(), returner(&semi).P(),
    ai().And(arrayDeclarer(varDeclarer(st).P(), st).P()).Seq(Semi).P(),
    ai().And(&semi, &popRax).P()).P())

コンパイラを単体テスト可能なモジュールを合成して作る

そもそもモジュールを単体テストしたい理由ですが、モジュール内のバグをモジュールの単体テストで潰したいからです。
機能追加をしてバグが出たときに、その原因として

1. 機能追加した分のコードに誤りがあった
2. 追加したコードと既存コードとの相互作用でバグが生まれた
3. 追加したコードによって既存のバグが明らかになった

などが考えられますが、1のような簡単なバグを原因箇所が限定された状態(=つまりモジュール内)で補足することでつまらないミスが原因のバグへの対処を短時間で済ませられます。

コンパイラモジュールを単体テストする方法

各モジュールの型はCompilerか、Compiler型の値を生成する関数になっています。モジュールの単体テストはCompiler型の値を作った上で実行する(コンパイルさせる)ことで行えます。

小さなコンパイラnumIntを例に取るとこれは以下のように数字1つのコードから作られたトークン列をアセンブリコードへと変換します。

tokens := tokenize("10")      // コード"10"をトークン列化する
ast, _ := numInt.Call(tokens) // トークン列をコンパイルしてASTを返す
ast.Eval(insts)               // ASTを評価してコード生成(instsへと書き出し)
fmt.Print(insts.Show())       // 書き出されたインストラクションを表示
// =>
//         push 10  // 書き出されたアセンブリコード

もっと複雑な場合、例えばif文の場合はどうするかというと以下のようなシグネチャーを持った関数iferとしてモジュールを定義します。

func ifer(condition, body *Compiler) Compiler

これは以下のような構文をコンパイルするコンパイラを出力する関数です。

"if" "(" <condition> ")" "{" <body> "}"

iferをインスタンス化して実行する場合、例えばconditionとbodyとしてnumIntを渡すと以下のようになります。

`ifer`をインスタンス化して実行

ifCompiler := ifer(&numInt, &numInt) // "if" "(" <Int> ")" "{" <Int> "}" としてインスタンス化
ast, _ := ifCompiler.Call(tokenize("if(888){999}"))
ast.Eval(insts)
fmt.Print(insts.Show())
// =>
//         push 888
//         pop rax
//         cmp rax, 0
//         je iflabel_0
//         push 999
// iflabel_0:

モジュールの単体テストは単体テスト用のコンパイラを作り、生成されたコードを実行することで行なえます。

生成されたコードを実行して単体テスト

func TestIfer(t *testing.T) {
    for _, c := range []psrTestCase{
        {
            "if(0) { return 1} return 2", // コンパイル対象のコード
            []asm.Fin{},                  // 期待される出力アセンブリコード(省略可能)
            true,                         // パースに成功すること
            "2",                          // コード実行後に`rax`に積まれている値
        },
        {
            "if(1) { return 1} return 2",
            []asm.Fin{},
            true,
            "1",
        },
    } {
        prologue, ret := prologuer(newST()), returner(&numInt)
        // 単体テスト用にコンパイラを組み立てる: "if" "(" <Int> ")" "{" "return" <Int> "}"
        compCode(t, ai().And(&prologue, ifer(&numInt, &ret).P(), &ret), c)
    }
}

コード実行だけではなく、吐かれたアセンブリコードをassertするような単体テストもできます。

想定通りのコードが生成されているか単体テスト

func TestWhiler(t *testing.T) {
    for _, c := range []psrTestCase{
        {
            "while(0) { 1 }", // コンパイル対象のコード
            []asm.Fin{ // 期待される出力アセンブリコード
                i().Label("while_begin_0"),
                i().Push().Val(0),
                i().Pop().Rax(),
                i().Cmp().Rax().Val(0),
                i().Je("while_end_0"),
                i().Push().Val(1),
                i().Jmp("while_begin_0"),
                i().Label("while_end_0"),
            },
            true, // パースに成功すること
            "",
        },
    } {
        // "while" "(" <Int> ")" "{" <Int> "}" としてインスタンス化
        compCode(t, whiler(&numInt, &numInt), c)
    }
}

他の単体テストの例はこちら

DSL使ったコンパイラモジュールの定義

DSLを使ったモジュールの定義は、パーサーコンビネータDSLでコンパイラを組み立てた後に、それにコード生成ルールのアタッチをすることで行います。

DSLを使ってコンパイラモジュールを定義する様子をnumIntとiferを例に紹介します。

var numInt Compiler = ai().And(Int).
    SetEval(func(nodes []*ast.AST, code asm.Code) { // func (ast.AST) Evalをセット
        n := nodes[0].Token.Vali()  // Intの値を取り出す
        code.Ins(i().Push().Val(n)) // スタックへとpushするコード生成
    })

func ifer(condition, body *Compiler) Compiler {
    // "if" "(" <condition> ")" "{" <body> "}" をパースする、ASTへの追加はconditionとbodyだけ
    return ai().Seq(If, LPar).And(condition).Seq(RPar, LBrc).And(body).Seq(RBrc).
        // nodesはconditionとbodyのASTが入っている配列
        SetEval(func(nodes []*ast.AST, code asm.Code) { // func (ast.AST) Evalをセット  
            nodes[0].Eval(code) // conditionのコードを書き出し

            label := fmt.Sprintf("iflabel_%d", ifcount)

            // 条件分岐のコード書き出し
            code.Ins(
                i().Pop().Rax(), // conditionのコードが実行された結果の値をスタックからpop
                i().Cmp().Rax().Val(0),
                i().Je(label)) // conditionの評価結果が0ならlabelへとジャンプ

            nodes[1].Eval(code) // bodyのコード書き出し
            code.Ins(i().Label(label)) // ラベル書き出し
            ifcount++
        })
}

func (Compier) SetEvalはコード生成時に呼び出させる関数func (ast.AST) Evalをセットする関数です。SetEvalに渡す値の型は`func(nodes []*ast.AST, code asm.Code)ですが、引数のnodesは子のASTで、nodesの各要素のfunc (ast.AST) Evalを適宜呼び出しながらcodeへのインストラクションの書き出しを行います。

コンパイラ本体へとモジュールを合成する

コンパイラ本体はパーサーコンビネータDSLを使ってnumIntやifer含め各モジュールがインスタンス化され合成されることで構築されます。

コンパイラ本体の組み立て

func Generator() Compiler {
    body := func(st *SymTable) Compiler {
        var term, muls, adds, expr, bodies Compiler

        ptrRef := ptrDeRefer(st, lvIdenter(st).P())
        val := oi().Or(rvAddrer(lvIdenter(st).P()).P(), rvIdenter(st, &ptrRef).P())
        adds, muls, ptrAdd := addsubs(&muls), muldivs(&term), ptrAdder(st, &val, &expr)

        term = oi().Or(
            ai().And(&ptrAdd, &deRefer).P(),
            &numInt, syscaller(&expr).P(), funcCaller(&expr).P(), &val, // ここでnumIntを合成
            ai().Seq(LPar).And(&adds).Seq(RPar).Trans(ast.PopSingle).P())
        expr = oi().Or(assigner(oi().Or(&ptrAdd, &ptrRef).P(), &expr).P(), eqneqs(&adds).P())
        semi := ai().And(&expr).Seq(Semi)

        bodies = ai().Rep(oi().Or(
            ifer(&expr, &bodies).P(), forer(&expr, &bodies).P(), // ここでiferを合成
            whiler(&expr, &bodies).P(), returner(&semi).P(),
            ai().And(arrayDeclarer(varDeclarer(st).P(), st).P()).Seq(Semi).P(),
            ai().And(&semi, &popRax).P()).P())

        return ai().And(&bodies)
    }

    return ai().And(ai().Rep(funcDefiner(body).P()).P()).Seq(EOF)
}

コンパイラ本体の定義

型安全なアセンブリコード生成DSLの実装方法

アセンブリコードを生成するDSLは型によってコンパイル時にインストラクションの有効性をチェックしています。

例えばインストラクションmov rax, 8を書き出す以下のようなコードがあったとして、

code.Ins(i().Mov().Rax().Vali(8))

ここで型は以下のように変化しています。

i()                     // Ini
i().Mov()               // Oped
i().Mov().Rax()         // Dested
i().Mov().Rax().Vali(8) // Fin
code.Ins                // func(...Fin)

Mov, Rax, Valiはそれぞれ以下のような型を持ったメソッドで、レシーバーと返り値の型の指定で"型のステートマシン"のようなものを実装しています。

func (i Ini) Mov() Oped       // Ini => Oped
func (i Oped) Rax() Dested    // Oped => Dested
func (i Dested) Vali(int) Fin // Dested => Fin

また、code.Insの型はfunc(...Fin)なので、未完成なインストラクションを受け付けません。
正しい順番でインストラクションが組み立てられ、Valiのようなフィニッシャーによって完成された(Fin型になった)インストラクションのみ受理されます。

実装ですが、Ini, Opend, Dested, FinはそれぞれInsのエイリアスとなっており、

type Ini Ins
type Oped Ins
type Dested Ins
type Fin Ins

Insはインストラクションを表現する構造体です。

type Ins struct {
        ope  Ope
        dest Reg
        srcI int
        ...
}

Movなどの実装では、構造体への値のセットと型の変換を行っています。

func (i Ini) Mov() Oped {
    i.ope = OMov 
    return Oped(i)
}

上記は説明のために単純化している部分もあるので、実装の詳細が知りたい人はこちらを参照。

パーサーコンビネータDSLの実装方法

コンパイラの定義や組み立てで使用するDSLは、パーサーコンビネータを使って実装しています。パーサーコンビネータ(Parser Combinator)とは複数のパーサーを合成して新しいパーサーを作る高階関数です。

まずパーサーコンビネータ一般について紹介し、その後でDSLの実装方法を紹介します。

パーサーの定義

パーサーの型Parserをトークン列[]Tokenを消費して、タプル("パースに成功したか" bool, "構文木" SyntaxTree, "消費された残りのトークン列" []Token)を返す関数とします。

type Parser func([]token) (bool, SyntaxTree, []token)

トークン列[]Tokenとは、プログラムの文字列を前処理して扱いやすい形にしたもので、例えばトークンの型を以下のように定義したとして

type Token struct {
    Value string
    Type  string
}

文字列をトークン列化する関数tokenize(string) []Tokenは以下のような処理を行います。

tokenize("1+x") => []Token{{"1", "Int"}, {"+", "Operator"}, {"x", "Variable"}}

構文木SyntaxTreeはトークン列をパースした結果得られるもので、プログラムを木構造で表現するものです。構文木から余計な枝を落としたものが抽象構文木(Abstract Syntax Tree)=ASTで、ASTをトラバースする(舐める)ことでコード生成が行われます。

パーサーがトークン列を消費して構文木を返す例です。

Int型を受け付けるパーサーintParserの例

tokens := []Token{{"1", "Int"}, {"+", "Operator"}, {"x", "Variable"}}
ok, st, rest := intParser(tokens) // パースを実行
// ok => true : パースに成功
// st => Int型の1つの値(=1)を表現する構文木
// rest => []Token{{"+", "Operator"}, {"x", "Variable"}} : `Token{"1", "Int"}`が消費されている

ok, _, _ = intParser(rest) // 続けてパースを実行
// ok => false : パースに失敗

パーサーコンビネータの定義

パーサーコンビネータとは、複数のパーサーを合成して新しいパーサーを返す関数です。

基本的な合成の仕方には二通りあり、1つは合成元のパーサーが受理するトークン列を連結したものを受け付けるパーサーを作るような合成で、もう1つは合成元のパーサーのどれか1つがパースに成功すれば、それを選択するような合成方法です。

andCombinedParser ::= leftParser rightParser // 連結的な合成(連結されたトークン列を受理する)
orCombinedParser ::= leftParsr | rightParser // 並列的な合成(受理に成功するパーサーを選ぶ)

合成元のパーサーleftParseとrightParserをそれぞれトークン列leftTokensとrightTokensを消費して、構文木leftSyntaxTreeとrightSyntaxTreeを返すものだとします。

ok, leftSyntaxTree, leftRest := leftParser(append(leftTokens, Rest...))
// ok => true, leftRest => Rest
ok, rightSyntaxTree, rightRest := rightParser(append(rightTokens, Rest...))
// ok => true, rightRest => Rest

このとき連結的な合成を行うパーサーコンビネータandParserCombinatorはleftParserとrightParserを合成し新しいパーサーcombinedParserを返します。combinedParserはleftTokensとrightTokensを連結したトークン列を先頭に持つトークン列をパースできます。

combinedParser := andParserCombinator(leftParser, rightParser) // パーサーの合成
combinedTokens := append(append(leftTokens, rightTokens...), Rest...) // トークン列の連結
ok, combinedSyntaxTree, rest := combinedParser(combinedTokens) // 連結されたトークン列をパースできる
// ok => true
// combinedSyntaxTree => Combine(leftSyntaxTree, rightSyntaxTree)
// rest => Rest

合成されたパーサーcombinedParserはそれぞれのパーサーが消費するトークン列の連結append(leftTokens, rightTokens...)を消費し、合成された構文木Combine(leftSyntaxTree, rightSyntaxTree)を返します。構文木の合成Combineはパーサーコンビネータとはあまり関係ないのですが、例えば片方の構文木の子ノードにもう片方を加えるなどをして返す関数です(実装の都合に寄ります)。

並列的な合成を行うパーサーコンビネータorParserCombinatorは２つパーサーの能力を合わせたようなパーサーを合成します。

combinedParser := orParserCombinator(leftParser, rightParser) // パーサーの合成

// leftParserと同じパースが可能
ok, leftSyntaxTree, leftRest := combinedParser(append(leftTokens, Rest...))
// ok => true, leftRest => Rest

// rightParserと同じパースが可能
ok, rightSyntaxTree, rightRest := combinedParser(append(rightTokens, Rest...))
// ok => true, rightRest => Rest

パーサーコンビネータの実装方法

andParserCombinatorとorParserCombinatorはそれぞれ戻り値のパーサーをクロージャーとして作る以下のような関数として実装できます。

func andParserCombinator(leftParser, rightParser Parser) Parser {
    return func(tokens[] Token) (bool, SyntaxTree, []Token) { // パーサーをクロージャーとして返す

        // 最初にleftParserを実行
        ok, leftSyntaxTree, restTokens := leftParser(tokens)
        if !ok {
            return false, nil, nil // パースに失敗したらリターンする
        }

        // 続けてrightParserを実行(引数にrestTokensを渡しているのに注意)
        ok, rightSyntaxTree, restOfRestTokens := rightParser(restTokens)
        if !ok {
            return false, nil, nil // パースに失敗したらリターンする
        }
        // 両方のパーサーに消費されたトークン列restOfRestTokensを返す
        return true, Combine(leftSyntaxTree, rightSyntaxTree), restOfRestTokens
    }
}

func orParserCombinator(leftParser, rightParser Parser) Parser {
    return func(tokens[] Token) (bool, SyntaxTree, []Token) { // パーサーをクロージャーとして返す
        // 最初にleftParserを実行
        if ok, leftSyntaxTree, restTokens := leftParser(tokens); ok
            return true, leftSyntaxTree, restTokens // パースに成功したらリターンする
        }

        // leftParserが失敗したらrightParserを実行
        if ok, rightSyntaxTree, restTokens := rightParser(tokens); ok
            return true, rightSyntaxTree, restTokens // パースに成功したらリターンする
        }
        // 両方のパーサーとも失敗したらパース失敗
        return false, nil, nil
    }
}

パーサーコンビネータを使ったDSLの実装

パーサーを合成するメソッドfunc (Parser) Andとfunc (Parser) Orですが、上記で説明したパーサーコンビネータのほぼそのままで、変更点としては、

• パーサーを構造体の中に関数Parser.Callとして入れている(メソッドチェーンしたかったため)
• func (ast.AST) AppendNodeによって構文木の合成(子ノードとして追加)を行っている
• パースの失敗を型ast.ASTの定数ast.Failを返すことで表現している
• Andは構文木をASTに追加するかどうか引数addNodeで選択できる
• 繰り返し合成Repはパースに失敗するまでAndと同じ操作を繰り返す

などです。

// lhspがleftParser, rhspはrightParser, addNodeでASTへ追加するか選択
func (lhsp Parser) And(rhsp *Parser, addNode bool) Parser {
    call := func(t []tok.Token) (ast.AST, []tok.Token) {

        lhs, lhst := lhsp.Call(t)
        if lhs.Fail() {
            return ast.Fail, t // パースに失敗したのでリターン
        }

        rhs, rhst := rhsp.Call(lhst)
        if rhs.Fail() {
            return ast.Fail, t // パースに失敗したのでリターン
        }

        if addNode {
            lhs.AppendNode(rhs) // 構文木の合成
        }

        return lhs, rhst
    }

    return Parser{Call: call} // 構造体`Parser`に包んで返す
}

func (lhsp Parser) Or(rhsp *Parser) Parser {
    call := func(t []tok.Token) (ast.AST, []tok.Token) {

        if lhs, lhst := lhsp.Call(t); !lhs.Fail() {
            return lhs, lhst // パースに成功したのでリターン
        }

        if rhs, rhst := rhsp.Call(t); !rhs.Fail() {
            return rhs, rhst // パースに成功したのでリターン
        }

        return ast.Fail, t // パースに失敗
    }

    return Parser{Call: call}
}

func (lhsp Parser) Rep(rhsp *Parser) Parser {
    call := func(rest []tok.Token) (ast.AST, []tok.Token) {
        var node ast.AST
        lhs, lhst := lhsp.Call(rest)
        if lhs.Fail() {
            return lhs, rest
        }
        node, rest = lhs, lhst
        for { // パースに失敗するまで繰り返す
            rhs, rhst := rhsp.Call(rest)
            if rhs.Fail() {
                return node, rest // パースに失敗したら1つ前の結果をリターン
            }
            rest = rhst
            node.AppendNode(rhs)
        }
    }
    return Parser{Call: call}
}

パーサーコンビネータの定義ファイル

これらをCompilerの型を返すようにラップしたものが実際に使用するDSLとなります。

func (c Compiler) And(cps ...*Compiler) Compiler {
    for _, cp := range cps {
        c = Compiler(p(c).And(pp(cp), true))
    }
    return c
}

func (c Compiler) Seq(cps ...*Compiler) Compiler {
    for _, cp := range cps {
        c = Compiler(p(c).And(pp(cp), false))
    }
    return c
}

func (c Compiler) Or(cps ...*Compiler) Compiler {
    for _, cp := range cps {
        c = Compiler(p(c).Or(pp(cp)))
    }
    return c
}

func (c Compiler) Rep(cp *Compiler) Compiler {
    return Compiler(p(c).Rep(pp(cp)))
}

ラッパーの定義ファイル

ASTからコードを生成するまでの流れ

コンパイラが返すASTにはコードジェネレーターが付属しており、このジェネレーターfunc (AST) Evalを呼ぶことでコードが生成されますが、この仕組について説明します。

コンパイラがトークン列をパースしてアセンブリコードを生成するプロセスは以下のようになりますが、

ast, _ := compiler.Call(tokens) // トークン列をパースしてASTを返す
ast.Eval(insts)                 // astを評価してコード生成(instsへ書き出し)

ここでコード生成を行っているastのメソッドfunc (ast.AST) Evalは以下のように定義されています。Evalは子ノードのASTのEvalを再帰的に呼び出してAST全体をトラバースすることでコードを生成します。

func (a AST) Eval(code asm.Code) {
    if a.eval == nil {
        for _, node := range a.nodes {
            node.Eval(code) // もしevalがnilなら子のASTを評価する
        }
    } else {
        a.eval(a.nodes, code) // evalがセットされていたらそれを評価
    }
}

Evalが定義されているコード

ここでコードジェネレータevalや子ノードnodesは構造体ast.ASTのフィールドです。

type AST struct {
    nodes []*AST // 子ノード
    eval  func(nodes []*AST, code asm.Code) // コードジェネレータ
    ...
}

コードジェネレータevalが受け取る2つの引数のうちの1つcodeはfunc (ast.AST) Evalから渡されます。
もう1つの引数nodesはコンパイラを組み立てる要素、つまりAndの引数に渡されるコンパイラの返すASTを配列にしたものです。
例えばASTとしてast1、ast2を返すようなコンパイラcomp1、comp2があったとして、それらの合成

ai().And(comp1, comp2)

が返すASTは、ast.AST.nodesとしてast1とast2をアペンドしたものとなります。

ast, _ := ai().And(comp1, comp2).Call(tokens)
ast.nodes // => []ast.AST{ast1, ast2}

ast.Evalを呼ぶとast.evalがnilの場合コードジェネレータast1.Evalとast2.Evalが順番に呼びされることになります。
一方で独自のコードジェネレータast.evalがセットされている場合はそれを使ってコード生成が行われます。
構造体ast.ASTのフィールドevalに値をセットするのがメソッドfunc (Compiler) SetEvalです。

SetEvalの使用例

var c = ai().And(comp1, comp2).
    SetEval(func(nodes []*ast.AST, code asm.Code) {
        nodes[0].Eval(code) // comp1の返したASTのEvalを呼び出す
        nodes[1].Eval(code) // comp2の返したASTのEvalを呼び出す
        code.Ins(i().Push().Rax()) // 独自のコードを書き出す
    })

func (Compiler) SetEvalの実装ですが、アイディアとしては以下のような感じです。

func (c Compiler) SetEval(eval func(nodes []*ast.AST, code asm.Code)) Compiler {
    call := func(t []tok.Token) (ast.AST, []tok.Token) {
        ast, rest := c.Call(t)
        ast.eval = eval // 戻り地のASTに介入してevalをセットしている
        return f(ast), rest
    }
    return Compiler{Call: call}
}

実際にSetEvalを定義しているコード。

このDSLや設計を採用した感想

• 良かった点

このような設計にしたそもそもの目的は、バグを事前に、あるいは出来るだけ速い段階で潰すことで、これについては成功したと思います。

なぜバグを抑えたかったかというと、コンパイラのような比較的複雑なコードを書く場合、バグを潰すのにかかる時間が最も開発時間の多くを占めるだろうと考えられたからです。

DSLにはコードの表現能力を「制限する」ことで有効でないコード=バグったコードはそもそも書けないようにする効果があります。またロジックをシンプルに書けるので、その意味でもバグが混入しにくくなったのではないかと思います。

実際、DSLを使ってモジュールを書き、単体テストを通した段階でほとんどすべてのバグは潰せてたと思います。本体へとモジュールを合成した後の結合テストでバグが出る場合もありましたが、ここで出てくるバグは本質的に根深いもの、アルゴリズムや実装の根本的なあやまりに起因するものが多かったような気がします。そういったバグはどっちにしても時間を掛けて解決する必要/価値のあるものだったと思います。

• 悪かった点

DSLの設計で想定していなかったケース、モジュール間での情報のやり取りをさせるのに苦労しました。

モジュール間の関係性は「コード実行時にスタックに何個値を積むか」だけで、各モジュールはお互いのことを知りません。なので、モジュール間で情報のやり取りをさせる必要があるケース、たとえばポインターの足し算で、足される変数の型を変数モジュールから足し算モジュールへと伝えるのが素朴にはできません。
最終的にはシンボルテーブルを使うことである程度解消されましたが、モジュール間の情報のやり取りをサポートする基本的な仕組みを用意する必要があったのかも知れません。

DSLで開発プロセスを固めると、うまく行っている内はとてもうまくいくが、DSLで扱えないものが出てくると途端に面倒くさくなり、その意味でDSLの設計は根本的に難しいのかも知れません。

はじめに

コンパイラ本の影響か最近巷ではコンパイラ自作がブームになっていますが、GoでCのコンパイラを書くというののN番煎じをやりました。その際に「Goの持つ表現能力を限界まで引き出す」というのをやってみたかったので、専用のDSLを作りならコンパイラを書いてみました。また、単体テストしやすいモジュール設計を採用しています。

今回作ったコンパイラの内部DSLや設計の特徴は以下のようになります。

型安全なアセンブリコード生成DSL

有効なインストラクション/アセンブリコードかどうかをコンパイル時にチェックするようなDSLを作りました。

パーサーコンビネータをベースとしたコンパイラ生成DSL

パーサーコンビネータは大きなパーサーを小さなパーサーから合成していくのに使われる高階関数ですが、これを使ってコンパイラを定義したり合成したりするDSLを作りました。

単体テスト可能な"小さなコンパイラ"を組み合わせていく設計

特定の構文に対応するパーサーとコードジェネレーターが一体化されたモジュール(=小さなコンパイラ)を作り、それを単体テストで動作検証した上でコンパイラ本体へとDSLを使って合成していくような設計にしました。

コンパイラのリポジトリ

コンパイラの能力

現状のコンパイラの能力ですが、例えばクイックソートの実装をコンパイルして実行することができます。

クイックソートの例

int main(){
  int size; size = 30;
  int array[30]; int mem[30];

  setInputArray(array, size);

  printArray(array, size);

  qsort(array, 0, size, mem);

  printArray(array, size);

  return 0;
}

int qsort(int* array, int head, int tail, int* mem){
  int size; size = tail - head;
  if(size < 2){ return 0; }

  int i;
  for(i=0; i<size; i=i+1){ mem[head+i]=array[head+i]; }

  int cmp; cmp = array[head];
  int leftTail; leftTail = head;
  int rightHead; rightHead = tail;

  for(i=1; i<size; i=i+1){
    int val; val = mem[head+i];
    if(val<cmp) {
      array[leftTail] = val;
      leftTail = leftTail+1;
    }
    if(cmp<val+1) {
      array[rightHead-1] = val;
      rightHead = rightHead-1;
    }
  }

  array[leftTail] = cmp;
  qsort(array, head, leftTail, mem);
  qsort(array, rightHead, tail, mem);

  return 0;
}

int setInputArray(int* array, int size){
  int x; x = 1; int i;
  for(i = 0; i<size; i=i+1){
    x = x * 20021 + 1; x = x - (x/65536)*65536;
    array[i] = x - (x/size)*size;
  }
  return 0;
}

int printArray(int* array, int size){
  int i; int v;
  for(i=0;i<size;i=i+1){
    v = *(array + i);
    printInt(v); put(32);
  }
  put(10);
  return 0;
}

int printInt(int n){
  int div; int rem;
  div = n / 10; rem = n - div*10;
  if(div != 0){ printInt(div); }
  put(48 + rem);
  return 0;
}

int put(int c) {
  syscall 1 1 &c 1;
  return 0;
}

コンパイル対象のコード

コンパイル&実行

$ make exec-qsort
SRC_PATH=./examples/quick_sort.c make exec
docker-compose exec main /bin/bash -c "go run ./src < ./examples/quick_sort.c > ./tmp/out.s; gcc -o ./tmp/out.o ./tmp/out.s; ./tmp/out.o"
12 17 20 11 28 19 0 23 16 9 6 25 28 13 2 5 16 13 16 1 24 29 20 27 26 5 4 21 14 27
0 1 2 4 5 5 6 9 11 12 13 13 14 16 16 16 17 19 20 20 21 23 24 25 26 27 27 28 28 29

実装済みの機能としては、四則演算/変数宣言・呼び出し/関数定義・呼び出し/制御構文(if/for/while/return)/ポインター/ポインターの加算/配列などです。まだまだ未実装の機能も多いのですが、特に目的もない(セルフホスト出来ない)ので、一旦このへんで区切りとしました。

DSLとモジュール設計の概要

DSLを使ってモジュールを書き、単体テストを行い、それをコンパイラ本体へと合成する様子を紹介します。

(1) DSLでモジュールを書く

特定の構文、例えばif文に対応するモジュールはDSLを使って以下のように定義できます。

if文のモジュールiferの定義

// 構文: "if" "(" <condition> ")" "{" <body> "}" に対応するコンパイラモジュール
func ifer(condition, body *Compiler) Compiler {
    // パーサーコンビネータDSLを使ってコンパイラ/パーサーの組み立てる
    return ai().Seq(If, LPar).And(condition).Seq(RPar, LBrc).And(body).Seq(RBrc).
        // アセンブリコード生成ルールをアタッチする
        SetEval(func(nodes []*ast.AST, code asm.Code) {
            nodes[0].Eval(code)
            label := fmt.Sprintf("iflabel_%d", ifcount)

            // アセンブリコード生成DSLでコードを書き出す
            code.Ins(
                i().Pop().Rax(),
                i().Cmp().Rax().Val(0),
                i().Je(label))

            nodes[1].Eval(code)
            code.Ins(i().Label(label))
            ifcount++
        })
}

パーサーコンビネータDSLとアセンブリコード生成DSLが使用されており、またパーサーとコードジェネレータが一体化されたモジュールとなっています。

(2) モジュールを単体テストする

各モジュールは単体テスト用に適当にインスタンス化して構文解析やコード生成を行うことができます。
単体テストは、生成されたコードをassertしたり、生成されたコードを実行することで行います。

`ifer`をインスタンス化して実行

ifCompiler := ifer(&numInt, &numInt) // "if" "(" <Int> ")" "{" <Int> "}" としてインスタンス化
ast, _ := ifCompiler.Call(tokenize("if(888){999}")) // パースしてコードジェネレータ付きASTを返す
ast.Eval(insts) // コード生成を実行
fmt.Print(insts.Show()) // コードを表示
// =>
//         push 888
//         pop rax
//         cmp rax, 0
//         je iflabel_0
//         push 999
// iflabel_0:

(3) モジュールをコンパイラ本体へと組み込む

モジュールをコンパイラ本体へとパーサーコンビネータDSLを使って組み込みます。

コンパイラ本体へのモジュールの合成

bodies = ai().Rep(oi().Or(
    ifer(&expr, &bodies).P(), forer(&expr, &bodies).P(), // ここでiferを合成
    whiler(&expr, &bodies).P(), returner(&semi).P(),
    ai().And(arrayDeclarer(varDeclarer(st).P(), st).P()).Seq(Semi).P(),
    ai().And(&semi, &popRax).P()).P())

この記事の構成

まずこれらのDSL/設計の仕様を紹介し、次に実装方法について紹介します。

• 仕様紹介
  • 型安全なアセンブリコード生成DSL
  • パーサーコンビネータをベースにしたコンパイラ生成DSL
  • コンパイラを単体テスト可能なモジュールを合成して作る
• 実装方法紹介
  • 型安全なアセンブリコード生成DSLの実装方法
  • パーサーコンビネータDSLの実装方法
  • ASTからコードを生成するまでの流れ

型安全なアセンブリコード生成DSL

アセンブリコードを生成する際に、専用のDSLを介することでコンパイル時に有効なインストラクションかどうかチェックできるようにしました。

例えば以下のようなアセンブリコードを生成する場合

pop rdi
pop rax
add rax, rdi
push rax

以下のようなDSLで書けます。

code.Ins(
    i().Pop().Rdi(),
    i().Pop().Rax(),
    i().Add().Rax().Rdi(),
    i().Push().Rax())

このDSLでは有効なインストラクションが書かれた時のみコンパイルが通り、それ以外はエラーになります。

code.Ins(i().Add().Rax().Rdi()) // OK
code.Ins(i().Rax().Add().Rdi()) // エラー
code.Ins(i().Rax().Rdi().Add()) // エラー
code.Ins(i().Add().Rax())       // エラー
code.Ins(i().Add())             // エラー
code.Ins(i().Rax())             // エラー

パーサーコンビネータをベースにしたコンパイラ生成DSL

コンパイラを定義したり合成するのにパーサーコンビネータを使用しています。

例えば"if" "(" <condition> ")" "{" <body> "}"という構文のパーサーは以下のように組み立てられます。

combinedPsr := ai().Seq(If, LPar).And(condition).Seq(RPar, LBrc).And(body).Seq(RBrc)

ここでfunc (Compiler) Andとfunc (Compiler) Seqはパーサーを連結するコンビネータで、前者はASTへ構文木を追加し、後者は追加をスキップします。

他のコンビネータとしては、パースに成功するパーサーを選択するfunc (Compiler) Orや

oi().Or(xxx, yyy, zzz) // <xxx> | <yyy> | <zzz>

パーサーの繰り返しからなるパーサーを作るfunc (Compiler) Repがあります。

ai().Rep(x) // ε | <x> | <x> <x> | <x> <x> <x> | ...

これらのコンビネータを使い、以下のような感じでコンパイラを組み立てることができます。

bodies = ai().Rep(oi().Or(
    ifer(&expr, &bodies).P(), forer(&expr, &bodies).P(),
    whiler(&expr, &bodies).P(), returner(&semi).P(),
    ai().And(arrayDeclarer(varDeclarer(st).P(), st).P()).Seq(Semi).P(),
    ai().And(&semi, &popRax).P()).P())

コンパイラを単体テスト可能なモジュールを合成して作る

そもそもモジュールを単体テストしたい理由ですが、モジュール内のバグをモジュールの単体テストで潰したいからです。
機能追加をしてバグが出たときに、その原因として

1. 機能追加した分のコードに誤りがあった
2. 追加したコードと既存コードとの相互作用でバグが生まれた
3. 追加したコードによって既存のバグが明らかになった

などが考えられますが、1のような簡単なバグを原因箇所が限定された状態(=つまりモジュール内)で補足することでつまらないミスが原因のバグへの対処を短時間で済ませられます。

コンパイラモジュールを単体テストする方法

各モジュールの型はCompilerか、Compiler型の値を生成する関数になっています。モジュールの単体テストはCompiler型の値を作った上で実行する(コンパイルさせる)ことで行えます。

小さなコンパイラnumIntを例に取るとこれは以下のように数字1つのコードから作られたトークン列をアセンブリコードへと変換します。

tokens := tokenize("10")      // コード"10"をトークン列化する
ast, _ := numInt.Call(tokens) // トークン列をコンパイルしてASTを返す
ast.Eval(insts)               // ASTを評価してコード生成(instsへと書き出し)
fmt.Print(insts.Show())       // 書き出されたインストラクションを表示
// =>
//         push 10  // 書き出されたアセンブリコード

もっと複雑な場合、例えばif文の場合はどうするかというと以下のようなシグネチャーを持った関数iferとしてモジュールを定義します。

func ifer(condition, body *Compiler) Compiler

これは以下のような構文をコンパイルするコンパイラを出力する関数です。

"if" "(" <condition> ")" "{" <body> "}"

iferをインスタンス化して実行する場合、例えばconditionとbodyとしてnumIntを渡すと以下のようになります。

`ifer`をインスタンス化して実行

ifCompiler := ifer(&numInt, &numInt) // "if" "(" <Int> ")" "{" <Int> "}" としてインスタンス化
ast, _ := ifCompiler.Call(tokenize("if(888){999}"))
ast.Eval(insts)
fmt.Print(insts.Show())
// =>
//         push 888
//         pop rax
//         cmp rax, 0
//         je iflabel_0
//         push 999
// iflabel_0:

モジュールの単体テストは単体テスト用のコンパイラを作り、生成されたコードを実行することで行なえます。

生成されたコードを実行して単体テスト

func TestIfer(t *testing.T) {
    for _, c := range []psrTestCase{
        {
            "if(0) { return 1} return 2", // コンパイル対象のコード
            []asm.Fin{},                  // 期待される出力アセンブリコード(省略可能)
            true,                         // パースに成功すること
            "2",                          // コード実行後に`rax`に積まれている値
        },
        {
            "if(1) { return 1} return 2",
            []asm.Fin{},
            true,
            "1",
        },
    } {
        prologue, ret := prologuer(newST()), returner(&numInt)
        // 単体テスト用にコンパイラを組み立てる: "if" "(" <Int> ")" "{" "return" <Int> "}"
        compCode(t, ai().And(&prologue, ifer(&numInt, &ret).P(), &ret), c)
    }
}

コード実行だけではなく、吐かれたアセンブリコードをassertするような単体テストもできます。

想定通りのコードが生成されているか単体テスト

func TestWhiler(t *testing.T) {
    for _, c := range []psrTestCase{
        {
            "while(0) { 1 }", // コンパイル対象のコード
            []asm.Fin{ // 期待される出力アセンブリコード
                i().Label("while_begin_0"),
                i().Push().Val(0),
                i().Pop().Rax(),
                i().Cmp().Rax().Val(0),
                i().Je("while_end_0"),
                i().Push().Val(1),
                i().Jmp("while_begin_0"),
                i().Label("while_end_0"),
            },
            true, // パースに成功すること
            "",
        },
    } {
        // "while" "(" <Int> ")" "{" <Int> "}" としてインスタンス化
        compCode(t, whiler(&numInt, &numInt), c)
    }
}

他の単体テストの例はこちら

DSL使ったコンパイラモジュールの定義

DSLを使ったモジュールの定義は、パーサーコンビネータDSLでコンパイラを組み立てた後に、それにコード生成ルールのアタッチをすることで行います。

DSLを使ってコンパイラモジュールを定義する様子をnumIntとiferを例に紹介します。

var numInt Compiler = ai().And(Int).
    SetEval(func(nodes []*ast.AST, code asm.Code) { // func (ast.AST) Evalをセット
        n := nodes[0].Token.Vali()  // Intの値を取り出す
        code.Ins(i().Push().Val(n)) // スタックへとpushするコード生成
    })

func ifer(condition, body *Compiler) Compiler {
    // "if" "(" <condition> ")" "{" <body> "}" をパースする、ASTへの追加はconditionとbodyだけ
    return ai().Seq(If, LPar).And(condition).Seq(RPar, LBrc).And(body).Seq(RBrc).
        // nodesはconditionとbodyのASTが入っている配列
        SetEval(func(nodes []*ast.AST, code asm.Code) { // func (ast.AST) Evalをセット  
            nodes[0].Eval(code) // conditionのコードを書き出し

            label := fmt.Sprintf("iflabel_%d", ifcount)

            // 条件分岐のコード書き出し
            code.Ins(
                i().Pop().Rax(), // conditionのコードが実行された結果の値をスタックからpop
                i().Cmp().Rax().Val(0),
                i().Je(label)) // conditionの評価結果が0ならlabelへとジャンプ

            nodes[1].Eval(code) // bodyのコード書き出し
            code.Ins(i().Label(label)) // ラベル書き出し
            ifcount++
        })
}

func (Compier) SetEvalはコード生成時に呼び出させる関数func (ast.AST) Evalをセットする関数です。SetEvalに渡す値の型は`func(nodes []*ast.AST, code asm.Code)ですが、引数のnodesは子のASTで、nodesの各要素のfunc (ast.AST) Evalを適宜呼び出しながらcodeへのインストラクションの書き出しを行います。

コンパイラ本体へとモジュールを合成する

コンパイラ本体はパーサーコンビネータDSLを使ってnumIntやifer含め各モジュールがインスタンス化され合成されることで構築されます。

コンパイラ本体の組み立て

func Generator() Compiler {
    body := func(st *SymTable) Compiler {
        var term, muls, adds, expr, bodies Compiler

        ptrRef := ptrDeRefer(st, lvIdenter(st).P())
        val := oi().Or(rvAddrer(lvIdenter(st).P()).P(), rvIdenter(st, &ptrRef).P())
        adds, muls, ptrAdd := addsubs(&muls), muldivs(&term), ptrAdder(st, &val, &expr)

        term = oi().Or(
            ai().And(&ptrAdd, &deRefer).P(),
            &numInt, syscaller(&expr).P(), funcCaller(&expr).P(), &val, // ここでnumIntを合成
            ai().Seq(LPar).And(&adds).Seq(RPar).Trans(ast.PopSingle).P())
        expr = oi().Or(assigner(oi().Or(&ptrAdd, &ptrRef).P(), &expr).P(), eqneqs(&adds).P())
        semi := ai().And(&expr).Seq(Semi)

        bodies = ai().Rep(oi().Or(
            ifer(&expr, &bodies).P(), forer(&expr, &bodies).P(), // ここでiferを合成
            whiler(&expr, &bodies).P(), returner(&semi).P(),
            ai().And(arrayDeclarer(varDeclarer(st).P(), st).P()).Seq(Semi).P(),
            ai().And(&semi, &popRax).P()).P())

        return ai().And(&bodies)
    }

    return ai().And(ai().Rep(funcDefiner(body).P()).P()).Seq(EOF)
}

コンパイラ本体の定義

型安全なアセンブリコード生成DSLの実装方法

アセンブリコードを生成するDSLは型によってコンパイル時にインストラクションの有効性をチェックしています。

例えばインストラクションmov rax, 8を書き出す以下のようなコードがあったとして、

code.Ins(i().Mov().Rax().Vali(8))

ここで型は以下のように変化しています。

i()                     // Ini
i().Mov()               // Oped
i().Mov().Rax()         // Dested
i().Mov().Rax().Vali(8) // Fin
code.Ins                // func(...Fin)

Mov, Rax, Valiはそれぞれ以下のような型を持ったメソッドで、レシーバーと返り値の型の指定で"型のステートマシン"のようなものを実装しています。

func (i Ini) Mov() Oped       // Ini => Oped
func (i Oped) Rax() Dested    // Oped => Dested
func (i Dested) Vali(int) Fin // Dested => Fin

また、code.Insの型はfunc(...Fin)なので、未完成なインストラクションを受け付けません。
正しい順番でインストラクションが組み立てられ、Valiのようなフィニッシャーによって完成された(Fin型になった)インストラクションのみ受理されます。

実装ですが、Ini, Opend, Dested, FinはそれぞれInsのエイリアスとなっており、

type Ini Ins
type Oped Ins
type Dested Ins
type Fin Ins

Insはインストラクションを表現する構造体です。

type Ins struct {
        ope  Ope
        dest Reg
        srcI int
        ...
}

Movなどの実装では、構造体への値のセットと型の変換を行っています。

func (i Ini) Mov() Oped {
    i.ope = OMov 
    return Oped(i)
}

上記は説明のために単純化している部分もあるので、実装の詳細が知りたい人はこちらを参照。

パーサーコンビネータDSLの実装方法

コンパイラの定義や組み立てで使用するDSLは、パーサーコンビネータを使って実装しています。パーサーコンビネータ(Parser Combinator)とは複数のパーサーを合成して新しいパーサーを作る高階関数です。

まずパーサーコンビネータ一般について紹介し、その後でDSLの実装方法を紹介します。

パーサーの定義

パーサーの型Parserをトークン列[]Tokenを消費して、タプル("パースに成功したか" bool, "構文木" SyntaxTree, "消費された残りのトークン列" []Token)を返す関数とします。

type Parser func([]token) (bool, SyntaxTree, []token)

トークン列[]Tokenとは、プログラムの文字列を前処理して扱いやすい形にしたもので、例えばトークンの型を以下のように定義したとして

type Token struct {
    Value string
    Type  string
}

文字列をトークン列化する関数tokenize(string) []Tokenは以下のような処理を行います。

tokenize("1+x") => []Token{{"1", "Int"}, {"+", "Operator"}, {"x", "Variable"}}

構文木SyntaxTreeはトークン列をパースした結果得られるもので、プログラムを木構造で表現するものです。構文木から余計な枝を落としたものが抽象構文木(Abstract Syntax Tree)=ASTで、ASTをトラバースする(舐める)ことでコード生成が行われます。

パーサーがトークン列を消費して構文木を返す例です。

Int型を受け付けるパーサーintParserの例

tokens := []Token{{"1", "Int"}, {"+", "Operator"}, {"x", "Variable"}}
ok, st, rest := intParser(tokens) // パースを実行
// ok => true : パースに成功
// st => Int型の1つの値(=1)を表現する構文木
// rest => []Token{{"+", "Operator"}, {"x", "Variable"}} : `Token{"1", "Int"}`が消費されている

ok, _, _ = intParser(rest) // 続けてパースを実行
// ok => false : パースに失敗

パーサーコンビネータの定義

パーサーコンビネータとは、複数のパーサーを合成して新しいパーサーを返す関数です。

基本的な合成の仕方には二通りあり、1つは合成元のパーサーが受理するトークン列を連結したものを受け付けるパーサーを作るような合成で、もう1つは合成元のパーサーのどれか1つがパースに成功すれば、それを選択するような合成方法です。

andCombinedParser ::= leftParser rightParser // 連結的な合成(連結されたトークン列を受理する)
orCombinedParser ::= leftParsr | rightParser // 並列的な合成(受理に成功するパーサーを選ぶ)

合成元のパーサーleftParseとrightParserをそれぞれトークン列leftTokensとrightTokensを消費して、構文木leftSyntaxTreeとrightSyntaxTreeを返すものだとします。

ok, leftSyntaxTree, leftRest := leftParser(append(leftTokens, Rest...))
// ok => true, leftRest => Rest
ok, rightSyntaxTree, rightRest := rightParser(append(rightTokens, Rest...))
// ok => true, rightRest => Rest

このとき連結的な合成を行うパーサーコンビネータandParserCombinatorはleftParserとrightParserを合成し新しいパーサーcombinedParserを返します。combinedParserはleftTokensとrightTokensを連結したトークン列を先頭に持つトークン列をパースできます。

combinedParser := andParserCombinator(leftParser, rightParser) // パーサーの合成
combinedTokens := append(append(leftTokens, rightTokens...), Rest...) // トークン列の連結
ok, combinedSyntaxTree, rest := combinedParser(combinedTokens) // 連結されたトークン列をパースできる
// ok => true
// combinedSyntaxTree => Combine(leftSyntaxTree, rightSyntaxTree)
// rest => Rest

合成されたパーサーcombinedParserはそれぞれのパーサーが消費するトークン列の連結append(leftTokens, rightTokens...)を消費し、合成された構文木Combine(leftSyntaxTree, rightSyntaxTree)を返します。構文木の合成Combineはパーサーコンビネータとはあまり関係ないのですが、例えば片方の構文木の子ノードにもう片方を加えるなどをして返す関数です(実装の都合に寄ります)。

並列的な合成を行うパーサーコンビネータorParserCombinatorは２つパーサーの能力を合わせたようなパーサーを合成します。

combinedParser := orParserCombinator(leftParser, rightParser) // パーサーの合成

// leftParserと同じパースが可能
ok, leftSyntaxTree, leftRest := combinedParser(append(leftTokens, Rest...))
// ok => true, leftRest => Rest

// rightParserと同じパースが可能
ok, rightSyntaxTree, rightRest := combinedParser(append(rightTokens, Rest...))
// ok => true, rightRest => Rest

パーサーコンビネータの実装方法

andParserCombinatorとorParserCombinatorはそれぞれ戻り値のパーサーをクロージャーとして作る以下のような関数として実装できます。

func andParserCombinator(leftParser, rightParser Parser) Parser {
    return func(tokens[] Token) (bool, SyntaxTree, []Token) { // パーサーをクロージャーとして返す

        // 最初にleftParserを実行
        ok, leftSyntaxTree, restTokens := leftParser(tokens)
        if !ok {
            return false, nil, nil // パースに失敗したらリターンする
        }

        // 続けてrightParserを実行(引数にrestTokensを渡しているのに注意)
        ok, rightSyntaxTree, restOfRestTokens := rightParser(restTokens)
        if !ok {
            return false, nil, nil // パースに失敗したらリターンする
        }
        // 両方のパーサーに消費されたトークン列restOfRestTokensを返す
        return true, Combine(leftSyntaxTree, rightSyntaxTree), restOfRestTokens
    }
}

func orParserCombinator(leftParser, rightParser Parser) Parser {
    return func(tokens[] Token) (bool, SyntaxTree, []Token) { // パーサーをクロージャーとして返す
        // 最初にleftParserを実行
        if ok, leftSyntaxTree, restTokens := leftParser(tokens); ok
            return true, leftSyntaxTree, restTokens // パースに成功したらリターンする
        }

        // leftParserが失敗したらrightParserを実行
        if ok, rightSyntaxTree, restTokens := rightParser(tokens); ok
            return true, rightSyntaxTree, restTokens // パースに成功したらリターンする
        }
        // 両方のパーサーとも失敗したらパース失敗
        return false, nil, nil
    }
}

パーサーコンビネータを使ったDSLの実装

パーサーを合成するメソッドfunc (Parser) Andとfunc (Parser) Orですが、上記で説明したパーサーコンビネータのほぼそのままで、変更点としては、

• パーサーを構造体の中に関数Parser.Callとして入れている(メソッドチェーンしたかったため)
• func (ast.AST) AppendNodeによって構文木の合成(子ノードとして追加)を行っている
• パースの失敗を型ast.ASTの定数ast.Failを返すことで表現している
• Andは構文木をASTに追加するかどうか引数addNodeで選択できる
• 繰り返し合成Repはパースに失敗するまでAndと同じ操作を繰り返す

などです。

// lhspがleftParser, rhspはrightParser, addNodeでASTへ追加するか選択
func (lhsp Parser) And(rhsp *Parser, addNode bool) Parser {
    call := func(t []tok.Token) (ast.AST, []tok.Token) {

        lhs, lhst := lhsp.Call(t)
        if lhs.Fail() {
            return ast.Fail, t // パースに失敗したのでリターン
        }

        rhs, rhst := rhsp.Call(lhst)
        if rhs.Fail() {
            return ast.Fail, t // パースに失敗したのでリターン
        }

        if addNode {
            lhs.AppendNode(rhs) // 構文木の合成
        }

        return lhs, rhst
    }

    return Parser{Call: call} // 構造体`Parser`に包んで返す
}

func (lhsp Parser) Or(rhsp *Parser) Parser {
    call := func(t []tok.Token) (ast.AST, []tok.Token) {

        if lhs, lhst := lhsp.Call(t); !lhs.Fail() {
            return lhs, lhst // パースに成功したのでリターン
        }

        if rhs, rhst := rhsp.Call(t); !rhs.Fail() {
            return rhs, rhst // パースに成功したのでリターン
        }

        return ast.Fail, t // パースに失敗
    }

    return Parser{Call: call}
}

func (lhsp Parser) Rep(rhsp *Parser) Parser {
    call := func(rest []tok.Token) (ast.AST, []tok.Token) {
        var node ast.AST
        lhs, lhst := lhsp.Call(rest)
        if lhs.Fail() {
            return lhs, rest
        }
        node, rest = lhs, lhst
        for { // パースに失敗するまで繰り返す
            rhs, rhst := rhsp.Call(rest)
            if rhs.Fail() {
                return node, rest // パースに失敗したら1つ前の結果をリターン
            }
            rest = rhst
            node.AppendNode(rhs)
        }
    }
    return Parser{Call: call}
}

パーサーコンビネータの定義ファイル

これらをCompilerの型を返すようにラップしたものが実際に使用するDSLとなります。

func (c Compiler) And(cps ...*Compiler) Compiler {
    for _, cp := range cps {
        c = Compiler(p(c).And(pp(cp), true))
    }
    return c
}

func (c Compiler) Seq(cps ...*Compiler) Compiler {
    for _, cp := range cps {
        c = Compiler(p(c).And(pp(cp), false))
    }
    return c
}

func (c Compiler) Or(cps ...*Compiler) Compiler {
    for _, cp := range cps {
        c = Compiler(p(c).Or(pp(cp)))
    }
    return c
}

func (c Compiler) Rep(cp *Compiler) Compiler {
    return Compiler(p(c).Rep(pp(cp)))
}

ラッパーの定義ファイル

ASTからコードを生成するまでの流れ

コンパイラが返すASTにはコードジェネレーターが付属しており、このジェネレーターfunc (AST) Evalを呼ぶことでコードが生成されますが、この仕組について説明します。

コンパイラがトークン列をパースしてアセンブリコードを生成するプロセスは以下のようになりますが、

ast, _ := compiler.Call(tokens) // トークン列をパースしてASTを返す
ast.Eval(insts)                 // astを評価してコード生成(instsへ書き出し)

ここでコード生成を行っているastのメソッドfunc (ast.AST) Evalは以下のように定義されています。Evalは子ノードのASTのEvalを再帰的に呼び出してAST全体をトラバースすることでコードを生成します。

func (a AST) Eval(code asm.Code) {
    if a.eval == nil {
        for _, node := range a.nodes {
            node.Eval(code) // もしevalがnilなら子のASTを評価する
        }
    } else {
        a.eval(a.nodes, code) // evalがセットされていたらそれを評価
    }
}

Evalが定義されているコード

ここでコードジェネレータevalや子ノードnodesは構造体ast.ASTのフィールドです。

type AST struct {
    nodes []*AST // 子ノード
    eval  func(nodes []*AST, code asm.Code) // コードジェネレータ
    ...
}

コードジェネレータevalが受け取る2つの引数のうちの1つcodeはfunc (ast.AST) Evalから渡されます。
もう1つの引数nodesはコンパイラを組み立てる要素、つまりAndの引数に渡されるコンパイラの返すASTを配列にしたものです。
例えばASTとしてast1、ast2を返すようなコンパイラcomp1、comp2があったとして、それらの合成

ai().And(comp1, comp2)

が返すASTは、ast.AST.nodesとしてast1とast2をアペンドしたものとなります。

ast, _ := ai().And(comp1, comp2).Call(tokens)
ast.nodes // => []ast.AST{ast1, ast2}

ast.Evalを呼ぶとast.evalがnilの場合コードジェネレータast1.Evalとast2.Evalが順番に呼びされることになります。
一方で独自のコードジェネレータast.evalがセットされている場合はそれを使ってコード生成が行われます。
構造体ast.ASTのフィールドevalに値をセットするのがメソッドfunc (Compiler) SetEvalです。

SetEvalの使用例

var c = ai().And(comp1, comp2).
    SetEval(func(nodes []*ast.AST, code asm.Code) {
        nodes[0].Eval(code) // comp1の返したASTのEvalを呼び出す
        nodes[1].Eval(code) // comp2の返したASTのEvalを呼び出す
        code.Ins(i().Push().Rax()) // 独自のコードを書き出す
    })

func (Compiler) SetEvalの実装ですが、アイディアとしては以下のような感じです。

func (c Compiler) SetEval(eval func(nodes []*ast.AST, code asm.Code)) Compiler {
    call := func(t []tok.Token) (ast.AST, []tok.Token) {
        ast, rest := c.Call(t)
        ast.eval = eval // 戻り地のASTに介入してevalをセットしている
        return f(ast), rest
    }
    return Compiler{Call: call}
}

実際にSetEvalを定義しているコード。

このDSLや設計を採用した感想

• 良かった点

このような設計にしたそもそもの目的は、バグを事前に、あるいは出来るだけ速い段階で潰すことで、これについては成功したと思います。

なぜバグを抑えたかったかというと、コンパイラのような比較的複雑なコードを書く場合、バグを潰すのにかかる時間が最も開発時間の多くを占めるだろうと考えられたからです。

DSLにはコードの表現能力を「制限する」ことで有効でないコード=バグったコードはそもそも書けないようにする効果があります。またロジックをシンプルに書けるので、その意味でもバグが混入しにくくなったのではないかと思います。

実際、DSLを使ってモジュールを書き、単体テストを通した段階でほとんどすべてのバグは潰せてたと思います。本体へとモジュールを合成した後の結合テストでバグが出る場合もありましたが、ここで出てくるバグは本質的に根深いもの、アルゴリズムや実装の根本的なあやまりに起因するものが多かったような気がします。そういったバグはどっちにしても時間を掛けて解決する必要/価値のあるものだったと思います。

• 悪かった点

DSLの設計で想定していなかったケース、モジュール間での情報のやり取りをさせるのに苦労しました。

モジュール間の関係性は「コード実行時にスタックに何個値を積むか」だけで、各モジュールはお互いのことを知りません。なので、モジュール間で情報のやり取りをさせる必要があるケース、たとえばポインターの足し算で、足される変数の型を変数モジュールから足し算モジュールへと伝えるのが素朴にはできません。
最終的にはシンボルテーブルを使うことである程度解消されましたが、モジュール間の情報のやり取りをサポートする基本的な仕組みを用意する必要があったのかも知れません。

DSLで開発プロセスを固めると、うまく行っている内はとてもうまくいくが、DSLで扱えないものが出てくると途端に面倒くさくなり、その意味でDSLの設計は根本的に難しいのかも知れません。