KOTET'S
PERSONAL
BLOG

#dlang 2つの「コンパイル時」【翻訳】

#dlang #tech #translation #d_wiki #advent_calendar

これは User:Quickfur/Compile-time vs. compile-time - D Wiki を翻訳した D言語 Advent Calendar 2018 5日目の記事です。

この記事は原文と同じGNU Free Documentation Licenseで公開されます。

誤訳等あれば気軽に Pull requestを投げてください


By H. S. Teoh, March 2017

よく宣伝文句にされるD言語の機能のひとつに、素晴らしい「コンパイル時」能力があります。 しかしこの能力はしばしばD言語初心者の混乱と誤解を引き起こし、 苛ついたユーザーはディスカッションフォーラムにこのような質問を投げかけることになります。 「どう考えてもコンパイル時にわかる値なのに、 なんでコンパイラはコンパイル時にこの値を読んでくれないんですか?!」

この記事ではそんな誤解を解き明かすべく、Dの「コンパイル時」機能とはなにか、 どのように動作するのか、頻出の問題をどのように解決するかを説明します。

これはコンパイル時、あれもコンパイル時

混乱の原因は複数の意味を持つ「コンパイル時」という言葉には無さそうですね。 「コンパイル時」という言葉は素直な言い方に思えます。 コンパイル時とは、単に人間の書いたDのコードをコンパイラが黒魔術でマシンリーダブルな実行ファイルに変換する時間のことです。 だとすれば、機能Xが「コンパイル時」の機能で、機能Yも「コンパイル時」の機能なら、 当然XとYは好きなように組み合わせられなければいけないはずですね? ということで、すべてが「コンパイル時」に起こり、 コンパイラは魔法のようにすべてをシュッとしてくれなければいけないはずです。

もちろん現実には、混乱の原因と多少の関係があります。 大まかに言うと、よく「コンパイル時」と呼ばれるDの機能には少なくとも2つのカテゴリが存在します。

「コンパイル時」にはコンパイルの過程に明確なフェーズとして存在するこの2箇所があり、 この区別を理解することはDの「コンパイル時」機能がいかに動作するかを理解するカギとなります。

特にAST操作機能はコンパイル過程の早い段階で適用され、CTFEはもっと後の段階に適用されます。 これを理解すると、コード片が通過していくコンパイル過程を大まかに知る役に立ちます。

  1. 構文解析とパーシング。コンパイラは人間の書いたプログラムをスキャンしコードの構造を表現する構文木に変換します
  2. AST操作。テンプレートは展開され、その他AST機能が適用されます
  3. 意味解析。識別子をデータ、関数、変数と関連付けるなどして、様々なASTの各部位に意味が与えられます
  4. コード生成。意味解析がされたコードは実行ファイルになる機械語を出力するのに使われます

CTFEは意味解析とコード生成の間のどこかに位置しており、 コンパイラに埋め込まれたインタプリタ(CTFEエンジンと呼ばれる)によるDのコードの実行が基本的に関わっています。

CTFEは意味解析が行われた後にあるので、AST操作機能にはアクセスできません。 同様に、AST操作の段階ではコード中の構造に意味が与えられていないため、 ASTを操作する「コンパイル時」機能はCTFEエンジンの成果にはアクセスできません。

したがって、Dの「コンパイル時」機能に関して言えば、2つの異なる「コンパイル時」が存在します。 先のAST操作に関わる段階と、後のCTFEが関わる段階です。 この2つの混同がDの「コンパイル時」機能において特に遭遇する問題の原因です。

実際には、この2つのフェーズはもっと複雑に作用します。 これがどのように動くか理解するために、 「コンパイル時」機能の2つのカテゴリについてもっと詳しく見ていきましょう。

テンプレート展開・AST操作

コンパイラがコードをコンパイルするときに最初にすることは、 コードのテキストを抽象構文木(Abstract Syntax Tree、AST)として知られるものに変換することです。

たとえば、このプログラムは

import std.stdio;
void main(string[] args)
{
    writeln("Hello, world!");
}

以下のように再構築されます。

AST.svg

(注意:これはコンパイラが生成する実際のASTではありません。ただ主要な点を例示しているだけです。 コンパイラによって生成されるASTはこれと構造や細かい点が異なるかもしれません。)

ASTはコンパイラが見ているプログラムの構造を表しており、 コンパイラがプログラムを機械語に変換する過程で必要になるすべてが含まれています。

このASTで注目すべき点は、変数、メモリ、入力や出力といったものが含まれないところです。 コンパイルのこの時点では、コンパイラはプログラムの構造のモデルを構築するだけです。 この構造の中にはargswritelnのような識別子がありますが、コンパイラはまだそれらに意味を与えていません。 それはコンパイルのもっと後の段階で行われます。

Dの強力な「コンパイル時」機能のうち、このASTを操作する能力に由来するものがコンパイルされます。 ここでDが提供するものはテンプレートとstatic ifです。

テンプレート

もしあなたがテンプレートの基礎を理解しているなら、以下のセクションは飛ばしてもいいかもしれません。

Dの強力な機能のひとつに、C++のそれと同じようなテンプレートがあります。 テンプレートはコードのステンシル(訳注:同じ形をたくさん描くための文房具。型紙。)、 もしくはASTの部分木を生成できるASTパターンとして考えることができます。 例えば、以下のようなテンプレート構造体を考えてみましょう。

