D言語で，(ゴリゴリの)コンパイル時メタプログラミングでADTを実現した話

最近，OCamlでプログラミングすることが多く，久しぶりにDでプログラミングをすると， やっぱりD言語にはどう考えても，ADT(代数的データ型)とパターンマッチが必要だと痛感した．
そこで，D言語でコンパイル時メタプログラミングを駆使し，ADTをD言語でもそれっぽく持ってくることに 成功した．
簡単に概要を書くと，

1. OCamlに似たSyntaxのADT用の構文を定義する．
2. それをコンパイル時にパースしASTを構築する．
3. ASTを元にDのコードを生成する．
4. 生成されたDのコードを文字列mixinすると，生成したADTを使うことができるようになる．

という感じである．とりあえず，リポジトリはこれ: https://github.com/alphaKAI/dadt

それでは，続きから具体的な話をしていく．

注: もともと2018/08/03に書く予定だったBlogを途中で書くのを中断していて，だいぶ日付が立ってしまった今日(2018/08/29)思い立って続きを書いたので最近やっていること(自作処理系の開発．これもBlogを書く予定)からはそれてしまうが，もったいないので書き上げて公開することにした．また，レポートに同じ内容を書いたので，そこから盛ってきている文章も多い．そのため，途中から文体が変わってしまっているかも知れない...

概要

Dには高機能な言語機能がたくさんあり，その中でもメタプログラミングするときには次の機能が生きてくる．

1. シンプルで強力なテンプレート
2. CTFE(Compile Time Function Execution)というコンパイル時に関数を実行できる機能
3. 文字列mixin，コンパイル時に求まるような文字列リテラルに正しいDのコードが入っていれば，それをその場に展開し，そのままコンパイルできる機能(動的な言語のevalにちかい)

なかでも，CTFEは本当に強力であり，今回のキモである．(というかCTFEが本当に強すぎる)

とりあえず，Dの紹介もいいが，本題に入っていく．
えーっと，代数的データ型の説明もしたほうがいいかも知れないけど，ちょっとそれはまた気が向いたら．．．(説明が長くなるし難しいので)
とりあえず，DにADTを持ってきたいとして，僕はOCamlが好きなのでOCamlのようにADTを使いたいと考えた．
そこで，まず説明のために，OCamlでoption(まあ，Maybeみたいなもん)という代数的データ型を考える．
コードとしては，次のようなものである．

type 'a option
  | Some of 'a
  | None

'a option型('aは型引数)は，SomeとNoneという2つのコンストラクタをとり，(例えば関数の実行結果が)正常な場合はSome 1のように値を，失敗した場合にNoneを返すことで， 例外を使わずに，失敗を表すことができる．
少し違うかもだけど，イメージ的には，ある関数の返り値があるクラスとなっているとして，その関数の実行結果がnullなら，失敗，具体的なインスタンスが入っていれば成功というような感覚である．しかし，それだと，null参照をうっかりしてしまったりとしんどいことになったりする．

とりあえず，これをD言語で実現するための基本的なアイディアとしては次のようなコードになる．

// 'a optionのをDで表した．Tはテンプレート引数ということで，これが型引数．
interface Option(T) {}

// Option!Tを継承した，Some(T)というクラスを定義する．これがOCamlのSome of 'aに対応する．
// Option!Tを継承しているので，Some!TはOption!Tとして扱える．
class Some(T) : Option!T {
  T value; // 値を保持するフィールド
  // 値をセットするコンストラクタ
  this (T value) {
    this.value = value;
  }
}

// Option!Tを継承した，None(T)というクラスを定義し，これがNoneに対応する．
// Some!Tと同様に，None!TはOption!Tとして扱える．
class None(T) : Option!T {
  // 値を保持しないので，フィールドもコンストラクタも空でok
  this () {}
}

基本となるアイディアはこの様になって，次のように使える．(例が適当なのはいい例が思いつかなかったので...)

