D 1.0   D 2.0
About Japanese Translation

Last update Fri Mar 23 17:15:54 2007

テンプレート再訪

by Walter Bright, http://www.digitalmars.com/d


"What I am going to tell you about is what we teach our programming students in the third or fourth year of graduate school... It is my task to convince you not to turn away because you don't understand it. You see my programming students don't understand it... That is because I don't understand it. Nobody does."
-- Richard Deeman

概要

C++のテンプレートは、単なるトークンの置き換え機能を越えて、それ自身確立された プログラミング言語へと発展を遂げています。設計時に意図されたよりも遙かに多く C++テンプレートの有用な側面が"発見"されました。このような歴史的経緯の結果、 C++テンプレートはその不格好な構文や、難解な規則、そして実装の難しさについて 多くの批判にさらされています。さて、テンプレートに何ができてどのように使われるのかが わかった今、もし、一歩戻って言語を再設計していたら、テンプレートはどんな様子になって いたでしょうか。より強力で、美しく、説明も実装も 簡単なテンプレートが実現できるでしょうか。 この記事では、プログラミング言語D [1] での、 C++に代わるテンプレートの設計を紹介します。

類似点

引数の構文

まず目につくのが、実引数リストや仮引数リストを囲む < > です。 この < > にはしかし、重大な問題があります。 この括弧は、演算子 <, >, >> と区別がつかないのです。 つまり、次のような式や 

a<b,c>d;
次のような式は 
a<b<c>>d;

プログラマにとってもコンパイラにとっても、構文的に曖昧です。 不慣れなコード中で a<b,c>d; という式を見たときには、 この式がテンプレートなのかそうでないのかを判断するには、大量の .h ファイルの 中の宣言を探し回る羽目になります。 この曖昧さのせいで、プログラマ、コンパイラ制作者、そして言語標準規格の制定者の 労力がどれほど費やされていることでしょう。

もっと巧い方法があります。D言語では、! が二項演算子に使われていないことに 着目して、これを解決しました。 

a<b,c>

と書くかわりに、 

a!(b,c)

と書くことで、曖昧さを無くしています。これによって、構文解析は簡単になり、 意味のあるエラーメッセージを出すことも簡単になり、そして、そう、コードを読む人が この a はテンプレートなんだと判断するのも簡単になります。

テンプレート定義の構文

C++ では、大きく分けて二種類のテンプレート、クラステンプレートと関数テンプレート を定義できます。例え密接に関係がある場合でも、それぞれのテンプレートは 別々に記述されます。 

template<class T, class U> class Bar { ... };

template<class T, class U> T foo(T t, U u) { ... }

template<class T, class U> static T abc;

POD (C方式の Plain Old Data) 構造体には大抵、関連するデータの宣言が 伴いますし、クラスにも大抵、関連するデータや関数の宣言が伴います。 しかし、これらを同時にインスタンス化される論理的にまとまった テンプレートとして記述することはできませんでした。 Dでは、次のように書けます。 

template Foo(T, U)
{
  class Bar { ... }

  T foo(T t, U u) { ... }

  T abc;

  typedef T* Footype;	// 任意の宣言はテンプレート化可能
}

Foo がテンプレートの名前空間になっていて、 例えば次のようにアクセスできます。 

Foo!(int,char).Bar b;
Foo!(int,char).foo(1,2);
Foo!(int,char).abc = 3;

もちろんこれが少々面倒なこともありますから、その場合は、 特定のインスタンスに対しaliasを使うと記述が簡単です。 

alias Foo!(int,char) f;
f.Bar b;
f.foo(1,2);
f.abc = 3;

クラステンプレートについては、さらに簡単な構文も用意されています。 次のように宣言されたクラスは… 

class Abc
{
    int t;
    ...
}

パラメータリストを加えるだけで、テンプレートにできます。 

class Abc(T)
{
    T t;
    ...
}

テンプレートの宣言、定義、エクスポート