struct Box(T)
{
    T data;
}

Dでは、これは冠名テンプレート(eponymous template)と呼ばれる略記であり、完全に書き下すとこうなります。

template Box(T)
{
    struct Box
    {
        T data;
    }
}

このテンプレートに相当するASTはこのようになります。

Template1.svg

テンプレートのインスタンス化はこのように行います。

Box!int intBox;

たとえば型Box!intはまだ定義されていないかもしれません。 しかし、コンパイラは自動的にAST部分木のコピーをTemplateBodyノード下に作り、 その中のTをすべてintに置き換えます。 こうして生成された以下のようなAST部分木が、プログラムの宣言に加えられます。

Template-example1.svg

これは以下のようなコード片に相当します。

struct Box!int
{
    int data;
}

(実際はこのようなコードを書くことはできません。 Box!intという名前はテンプレート展開プロセスのためのものであり、 ユーザーコードで直接定義することはできません。)

同様に、同じテンプレートを以下のように違う宣言でインスタンス化すると、

Box!float floatBox;

以下のようなものを宣言したのと同じになります。

struct Box!float
{
    float data;
}

Box!float floatBox;

実際テンプレートをインスタンス化するたびに新しいAST部分木が生成され、プログラムのASTに組み込まれます。

この機能を使う主目的はコードの繰り返しの回避です。 よく繰り返されるコードを取り除いてテンプレートにすることができて、 そうするとコンパイラは自動的にテンプレートをインスタンス化して挿入します。 これによって多くの無駄なタイピングを防ぐことができて、 結果DRY(Don’t Repeat Yourself)の原則を守ることができます。

もちろんDのテンプレートはこれよりも奥がとてもとても深いものですが、 テンプレートのすべてを解説するのはこの記事のスコープを超えています。

ここで重要なのは、テンプレート展開はコンパイルのAST操作フェーズに行われ、 したがってテンプレート引数は問題のコードがAST操作フェーズにある時にわかっていなければならない、ということです。 Dにおいてはこのことが、テンプレート引数は「コンパイル時」にわかっていなければならない、と言われる傾向にあります。 しかしこれは多くの場合正確な表現ではありません。 テンプレート引数はコンパイルのAST操作フェーズの間にわかっていなければならない、と言ったほうが正確です。 後に見ていくように、正確な表現は理解を助け、 Dを学習する者がDの「コンパイル時」機能を使おうとしたときに遭遇する問題を回避する助けになります。

static if

DのコンパイルのAST操作フェーズにおけるもうひとつの強力な機能がstatic ifです。 これを使うとASTの部分木をコンパイルするか、逆にコンパイルせず取り除くかを選択できます。 たとえばこのように。

struct S(bool b)
{
    static if (b)
        int x;
    else
        float y;
}

このstatic ifは、コンパイラがテンプレートSを展開している時にブーリアン引数bが評価されることを意味しています。 この値はテンプレートが展開される時にわかっていなければなりません。 D業界では、値は「コンパイル時」にわかっていなければならない、 とよく言いますが、もっと正確であらねばなりません。 これは後で説明します。

bの値がtrueなら、static ifelseブランチは展開後のテンプレートから取り除かれます。 このように書いたなら、

S!true s;

このように宣言したのと同じことです。

struct S!true
{
    int x;
}

(もちろん実際はこのようなコードを書くことはできません。 S!trueという名前はテンプレート展開プロセスのためのものでありユーザーコードで直接定義できないからです。 これは説明のためのものです。)

elseブランチは展開後のテンプレートから完全になくなっています。 これは非常に重要なことです。

同様に、以下のように書いたなら、

S!false t;

以下のように宣言したのと同じ意味になります。

struct S!false
{
    float y;
}

ifブランチは展開後のテンプレートから完全になくなっています。 これもまた非常に重要です。

言い換えると、static ifは後のコンパイル段階が関わるASTに影響します。

もっと深く取り扱いましょう。 この段階、static ifが評価される段階で、変数、メモリ、I/Oのような概念はまだ存在しません。 私達はプログラムの構造を操作しています。 実行には関わりません。 上のコードで、xyは単なる識別子です。 まだ変数や、 structの具体的なオフセットに配置されるデータフィールドのような意味は与えられていません。 それはコンパイルの後の段階で行われます。

なぜこれが重要なのでしょうか?これがDの「コンパイル時」機能に対するよくある誤解に関係しているからです。 それにはCTFE、コンパイル時関数実行が関わってきます。 次はそれについて話しましょう。

CTFE

CTFEとはコンパイル時関数実行(Compile-Time Function Evaluation)という意味です。 これはDの提供する極めて強力な機能であり、 (筆者はDのそれのほうがはるかに強力だと思いますが)C++のconstexprと似ています。

CTFEを理解するにあたって最も重要なのは、それがAST操作フェーズが完了した後に行われるということです。 もっと正確に言うと、プログラムの問題になっている部分のASTが「ファイナライズ」され、 意味解析を行っている時に行われます。 識別子にはモジュール、関数、引数、変数などの意味が割り当てられ、 ifforeachのような制御構文にも意味が与えられ、 その他にも値範囲伝播(VRP、Value Range Propagation)のような意味解析が行われます。

定数畳み込み

意味解析の一部に定数畳み込みがあります。 たとえば、以下のようなコードを書いたとします。

int i = 3*(5 + 7);

