ltmpc:Parserの解説

Parserは、LR(1)法もどきの手法によりトークン列を抽象構文木に変換しています。 まずは、LR(1)法のおさらいからします。

LR(1)法

LR(1)法を使うと、（文法を適切に書いたとき）あらゆる決定性文脈自由言語を認識することができることが知られています。 また、完全に同様の方法で構文解析（出力がyes/noではなくて、抽象構文木も作らないといけない問題）も行うことができ、こちらもLR(1)法と呼びます。 LR(1)法を用いた構文解析は、仮想的に構文木が置けるスタックを使うプッシュダウンオートマトンとして理解することができます （ただし、プッシュダウンオートマトンからは、ノード構築子の種類が何であるかしかアクセスできず、その先のノードが何であるかはわからない）。

ところで、多くのLRオートマトンでは、認識の時だけでなく構文解析の時でも「現在の状態」と「現在までの状態のスタック」を使います。 Reduceする前の部分抽象構文木が置いてあるスタックのスタックトップ付近を眺めると、現在のLRオートマトンの状態はほとんど復元できるので、 これは単に何度もスタックを見返さなくて済むようにするためのメモであるということです。

（注：一般に、スタックに積まれている情報だけから現在のLRオートマトンの状態を復元できます。 ただし、一般の言語の場合はスタックトップだけではなくスタック全体が、特定の正規言語にマッチしているかを確認する必要があり、メモなしにいちいち確認していては線形時間で構文解析することができなくなります。）

LR法を手で書き下すのは困難なので、通常はパーサージェネレータを利用します。 しかし、今回のように手で書く場合にはLRオートマトンの状態を列挙するのが非常に面倒な上、どのLRオートマトンの状態がどのスタックトップ付近の状態に対応しているかを一目で判断することができなくなります。 そのため、今回はスタックトップ付近を何度も眺める方法を採用しました。

Parser

前提知識として、C++11TMPによるコンパイル時コンパイラltmpcを支えるテンプレートメタプログラミングテクニック - Qiitaの暗黙変換の項を理解しているものとします。

ソースコードの上から解説していきます。

CRTP型クラスの基底クラス

lr_element<T>はここでいうAny<T>に相当するもので、CRTP型クラスのうち必要なものはこれを継承しています。 lr_postfix_posはどうやら何にも使われていないようです……orz。 lr_suffix_pos<T>は、次に前置の単項演算子が登場しうる部分構文木を表すCRTP型クラスになっています。 例えば、if(expr)の直後には前置の単項演算子が登場し得ますが、3+(expr)の後ろには登場しません。 このため、if(expr)の次の'+'は単項演算子、3+(expr)の次の'+'は二項演算子であると判断することができます。

Statement

Statement<T>は、文(Statement)である部分構文木を表すCRTP型クラスになっています。

IfStatement_Nodeは、IfStatement_Node<>、IfStatement_Node<Cond>、IfStatement_Node<Cond, St>、IfStatement_Node<Cond, St1, St2>の四種類の形態を取り得ます。 これは、単なる濫用です。本来は別のクラスを作るべきです。また、IfStatement_Node<>とIfStatement_Node<Cond>は文法が正しい限り、出力には現れません。 これは、文法（参考）を以下の

<selection-statement> ::= if ( <expression> ) <statement> | ...

から

<selection-statement> ::= <if-begin> <expression> ) <statement> | ...
<if-begin> :: if (

のようにReduceするのを早める文法変換を行っているためです（本質的な効果はありませんが、スタックトップ付近を眺めないといけない個数が減り、また文法違反を早期に検出しやすくなります）。

また、BraceStatement_Node<T...>やDeclareStatement_Node<T...>は、真に可変長なテンプレート引数を持っています。 このため、「まだ後ろに足せる（閉じられていない）BraceStatement_Node」と「閉じられたBraceStatement_Node」を区別する必要があります。 これに使うのがStatement_Node<T>で、閉じるときはこれで囲うことにしています。紛らわしい……。別のクラスを作ればよかったですね……。

Expr

Expr<T>は、式(Expression)である部分構文木を表すCRTP型クラスになっています。 以下、演算子に対応する構文木のノードをたくさん定義しています。抽象構文木に一本道の部分を残さないようにするために、一つ優先順位が低い演算子のノードを継承 しています。 Term_Nodeは、識別子やリテラル、かっこでかこまれた式を表すノードです。

識別子とリテラルの定義

Nameは識別子、IntLiteralとCharLiteralとStringLiteralはリテラルです。

Func_Node

これも引数が可変長なので、「まだ後ろに足せるもの」と「閉じられたもの」を区別する必要があります。 このとき、閉じられたものはTerm_Node<T>で囲うことによって区別することにしています。

Type

ところで、C言語の単純な型は全てC++の型で表せるわけですが、さすがにそれはセコいかな、と思いちゃんとtype_int等と定義しています。 DeclareSpecifier、Declare、DirectDeclaratorなどは参考にした文法のそれを意味します。 NullDeclaratorは、型宣言のうち識別子が出現しないものの場合に使うプレースホルダーです。 識別子が出現しない型宣言は、典型的には関数の仮引数ですが、文法が同じなのでキャスト式の時にも使われます。

ropとトークン、traits

a+b&cをLR(1)法でパースするとき、'a'をスタックに積み、'+'をスタックに積み、'b'をスタックに積み、'&'を先読みした時点でa+bにReduceします。 a+b*cをパースするときには、'*'を先読みした段階ではa+bをReduceすることはありません。 このように、スタックの二番目の演算子によってReduceするべきかShiftするべきかが変化します。 lr_mult_ropは、乗算系の演算子（'*'、'/'、'%'）を先読みしたときにReduceするべき演算子を表すCRTP型クラスになっています。ropは、reduce_operatorを略したものです。

その他、lr_ifなど、Lexerの出力したトークンをParser独自の定義に変換するための定義が並んでいます。

C言語の型宣言は複雑で、構文木の上の方に出現するのは、使った時に得られる型です。 重要なのはその変数の使い方（これはポインタなのか配列なのか関数なのか？）なのですが、その情報は構文木の最下層に出現します。 そのため、再帰的に情報を収集する必要がありますが、それを実現するのがHasNameなどのtraits手法です。

Reduce

(下)...LRStack B Op A (上)のようなスタック状況でOp2を読み込んだ時、演算子の優先順位的にOpをReduceするべきだとわかったとします（これの判定にはCRTP型クラスが用いられます）。 このような時、Reduce<Op>::operator()( A B LRStack... )を呼び出すことでReduceを行います（Opは関数の引数には渡していない点に注意します）。 この時、AとBは暗黙変換せず、直接同じ型で渡します。なぜなら先読みしたOp2だけの情報からでは、Aをどこまで暗黙変換するべきかが分からないからです。 Aをどこまで暗黙変換するべきかはOpを見ればわかるのですが、それはOp2によらないのでそこだけ抽出しているのがReduceになります。

さらに、ほとんどの二項演算子は同じ構造を持っているので、テンプレートテンプレートパラメータによる抽象化が行われています。 ただし、代入演算子は他のものと異なる右結合であるので別に書かれています。

tuple expand

関数の返り型にパラメータパックを書くことができません。そのため型タプルを返すことになるのですが、それをパターンマッチしても暗黙変換は行われません。 暗黙変換を発動させるためには、関数の引数で受け取ることが必要です。そのため、タプルの中身を展開して関数の引数に渡す関数を作っています。

ReduceToken

これを継承することでReduceを行う定義をいちいち書かなくて済むようになります。

ReduceStatement

if(a)if(b)if(c)x=y;のようなものをパースすることを考えると、最後のセミコロン一つで合計四つの文(Statement)を完成させる必要があります。 これにはいろいろな方法がありますが、次のトークンを先読みした段階でスタックトップがCRTP型クラスStatement<T>を満たしていればReduceするという方法で行っています。 ReduceStatementは、本来は先読みなしでも完成させることができます。 しかし、そのような場合、一つのトークンを読み込んだ時にやる仕事が「Reduceを何回か、Shiftを一回、Reduceを何回か」のようになり、複雑になります。 ReduceStatementを次のトークンを先読みした段階で行うことにより、「Reduceを何回かしたのち、Shiftを一回やって完了」のように簡単になります。 このため、トークン列をすべて処理した後にfinalizeという関数で一度Reduceする必要があります。

reduceDeclare

';'、','、)を読んだ時に共通に行われる、DeclareへのReduceをまとめたものです。