// ある数Nが偶数であれば，NをSome!intでくるんで返し，奇数のときはNone!intを返す
Option!int is_even(int n) {
  if (n % 2 == 0) {
    return new Some!int(n);
  } else {
    return new None!int;
  }
}

void main() {
  Option!int ret1 = is_even(2);
  Option!int ret2 = is_even(3);

  // ret1をSome!intにキャストしてnullでなければ，ret1の中身はSome!int
  if ((cast(Some!int)ret1) !is null) {
    Some!int x = cast(Some!int)ret1;
    int val = x.value;
    writeln(val, " is even number!");
  } else {
    writeln("ret1 is None");
  }

  // 同様にret2について調べる
  if ((cast(Some!int)ret2) !is null) {
    Some!int x = cast(Some!int)ret2;
    int val = x.value;
    writeln(val, " is even number!");
  } else {
    writeln("ret2 is None");
  }
}

こんな感じに使える．(これでは全然良さ味が見られないし，キャストして判定とかダサいけど，まあまあ，それはちゃんと解決しますんでね，ちょっとまってね，)

とりあえず，説明すると，interface Option(T)が，ADTの型に対応して，それぞれのインスタンスSome of 'aをclass Some(T) : Option!Tで，Noneをclass None(T) : Option!Tに対応する．
ただ，やっぱりこのままでは何がいいよくわからない．そもそもこれはパターンマッチがあってこそ，真価を発揮する． 例えば，次のように書けたらとても便利である．

ret1.matchWithOption!(void, int,
  (Some!int _) => (int x) => writeln("ret1 is even number! and x is ", x),
  (None!int _) => writeln("ret1 is None"));

ret2.matchWithOption!(void, int,
  (Some!int _) => (int x) => writeln("ret2 is even number! and x is ", x),
  (None!int _) => writeln("ret2 is None"));

で，これは次のようなコードで実現できる．

_RETURN_TYPE_OF_MATCH_WITH_Option matchWithOption(_RETURN_TYPE_OF_MATCH_WITH_Option, T, choices...)(Option!(T) arg) {
  import std.traits;

  _RETURN_TYPE_OF_MATCH_WITH_Option delegate() otherwise = null;

  foreach (choice; choices) {
    alias params = Parameters!choice;
    static if (params.length < 1) {
      otherwise = () => choice();
    }

    if (cast(params[0])(arg) !is null) {
      static if (is(Some!(T) == params[0])) {
        Some!(T) x = cast(Some!(T))arg;

        static if (is(ReturnType!(choice) == _RETURN_TYPE_OF_MATCH_WITH_Option)) {
          static if (is(_RETURN_TYPE_OF_MATCH_WITH_Option == void)) {
            choice(x);
          } else {
            return choice(x);
          }
        } else {
          static if (isCallable!(ReturnType!(choice))) {
            return cast(_RETURN_TYPE_OF_MATCH_WITH_Option)choice(x)(x._0);
          } else {
            return cast(_RETURN_TYPE_OF_MATCH_WITH_Option)choice(x);
          }
        }
      }

      static if (is(None!(T) == params[0])) {
        None!(T) x = cast(None!(T))arg;

        static if (is(ReturnType!(choice) == _RETURN_TYPE_OF_MATCH_WITH_Option)) {
          static if (is(_RETURN_TYPE_OF_MATCH_WITH_Option == void)) {
            choice(x);
          } else {
            return choice(x);
          }
        } else {
          static if (isCallable!(ReturnType!(choice))) {
            return cast(_RETURN_TYPE_OF_MATCH_WITH_Option)choice(x)();
          } else {
            return cast(_RETURN_TYPE_OF_MATCH_WITH_Option)choice(x);
          }
        }
      }

    }
  }

  if (otherwise !is null) {
    static if (is(_RETURN_TYPE_OF_MATCH_WITH_Option == void)) {
      otherwise();
      return;
    } else {
      return otherwise();
    }
  }

  static if (!is(_RETURN_TYPE_OF_MATCH_WITH_Option == void)) {
    return null;
  }
}

