このブログは、旧・はてなダイアリー「檜山正幸のキマイラ飼育記 メモ編」(http://d.hatena.ne.jp/m-hiyama-memo/)のデータを移行・保存したものであり、今後(2019年1月以降)更新の予定はありません。

今後の更新は、新しいブログ http://m-hiyama-memo.hatenablog.com/ で行います。

ウッギャーッ!! テンプレートを忘れてた

もう、なにやっているんだぁーーー、俺はぁ。見つけたミッシングピースをまた置き忘れている。バッカじゃないの。

ソート付きプレイスホルダーを持つテンプレートとコンテキストを使うべし!使うべし!使うべし!

非終端記号という変な概念にまっとうな定式化を与える。ソート付き変数をプレイスホルダーだと定義して:

  • すべての変数名が違うときはソートだけを指定すればいい。
  • あるいは、出現場所が変数名の代わりをすると考える。
  • 同じ変数名であることは、何か特別な方法で指定する。
  • 変数名を番号として、1から順に使う約束をする。

などで、従来の非終端記号をエミュレートできる。←少しウソ入っている。

テンプレート(テンプレートインスタンス)とは、ソート付き変数を含む項に過ぎないが、「テンプレート」とか「フォーム」と言い換えると言語理論的な解釈がしやすくなる。そして、コンテキストがKleisli射と解釈できる。テンプレート置換がKleisli結合になる。

おっと、定義; Xをソート付き変数集合として、指標Σのテンプレート・インスタンスの集合TIΣ(X)は、事実上変数を含む項集合に過ぎない。その例は、線形文形式(linear sentential form; 右端だけにプレイスホルダーがある列)。TIΣモナドになる、そのKleisli射が重要。

TIΣのKleisli射は、単純な文法(テンプレート文法/パターン文法と呼ぶといいかも)でもあり、図式化すると構文図になる。図式(グラフ)的にトレースをいれて、トレース付き圏にできる。さらに、木下のベキ圏構成を使えば“言語の圏”ができる。以上の構成以外に、Pow(TIΣ(-)) というモナドを作って、これのKleisli圏を作る方法もあるが、2つの構成は一致するはずだ。

これらの概念で、構文図、境界付き有向グラフが実はテンプレート・コンテキスト=Kleisli射であることがわかり、ベキ構成(hom-setスタイル/モナドス・タイル)により、新しい圏ができる。新しい圏は、テンプレート言語圏と呼んでもよいだろう。ベキ構成を使っているので、テンプレート言語圏はorder-enrichedになっている。

つまり、テンプレート言語圏TLは、OrdやΩΟに対して“具象的”である。よって、具象表現の枠組みが適用できて、TLをTL上の具象(余)層で表現することができる。

一方で、テンプレート言語モナドと文法モナドのあいだに作用積が定義できて(重畳モナド構造)、Klesili圏がoverlapする現象が生じる。2つのKleisli圏のoverlapからindexed categoryが定義できて、その平坦化も定義できる。

基礎(ground)インスタンス/基礎言語は、テンプレートインスタンス/テンプレート言語のなかに埋め込める。よって、テンプレートインスタンスの圏とテンプレート言語の圏を考えれば十分。基礎(ground)が欲しいなら、空変数集合上で局所的な議論をすればよい。

境界付き有向グラフに極性を入れて考えれば、「正規言語のreverse問題」が解けるかもしれない。射f:A→Bに対して、f*:B*→A*が定義できればいい。偏極アルファベット上のタプルをプレイスノードとするペトリネットを考えればいいような気がする。トランジションノードが射だ。双対は、プレイスノードの極性反転とトランジションンの逆転ができればいい。生成規則と遷移規則が、ある種の双対になっている理由も説明できるかもしれない。

とにかく、とにかく、とにかく、非終端記号をまっとうな定式化に置き換えて、テンプレートインスタンスを境界付きグラフ(ペトリネット)で表現し、ベキ構成をマジメに考えよう。