SuffixPosReduceStatement

スタックトップがlr_suffix_pos<T>に該当するCRTP型クラスであったとき、

  • reduceStatementが行えるなら行ってから、行った後のスタックの状態で再度判断を行う
  • reduceStatementが行えないなら、lrElem...をスタックに積む

のどちらかを行います。lr_suffix_pos<U>で受ける上のオーバーロード関数は優先順位が低いため、Statement<U>にマッチしない場合のみ選ばれます。

それ以外のタイプのReduceの選択肢がある場合、SuffixPosReduceStatementを継承したうえで追加のオーバーロード関数を定義しています。

ReduceType

intなどの型を示すトークンが登場したときは、三通りのパターンが存在します。

  • 変数・関数宣言。前置単項演算子が登場し得るところ（の一部）に出現する。ReduceStatementする必要があるかもしれない。
  • 関数の仮引数宣言。開きかっこの後ろなら、仮引数リストの始まりで、コンマの後ろなら仮引数リストの続きである
  • キャスト。開きかっこの後ろに出現する

厄介なのは直前のトークンだけの情報では三つのうちどれが該当するのかわからない点です。幸い、文脈、つまりスタックのトップの方をもう少しだけ見れば区別がつきます。

Token<Lexer::Symbol<'('>>

開きかっこトークンに関する、Reduce/Shiftルールです。五通りのパターンが存在します。

  • 優先順位かキャストのかっこ。前置単項演算子が登場し得るところに出現する
  • 関数適用のかっこ。後置演算子が登場し得るところに出現する。後置演算子は一番優先順位が高いので、スタックトップがTerm_Node<T>であるパターンのみ
  • 構文のかっこ。if(、for(、while(のように出現する
  • 型宣言の時の優先順位のかっこ。型名のあとにポインタの'*'を0個以上伴った後に出現する
  • 型宣言の時の関数仮引数のかっこ。DirectDeclaratorのあと（簡単に言ってセミコロンが来れるところ）に出現する

Token<Lexer::Symbol<')'>>

閉じかっこトークンに関する、Reduce/Shiftルールです。開きかっこに対応する六通りのパターンが存在しますが、空のかっこ対が許されるためにイレギュラーが多いです。

  • 優先順位のかっこ。lr_commma_rop<T>に該当する演算子をReduceし切ってから閉じる
  • キャストのかっこ。reduceDeclareし切ってから閉じる
  • 関数適用のかっこ。直前に'('があれば空の実引数リストであり、そうでなければlr_commma_rop<T>に該当する演算子をReduceし切ってから閉じる
  • 構文のかっこ。for(;;)、for(;;e)、if(e)、while(e)のようになるのでlr_commma_rop<T>に該当する演算子をReduceし切ってから閉じる
  • 型宣言の時の優先順位のかっこ。reduceDeclareし切ってから閉じる
  • 型宣言の時の関数仮引数のかっこ。直前に'('があれば空の仮引数リストであり、そうでなければreduceDeclareし切ってから閉じる

今見ていたら、

template<class... LRStack, std::size_t M> 
static auto move_to( Pointer<0>, lr_open_paren, Pointer<M>, LRStack... ) 
    -> type_stack<DirectDeclarator<Function<NullDeclarator, ParameterList<>>, Pointer<0>>, Pointer<M>, LRStack...>;

は名前のない関数の宣言か仮引数宣言かキャストかしかありえないけれど、いずれも文法違反だからこの行は必要ない気がしますね……。

Token<Lexer::Symbol<'['>>

開き角かっこトークンに関する、Reduce/Shiftルールです。二通りのパターンがあります。

  • 配列アクセスの角かっこ。後置演算子が登場し得るところに出現する
  • 配列型宣言の角かっこ。型名のあとにポインタの'*'を0個以上伴った後に出現すれば識別子なしの宣言であり、そうでなければ普通の宣言

Token<Lexer::Symbol<']'>>

閉じ角かっこトークンに関する、Reduce/Shiftルールです。開きかっこトークンに対応する二通りのパターンがあります。

Error_multidimensional_array_must_have_sizeは正しくない気がしますね……。 int (*a[])[]がパースできなさそうです。そもそもこんなことはTypeAnalysisでやるべきです。

Token<Lexer::Symbol<'{'>>

開き中かっこトークンに関する、Reduce/Shiftルールです。いずれにしてもBraceStatement_Nodeをスタックに積みます。 ここで、スタックトップだけ見る方法でdo;while(e){のようなものをパースするとき、最終的に失敗するとしても一見正常にパースが進んでしまいます。 そのため、このパターンを検出してエラーにするということを行っています（これをしないと非常にわかりづらいSFINAEエラーで落ちてしまいます）。 また、関数宣言の直後に来た場合には関数定義の中かっこになるのですが、「関数宣言かどうか」はC言語の複雑な型宣言の仕様により構文木の最下層を見ないとわかりません。 そのためtraitsで関数宣言か判定しています。これはSFINAEにならないパターンですね。ちゃんと継承を使って書かないといけないのでした。直し忘れていました。

Token<Lexer::Symbol<'}'>>

閉じ中かっこに関する、Rebuceルールです。BraceStatement_NodeにReduceする前に{if(a)if(b)if(c)x=y;}のような多段になっているものをReduceしていきます。

Token<Lexer::Symbol<'?'>> Token<Lexer::Symbol<':'>>

条件演算子に関する、Rebuce/Shiftルールです。他の二項演算子と結合法則が異なるため、直書きしています。

AssignTokenRule

右結合の代入演算子に関するReduce/Shiftルールをまとめたものです。 Cond_Node<T>, lr_element<U>で受けるのは、T, lr_assign_rop<U>で受けるよりも優先順位を下げないといけないことによります。 他の部分でも、lr_element<U>と出現している箇所はこれと同じ理由によります。

BinaryTokenRule MultiBinaryRule

左結合の二項演算子に関するReduce/Shiftルールをまとめたものです。 And_Node<class...>とPlus_Node<PlusOpType, class...>等は別の形になっていて一つのテンプレートテンプレートパラメターにマッチしないためMultiBinaryRuleが存在します。

UnaryTokenRule

前置単項演算子に関するReduce/Shiftルールをまとめたものですが、単にSuffixPosReduceStatementを継承するだけになっています。

UnaryMultiBinaryTokenRule

'*'、'+'、'-'の三種類の、前置単項演算子としても二項演算子としても使える演算子に関するReduce/Shiftルールをまとめたものです。 多重継承する場合はusing宣言しないとオーバーロード解決されません。

以下、これらのルールをまとめたものを継承した具体的なルール定義が並びます。

Token<lexer::Symbol<','>>

コンマに関するReduce/Shiftルールです。以下の三通りが存在します。

  • 関数の引数の区切り記号（lr_comma_rop<T>に該当する演算子をReduceし切ってから）
  • 順次演算子（lr_comma_rop<T>に該当する演算子をReduceし切ってから）
  • 関数宣言の仮引数の区切り記号（reduceDeclareし切ってから）

Token<lexer::Symbol<';'>>

セミコロンに関するReduce/Shiftルールです。以下の四種類が存在します。

  • ;（セミコロンだけ）、break;、continue;、return;の形の文
  • expr;かreturn expr;のような式文の終わり（lr_comma_rop<T>に該当する演算子をReduceし切ってから）
  • 変数宣言の終わり（reduceDeclareし切ってから）
  • int;のような意味のない文

parse

二分再帰により、トークン列をLR(1)法で順次パースしていきます。 ただ、散々Lexerのところで空間計算量Ο(NlogN)にこだわってきたというのにこの方法は、"後ろに渡す情報量"がΘ(N)あるので、空間計算量がΘ(N2)になっています。 LR法で構文解析する限り、TMPの制約のもとでは空間計算量Ω(N2)の壁は破れなさそうに思っています。

finalize

「トークン列の終端」を先読みした時にReduceStatementが必要であれば行う関数です。

Parserを書いてみて

Parser.hppは、千行を超える長大なファイルになっています。 C言語ほどの文法をLR(1)法により構文解析するプログラムを一から書きあげるのはそれなりに大変でしたが、それなりに現実的に書き下すことができました。 LR(1)法といってもスタックトップ付近を見ながらパターンマッチで「今の状態」を導出する、という方法はC++TMPのパターンマッチング機能が優秀なこともありますが、大域的なことを考えずにかけるので楽でした。 言語処理系論の授業で習った時はいまいち理解が深まらなかったLR法でしたが、yaccのようなパーサージェネレータに頼るのではなく、自分の手で書くとさすがに理解が深まったと思います。

ltmpc: LexerとPreLexerについての解説

この二つのプログラムでは、ltmpcへの入力文字列をトークン列に切り分けることを行っています。 トークン列への切り分けは、前から順に行っていくのではなく、(疑似的な)並列処理を行いマージしていく、という普通ではない方法を使っています。 なぜこのような方法を取っているのかについては、並列アルゴリズムのことを知っていると理解しやすいので、まずは並列アルゴリズムのおはなしをします。

並列アルゴリズム

並列アルゴリズム、というと普通はもっと広い範囲を指し示しますが、以下に紹介する例は、いずれも「プロセッサがΘ(N)個あればΘ(log N)段で動作するアルゴリズム」です。

例その0：FFT

入力の要素数が N=2^{n}の時、「 2^{n-1}個のプロセッサが並列にバタフライ演算をし、次のプロセッサにデータを渡す」という操作をn段繰り返すと仕事が終了します。

(細かい注)現実には、あまりに大きいNに対しては配線遅延により遠くのプロセッサにデータを渡すことが律速になり、Ο(logN)時間には間に合わなくなります。

例その1：parity

2bitのxorを取り1bitにする、というのを完全二分木型の分割統治で行えばlogN段で仕事が終了します。

例その2：キャリー予測加算器

普通にNbit加算器を作ると、255+1のような、繰り上がりの連鎖が発生する場合に最悪Θ(N)の時間がかかってしまいます（リプルキャリーアダー）。 そこで、次のように仕事を分割します。

  • 下N/2bitの加算を行い、繰り上がりの有無を報告する仕事
  • 下からの繰上りはないものと仮定し、上N/2bitの加算を行う仕事
  • 下からの繰上りがあるものと仮定し、上N/2bitの加算を行う仕事

以上の3つの仕事は、明らかに並列に計算できます。そして、繰り上がりの有無の報告後、上N/2bitの加算の結果のうち適切な方を選ぶのはΘ(1)時間で行えます。 N/2bitの加算を同じ方法で再帰的に分割統治により行えば、logN段で仕事が終了します。

例その3：かっこの対応

次の文脈自由文法は、かっこが正しく対応している文字列を作り出します。

S = SS | () | ε

あるいは、左右の対称性が読み取れなくなりますが、以下のようにも変形できます。

S = (S)S | ε

かっこの対応を並列に判定するのは難しそうですが、まず以下のように問題を切り分けます。

  • 左右のかっこの数が等しいこと
  • \forall n \in \left[0, N\right]: 文字列の先頭からn文字の中に、')'が'('より多く含まれないこと

以上の二点が満たされていることと、かっこの対応が正しいことは同値になります。

これを並列アルゴリズムで書くと、以下のようになります。

まず、入力に含まれる

  • '(' を{ balance: 1, depth: 0 }に、
  • ')' を{ balance: -1, depth: -1 }に、

それぞれ変換します。

merge( { balance: w, depth: x }, { balance: y, depth: z } ) {
    return { balance: w+y, depth: min( x, w+z ) }
}

と定義します。 このmerge関数により、二分木型のマージを行ってゆけば、最終的に{ balance: x, depth: y }が得られます。 この時、x == 0 && y == 0であれば、かっこが正しく対応しており、それ以外の場合は正しく対応していないことになります （ところで、このmerge関数は結合法則が成り立っています。確かめてみると理解が深まるかと思います）。

その１、その２、その３は、いずれも二分木型の分割統治で、ランダムアクセスがいらないタイプの、 非常に取り扱いやすいアルゴリズムのパターンであるという共通点があります。

この種類のアルゴリズムを一般化すると、以下のようなことができます。

  • 正規言語の判定
  • 有限状態トランスデューサ―
  • DSPACE(logN)でできる文脈自由文法の判定

これは、順に先の例に対応します。なぜ一般化できるかを説明します。

並列アルゴリズムのパターンを一般化

正規言語の認識

基本的なアイデアは、キャリー予測加算器で行っていたような、「この状態で始まったら、この状態になるはず」というものを、その可能性全てについて投機的実行するというものです。

有限状態オートマトンを事前に構築しておくきます。

入力文字列は長さNの文字列sであるとし、s[0]...s[N-1]で各文字を表すとします。 プロセッサはN個用意し、P[0]...P[N-1]と表すとします。

アルゴリズムは以下のようになります。

第0段

各プロセッサP[i]はs[i]を読み込む。

M要素の配列、 P\left[i\right]_{0}を構築する。 P\left[i\right]_{0}\left[j\right] = δ(q(j), s\left[i\right])であるとする。

第k段(k>0)

プロセッサ番号が 2^{k}で割り切れなければ、何もしない。

プロセッサ番号が 2^{k}の倍数であれば、M要素の配列 P\left[2^{k} i\right]_{k}を次のように構築する。

P\left[2^{k} i\right]_{k}\left[j\right] = P\left[2^{k} i + 2^{k-1}\right]_{k-1}\left[ P\left[2^{k} i\right]_{k-1}\left[j\right] \right]

ただし、 P\left[2^{k} i + 2^{k-1}\right]が存在しない場合は、 P\left[2^{k} i\right]_{k}\left[j\right] = P\left[2^{k} i\right]_{k-1}\left[j\right]とする。

この時、 n = \lfloor \log{2}(N)\rfloorとする。第n段では、P[0]だけ動作している。

この時、 P\left[0\right]_{n}\left[q(0)\right]を調べ、それが受理状態であれば、受理。そうでなければ拒否。

例："aaabaab"が/(aaa)+b)*/にマッチするを並列に判定する。

  • Σ = { 'a', 'b' }
  • Q = { q(0), q(1), q(2), q(3), q(m) }
  • δ(q(0), 'a') = q(1)
  • δ(q(1), 'a') = q(2)
  • δ(q(2), 'a') = q(3)
  • δ(q(3), 'a') = q(1)
  • δ(q(m), 'a') = q(m)
  • δ(q(0), 'b') = q(m)
  • δ(q(1), 'b') = q(m)
  • δ(q(2), 'b') = q(m)
  • δ(q(3), 'b') = q(0)
  • δ(q(m), 'b') = q(m)
  • 開始状態：q(0)
  • 受理状態：{q(0)}

ちなみに、

  • q(0) は /((aaa)+b)*/
  • q(1) は /((aaa)+b)*(aaa)*a/
  • q(2) は /((aaa)+b)*(aaa)*aa/
  • q(3) は /((aaa)+b)*(aaa)+/
  • q(m) は /((aaa)+b)*(b|(aaa)*ab|(aaa)*aab)[a|b]*/

に、それぞれ対応しています。

マージしていく過程は、以下のようになります。

f:id:lpha_z:20180107224613p:plain

そして、最終段にq(0)→q(m)と書いてあることから、マッチに失敗したことが分かります。

有限状態トランスデューサー

先の例とほとんど同じに構築できます。プロセッサの作る配列の要素は「次状態」だけではなくて「次状態と出力文字列のタプル」に変更します。 出力文字列を構築するのはただの文字列連結なので簡単です。休んでいるプロセッサで並列にコピーができるのでΘ(1)時間で行えます。

以上の二つのようなことができるのは、有限モノイドが背後に隠れています。 簡単にいうと、結合法則が成り立つmerge関数が作れるということです。 DFAの次状態の導出は過去の状態などによらないので、結合法則が成り立ちます。 文字列の連結も同様に結合法則が成り立ちます。

DSPACE(logN)な文脈自由文法の認識

[[{}{()(())}]()]
[              ]
 [          ]
  {}{      }
     ()(  )  ()
        ()

この項は思いつきで書いているので、間違っているかもしれません。 プッシュダウンオートマトンのスタックを考えてみます。スタックの状態を記述するのにDSPACE(logN)で済むということは、 スタックの状態としてあり得るのがΟ(Nc)種類くらいしかないということです。 これは、スタックに積む文字の種類がc個(A,B,C,...とします)あり、それが入り混じることはなく順番に現れる、という状態だと思われます。 スタックの状態としてはAABBBBBBCCとか、BCCCとかしかありえなくて、ABACとかは無理だということです。 こういうのを許すと、スタックの状態としてあり得るパターンがΟ(cN)種類になります。

こういう場合でも、先の並列アルゴリズムメソッドを少し改良するだけで並列アルゴリズムが生み出されます。 この状態で入力文字列を読んだらこの状態になる、という一覧表を作るのは、状態数が無限にあることから不可能ですが、 幸い、状態としてあり得るのはΟ(Nc)個くらい、整数がc個分くらいの情報量です。 Φ(q)を満たす状態qで読み込んだら次状態はf(q)、……という風に条件式Φを用いてまとめることが可能です。 Φは、0判定の条件式c個になり、fはいずれか一整数を+1/-1する関数になるはずです。

ここでもモノイドが背後に隠れています（ただし無限モノイドです）。 実際、かっこの対応のところで見たように、merge関数は結合則を満たしています。

（実際は、DSPACE(logN)で認識できる文脈自由文法に限らず、あらゆる決定性文脈自由文法で、このような結合則を満たすmerge関数を作ることができます。 しかし、その台集合はプッシュダウンオートマトンのスタック操作の履歴同然のものになってしまっています。 それのマージは結局元の文脈自由文法認識問題と大差ない仕事が必要なのでmerge関数の計算量が非常に多くなり、並列化の意味がなくなってしまいます。）

Lexer と PreLexer の説明

さて、以上の並列アルゴリズムを直列アルゴリズムに変換します。 直列アルゴリズムを並列アルゴリズムに変換するのは非常に困難な問題ですが、逆は簡単です。

ではなぜ、わざわざ並列アルゴリズムから考えたのでしょうか。その答えは、TMPにおいては*1空間の節約のためです。 並列アルゴリズムがあるということは、前の結果を使わなくても計算を進めることができるということです。 これは、直列化したアルゴリズムにおいて、一見Nステップの逐次に見える動作をしていても、 そのステップの間で受け渡される情報量がそれほど多くないということを意味しています。

これは重要で、ステップ間で受け渡される情報量がΘ(N)とかだと、Nステップで合計Θ(N2)になるのでスケールしない、ということを意味します。

Lexer

Lexprの基本となる作戦は、入力文字をN個の文字に切り分け、ボトムアップに隣とマージして行く、という方法です。

Lexprでは、入力文字をN個の文字に切り分け、ボトムアップに隣とマージしていきます。 トークナイズのルールは正規文法で表されているため、結合則が成り立ちます。 そのため、どこを先にマージしても最終的な結果が変わることはないので、安心して並列にマージを進めることができます。 実際には並列にマージしているわけではなく前半分の処理が終わってから後ろ半分の処理をしているのですが、後ろ半分の処理には前半分の結果を全く渡していません。

マージしていくと、担当している部分入力文字列について、それをトークナイズした出力は、以下のような感じになります。

  • 入力 "alpha+beta/56"
  • 出力 [ "alpha", "+", "beta", "/", "56" ]

しかし、"56"は"56789"の一部の可能性が残るため、確定トークンとは言えません。"alpha"についても同じです。 逆にいうと、二つの出力をマージする時、出力全てを見る必要はなく、前半分の結果の末尾に存在する未確定トークンと後ろ半分の結果の先頭に存在する未確定トークンだけを眺めてマージし、 他の部分は全くそのままコピーすればよいのです。

ところで、ソースコード上の空白の情報は、トークン列化すると残らないのでした。空白により確定トークン化していることを表す情報がないと、" a "と"a"の区別をつけることができません。 そこで、以下のような記法を導入します。なんかブラケット記法を彷彿とさせますがあまり関係ありません。

  • <α>　は文字列αであり、その文字列を含むトークンが右にも左にも伸びうることを意味します。
  • <α|β> は、文字列αβはαとβの間にトークンの切れ目が存在し、αは左に伸びうる、βは右に伸びうることを意味します。
  • <α|β| は、文字列αβはαとβの間にトークンの切れ目が存在し、αは左に伸びうるが、βは右に伸びることはないことを意味します。
  • |α| は、文字列αであり、その文字列でトークンが完結していることを意味します。

  • <α|β|γ|δ> は、文字列αβγδについて、βとγが確定トークンで、αは左に伸びうる、δは右に伸びうる、ということを意味します。

  • 例1:文字列":"はひとつでトークンを成すので、|":"|となります。

  • 例2:文字列"%"は左に伸びる可能性はありませんが、右に伸びる可能性はある(%=がある)ので、|"%">となります。
  • 例3:文字列"a"は左にも右にも伸びる可能性があるので、<"a">となります。
  • 例4:文字列"a "は右に伸びる可能性はありませんが、左に伸びる可能性はあるので、<"a"|となります。
  • 例5:文字列"abc"は<"abc">
  • 例6:文字列"abc = 123"は<"abc"|"="|"123">

LexerのCombSingle<T>は<α>を意味し、CombTriple<T1, TokenTuple<T2...>, T3>は<α|β……γ|δ>を意味します。 また、NullTokenを含む場合、例えばCombTriple<T1, TokenTuple<T2...>, NullToken>は、<α|β……γ|を意味します。 CombTriple<NullToken,TokenTuple<T2>, NullToken>は|α|を表すのに対し、Combsingle<T>は<α>を表すという違いに注意します。

マージするときは、端が何で終わっているかによって対応が異なります。

  • 端が両方|の場合は、単に結合すればマージ完了です。
  • 端の片方が|でもう片方が<や>の場合は、もう片方の未確定トークンを確定させ、結合すればマージ完了です。
  • 端が>と<の場合は、トークンの連結（concat関数）が発生します。

最後のパターンは厄介です。|"a"> <"+"> をマージすると|"a"|"+"> になるように、トークンの連結の結果一トークンになる時と二トークンになる時があります。 このため、<α|β|γ><δ|ε|ζ>をマージする時、確定部分<α|β|、マージした結果、確定部分|ε|ζ>の三要素をマージするが存在します。

また、concat関数には技巧的な部分もあります。"&&&"みたいなものをパースするとき、"&&" "&"が正しく、"&" "&&"は正しくありません。 先頭から強欲に二文字にマッチするのが正しいのです。そのため、|"&"> <"&&"|という連結が発生した場合は、|"&&"|"&"|のように組み換えが発生します。 更に技巧的な点がありますが、それは後述します。

PreLexer

実は、並列トークナイザでは厳しいことがあります。

それは、自分の周りの状況だけからでは、文字列リテラルの中、コメントの中、といった環境を推定することは絶対に不可能だからです。 上で述べた並列トランスデューサの理論によれば、有限個しかない全てのありうる可能性を列挙していたのですが、明らかに空間を浪費します。

そこで使われるのがPreLexerです。文字列リテラルの中、コメントの中、といった情報を有限状態トランスデューサーを動かすことで 収集します。この実行は直列的に行うので、あらゆる可能性に対して計算をする必要はなく空間を浪費しません。また、後ろに渡す状態は

template<bool Slash> 
struct Normal; 
template<bool NextEscape> 
struct InCharLiteral; 
template<bool NextEscape> 
struct InStringLiteral; 
template<bool Asterisk> 
struct InComment;

の8種類(有限個)しかありません。

Lexerの変に技巧的な部分

もう一つは、'+'が複数並んだような入力列に対しては連鎖的に組み換えが発生する可能性があるため、「マージするときは端だけ書き換えればいい」が成り立たないという点です。

二通りしかないので両方の可能性を考慮するとか、PreLexerでチェックするといった方法も考えられますが、 今回は「"+++"とあらわれた場合、その解釈は(周りを見なくても)C言語の文法的・意味論的に"++"(後置インクリメント) "+"(二項加算)しかありえない」 という事実を用いました。

というのも、もう一つ'+'が続いて"++++"となるとトークナイズは貪欲マッチなので"++" "++"とパースせざるを得なく、 これは前置/後置インクリメントの連続と解釈するしかないですが、意味論的にそのようなことはできません。 ちなみに、"++"(前置インクリメント) "+"(正符号)も文法的には正しいですがこれも意味論的には誤りです。

さいごに

Lexerを作ってから足りないところを補うためにPreLexerを作ったわけですが、 今考えてみると、並列トークナイズなどせずに、すなおに有限状態トランスデューサーを使ってトークナイズした方が簡単にできそうな気がしています。

そのうち直すかもしれません……。

*1:余談ですが、constexprメタプログラミングにおいては、書き換え回数を減らすために真の並列性が重要です。たとえば、Sprout constexprライブラリの制作者のボレロ村上さんがC++11constexprでは不可能とおっしゃっていたFFTを実現した私のコードがその顕著な例です。その他の例は GitHub - lpha-z/lfl: header only c++11 constexpr libraryにたくさん揃っています。

ltmpcの開発中に出会ったTMP注意点10選

C++11テンプレートメタプログラミングによるコンパイル時Cコンパイラ「ltmpc」を開発しています。

ltmpcのはなし - よーる

C++11TMPによるコンパイル時コンパイラltmpcを支えるテンプレートメタプログラミングテクニック - Qiita

テンプレートメタプログラミング(TMP)では、デバッグが非常に困難です。書き間違えの場合は注意深くソースコードを見つめることで除去可能ですが、C++の仕様を知っていないと取り除くことが不可能なものも多く存在します。今回は、ltmpcの開発中に出会った、つまらないミスからコンパイラのバグまで、TMPを行う上での注意点をまとめたいと思います。

なお、エラーの原因等は、C++の規格書もコンパイラのソースコードも読まずに推測して書いているので、かなり間違いがあると思います。鵜呑みにしないでください。 もしこれらの真の原因を知っている方がいらっしゃいましたら、指摘してくださると大変助かります。

0. sizeof...を繰り返し使わない

これは厳密にはltmpcの開発より前の出来事ですがどうせなのでまとめます。

  • 重大度：大（コンパイラがメモリを使い果たす）→小（最近のコンパイラだと大丈夫）
  • 解決困難度：中（設計の見直しが必要）→小（最近のコンパイラだと大丈夫）

問題

index_tupleの実装（ltmpc/index_tuple.hpp at master · lpha-z/ltmpc · GitHub）をしている時のことです。 make_index_tupleを実装するとき、index_t... Indicesとindex_t Stepを使って以下のように書きます。

Indices..., (Indices+Step)...

しかし、Stepはsizeof...(Indices)と同じ値なので、テンプレート引数からStepを除去し、以下のように書き換えました。

Indices..., (Indices+sizeof...(Indices))...

こうしてしまうと

  • `sizeof...(Indices)の計算にはΘ(N)の時間かかる
  • しかも、Indices...のΘ(N)回ある展開の毎回でそれが計算される

というわけで、Θ(N2)の時間がかかってしまいます（たぶん）。しかし、実際にはメモリを使い果たしてコンパイルに失敗する結果になります。なぜなのでしょう？

実行例

解決策

  • Nをテンプレート引数に持つ
  • デフォルトテンプレート引数を使って、一回しか計算が走らないようにする
  • 最近のコンパイラでコンパイルする

1. クラス定義の中では、まだ不完全型

  • 重大度：大（clangでコンパイルできない）
  • 解決困難度：大（設計の大幅な見直しが必要）

問題

フリー関数をメンバ関数にすれば、定数倍高速化するのではないかと考えていた時のことです（以下にはあまり関係がないです）。

「パラメータパックへのランダムアクセス」は推論を伴うアップキャストを使っています。これをクラス定義の中で行おうとすると、まだ不完全型なので変換コンストラクタがviableではないというエラーをclangは出します。これを回避するため、不完全型でも使えるはずのポインタを介して行おうとするのですが、推論が絡むとエラーになるという問題があります。clangの基準がよくわからないです。

実行例

#include <type_traits>

struct Base {};

int f( Base );

struct Derived : Base {
    using type = decltype( f( std::declval<Derived>() ) );
};

int main() {
    Derived d;
}
template<class>
struct Base {};

int f( Base<int>* );

struct Derived : Base<int> {
    using type = decltype( f( static_cast<Derived*>(nullptr) ) );
};

int main() {
    Derived d;
}
  • これならgccもclangも文句を言わない
template<class>
struct Base {};

template<class T>
int f( Base<T>* );

struct Derived : Base<int> {
    using type = decltype( f( static_cast<Derived*>(nullptr) ) );
};

int main() {
    Derived d;
}

解決策

参考文献：C++11でメンバ関数を持つ列挙体のようなものを作る - natrium's reminder

2. 前方宣言が必要ないのはいつ？

  • 重大度：大（gccでコンパイルできてしまう）→小（gccHEAD8.0.0で直った）
  • 解決困難度：大（大幅な設計の見直しが必要）

問題

関数形式のTMPを行っていると、再帰をするために必要な前方宣言ができない、とかADLが行われる形式なら問題ない、とかそういうことが分かっていなかった時のことです。

素直にADLが行われる形式で書けばよい話ですが、gccだとなぜか、名前修飾されていても同じstruct内の後ろの関数を参照できてしまうというバグがありました。 gccHEAD8.0.0で試してみたらこの問題は修正されているようなので、今後はこのバグに悩まされることはないでしょう。

実行例

struct Begin {};
struct Body {};
struct End {};

template<class...>
struct Tuple {};

template<class... Ts>
Tuple<Ts...> make_tuple( Ts... );

template<class T>
static auto f( T, End )
        -> int;

template<class... Ts>
static auto f( Begin, Ts... args ) 
        -> decltype( f( make_tuple( args... ) ) );

// tuple expand
template<class... Ts>
static auto f( Tuple<Ts...> )
        -> decltype( f( Ts{}... ) );

int main() {
        decltype( f( Begin{}, Body{}, End{} ) ) x;
}

上記のコードは上から二つ目のfで、それより後ろに存在する、三つ目のfを参照する必要があります。名前修飾されていないので、引数であるTupleに関連する名前空間（この場合、global空間を含む）からADLで検索されるため、後ろにあっても問題なく参照できます。

struct Begin {};
struct Body {};
struct End {};

template<class...>
struct Tuple {};

template<class... Ts>
Tuple<Ts...> make_tuple( Ts... );

struct X {
        template<class T>
        static auto f( T, End )
                -> int;

        template<class... Ts>
        static auto f( Begin, Ts... args ) 
                -> decltype( X::f( make_tuple( args... ) ) );

        // tuple expand
        template<class... Ts>
        static auto f( Tuple<Ts...> )
                -> decltype( X::f( Ts{}... ) );
};

int main() {
        decltype( X::f( Begin{}, Body{}, End{} ) ) x;
}

上のコードは、名前修飾されていますから、ADLが発動する余地はありません。しかし、gcc7.2.0まででコンパイルすると、構造体で囲った場合に限ってなぜか後ろの関数を参照してもコンパイルが通ってしまうのです（名前空間で囲んだ場合は問題が発生しません）。

解決策

  • ADLが行われるような関数にする（引数に来るものと同じ名前空間に入れる）
  • 構造体を使う形式にする
    • 暗黙変換が必要なら、暗黙変換を行う関数と、それを受け取る構造体に分離する→[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ
      • ただし、分離して書くと非常に読みづらいため使わない方がいいと思います
  • 擬似的な前方宣言を行う→[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ
    • デフォルトテンプレート引数を使って、無理やり依存名にして後方参照できる関数との相互再帰を行う方法です。おすすめです

3. 完全に覆い隠す関数

  • 重大度：大（gccでコンパイルできてしまう）
  • 解決困難度：小（部分的な修正で解決可能）

問題

パーサーを書いていて、同じコードが増えてきたので抽象化しようとまとめていた時のことです。

基底クラスと同じ名前の関数を作る場合、usingで派生クラスにも持ってこないとオーバーロードではなく、オーバーライドのようになります。まず、これに注意する必要があります。

また、SFINAEを使った振り分けを行う場合、同じ形の関数を二個書くことがありますが、常に片方がSFINAEの文脈でのエラーになるなら、問題なく動作するはずです。

しかし、以下の条件を満たす場合、gccではコンパイルできるのにclangではコンパイルができません。どちらが正しいのかはよくわかりませんが、両方SFINAE的エラーが発生しなかった時に「あいまい」とは言われない（派生クラスの方が優先される）ことを考えると、clangが正しそうな気もします。

  • 派生クラスで、基底クラスと完全に同じ形の関数を定義する
  • 基底クラスの関数は、usingで派生クラスに持ってくる
  • 派生クラスの方の関数は、SFINAEの文脈でエラーになる
  • つまり、持ってきた基底クラスの方の関数が選ばれてほしい

実行例

#include <type_traits>

struct Base {
    template<class... Args>
    static char f( Args... );
};

struct Derived : Base {
    using Base::f;

    template<class... Args>
    static auto f( Args... args ) -> decltype( Unknown( args... ) );
};

int main() {
    using Type = decltype( Derived::f( 1 ) );
    static_assert( std::is_same<Type, char>::value, "" );
    Type a;
}

解決策

  • 完全に同じ形の関数を書かなければよいので、たとえば以下のように変更すればよいです。
// Before
template<class... Args>
auto func( Args... ) -> ...;

// After
template<class T, class... Args>
auto func( T, Args... ) -> ...;

引数が0個の場合を許容する場合は、手間がかかりますが引数0の関数を別に作成すればよいです。 他の形の場合でも、いろいろやり方はあると思います。暗黙変換が必要ない場合は、Tで受け取ってtypename std::enable_if<std::is_same<T, int>::value, std::nullptr_t>::type = nullptrなどとSFINAEで制限すると実質的に同じ引数を持つ関数を定義できます。暗黙変換が必要な場合は、一般的な解法はないように思われますが、暗黙変換を担う関数と、オーバーロード振り分けを行う関数の二段に分離するなどの方法が考えられます。

4. 可変長テンプレートに引数を渡し忘れる

  • 重大度：小（ただのミス）

問題

可変長テンプレートに引数を渡し忘れると、それ自体は文法違反ではないので、SFINAEの文脈でそれをやってしまうとエラーにならずに発見が困難になりました。

UnaryTokenRule<lr_unary_increment, '+','+'>

と書くべきところを、

UnaryTokenRule<lr_unary_increment>

と書いてしまっていたのでした。

5. elipsisの優先順位

  • 重大度：小（ただのミス）
  • 解決困難度：小（容易に解決可能）

問題

関数の型チェックのコードを書いていた時のことです。

次のコードは、オーバーロード解決があいまいになります。なんで優先順位が同じなのでしょうか……？

int f();
char f(...);

int main() {
    decltype( f() ) a;
}

解決策

  • C++11以降が使えるなら、可変長テンプレートを使うのが"現代流"です。優先順位も意図通りになります。

6. SFINAEではない

  • 重大度：小（ただのミス）
  • 解決困難度：小（容易に解決可能）

問題

型宣言をパースするコードを書いている時のことです。C言語の型宣言は複雑で、構文木の上の方に出現するのは、使った時に得られる型です。重要なのはその変数の使い方（これはポインタなのか配列なのか関数なのか？）なのですが、その情報は構文木の最下層に出現します。そのため、再帰的に情報を収集する必要がありました。

再帰的に情報を集めるのを以下のように行い、SFINAEの文脈で使おうと思うのは間違いです。

template<class T>
struct Traits<Wrapper<T>> { using type = typename Traits<T>::type; };

// SFINAEを行う
template<class T, typename Traits<T>::type = nullptr>
auto f( T ) -> ...;

実行例

解決策

7. 非型パラメータの型の推論

問題

これもパーサーを書いていて、同じコードが増えてきたので抽象化しようとまとめていた時のことです。

テンプレートテンプレートパラメターの中に非型テンプレート引数が含まれるとき、その型を取得したいという状況がありました。というか言葉で伝えるのには無理があるのですが、以下のようなことがしたいということです。

template<class T, template<T>class U, T N>
void f( U<N> ) { std::cout << N << std::endl; }

残念ながらTを推論することができません。しかし、最近のコンパイラで-std=c++1z以降を指定するとコンパイルできるのです。そんな新機能の追加ありましたっけ……？もしかすると、非型テンプレートとしてauto型が使えるようになったことと関係があるのでしょうか……？

実行例

解決策

  • gcc7.1.0以降か、clang4.0.0以降で、-std=c++1z以降を指定する

8. オーバーロード解決時に、不要なテンプレートがインスタンス化される

  • 重大度：大（未規定の挙動）
  • 解決困難度：大（設計の大幅な見直しが必要）

問題

コンパイラに意図しない入力が入ってきたとき、「マッチするオーバーロード関数がありません」で終わらせてもいいのですが、static_assertでメッセージを出力しつつ落とすほうが親切ですし、デバッグも楽です。そのため、以下のようにマッチする関数がない場合はなるべく落とすようにしました。

template<std::nullptr_t N = nullptr>
struct Error { static_assert( N != nullptr, "error!" ); };

auto f( int ) -> int;
auto f( ... ) -> Error<>;

ここで、Errorクラスをわざわざテンプレートにしているのは、テンプレートのインスタンス化を遅らせないと、常にstatic_assertがかかってしまうためです。static_assertの条件式を依存式にする必要があります。

それはいいのですが、なんとこの手法は未既定の挙動を含んでいるというのです！オーバーロード解決時、そのオーバーロードを解決するのに必要ないテンプレートのインスタンス化は、してもしなくてもいいことになっています。そのため、上記のコードはたとえ上のオーバーロード関数が呼ばれる状況であっても、Error<>をインスタンス化する可能性があります。

幸いgccやclangはそのような動作をしません。gccやclangの挙動を観察してみたところ、「上記のような、関数の返り型等、不完全型でよい文脈ではテンプレートのインスタンス化をしない」、「完全型が要求される文脈（関数の実引数等）で使われたらテンプレートのインスタンス化を行う」という法則に従っていると思われます。

実行例

template<bool B = false>
struct Error { static_assert( B, "error!" ); };

template<class T>
char wrap( T );

template<class T>
auto raise( T ) -> Error<>;

int f( int );

template<class T>
auto f( T ) -> decltype( wrap( raise( 0 ) ) );

int main() {
    decltype( f(0) ) obj;
}

解決策

  • オーバーロード解決の時だけ問題になるので、オーバーロードの振り分けを使うのではなく、構造体の部分特殊化で振り分けを行うと解決します
  • 未規定の挙動ではありますが、gccやclangの評価戦略の範囲においては、返り型のdecltype内でネストした関数呼び出しをしない場合問題になりません

Thanks!

この原因を究明されたのは、nus氏でした。ありがとうございました！！

twitter.com

9. 可変長引数テンプレートのマッチングバグ

  • 重大度：大（clangでコンパイルできない）
  • 解決困難度：中（設計の見直しが必要）

問題

この問題は8. の直後に発生しました。というか、8. が解決した後に発生したから原因を突き止められたものの、同時に発生していたら解決は不可能だったのではないでしょうか……。

さて、先ほどの8. の問題は、すべての関数テンプレートを実体化してみるという点に問題がありました。これは、優先順位とか以前に、完全に合わない形の関数テンプレートまでも実体化しているのです。そのせいで、以下のようなコードもエラーになります。

int f( int );
template<class T, class U>
auto f( T, U ) -> decltype( wrap( raise( 0 ) ) );

f( 0 ); // static_assertに引っかかる

さて、テンプレート引数のTやUは推論できるはずがありませんから、これに触ることでSFINAE的エラーを誘発できるはずです。

int f( int );
template<class T, class U>
auto f( T, U ) -> decltype( wrap( raise( T{} ) ) );

f( 0 ); // 問題なく動作する

ここまでは、常識的な挙動です。しかし、関数の引数ではなくテンプレートの引数でこれを行うと、clangはわけのわからないことを言い出します。

template<class T, bool B = false>
struct Error { static_assert( B, "error!" ); };

template<class... Ts>
struct Tuple {};

template<class T>
char wrap( T );

template<class T>
auto raise() -> Error<T>;

template<class T, class U>
int f( Tuple<T, U> );

template<class T>
auto f( Tuple<T> ) -> decltype( wrap( raise<T>() ) );

int main() {
    decltype( f( Tuple<float, double>{} ) ) obj;
}

これを実行すると、clangでのみstatic_assertに引っかかりエラーになります。どうやら、Error<float, nullptr>をインスタンス化しているようです。Tuple<float, double>をTuple<T>にマッチさせてTを推論することはできないはずです。勝手に同じ位置の物を持ってきてしまっているのでしょうか。

実行例

解決策

  • 基本的に8. の問題と同時に発生するので、同様の対処法が有効です

さいごに

少しでもバグに直面したテンプレートメタプログラマのお役にたてれば幸いです。 ただ、バグへの対処方法はまとめましたが、根本的な原因はわかっていません。 バグの原因がわかる方がいらっしゃいましたら、ぜひ教えてください……。

ltmpcのはなし

C++のテンプレートメタプログラミングによるコンパイル時C言語コンパイラ、「ltmpc」を作っています。 やっとコードが生成できるようになったので、今日はそのはなしを書こうと思います。

動くものが見たい！

GitHub - lpha-z/ltmpc: C++11TMP compile time C compiler

はじめに

世の中には、プログラムを書くこと自体が難しいような、難解言語と呼ばれるものがあります。難解言語は何かを効率化するためにはあまり役に立ちませんが、その魅力から意外と愛好者がいるようです。

難解言語は手で書くのが難しいため、自動生成しようとの試みがよく起きます。それを推し進めたものとして、去年、ELVMというコンパイラ基盤が出現しました。

ELVM Compiler Infrastructure について - 兼雑記

これは、いきなりC言語ソースから難解言語ソースを生成するのではなく、途中に中間層をはさみ、フロントエンド・バックエンド構成としたものです。バックエンドは、各難解言語ごとに作る必要がありますが、フロントエンドの出力はかなり小さい命令セットを持った仮想機械語になっているので、バックエンドを制作するときは、それらの機械語だけを難解言語に落とし込めればよいということになります。この方法により、C言語を難解言語に変換することがより簡単になりました。

そして、多くの人が自分の好きな難解言語バックエンドを追加していった結果、平易なC言語で書かれたC言語コンパイラ8ccを変換することにより、非常に多くの難解言語上でC言語のコンパイラが動くようになったのでした。

Cコンパイラをスクラッチから開発してみた（日記） - Qiita

C言語のコンパイラが動く難解言語のうちには、C++14constexprもあります。これも去年非常に話題になりました。

コンパイル中にコンパイルする「コンパイル時Cコンパイラ」をつくった話 - kw-udonの日記

C++にはテンプレートという機能もあります。テンプレートはコンパイル時に処理されるのですが、おそろしいことに、コンパイル時の型の計算のみでチューリング完全になっています。 これを使ってコンパイル時にいろいろと計算することをテンプレートメタプログラミング(TMP)と呼んでいます。もちろんTMPは実用的な計算をするための言語ではないので、難解言語と言ってもいいでしょう。さて、それではTMPでC言語コンパイラは動くのでしょうか？

残念ながら、ELVMのC++TMPバックエンドでは、C言語のコンパイラを動かすことは叶いませんでした。これについては、上のブログで考察されているように、TMPにはメモリを開放する方法が一切なく、メモリ使用量が非常に大きくなってしまうことが原因です。

それでも、TMPでC言語がコンパイルしたい

TMPは純粋関数型言語なので、C言語のような手続型のコードを変換するのはそれなりに大変です。ELVMのC++TMPバックエンドでは、Store-passing Styleを用いることでこの問題を解決しようとしていますが、この自動生成コードをコンパイルすると非常にメモリを消費します。これは、一変数だけ変更する時、他の部分は全く書き換わらないのにもかかわらず、全てコピーする必要があるからです。普通の関数型言語でよく使われるリスト(イミュータブルな単方向連結リスト)において、末尾の要素だけを変更したリストを作ることが高くつくことと似ています。しかし、普通の関数型言語においては時間的には高くつきますが、ガベージコレクション(GC)が働くため、空間的にはそれほど問題になりません。ところが、TMPではいったんテンプレートがインスタンス化されるとコンパイルが終了するまで残ってしまうため、空間的にも非常に高くつくことになります。

よくよく考えると、これらのコードはテンプレートメタプログラミングの機能を生かし切れていません。たとえば、TMPには組み込みでパック展開というものが存在します。パック展開で一気に処理をすることができれば、テンプレートのインスタンス化量が激減するため、メモリ使用量の問題を解決できるかもしれません。

パック展開は関数型言語のmap関数のようなことができます。部分特殊化を使えば、パターンマッチングをすることだってできます。そう、TMPには関数型言語的な気の利いた機能がたくさんあるのです。 C言語を変換するという作戦ではなく、最初から純粋関数型言語っぽく、C言語のコンパイラを書けば、もしかしたら、TMPでもC言語のコンパイラが作れるのではないでしょうか……？

ということを9月ごろに思ってから、ちまちまと作り続けて、

ついに動きました！

ようやく今朝コンパイルができるようになりました！

なんとか、アドベントカレンダーに間に合いましたね……。

ltmpcの中身の紹介

本当はこれも書きたかったんですが、今日はとても疲れてしまったので、明日以降に書きましょう。

なんか内容がとても少ない記事になってしまった。プログラマはコードで語る、ということにしておきましょう。