詳しい説明は端折るが，これで簡易的なパターンマッチが実現できる．(静的にパターンを解析している)

とりあえず，これをコンパイル時に生成できれば，D言語でADTを実現できる．

ADTの構文を決め，コンパイル時にパースする．

ということで，コンパイル時に，生成するにあたって，ADTを表す構文を決め，そこからコードを生成する．
そこで，OCamlのADTの構文を真似，次のような構文とした．

type Option(T) =
  | Some of T
  | None

このように書く．もちろん，型引数として書いてあるTは複数書くことができ，その場合はカンマ区切りでSomeType(T, U, R)のように書く．
また，ネストすることも可能で，次のようにツリー構造を書くこともできる．

type BinaryTree(T) =
  | Node of BinaryTree!(T) * BinaryTree!(T)
  | Leaf of T

また，コンストラクタにはうえのBinaryTreeのNodeのところで書いたが，複数の値をもたせたいときは，その型を*で区切って書けば良い．

さて，このように構文を定めたので，あとはコンパイル時に動く字句解析器や構文解析器を書けばよい． ところが，D言語にはとても便利なライブラリがあり，PEG文字列を解釈し，そこからパーサーを生成してくれるpeggedという ライブラリがある．これはコンパイル時にも動き，とても使いやすい．したがってこれを使うことで，簡単にコンパイル時に構文解析をすることができる．

そして，peggedの提供するExtended PEG Syntaxを用いて次のように構文を定義する．

DADT:
  TypeDeclare < "type" BaseConstructor "=" ConstructorList Deriving?

  BaseConstructor < TypeNameWithArgs / TypeNameWithoutArgs

  TypeName <~ !Keyword [A-Z_] [a-zA-Z0-9_]*

  Field < FieldOfArray / FieldWithArgs / FieldName
  FieldArgs < "()" / :"(" Field ("," Field)* :")"
  FieldWithArgs < FieldName "!" FieldArgs
  FieldOfArray < (FieldWithArgs / FieldName) ArrayBracket+
  FieldName <~ !Keyword [a-zA-Z_] [a-zA-Z0-9_]*

  ArrayBracket < UnsizedBracket / SizedBracket

  UnsizedBracket < "[]"
  SizedBracket < "[" ArraySize "]"
  ArraySize <~ [a-zA-Z0-9_]*

  TypeNameWithoutArgs < TypeName
  TypeNameWithArgs < TypeName ParameterList
  ParameterList < "()" / :"(" TypeName ("," TypeName)* :")"

  ConstructorWithField < "|" TypeName "of" Field ("*" Field)*
  Constructor <  "|" TypeName
  ConstructorDeclare < ConstructorWithField / Constructor
  ConstructorList < ConstructorDeclare+

  Deriving < "[@@deriving" DerivingArgs "]"
  DerivingArgs < DerivingArg ("," DerivingArg)*
  DerivingArg <~ !Keyword [a-zA-Z_] [a-zA-Z0-9_]*

  Keyword <~ "of"
  Integer <~ digit+

配列も定義可能だが(可変長配列と固定長配列のみ)，定義が複雑になってしまうため，まだ，多次元配列や連想配列はサポートしていない． また，フィールドと呼ぶのは不適切かもしれないが，コンストラクタの小要素として存在する値の型をここではフィールドとよんでいる．

また，このPEGをみて，勘の鋭い方は気がついたかも知れないが，OCamlのppx_derivingのように，ADTの定義のあとに[@@deriving <引数>]として引数にshow，ord，eqを渡すとそれぞれ，表示用の関数，比較関数，同値比較関数を自動生成できるようにしている．

これをpeggedのpegged.grammarという関数に食わせることで，DADTという名前のパーサーをコンパイル時に生成できる．

mixin(grammar(`ここに先程のPEG文字列を入れる`));

