理论计算机科学电子笔记192（2007）29-44www.elsevier.com/locate/entcs双归纳结构语义学（延伸摘要）帕特里克·库索1D'epartementRadhia Cousot2CNRSE'colepolytechnique，91128Palaiseaucedex，法国摘要我们提出了一个简单的序理论的集合论归纳定义的推广。这个推广涵盖了归纳、共归纳和双归纳的定义，并通过抽象来保持。这使得结构操作语义可以同时描述程序的有限/终止和无限/发散对象。这在按值调用λ-演算的结构双元小/大步跟踪/关系/操作语义上得到了说明。关键词：定点定义，归纳定义，共归纳定义，双归纳定义，结构操作语义，SOS，跟踪语义，关系语义，小步语义，大步语义，发散语义，抽象。1介绍在指称语义学[17]中使用定点与在公理语义学[10]和结构操作语义学（SOS）[19，20，21]中使用基于规则的归纳定义之间的联系可以通过归纳定义[1]的推广来包括共归纳定义[8]。然后可以概括描述有限输入/输出行为的自然语义[12]故，《易经》也称“七经”。这是必要的，因为无限行为的定义不能从有限的大步SOS行为中推导出来。1Patrick. 你好。fr，www.di.ens.frwww.example.com/cancousot/2Radhia. 我是说，我的意思是，我网址：www.polytechnique.edu/Radhia.Cousot/1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2007.08.01530P. 库索河Cousot/Electronic Notes in Theoretical Computer Science 192（2007）29⇒ ⊥⇒ ⊥⇒⇒|⟨⊇⟩⟨⊆⟩⟨ ⊆⟩ ⟨D ±⟩例1.1让我们考虑选择运算符 E1E2，其中E1的求值要么终止（返回值a，写作E1=a），要么不终止（写作E1=）。 类似地，E2的大步骤语义是E2=b，表示终止求值返回b，或者E2=表示非终止。让我们考虑选择运算符的几种可能的语义：• 不确定性：一个内部的选择，最初作出评估E1或评估E2;• 并行：使用未指定的调度同时计算E1和E2，并返回第一个可用结果a或b;• 混合从左到右：计算E1，然后返回结果a或计算E2并返回其结果b;• 混合从右到左：计算E2，然后返回结果b或计算E1并返回其结果a;• Eager：同时计算E1和E2，如果两者都终止，则返回其中一个结果相应的有限大步行为，如自然语义[12]中所描述的，都定义如下：一|b=aa|b=100b。但对于此案，|=无阻牧师的平行混合左-到右混合右-到左渴望⊥|b=0.000000b⊥|b=a|=|=⊥|b=0.000000b一|=⊥|b=a|=|=⊥|b=0.000000b⊥|b=0一|=⊥|b=0一|=由于自然语义定义了有限的行为，但没有定义发散的行为，因此在Prolog [2，9]中实现的将大步求值规则解释为Horn子句将具有由实现确定的发散行为（例如，Prolog解释器具有从左到右的求值）。Q本文发展并举例说明了在操作语义学中使用“双归纳”定义，使有限和一般的方法包括通过替换幂集来扩展希尔伯特证明系统[1] （U）， 宇宙U的偏序、.除了经典的归纳定义<$（U），这个扩展还包括共归纳定义<$（U），和双电感的定义和共归纳的定义[7，8]。这个扩展还处理了指称语义学或SOS中的组合结构定义。这示P. 库索河Cousot/Electronic Notes in Theoretical Computer Science 192（2007）2931∀∈| { ∈|}|∈||≺≺⟨≺⟩≺≺LD∈公司简介∈l联系我们n ∈ DDS是集合S的元素作为i∈Δ<$S的向量的集合。通过定义按值调用λ演算的语义。我们引入了一个原始的大步跟踪语义，使操作意味着-ING收敛和发散行为的程序。组合结构定义混合了有限行为的归纳和无限行为的共同归纳这种大步跟踪语义排除了出错的错误行为。其他语义则通过抽象系统地导出。大步跟踪语义首先被抽象为关系语义，然后被抽象为标准大步或自然语义。这些抽象是合理和完整的，因为大步跟踪和关系语义描述了相同的收敛或发散行为，而大步跟踪和自然语义描述了相同的有限行为。然后，通过收集沿跟踪的转换，将大步跟踪语义抽象为小步语义。这种抽象是合理的，但不完整，因为小步语义生成的轨迹描述了程序的收敛、发散和错误行为。这表明，基于跟踪的操作语义可以比小步操作语义提供更多的信息。2双归纳结构定义及其抽象2.1结构序论归纳定义我们引入了不同形式的结构序论归纳定义，并证明了它们的等价性。我们把语言L的句法形式化为L上的二元关系，理解为L上的因 此 ， L是一个完全成立的集合，是irrexexive（诱导rexexive有有限个左图像lL：lJLlJLN（S是集合S的基数，N是自然数的集合）。因此，我们可以写l：：=l1，.，ln表示元素的元组LJIIJ=II，...，ln，使得{l1，...，ln}={lJ∈L|lJl}。例如，fo.r是lambda项a、b、.的语言L* *= x |λ x. 一|ab我们可以定义a<$λx a，a<$ab和b<$a b，所以a b：：=a，b。如果没有结构，即语法导向的推理是必要的，L可以被选择为单例，而T为假。对于每个“句法成分”l L，我们考虑语义域l，l，l，l是一个有向完全偏序（DCPO）。对于每个“系统策略组件”L，我们考虑变量Xl，Yl，. . . 范围在语义域L上。当相应的语义域从上下文中清楚时，我们删除下标l（例如， 语义域对于所有的“句法成分”都是相同的，即L：1 =）。对于每个“句法成分”l L，我们让Δ是索引序列（全序集）。当考虑序列<$xi，i∈Δl<$∈Δl <$<$→对于序列的每个元素i∈Δl，我们考虑变换器Fi∈Dl×32P. 库索河Cousot/Electronic Notes in Theoretical Computer Science 192（2007）29LJJHDJ. jlK=lfpλXfF（X，SJJlK）f写LJJKLJ K具有以下形式：SJ K∈⎧⎪⎨jLi∈Δεi∈Δεi∈Δεi∈ΔεLi∈ΔεLLi∈ΔεLLLL一个等式定义iJ∈{i}D11。 . . ×Dln−→Dl其中n=|{lJ∈L|lJl}|和d{11， .. . ，ln}={lJ∈L|lJl}。当n = 0时，我们有Fi ∈ Dl<$−→ Dl。假设变换器的第一个参数是e±l-单调的，即εi∈Δl，l1， .. ，ln∈l，X，Y∈Dl，X1∈Dl1， . ，Xn∈Dln：X±lY=πFi（X，X1，...， Xn）±1Fi（Y，X1，...， Xn）。L l对于一个有向对称复合物n t”l ∈ L， ∈（Δl<$−→Dl）<$−→Dl是设nt阶互补±l-单调（<$$> Xi，i∈Δl<$$>：<$$>Yi，i∈Δl<$$>：（<$i∈Δ l：Xi±lYi）= Δ l（Xi）±ll（Yi））。连接运算符用于收集alternati v在正式定义中。或者说，我们写Y_i（X_i）=jlX_i，暗示了一个事实，i∈Δεi∈Δε序列Δl。Xi应该按照在大多数情况下，这些备选项在正式定义中的呈现顺序在这种情况下，Δl只是一个集合，并且连接通常可以根据二元连接Y∈（Dl×Dl）−→Dl来定义，其中假设是类连接，共形，±l-单调，如Y∈（Xi）jlXi. 二进制连接maybe与语义域L的最小上界（lub）L不同。定点定义具有以下形式±Æli∈ΔεIllJl其中lfp±是偏序集P，± p上的部分定义的±-最小定点算子。为了强调结构组成，我们也让{l1，.，ln}={lJ∈ L |lJl}和l∈L：Sfl：：= l1，.，ln=lfp±10 λX。i∈ΔεFi（X，Sf）I IIK， . ，SfJlnK）.引理2.1<$l∈L：Sfl定义良好。不需要固定点或连接的定义也可以包含为固定点，作为jFi（SfJ11K， .. . ，SfJlnK）=lfp±λX. jFi（SfJ11K， . ，SfJlnK）或没有加入Fi（SfJ11K， . ，SfJlnK）=lfp±λX. jFiJ（SfJIIK， . ，SfJlnK）.el，llL方程是满足以下系统的分量式±l-最小<$Xl，l∈L <$Xl=li∈ΔL.P. 库索河Cousot/Electronic Notes in Theoretical Computer Science 192（2007）2933Fi（Xl，lJ<$lXlJ）34P. 库索河Cousot/Electronic Notes in Theoretical Computer Science 192（2007）29JL⎪⎩L联系我们LJKJLLXl±lSrJlKFi（.Dβ，SrJljK）。i∈ΔεlJl基于约束的定义具有以下形式：是满足以下系统的分量式±l-最小<$Xl，l ∈L <$SeJlK，l∈L <$约束（不等式）⎧⎪⎨li∈ΔεFi（Xl，lJ<$lXlJ）±lXll∈L.基于规则的定义是一系列规则的形式，Fi（Xl，XLlJlSrJlJK±l∈L，i∈Δl其中前提和结论是L.L.CPO的要素。当以逻辑形式理解规则时（前提是一个假设为真的陈述，从中可以得出结论），下面的形式可能更可取。Xl±lSrlFi（Xl，SrJlJK）±lSrJlKl∈L，Xl∈Dl，i∈ΔllJl如果Fi不依赖于前提Xl，它就是公理。在这种介绍中，L加入Y 的交替是左隐式定义的形式. 为了使它明确，我们重写这样的（一）li∈ΔεFi（Xl，lJlSrJlJK）±lSrJlK±εl ∈ L，Xl∈ Dl.联接的形式定义明确了规则的表示顺序是否重要。如果没有，可以使用二元关联和交换连接来定义连接。这个二元连接甚至可以是隐式的，并且通过结合性和交换性，规则可以以任何顺序给出。我们的例子就是这样一个D∈Dl是可证明的，当且仅当它有一个证明是一个transfinite序列4D0，.j.. ，Dλ，则D0=λ1，Dλ=D，且对所有0δ≤λ，Dδ<基于规则的定义（1）的含义是[3]这是经典希尔伯特形式系统的情况4在经典情形[1]中，定点算子是连续的，因此证明是有限的。）±lLLβ δ±Æ3P. 库索河Cousot/Electronic Notes in Theoretical Computer Science 192（2007）2935JK J K J K J KJ KS.l∈L.D±J K∈SJKJ K J KCi{ci|PiX} SLLLLLLLLLLγγLLLLLLL1Ln·Srl.l{D∈Dl|D是可变的。上面的序论归纳定义都是等价的：定理2.2<$l∈L：SlSfl=Sel=Scl=Srl。[1]的这种推广也可以包括博弈论版本。关闭条件版本[1]也很容易适应。例2.3用规则对论域U的子集P的 . i∈I，其中Pi<$U和ci∈U，i∈I可以写成X<$S <$，i∈I或Pi<$X，X< $ S<$，i∈I，这是Pi< $ S<$，i∈I，对于s短。所以，ci∈ Sci∈ SD·，±·，⟨℘(U),⊆,∅,∪⟩, Δ·I，Fi∈<$（U）<$→ <$（U）是Fi（X）{ci|Pi<$X}和j·t定义S=lf p <$λX{c|i∈I<$P<$X}。·i iQ2.2双语义域为了解释终止/有限和发散/无限的程序行为，我们考虑双语义域，每个语义域由一个有限的语义域组成。（指有限程序）D+，±+，D+，.+∞与无穷语义CODomain（指无限程序behaviors）l−， −l，−l，−which被假定为bedcpos[17]（分别为完全格）。由于投影π+∈Dl→ D+，它们被组合成一个双语义域（双有限程序行为）Dl，πl−∈Dl→Dl−，构造函数πl∈D+×Dl−→<$Dl满足<$x∈D+， y∈Dl−：π+（πl（x，y））=xanddπl−（πl（x，y））=ywhile<$X∈D：πl（π+（X），πl−（X））=X.例子是笛卡尔积，不相交并集或不相交集的并集双语义整环<$+Dl，±l，Hl<$是dcpo（或完备格）by定义X+πl（X），X−πl−（X），X±lY（X+±+Y+）<$（X−±−lY−），L和d.Xiπl（.+X+，.−X−）。li∈I2.3抽象li∈Iilii∈I我们考虑一种基于连续抽象函数的简单抽象形式α[6]，其中包括伽罗瓦连接的特殊情况[5]（表示为αP，“是偏序集，且x“γ（y））.对所有l∈L，设d ∈ D，±，f∈H ∈dcpos，Fi∈D ×D... × D<$−→ DiΔl在它们的第一个参数中是单调的，并且定义抽象语义fl的等价形式之一。 2.2.如果αl∈ Dl<$−→ Dl，我们说抽象语 义<$Sl ，l ∈ L <$关于具 体 语 义<$Sl，l ∈ L<$是sound当且仅当<$l ∈ L：αl（Sl）±lSl. 当verl∈L时，如果是完备的：SJlK±lαl（SJlK）。L36P. 库索河Cousot/Electronic Notes in Theoretical Computer Science 192（2007）29←J KDD{·}SFFZZ3按值调用λ演算带常数的λ-演算的语法是x，y，z，. ∈ X变量c∈C常数（X<$C=<$）c：：= 0|1|......这是什么？v ∈Vv：：=c|λx。 一值e∈E误差e：：= c a|e aa，aJ，a1，...，b，，.∈T项a：：= x |v |a aJ我们写a[x b]，用于b对a中x的所有自由出现的捕获避免替换。我们让FV（a）是a的自由变量。我们定义按值调用封闭术语的语义。（没有自由变量）。T{a ∈ T |FV（a）= 0}。函数λx a对值v的应用（λx a v）由下式计算：用实际参数v的a[x←v]替换形式参数x，功能体 这不能理解为归纳论的亲。文法语法因为a[x←v]一般不是（λx a v）的严格语法子成分因此下面的各种语义不能通过λ表达式的语法的结构归纳来定义因此，Sect的框架2.1用L=实例化，在L上被定义为假，这阻止了在程序语法上使用结构归纳法为了简洁起见，我们省略了空语法成分·，例如将F写成F·，对于·，Δ对于Δ·，等等。我们引入了一个最大的跟踪语义描述终止和发散计算。然后将跟踪语义抽象为关系语义[20]和操作语义[15]。每个语义都可以使用小步骤或大步骤的计算来定义。每个语义都可以用定点或基于规则的形式定义。语义不动点定义基于规则的定义大步小步大步小步T种族→S关系型操作Slfp±F→lfp±Flfp±f→lfp±flfpf=gfpf==- A.P. 库索河Cousot/Electronic Notes in Theoretical Computer Science 192（2007）2937∈ω{a，b，c，d，e，f} F S i∈i··⎪∪4按值调用的大步最大迹语义λ演算WeeletT（resp. T+，Tω，Tω和T∞）是有限的集合（分别为）。 nonempt yfinite，in finite，finite or in finite，and nonempty finite or in finite）项序列，其中n是空序列n·σ = σ·n = σ。 我们让|σ|∈ N <${ω}是σ ∈ T<$的长度。|= 0。|=0. Ifσ∈T+则|σ|>0且dσ=σ0·σ1·.. .·σ|σ|-1。 Ifσ∈Tω，则|σ|=ωdσ=σ0·.. .·σn·。 . . . 定义S+S <$T+，SωS <$Tω和S±TS+<$T +<$Sω<$Tω，使得定义域S <$T（T∞），±，Tω，T+，H，H <$是完备格.对于a∈T和σ∈T∞，我们定义a @ σ为σJ∈T∞，使得<|σ|：σiJ= a σi，类似地，σ @ a是σJ，使得<|σ|：σiJ= σia.4.1不动点大步最大迹语义闭调用-y-值λ-演算T的双无穷迹语义→S ∞（T∞）可以指定为定点形式→Slfp±F→其中迹线集合TransformerF→计算∈<$（T∞）<$→<$（T∞）描述了F→（S）{v∈T∞|v∈V}（a）{（λx. a）v·a [x←v]·σ|v∈ V<$a [x←v]·σ∈S}<$（b）{σ @ b|σ∈ Sω}<$（c）{（σ @ b）·（v b）·σJ|σ<$$>σ·v∈S+<$v∈V<$（v b）·σJ∈S}<$（d）{a @ σ|a∈V<$σ∈ Sω}<$（e）{（a @ σ）·（a v）·σJ|a，v∈V <$σj<$σ·v∈S+<$（a v）·σJ∈S}.（f）第（1）款F→的定义有：（a）终止，（b）所有-通过-值β-约化，（c）以及（d）用于应用下的左归约，以及（e）和（f）用于应用下的右归约，对应于从左到右的评估。（b）、（d）和（f）处理终止迹线和发散迹线。在Sect.2.1我们有Δ其中→i（），Δ由等式（）定义。连接操作符以二进制形式选择。我们观察到（S+S<$T+，S·S<$Tω所以S+<$Sω=<$）（二）→S=→S+→Sω⎨⎪→S+=F→(→S+)=lfp⊆F→+where38P. 库索河Cousot/Electronic Notes in Theoretical Computer Science 192（2007）29F→+（S）F→（S+）F→Sω=（F→（→S+F→Sω））ω=gf p<$F→ω 其中F→ω（S）（F→（→S+F→Sω））ω。双元迹语义→S的成立在于，P. 库索河Cousot/Electronic Notes in Theoretical Computer Science 192（2007）2939一JKBJ K←JK<$σ∈T∞：a·σ∈→S=<$σ∈→S。二元迹语义→S是全的，因为它排除了中间或结果错误εa∈T：/εσ，σJ∈Tε，e∈E：a·σ·e·σJ∈→S。有限个最大轨迹是阻塞的，因为有限个计算的结果总是一个最终值<$σ∈T∞<${<$}：σ·b∈→S+=<$b∈V.4.2基于规则的大步最大迹语义最大迹语义→S也可以定义如下v∈→S，v∈Va[x←v]·σ∈→S（ 。→±，v ∈Vλx a）v·a [x←v]·σ∈ Sσ∈→Sωσ·v∈→S+，（vb）·σJ∈→S±σ@b∈→S（σ@b）·（vb）·σJ∈→S±， v ∈Vσ∈→Sωσ·v∈→S+，（av）·σJ∈→Sa@σ∈→S±， a ∈V（a@σ）·（av）·σJ∈→S±， v，a∈V.定义→Sa{a·σ|a·σ∈→S}，→S+JaK{a·σ|a·σ∈→S+}，andnd→SωJaK{a·σ|a·σ∈→Sω}J，wKe可以写成→σ∈→SJa[x←v]Kv∈SJvK， v ∈V（ X. a）v→（x.（a）五±， v ∈Vσ∈→SωJK→λ·σ∈Sλσ·v∈→S+JaK，σJ∈→SJvbK±J→σ@b∈SJa bKσ∈→SωJKa@→ a B（σ@b）·σ∈Sa bσ·v∈→S+JbK，σJ∈→SJavK（a@a B） J→σ∈SJKσ·σ∈SJK观察到→S的归纳定义为也不应该被理解为关于a（since a [xv]（λx. a）v）也不作为动作诱导[16][17][18][19] 这个定义可以分为归纳规则，±， v ∈V±， a ∈V±， a，v∈V.40P. 库索河Cousot/Electronic Notes in Theoretical Computer Science 192（2007）29σ∈→SJKZZZZZ，σ TZZZZZ∈ ∈Z+ZγS⊥S∈ ×{}ñ⇒如（2）所示，对于发散，存在终止和共归纳规则，但上述双归纳定义避免了常见规则的重复。定义a=σa我们也可以写v=v，v∈Va[x←v]=<$σ（ 。.±， v ∈Vλxa）v=<$（λxa）v·σa=σ±ωa=ωσ·v，∈vb=σJ±， v∈V，σ∈Tab=σ@bb=σab=a@σab=σ（σ@b）·σJ， aV， σ Tωb=<$σ·v，av=<$σJab=（a@σ）·σJ±，a，v ∈V，σ ∈ T.5大步长跟踪语义到按值调用λ演算的大步长关系语义的抽象轨迹集的关系抽象是（三）α∈<$（T∞）<$→ <$（T×（T <${<$}））α（S）{|σ ∈ S |σ|= n}{σ0，|σ ∈ S |σ|= ω}γ∈<$（T×（T<${<$}））<$→<$（T∞）γ（T）{σ∈T∞|（一）|σ|=nσ0，σn−1（|σ|=ωσ0，∈T）}使得⟨℘(T∞),⊆⟩−←−−−−α−→−→−⟨℘(T×(T∪{⊥})),⊆⟩.二元关系语义学<$α（→S）中文（简体）（T）的））是将表达式映射到其最终值或发散情况下的跟踪语义的关系抽象。5.1不动点大步二元关系语义二元关系语义<$α（→S）=α（lfp±F→）可以定义为固定p的nt形式lfp±F，其中大步长Transformer<$∈F（T×（T<${f}））<$$> →F（T×（T<${F F{}））是F（T）{\fn黑体\fs22\bord1\shad0\3aHBE\4aH00\fscx67\fscy66\2cHFFFFFF\3cH808080}| v ∈ V} ∪{\displaystyle {\frac {x} a）v，r|v∈ V<$<$a [x<$v]，r<$∈T}<${（a b），|a，+±P. 库索河Cousot/Electronic Notes in Theoretical Computer Science 192（2007）2941FJ K⇒联系我们⊥±⊇ ⇒ ⊥⇒⊥ ±⊆∩×{\displaystyle {\frac {a\frac {b}，|a，v<$∈T+{（a b），|a∈V<$$>b，<$$> ∈T}<$+{\displaystyle {\frac {a\frac {b}，|a，v∈V <$$>b，v <$∈ T<$$>（av），r <$∈T}.定理5.1我们有α（F→（S））=α（α（S）），所以α（→S）=α（lfp±F→）=FSlfp±0.001。5.2基于规则的大步长二元关系语义大步长二元关系语义=Sa定义为a=SrAa，rA∈α（→Sa），其中a∈T，r∈T A{A}. 是a[x←v]=rv=v，v∈V（λx. a）v=πr±， v∈V，r∈V <${<$}a=ab=b=0ab=0±±， a ∈Va=v，vb=rab=rb=v，av=rab=r±， v∈V，r∈V <${<$}±， a ∈V，v ∈V，r∈V<${<$}.阿盖n这也不应该被理解为结构归纳（因为a[x←v]/n）。（λx a）v）也不是动作归纳（因为无限行为）。抽象α（T）T （T）的T）产生经典的自然语义[12]（其中所有规则 被淘汰，成为其余的）。抽象α（T）T（T）产生发散语义（仅保留具有、是 ，anda=在[ 15 ]中写为a=∞）。观察到Sec. 4.1和上述Sec. 5将“出错”的术语的语义定义为空。上面的big-step二元关系语义=等价于但不等同于标准的big-step语义，而后者是二元泛化。v=v，v∈Va=λx。c，b=vJ，c[x←vJ]=ra b=±， v，vJ∈V，a=ab=a=v，b=vab=v布雷尔±， v ∈Vr∈V <${<$}±42P. 库索河Cousot/Electronic Notes in Theoretical Computer Science 192（2007）29γ我们选择将应用程序的求值分解为更小的块，以便在参数求值之前强制执行函数求值，并在跟踪语义中明确减少步骤6按值调用λ演算的大步跟踪语义到小步操作语义的抽象一步归约语义通过收集沿着任何跟踪的所有转换来抽象跟踪语义。痕迹的小步骤抽象是αs∈ε（T∞）<$→ε（T×T）αs（S）{σi，σi+1|σ∈S<$0 ≤i<$i +1 <|σ|}。由于双参数跟踪语义是sunix封闭的，我们也可以使用α∈ε（T∞）<$→ε（T×T）α（S）{σ0，σ1|σ∈S|σ|> 1}因此，当S是超闭的时，我们有αs（S）= α（S）。 通过定义T_∞（T_∞）为T_∞的SUMX-闭和阻塞子集的集合，γ（τ）为由转移关系τ ∈ T_∞（T×T）生成的极大迹的集合，即γ+（τ）{σ∈T+|吉吉<|σ|：<$σi，σi+1<$∈τ<$<$a∈T：<$σ<|σ| −1，a<$/∈τ}γω（τ）{σ ∈ Tω|<$i ∈ N：<$σi，σi+1<$∈ τ}γ（τ）γ+（τ）<$γω（τ），我们有⟨℘(T∞),⊆⟩−←−−−−α−→−→− ⟨℘((T\V)×T),⊆⟩.6.1小步操作语义学小步长操作语义或转移语义S由二元迹语义→ S的α-迭代近似αs（→S）=α（→S）定义。（四）SLFPf（τ）{x（λx. a）v，a [x←v] |a0，a1 <$∈τ}{v b0，v b1}|<$b0，b1<$∈ τ}。（4）的基于规则的表示具有按值调用的β-归约公理加上用于在应用下归约的两个上下文规则，对应于从左到右的求值[20]。a −Ab表示εa，bε ∈S。P. 库索河Cousot/Electronic Notes in Theoretical Computer Science 192（2007）2943--−−−A{σ∈−XA|σn−1∈V}长度为n的最大执行迹−A- A最大有限执行跟踪ω−ω−n>0（（λx. a）v）−Aa[x←v]a0a1⊆a0b −A a1bb0A b1- 是的V b 0−A v b1S的归纳定义也可以理解为共归纳，因为lfp=绿色粮食计划署我们有α→β→γ的应力。事实上，由于单次跃迁，α<$F→αγstecf无法预测未来的计算是否会例如（（λx. x0）0）−A（00）∈f<$f（λ）while（（λx. x0）0）−A（00）/∈α<$F→<$γ<$α<$F→<$γ（λ x），因为不存在形式为σ·（λx）的迹。x0）0）·（00）·σjF→<$γ<$α<$F→<$γ（<$）。由此可见，小步长操作语义或转移语义S是合理的，但不完全的，因为由转移关系S生成的最大迹的集合γ（S）包括双有限迹语义→S加上可能“出错”的计算的伪迹，运行时错误e ∈E。7按值调用λ-演算小步极大迹语义∞A转换关系A被定义为−nA{σ∈T+|σ|σ|=n>0i：0≤i n−1：σi−Aσi+1}部分迹n n+n−A {σ∈T| ∀i ∈ N : σi−A σi+1}infinite execution traces−∞A+A 一个极大的有限的和可分的e-迹。7.1不动点小步最大迹语义表示小步长极大迹语义∞A在固定点的形式中，让我们定义迹线集合的结点为：S;TSω<${σ0·.. .·σ|σ| −2·σJ|σ∈S+σ|σ| −1=σ0J<$σJ∈T}，以及迹的小步长集Transformerf→∈N（T∞）→N（T∞）（五）f→（T）{v∈T∞|v∈V2}−X描述计算的小步骤。我们有一 ;44P. 库索河Cousot/Electronic Notes in Theoretical Computer Science 192（2007）29−SSñZ一−∞A=lf p±f→.大步长和小步长跟踪语义是相同的→S=−∞A.7.2基于规则的小步最大迹语义最大迹语义→S=∞A =lf p±f→其中f→由y（5）定义，可以用小步长归纳定义为v∈→S，v∈Va−Ab，b·σ∈→Sa·b·σ∈→S也就是说，对于σ∈→S和σ0=a，a−Ab，bZ <$σv<$Z<$v， v∈V±a·σ8按值调用λ演算的小步长二元关系语义二元关系语义被定义为α（→S）（其中α是迹集的关系抽象（3）），并在第二节中以大步形式给出。五、它可以通过抽象Sec的小步双无穷大迹语义以小步形式给出。 7.1.8.1不动点小步长二元关系语义二元关系语义→f（T×f f（T<${}））是f（R）{v，v}| v ∈ V} ∪{\displaystyle {\frac {x} a）v，r|v∈ V<$<$a [x←v]，r<$∈R}<${a0b，r|0−Aa1<$$>a1b，r<$∈R}<${v b0，r}|b0−Ab1<$vb1，r<$∈R}.±P. 库索河Cousot/Electronic Notes in Theoretical Computer Science 192（2007）2945S8.2基于规则的小步长二元关系语义二元规则库形式是（a<$b代表a，b<$∈，r∈V <${}）9结论v∈v，v ∈Va−Ab，brar发散/非终止行为在静态程序分析[18]或类型化[3，15]中是需要的这种分歧信息是经典序理论定点指称语义[17]的一部分，但在基于小步/抽象机器的操作语义[19，20，21]中并不明确，并且缺乏大步/自然操作语义[12]。因此，标准方法是从（标记的）转换系统/小步操作语义生成执行跟踪语义，使用序理论[4]或度量[23]定点定义或分类定义作为行为函子的最终余代数（建模转换关系）直到弱互模拟[11，14，22]或使用方程定义在序丰富的范畴中进行递归[13]。然而，执行跟踪并不总是处于适当的抽象级别。当扩展到双归纳结构双无穷小/大步跟踪/关系/操作语义时，有限和无限行为都可以由SOS处理。健全的（有时是完整的）抽象对于建立这种语义层次是必不可少的[4]。这应该满足形式有限和无限语义的需要，在不同的抽象层次上，并使用静态程序分析所需的各种等价表示（定点，等式，约束和推理规则）确认我们感谢匿名推荐人提供的有益意见和建议。引用[1] P. Aczel。归纳定义导论。在J.Barwise，编辑，数学逻辑手册，逻辑研究和数学基础第90卷，第739-782页。爱思唯尔，1977年。[2] I. Attali、J.Chazarain和S.吉莱特自然语义规范的增量评估。In M. Bruynooghe和M.《第四届国际研讨会论文集》编辑。PLILP '92，比利时鲁汶，1992年8月26-28日，LNCS 631，第87-99页。Springer，1992年。[3] P. Cousot。类型作为抽象的解释，邀请文件。在第24届POPL，第316-331页，法国巴黎，1997年1月。Press.[4] P. Cousot。抽象解释转换系统语义层次的构造性设计。理论计算。Sci. ，277（1-2）：47[5] P. Cousot和R.库索程序分析框架的系统设计。在第6届POPL，第269-282页Press.±46P. 库索河Cousot/Electronic Notes in Theoretical Computer Science 192（2007）29[6] P. Cousot和R.库索抽象的解释框架。J.逻辑与比较，2（4）：511-547，1992年8月。[7] P. Cousot和R.库索归纳定义、语义学和抽象解释。在第19届POPL，第83Press.[8] P. Cousot和R.库索在定点，等式，约束，闭合条件，基于规则和博弈论形式的组合和归纳语义定义，邀请论文。在p.Wolper，editor，Proc. 第七届国际 Conf. C AV'95 ， L i' ege ， BE ， LNCS 939 ， 第293-308页。7月3日至5日，施普林格一九九五年[9] 日德斯佩鲁TYPOL：一种实现自然语义的形式主义。Tech.代表RT-0094，INRIA Sophia Antipolis，Mar. 一九八八年[10] C.A.R.霍尔计算机程序设计的公理基础。ACM通讯，12（10）：576[11] B.雅各布斯和J·鲁滕。关于（余）代数和（余）归纳法的教程。EATCS Bulletin，62：222[12] G.卡恩自然语义学在K。Fuchi和M. Nivat，编辑，未来一代计算机编程，第237-258页。爱思唯尔，1988年。[13] B. Klin. 为双代数语义添加递归结构 J. 逻辑与代数Prog. ，60-61：2592004年[14] B. Klin. 结构操作语义学中的双代数方法ENTCS，175（1）：33[15] X.勒罗伊共归纳大步操作语义学。在P. Setoft编辑的Proc.15thESOP3月27日至28日，施普林格2006年。[16] R. 米尔纳并发进程的操作和代数语义 在j. van Leeuwen，编辑，形式模型和语义，理论计算机科学手册B卷，第19章，第1201-1242页。爱思唯尔，1990年。[17] 警 局 苔 藓 指 称 语 义 学 。 在 J.van Leeuwen ， 编 辑 ， Formal Models and Semantics ， Handbook ofTheoretical Computer Science，第11章，第575-631页的B卷中。爱思唯尔，1990年。[18] A. 迈克罗夫按需呼叫转化为按值呼叫的理论与实践芽孢杆菌中Robinet，编辑，Proc.4thInt.Symp。onProgramming，Paris，FR，22-24 Apr. 1980，LNCS 83，pages 270-281. Springer，1980年。[19] G.D. 普洛特金操作语义学的结构化方法技术报告DAIMI FN-19，奥胡斯大学，丹麦，9月。一九八一年[20] G.D.普洛特金结构操作语义学的起源。J.逻辑与代数Prog. ，60-61：3-15，Jul.-Dec. 2004年[21] G.D. 普洛特金操作语义学的结构化方法 J. 逻辑与代数Prog. ，602004年[22] D.图里和动力局普洛特金数学运算语义学。在Proc.12thLICS一九九七年。IEEE Comp.Soc. Press.[23] F.凡·布鲁格尔。度量语义学导论：程序设计和规范语言的操作和指称模型。理论计算。Sci. ，258：1
我的内容管理
展开