C++のテンプレートは、テンプレート宣言、テンプレート定義、 そしてexportテンプレート、の３種類の形式で書かれ得ます。 Dには、#includeによるテキスト貼り付けではない真のモジュールシステムがありますから、 Dではテンプレート定義のみが存在します。テンプレート宣言やexportテンプレートは もはや不要です。例えば、モジュール A でテンプレート定義が あったとします： 

module A;

template Foo(T)
{
    T bar;
}

これは別のモジュール B から次のようにアクセスできます。 

module B;

import A;

void test()
{
    A.Foo!(int).bar = 3;
}

アクセスの簡略化のためにaliasを使うのももちろん自由です。 

module B;

import A;
alias A.Foo!(int).bar bar;

void test()
{
    bar = 3;
}

テンプレート・パラメータ

C++でテンプレート・パラメータとして使えるもの：

Dでテンプレート・パラメータとして使えるもの：

いずれもデフォルト値を指定することができ、 型パラメータについては（ある種の）制約を加えることもできます。 

class B { ... }
interface I { ... }

class Foo(
  R,            // R はどんな型でもよい
  P:P*,         // P は必ずポインタ型
  T:int,        // T は必ずint型
  S:T*,         // S は必ずTへのポインタ型
  C:B,          // C はクラスBかその派生型
                  // 
  U:I,          // U はインターフェイスIを
                  // 実装したクラス型
  char[] string = "hello",
                // 文字列リテラル
                  // デフォルトは "hello"
  alias A = B   // A は任意の識別子
                  // (テンプレート識別子も含む),
                // デフォルトは B
  )
{
    ...
}

特殊化

部分特殊化や明示特殊化は、C++と同じように動作します。ただし、C++のような 'primary' テンプレートの概念はありません。インスタンス化の際には同名のテンプレート 全てが調べられ、引数がもっとも良くマッチしたものが インスタンス化されます。 

template Foo(T) ...
template Foo(T:T*) ...
template Foo(T, U:T) ...
template Foo(T, U) ...
template Foo(T, U:int) ...

Foo!(long)       // Foo(T) を選択
Foo!(long[])     // Foo(T) を選択。T は long[]
Foo!(int*)       // Foo(T*) を選択。T は int
Foo!(long,long)  // Foo(T, T) を選択
Foo!(long,short) // Foo(T, U) を選択
Foo!(long,int)   // Foo(T, U:int) を選択
Foo!(int,int)    // 曖昧 - Foo(T, U:T)
                 // と Foo(T, U:int)

二段階名前探索

C++ では、テンプレートの内部では通常と異なる名前探索規則が適用されます。 例えば、基底クラスの名前空間を見ないことや、スコープを切ったテンプレートパラメータ名の 再定義を許さないこと、テンプレート定義箇所より後ろで定義されたオーバーロードは 考慮しないこと、などがあります。（以下の例は C++98標準 から抜粋しました） 

int g(double d) { return 1; }

typedef double A;

template<class T> B
{
  typedef int A;
};

template<class T> struct X : B<T>
{
  A a;              // a はdouble型
  int T;            // エラー、T が再宣言された
  int foo()
  {  char T;        // エラー、T が再宣言された
     return g(1);   // 常に 1 を返す
  }
};

int g(int i) { return 2; }	// この定義はXからは見えない

Dでは、テンプレートを使わない場合と全く同じ規則が適用されます。 

int g(double d) { return 1; }

typedef double A;

class B(T)
{
  typedef int A;
}

class X(T) : B!(T)
{
  A a;             // a は int 型
  int T;           // ok, T を int に再宣言
  int foo()
  {   char T;      // ok, T を char に再宣言
     return g(1);  // 常に 2 を返す
  }
};

int g(int i) { return 2; }	// 関数は前方参照可能

テンプレートの再帰

テンプレートの再帰は特殊化と組み合わさることで、 C++テンプレートを一つの（いささか変わってはいますが）プログラミング言語としています。 階乗を計算するテンプレート群を考えてみましょう。 "hello world" プログラムのように、階乗計算は、 テンプレートメタプログラミングの標準的な例題です。 