計算に用いられるすべての引数がコンパイラの知っている定数であり、実行時に結果が変化しないため、 実行時にこのような計算をする(5を7に足して、その結果を3にかける)のは計算資源の無駄です。 もちろんこの例はささいなものですが、 もしプログラムのパフォーマンスに大きく影響するビジーインナーループにこのコードがあったら、 と想像してみてください。 もしこの定数式を結果の値に畳み込むことができたなら、 繰り返し同じ計算をしなくて良くなるためプログラムは速くなるはずで、 実際コンパイラは答えがわかっているので、ここでは何も行う必要はなくなります。 答えは直接iに代入できますね。

int i = 36;

この過程は定数畳み込みと呼ばれ、基本的に現代的なコンパイラならどの言語でも実装されています。 何も新しいことではありません。 しかしDコンパイラは、これを全く新しいレベルに昇華させました。

定数畳み込み(進化版)

例えばこんなコードを考えてみます。

int f(int x)
{
    return x + 1;
}

int i = 3*(5 + f(6));

再び手計算してみると、この式の値は36であるとわかります。 しかし今回は、式に関わる定数がfへの関数呼び出しで隠されています。 でもコンパイラはfの定義を見ることができて、そこでは引数に定数1を足しているだけなので、 コンパイラはこの式も定数であると推測可能であり、実行時には計算を行いません。

しかしfが単純な定数の足し算よりも複雑だったならばどうでしょうか。

int f(int x)
{
    int a = 0;
    for (int i=1; i <= x/2; i++)
    {
        a += i;
    }
    return a + 1;
}

int i = 3*(5 + f(6));

またもf(6)の値は定数ですが、 コンパイラがその値を知るためにはこの関数をコンパイル中に効率的に実行しなければなりません。 そしてそのためには、コンパイラはコンパイラの中に埋め込まれているDインタプリタで実行できる状態へと、 fの中身をコンパイルする必要があります。

簡単に言うと、これがCTFEがDの歴史に現れた経緯です。 D仮想マシンでできることには限界がありますが、その限界を可能な限りひろげようとする試みが目下進行中です。 これを書いている時点で、 DコンパイラはPhobos標準ライブラリのかなりの部分をコンパイル中に実行できるようになっており、 したがって多くのライブラリ機能はコンパイラ組み込みの実装を必要とせずにコンパイル時にアクセスできます。 さらに、現在のCTFEエンジンをバイトコードインタプリタを元にした、 より優れたCTFEパフォーマンスとメモリ管理、そしていつかは機能もより多くを実現する、 さらに強力なものに置き換える試みがStefan Kochの指揮のもと進められています。

CTFE評価の強制

もちろんコンパイラは定数畳み込みを常に前もって行ってくれるとは限りません。 複雑さがある一定のレベルを超えたら、 コンパイラはその式の値を計算するコードを実行時用に生成するために残しておいたほうが合理的です。 プログラム全体の目的が複雑な数学の問題を解いて決まった解を計算することかもしれません。 そのような計算は遅いCTFE上で行うよりも、 実行ファイルを生成してネイティブな実行速度で行ったほうがいいでしょう。

しかし、そのような計算を必要に応じてコンパイル時にできるようにしておくと、とても便利です。 たとえばルックアップテーブルの値を事前計算して実行ファイルに埋め込みたいとします。 そうすればプログラムの開始時のルックアップテーブルの初期化に関する実行時コストがなくなります。 このように、式の評価を実行時でなくコンパイル時に行ったほうが望ましい場面が時々あります。 そういうった場合に便利なイディオムとして、 コンパイル時に判明している値で計算を行った結果を代入するenumやテンプレート引数があります。 以下に例を挙げましょう。

int complicatedComputation(int x, int y)
{
    return ...; /* ここに複雑な計算が入る */
}

void main()
{
    // コンパイラは計算の複雑度に応じて、
    // これをコンパイル時に評価するか決定します。
    int i = complicatedComputation(123, 456);

    // enum の値はコンパイル時に判明していなければならないため、
    // コンパイラにはこれをCTFEで評価する以外の選択肢がありません。
    // これが式のCTFE評価を強制する標準的イディオムです。
    enum j = complicatedComputation(123, 456);
}

式の値がコンパイル時に判明している必要があるためにCTFE評価が強制されるので、 Dユーザー間の議論ではCTFEはこのような文脈で語られることが多いです。

異なる「コンパイル時」

元の話題に戻りますが、CTFE、 「バーチャルマシン」や「バイトコードインタプリター」と呼ばれるCTFEについては気をつけてください。 つまりどういうことかというと、ここでCTFEは、 コンパイル過程が実行ファイルを生成する手前まで進んだときに行われるということを意味しています。

特に、AST操作段階はとうの昔に終わっていることを意味しています。 つまり、CTFEで評価できるコードはもはやstatic ifのようなAST操作ができないということを意味します。 CTFEが動作するためには、 変数やメモリのような意味論的概念がコードの構成物に対して割り当てられている必要があり、 そうでなければ実行も評価もできません。 しかしAST操作フェーズでは、そのような意味は与えられていません。 まだプログラムの構造を操作しているところです。

