Inside Pattern Matchings

2018-09-16

# Inside Pattern Matchings
----------------------
[ML Day #2](https://ml-lang.connpass.com/event/94284/)

===
# About Me
---------
![κeenのアイコン](/images/kappa.png)

* κeen
 * [ちゅーんさんだよー](https://shindanmaker.com/789932)
 * [@blackenedgold](https://twitter.com/blackenedgold)
 * Github: [KeenS](https://github.com/KeenS)
 * [Idein Inc.](https://idein.jp/)のエンジニア
 * Lisp, ML, Rust, Shell Scriptあたりを書きます

===

<pre>
( ^o^)パターンマッチって便利だなー
( ˘⊖˘) 。o(待てよ？なんでこんなに簡単にコードが書けるんだ)
|コンパイラ|┗(☋｀ )┓三
( ◠‿◠ )☛そこに気づいたか・・・消えてもらう
▂▅▇█▓▒░(’ω’)░▒▓█▇▅▂うわああああああ
</pre>
<p>===</p>
<h1 id="発表について">発表について</h1>
<hr>
<ul>
<li>元ネタ <a href="http://pauillac.inria.fr/~maranget/papers/opat/">Optimizing Pattern Matching</a> (Fabrice Le Fessant, Luc Maranget)</li>
<li>自作SMLコンパイラにパターンマッチを入れようとしたら難しかった
<ul>
<li>「コードを生成」が割と厄介</li>
<li>次の中間言語の設計に影響を与える
<ul>
<li>というか専用の中間言語作るくらいの心意気が必要</li>
</ul>
</li>
</ul>
</li>
</ul>
<p>===</p>
<h1 id="発表について-1">発表について</h1>
<hr>
<ul>
<li>既存手法を調べたら非自明だった
<ul>
<li>→ 既存手法の紹介だけでも価値がありそう</li>
<li>→ 発表するか</li>
<li>(本当は実装までしたかったけど進捗だめです)</li>
</ul>
</li>
<li>変数束縛の話はしない
<ul>
<li>ワイルドカードで我慢して</li>
</ul>
</li>
</ul>
<p>===</p>
<h1 id="パターンについて">パターンについて</h1>
<hr>
<ul>
<li>パターンは値の集合にマッチする</li>
<li>ワイルドカードパターンがある</li>
<li>直積にマッチするときは <em>横</em> に伸びる</li>
<li>直和にマッチするときは <em>縦</em> に伸びる</li>
<li>パターンをネストするときは <em>奥</em> に伸びる</li>
<li>パターンが <em>網羅的</em> であるかに関心がある</li>
<li>複数マッチする場合は最初のものにマッチする</li>
</ul>
<p>===</p>
<h1 id="例">例</h1>
<hr>
<pre tabindex="0"><code class="language-standard-ml" data-lang="standard-ml">case (lx, ly) of
   ([], _) => 1
 | (_, []) => 2
 | (x::xs, y::ys) => 3
</code></pre><p>===</p>
<h1 id="パターンマッチの実装">パターンマッチの実装</h1>
<hr>
<ul>
<li>いくつか方法がある
<ul>
<li>素朴なifのチェーン</li>
<li>decision tree</li>
<li>backtracking automata</li>
</ul>
</li>
<li>それぞれメリットデメリットがある</li>
</ul>
<p>===</p>
<h1 id="ifのチェーン">ifのチェーン</h1>
<hr>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-C" data-lang="C"><span class="line"><span class="cl"><span class="k">if</span> <span class="p">(</span><span class="n">lx</span> <span class="o">==</span> <span class="p">[]</span> <span class="o">&&</span> <span class="nb">true</span><span class="p">)</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">  <span class="k">return</span> <span class="mi">1</span><span class="p">;</span>
</span></span><span class="line"><span class="cl"><span class="p">}</span> <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="nb">true</span> <span class="o">&&</span> <span class="n">ly</span> <span class="o">==</span> <span class="p">[])</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">  <span class="k">return</span> <span class="mi">2</span><span class="p">;</span>
</span></span><span class="line"><span class="cl"><span class="p">}</span> <span class="k">else</span> <span class="k">if</span> <span class="p">(</span><span class="n">lx</span> <span class="o">==</span> <span class="p">(</span><span class="o">::</span><span class="p">)</span> <span class="o">&&</span>  <span class="n">ly</span> <span class="o">==</span> <span class="p">(</span><span class="o">::</span><span class="p">))</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">  <span class="c1">// discriminantとデータは別
</span></span></span><span class="line"><span class="cl"><span class="c1"></span>  <span class="n">x</span> <span class="o">=</span> <span class="n">lx</span><span class="mf">.0</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">  <span class="n">xs</span> <span class="o">=</span> <span class="n">lx</span><span class="mf">.1</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">  <span class="n">y</span> <span class="o">=</span> <span class="n">ly</span><span class="mf">.0</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">  <span class="n">ys</span> <span class="o">=</span> <span class="n">ly</span><span class="mf">.1</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">  <span class="k">return</span> <span class="mi">3</span><span class="p">;</span>
</span></span><span class="line"><span class="cl"><span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">  <span class="c1">// match fail
</span></span></span><span class="line"><span class="cl"><span class="c1"></span><span class="p">}</span>
</span></span></code></pre></div><p>===</p>
<h1 id="ifのチェーン-1">ifのチェーン</h1>
<hr>
<ul>
<li>パターンを1つ1つifで検査する</li>
<li>最初に思いつく</li>
<li>O 素朴</li>
<li>O 実装が楽</li>
<li>X 遅い(横、縦、深さ全てに比例)</li>
<li>X 網羅性検査は別途実装</li>
</ul>
<p>===</p>
<h1 id="decision-tree">decision tree</h1>
<hr>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-C" data-lang="C"><span class="line"><span class="cl"><span class="nf">swith</span><span class="p">(</span><span class="n">lx</span><span class="p">)</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">  <span class="k">case</span> <span class="p">[]</span><span class="o">:</span> <span class="k">return</span> <span class="mi">1</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">  <span class="k">case</span> <span class="p">(</span><span class="o">::</span><span class="p">)</span><span class="o">:</span> <span class="k">switch</span> <span class="p">(</span><span class="n">ly</span><span class="p">)</span> <span class="p">{</span>
</span></span><span class="line"><span class="cl">    <span class="k">case</span> <span class="p">[]</span><span class="o">:</span> <span class="k">return</span> <span class="mi">2</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">    <span class="k">case</span> <span class="p">(</span><span class="o">::</span><span class="p">)</span><span class="o">:</span> <span class="k">return</span> <span class="mi">3</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">  <span class="p">}</span>
</span></span><span class="line"><span class="cl"><span class="p">}</span>
</span></span></code></pre></div><p>===</p>
<h1 id="decision-tree-1">decision tree</h1>
<hr>
<ul>
<li>パターンから決定木を作る
<ul>
<li>直和は <code>switch</code> に変換する</li>
<li>直積は <code>switch</code> のネストに変換する</li>
<li>パターンのネストは<code>switch</code>のネストに変換する</li>
</ul>
</li>
<li>ifのチェーンの次に思いつく</li>
<li>O 実行が(横幅と深さに)線形</li>
<li>O 網羅性検査がfor freeでついてくる</li>
<li>X コードが嵩む(パターンがコピーされうる)</li>
</ul>
<p>===</p>
<h1 id="decision-tree-2">decision tree</h1>
<hr>
<ul>
<li>最初に実装しようとした</li>
<li>パターンがネストしたケースで実装が難しかった
<ul>
<li>主にデータの持ち方の問題</li>
<li>1つの節の中にネストさせるパターンを集めるのが大変</li>
</ul>
</li>
<li>直積とパターンのネストどっちを先にやるかは調べてない</li>
<li>ORパターンを入れるとdecision diagramになりそう？
<ul>
<li>CFGが欲しくなる</li>
</ul>
</li>
</ul>
<p>===</p>
<h1 id="backtracking-automata">backtracking automata</h1>
<hr>
<pre tabindex="0"><code>catch
  catch
    switch lx with
      case []: 1
      default: exit
  with catch
    switch ly with
      case []: 2
      default: exit
  with catch
    switch lx with
      case (::): switch ly with
                   case (::): 3
                   default: exit
      default: exit