これで，パーサーの準備はできた．

peggedが生成したパーサーは，パースした後に，ParseTreeという型を返し，パース結果がツリー構造になっている． あとはそれを再帰的にvisitして，ASTを構築すれば良い．
ここからはpeggedの生成したDADTという関数を用いてパースし，ASTを表すクラスを定義し，そのインスタンスをそのノードごとに作っていくだけなので詳細はコードを参照してほしい．(クラスの定義や，AST構築の部分だけで400行を超えるので): parser.d
驚くことに，D言語ではここまでの処理を，コンパイル時に行うことができる．

とはいっても，少しだけ，ASTの生成について説明しておいたほうが親切だと思うので簡潔に説明を行う．
基本的に先程のPEGの左側に出てきた規則名のクラスを作る．そのときに全てのASTのノードのクラスを統一的に扱いたいので，ASTElementというinterfaceを作り そのインスタンスとして，クラスを作る．
参考までにごくごく一部を抜粋する．

interface ASTElement {
}

class BaseConstructor : ASTElement {
  TypeName baseName;
  ParameterList parameterList;

  this(TypeName baseName) {
    this.baseName = baseName;
    this.parameterList = new ParameterList([]);
  }

  this(TypeName baseName, ParameterList parameterList) {
    this.baseName = baseName;
    this.parameterList = parameterList;
  }
}

class TypeName : ASTElement {
  string name;

  this(string name) {
    this.name = name;
  }
}

このようにして，ノードに対応するクラスを作ればよい．
また，DADTに文字列を渡すと，パース結果をParseTreeというクラスのインスタンスとして得ることができるので，そこから先程のASTElementを生成することでASTの構築ができる． 以下にコードを抜粋する．