したがって、AST操作が「コンパイル時」に行われているようにCTFEも「コンパイル時」に行われていたとしても、 それは異なる「コンパイル時」です。 CTFEのそれは、コンパイル過程の速いところで行われるAST操作よりも「実行時」に近いところにあります。 これが「コンパイル時」という用語が混乱を招く理由です。 この言葉はAST操作やCTFEのような機能すべてをひとつに固めて、 はっきりしない時間のまとまりである「コンパイル時」にしてしまうことで、 コンパイラがなにか魔法のように命令に従ってくれるという誤った印象を与えます。

重要なのは、AST操作が最初に適用され、その後必要に応じてCTFEが使われるということです。

AST操作 → CTFE

この単方向の矢印はコード片がAST操作からCTFEに移動して、逆には動かないことを示しています。

もちろんこれは単純化された図式です。 これらがどのように動くかを理解するためには、実際のコードを見てみるのが一番です。 というわけでD学習者が陥りがちな落とし穴と、そこで上の法則がいかに適用されるかを見ていきましょう。

ケーススタディ:CTFE変数をAST操作時に読む

Dフォーラムでとくに何度も現れる苦情はこのようなコードに関するものでしょう。

int ctfeFunc(bool b)
{
    static if (b)    // <--- この行でコンパイルエラー
        return 1;
    else
        return 0;
}

// 注:enumはコンパイラに関数のCTFEによる評価を強制します
enum myInt = ctfeFunc(true);

上のコードをコンパイルしようとすると、 コンパイラはstatic ifbの値を「コンパイル時」に読めないと主張します。 これは明らかにこんな反応を引き出すでしょう。 「は??!bがコンパイル時に読めないってどういう意味だよ?! このコードはコンパイル時であるCTFEで実行されてるんだからbの値はコンパイル時にわかるはずだろ?」

表面上、これはあきらかにコンパイラのバグか、Dの「コンパイル時」機能の欠陥か、 Dコンパイラ作者の驚くべき力量不足によって明らかかつシンプルなCTFEのユースケースにおける問題を通知することに失敗しているように見えます。

しかし、何が起きているかを正しく理解すれば、なぜコンパイラがこのコードを受け付けないかわかります。 コンパイルの過程で、DコンパイラはまずコードのASTを生成し、 static ifの評価はその結果出力されるASTの形を変えることを思い出してください。

コンパイラがctfeFuncの宣言に遭遇すると、コンパイラはその中身をスキャンし、 この関数のASTを構築するその時にstatic if (b)に遭遇します。 bの値がtrueなら、コンパイラはだいたいこんな感じのASTを出力します。

int ctfeFunc(bool b)
{
    return 1;
}

(AST操作段階で、static ifのfalseブランチは結果のASTから除外され、 はじめから何もなかったのと同じようになることを思い出してください。 したがってreturn 0はこの段階以降現れません。)

bの値がfalseならば、以下のコードに相当するASTツリーが出力されます。

int ctfeFunc(bool b)
{
    return 0;
}

しかし、ここで問題が発生します。 bの値はこの時点ではわかっていないのです。 この時点でbについてコンパイラが知っていることはこれが関数の引数を表す識別子だということだけです。 これがどんな値を持ちうるか等の意味はまだ与えられていません。 実際、コンパイラは引数trueが渡されているctfeFuncを呼び出すenumのことをまだ知りません!

コンパイラがenumの行を読んでいたとしても、今度は関数のASTがまだ完全に処理されていないため、 その値をbに代入することはできません。 ASTが変化すると識別子の意味も変化してしまう可能性があるので、 ASTが完全に構築されるまで値を識別子に代入することはできません。 この時点ではbになにか意味があるかのように値を代入するのはまだ早いのです。 引数への値の代入という概念ははAST操作フェーズが適用された後にのみ適用できる意味論的概念です。 しかしASTを最後まで処理するには、コンパイラはbの値を知らなければなりません。 bの値はASTを最後まで処理しないとわかりません。 これは解決できない袋小路なので、コンパイラは諦めてコンパイルエラーを出力するのです。

解決策1:AST操作中に値を使えるようにする

解決策のひとつはbの値をAST操作フェーズに使えるようにすることです。 それを実現する最も単純な方法はctfeFuncをテンプレート引数にbをとるテンプレート関数にして、 それに応じてenumの行がtrueを実行時引数でなくテンプレート引数として渡すように変更することです。

int ctfeFunc(bool b)()    // 注:最初のカッコの組にはテンプレート引数が入ります
{
    static if (b)    // エラーを出さずにコンパイルできるようになりました
        return 1;
    else
        return 0;
}

enum myInt = ctfeFunc!true;

bはテンプレート引数なので、その値はAST操作の時点で判明しており、 したがってstatic ifも問題なくコンパイルできます。

解決策2:すべてをAST操作で行う

先の方法もいいですが、より注意深く見てみると、もっとうまくできることに気が付きます。 AST操作の観点からもう一度考えてみましょう。 AST操作フェーズのあと、関数はこうなっているはずです。

int ctfeFunc()    // 注:テンプレート引数はAST操作フェーズの後には存在しません
{
    return 1;     // 注:static ifのelseブランチは取り除かれています
}

つまりCTFEはそもそも最初からこの関数について何も評価する必要はないのです! ctfeFuncを限界までテンプレートとして宣言すると、完全にAST操作フェーズに評価されるようになります。 (これはもはやCTFEで評価されておらず、関数でもないので、 名前もctfeFuncから変えたほうがいいかもしれません。)

template Value(bool b)
{
    static if (b)
        enum Value = 1;
    else
        enum Value = 0;
}

enum myVal = Value!true;

