- 著者
-
森 彰
松本 吉弘
- 雑誌
- 全国大会講演論文集
- 巻号頁・発行日
- vol.49, pp.11-12, 1994-09-20
Curienは,カルテシアン閉圏(cartesian closed category,以下,CCCと略す)の定義における普遍写像性を,圏論的結合子と呼ばれる特別な射に関する等式に翻訳し,この等式を書き換え規則とみなすことで,関数型言語の操作的意味が圏論を通じて与えられることを示唆した.特にCCCの圏論的結合子から型,すなわち定義域と値域に関する情報と,終対象に関する結合子を取り除いた代数系(C-モノイドと呼ばれる)を用いれば,型なしのラムダ計算を従来の項書換え系として扱うことができる.横内も独立して,型なしの場合に圏論的結合子の等式を書き換え規則として扱うことを提唱した.しかし圏の射はf:A→Bのように定義域Aと値域Bによって型付けられた存在であり,射の結合は一方の値域と他方の定義域が一致するような射の対に対してのみ部分的に定義される.個々の結合子についても,異なる対象の上で同様に作用し得るという多相的な性質を持っている.たとえ型なしのC-モノイドを扱うとしても,結合子に関する個々の等式がどのような計算的・意味論的性質に連係しているのかが明らかでないので,合流性や停止性といった項書換え系の性質を考察することが困難である.本稿では,まずCCCのための圏論的結合子とその等式を随伴関手から直接導き出し,自由圏を生成する逐次式計算系を定義する.そしてこの体系におけるカット除去を圏論的結合子の操作的意味として用いることを提案する.