template<int n> class factorial
{
  public:
    enum
    {
      result = n * factorial<n - 1>::result
    }; 
};

template<> class factorial<1>
{
  public:
    enum { result = 1 };
};

void test()
{
  // 24と表示
  printf("%d\n", factorial<4>::result);
}

Dでも再帰は同じように使えます。タイプ数も少なく済みます。 

template factorial(int n)
{
  const factorial = n * factorial!(n-1);
}

template factorial(int n : 1)
{
  const factorial = 1;
}

void test()
{
  writefln(factorial!(4));  // 24と表示
}

static if を使えば テンプレート一つで記述することも可能です。 

template factorial(int n)
{
  static if (n == 1)
    const factorial = 1;
  else
    const factorial = n * factorial!(n-1);
}

13行のコードが、ずっと簡潔な7行に収まりました。 static if は C++ の #if とほぼ同じ物です。 しかし、#if はテンプレート引数の値を知ることができないため、 テンプレートを使った条件分岐は全て 部分ないしは明示特殊化で記述しなければなりませんでした。 static if はこのような状況を 劇的に改善します。

D では、これは更に簡単になります。 上に載せたように階乗の値を生成するテンプレートを書くことも可能ですが、 コンパイル時に計算可能な関数を書いてしまうのがもっと簡単です:

int factorial(int n)
{
  if (n == 1)
    return 1;
  else
    return n * factorial(n - 1);
}

static int x = factorial(5);  // x は 120 にコンパイル時に初期化される

SFINAE (Substitution Failure Is Not An Error)

以下の例は、テンプレート引数型が関数型かどうかを判定しています。 Vandevoorde & Josuttis の "C++ Templates: The Complete Guide", 353ページ からの引用です。 

template<U> class IsFunctionT
{
  private:
    typedef char One;
    typedef struct { char a[2]; } Two;
    template static One test(...);
    template static Two test(U (*)[1]);
  public:
    enum {
      Yes = sizeof(IsFunctionT::test(0)) == 1
    };
};

void test()
{
  typedef int (fp)(int);

  assert(IsFunctionT<fp>::Yes == 1);
}

IsFunctionT テンプレートは、二つの副作用によってその機能が実現されて います。一つめは、関数の配列というのがC++では不正な型であることです。 このため、U が関数型だった場合、二番目の test を選択すると エラーになるため(SFINAE (Substitution Failure Is Not An Error))こちらは選ばれず、一つめの test が選択されます。U が関数型ではなかった場合、二番目の test が...よりも適合度の高い マッチになります。次に、どちらの test が選択されたかが、返値の サイズ…つまり sizeof(One) か sizeof(Two) かによって判定されます。 残念なことにC++でのテンプレートメタプログラミングは、直接表現したいことを 記述するコードではなく、副作用に頼ったコードになってしまいがちです。

Dでは次のように書けます。 

template IsFunctionT(T)
{
  static if ( is(T[]) )
    const int IsFunctionT = 0;
  else
    const int IsFunctionT = 1;
}

void test()
{
  alias int fp(int);

  assert(IsFunctionT!(fp) == 1);
}

is(T[]) は SFINAE (Substitution Failure Is Not An Error) と同じ効果を持ちます。T の配列型を作ろうとしますが、 T が関数型の場合、これは関数の配列です。これはDでも 不正な型であるため、T[] は失敗して is(T[]) はfalseを返します。

このように SFINAE (Substitution Failure Is Not An Error) を用いることもできますが、is式はもっと直接的に型を調べることが 可能です。型についての条件を書くのにテンプレートを使う必要すらありません。 

void test()
{
  alias int fp(int);

  assert( is(fp == function) );
}

浮動小数点数を使ったテンプレートメタプログラミング

ここからは、C++のテンプレートでは現実的に実装するのが難しい例に移りましょう。 例えば、実数 x の平方根を Babylonian method で計算するテンプレートです。 

import std.stdio;