with (failwith "Patrtial match")
</code></pre><p>===</p>
<h1 id="backtracking-automata-1">backtracking automata</h1>
<hr>
<ul>
<li>順番に検査しつつ失敗したら巻き戻す
<ul>
<li>パターンの並びのままprefixが共通なら共有する</li>
<li>例外とハンドラを使う</li>
</ul>
</li>
<li>O コードがコンパクト(パターンはコピーされない)</li>
<li>X decision treeほど速くない</li>
<li>O 最適化ができる
<ul>
<li>まずは動くものを作ってあとで高速化</li>
</ul>
</li>
</ul>
<p>===</p>
<h1 id="backtracking-automata-2">backtracking automata</h1>
<hr>
<ul>
<li>今回紹介する内容</li>
<li>DT vs BA</li>
<li>少し正規表現のDFA vs NFAに似てる
<ul>
<li>ただしパターンマッチはコード生成の話</li>
</ul>
</li>
<li>Backtracking Automataを最適化するとそれなりに速い</li>
</ul>
<p>===</p>
<h1 id="イメージ">イメージ</h1>
<hr>
<h2 id="if">if</h2>
<pre tabindex="0"><code>.-.-
.-.-
.-.-
.-.-
</code></pre><p>===</p>
<h1 id="イメージ-1">イメージ</h1>
<hr>
<h2 id="dt">DT</h2>
<pre tabindex="0"><code>   /
  .
 / \
