効率的な関数オーバーロード解決手続きの生成

• このページでは，次のような入出力を実現するアルゴリズムを解説する
  • 入力: 関数オーバーロードの引数リストのリスト
  • 出力: 最も効率的に関数オーバーロードを解決できるような手続き

• C++のオーバーロード関数をLuaに露出させる際に，Luaから呼び出された時の引数の型による動的なオーバーロード解決が必要になった

• 入力: $V \in \textbf{A}^{**}$
  • 符号アルファベット$\textbf{A}$
    • 終端シンボル$\$$を含む
  • $V$の要素は符号語
  • $V\neq \phi$
  • $\forall{v}\in V, v\neq \phi,$ $v$の最後の要素は終端シンボル$\$$
• 出力: 木$T$
  • $T$の枝は，シンボル$a\in \textbf{A}$
  • $T$の節点ノードは，整数値
  • $T$の葉ノードは，$v\in V$
  • 任意の$v^r\in V$について，任意の葉ノードを$v$としたとき，$\forall{\left<n, e\right>}, P\left(v^r,n,e\right)$，ならばその時に限り，$v^r=v$である
    • $\left<n, e\right>$は，根から葉ノード$v$までのパス$p^v$における，ノード$n\in p^v$と，$n$の次のノードへの枝$e\in \textbf{A}$である
      • ただし，$n$は$p^v$の最後の要素ではない
    • 命題$P(v^r, n, e): v^r_{n}=e$

1. 中間木$T'$を生成する
   • $T'$の枝は，シンボル$a\in \textbf{A}$
   • $T'$の節点ノードは，その深さを表す整数値
   • $T'$の葉ノードは，根からその葉まで辿る際に通る枝のシンボル列
   • $T'$のすべての葉ノードの集合は，$V$と等しい
2. $T'$から出力$T$を作成する
   • $T'$の全てのノードのうち，子ノードを1つだけ持つノード$x$と$x$から子ノードへ伸びる枝を，その子ノードで置換する

pythonのサンプルプログラム

• 任意の$v^r$について，次のことが言える
  • $T$の根から$P(v^r, n, e)$が真となるような枝を辿り
    • 葉$v$まで行き着いた場合，$v_r=v$，あるいは，$v_r\notin V$
    • 葉まで辿り着かなかった場合，$v_r\notin V$