魔術とプロコン

この記事は[TUT Advent Calendar](http://www.adventar.org/calendars/639)の2日目の記事です。


## 闇の時代

C++に代表されるような静的型付言語にあるようなテンプレートは偉大である。
テンプレートによって様々な不可能なことが可能にされ、様々な機能の先駆けとなった。
コンパイル時に計算を行うという無謀だが夢のある行為はテンプレートから始まった。
コンパイラ言語において計算の実行時をRuntimeというが、コンパイル時も実行時となったのである。
しかし、C++テンプレートだけで黒魔術と呼ばれる高度な計算を行うことは、闇プログラマでないと困難な技術であった。


## 闇プログラマ

C++を使用すれば、原初の最も低レベルな要素からテンプレートなどの上位レベルまでのコードを書くことができる。
それゆえC++は膨大で複雑な言語仕様を持つ。
この言語は、ある者からすれば普通の言語であるが、他の者からすれば黒魔術でもあるのだ。
そのC++の言語仕様を理解した一部の選ばれし者の末路が闇プログラマである。

闇プログラマは、時には複数人が団結することで闇の軍団と呼ばれるコミュニティを形成する。
闇の軍団では、互いの魔力を高め合うために日々訓練とディスカッションが行われている。
一般人からするとその会話や行動は一切理解不能である。


## 闇言語

C++は普通のプログラミング言語のように見えて、実際には黒魔術を実行可能な闇言語の一つなのである。
公表されている闇言語は、C++, D, Haskell, Nemerleなど多数存在する。
また、近年では鳥類が黒魔術を扱うためのRillという言語も開発されている。
Rillは別名を文鳥言語というが、その思想はC++やD言語といった闇言語の血筋そのものである。


## D言語

D言語、Dark Languageは黒魔術を行うために開発された言語である。
言語の中核に黒魔術が豊富に活用されており、D言語話者のうち中級以上のものは黒魔術を呼吸をするように扱う。

彼らにとって、黒魔術、つまり高度なコンパイル時計算は実行時計算にほぼ等しいのである。
数年前には、コンパイル時に乱数を生成することで、確率的にコンパイルに失敗するという技術もD言語において開発された。

[wiki : 確率的にコンパイルを失敗させる - D言語友の会](http://dusers.dip.jp/modules/wiki/?Articles%2F%E7%A2%BA%E7%8E%87%E7%9A%84%E3%81%AB%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%AB%E3%82%92%E5%A4%B1%E6%95%97%E3%81%95%E3%81%9B%E3%82%8B)

実に馬鹿げていると思うかもしれないが、それは私達が闇プログラマではないためである。
闇プログラマであれば、このような一見使いどころのなさそうなプログラムでも、性能を十分に発揮し活用するのである。

コンパイル時に乱数が動作するということは、乱数を扱うアルゴリズムがコンパイル時に動作するということである。
その有用性は計り知れない。


## プロコンとC++14魔術

いきなり筆者の話になるが、今年は高専プロコンというプログラマの卵から病的プログラマまでが集うイベントに参加してきた。
私が参加した競技部門では、出場者それぞれが開発したコードで戦うのだ。
参加者の程度は推測であるが、プログラマの卵から病的プログラマまで幅が広いかと思われる。
参加者の中には闇プログラマもいたことだろう。
私は日常的にD言語を使用しているが、C++に関しては初心者であるから、C++で黒魔術を書くことに慣れていない。
しかし、私もコードの中に小規模だが、しかし至る所に黒魔術を仕込んでプロコンに挑んだ。
たとえば、次のような例を示そう。

~~~~~cpp
/**
swritef(std::cout, "% is %", "(3+2)", 5);   // (3+2) is 5
*/
template <typename Stream, typename T, typename... Args>
void swritef(Stream & stream, const char *s, T&& value, Args&&... args)
{
    while (*s) {
        if (*s == '%') {
            if (*(s + 1) == '%')
                ++s;
            else {
                swriteOne(stream, std::forward<T>(value));
                swritef(stream, s + 1, std::forward<Args>(args)...); // call even when *s == 0 to detect extra arguments
                return;
            }
        }
        stream << *s++;
    }
    PROCON_ENFORCE(0, "extra arguments provided to printf");
}
~~~~~~~~

この`swritef`関数は、コメントにあるようにただのフォーマット出力を行うだけだ。
しかし、この`swritef`関数は、文字列, 数値はもちろんのこと、以下の様な型にも対応している。

* `obj.to_string(stream);`のコンパイルが通る型
* `std::cout << obj;`可能な型
* イテレータを持つ型
* 配列に似たような型
* 例外のような型

これらの型への対応には、`swriteOne`関数で行っている。
`swriteOne`関数の定義は次のようになっている。

~~~~~cpp
template <typename Stream, typename T>
void swriteOne(Stream& stream, T&& value)
{
    //std::enable_ifもまともに使えないVC++ 2013 Nov. CTPコンパイラやめてくれ～～～
    // 仕方なく、conditionalで分岐するマン
    std::conditional_t<has_to_string<T>(),
          HasToStringWriter,
        std::conditional_t<can_stream_out<T>(),
          CanStreamOutWriter,
        std::conditional_t<is_input_iterator<T>(),
          IsInputIteratorWriter,
        std::conditional_t<is_similar_to_array<T>(),
          IsSimilarToArrayWriter,
        std::conditional_t<is_similar_to_exception<T>(),
          IsSimilarToExceptionWriter,
          StaticAssertWriter
    >>>>>::writer(stream, value);
}
~~~~~~~~

すべて`std::conditional_t`で分岐している理由は、VC++ 2013 Nov. CTPというコンパイラを開発環境として使用していたためである。
本来であれば、`std::enable_if`で分岐をすべきである。

`HasToStringWriter`や`CanStreamOutWriter`といった、大文字で始まり、最後に`Writer`と付くものは、次のような型である。

~~~~~cpp
struct HasToStringWriter
{
    template <typename Stream, typename T>
    static void writer(Stream& s, T&& value)
    {
        value.to_string(s); // ストリームに文字列表現を流し込むだけ
    }
};
~~~~~~~~


それはさておき、`has_to_string<T>()`や、`can_stream_out<T>()`といった関数が、実は黒魔術なのである。
それぞれの定義を示そう。

~~~~~~cpp
PROCON_DEF_TYPE_TRAIT(has_to_string, true,
(
    p->to_string(std::declval<std::ostream&>())
));
~~~~~~~~~

`std::declval<T>()`は、コンパイル時に`T`型の値を返す関数である。
では、`PROCON_DEF_TYPE_TRAIT`というマクロが怪しい。
このマクロは次のような定義になっている。

~~~~~~cpp
#define PROCON_DEF_TYPE_TRAIT(name, inh, code)  \
template <typename T>                           \
constexpr auto name##_impl(T* p)                \
-> decltype((code, true))                       \
{ return true; }                                \
                                                \
constexpr bool name##_impl(...)                 \
{ return false; }                               \
                                                \
template <typename T>                           \
constexpr bool name()                           \
{                                               \
    return inh && name##_impl(static_cast<      \
    typename std::remove_reference<T>::type*>   \
    (nullptr));                                 \
}
~~~~~~~~~

たとえば、`has_to_string<T>()`の場合、次のように展開される。

~~~~~~cpp
template <typename T>
constexpr auto has_to_string_impl(T* p)
-> decltype(((p->to_string(std::declval<std::ostream&>)), true))
{
    return true;
}

constexpr bool has_to_string_impl(...)
{
    return false;
}

template <typename T>
constexpr bool has_to_string()
{
    return true && has_to_string_impl(
                    static_cast<typename
                        std::remove_reference<T>::type*>
                        (nullptr)
                    );
}
~~~~~~~~~

`has_to_string<T>()`関数は、`T`型の値`t`が`t.to_string(stream)`コンパイルが通るのであれば、コンパイル時にtrueと評価される。
そうでない場合には、コンパイル時に`false`と評価されるのだ。
これこそが黒魔術である。


## 黒魔術入門方法

今回の記事では、C++を例にして黒魔術を紹介した。
しかし、D言語では黒魔術をもっと簡単に使用できる。
黒魔術に興味が出たのであれば、D言語を始めることをお勧めする。


## 明日は…

誰なんでしょうか？