線形論理のパラメトリック性

$ f: forall Aのような関数について自由パラメトリテイト定理を証明できるか? [A]⊸[A] $? $ f
$はリストをとり、常にその順列を返すと述べられています。

別の例:関数$ f: forall Aを証明する。 (A⊸(A、A))⊸[A]⊸[A]
$は常に1つの要素がコピーされた置換リストを返します。

ベストアンサー

さまざまな人々がこの種のことを証明することに興味があります。 Neel
Krishnaswamiは、この特定の定理をここで述べました。また、Frank
Pfenningが順序付けされたロジックのいくつかの素晴らしい例を見てきました。たとえば、$ A、x:[A]、y:[A]
vdash e:[A] $がある場合、順序付き型システムでは、$ e $はリスト$ x $および$ y
$を追加する必要があります。

短い答えは、はい、あなたの最初の例を証明できるということです。ラムダ計算の文脈において、論理的関係に基づくアプローチは、この論文。彼らはあなたの定理を2つのステップで証明するでしょう:

  1. タイプのリレーショナル解釈を定義し、それを使用して、直線性を完全に無視した従来のフリー定理、つまり「Theorems for
    Free!」のような本質的に同じ推論を使用することを証明します。与えられた$ vdash f: forall A。 [A]
    multimap [A​​] $、通常のフリー定理は$ f
    $が与えられたリストに存在する要素のみを含むリストを返すことを示しています。異なる自由な線形変数$ x_1 ldots x_n
    $のリストが与えられれば、$ f [x_1、…、x_n] $はいくつかのリスト$ [y_1、…、y_m]
    $に評価されると推論します。$ {y_1 、 ldots、y_m } subseteq {x_1、…、x_n }
    $。
  2. 評価中は、自由な線形変数を保存しなければならないことに注意してください。これにより、直線性を利用することができます。 $
    [y_1、 ldots、y_m] $が$ [x_1、…、x_n] $の順列でない場合、評価中にいくつかの$ x_i
    $が失われたり複製されたりすることはありません。 >

しかし、このような定理は、効果を持つ言語を見て、そのような言語のためにそれらを証明する能力が悲しいほど制限されているとき、より興味深いものになります。例えば、同型写像$
tau cong forall Aを考えてみよう。 ( tau 〜A)をシステムFのA
$に変更します。コールバイバリュー設定では、この同形が破損します私たちは非終了を追加します。しかし、類似の同型写像を線形型で復元できるはずです:$
tau cong forall A。 ( tau 〜A) multimap A
$です。残念ながら、我々はこれを証明できる運用上の論理的関係は持っていません。

つまり、この同型性とあなたの定理の両方を証明できる統語的方法もあります。これは、線形設定において特に有用なアプローチであると思われ、単純な定理を証明するための論理的関係を設定するよりもはるかに負担が少ない。

Edit: Since you asked, here’s an example of a
syntactic proof of a free theorem for the type $forall A . (A
otimes A) multimap A$ in a setting with a term $bot$ that loops
forever and is well-typed under any context at any type. The idea
is to find a set of canonical terms of a type and use that to
determine what the possible return values for a function are. We
start with a soundness theorem for well-typed terms.

Theorem (Canonicity). If $Delta; Gamma vdash
e : tau$ then either

  • $e approx v$, which is a value such that $Delta; Gamma
    vdash v : tau$.
  • $e approx n$, a term which is stuck because it is trying to
    use a free variable in $Gamma$, and $Delta; Gamma vdash n :
    tau$ OR
  • $e approx bot$

Here, $approx$ is your favorite notion of equivalence for the
language and $Delta$ is an environment containing free type
variables. I will consider free variables $x$ to be values. For
simple languages, a straightforward progress & preservation
argument can be made to justify this theorem.

さて、値$ vdash f: forall Aが与えられました。 (A otimes A) multimap A
$、我々は$ f approx lambda xを知っている。 e $ここで$ A; x:(A otimes A)
vdash e:A $です。 eのタイプから、可能なケースが2つあります。

  • $ e $はペア$ Aに相当します。 x:(A otimes A) vdash(v_1、v_2):A $です。 $
    v_1 $と$ v_2 $は自由型変数である$ A $型の値でなければならないので、このケースは不可能です。 $ A
    $型のコンテキストに変数がないため、このような値はありません。
  • $ e $は自由変数$ x $を使用しようとする用語に相当します。
  • $ e $が発散します。この場合は、$ f $:$ lambda xに対して可能な値が1つ与えられます。 bot
    $。

2番目のケースが残っているだけなので、$ A approx mathrm {let}(x_1、x_2)= x
mathrm {in} e ‘$ where $ A; x_1:A、x_2:A vdash e ‘:A
$です。これまでの証明では、$ f approx lambda xを確立しています。 mathrm {let}
(x_1、x_2)= x mathrm {in} e ‘$。最後に、もう一度正規化定理を適用して、$ e
‘$が分岐しなければならないことを見いだします。$ A $型の唯一の値は変数ですが、コンテキストには
2つの変数があります。 $ e ‘ approx x_i $の場合。

したがって、私たちは$ forall Aの唯一の住人です。 (A otimes A) multimap A $は$
lambda xです。 bot approx lambda x。 mathrm {let} (x_1、x_2)= x
mathrm {in} bot $。

あなたはこの種の証明のための参照を求めましたが、私は良いものについては分かりません。この種の推論は特定のサークルではよく知られており、おそらくGentzenまで戻っています。私はそれがシーケンシャルな微積分のための焦点を絞った証明検索を連想させると言われますが、私は接続が何であるかを正確にはわかりません。

つまり、私はこの比較的簡単な方法をうまく説明している現代の出版物を知らない。確かに、それはより単純な言語への適用性に少し制限がある。一方、私はそれが
“Theorems for Free!”などの影で覆われていると思う。その結果、多くの上級研究者でさえ、論理的関係を即座に考えると
“フリー定理”という言葉が聞こえる。そのようなプルーフに対するより簡単な代替アプローチ(特に、リニアタイプシステムの場合)。

あなたの2番目の例として、私は実際に望む自由定理を考えていません。たとえば、$ A $を整数型でインスタンス化し、$ f
$に渡すリストにない整数を返す関数を渡すことができます。 $ B multimap(B、B)) multimap [A​​]
multimap [A​​] $はあなたが気にしていたタイプに近いでしょう。しかしそれでも、B
multimap(B、B)$型の関数は入力を複製する必要があるため、$ B
multallap(B、B)$型の関数はありません。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です