可在www.sciencedirect.com在线获取理论计算机科学电子笔记332（2017）149-168www.elsevier.com/locate/entcs极化λ-演算Jos'eEsp'ıritoSanto1CentrodeMatem'aticaUniversidade do MinhoBraga，Portugal摘要提出了一个与极化直觉逻辑的聚焦演算同构的自然演绎系统。该系统带有一种名为极化λ-演算的证明术语语言，其归约规则同时表示与聚焦λ-演算有关的归一化过程和割消过程的同构副本。这一自然演绎系统的显著特征是：连接词的极性如何决定其排除规则的风格;证明搜索策略的存在，这相当于在微积分中的聚焦;高度纪律性的组织。甚至原子也有引入、消除和规范化规则。 极化λ演算 是一种接近按推值调用的编程形式主义，但由其证明理论谱系证明关键词：极化逻辑，聚焦，双向自然演绎，一般消去规则，η-展开1引言聚焦和极性是两个起源于线性逻辑的证明理论思想，但被认为在整个证明理论中有足够的影响。聚焦[1，10，13]是一种自下而上的证明搜索策略，试图将该过程中固有的非确定性降至最低。极性是逻辑连接词的特征，当它在聚焦证明搜索时具有明确的直觉主义逻辑和经典逻辑的极化版本可以在逻辑运算具有这种行为的情况下给出，并且甚至极性转移是明确的[15]。聚焦于极化逻辑是证明搜索的一种但是，极化逻辑中的割消也是函数计算的一种1电子邮件：jes@math.uminho.pt本研究由PortuesarFunds通过FCT提供资金项目UID/MAT/00013/2013内的《生物技术领域的基础与应用》。http://dx.doi.org/10.1016/j.entcs.2017.04.0101571-0661/© 2017作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。150J. Espírito Santo/Electronic Notes in Theoretical Computer Science 332（2017）149系统[15，2]。因此，研究按推值调用（CBPV）范式[9]和极化逻辑之间的联系是很自然的。本文将在直觉主义的背景下讨论这样的研究是可能的。 这涉及几个同时进行的任务。首先，我们必须准备好弥合微积分与自然演绎的鸿沟，因为后者第二，本着Curry-Howard对应的精神，我们必须为证明系统配备适当的证明术语语言，最好是透明的计算解释;第三，我们必须跟踪对偶性和对称性，通过集中精力进行深入探索，在直观的环境中，它们被隐藏，更是如此在自然演绎符号中。 此外，我们需要正确的方法论：我们不需要坚持每个有用的编程形式主义都可以简 化 为证明理论;相反，我们将让证明理论做它的工作，即产生标准系统，然后判断这些系统与我们想要捕获的系统之间的距离。本文从其中一个标准对象--极化直觉主义逻辑的聚焦序列演算出发，提出了另一个标准对象--极化λ-演算，或λ±N，在此基础上，h是一个与我们开始的λ-演算同构的自然演绎系统。这种同构在所有层次上都起作用：导子、导子类及其判断形式、归约关系。结果，我们得到了一个非常有趣的证明系统，它对自然演绎理论中的热门话题有很多要说的：子公式性质，证明搜索，析取处理，一般消除规则[11，8，14，12]。同时，极化λ演算是柯里-霍华德对应的一个补充：从它可以提炼出CBPV演算的一个变体我们首先（第2节）回顾聚焦和极性，因为我们提出了一个名为λ±G的序列演算。 第3节专门讨论了广义λ-演算λ±N，它的一些性质在第4节中得到。第5节讨论了结果。2极性和聚焦的回顾系统λ±G具有用于模的正和负，由以下文法给出：（正式） P，Q：：= a+|↓N| ⊥ |Pν Q（负公式）M，N：：= a−|↑P|PN|NM在这里，a+（resp.a−）的范围大于正（分别为负）原子。极性变化用↓和↑表示。一个基本的正式B要么是一个正原子，↓N或。复合负式C是不是原子的负式。以下定义是有用的：（公式）A：：= P |N（右式）R：：= P |a−（左公式）L：：= N|a+J. Espírito Santo/Electronic Notes in Theoretical Computer Science 332（2017）149151·RΓ =Δt：C/跳跃Γdlv（t）：CΓ [V：P]·/焦点Γ，x：N[S：N]A·/焦点Γr（V）：PΓ，x：Nr（x，S）：AΓ = πt：NΓ[S：N] πA截-/·Γ π [V：P]Γ |p：P= 10A切割+/·伊什特|S：AΓV|p：A图1.一、稳定序列Γ_e：A的λ±G-规则的类型规则本文给出了λ±G，g的推理/打字规则。1、2和3，处理以下序列：Γ [V：P]Γ =t：NΓ[S：N] AΓ |p：P =AΓe：A.上下文Γ是一组声明x：L（因此要么x：N要么z：a+），其中每个变量x最多声明一次。推理规则被双重标记为[tag 1/tag2]。第一个标记根据自顶向下的读取方式为规则提供通常的名称第二个标签根据在证明搜索过程中自底向上应用规则时产生的操作给出一个名称。如果没有合适的标签，我们就放·。证据搜索为了理解这个系统，首先要做的是剥离所有的术语注释，包括声明中的变量。r变为暂时地，左公式的多集，我们得到五种形式的序列：• ΓA-稳定的• r [P]--关注r.h.s.中的正P的。• r =N-将r.h.s.中的负N的。• Γ[N]A--关注左心室中的负N的。• Γ |P = ΔA-在l.h.s.中反转正P。 的。证明搜索在子系统中定义，其中省略了切割规则，并按如下方式处理。给定一个稳定的π ΓπA，需要一个外部决定，即选择π的哪个公式：要么是正的P（如果A=P），要么是负的N∈Γ（如果Γ中存在负的）。• 在第一种情况下，P的分解将在焦点模糊后产生一个正原子或一个负M在前一个子情形中，如果产生的原子在Γ中，则接受π，否则搜索失败。在后一种子情况下，该过程继续进行M的反演。 右倒位在r.h. s上聚集要么是带负电的原子，要么是带正电的原子，L152J. Espírito Santo/Electronic Notes in Theoretical Computer Science 332（2017）149·∨LRR原子+/接受+Γ =模糊：N↓R/模糊Rr，z：a+n[z：a+]Rrn [thunk（t）：↓N][V：Pi][ini（V）：P1<$P2]R/·（i=1， 2）原子−/接受−Γ |p：P =A↑/模糊Γ[nil：a−]a−LΓ[cothunk（p）：↑P]AΓ [V：P] Γ[S：N]A/·Γ[S：Ni]A（i=1， 2）Γ[V：：S：P<$N]<$AΓ[i：：S：N1<$N2]<$A图二、聚焦序列Γ_∞[V：P]和Γ_∞ [S：N]_∞A的λ±G-规则的类型规则e：a−Atom−/Colect−Re：P↑R/收集+r=e'：a − R r =[e|：↑PRΓ |p：P = N/·r = t1：N1r=t2：N2/·r =λp：P<$Nr=λt1，t2<$：N1<$N2r，z：a+e：A++r，x：Ne：A−Γ |z.e：a+= A原子L/收集LΓ |x.e：↓N = ≤A↓L/收集LΓ|异常终止：=A/Γ |p1：P1= Δr |p2：P2= AΓ |[p1，p2]：P1P2=AL/·图3.第三章。逆序列Γ=λt：N和Γ的λ ± G -规则的类型规则|p：P=A再• 在第二种情况下，N的分解将在焦点模糊后产生负原子或正Q在前一个子案例中，一个人接受∨LLLLJ. Espírito Santo/Electronic Notes in Theoretical Computer Science 332（2017）149153（值）V：：= z|形实字|在1（V）中|在2（V）（Terms）t：：=e'中，|[e| |t1，t2|⟨t1,t2⟩(Co − values，aka spines）S：：= nil|同形异义词|V：：S |1：：S |2：：S(Co−terms） p：：= z.e| x.e|[p1，p2]|中止（表情） e：：= dlv（t）|ret（V）|核心（x，S）|阿勒特|S| 1995年|p图四、λ±G的Proof-terms如果生成的原子是R，则搜索失败。在后一种子情况下，该过程继续进行Q的反演。左反转要么停止，如果AFL被击中，或收集在l.h. s。要么是正原子，要么是负原子，这使得原子再次稳定。这个令人愉悦的对称图像被一个事实稍微扰乱了，即r.h.s.初始稳定常数的公式A可以是一个复合负公式C。在这种情况下，搜索过程存在第三种可能性：直接跳到C的逆。为什么皇家骑警不能。公式在Γ <$A，在Γ[N]<$A，和在Γ |P = λA是否仅限于右公式R？原因是图3中的推理规则R：前提中的反演具有负的r.h.s.。公式，因此，在左反转阶段结束时收集的稳定序列可能在r.h.s.上具有负公式，因此，由于图1中的规则FocusL，左聚焦序列也是如此（如果r.h.s.序列的公式Γ[N]<$A被限制在R上，只要一个稳定的数列在r.h.s.中有一个公式C，我们就被迫跳起来，即使lhs里有个N专注于）。一种术语表达的语言。图10给出了λ±G的前项的syn税。4.由于逻辑系统中有5种顺序，所以有5种句法类。我们假设两个可数的，不相交的负变量和正变量的集合，范围分别为x和z。 在Γ[S：N]<$R的情况下，|p：P = R或r =e：R，我们可以认为R是一个共上下文（=r.h.s.上下文），使用单个声明，要么是默认的正协变量，比如说*，具有正类型，要么是默认的负协变量，具有原子负类型。 在比较了类型规则Atom+和Atom-之后，我们必须认识到nil是默认的负数R L协变量，而*没有写。我们可能认为*有一个独特的，在每个正的S、p或e中隐式出现，而在V、t或负的e中没有。我们应该再看一下图2中的系统。1，2和3，现在作为一个打字系统，所有的术语注释都放回去了。 我们认为值V和项t是在右边类型化的，分别具有正和负类型;并且认为共同值S和共同项p是在左边类型化的，具有负和正类型，154J. Espírito Santo/Electronic Notes in Theoretical Computer Science 332（2017）149r =rt：Nr，x：Nre：Art [t/x]e：AΓ|p：P =<$NΓ[S：N]<$AΓ |p @ S：P=A中文（简体）|p：P=A[*\p]：AΓe：NΓ[S：N]Ae@S：AΓ[SJ：AJ]<$NΓ[S：N]<$AΓ[SJ@S：AJ]A图五、λ±G的合成运算的容许型规则分别表达式注释稳定的序列。句法类之间的二重性还表现在它们各自的特殊性上。值z和thunk（t）分别是nil和cothunk（p）的对偶。如果我们写了e，|作为共同绑定E. nil和e。*，可以看到分别与绑定z.e和x.e的对偶。三个连接词、和的构造词是配对、注入和λ-抽象，后者是不寻常的形式λp，其中p是形式z.e、x.e或abort的多个共配对是而否定词“”和“”有一种通用的破坏形式，即推动脊柱（具有值V或投影符号1，2）。如果我们忽略传递项dlv（t）（它表示在证明系统中引入的跳跃便利性），表达式e的四种形式是两对双重结构。如果我们把前者看作ret（V，*），则返回和共同返回之间的对偶性得到增强。 有一个 积极的 削减|p和负切阿勒特|S：割的极性就是它的割公式的极性。派生语法。 有一个负代换运算[t/x] e，在其递归定义中，临界方程为[t/x]coret（x，S）=t|SJ= [t/x] S。对偶地，存在正替换e [*\p]，在其递归定义中，临界方程为ret（V）[*\p]= RtV |p. 可接受的类型规则如图5所示。我们需要第三次行动。 如果S=nil，设p@S=p，e@S=e，且SJ@S=SJ;否则，共项p@S、表达式e@S和脊SJ@SJ. Espírito Santo/Electronic Notes in Theoretical Computer Science 332（2017）149155⊃Jλp|V：：S→ V|p @ S⟨⟨t1, t2⟩|i：：S→t i|S（i = 1，2）[e||cothunk（p）→e [*\p]阿塞|nil →e胡萝卜素i（V）|[p1，p2] V→ V |p i ii（i = 1，2）吨（t）|x.e→ [t/x] e拉斯|zJ.e→ [z/zJ] e图第六章λ±G中的割消由p和e和SJ上的同时递归定义：abort @ S = abort（dlv（t））@ S = dlvt|S[p1，p2]@ S =[p 1@S，p 2@S]V|pΩ @S=ΩV|p @S（x.e）@ S = x. （e @ S）|SJ@S=t|SJ @ S（z.e）@ S =z。（e@S）coret（x，SJ）@S=coret（x，SJ@S）零@S=Scothunk（p）@S=cothunk（p@S）（V：：SJ）@S=V：：（SJ@S）（i：：SJ）@S=i：：（SJ@S）一个人检查p或e或SJ，搜索将创建切割的交付项t阿勒特|S.两极分化淘汰。图中给出了切割消除规则。6. 这些规则是表达式上的关系，通过相容闭包生成一步归约关系，记为→.前四个规则减少负的削减，最后三个正的削减。请注意，减少一个负的切割可能会产生一个正的切割-这已经在第一条规则中可见。每一个Redex都是一个切割。在类型化表达式中，每个剪切都是一个redex，因为类型化强制剪切具有显示的redex之一的形式。例如，在一个类型化的割集<$λp中，|S必须具有V：：S的形式，因为这是S唯一与蕴涵（在左焦点中）共类型的形式。因此，一个类型化的表达式∧↑a−∨↓a+156J. Espírito Santo/Electronic Notes in Theoretical Computer Science 332（2017）149是无割的，因为它是不可约的。此外，每个切割都是主要的，因为切割公式在两个过程中都被引入，即使切割公式是原子的（具有用于引入的推理/类型规则的结果）。J. Espírito Santo/Electronic Notes in Theoretical Computer Science 332（2017）149157Γ =Vut：C·/JumpΓ [V：P]Id+/FocusΓdlv（t）：CΓDH：a−Γap（H）：a−V（V）：PAtom−E/Accept−ΓDH：↑PP=B1···Bn（Γ|bi：Bi−→A）i=1，···，nr_i_i（H，b_i，···，b_n）：↑E/BICD[V：P]P=B1<$··<$Bn（Γ|bi：Bi−→A）i=1，···，nr= val（V，b1，···，bn）：A+E/·图第七章稳定序列Γ_e：A的λ±N-规则的类型规则两个原子都在L.H.S. 和r.h.s. 的顺序）。3极化λ演算极化直觉主义逻辑的自然演绎系统 在图1和图2中给出了λ ± N的推断/分类规则。7、8和9。它们处理以下翼序列：[V：P]r = Vt：Nr D H：Nre：A.上下文Γ也是一组声明x：L（因此要么x：N要么z：a+），其中每个变量x最多声明一次。λ ±N的推理规则被双重标记为[tag 1/tag 2]。第一个标签根据自上而下的阅读方式为规则命名;第二个标签根据规则在下面介绍的证明搜索过程中产生的动作命名。如果没有合适的标签，我们就放·。为了理解这个系统，首先要做的是专注于逻辑方面，省略所有的术语注释，包括声明中的变量。上下文Γ成为左公式（N或a+）的临时多集回想一下，B涵盖了基本的正公式，即a+、↓N或的形式的公式。因此，每一个正公式都具有B1<$··<$Bn的形式。某些推理规则具有形式为Γ的规则集|B−→A。这是一个派生的形式，它是由B的案例分析定义的：Γ |a+−→A：= Γ，a+<$AΓ |↓N−→A：= Γ，N <$AΓ |−→A：= true（一）U158J. Espírito Santo/Electronic Notes in Theoretical Computer Science 332（2017）149K-−·ID·联系原子+/接受+Γ =模糊：N↓I/模糊UΓ，z：a+n[z：a+]IΓn [thunk（t）：↓N]Γ[V：Bk]/·（n≥2， 1≤k≤n）Γ[inn（V）：B1<$· ·<$Bn]r，x：NDx：NId/焦点Γ=t：N/rDhd（t）：NΓDH：P<$NΓ[V：P]ΓDHV：NH：N1N2EΓDHi：Ni（i= 1， 2）图八、聚焦序列Γ[V：P]和ΓQH：N的λ±N-规则的类型规则e：a−Atom−/Colect−U电子邮件：P ↑I/收集+r=e'：a − I r =[e|：↑PUP=B1···Bn（Γ|bi：Bi−→N）i=1，···，nr =<$λ（b1，···，bn）：P<$NI/·Γ =πt1：N1Γ= πt2：N2r=t1，t2：N1<$N2I/·图第九章逆序列Γ=λt：N的λ±N-规则的类型规则（1）的第三个方程意味着我们可以消去形式为Γ的代数|− → A。第一个（resp）第二）等式（1）隐藏了正原子的消除（分别为：消除↓）。例如，下面是rule + E的一个实例：Γ [a+↓N] Γ，a+AΓ，N<$AΓα为了理解推理规则的自上而下的解读，让我们暂时忘记各种形式的相继式之间的区别。连接词⊃我J. Espírito Santo/Electronic Notes in Theoretical Computer Science 332（2017）149159二次和三次都有原始的引入和排除规则。 关于《圣经》和《160J. Espírito Santo/Electronic Notes in Theoretical Computer Science 332（2017）149我我排除法是最简单的。请注意，对于RISK的引入规则有这样一个熟悉的特殊情况：Γ，MNΓ =↓MN同样熟悉的是引入规则。上移↑也有一个引理和一个消元规则，但后者是复杂的，因为它可能涉及通过定义（1）消元和基本原子正式此规则类似于+E，它是正公式的通用消元规则。对偶地，否定公式-I有一个通用的引入规则：在+E中，我们排除了一个聚焦的肯定式，在-I中，我们得出一个聚焦的否定式，开始了向下聚焦的阶段（见下面这个系统中的证明搜索下移位↓的引入规则是原始的，而它的消除规则又隐藏在（1）中。因为Γ包含形式为a+或N的公式，所以有公理Atom+和Id−。后者从一个假设开始一个负向下的焦点，而它的对偶Id+从一个结论开始一个正向上的焦点。另一方面，Atom+属于原子的四个规则，其中一个隐藏在（1）中。任何作为m的消去式的前一种形式，m的消去式给出了一个A到m−I的转化规则;作为负式（↑P）的另一种基本情况，负原子有一个消去式结束向下聚焦阶段的规则。仍然有一个没有第一标签的规则：就像在微积分中一样，它是一个只能通过证明搜索来解释的跳跃工具。正常。 在一个稳定项的推导中，一个正公式P是极大的（=一个引理的结论和一个消元的主前提）i P是+ E的一个实例的主前提的右焦点（因为Γ [P]的推导必然以一个引理结束，并且没有其他消元规则在主前提中有一个正公式）;并且一个负公式N是极大的i它是r.h.s. -I的一个实例的公式（因为每一个消去的主前提都有形式ΓDN;除了-I之外，没有任何推导这种消去的规则是引理;而推导-I的前提的所有规则都是引理）。这些观察证明了以下定义。定义3.1λ ± N中的一个导数被称为e正规的，如果它不包含规则-I或+E（一般规则）的发生。命题3.2（子公式性质）（i）在Γ [ P ]的正规导子中（分别为r =<$N，r <$A）每个公式都是P的一个子公式（或 N，A）或Γ中的某个公式。(ii)在Γ D N的正规导子中，包括N在内的每个公式都是Γ中某个公式的子公式。证据 通过对Γ [P]的同时归纳，得到了Γ=N，ΓA和ΓDN.Q预烧ch。 我们为λ±N定义了一个prof-sear chproc cc，它解释了四种形式的序列之间的差异：• ΓA-稳定的J. Espírito Santo/Electronic Notes in Theoretical Computer Science 332（2017）149161K（值）V：：= z|形实字|inn（V）（Terms）t：：=e'|[e| |t1，t 2|⟨t1,t2⟩（头部、孔表达式）H：：= x|HV|H1|H2|hd（t）（表达式）e：：=dl v（t）|re t（V）|ap（H）|情况ap（H，−→b）|caseval（V，−→b）图10. λ±N的Proof-terms• r [P]--聚焦于正P（在r.h.s.的）。• r =N-将负N向上反转（在r.h.s. 的）。• ΓDN-关注负N（在r.h.s. 的）。就像微积分一样，这里的证明搜索被组织成聚焦和反转的阶段的顺序。我们现在有向上（而不是向右）和向下（而不是向左）的聚焦和反转。在向上（resp）。向下）阶段，推理规则自底向上（分别自上而下）。证明搜索是在正常推导上定义的。给定一个稳定的N∈ ΓA，我们必须选择要么开始向上聚焦于正的P（如果A=P），要么开始向下聚焦于负的N∈Γ（如果存在一个这样的N）。• 在第一种情况下，我们完全按照微积分中证明搜索的正确聚焦阶段进行。• 在第二种情况下，我们暂停了自底向上的发展，并把自顶向下的推理规则的应用阶段。由规则FocusD选择来自Γ的负公式N以开始向下聚焦。N通过消去规则的分解将产生一个负原子或一些↑Q。在前一种情况下，如果生成的原子是R，则接受给定的稳定的R，否则搜索失败。在后一种子情况下，我们返回到给定的稳定模式，并继续进行BICD的自底向上应用，BIC D代表向下模糊-反转-收集。通过这一规则，向下的焦点↑Q变得模糊，正Q被颠倒，Q底部的正原子和负原子被收集起来，并且，对于每一个，都产生了一个新的稳定的原子。和微积分中一样，这个证明搜索过程稍微扩展了一下：如果A是某个复合负数C，那么这个过程可以直接跳到C的逆。一种术语表达的语言。图10给出了λ±G的前项的syn税。10. 在这种语言中有4个语法类，因为有4种在逻辑系统中的顺序。 现在我们应该回到图1和图2中的系统。7,8和9，把所有的术语注释放回去。 我们有一个这个术语的打字系统。162J. Espírito Santo/Electronic Notes in Theoretical Computer Science 332（2017）149↑在λ±N中，basic cco-termsb形成由以下公式定义的派生语法类：b：：= z.e| x.e|中止因此，存在序列Γ的导出形式，|b：B −→ A定义如下：Γ |z.e：a+−→A：= Γ，z：a+e：AΓ |x.e：↓N−→A：= Γ，x：N<$e：AΓ |abort：−→A：= true（二）λ ± N中的co-项是基本余项的向量−→b=b1，· · ·，bn。 注意，在λ±N中，余项不是伪项perse（与λ±G相反）。例如，bort就是一个符号，它可以用来构成λ-抽象和格-表达式。相对于λ±G的伪项语言，nvel y是e ad的类，e ad是从一个负变量x或一个首项开始的一系列“应用”。这里的因此，ap（H）（当H有原子类型时，我们可以键入）被称为“应用”表达式。如果H有P型，我们可以键入否定case-expr essioncaseap（H，−→b）. 另一种形式的情况下表达说是POSITIVE。定义3.3λ±N的表达式是正常的，如果它不包含hd或caseval.派生语法。应用表达式和负情况表达式可以统一地给出为[H]S，表示将H填充在S的洞中的结果，其中S是一个上下文（一个有洞的表达式），有两种可能的形式2：ap（[]W1· · ·Wm）情况ap（[]W1· · ·Wm，−→b）。这里，每个Wi是值V或投影符号1、2。 注意这个洞S期待一个H，这就是为什么头也可以被称为洞表达式。这样的卷积是λ±N的脊，由S：：=ap（[]）|caseap（[]，−→b）|[[]V]S|[[]1]S|[[]2]第三章（三）所以，为了生成spines 3，我们用[] V或[] i填充spines的孔。除了脊柱中的孔填充之外，还有另外两个稍微放松的孔填充概念。首先是这样的：我们定义了在S的空穴中填充非原子负类型C的e意味着什么，产生一个表示为[e]]S的表达式，并且[2]请注意，我们偏离了通常的填充空洞的符号，即S[H]。所采用的符号的一个合理解释是S的洞在表达式的左端[3]对术语“棘”的解释将在后面进行：连接λ ± G和λ ± N的映射将精确地将前者的棘与后者的“棘”联系起来。J. Espírito Santo/Electronic Notes in Theoretical Computer Science 332（2017）149163SΓe：NΓ[S：N]−→A[[e]]S：AΓ |b：B −→ NΓ[S：N]<$AΓ |b @ S：B −→ Ar_e：P_P=B_1···|bi：Bi−→A）i=1，···，nΓ [e]（b1，···，bn）：AΓ|b：Q−→PP=B1<$··<$Bn（Γ|bi：Bi−→A）i=1，···，nΓ|b@J−→b：Q−→Ar =rt：Nr，x：Nre：Art [t/x]e：A图十一岁λ±N的合成运算的容许型规则同时我们定义了基本的共项b@S：[[dlv（t）]]S=[hd（t）]S中止@S=中止[[caseval（V，−→b）]]S=caseval（V，（−→b）@S）（x.e）@S=x. （[[e]]S）[[caseap（H，−→b）]]S=caseap（H，（−→b）@S）（z. e）@S=z。（[[e]]S）其中（b1，···，bn）@ S=b1@S，···，bn @ S。在[e]]S的定义中，搜索e以找到交付项dlv（t），并继续进行hd（t）的普通填充，. 我 们 将这些运算扩展到a−是e的类型和S的余型的情况，即：[e]] ap（[ ]）=e 4和b @ ap（[ ]）=b。 可接受的类型规则在图中。十 一 岁空穴填充的第二个宽松概念是[e]]−→b，其中我们将−→b视为n ntextcaseval（[]，−→b），其中定义了填充valueV的含义。We定义表达式[e]−→b和基本余项b@J−→b：[ret（V）]]−→b=caseval（V，−→b）abort@J−→b=abort[caseap（H，−→bJ）]]−→b=caseap（H，（−→bJ）@J−→b）（z. e）@J−→b=z。（[[e]]−→b）[caseval（V，−→bJ）]]−→b=caseval（V，（−→bJ）@J−→b）（x.e）@J−→b=x. （[[e]]−→b）其中（bJ1，· · ·，bJn）@J−→b=bJ1@j−→b，· · ·，bJn@J−→b。在[e]]−→b的定义中，e找到一个返回值ret（V）， 并继续进行常规填充V4我们可以把[e]]ap（[]）=ap（hd（e'）），但我们会看到e是ap（hd（e'））的约简。164J. Espírito Santo/Electronic Notes in Theoretical Computer Science 332（2017）149⊃.ΣK[.hd（λ−→b）<$V]S→caseval（V，−→b@S）hd（t1，t2）i→hd（ti）（i= 1， 2）情况ap（hd（[e|），−→b）→[e]]−→bap（hd（ecase val（inn（V），b1，···，bn）→case val（V，bk）（n≥2， 1≤k≤n）case val（thunk（t），x.e）→[t/x]ecase val（z，zJ.e）→[z/zJ]e图12个。λ±N归一化在val（[]，−→b）的情况下。e的casemissingcase不会增加，因为caseval（[]，−→b）的hole具有positi vety pe。同样，图11中给出了允许的打字规则， 其中e−→b=b1，· · ·，bn。最后，有一个负替换[t/x]e的运算，在其递归定义临界方程为[t/x]x=hd（t）。两极分化的正常化。归一化规则在图中给出。12个。这些规则都是关于表达式的关系，除了关于头的规则，它是关于头的规则，通过性质H→HJ<$[H]S → [HJ] S生成关于表达式的关系。然后，通过相容闭包，生成一步约简关系，记为→。在前四个规则中，负的赎回具有形式[hd（t）]SJ，后三个规则减少正的赎回，这是正的情况表达式。因此，如果一个表达式包含一个redex，它是不正常的。另一方面，如果一个类型化的表达式不是正规的，那么它要么包含一个正的case表达式（它必须具有正的redex形式，因为值的三种可能形式被最后三个归约规则所覆盖），要么它包含一个负的redex（因为hd（t）的四种可能形式被前四个归约规则所覆盖，类型化强制hd（t）如图所示）。因此，一个类型化的表达式是正常的，如果它是不可约的。此外，每个归约规则消除了一个极大公式（hd（t）中的t的类型或在val（V，−→b）的情况下为V）。 因此，每个约简规则都是迂回约简规则。对于重复的规则是熟悉的，也是最简单的。规则的减少普通的β-redex：一个积极的情况下，表达式创建，其中第一个组件是V，以用最后三个简化规则来分析他们要么选择了一个组件，aco-pair−→b表示为yn注入，或替换一个hunked项，或重命名a正变量剩下的两条规则处理的是head项是co-binding的情况，它们的共同点是（case）ap和hd相互抵消。∧↑a−∨↓a+J. Espírito Santo/Electronic Notes in Theoretical Computer Science 332（2017）149165K4结果同构。特别地，我们证明了λ±G和λ±N是同一系统的两个视图.我们受益于一种在更简单的逻辑中已经成熟的技术[5，6]。本文对λ±G中析取的处理作了如下调整：（i）在n（V）中采用n元注入;（ii）右引入规则为：Nk在λ±N中的引入规则也是如此;（iii）左引入规则（Γ|bi：Bi=A）i=1，···，nΓ |[b1，···，b n]：B1<$···<$Bn=<$AL/·（iv）归约规则现在在n（V）中被证明。|[b1，···，b n] n→nV |b k. 该方法包括：θ：λ±G−→λ±N和θ：λ±N−→λ±G：• 对于T=V，t，e∈λ±G，我们定义了值（分别为： 对于S∈λ±G，我们定义表达式Θ（H，S），givenH. 这个定义是T和S上的同时递归。• 对于T=V，t，e∈λ±N，我们定义了值（分别为： 对于H∈λ±N，我们定义表达式<$（H，S），givenS. 这个定义是T和H上的同时递归。鉴于λ±N中没有共项，共项的翻译是“在λ ±N上”完成的e（Θ（b1），···，Θ（bn））和θ（b1，···，bn）=[θ（b1），···，θ（bn）]。值和项被同态翻译;作为返回值或传递项的表达式也是如此。表达式的其余子句为：Θ（coret（x，S））= Θ（x，S）θ（ap（H））= θ（H，nil）Θ（θt|S）=Θ（hd（Θt），S）（情况ap（H，−→b））=<$（H，cothunk（<$（−→b）θ（<$V|p）=caseval（θV，θp）V|（−→b）翻译的动力是脊椎和头部之间的相互作用。给定参数H（resp. S）、Θ（H，S）（分别[1][2][3][4][5][6][7][8][9][10][10][11][10][11][12][11][12][12][13][14][15][16][17][18][19][19][10][10][11][19][10][10][11][10][10][11][10][11][11][10][11][10][11 H）如下：Θ（H，nil）= ap（H）θ（x，S）= coret（x，S）Θ（H，cothunk（p））= case ap（H，Θ p） θ（hd（t），S）= cothunk（t）|SΘ（H，V：：S）= θ（HθV，S）Θ（H，i：：S）= Θ（Hi，S）θ（Hi，S）= θ（Hi，S）166J. Espírito Santo/Electronic Notes in Theoretical Computer Science 332（2017）149对于T=V，t，e，映射Θ和θ保持类型。对于H和S，类型在图中给出。13.J. Espírito Santo/Electronic Notes in Theoretical Computer Science 332（2017）149167ΓDH：NΓ[S：N]AΓθ（H，S）：AΓDH：NΓ[S：N]A（H，S）：A图十三. 为Θ和θ定理4.1（双射）Θ和τ在值、项和e × ressions的层次上是相互逆的，即：（i）Θ τ（T） =T，其中T=V，t，e在λ±N中;和（ii）τ Θ（TJ）=TJ，其中TJ=V，t，e在λ±G中。证据证明了命题（i）和命题（iii）对所有S，Θ ∈（H，S）= Θ（H，S），其方法是在λ±N中同时归纳T和H. 国家t(ii)与（iv）对所有H，<$Θ（H，S）=<$（H，S）一起证明;证明是由λ ± G中TJ和S同时诱导。Qλ ± N的完备性如下：每一个直觉主义定理在系统中都有一个prof（在被极化成为极化公式之后）--在λ±G（focusing的完备性[13]）的情况下也是如此，这要归功于前面的定理。为了证明下面的同构定理（定理4.3），我们需要做一些准备工作。我们用棘到棘的映射来扩展Θ和θΘ（nil）=ap（[]）θ（ap（[ ]））=nilΘ（cothunk（p））=caseap（[]，Θp）<$（caseap（[]，−→b））=cothunk（<$（−→b））Θ（V：：S）= [[]ΘV]ΘS（[[ ]V]S）=V：：SΘ（i：：S）=[[]i]ΘS（[[ ]i]S）=i：：S定理4.1的直接结果是，θS =S和θS =S。将Θ推广到棘之后，用孔填充来表示Θ（H，S）就非常方便了。令S=ΘS。关于S的一个简单归纳法建立了Θ（H，S）= [H]S，由此得出等式θ（H，S）= θ（[H]S）。接下来，我们将看到Θ如何映射替换和孔填充的各种操作。引理4.2(i)Θ （[t/x] T）=[Θ t/x]Θ T，其中T = e，V，t，J，b，p。(ii)Θ（e [*|p]）=[θ e] θ p。(iii) Θ（T @ S）=（Θ T）@（Θ S），其中T = b，p.(iv) Θ（[z/zJ] T）=[z/zJ]Θ T，其中T = V，t，S，b，p，e。证据（i）对所有的H，证明了该陈述与Θ（[Θ t/x] H，[t/x] S）=[Θ t/x]Θ（H，S）.证明是通过T和S上的同时归纳法。(ii)声明168J. Espírito Santo/Electronic Notes in Theoretical Computer Science 332（2017）149证明了：对于所有H，Θ（H，S[*|p]）=[[θ（H，S）]Θp;和Θ（pJ[*|p]）= Θ（pJ）@J Θ（p）;和Θ（b[*|p]）= Θ（b）@J Θ（p）。证明是通过同时归纳法
我的内容管理
展开