myValは完全にAST操作フェーズに評価されるようになり、CTFEは全く関与しなくなりました。

解決策3:すべてをCTFEに移す

さらにもうひとつ方法があります。 この例はいささか単純ですが、実際のCTFE関数は単なるブーリアン引数のif条件より、もっと複雑のはずです。 そういったものは素直にテンプレートに書き直すのが難しそうです。 そういった場合どうすればいいのでしょうか?

答えを聞いて驚かれるかもしれません。 static ifを取り除き、普通で「実行時」のifに置き換えるのです。 このように。

int ctfeFunc(bool b)
{
    if (b)    // <--- 注:static ifではなく普通のifです
        return 1;
    else
        return 0;
}

// 注:enumはコンパイラにCTFEでの関数評価を強制します
enum myInt = ctfeFunc(true);

そして不思議なことにこれはエラーを出さずにコンパイルされ、myIntには正しい値が入ります! しかしちょっと待ってください。 何が起こったのでしょう? どうしてstatic ifは、「コンパイル時」に必要な値を計算するのに、 「実行時」の物っぽいifへと変えることができたのでしょうか? コンパイラがずるをして、裏でこっそりmyIntを実行時に計算するようにしてしまったのでしょうか?

実際、実行ファイルのコードをディスアセンブラーで調べてみてもそのような不正は起きていません。 ならなんで動いているんでしょう?

インターリーブされるAST操作とCTFE

詳しく見てみましょう。この時、AST操作フェーズにおいて、 ctfeFuncに相当するASTの構築の他に行われることはありません。 static ifやその他テンプレートに関するものはないので、結果のASTは書いたとおりの素直なものになります。 そしてコンパイラはenumの宣言を見て、 ctfeFuncの「コンパイル時」評価が必要だと知ります。

ここで興味深いことが起こります。 ここまでしてきた話を元にすると、 (myIntのASTが完全に構築されていないので)コンパイラはまだ「AST操作」段階にあり、 ctfeFuncの意味解析フェーズが終わっていないので、これは失敗するはずですね? 確かにmyIntのASTはまだ完全には解決されていませんが (したがってCTFEで得られるmyintの値をこの時点で読むことはできません)、 しかしこの時点で、ctfeFuncのほうはコンパイルの次の段階に進む準備ができています。 より正確に言うとctfeFuncに関するプログラムのASTの部分木の処理は完了しており、 意味解析に渡すことが可能になっています。

そしてDコンパイラはこの分野に関してとても賢いので、ctfeFuncの意味解析がプログラムの他の部分、 つまりまだ完了していないmyIntの宣言のASTと独立して進められるとわかります。 これはctfeFuncのASTの部分木の意味解析が、 myIntのASTの部分技とまったく依存を持たず単体で可能なためにできることです! (ctfeFuncmyIntの値に何らかの形で依存している場合は失敗します。)

したがって、コンパイラはctfeFuncのASTに対して意味解析を行い、 CTFEエンジンが理解できる形まで持っていきます。 そしてCTFEエンジンは値trueを引数としてctfeFuncを呼び出し、実行します。 CTFEエンジンは、本質的に実行時に起きることをシミュレートします。 そして返り値1myIntのASTの処理を待つAST操作コードに戻され、残りのASTがすべて構築されます。

このAST操作にインターリーブする「スマートな」CTFEの呼び出しは、 プロセス全体に関わることにより「コンパイル時」という言葉にいくらか妥当性を与えるかもしれません。 しかし、あなたたちは今や2つの異なる「コンパイル時」が存在する理由についてよく理解できているはずです。 先にくるAST操作が行われる段階と、 後にくる、それがコンパイラの中で行われることを除けば実行時と似ているCTFEの段階、この2つです。 これらのフェーズはプログラムのASTの異なるパーツに対してはそれぞれバラバラなタイミングで適用されますが、 ASTの各パーツに対しては常にAST操作が先、CTFEが後という順番が守られます。 どのASTの部分木に対してもAST操作はCTFEがその部分技に適用できるようになる前に行われ、 ASTの部分木に対するCTFEは部分木全体がAST操作フェーズを通過している場合のみ実行できるようになります。

このAST操作とCTFEのインターリービングによってDの「コンパイル時」機能は非常に強力になっています。 任意の複雑な計算をCTFEで行い(もちろんCTFEエンジンの制約には従います)、 その結果をプログラムの別の部分のASTの操作に使うことができます。 CTFEを元にしてできたプログラムの一部を元に、 さらにそのプログラムの結果をまた別のプログラムのASTに影響させ、 さらに連鎖させていくこと、そのすべてがコンパイル過程の一部として行えます。 これはDのメタプログラミングの柱となる機能のひとつです。

ケーススタディ:pragma(msg)とCTFE

次に紹介するD学習者の一般的な苦情はCTFE関数のデバッグをしようとするときに起きるもので、 CTFEにおけるpragma(msg)の「奇妙な」振る舞いと関連しています。

ます最初にpragma(msg)のことをよく知らない人のために説明すると、 pragma(msg)というのはコンパイル時に起きることをデバッグする便利な機能のことです。 pragma(msg)ディレクティブがコンパイラに処理される時、 コンパイラはpragmaの引数として渡されたものをなんでも出力します。 たとえばこんなコードがあります。

template MyTemplate(T)
{
    pragma(msg, "instantiating MyTemplate with T=" ~ T.stringof);
    // ... ここに実際のコードが入る
}