template sqrt(real x, real root = x/2, int ntries = 0)
{
  static if (ntries == 5)
    // 繰り返しのたびに精度は倍になる。
    // 5回で十分
    const sqrt = root;
  else static if (root * root - x == 0)
    const sqrt = root;  // ちょうどぴったり
  else
    // 再度繰り返し
    const sqrt = sqrt!(x, (root+x/root)/2, ntries+1);
}

void main()
{
    real x = sqrt!(2);
    writefln("%.20g", x); // 1.4142135623730950487
}

平方根リテラルは、例えばガンマ関数などの、他の実行時の浮動小数点演算の 高速化のために必要となることがあります。 これらのテンプレート浮動小数点アルゴリズムはコンパイル時に完了するため、 それほど効率的である必要はなく、ただ正確であることが求められます。

もっと複雑なテンプレートを構築することも可能で、例えば Don Clugston は コンパイル時に円周率 π を計算するテンプレートを書いています。[2]

これも、 コンパイル時に実行される関数として記述することができます:

real sqrt(real x)
{
    real root = x / 2;
    for (int ntries = 0; ntries < 5; ntries++)
    {
	if (root * root - x == 0)
	    break;
	root = (root + x / root) / 2;
    }
    return root;
}
static y = sqrt(10);   // y はコンパイル時に 3.16228 へと初期化される

文字列を使ったテンプレートメタプログラミング

文字列を使うと、もっと面白いことができます。次の例は、 コンパイル時に整数を文字列に変換します。 

template decimalDigit(int n)	// [3]
{
  const char[] decimalDigit = "0123456789"[n..n+1];
} 

template itoa(long n)
{   
  static if (n < 0)
     const char[] itoa = "-" ~ itoa!(-n);  
  else static if (n < 10)
     const char[] itoa = decimalDigit!(n); 
  else
     const char[] itoa = itoa!(n/10L) ~ decimalDigit!(n%10L); 
}

char[] foo()
{
  return itoa!(264);   // "264"を返す
}

以下のテンプレートは文字列リテラルのハッシュ値を計算します。 

template hash(char [] s, uint sofar=0)
{
   static if (s.length == 0)
      const hash = sofar;
   else
      const hash = hash!(s[1 .. length], sofar * 11 + s[0]);
}

uint foo()
{
    return hash!("hello world");
}

正規表現コンパイラ

Dのテンプレートはもっとずっと有意義なもの をどんな風に扱うのでしょう。例えばC++では、Eric Niebler が、 Expression Template を用いて正規表現コンパイラを実装しています [4]。 Expression Template を使うことの問題点は、C++の演算子の構文と優先順位しか 使えなくなることです。 このため、Expression Template を使った正規表現はあまり正規表現には見えず、 要するに"C++表現"にしか見えません。 Eric Anderton は、文字列を構文解析できるというテンプレートの能力を活かして Dでこれを実装しました [5]。 これはつまり、パターン文字列の中で、普通に使われている正規表現の文法と 演算子を使えると言うことです。

この正規表現コンパイラテンプレートは、文字列引数を構文解析して トークンを先頭から一つずつ切り出しつつ、 それぞれのトークンに対応する正規表現マッチを行う カスタム関数を生成し、 それらを最終的に一つにまとめて 正規表現全体を表す関数を作り上げます。 正規表現の文法エラーに対しては、 意味のあるエラーメッセージをきちんと表示することができます。

生成された関数に文字列を渡すと、 マッチした部分文字列の配列が返されます。 

import std.stdio;
import regex;

void main()
{
    auto exp = &regexMatch!(r"[a-z]*\s*\w*");
    writefln("matches: %s", exp("hello    world"));
}

以下に、Eric Anderton の正規表現コンパイラの簡略化版を掲載します。 上の例の正規表現がどのようにコンパイルされるかを見て取るのに 必要な部分の抜粋となっています。 

module regex;

const int testFail = -1;

/**
 * pattern[] をコンパイルして、このパターン用の関数をカスタム生成します。
 * 生成された関数は文字列 str[] を受け取って正規表現を適用し、
 * マッチした部分の配列を返します。
 */

