この二つのプログラムでは、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)でできる文脈自由文法の判定

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

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

正規言語の認識

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

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

文字集合 $Σ$
状態集合 $Q=\left\{ q(0), ..., q(M-1) \right\}$
遷移関数 $δ: Q×Σ→Q$

入力文字列は長さ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)で済むということは、スタックの状態としてあり得るのがΟ(N^c)種類くらいしかないということです。これは、スタックに積む文字の種類がc個(A,B,C,...とします)あり、それが入り混じることはなく順番に現れる、という状態だと思われます。スタックの状態としてはAABBBBBBCCとか、BCCCとかしかありえなくて、ABACとかは無理だということです。こういうのを許すと、スタックの状態としてあり得るパターンがΟ(c^N)種類になります。

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

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

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

Lexer と PreLexer の説明

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

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

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

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: LexerとPreLexerについての解説