MyTemplate!intがインスタンス化された時、 この行でコンパイラは”instantiating MyTemplate with T=int”と出力します。 この便利なデバッギングツールによって、 コード中でどんなインスタンス化が行われたか追跡することができます。

すてきですね、ここまでは。

しかしこのようなことをしようとすると苦情のもとになります。

int ctfeFunc(int x)
{
    if (x < 100)
        return x;
    else
    {
        pragma(msg, "bad value passed in");
        return -1;
    }
}
enum y = ctfeFunc(50); // 注:enumはctfeFuncに対してCTFEを強制します

引数50はctfeFuncの処理できる定義域内にあるにもかかわらず、 コンパイラは”bad value passed in”を出力し続けます。 そしてこれは101のような関数が拒否する値を与えてもかわりません。 何が起きているんでしょうか?

「コンパイラのバグだ!」と叫ぶ人がいるかもしれません。

しかし今のあなたなら答えが想像できるはずです。 pragma(msg)はAST操作フェーズに関連した概念なのです。 コンパイラはctfeFuncのASTを構築している時、 つまりCTFEの必要があるかわかっていない時点でメッセージを出力します。 その後、pragma(msg)はASTから取り除かれます。 前に述べたとおり、AST操作フェーズの間、コンパイラはifに意味を与えておらず、 また識別子xにもなんの値も与えていません。 それらはASTを構成するただのシンタックスノードとして扱われます。 なのでpragma(msg)は対象となるコードの意味論を尊重しません。 まだ意味はASTに結び付けられていないのです! ASTを操作してpragma(msg)の含まれる部分木を取り除くものが何もないので、 このメッセージはxの値がCTFEの結果どうなろうと常に出力されます。 関数がCTFEを行う時点では、pragma(msg)はすでにASTから取り除かれているため、 CTFEエンジンはそれについて何もしません。

ケーススタディ:static ifと__ctfe

もうひとつ度々誤解のもとになるのが、言語組み込みの魔法の変数__ctfeです。 この変数はCTFEエンジンの中ではtrueと評価され、実行時は常にfalseと評価されます。 実行時には動くものの、CTFEではサポートされていないような機能をコードが含む際に、 CTFEエンジンの制限を回避するのにこれが役立ちます。 パフォーマンス上の特徴を活かしてCTFEエンジンのコードを最適化するのにも使えます。

シンプルな例を挙げると、一般にstd.array.appenderは実行時に大量の値を配列に追加する際推奨されます。 しかし現在のCTFEエンジンの仕組み上、 CTFEエンジンの中では単に配列組み込みの追加演算子~を使ったほうがいいです。 そうすることでCTFEのメモリーフットプリントの削減ができるので、 コンパイル速度の改善につながるかもしれません。 そこで__ctfe変数を参照してCTFEと実行時、どちらの実行に依存した実装を使うか選ぶのです。

__ctfeが一見して「コンパイル時」変数で、CTFEエンジンに使うためのものに見えるので、 Dの初心者はこんなコードを書きがちです。

int[] buildArray()
{
    static if (__ctfe)  // <-- ここが3行目です
    {
        // CTFE中なので追加には単に~=を使います
        int[] result;
        foreach (i; 0 .. 1_000_000)
            result ~= i;
        return result;
    }
    else
    {
        // 実行時にはappender()をより高速なパフォーマンスのために使います
        import std.array : appender;
        auto app = appender!(int[]);
        foreach (i; 0 .. 1_000_000)
            app.put(i);
        return app.data;
    }
}

残念ながら、このコードはコンパイラに拒否されます。

test.d(3): Error: variable __ctfe cannot be read at compile time

これはほぼ確実にこんな反応を引き出します。 「なんだって?!__ctfeがコンパイル時に読めないってどういうことだよ?! これはCTFEのために作られたものなんだからコンパイル時の機能じゃないのか??」

しかし、知識を前もって身につけておけば、なぜこれが動かないかわかります。 static ifはコードのAST操作フェーズに関わるもので、 一方__ctfeは明らかにその後のCTFEフェーズのものです。 コンパイルのAST操作フェーズで、コンパイラはbuildArrayがCTFEで評価されるか否かを知りません。 実際ASTの構築が終わるまで意味解析は行われないため、 識別子__ctfeにはまだ意味は与えられていません。 意味解析が完了するまで識別子は決まった意味を持ちません。 そのためstatic if__ctfeはともに「コンパイル時」機能でありながら、 前者はコンパイルの早い段階、後者は後の段階に関わるものです。 ふたたび、その2つを混ぜ合わせて隠してしまう言葉「コンパイル時」が混乱を呼んでしまったようです。

解決策:単にifを使う

解決策はシンプルです。 単にstatic ififに置き換えてください。

int[] buildArray()
{
    if (__ctfe)   // <--- 注:static ifではありません
    {
        // CTFE中なので追加には単に~=を使います
        int[] result;
        foreach (i; 0 .. 1_000_000)
            result ~= i;
        return result;
    }
    else
    {
        // 実行時にはappender()をより高速なパフォーマンスのために使います
        import std.array : appender;
        auto app = appender!(int[]);
        foreach (i; 0 .. 1_000_000)
            app.put(i);
        return app.data;
    }
}