template regexMatch(char[] pattern)
{
  char[][] regexMatch(char[] str)
  {
    char[][] results;
    int n = regexCompile!(pattern).fn(str);
    if (n != testFail && n > 0)
      results ~= str[0..n];
    return results;
  }
}

/******************************
 * testXxxx() 関数はテンプレートによってカスタム生成されるもので、
 * 正規表現の要素それぞれに対応しています。
 *
 * Params:
 *	char[] str	マッチ対象の入力文字列
 *
 * Returns:
 *	testFail	マッチ失敗
 *	n >= 0		n文字マッチ
 */

/// 常にマッチ
template testEmpty()
{
  int testEmpty(char[] str) { return 0; }
}

/// testFirst(str) とそれに続けて testSecond(str) がマッチすればマッチ
template testUnion(alias testFirst, alias testSecond)
{
  int testUnion(char[] str)
  {
    int n1 = testFirst(str);
    if (n1 != testFail)
    {
      int n2 = testSecond(str[n1 .. $]);
      if (n2 != testFail)
        return n1 + n2;
    }
    return testFail;
  }
}

/// str[] の先頭が text[] ならばマッチ
template testText(char[] text)
{
  int testText(char[] str)
  {
    if (str.length &&
        text.length <= str.length &&
        str[0..text.length] == text
       )
      return text.length;
    return testFail;
  }
}

/// testPredicate(str) が0回以上マッチすればマッチ
template testZeroOrMore(alias testPredicate)
{
  int testZeroOrMore(char[] str)
  {
    if (str.length == 0)
      return 0;
    int n = testPredicate(str);
    if (n != testFail)
    {
      int n2 = testZeroOrMore!(testPredicate)(str[n .. $]);
      if (n2 != testFail)
        return n + n2;
      return n;
    }
    return 0;
  }
}

/// term1[0] <= str[0] <= term2[0] ならマッチ
template testRange(char[] term1, char[] term2)
{
  int testRange(char[] str)
  {
    if (str.length && str[0] >= term1[0]
                   && str[0] <= term2[0])
      return 1;
    return testFail;
  }
}

/// ch[0]==str[0] ならマッチ
template testChar(char[] ch)
{
  int testChar(char[] str)
  {
    if (str.length && str[0] == ch[0])
      return 1;
    return testFail;
  }
}

/// str[0] が単語文字ならマッチ
template testWordChar()
{
  int testWordChar(char[] str)
  {
    if (str.length &&
        (
         (str[0] >= 'a' && str[0] <= 'z') ||
         (str[0] >= 'A' && str[0] <= 'Z') ||
         (str[0] >= '0' && str[0] <= '9') ||
         str[0] == '_'
        )
       )
    {
      return 1;
    }
    return testFail;
  }
}

/*****************************************************/

/**
 * pattern[] の先頭から
 * 終端か特殊文字までを切り出し
 */

template parseTextToken(char[] pattern)
{
  static if (pattern.length > 0)
  {
    static if (isSpecial!(pattern))
      const char[] parseTextToken = "";
    else
      const char[] parseTextToken =
           pattern[0..1] ~ parseTextToken!(pattern[1..$]);
  }	
  else
    const char[] parseTextToken="";
}

/**
 * terminatorを含めてそこまでを pattern[] から切り出し
 * Returns:
 *	token[]	 	terminatorの直前までの文字列
 *	consumed	pattern[] から切り出された文字数
 */
template parseUntil(char[] pattern,char terminator,bool fuzzy=false)
{
  static if (pattern.length > 0)
  {
    static if (pattern[0] == '\\')
    {
      static if (pattern.length > 1)
      {
        const char[] nextSlice = pattern[2 .. $];
        alias parseUntil!(nextSlice,terminator,fuzzy) next;
        const char[] token = pattern[0 .. 2] ~ next.token;
        const uint consumed = next.consumed+2;
      }
      else
      {
        pragma(msg,"Error: expected character to follow \\");
        static assert(false);
      }
    }
    else static if (pattern[0] == terminator)
    {
      const char[] token="";
      const uint consumed = 1;
    }
    else
    {
      const char[] nextSlice = pattern[1 .. $];
      alias parseUntil!(nextSlice,terminator,fuzzy) next;
      const char[] token = pattern[0..1] ~ next.token;
      const uint consumed = next.consumed+1;
    }
  }
  else static if (fuzzy)
  {
    const char[] token = "";
    const uint consumed = 0;
  }
  else
  {
    pragma(msg,"Error: expected " ~
               terminator ~
               " to terminate group expression");
    static assert(false);
  }			
}