ASTElement buildAST(ParseTree p) {
  /*
  if (!__ctfe) {
    writeln("p.name : ", p.name);
  }
  */

  final switch (p.name) {
  case "DADT":
    auto e = p.children[0];
    return buildAST(e);
  case "DADT.BaseConstructor":
    auto e = p.children[0];
    return buildAST(e);
  case "DADT.TypeDeclare":
    BaseConstructor baseConstructor = cast(BaseConstructor)buildAST(p.children[0]);

    if (baseConstructor is null) {
      throw new Error("Error in %s!".format(p.name));
    }

    ConstructorList constructorList = cast(ConstructorList)buildAST(p.children[1]);

    if (constructorList is null) {
      throw new Error("Error in %s!".format(p.name));
    }

    if (p.children.length == 2) {
      return new TypeDeclare(baseConstructor, constructorList);
    } else {
      Deriving deriving = cast(Deriving)buildAST(p.children[2]);

      if (deriving is null) {
        throw new Error("Error in %s!".format(p.name));
      }

      return new TypeDeclare(baseConstructor, constructorList, deriving);
    }
  case "DADT.TypeName":
    string typeName = p.matches[0];
    return new TypeName(typeName);
//このように，以下にDADT.<規則名>という感じで，PEGの左側に出てきた規則名について網羅的にcaseを定義する

このようにしてASTの生成ができる．
PEGで文法の定義，ASTのクラスの定義，ASTの構築用コードまでで450行程度である．

さて，ASTの生成ができたので，コード生成．

ということで，ASTの生成ができたのでそこからDのコードを生成する．

先程基本的なアイディアとして示した，Option(T)の表現だが，先程の表現では，少しばかり物足りないので，実際には次のようなコードを生成させる．

enum OptionType {
  Some,
  None
}

interface Option(T) {
  OptionType type();
}

class Some(T) : Option!(T) {
  T _0;

  this(T _0) {
    this._0 = _0;
  }

  OptionType type() {
    return OptionType.Some;
  }
}
// new Some!T(_0)と毎回書くのは大変なのでsome(_0)と書くことでクラスの生成ができるヘルパ関数
Some!(T) some(T)(T _0) {
  return new Some!(T)(_0);
}

class None(T) : Option!(T) {


  this() {

  }

  OptionType type() {
    return OptionType.None;
  }
}
// これもヘルパ関数
None!(T) none(T)() {
  return new None!(T)();
}

このような表現を生成する．

また，代数的データ型は，パターンマッチと合わさることで真価を発揮する．つまり，次のように書けると便利である．

// ある数Nが偶数であれば，NをSome!intでくるんで返し，奇数のときはNone!intを返す
Option!int is_even(int n) {
  if (n % 2 == 0) {
    return new Some!int(n);
  } else {
    return new None!int;
  }
}

void main() {
  Option!int ret1 = is_even(2);
  Option!int ret2 = is_even(3);

  // ret1がSomeの場合はret1 is even number!と出力し，中身の数を出力する．
  // ret1がNoneの場合は，ret1 is Noneと出力する．
  ret1.matchWithOption!(void, int,
    (Some!int _) => (int x) => writeln("ret1 is even number! and x is ", x),
    (None!int _) => writeln("ret1 is None"));
  // re1のときと同様．
  ret2.matchWithOption!(void, int,
    (Some!int _) => (int x) => writeln("ret2 is even number! and x is ", x),
    (None!int _) => writeln("ret2 is None"));
}

したがって，デフォルトでは，先程のinterfaceとそれを継承したclassの表現に加えて，パターンマッチを行う関数を生成するべきであると考え， 次のような関数を生成する．

_RETURN_TYPE_OF_MATCH_WITH_Option matchWithOption(
    _RETURN_TYPE_OF_MATCH_WITH_Option,
    T,
    choices...)(Option!(T) arg) {
  import std.traits;

  _RETURN_TYPE_OF_MATCH_WITH_Option delegate() otherwise = null;

  foreach (choice; choices) {
    alias params = Parameters!choice;
    static if (params.length < 1) {
      otherwise = () => choice();
    }

    if (cast(params[0])(arg) !is null) {
      static if (is(Some!(T) == params[0])) {
        Some!(T) x = cast(Some!(T))arg;

        static if (is(ReturnType!(choice) == _RETURN_TYPE_OF_MATCH_WITH_Option)) {
          static if (is(_RETURN_TYPE_OF_MATCH_WITH_Option == void)) {
            choice(x);
          } else {
            return choice(x);
          }
        } else {
          static if (isCallable!(ReturnType!(choice))) {
            return cast(_RETURN_TYPE_OF_MATCH_WITH_Option)choice(x)(x._0);
          } else {
            return cast(_RETURN_TYPE_OF_MATCH_WITH_Option)choice(x);
          }
        }
      }

      static if (is(None!(T) == params[0])) {
        None!(T) x = cast(None!(T))arg;

        static if (is(ReturnType!(choice) == _RETURN_TYPE_OF_MATCH_WITH_Option)) {
          static if (is(_RETURN_TYPE_OF_MATCH_WITH_Option == void)) {
            choice(x);
          } else {
            return choice(x);
          }
        } else {
          static if (isCallable!(ReturnType!(choice))) {
            return cast(_RETURN_TYPE_OF_MATCH_WITH_Option)choice(x)();
          } else {
            return cast(_RETURN_TYPE_OF_MATCH_WITH_Option)choice(x);
          }
        }
      }

    }
  }

  if (otherwise !is null) {
    static if (is(_RETURN_TYPE_OF_MATCH_WITH_Option == void)) {
      otherwise();
      return;
    } else {
      return otherwise();
    }
  }

  static if (!is(_RETURN_TYPE_OF_MATCH_WITH_Option == void)) {
    return null;
  }
}

また，さらなる利便性のために，OCamlのppx_derivingのように，ADTの定義のあとに[@@deriving <引数>]として引数にshow，ord，eqを渡すことで，それぞれ自動的に 型名をTypeNameとして，show_TypeNameという表示用の関数(整形された文字列表現を返す関数)，compare_TypeNameという比較用の関数．equal_TypeNameという同値判定用の関数の自動生成も導入した．

そして，コード生成だが，その生成するコードをここに張ってしまうと，またそれも400行程度あるのでとても大きなスペースを要してしまうので，簡単な説明に留める．
先程構築したASTを用いて，そのクラスのフィールドを元にコードを生成するという流れである．

基本的に今までに貼ったようなコードの具体的なクラス名などを適切に置換することでテンプレートから生成するような感じである．

そこで，例えばクラスを文字列から作る場合，

import std.format;

string class_name = "Klass";

mixin(`
class %s {
}
`.format(class_name));

などのようにstd.format.formatを使うことなどが考えられるが，これをしてしまうと，あるフォーマット指定子が一体何の変数に展開されるかがわかりにくくなってしまう．そこで，次のような簡易的なブレース展開を行う関数を作ると便利であり，dadtの実装ではそれを使っている．

string patternReplaceWithTable(string code, string[string] table) {
  string[] codes;
  size_t[][string] targets;
  bool in_bracket;
  string buf;

  for (size_t i = 0; i < code.length; i++) {
    char ch = code[i];

    if (!in_bracket) {
      if (ch == '#') {
        if (i + 1 < code.length && code[i + 1] == '{') {
          in_bracket = true;
          i++;

          codes ~= buf;
          buf = "";
          continue;
        } else {
          throw new Error("Syntax Error");
        }
      } else {
        buf ~= ch;
      }
    } else {
      if (ch == '}') {
        if (i + 1 < code.length && code[i + 1] == '#') {
          in_bracket = false;
          i++;

          codes ~= buf;
          targets[buf] ~= codes.length - 1;
          buf = "";
          continue;
        } else {
          buf ~= ch;
        }
      } else {
        buf ~= ch;
      }
    }
  }

  if (buf.length) {
    codes ~= buf;
  }

  foreach (key, value; table) {
    size_t[] idxes = targets[key];
    foreach (idx; idxes) {
      codes[idx] = value;
    }
  }

  return codes.join;
}

次のように使うことができる．

string function_template = `
#{RET_TYPE}# #{FUNC_NAME}##{TEMPL_ARGS}#(#{FUNC_ARGS}#) {
  #{FUNC_BODY}#
}
`;

mixin(function_template.patternReplaceWithTable([
  "RET_TYPE"   : "T",
  "FUNC_NAME"  : "square",
  "TEMPL_ARGS" : "(T)",
  "FUNC_ARGS"  : "T v",
  "FUNC_BODY"  : "return v * v"
]));

/*
  これで，次のような関数が生成される

T square(T)(T v) {
  return v * v;
}
*/

実際にpatternReplaceWithTableで展開する際に，同じキー(上の例でのRET_TYPEのような)は1度書くだけでよく，formatで整形する場合は同じものでも複数回書かないといけなかったことや，実際に何が展開されるかもわかりやすい．

長くなってしまうので，コード生成部分の雰囲気を見てもらうためにコードを抜粋して記載する．

string genCode(const TypeDeclare td) {
  string code;
  string interface_name = td.baseConstructor.baseName.name;
  const string[] interface_args = td.baseConstructor.parameterList.parameters.map!(
      (const TypeName tn) => tn.name).array;
  string args_str;
  string interface_args_str;
  if (interface_args.length) {
    interface_args_str = "(" ~ interface_args.join(", ") ~ ")";
    args_str = "!" ~ interface_args_str;
  }

  string[] enum_elements;
  foreach (i, constructor; td.constructorList.constructors) {
    if (i > 0) {
      enum_elements ~= "  " ~ constructor.typeName.name;
    } else {
      enum_elements ~= constructor.typeName.name;
    }
  }

  // dfmt off
  code ~= 
`
enum #{interface_name}#Type {
  #{enum_elements}#
}
`.patternReplaceWithTable([
  "interface_name" : interface_name,
  "enum_elements"  : enum_elements.join(",\n")
]);
  // dfmt on  

  // dfmt off
  code ~= 
`
interface #{interface_name}##{interface_args_str}# {
  #{interface_name}#Type type();
}
`.patternReplaceWithTable([
      "interface_name"     : interface_name,
      "interface_args_str" : interface_args_str]);
  // dfmt on

  foreach (constructor; td.constructorList.constructors) {
    string constructor_name = constructor.typeName.name;

    string[] field_names;
    string[string] field_info;
    string field_code;
    string[] field_type_and_names;
    foreach (i, fieldType; constructor.fields) {
      string field_name = "_%d".format(i);
      field_names ~= field_name;
      field_info[field_name] = fieldType.typeString();
    }

    foreach (field_name; field_names) {
      string field_type = field_info[field_name];
      field_type_and_names ~= "%s %s".format(field_type, field_name);
    }
    foreach (field_type_and_name; field_type_and_names) {
      field_code ~= field_type_and_name ~ ";";
    }

    string this_code;
    string this_argument = field_type_and_names.join(", ");
    string initialize_list;
    foreach (field_name; field_names) {
      initialize_list ~= "this.%s = %s;".format(field_name, field_name);
    }

    // dfmt off
    this_code = `
  this(#{this_argument}#) {
    #{initialize_list}#
  }`.patternReplaceWithTable([
        "this_argument"   : this_argument,
        "initialize_list" : initialize_list]);

    string type_code = `
  #{interface_name}#Type type() {
    return #{interface_name}#Type.#{constructor_name}#;
  }
`.patternReplaceWithTable([
  "interface_name"   : interface_name,
  "constructor_name" : constructor_name
]);

    code ~= `
class #{constructor_name}##{interface_args_str}# : #{interface_name}##{args_str}# {
  #{field_code}#
  #{this_code}#
  #{type_code}#
}`.patternReplaceWithTable([
        "constructor_name"   : constructor_name,
        "interface_args_str" : interface_args_str,
        "interface_name"     : interface_name,
        "args_str"           : args_str,
        "field_code"         : field_code,
        "this_code"          : this_code,
        "type_code"          : type_code]);
    // dfmt on

    string helper_code;
    string helper_returnType = constructor_name ~ args_str;
    string helper_name = constructor_name.toLower;
    string helper_typeParameters;

    if (interface_args.length) {
      helper_typeParameters = "(" ~ interface_args.join(", ") ~ ")";
    }

    string[] helper_arguments;
    string[] helper_variables;

    foreach (i, field; constructor.fields) {
      helper_arguments ~= "%s _%d".format(field.typeString(), i);
      helper_variables ~= "_%d".format(i);
    }

    // dfmt off
    helper_code = `
#{helper_returnType}# #{helper_name}##{helper_typeParameters}#(#{helper_arguments}#) {
  return new #{helper_returnType}#(#{helper_variables}#);
}
`.patternReplaceWithTable([
      "helper_returnType"     : helper_returnType,
      "helper_name"           : helper_name,
      "helper_typeParameters" : helper_typeParameters,
      "helper_arguments"      : helper_arguments.join(", "),
      "helper_variables"      : helper_variables.join(", ")]);
    // dfmt on

    code ~= helper_code;
  }

  string match_returnType = "_RETURN_TYPE_OF_MATCH_WITH_%s".format(interface_name);
  // dfmt off
  string match_header = "#{match_returnType}# matchWith#{interface_name}#(#{match_returnType}#, #{interface_args}# choices...)(#{interface_name}##{args_str}# arg) {".patternReplaceWithTable([
      "match_returnType" : match_returnType,
      "interface_name"   : interface_name,
      "interface_args"   : interface_args.join(", ") ~ (interface_args.length > 0 ? "," : ""),
      "interface_name"   : interface_name, "args_str":args_str]);
  // dfmt on

  string match_static_routers;

  foreach (constructor; td.constructorList.constructors) {
    string type_signature = constructor.typeName.name ~ args_str;
    string[] field_names;
    foreach (i, fieldType; constructor.fields) {
      string field_name = "x._%d".format(i);
      field_names ~= field_name;
    }

    // dfmt off
    match_static_routers ~= `
      static if (is(#{type_signature}# == params[0])) {
        #{type_signature}# x = cast(#{type_signature}#)arg;

        static if (is(ReturnType!(choice) == #{match_returnType}#)) {
          static if (is(#{match_returnType}# == void)) {
            choice(x);
          } else {
            return choice(x);
          }
        } else {
          static if (isCallable!(ReturnType!(choice))) {
            return cast(#{match_returnType}#)choice(x)#{field_args}#;
          } else {
            return cast(#{match_returnType}#)choice(x); 
          }
        }
      }
`.patternReplaceWithTable([
  "type_signature"   : type_signature,
  "match_returnType" : match_returnType,
  "field_args"       : field_names.length > 0 ? `(` ~ field_names.join(", ") ~ `)` : "()"]);
    // dfmt on
  }

  // dfmt off
  string match_code = `
#{match_header}#
  import std.traits;
  #{match_returnType}# delegate() otherwise = null;

  foreach (choice; choices) {
    alias params = Parameters!choice;
    static if (params.length < 1) {
      otherwise = () => choice();
    }

    if (cast(params[0])(arg) !is null) {
      #{match_static_routers}#
    }
  }

  if (otherwise !is null) {
    static if (is(#{match_returnType}# == void)) {
      otherwise();
      return;
    } else {
      return otherwise();
    }
  }

  static if (!is(#{match_returnType}# == void)) {
    return null;
  }
}
`.patternReplaceWithTable([
  "match_header"         : match_header,
  "match_returnType"     : match_returnType,
  "match_static_routers" : match_static_routers
]);
  // dfmt on
  code ~= match_code;

  // この下に@@derivingのためのコード生成が入るが省略
  if (td.deriving !is null) {
    //中略
  }

  return code;
}

実際に使う例

また，実際に使う際には，次のように，パース，及びコード生成の結果をトップレベルに文字列mixinすることで組み込んで使うことができる．

enum code = `
type Option(T) =
  | Some of T
  | None
  [@@deriving show, ord, eq]
`;

mixin(genCode(buildAST(cast(TypeDeclare)DADT(code))));


void main() {
  Option!int opt1 = new Some!int(1);
  Option!int opt2 = new None!int;

  assert (equal_Option(opt1, opt2) == false);
}

結果

これまで，D言語でプログラミングをする際に，代数的データ型の必要性を痛感していたのだが，これによってD言語でも実用的な代数的データ型を使うことができるようになった．また，自分でbindを定義することで，Monadを扱うような感じでつかうこともできる．そして，簡易的なパターンマッチも提供することで，代数的データ型としての真価も発揮できるようになったといえる．
また，今回の例では，Optionと，BinaryTreeといった，一番基本的な例と，再帰的な構造を含む例のみを述べたが，Eitherなども考えることができ， それらはリポジトリ: https://github.com/alphaKAI/dadt のstdadtsというディレクトリの中に収録した．

まとめ

コンパイル時メタプログラミングを駆使することでD言語に，関数型プログラミング言語の強力な機能であるADT(Algebraic Data Type; 代数的データ型)を導入した． 実装は，次のステップで行った．

• 1: OCamlに似たSyntaxのADT用の構文を定義する．
• 2: それをコンパイル時にパースしASTを構築する．
• 3: ASTを元にDのコードを生成する．

そして，生成されたDのコードを文字列mixinすると，生成したADTを使うことができるようになる． 今後はさらなる利便性のために，実用的な様々なデータ型に対して適応可能なパターンマッチをD言語に導入すべく，今回の手法である，コンパイル時メタプログラミングを駆使することでパターンマッチの実装も行いたいと考えている．