この関数のASTは完全に構築、解析、さらに必要に応じてCTFEエンジンに渡して実行することもできるようになったので、 buildArrayが正しく動作するようになりました。 CTFEエンジンがコードを実行する際には、 __ctfeには意味が割り当てられif文のtrueブランチが選ばれます。 実行時には、__ctfeは常にfalseとなりfalseブランチが常に選ばれます。

でも実行時パフォーマンスはどうなる?

残った疑問は、 一見実行時のものに見える「非静的」のifが実行ファイルに冗長なコードを生成してしまわないかです。 __ctfeは実行時には常にfalseのため、 CTFE専用のコードを実行しないという分岐を毎回行うのはCPUリソースの無駄です。 現代的CPUでは、分岐は命令パイプラインをストールさせ、パフォーマンスの低下に繋がります。 CTFEスペシフィックの部分はデッドウェイトでもあり、実行ファイルのサイズを増やし実行時に余分なメモリを消費し、 しかもそれは絶対に実行されないので無駄でしかありません。

しかしコードをコンパイルしディスアセンブラーで検証すると、そのようなことは起こっていません。 __ctfeの値はCTFEエンジンの外では静的にfalseであるため、分岐はコンパイラによって取り除かれます。 オプティマイザはif文のtrueブランチがデッドコードだとわかるので、 生成されるオブジェクトコードから単純に取り除きます。 パフォーマンスに影響はなく、実行ファイルにデッドコードも生まれません。

ケーススタディ:型リストに対するforeach

経験あるDコーダーでも間違えそうな例を見てみましょう。 以下の関数を考えてみます。

void func(Args...)(Args args)
{
    foreach (a; args)
    {
        static if (is(typeof(a) == int))
        {
            pragma(msg, "is an int");
            continue;
        }
        pragma(msg, "not an int");
    }
}
void main()
{
    func(1);
}

ひっかけ問題を出します。 このプログラムがコンパイルされる時、コンパイラは何を出力するでしょうか。

“is an int”と答えたあなた、間違いです。

こちらが出力です。

is an int
not an int

ちょっと待ってください! これは本当にバグでしょうか? funcには引数がひとつしか渡されていません。 どうして2行の出力が起きるのでしょうか?

これまでやってきたようにして、何が起きたか見ていきましょう。

まず、funcはテンプレート関数なので、 それが引数の型を指定した関数呼び出しによりインスタンス化されるまで意味論的に解析されません。 解析はコンパイラがmain関数を処理する途中、func(1)の呼び出しに遭遇したときに行われます。 そこでIFTI(Implicit Function Template Instantiation、関数テンプレートの暗黙的インスタンス化。 テンプレート関数のテンプレート引数を関数に渡された実行時引数の型から推測する処理)によって、 コンパイラはArgsに1要素のシーケンス(int)を代入します。

以上より関数呼び出しはこのように翻訳されます。

func!(int)(1);

これはfuncのインスタンス化を引き起こし、コンパイラはテンプレート本文をもとに専用のASTを構築します。 つまり、関数本文(のコピー)はAST操作フェーズに入ります。

自動アンローリング

ここではargsに対するforeachが行われています。 ここでトリッキーなことが起きていて、このforeachはただのforeachループではありません。 可変長引数に対するループです。 Dにおいてこのようなループは特殊な扱いをされます。 これは自動的にアンローリング、つまり展開されるのです。 ASTの観点から言うと、これはコンパイラがイテレーションごとにASTのコピーを生成するという意味です。 これがAST操作フェーズに行われるということにも注意してください。 これはCTFEとは関係ありません。 この種のforeachループは「実行時」のforeachとは異なるものです。

コンパイラがループ本文を処理すると、次はstatic ifに遭遇します。 条件がtrueなので(現在ループの対象になっており、関数の引数でもある要素は、値1のintです)、 コンパイラはstatic iftrueブランチを展開します。

その次にpragma(msg)が来るので、メッセージ”is an int”を出力します。

その下にはcontinueがあります。 そしてここが重要なポイントです。 今我々はAST操作フェーズにいるので、 continueは単に構築されるASTに付属するシンタックスノードでしかありません。 continueはAST操作フェーズでは解釈されません!

なので、ループ本文の次の要素に移動し、 AST操作コードは次のpragma(msg)を見つけて”not an int”と出力するのです。

これは注目すべき重要事項なので、強調のため繰り返します。

  1. CTFEはここで関係ありません。CTFEではなくAST操作フェーズでループアンローリングが起きています。
  2. continueはAST操作フェーズで解釈されず、あとでコードに翻訳するためにASTに残されます。

型リストに対するforeachはbreakやcontinueを解釈しない

最後の点は、 型リストに対するforeachが特別にループのアンローリング中にbreakcontinueを解釈してくれる、 と習熟したDユーザーでも誤解する可能性があるため念入りに説明するべきところでしょう。 次のコード片はその要点を表しています。

import std.stdio;
void func(Args...)(Args args)
{
    foreach (arg; args)    // 注:これは型リストに対するforeachです
    {
        static if (is(typeof(arg) == int))
            continue;

        writeln(arg);

        static if (is(typeof(arg) == string))
            break;

        writeln("Got to end of loop body with ", arg);
    }
}
void main()
{
    func(1, "abc", 3.14159);
}

このプログラムの出力はどうなると思いますか?(ひっかけではありません)

こちらが出力です。

abc