/**
 * 文字クラスの内容を構文解析
 * Params:
 *   pattern[] = コンパイルしたい残りのパターン
 * Output:
 *   fn       = 生成される関数
 *   consumed = pattern[] から切り出された文字数
 */

template regexCompileCharClass2(char[] pattern)
{
  static if (pattern.length > 0)
  {
    static if (pattern.length > 1)
    {
      static if (pattern[1] == '-')
      {
        static if (pattern.length > 2)
        {
          alias testRange!(pattern[0..1], pattern[2..3]) termFn;
          const uint thisConsumed = 3;
          const char[] remaining = pattern[3 .. $];
        }
        else // 長さは 2
        {
          pragma(msg,
            "Error: expected char following '-' in char class");
          static assert(false);	
        }
      }
      else // '-' ではない
      {
        alias testChar!(pattern[0..1]) termFn;
        const uint thisConsumed = 1;
        const char[] remaining = pattern[1 .. $];
      }
    }
    else
    {
      alias testChar!(pattern[0..1]) termFn;
      const uint thisConsumed = 1;
      const char[] remaining = pattern[1 .. $];
    }
    alias regexCompileCharClassRecurse!(termFn,remaining) recurse;
    alias recurse.fn fn;
    const uint consumed = recurse.consumed + thisConsumed;
  }
  else
  {
    alias testEmpty!() fn;
    const uint consumed = 0;
  }
}

/**
 * 文字クラスを再帰的に構文解析
 * Params:
 *  termFn = ここまでに生成された関数
 *  pattern[] = コンパイルしたい残りのパターン
 * Output:
 *  fn = termFn と今回解析した文字クラスをあわせて
 *       生成された関数
 *  consumed = pattern[] から切り出された文字数
 */

template regexCompileCharClassRecurse(alias termFn,char[] pattern)
{
  static if (pattern.length > 0 && pattern[0] != ']')
  {
    alias regexCompileCharClass2!(pattern) next;
    alias testOr!(termFn,next.fn,pattern) fn;
    const uint consumed = next.consumed;
  }
  else
  {
    alias termFn fn;
    const uint consumed = 0;
  }
}

/**
 * 文字クラスの先頭。コンパイルする
 * Params:
 *  pattern[] = コンパイルしたいパターンの残り
 * Output:
 *  fn = 生成された関数
 *  consumed = pattern[] から切り出された文字数
 */

template regexCompileCharClass(char[] pattern)
{	
  static if (pattern.length > 0)
  {
    static if (pattern[0] == ']')
    {
      alias testEmpty!() fn;
      const uint consumed = 0;
    }
    else
    {
      alias regexCompileCharClass2!(pattern) charClass;
      alias charClass.fn fn;
      const uint consumed = charClass.consumed;
    }
  }
  else
  {
    pragma(msg,"Error: expected closing ']' for character class");
    static assert(false);	
  }
}

/**
 * 接尾辞 '*' を探して切り出し
 * Params:
 *  test = ここまでにコンパイルされた正規表現の関数
 *  pattern[] = コンパイルしたいパターンの残り
 * Output:
 *  fn = 生成された関数
 *  consumed = pattern[] から切り出された文字数
 */

template regexCompilePredicate(alias test, char[] pattern)
{
  static if (pattern.length > 0 && pattern[0] == '*')
  {
    alias testZeroOrMore!(test) fn;
    const uint consumed = 1;
  }
  else
  {
    alias test fn;
    const uint consumed = 0;
  }
}

