没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子札记91(2004)96-115www.elsevier.com/locate/entcsProlog语言中移动环境的类型推断Elio Giovannetti1Dipartimento diInformaticaUniversit`adiTorinoCorso Svizzera 185,10149都灵,意大利电子邮件地址:elio@di.unito.it摘要环境演算M3 [8]的类型系统以一种新的形式呈现,该形式导出具有最小移动性假设集的项的类型,因此比原始形式更易于转换为类型推理算法。从新的配方Prolog程序派生,它实现了一个类型的推理算法M3类似于以前指定通过正式的规则。该实现以标准的方式利用了逻辑编程范式的特性,因此在某种意义上,这个严格的要求使他的个人意愿不能自我实现。关键词:类型系统和推理,逻辑编程,Prolog1介绍移动性(设备、软件甚至运行的程序)已经成为计算和通信的一个重要方面已经提出了几个理论模型来描述这方面,推理,从而控制系统的行为,其中流动性是一个相关的功能。大多数模型都是基于命名位置的概念[9],或者是在[7]中首次引入的移动环境的行为类型系统已经被广泛地提出作为控制移动性、干扰、安全性、资源使用的特权手段,从而扩展了类型的概念,远远超出了它在逻辑和计算机科学中的原始含义在这个新1由MURST公司2001年NAPOLI项目和欧盟在FET -全球计算倡议项目DART IST-2001-33477内提供部分支助1571-0661 © 2004 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi:10.1016/j.entcs.2003.12.007E. Giovannetti / Electronic Notes in Theoretical Computer Science 91(2004)96-97在这种情况下,类型仅仅是一段程序的行为属性,涉及人们感兴趣的任何方面;因此,在不同的系统中,为了不同的目的,类型可能具有在任何环境演算中,至少需要一个类型系统来确保通信的正确性。第一个系统也控制着流动性和开放性,尽管只是以二元方式(流动/不流动等),”[5]这是其中的一个。下一步在[6]中进行:环境组的概念允许定义能够更精细地静态跟踪环境运动的系统,同时避免类型依赖于环境名称。执行非平凡静态队列流分析的类型系统是在[3,4]中提出的,其中静态提供的运行时行为的近似是相当细粒度的。Boxed Ambients[2]的演算是第一个用环境间通信取代环境开放的环境演算,因此要求即使是最简单的类型系统也要同时处理通信和移动性(环境不能移动到它应该与不理解其语言的环境通信的地方)。 在[10]中,子类型第一次被广泛用于环境的类型系统中,以获得更大的表达能力和灵活性。[8]中提出的系统M3是移动环境演算[7]的变体,其中开放能力也被丢弃,并引入了一种新形式的进程移动性,类似于分布式π演算[9]的go原语。如在上面引用的提议中,演算配备有类型系统,该类型系统控制移动性并确保没有由于不恰当的价值观的沟通可能会发生。由于通常是语法导向的,M 3的简单类型规则可用于类型检查,因为它们可以被解读为一种算法的规范,该算法另一方面,它们不能用于类型重建,即,用于从给定的原始项trm生成有效的类型判断Etrm:类型,如果存在的话,其中|TRM|=trm,如果我们称原始术语为伪术语,其中所有类型信息都不存在,并且如果|TRM|是通过擦除所有类型信息从TRM获得的原始项。这主要是由于系统中存在一种隐含的弱化形式因此,在[8]中,类型重构算法是通过一组形式规则单独指定的;M3在[12]的意义上享有主属性,并且算法计算主类型(对于原始项trm)。在本文中,我们遵循一种补充方法:类型规则是98E. Giovannetti / Electronic Notes in Theoretical Computer Science 91(2004)96-重新转换成一种形式,消除了隐式的削弱(如果需要除principal之外的类型,可能在最后的可选步骤中将其隔离),并容易地转换为类型推断的逻辑编程实现。具有类似Horn的形式,每个规则对应于一个Prolog子句;统一和替换应用程序,内置于Prolog解释器中,不必显式指示。因此,Prolog原型实现在某种意义上比原始算法规范更抽象,正如众所周知的那样(例如,对于ML类类型系统)。只有一些机制必须明确编程。 主要的一个是从对应于两个子项的两个环境的并集生成一个项的良构(最小)环境。这是通过一个简单的循环来实现的,该循环迭代地计算环境简化变换的一种固定点,并在每一步执行必要的统一。一个(更简单的)固定点过程也需要通过隐式信息的展开将预类型转换为类型。本文的结构如下:第2节简要回顾了演算的语法和操作语义;第3节描述了类型和类型假设(环境)的语法和直观意义;第4节给出了类型规则的新公式,并与[8]中的公式进行了比较;第5节描述了实现的主要方面最后,在第6节中,得出了一些简短的结论并说明今后的工作。2微积分术语的语法如图1所示。注意观察,w.r.t.移动环境的演算,开放的不存在和新原语的存在,以用于“裸”过程移动性(通过“裸过程”,我们意指不具有m [ P ]形式的此外,允许同步输出,其中异步版本是一种特殊情况。我们遵循字母m,n,.对于环境名称和字母x,y,.输入变量。然而,在形式上,它们属于一个语法类别,我们称之为变量;简单地说,环境名是自由的变量,不出现在前缀或路径前缀位置(例如,x.P,x.M),或者被ν-绑定器绑定(但不被输入绑定器绑定)。字母“C”将用于表示一个泛型变量,它可以是一个环境名称,也可以是一个输入变量。此外,假设Barendregt约定[1]对任何项或项集的变量和组名(见下文)都成立:所有绑定变量(或绑定组名)都是不同的E. Giovannetti / Electronic Notes in Theoretical Computer Science 91(2004)96-99trm,trmi::=MP方面消息过程M,N,L::=消息你... m,n... x,y,.变量,即, 环境名称和输入变量在M中将包含环境移动到环境M中outM将包含环境移出环境MtoM从它的ambient到兄弟ambientMM.M′路径P,Q,R::=0M . PM(x:W)PP|QM[P]!P(νn:amb(g))P(v{g:G}(k))P−−→过程null前置同步输出型输入平行合成环境复制名称限制群限制其中:W是消息类型,g是组名称,ν{g:G}(k)是用于V{g1:G1,...,gk:Gk},其中g1,...,gk组名和G1,.,Gk群类型(见图1)。5)。−−→它们之间,并且与所有的自由变量(或相应的自由组名)不同这样就避免了与α-转换和自由名捕获图1:图2中给出的原始术语的语法是从普通语法中获得的,通过擦除输入和名称限制绑定器中的类型,并完全消除组限制构造。擦除函数的定义||,它将普通项trm转换为原始项|TRM|,是显而易见的。操作语义包括,像往常一样,一个减少关系,以及结构一致性,允许琐碎的语法重组的一个术语,以便减少规则可以下一步应用。结构一致性,如图3所示,与图3中给出的结构一致性不同。[8]因为组限制的范围也可以跨越前缀、输入、输出和复制;因此组限制可以总是被带到术语的最外面的位置。这一特征并不包括在通常的定义中,因为它并不满足允许形成赎回的主要目的。然而,它与另一个定义是自然一致的-100E. Giovannetti / Electronic Notes in Theoretical Computer Science 91(2004)96-trm,trmi::=原始项M个消息P原始过程P,Q,R::=0M. PM㈩PP|QM[P]!P(νn)P原始过程null前置同步输出输入平行合成环境复制名称限制图2:原始术语ing子句,并允许我们避免纯粹形式化问题的出现,因为类型重构算法留下了未确定的组限制可能插入项中的位置。 有了新的定义,这是无关紧要的:所有不同类型的术语都是等价的。请注意,由于Barendregt约定,即使是在将范围作为输入变量的情况下,范围挤出的第二条规则对于其余的,全等几乎是在[5]中发现的标准关系约简规则如图4所示。备注,w.r.t.原始的Mobile Ambients、同步输出、missingopen和to动作的规则,类似于Dπ的go原语或软件代理中用于强代码移动性的执行atom动作的进程在兄弟环境之间移动:从环境n(它最初所在的位置)到一个名为m的环境(它是n的兄弟环境)。因此,它在一个步骤中跨越两个边界;然而,边界在同一级别上,因此,与向上或向下移动不同,该过程不会改变其嵌套级别。执行inm或outm动作的进程像往常一样,分别将其包围的环境驱动到环境m中或从环境m中驱动出来3类型和环境类型的语法如图5所示。术语类型分为过程类型和消息类型,对应于术语的两个主要句法类别。反过来,消息类型可以是环境类型或能力类型,但不能是流程类型,因为消息不能是整个流程(演算不是高阶的)。为了在任何情况下都能很好地定义主体类型的概念,bot-E. Giovannetti / Electronic Notes in Theoretical Computer Science 91(2004)96-101等效性:一致性:PPQ=QPQ,QR=P RPQ = M。P M. QPQ = M[P] M [Q]PQ = M PM QPQ =!P!QP<$Q=<$(x:W)P<$(x:W)Q P<$Q=<$(νn:amb(g))P<$(νn:amb(g))Q−−→−−→PQ = P|罗克|RPQ= (v{g:G}(k))Pn(v{g:G}(k))Q前缀关联性:′ ′(M.M).P M.M.P并行复合P|QQ |P(P|Q)|RP|(Q |R)P|0元复制:!P P|!P!0 ≡0限制交换和组限制拆分:n/=m=(νn:amb(g))(νm:amb(g′))P(νm:amb(g′))(νn:amb(g))Pgig′gi/∈GN(G′)g′/∈GN(Gi)(1≤i≤k)(1≤j≤h)j−−→j−→j−−−→−−→=n(v{g:G}(k))(ν{g′:G′}(h))P(ν{g′:G′} (h))(ν{g:G}(k)P−−→−−→g gi(1≤i≤k)=<$(νn:amb(g))(ν{g:G}(k))P<$(ν{g:G}(k))(νn:amb(g))Pgk+j/∈GN(Gi)(1≤i≤k)( 1≤j≤h)−−→=(ν{g:G}(k+h))P≡(v{g1:G1,.,gk:Gk})(ν{gk+1:Gk+1,.,gk+h:Gk+h})P范围挤压:n/∈ AN(Q)= n(νn:amb(g))P |Q(νn:amb(g))(P |Q)n/==[(νn:amb(g))P](νn:amb(g))[P]−−→−−→gi/∈ GN(Q)(1 ≤ i ≤ k)=<$(ν{g:G}(k))P |Q ∈(ν{g:G}(k))(P|Q)−−→−−→n[(v{g:G}(k))P]≡(v{g:G}(k))[P]−−→−−→M. (v{g:G}(k))Pn(v{g:G}(k))M.P−−→−−→gi/∈GN(W)(1≤i≤k)=<$(x:W)(ν{g:G}(k))P<$(ν{g:G}(k))(x:W)P−−→−−→<$M<$(ν{g:G}(k))P<$ (v{g:G}(k))MP−−→−−→!(v{g:G}(k))P≡(v{g:G}(k))!P等于零:(v n:amb(g))0 ≡0−−→(v{g:G}(k))0 ≡0(v n:amb(g))n[0]0其中AN(Q)是Q中的自由环境名称的集合,GN(Q)是Q中的自由组名称的集合,并且GN(G)是G中的自由组名称的集合。图3:结构一致性102E. Giovannetti / Electronic Notes in Theoretical Computer Science 91(2004)96-引入了tom消息类型CNOW;在[8]中没有出现,它对应于一个无限消息类型。术语类型的唯一组成部分(除了CNOW)是amb(g),cap(g1,g2)或pr(g)的形式,是组名g;这些,反过来,可能是E. Giovannetti / Electronic Notes in Theoretical Computer Science 91(2004)96-103基本还原规则:(R-in)n [in m.P|Q] |m [R] → m [n [P |Q] |R](R-输出)m [n [输出m.P |Q] |R] → n [P|Q] |m[R](R到)n [到m.P|Q] |m [R] → n [Q] |m [P|R](R-R)(x:W)P|M|Q结构简化规则:(R-P′P′,P→Q,QQ′(R-v)P→Q(R-ν-群)P→QP′→Q′(νn:amb(g))P→(νn:amb(g))Q(v{g:G}(k))P→(ν{g:G}(k))Q−−→−−→(R-in)P→ Q⇒P|R → Q |R(R-amb)P→ Q⇒n[ P] → n[ Q]图4:减少使用组类型进行类型化,其形式为gr(S,C,E,T),其中S,C和E是组名的集合,T是通信类型。在移动性类型中使用组(从纯数学的角度来看,这是一个相当不幸的名称)是避免类型和值之间依赖性的标准技术,这将防止或使有意义的术语的简单类型化变得不正确。直观地说,组名g挑出具有“相同属性”的环境的集合类型cap(g1,g2)是可以由g2进程(在g2环境中)执行的动作的类型,延续是一个G1过程(在G1环境中)。我们回想起组类型的直观含义,即,假设g:gr(S,C,E,T)的含义:• S是环境组的集合,其中组g的环境可以停留;• C是环境群可以跨越的环境群的集合,即,那些他们可能被赶进或出,分别通过在或出的行动;它必须是C/S;• E是(裸)g-进程可以• ”(《易经》卷一)“言之以信,行之以行,行之以行。104E. Giovannetti / Electronic Notes in Theoretical Computer Science 91(2004)96-1氛围为了处理(OUT)规则中组类型的S分量上的条件,引入了包含带星号的组名称的组前类型组前类型gr(S,C,E,T)与类型的区别在于第一个组成部分S可以包含组名和带星号的组名。群预类型假设g:gr(S,C,E,T)的含义与群类型假设的含义相同,不同之处在于每个g∈S表示g1-ambient可以停留的所有环境群,即,它表示集合S1的所有元素,使得g1:gr(S1,)(如果这样的假设存在于环境中)。几乎所有的类型规则实际上都涉及群前类型;没有星号群的真正类型只有在最后阶段通过显式地展开星号的含义才能获得。如果G=gr(S,C,E,T)是一个群预类型,我们写S(G),C(G),E(G),T(G)来分别表示G的分量S,C,E,T;一个类似的符号当然可以用于群类型。通信类型是组(前)类型的组成部分,但它们不是术语类型; T是环境中允许的通信类型,它可以由消息类型组成,但也可以是通信的缺失,由shh表示。注意,新引入的无限消息类型CNOW与shh不同。与[8]不同的是,为了强调由消息类型组成的通信类型与其组件属于不同的类别(因此它是元语言中的不同数据类型),使用了一元类型构造函数com一个环境(或一个前环境)E由两个部分组成:一个组(前)环境Γ和一个变量(和环境)环境Γ,由以下语法定义:E::=r; Er::= r| r,g:G(or g:G)::=| ,其中,变量是变量或环境名称。在下文中,除非另有说明,否则为环境引入的所有概念也将被隐含地考虑为前环境定义,并明显地用前类型代替类型。环境的定义域是Dom(E)=Dom(T)<$Dom(E),其中:Dom(r,g:G)=Dom(r)<${g}Dom(r,g:W)=Dom(r)<${g}GN(G)表示出现在群类型G中的所有群名的集合,GN(E)表示出现在E中的所有群名的集合,不仅出现在Dom(Γ)中,而且还出现在E中的类型的分量中。环境被认为是语句的集合,因此是模置换。E. Giovannetti / Electronic Notes in Theoretical Computer Science 91(2004)96-105G::= gr(S,C,E,T)群预型g,h,.组gh...星号群S组群和星号群;类型::= WPRW::=中国琥珀色(g)帽PRGterm型讯息类型处理类型消息类型任何消息环境类型:g能力类型:预先定义为pr(g1)类型的过程的能力,将其转变为pr(g2)进程类型:可以停留在g组类型不* =pr(g)* =gr(S,C,E,T)关于C* =通信类型嘘,不要交流com(W)W类型消息的通信g,h,.组S,C,E,.组的集合;G是群图5:类型图6:组前类型一个变量环境变量是良构的,如果对于每个变量∈Dom(变量),在变量中只有一个类型与之相关联,即,不存在W1与W2 不 同的n:W1,n:W2∈n.我们假设所有的变量环境都是良构的。类似地,群环境Γ是良构的,如果对于每个g∈Dom(Γ),在Γ中恰好有一个群类型G与它相关联。当然,在类型判断中只允许格式良好的组环境,但是(潜在地)非格式良好的组环境被类型推断过程使用。我们用标准符号G,G:W来表示一个包含状态G:W的变量环境,假设gt∈/Dom(G);类似于Γ,g:G;等等.两个可变环境1、2是兼容的,写为12,如果12002是一个格式良好的环境。 两个群环境Γ1和Γ2是相容的,也写为Γ1 Γ2,如果:(g:gr(S1,C1,E1,T1))∈ Γ 1,(g:gr(S2,C2,E2,T2))∈ Γ2<$T1= T2.106E. Giovannetti / Electronic Notes in Theoretical Computer Science 91(2004)96-我们将写为Γ1 Γ2 Γ3以指示Γ1、Γ2、Γ3是成对相容的;等等。两个相容环境Γ1和Γ2的G-并是(良构)环境:r 1r 2=(r 1<$r 2− {(g:G)|g ∈ Dom(Γ 1)<$Dom(Γ 2)})<$ΓJ,其中:Γ ′={g:gr(S 1<$S 2,C 1<$C 2,E 1<$E 2,T)|g:gr(S1,C1,E1,T)∈ Γ 1&g:gr(S2,C2,E2,T)∈ Γ 2}偏序是根据通信和组类型自然定义的:W≤Wshh ≤com(W)W≤Wjgr(S,C,E,T)≤gr(SJ,CJ,EJ,TJ)如果S<$SJ,C<$CJ,E<$EJ,T≤TJ通常,陈述T≤TJ的直观含义是T是TJ的子类型,即,一种更专门的通信类型;在组类型的情况下,关系G≤GJ意味着G比GJ更具限制性,因为允许一个人停留或允许哪个人停留的环境集合十字架等,更小。该顺序通过集合包含单调地扩展到环境:如果n(g:G)∈ Γ,则Γ ≤ Γ j. n(g:GJ)∈ Gj,G ≤ GJ如果n(n:W)∈ n,则n ≤ n j. n(n:W J)∈ n J.W≤ W J如果Γ≤ ΓJ且≤J,则为Γ;≤ Γ j;J同样,环境排序E≤ EJ的含义是E是比EJ更具约束性的假设集。然后,与[ 12 ]一致的主类型化的概念是可以定义的:类型化判断EM3 P:pr(g)是主的,如果对于每个可导类型化E jM3PJ:pr(gJ),使得|PJ|为|P|当P和PJ不受群限制时,存在从群名到群名的置换σ,使得σ(g)= GJ且σ(E)≤EJ.类似地,我们可以定义主类型的概念Etrm:Typefor a generic term(即,不仅是过程)。P和PJ不包含群限制的条件并不违反主类型化的标准定义,因为群限制是通过抽象w.r.t.在最后的打字步骤中,通过规则GR pRES注意,由于术语类型仅由组名组成,因此r.h.s.的旋转栅门是相同的模组名称的重命名打字判断的特征是什么E. Giovannetti / Electronic Notes in Theoretical Computer Science 91(2004)96-107因此,主要的是环境E是允许键入给定(原始)项trm的最严格的假设集合,即,要正确键入术语所需的最小权限集4类型规则M3的原始类型赋值规则在图7中给出,遵循上一节中给出的语法。如在引言中所观察到的,系统不提供用于推断可键入术语的(主要)键入的算法,这是因为在规则E中明显的隐式弱化,当然再加上单个规则的不同类别包含相等环境的事实。这一现象在证明论和函数式语言的类型系统中都是众所周知的;在这种情况下,通过延迟弱化的应用直到推理过程结束,可以获得一个更算法化的系统。面向主体类型化的新类型化规则集如图8所示。在规则(E)、(N)和能力的规则中,环境由最小移动性假设组成;在系统的其余部分中,规则的不同属性具有不同的环境,这些环境在结论中被关于通信类型的假设不是最小值的原因,正如从能力规则中的通用T而不是shh的存在中显而易见的那样,是这种最小值,尽管理论上更适合于预期的框架,但会使逻辑编程实现更加复杂而不需要。相反,最小通信类型仅在Prolog程序中通过统一化自动获得,然后通过一个最终步骤,其中未实例化的通信和消息类型被实例化为它们各自的最小值,如下面将解释的。第(IN)及(OUT)条规则订明,行使输入/输出命令的法律程序─pability不改变它的组g2,因为它不改变它的封闭g2-ambient;最小移动性假设是g2-ambient(仅)被允许穿过g1-ambient(如g1),因此也被允许(仅)停留在 g1-ambient中(此处和下文中观察到,如果g1是输入,变量,到动作执行时,变量将被环境名称替换)。在旧系统中,规则(IN)和(OUT)有几个例外。然而,E M3g:G和E M3M:amb(g)形式的表达式反过来只能通过(E)规则导出,即,从g:G或amb:amb(g)分别在E中的事实,M专门化为amb。像往常一样,通过结合两者108E. Giovannetti / Electronic Notes in Theoretical Computer Science 91(2004)96-g:G∈Γ:W∈(Er)(ER)r;β3g:GE/CN.30:pr(g)(无)MΓ;β3β:WME组3g2:G2E ∈M3M:amb(g1)g1∈C(G2)E-3M inM:cap(g2,g2)(IN)EM3g1:G1EM3g2:G2EM3M:amb(g1)g1∈C(G2) S(G1)→S(G2)(OUT)E-3M outM:cap(g2,g2)E-3M g2:G2EBLM3 M:amb(g1)g1∈E(G2)(TO)E-3M 到M:cap(g1,g2)EM3M:cap(g3,g2)EM3N:cap(g1,g3)(PATH)E M3M.N:cap(g1,g2)E-3M M:盖(g1,g2)E-3M P:pr(g1)(PREFIX)E/CN.3M.P:pr(g2)r; r,x:W<$M3P:pr(g)r; r<$M3g:gr(S,C,E,com(W))(IN pUT)r; r=M3(x:W)P:pr(g)EM3P:pr(g)EM3M:WEM3g:gr(S,C,E,com(W))(OUT pUT)E/CN.3/CN.4/CN.5/CN.4/EM3P:pr(g)EM3M:amb(g)E ∈M3g:G g∈S(G)′(AMB)′EM3M [P]:pr(g)E/CN.3P:pr(g)E/CN.3Q:pr(g)E/CN.3P:pr(g)(PAR)(RE pL)E-3P|问:pr(g)E M3!P:pr(g)r; n,m:amb(g′)nM3P:pr(g)r; n=3(νm:amb(g′))P:pr(g)(AMBRES)Mr,g1:G1, . . . ,gk:Gk;M3P:pr(g)gi∈/GN(Γk)gi/=g(1≤i≤k)(GR pRES)I; I; I (v{g1:G1,.,gk:Gk})P:pr(g)图7:键入规则E. Giovannetti / Electronic Notes in Theoretical Computer Science 91(2004)96-109;(E)(无)◦n;n0:pr(g)◦g:gr({g},{g},T);T:amb(g)T:cap(g,g)(IN)21 11◦2 2g:gr({g,g},{g},T); 中文(简体) 输出端:cap(g,g)∗(OUT)21111◦2 2g:gr(n,n,{g},T); 中文(简体) 到g:cap(g,g)(TO)211◦12r1;n1n(PATH)r1r2; n1n nn2nn nM. N:盖(g1,g2)Γ1;1M:cap(g1,g2)Γ2;2P:pr(g1)Γ1Γ212(PREFIX)r1r2; n1n nn2nn nM. P:pr(g2)r;r=P; r =p(g){x:W}当r r r r r 0n{ g:gr(n,n,n,c o m(W))}时,rr rr 0n { g:gr(n,n,n,c o m(W))}(IN pUT)ΓΓ0; <$−{x:W}<$(x:W)P:pr(g))r1;n1nn nP:pr(g)r2;n2nnn nM:Wr1r2r0n 1n n n2(OUT pUT)r1r2r0;r1r2 r 0;r1r2 r2r2r0MP:pr(g)其中,Γ0<${g:gr(m,m,m,com(W))}r; r,r:amb(g)rP:pr(g) Γ Γ 其中,Γ{g:gr({g′},T)}◦00Γr; r,r:amb(g)r [P]:pr(g′)(AMB)0◦r1;r 2; r 3; r 4; r 5; r 6; r 7; r 8; r 9; r10; r 11; r 12; r 13;r14; r 15; r16; r 14; r 15;r2;n2nnQ:pr(g)r1r2n1nn2(PAR)r1r2; r 1 r 2; r1r2|Q:pr(g)r;r=P; r =p(g)(RE pL)你好!P:pr(g)r;nP:pr(g)n{m:amb(g′)}◦Γ;<$− {m:amb(g′)}<$(νm:g′)P:pr(g)(AMBRES)◦图8:主体类型逐步进入单个规则并且通过在任何地方用满足那些条件的最小集合替换成员条件,规则变成公理(即,没有规则)。例如,在规则(IN)中,条件(g2:G2)∈Γ和(g1:amb(g1))∈110E. Giovannetti / Electronic Notes in Theoretical Computer Science 91(2004)96-1成为Eg2:G2;:amb(g1);条件g1∈C(G2)成为C(G2)<${g1},群型良构性条件C<$S成为S <${g1}。此外,在(OUT)的情况下,g2-ambient-规则(TO)指出,如果由群g2的过程(在g2-环境中)执行,则将g1的过程作为继续,如果g1是g2的过程;最小假设是(裸)g2-过程只允许去(即,发送它们的延续)到G1环境。规则(PATH)和(PREFIX)规定,能力的顺序组合需要单个能力分别需要的移动性假设的联合(其中,在对同一组g的类型进行不同假设的情况下,执行不同类型的同源组件S、C、E的联合,如操作定义所规定的)的。规则(PAR)对于并行合成也是这样中心规则(AMB)是相当标准的:它要求在项[P]中,周围环境和它的内容P属于同一组,而过程[P]是一个完全被动的对象,既不能通信也不能移动其他环境,可以反过来留在任何环境中,即,它可以是任何组GJ。最低限度的要求是,g-ambients(如families)被允许留下来在gJ-环境中,如通过将gJ添加到类型G。其余的规则相当简单;只观察到在“抽象”中,即,在(INpUT)和(AMB RES)中,由于前提中环境的最小性,结论中需要集合论的差异,与图7中的同态规则不同。例如,在(IN pUT)中,不能假设语句x:W总是存在于类型为P的环境中:如果x不在P中出现,则在环境中不会出现这样的语句。从上面可以清楚地看到,在这个系统中,正如在一个在图7中,可导出不仅仅是主要类型的更多类型,因为元变量T和W可以分别是任何通信类型和任何消息类型,而不仅仅是最小类型。然而,如果我们把类型系统看作一个逻辑理论,把可导出的类型判断看作这个理论的定理,那么T和W就变成了(不同种类的)逻辑变量,它们可以在一个项的类型化中自由出现;T和W的自由出现,被隐含地普遍量化,可以分别实例化为任何通信类型和任何消息类型,特别是最小的类型。E. Giovannetti / Electronic Notes in Theoretical Computer Science 91(2004)96-111因此,将T实例化为shh,将W实例化为WrittenW, 产生最小类型。这正是在实现中发生的事情,其中T和W是Prolog变量,可以通过类型推理算法保持未实例化,在这种情况下,它们分别绑定到最后的原子shh和w(对于WP2W举例来说,请注意finish(T):-var(T),!,T=嘘。finish(_).此外,群前类型必须通过展开星号群名所传达的所有信息而转化为群类型这是由闭包函数完成的,它计算变换的最小不动点Γ<$→{g:gr(S(G)<$(gJ∈<$(S) gJ:GJ∈Γ&S(GJ)),C(G),E(G),T(G))|g:G ∈ Γ}其中,S ={g|g∈S},并最终删除所有带星号的组。因此,我们可以引入类型判断固有Γ;环境固有·trm:类型,其中Γ环境固有(即,没有星星),通过以下规则:ΓJ;类型闭包(ΓJ);类型闭包·trm:类型(C输)其中必须提醒的是,trm是进程P或消息M,并且相应地Type是进程类型或消息类型。类型化关系可以被示出为对应于原始关系在以下意义上的第三个• (soundness)if Γ;·trm:Typeholds,then also Γ;M3trm:Typeholds;• (completeness)if r; trm:类型成立,则存在项trmJ结构上等同于TRM(即,trmjtrm)的形式trmJ=(v{g1:g1,.,gk:Gk})trm0其中trm0不受群限制,存在Γ J和J使得Γ J; J<$M3 trm0:Type成立,其中Γ J≤ Γ,g1:G1,. ,gk:Gk,且φ J≤ φ.因此,任何在原始系统中可导出的类型都可以通过环境的包容从我们的新系统或者,我们可以在新的类型系统中增加第三种判断,它是由一个弱化规则引入的,也是由一个与第三章中的规则相同的群体限制规则定义的,但现在只适用于顶部。112E. Giovannetti / Electronic Notes in Theoretical Computer Science 91(2004)96-级别:E·trm:TypeE≤ EJEjtrm:Type(WEAK)r,g1:G1, . . . ,gk:Gk; G_kP:pr(g)gi∈/GN(Γ_k)gi/=g(1≤i≤k)r; n(v{g1:G1,.,gk:Gk})P:pr(g)(GRpRES)有了这个定义,可靠性和完整性当然就成了两个系统之间的等价:类型保持 当且仅当 E-3M trm:类型保持然而,注意,如果人们只对主要类型感兴趣,那么只需要关系·:从上面可以立即看出,M3和·的主要类型是一致的。5Prolog实现Prolog实现只关注类型E·;特别地,程序将原始项trm作为输入,并返回主类型E·trm:Type,使得|TRM|= trm。因此,如果判断E·trm:Type是可导出的,那么Prolog程序,输入原始项|TRM|通常不返回原始类型,也不简单地返回具有可能“较少限制”的环境的类型。相反,它返回一个类型E0·trm0:Type0,这样,对于一个替换σ,其中σ(E0)≤E,σ(trm0)=trm,σ(Type0)=Type。如第4节所述,这取决于这样一个事实,即当规则被翻译成Prolog子句时,所有未实例化的逻辑变量最初都是新的不同变量,而在一个逻辑判断的形式演绎中,例如,可以从不同叶子中的相同名称开始,即,其中逻辑变量已经被某个σ实例化;因此最终得到一种类型,它是(大于)主类型的σ-实例在Prolog中编码新类型规则的第一步是为组和变量环境Γ和Γ选择合适的表示。在工作原型中,它们被简单地实现为列表:特别地,它们被实现为由未绑定的逻辑变量终止的列表。然后,在检查它不存在之后,通过逻辑变量的绑定(逻辑编程的标准技术)“强制性地”修改列表,可以在列表的末尾添加新元素中类型的所有集合组件都采用同一种表示形式E. Giovannetti / Electronic Notes in Theoretical Computer Science 91(2004)96-113环境对象语言变量和环境名由Prolog常量表示。组名由Prolog变量表示,因此当两个不同的组名必须相等时,解释器执行的统一可能会被利用。另一方面,由于组名是对象语言实体,而不是实际的元变量,因此经常需要测试它们的相等性:在这种情况下,当然必须求助于逻辑外的Prolog的基本类型,比如操作符==。虽然类型在它们的原始形式和新形式中都不包含类型变量,但在程序中自然使用类型元变量,由Prolog变量表示。每一个类型规则几乎都字面上翻译成一个Prolog子句;唯一的区别是,结论中环境的构造和结论中环境之间的兼容性检查显然被组合成一个单一的过程sumunion,它试图通过可能的“进一步实例化”组件环境来构建结论然而,这样的操作不能通过统一自动执行,因为两个组环境的集合论并集可能产生非良构组环境Γ,其中具有不同通信类型的组类型被分配给相同的组名;如果这样的通信类型是可统一的,则统一器可能依次等同于具有不同通信类型的其他组,等等。因此,环境的完成必须通过迭代来明确编程,该迭代在每个步骤中都试图统一由前一个统一步骤生成的不同通信类型。由于在任何给定环境中组名的数量是有限的,因此迭代肯定会终止,要么失败(不可统一的类型),要么成功(没有“关键类型对”)。相关的Prolog子句是:sumunion(Env1,Env2,GEnv1,GEnv2,GEnv):-uniongenv(GEnv1,GEnv2,GEnvU),unionenv(Env1,Env2),comp(GEnvU,GEnv).Prolog过程comp包含一个命令循环,它试图通过统一通信类型和加入组集,将可能非良构的环境转换为良构的环境集合成分的联合在每一步递增地执行,连同通信类型的统一,通过子句:unigt(gr(S1,C1,E1,T1),gr(S2,C2,E2,T2)):-union(S1,S2)、union(C1,C2)、union(E1,E2)、uniw(T1,T2)。T1和T2之间的统一也必须通过显式子句来完成,因为它必须检查是否产生了组名的新标识,这是uniw(T1,T2):-var(T1),!,T1=T2。114E. Giovannetti / Electronic Notes in Theoretical Computer Science 91(2004)96-uniw(T1,T2):-var(T2),!,T1=T2。uniw(T1,T2):-T1==T2,!.uniw(T,T):-retract(repeating(_)),assert(repeating(true)).一旦定义了所有的辅助ΓJ隐式尝试以这样的方式实例化两个环境Γ和ΓJ,如上文所述。另一方面,被删除的形式为j的语句会被Prolog unionenv子句中的unionenv自动检查,也会被sumunion调用。例如,平行合成的规则简单地变成:typing(GEnv,Env,P1 par P2,pr(G)):- typing(GEnv1,Env1,P1,pr(G)),typing(GEnv2,Env,P2,pr(G)),sumunion(Env1,E
下载后可阅读完整内容,剩余1页未读,立即下载
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- VMP技术解析:Handle块优化与壳模板初始化
- C++ Primer 第四版更新:现代编程风格与标准库
- 计算机系统基础实验:缓冲区溢出攻击(Lab3)
- 中国结算网上业务平台:证券登记操作详解与常见问题
- FPGA驱动的五子棋博弈系统:加速与创新娱乐体验
- 多旋翼飞行器定点位置控制器设计实验
- 基于流量预测与潮汐效应的动态载频优化策略
- SQL练习:查询分析与高级操作
- 海底数据中心散热优化:从MATLAB到动态模拟
- 移动应用作业:MyDiaryBook - Google Material Design 日记APP
- Linux提权技术详解:从内核漏洞到Sudo配置错误
- 93分钟快速入门 LaTeX:从入门到实践
- 5G测试新挑战与罗德与施瓦茨解决方案
- EAS系统性能优化与故障诊断指南
- Java并发编程:JUC核心概念解析与应用
- 数据结构实验报告:基于不同存储结构的线性表和树实现
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)