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

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

上江州計算の応用範囲

Cが対称モノイド圏なら、ある程度上江州計算ができる。Xが全順序が入った型付き変数集合=型環境(型宣言の順序リスト)なら、上江州拡張CC[X]が作れるから、

  1. from-v射(上江州さんのv→射)としての変数を含む式
  2. 式のタプル
  3. to-v射(上江州さんのv←射)としての複数変数への同時代入文
  4. FreeVar(E)とちょうど同じ変数からなる変数リスト(x1, ..., xn)による上江州抽象 <x1, ..., xn | E>
  5. 同時代入文と変数を含む式を組み合わせたlet式

などが使える。さらに、Cが閉圏であれば、通常のラムダ抽象と適用が行える。

ふと気が付いたのだが、λは圏上のオペレータ(射に射を対応させる写像の族)だが、他のオペレータでも上江州計算が使える。具体的には、最小不動点オペレータμ、最大不動点オペレータν、トレース・オペレータτなどだ。

μx.f(a, x) とかτ(x, y).(u(x, y, t), v(x, u, t))などの表現に、射として直接的な意味を与えることができる。式の等式的な書き換え(変形)の健全性は、射の等しさや同型で定義できる。等式、不等式も、射のあいだの関係、さらには2-射として意味を与えることができるだろう。

CがωCPOなら、λもμもτも全部使える。λa.μx.f(a, x) とかも、I→[A, X]の射として直接解釈ができる(f:A×X→X, μx.f(a, x):[a]→X)。上江州計算を使えば、もっと具体的な計算が楽にできそうだ。

上江州拡張C[X]内では、from-v to-v射も定義できる。form-v to-v射は、[x1, ..., xn]→[y1, ..., xm]のような射で、上江州抽象すると基礎(自由変数を含まない)代入文になる。