/**
 * Parse escape sequence.
 * Params:
 *  pattern[] = コンパイルしたいパターンの残り
 * Output:
 *  fn = 生成された関数
 *  consumed = pattern[] から切り出された文字数
 */

template regexCompileEscape(char[] pattern)
{
  static if (pattern.length > 0)
  {
    static if (pattern[0] == 's')
    {
      // 空白文字
      alias testRange!("\x00","\x20") fn;
    }
    else static if (pattern[0] == 'w')
    {
      // 単語文字
      alias testWordChar!() fn;
    }
    else
    {
      alias testChar!(pattern[0 .. 1]) fn;
    }
    const uint consumed = 1;
  }
  else
  {
    pragma(msg,"Error: expected char following '\\'");
    static assert(false);
  }
}

/**
 * pattern[] で表されたパターンをコンパイル
 * Params:
 *  pattern[] = コンパイルしたいパターンの残り
 * Output:
 *  fn = 生成された関数
 */

template regexCompile(char[] pattern)
{
  static if (pattern.length > 0)
  {
    static if (pattern[0] == '[')
    {
      const char[] charClassToken =
          parseUntil!(pattern[1 .. $],']').token;
      alias regexCompileCharClass!(charClassToken) charClass;
      const char[] token = pattern[0 .. charClass.consumed+2];
      const char[] next = pattern[charClass.consumed+2 .. $];
      alias charClass.fn test;
    }
    else static if (pattern[0] == '\\')
    {
      alias regexCompileEscape!(pattern[1..pattern.length]) escapeSequence;
      const char[] token = pattern[0 .. escapeSequence.consumed+1];
      const char[] next =
          pattern[escapeSequence.consumed+1 .. $];
      alias escapeSequence.fn test;
    }
    else
    {
      const char[] token = parseTextToken!(pattern);
      static assert(token.length > 0);
      const char[] next = pattern[token.length .. $];
      alias testText!(token) test;
    }
    
    alias regexCompilePredicate!(test, next) term;
    const char[] remaining = next[term.consumed .. next.length];
    
    alias regexCompileRecurse!(term,remaining).fn fn;
  }
  else
    alias testEmpty!() fn;
}

template regexCompileRecurse(alias term,char[] pattern)
{
  static if (pattern.length > 0)
  {
    alias regexCompile!(pattern) next;
    alias testUnion!(term.fn, next.fn) fn;
  }
  else
    alias term.fn fn;
}

/// 構文解析のためのユーティリティ関数
template isSpecial(char[] pattern)
{
  static if (
    pattern[0] == '*' ||
    pattern[0] == '+' ||
    pattern[0] == '?' ||
    pattern[0] == '.' ||
    pattern[0] == '[' ||
    pattern[0] == '{' ||
    pattern[0] == '(' ||
    pattern[0] == ')' ||
    pattern[0] == '$' ||
    pattern[0] == '^' ||
    pattern[0] == '\\'
  )
    const isSpecial = true;
  else
    const isSpecial = false;
}

さらにテンプレートメタプログラミング

  1. Tomasz Stachowiak の、コンパイル時 レイトレーシング
  2. Don Clugston の、コンパイル時 99 Bottles of Beer.

参考文献

[1] プログラミング言語 D, http://www.digitalmars.com/d/

[2] Don Clugston, 円周率計算機, http://trac.dsource.org/projects/ddl/browser/trunk/meta/demo/calcpi.d

[3] Don Clugston, decimaldigit と itoa, http://trac.dsource.org/projects/ddl/browser/trunk/meta/conv.d

[4] Eric Niebler, 正規表現テンプレートライブラリ "Boost.Xpressive", http://boost-sandbox.sourceforge.net/libs/xpressive/doc/html/index.html

[5] Eric Anderton, D言語向け正規表現テンプレートライブラリ, http://trac.dsource.org/projects/ddl/browser/trunk/meta/regex.d

謝辞

Don Clugston, Eric Anderton, Matthew Wilson の助言、助力に心から感謝します。