これはcontinuebreakがforeachによって解釈されるという最初の仮説にあわせて、 intである最初の引数が次のイテレーションまでループ本文をスキップしているかのように、 stringである2番めの引数がループから脱出してループアンローリングを中断したかのように見えます。

しかしそれは正しくありません。 最後のwritelnstatic assertに置き換えてみるとわかります。

import std.stdio;
void func(Args...)(Args args)
{
    foreach (arg; args)    // 注:これは型リストに対するforeachです
    {
        static if (is(typeof(arg) == int))
            continue;

        writeln(arg);

        static if (is(typeof(arg) == string))
            break;

        // stringによってループから脱出するので、
        // これはtrueになるはずですね?
        static assert(!is(typeof(arg) == string));  // 16行目
    }
}
void main()
{
    func(1, "abc", 3.14159);
}

これがコンパイラの出力です。

test.d(16): Error: static assert  (!true) is false
test.d(21):        instantiated from here: func!(int, string, double)

何が起きたのでしょう?

直感に反した結果に見えますが、実はとても単純で、 AST操作に対しての明瞭な考えで容易に理解できるはずです。 単に、foreachはAST操作フェーズでcontinuebreakを解釈していません。 それらは単にAST内のノードとして扱われ、コンパイラはループ本文の残りを処理します。 したがって、static assertは、 typeof(arg) == stringのため失敗するものも含めループの3回のイテレーションすべてで評価されます。

型リストに対するforeachは実際何をしているのか

しかし元のループはなぜcontinuebreakに従うのでしょうか? それに答えるために、Dコンパイラdmdが出力するAST(コメントが追記されています)を見てみましょう。

@safe void func(int _param_0, string _param_1, double _param_2)
{
        import std.stdio;
        /*unrolled*/ {
                {
                        int arg = _param_0;
                        continue;
                        writeln(arg);  // 注:スキップされていません!
                }
                {
                        string arg = _param_1;
                        writeln(arg);
                        break;
                }
                {
                        // 注:このイテレーションはスキップされていません!
                        double arg = _param_2;
                        writeln(arg);  // 注:スキップされていません!
                }
        }
}

コード生成(AST操作のあとにくるフェーズです)の時に、 コンパイラのコードジェネレータは最初のイテレーションが次のイテレーションへの無条件分岐をしていることに気づきます。 本質的に最初のイテレーションの残りの部分はデッドコードなので、全部取り除くことができます。 同様に、2番めのイテレーションのなかで、コードジェネレータはループの最後への無条件分岐を発見し、 イテレーションの残りがデッドコードであり除去できると気づきます。 最後に、3番目のイテレーションには絶対に到達しません。 これはデッドコードであり、すべて除去されるからです。

除去の結果、残りはこのようになります。

void func!(int, string, double)(int __arg0, string __arg1, double __arg2)
{
    writeln(__arg1);
}

これが出力されるものになります。

言い換えると、型リストに対するforeachはbreakcontinueの下のコードを取り除きません。 実際にはコードジェネレータの一部であるコンパイラのオプティマイザが、 最終的な実行ファイルに絶対に実行されない無駄なスペースができないようデッドコードを取り除いているのです。

解決策

元コードで提示されている難問を解決するこの場合で最もシンプルな解決策は、 static ifelse節をつけることです。

void func(Args...)(Args args)
{
    foreach (a; args)
    {
        static if (is(typeof(a) == int))
        {
            pragma(msg, "is an int");
            continue;
        }
        else    // <---- 注:else節
            pragma(msg, "not an int");
    }
}
void main()
{
    func(1);
}

これによって2番めのpragma(msg)は、 static ifの条件がfalseの時に生成されるASTからちゃんと取り除かれるようになります。

まとめ

まとめると、Dのコード片が通るコンパイルの段階には明確に区別できる(少なくとも)2つがあるということをここまでで学んできました。

  1. テンプレートが展開されstatic ifが処理されるAST操作フェーズ。 このフェーズではコードの構造をそのAST(Abstract Syntax Tree、抽象構文木)の形で操作します。 変数などの意味論的概念、breakcontinueのような制御構造の意味はこの段階では適用されません。
  2. 意味がASTに割り当てられる意味解析フェーズ。 変数、引数、制御構造などの概念がここで割り当てられます。 AST操作に関するものはここでは適用されません。 CTFE(Compile-Time Function Evaluation、コンパイル時関数実行)は、 すでにAST操作フェーズと意味解析フェーズを通ったコードに対してのみ行うことができます。 CTFEエンジンがコードに到達する時点では、テンプレートに関するものやstatic if、 その他AST操作機能は処理が行われており、CTFEエンジンには元のAST操作関連の構造物が見えません。

各コード片はAST操作フェーズと意味解析フェーズをこの順で通過して、逆の方向には行きません。 したがって、CTFEが実行できるのはAST操作フェーズが完了した後のコード片のみです。

そのうえで、まだAST操作フェーズにあるプログラムの他の部分は、 AST操作フェーズを通過してCTFEエンジンで実行できるようになったコード片によって計算された値に依存できます。 このAST操作とCTFEのインターリービングはDの「コンパイル時」機能を非常に強力にしています。 しかしあくまでCTFEで実行されるコードはその前にAST操作フェーズを通過していなければならない、 という条件の支配下にあります。 意味解析フェーズに到達していないものに依存することはできません。

AST操作とCTFEの混同はDの「コンパイル時」機能にたいする混乱とフラストレーションの原因の多くを占めます。