.
 \./
   \
</code></pre><p>===</p>
<h1 id="イメージ-2">イメージ</h1>
<hr>
<h2 id="ba">BA</h2>
<pre tabindex="0"><code>.-.-
   \
.-.-
   \
</code></pre><p>===</p>
<h1 id="準備">準備</h1>
<hr>
<h2 id="データ">データ</h2>
<ul>
<li>データは直和と直積からなるとする
<ul>
<li>intも無限の直和からなるとする</li>
</ul>
</li>
<li>値はコンストラクタで作られる
$v ::= c(v1, .., vn)$</li>
<li>パターンへの入力はベクトルで与えられる
$\vec{v} = (v_1 \cdots v_n)$</li>
</ul>
<p>===</p>
<h1 id="準備-1">準備</h1>
<hr>
<h2 id="パターン">パターン</h2>
<ul>
<li>パターンは2つ $p ::=$
<ul>
<li>$\mathbf{\_}$ (ワイルドカード)</li>
<li>$c(p_1, .., p_n)$ (コンストラクタ)</li>
</ul>
</li>
<li>パターンもベクトルになる
$\vec{p} = (p_1 \cdots p_n)$</li>
</ul>
<p>===</p>
<h1 id="準備-2">準備</h1>
<hr>
<h2 id="節行列">節行列</h2>
<ul>
<li>パターンは節が複数あるので行列になる</li>
</ul>
<pre tabindex="0"><code class="language-standard-ml" data-lang="standard-ml">case (lx, ly) of
   ([], _) => 1
 | (_, []) => 2
 | (_::_, _::_) => 3
