19
Help us understand the problem. What are the problem?

More than 5 years have passed since last update.

posted at

魔術とプロコン

この記事はTUT Advent Calendarの2日目の記事です。

闇の時代

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

闇プログラマ

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

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

闇言語

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

D言語

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

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

wiki : 確率的にコンパイルを失敗させる - D言語友の会

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

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

プロコンとC++14魔術

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

/**
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関数の定義は次のようになっている。

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で分岐をすべきである。

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

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>()といった関数が、実は黒魔術なのである。
それぞれの定義を示そう。

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

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

#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>()の場合、次のように展開される。

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型の値tt.to_string(stream)コンパイルが通るのであれば、コンパイル時にtrueと評価される。
そうでない場合には、コンパイル時にfalseと評価されるのだ。
これこそが黒魔術である。

黒魔術入門方法

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

明日は…

誰なんでしょうか?

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
19
Help us understand the problem. What are the problem?