</code></pre><p>を</p>
<p>\[
\begin{equation*}
(P \to L) = \begin{pmatrix}
[] & \mathbf{\_}  & → & 1 \\<br>
\mathbf{\_} & [] & → & 2 \\<br>
(::) & (::) & → & 3
\end{pmatrix}
\end{equation*}
\]</p>
<p>に</p>
<p>===</p>
<h1 id="準備-3">準備</h1>
<hr>
<h2 id="ターゲット言語">ターゲット言語</h2>
<ul>
<li><code>let</code>バインディング</li>
<li><code>catch l1 with l2</code> と <code>exit</code></li>
<li><code>switch</code> 式
<ul>
<li><code>default</code> 節は省いて良い</li>
<li>定義上は<code>case</code> に引っかからず <code>default</code> もなければUB</li>
<li>実際はそういうコードを吐かない</li>
</ul>
</li>
<li>フィールドアクセス <code>field n x</code></li>
</ul>
<p>===</p>
<h1 id="コンパイル">コンパイル</h1>
<hr>
<ul>
<li>値 $\vec{x}$ を節行列 $P \to L$ にマッチさせるとする</li>
<li>手続き $\mathcal{C}((x), P \to L)$ でコンパイルする</li>
<li>$\vec{x} = (x_1 \cdots x_n)$</li>
<li>\[
\begin{equation*}
(P \to L) = \begin{pmatrix}
p^1_1 & \cdots & p^1_n & → & l^1 \\<br>
&        & \vdots &  &  \\<br>
p^m_1 & \cdots & p^m_n & → & l^m
\end{pmatrix}
\end{equation*}
\]</li>
</ul>
<p>===</p>
<h1 id="コンパイル-1">コンパイル</h1>
<hr>
<ul>
<li>ただしパターンは少なくとも1つはあるとする
<ul>
<li>つまり $m > 0$</li>
</ul>
</li>
<li>節なしマッチは許可されない or 特別扱いが多いので一般性を損ねない</li>
<li>最初はマッチ失敗のガードから始める</li>
</ul>
<pre tabindex="0"><code class="language-standard-ml" data-lang="standard-ml">catch
  C((x), P → L)
with (failwith "Patrtial match")
</code></pre><p>===</p>
<h1 id="n--0">$n == 0$</h1>
<hr>
<ul>
<li>$n$ が0、つまりパターンが残っていなければ最初のパターンがマッチする</li>
</ul>
<p>\[
\begin{equation*}
\mathcal{C}((), \begin{pmatrix}
→     & l^1 \\<br>
\vdots &  \\<br>
→     & l^m
\end{pmatrix}) = l^1
\end{equation*}
\]</p>
<p>===</p>
<h1 id="n--0-1">$n > 0$</h1>
<hr>
<h2 id="a変数則">(a)変数則</h2>
<ul>
<li>最初の列のパターンが全てワイルドカードならマッチさせない。つまり
$\mathcal{C}(\vec{x}, P \to L) = \mathcal{C}(\vec{x^{\prime}}, P^{\prime} \to L^{\prime})$</li>
<li>$\vec{x^{\prime}} = (x_2 \cdots x_n)$</li>
<li>\[
\begin{equation*}
(P \to L) = \begin{pmatrix}
p^1_2 & \cdots & p^1_n & → & l^1 \\<br>
&        & \vdots &  &  \\<br>
p^m_2 & \cdots & p^m_n & → & l^m
\end{pmatrix}
\end{equation*}
\]</li>
</ul>
<p>===</p>
<h1 id="n--0-2">$n > 0$</h1>
<hr>
<h2 id="bコンストラクタ則">(b)コンストラクタ則</h2>
<ul>
<li>最初の列のパターンが全てコンストラクタならコンストラクタ毎に分解する</li>
<li>雑にいうとこうなる</li>
</ul>
<pre tabindex="0"><code>switch x1 with
  case c1: C(...)
  case c2: C(...)
     ...
  default: exit
</code></pre><p>===</p>
<h1 id="n--0-3">$n > 0$</h1>
<hr>
<h2 id="bコンストラクタ則-1">(b)コンストラクタ則</h2>
<ul>
<li>コンストラクタ $c$ に特殊化された節行列$\mathcal{S}(c, P \to L)$を次のように定義する
<ul>
<li>$p^i_1 = c(q^i_1, \cdots, q^i_a)$のとき$q^i_2 \cdots q^i_a p^i_2 \cdots p^i_n \to l^i$</li>
<li>$p^i_1$ が $c^{\prime} \not= c$ のときナシ</li>
</ul>
</li>
<li>各コンストラクタの腕を以下のようにする</li>
</ul>
<pre tabindex="0"><code>(let (y_1 (field 0 x_1)) ... (y_a (field (a-1) x_1))
  C((y_1, ..., y_a, x_2, ..., x_n), S(c, P → L)))
</code></pre><p>===</p>
<h1 id="n--0-4">$n > 0$</h1>
<hr>
<h2 id="c-orパターン則">(c) ORパターン則</h2>
<ul>
<li>ORパターンは扱わないので飛ばす</li>
<li>元論文だとORパターンの最適化も扱っており重要</li>
</ul>
<p>===</p>
<h1 id="n--0-5">$n > 0$</h1>
<hr>
<h2 id="d-混合則">(d) 混合則</h2>
<ul>
<li>上記どのルールにも当てはまらない場合は節行列を2分割する
<ul>
<li>先頭から(a), (b), (c)のどれかが適用できる最大の集合を前半、残りを後半とする</li>
</ul>
</li>
<li>コードは以下のように生成する</li>
</ul>
<pre tabindex="0"><code>catch
  C(\vec{x}, P_1 → L_1)
with C(\vec{x}, P_2 → L_2)
</code></pre><p>===</p>
<h1 id="例-1">例</h1>
<hr>
<pre tabindex="0"><code class="language-standard-ml" data-lang="standard-ml">case (lx, ly) of
   ([], _) => 1
 | (_, []) => 2
 | (x::xs, y::ys) => 3
</code></pre><p>===</p>
<h1 id="例-2">例</h1>
<hr>
<ul>
<li>混合則を2回適用する</li>
</ul>
<pre tabindex="0"><code class="language-standard-ml" data-lang="standard-ml">catch
  catch
    C((lx ly), ([] _ → 1))
  with catch
    C((lx ly), (_ [] → 2))
  with C((lx ly), (x::xs y::ys → 3))
with (failwith "Patrtial match")
</code></pre><p>===</p>
<h1 id="例-3">例</h1>
<hr>
<ul>
<li>順にコンストラクタ則、変数則、コンストラクタ則を適用する</li>
</ul>
<pre tabindex="0"><code>catch
  catch
    switch lx with
      case []: C((ly), (_ → 1))
      default: exit
  with catch
      C((ly), ([] → 2))
  with switch lx with
         case (::): C((ly), (y::ys → 3))
         default: exit
with (failwith "Patrtial match")
</code></pre><p>===</p>
<h1 id="例-4">例</h1>
<hr>
<ul>
<li>順に変数則、コンストラクタ則、コンストラクタ則を適用する</li>
</ul>
<pre tabindex="0"><code>catch
  catch
    switch lx with
      case []: C((), (→ 1))
  with catch
    switch ly with
      case []: C((), (→ 2))
      default: exit
  with switch lx with
         case (::): switch ly with
                      case (::): C((), (→ 3))
                      default: exit
with (failwith "Patrtial match")
</code></pre><p>===</p>
<h1 id="例-5">例</h1>
<hr>
<ul>
<li>n == 0のケースで終了</li>
</ul>
<pre tabindex="0"><code>catch
  catch
    switch lx with
      case []: 1
      default: exit
  with catch
    switch ly with
      case []: 2
      default: exit
  with switch lx with
         case (::): switch ly with
                      case (::): 3
                      default: exit
         default: exit
with (failwith "Patrtial match")
</code></pre><p>===</p>
<h1 id="最適化概要">最適化(概要)</h1>
<hr>
<ul>
<li>初手3分割だった</li>
<li>2節目と3節目が入れ替わってたら2分割で済んでた</li>
<li>勝手に入れ替えればいいのでは？
<ul>
<li>ただしマッチの順番を変えてはいけない</li>
</ul>
</li>
<li>→ マッチの順番を変えずに入れ替えられる条件を調べよう</li>
<li>他にはバックトラックで遠くに飛ぶためにcatchにラベルを付けたり</li>
<li>続きは論文で</li>
</ul>
<p>===</p>
<h1 id="まとめ">まとめ</h1>
<hr>
<ul>
<li>パターンマッチには少なくとも3種類の実装があるよ</li>
<li>そのうちバックトラッキングのアルゴリズムを紹介したよ
<ul>
<li>変数とORパターンは紹介してないよ</li>
</ul>
</li>
<li>最適化もありうるよ
<ul>
<li>紹介してないよ</li>
</ul>
</li>
</ul>