没有合适的资源?快使用搜索试试~ 我知道了~
199理论计算机科学电子笔记70第3期(2002)URL:http://www.elsevier.nl/locate/entcs/volume 70. html18页s参数化数据类型Yngve Lamo1挪威卑尔根大学工程学院,5020 Bergen,Michal- Walicki2挪威卑尔根大学信息学系,5020 Bergen,摘要在[5]中,我们介绍了一个用于指定参数化数据类型的框架,该框架利用了基于推出构造的传统语义的泛化。 在本文中,我们使用这个框架解决程序开发的问题,特别强调细化的概念。与松散的规范不同,细化并不仅仅意味着缩小模型类,而主要是将额外的结构引入到指定的程序中。我们给出的例子是基于这些规范的经典垂直和水平组成的类似物1介绍大型软件项目很好地推动了软件开发中对模块化技术的需求在这样一个大型项目的实施阶段,可以将整个系统的子任务识别为参数程序。通过逐步识别子任务,整个系统可以通过组合参数化程序来实现。参数化规范和参数化程序的规范之间的重要区别最初在[8]中指出。主要的区别在于被重用的对象。参数化规范,即这使得PSP适用于在软件项目的分析阶段构造问题域。参数化数据类型,第1yla@hib.no2 michal@ii.uib.no。第二作者感谢挪威研究理事会(NFR)的财政支持。2002年由ElsevierScienceB. V. 操作访问根据C CB Y-NC-N D许可证进行。拉莫和瓦立基200“PDT” [8,9], on the other hand, requires a reusable这样一个规范的模型类被看作是由一些(也许是所有)函子组成的,这些(1)FMod(P[X])<${F:M od(X)→M od(P[X])}.现在,一个以另一个程序X为参数的程序P不能在P的上下文中,也就是在P [ X ]中改变X-X这种“保持实际参数”的直觉已经被确定为语义要求之一,即来自(1)的函子的持久化,例如,[2,10,1]。然而,这个要求是非常严格的,一般来说,禁止从具有新元素的参数程序扩展数据类型在[5]中,我们介绍了一个更充分的框架来指定PDT。我们推广了持久函子的概念,使得我们的持久函子可以向参数代数中添加新元素,但仍然保证其保护。这推广了[6,7]的想法(其中只有新的错误元素的扩展是可能的),通过允许扩展也有“常规”元素(例如,通过添加逆元素将幺半群扩展为群),并选择参数指定的公理是否适用于新元素。本文的新贡献是改进的概念和有关PDT合成的结果。我们讨论了与实现的经典概念(如模型类包含)相关的PDT的改进。主要区别在于我们将PDT视为设计规范,即,相当低级别的规范,不仅规定了一些所需的功能,而且还规定了程序的特定结构然后,精化相当于引入额外的结构,并举例说明了[9]中的“构造函数规范”的思想。我们还提出了关于PDT的垂直和水平组成的结果,实际上,这些结果提供了细化的例子。他们的关系,各自的经典概念进行了讨论。为了使本文至少在某种程度上自成一体,我们在第2节中总结了[5]的内容。更多的细节和证据,读者可以参考[4]。第3节以PDT细化的一般概念开始,然后通过垂直和水平组成来举例说明。该演示文稿是基于机构的多代数[3],但它应该很容易辨别其更一般的应用。第4节载有对此的一些评论和其他结论性意见。拉莫和瓦立基201∪2背景我们在多重代数MA的机构中工作,[3],允许指定非确定性数据类型。但这里使用的唯一方面是MA允许将常数解释为集合(即,一元谓词)。定义2.1给定一个标准代数签名<$=(S,<$),一个<$-多代数A由下式给出:• 对于每个排序符号s∈S,• 运算ωA:sA×. × sA→ P(sA)对于每个操作符号ω:1Ns1,.,sn→s∈ n• 运算的合成由逐点扩展定义:对于集合X,sA:ωA(X)=x∈XωA(x)在X上的项和来自X的变量,T(X,X)以标准方式定义,然后任何赋值α:X→|一|从携带者的个体的一个唯一的解释α(t)的所有条款t∈T(X)。定义2.2一个规范SP由一个特征向量和一组特征向量公式组成,这些特征向量公式或者是原子:• t=stectJ,对于t,tJ∈T(X,X)• t<$tJ,对于t,tJ∈T(X)或一般序列:1. . . anb1. . . bm,其中achai,bj是原子。定义2.3一个特殊化SP的模型,Mod(SP)是所有满足SP公理的多重代数的类,根据以下。给定赋值α:X→|一|,A| = αφ i φ:• 一|=αt=stectJi<$α(t)=α(tJ)={e}对于s ome e∈|一|• 一|= αt <$tJi <$α(t)<$α(tJ)• 一|= αa1. . . anb1. . . bmiai:A|= αai,orrbj:A|= αbj。A满足φ,A| = φ,i|对于所有α,= αφ。这些片段产生机构MA,其中模型范畴中的态射是弱同态,即,满足h(ωA(x))<$ωB(h(x))。MA是半精确的(实际上是精确的),也就是说,模型函子发送推出各模型类回调的规范。这为参数化数据类型的语义提供了基础为了指定PDT,我们首先介绍一种特殊的签名表示每个签名都有一组独特的常量符号S=*C。集合*包含用于各种排序符号的常量符号,用于表示各个排序的所有元素;C可以包含表示子排序的附加常数。定义2.4带有排序常数的签名是(S,,*,C),拉莫和瓦立基202≺联系我们≺⇒S =(S,S)是一个普通的签名,* C= S是一个(可能是空的)有限签名集,比如SC=和*C=。定义2.5给定φ=(S,φ,*,Cφ),我们令:(i) − =(S,(ii) =(S,同样,对于一个普通的S-性质<$=(S,<$),我们有<$=(S,<$,*,<$),其中 *={*s:s f or each s ∈ S}.我们说的“签名”是指带有排序常量的签名。当*和C之间的区别不重要时,我们简单地写S。(签名态射将排序常量映射到排序常量。)为了编写参数化数据类型的规范,我们将使用保护公理。一般来说,我们只需要参数指定的公理只对参数代数中的元素成立定义2.6对于一个a_x=(S,x,*,C_x),我们区分如下:(i) 保护γ是一个原子x<$p,其中x是一个变量,p∈S<$=*<$C<$;(ii) (完全)保护公式的形式为γ,ab,其中• a、b是α-原子的序列,• γi是一个保护序列sγi:xipi,对于每个(且唯一)变量xi存在于原子a,b中在这种公式条件下的γi一个基本公式是受保护的,因为它没有变量。*可能出现的唯一地方是在守卫i中,因此在守卫公式ii的前件中。 守卫x<$*,其中*∈*,只是特殊情况定义2.7一个保护规范是SP=(,Φ,Γ),其中:• 对于每一个排序s,=(S,,*,C)有(至少)一个常数*s∈*。• 每一个φ∈Φ∈是一个(完全)保护公式。• Γ s=xs*s:*s*是一组公理,称为全局守卫(具有适当排序的变量,如下标所示)。请注意,所有形式为x * 的局部守卫... 在一个受保护的规范中,由于全局保护的存在,然而,这种明显多余的句法形式对于定义关于具体化的结构是很重要的。所有这些构造都将假设所涉及的规范是受保护的。定义2.8给定一个有保护的规范SP−=(φ1, Φ2, Γ2),它的弱化是一个规范SP−=(φ 1,Φ2)。相反,对于一个普通的规范SP=(φ, Φ),SPφ表示拉莫和瓦立基203∪∪→≺ ≺ ≺ ≺⇒保护规范(sq, Φq, Γq),其中*与def中相同2.5,则τε =(S,τε,*)且τε ={xε*s:*s∈*}。请记住,给定一个具有签名的规范SP,其弱化版本SP−的签名仍然是而不是−。一个保护的规范SP<$的模型就是满足Φ<$Γ <$的多重代数(在签名(S,<$S<$)上)。给定一个普通的规范SP,在无保护Mod(SP)和保护Mod(SP)之间存在一个明显的模型范畴等价性。此外,对于一个受保护的SP函子,有一个明显的包含函子将每个代数发送给它自己:(2)id−:Mod(SP−)→Mod(SP−)。2.1参数化数据类型的规范定义2.9参数化数据类型规范(PDT)是一个四边形(μ,X,P[X],δ),其中(i) X=(,Φ,Γ),P[X]=(j, Φj, ΓjJ)是保护规范,(ii) j=(S,(iii) µ:*→*JCj被称为一个命名的特化态射(iv) δ:*→*J∈C_(?)J称为一个保角映射(v) 两个映射μ和δ是这样的:(a) 对每个公理φ∈Φ∈:δ(φ∈)∈ΦJ∈。(b)如果µ(*s)/= δ(*s)/=*s,则µ(*s)<$δ(*s) ∈Φ J为了方便起见,我们将μ和δ视为签名态射这是所有符号上的恒等式,除了(可能)一些*简单地包含在P[X]中。我们把δ写在元组的末尾,因为在许多构造中它不起作用,然后它可能会从符号中删除。出于所有实际目的,我们可以认为语法是由μ和δ给出的,其中δ(*s)=μ(*s)或者δ(*s)=*s(见下文)。这涵盖了大多数自然情况,在我们所有的例子中也是如此(v)。(a)更详细地说:对于每个受保护的公理φ<$∈ Φ <$:φ1=x1×1, . . ,xm*m,xm+1pm+1, . . ,xz<$pz,a<$b,在所有局部保护都明确列出且*i∈*(和a,b序列的n-原子)的情况下,相应的公理δ(φ∈)∈ΦJ∈,其中:δ(φ)=x1δ(*1), . . . ,xmδ(*m),xm+1pm+1, . . . ,xzpz,aB. 需要v.b形式的公理来确保参数指定至少仍然适用于源自参数代数的元素。(We当δ(*)=*时,不包括公理μ(*)<$δ(*),以符合定义2.7(和2.6)的格式,但由于P[X]中的全局保护,它将得到满足。µ:*→SJ下的图像可以是双重的:拉莫和瓦立基204→≺≺|1) µ(*s)=*s,对应于持久性的经典情况,即,到不延伸载体S。2) µ(*s)*s引入了sorts的元素之间的区别,从参数µ(*s)和可能的新参数*s扩展载体s。映射δ允许PDT中的更大灵活性。 如果s类的载体不被扩展,上面的情况1),δ没有效应3但是如果s的载波被扩展,上面的情况2),δ允许2a)当δ(*s)=µ(*s)时,限制形式参数的局部保护– in this case the axioms from the parameter specification are required tohold2b)或者扩展局部保护2a)通常适用于数据类型的载体被扩展为特殊类型的元素(如“错误”值)的情况2b)适用于添加的元素“基本上”是相同种类的情况(例如,由幺半群参数化的群可能需要添加新的、但命题2.10如果(μ,X<$,P[X]<$,δ)是PDT,则:(i) μ:X→P[X]可能不是特定态射,但(ii) [1][2][3][4][5][6][7][8][9](iii) [1][2][3][4][5][6][7][8][9]2.2PDT的语义PDT的语义是使用多重代数的一般(弱)同态的特殊情况定义的。定义2.11紧同态h:A B是一个函数,使得对于所有运算ω:h(ωA(x1,. xn))= ωB(h(x1),.,h(xn))。对于常数,这意味着h(cA)=cB,这也是紧子代数的以下逻辑特征的基础。命题2.12如果h:A→B是紧的保序单态,φ是任意的保序公式,则A| =φB| = φ。3一般来说,δ(*s)可以等于另一个子排序常数p。但是v.b迫使P[X]=*sp,它与全局保护x *s一起表示两个常数*s和p表示相同的集合,即,整个航母的排序。拉莫和瓦立基205S|有必要把这个命题限制在被保护的公式上,因为对B中不属于h [ A ]的象的“新”元素的赋值现在,给定一个PDT(μ,X<$,P[X]<$,δ)和一个函子F:Mod(X<$)→Mod(P[X]<$),我们得到两个函子:• id−:Mod(X−)→Mod(X−)在2.1节之前的(2)中定义,• 组合物F; |µ:Mod(X)→Mod(X−)。定义2.13 PDT 的语义P =(μ,X,P [X],δ)是所有函子F:Mod(X)→Mod(P [X])的类,使得存在自然变换I:id−F; |μ,其中对于每个A∈Mod(X<$),分量ιA是紧<$(X<$)-单态。这样的函子称为PDTP的语义函子。以下事实是定义的另一种表述。两点十三分命题2.14函子F:Mod(X)→Mod(P[X])是PDT(μ,X,P[X],δ)i的语义函子:(i) 存在一个函子ι:Mod(X<$)→Mod(X−)使得<$A∈Mod(X<$)存在一个紧单态映射ιA:A→ι(A)(ii) 对于每个A∈Mod(X):ι(A)=(F(A))|µ,即, 下图通勤:4Mod(X)FMod(P[X]),z、、ι Mod--|µ,(X−)(iii) 对任意的同态h:A→B,F满足F; |µ(h)= h。在具有弱(和紧)同态的多重代数范畴中,ιA是单同态,是单射的。紧密性确保了ιA(*A)=μ(*)F(A)|µ,即,则载波为A=*A被注入嵌入到sF(A)asthesubsetμ(*s)F(A).总之,这个要求意味着A是F(A)μ的(紧)子代数,并且它的载体在F(A)中双射对应于μ(*s)F(A)-从而确保参数代数的保护。这是F必须是持久函子的要求的推广。经典的持久性是作为当μ(*s)=*s时的特殊情况得到的,对所有s。2.3实际参数传递给定一个PDT(μ,X,P[X],δ)和一个传递v和目标Y的实际参数,我们想使用经典的推出方法来定义实例化的语义。为了确保推出的存在性,我们必须确保所涉及的态射μ和ν是特定态射。第2.10号提案将对前者作出规定。至于后者,我们必须考虑到[4]虽然这里的ι与定义2.13中的ι不同,但它的作用本质上是相同的,因此将两者混淆并没有真正的危险。拉莫和瓦立基206一种更一般的情况,即,实际参数Y包含不在ν的像中的种类的可能性。对于这样的排序,我们应该在pushout对象中保留全局守卫。这促使了下面的Def. 两千五定义2.15(i) 给定签名<$=(S,,S)和<$j=(SJ,<$J,S<$j),保护规范SP =(<$,Φ,Γ),SPj=(<$j,Φj, Γ<$J)和签名同态ν:<$→<$j,SPj沿 ν 的 弱 化 是 规 范 SPJν ( − ) = ( <$j , Φj , Γ<$J\ {x<$ν ( *s ) :s∈S})。(ii) 给定保护规范X−,Y−,一个实际的参数传递app是一个规范态射:ν:X−→Yν(−)满足ν(*s)=*ν(s),对所有s∈φ(X−),其中φ(X−)是规范X−的签名。额外要求ν(*s)=*ν(s)背后的直觉很简单,因为*s表示形式参数X中所有排序为s的元素,所以它在ν下的图像在实际参数Y中也应该如此。引理2.16给定(保护)规范X<$和Y<$,如果ν:X−→Yν(−)是一个应用程序,则ν:X→ Y是一个特定态射。定义2.17给定一个PDT(μ,X,P[X],δ)和一个appν:X−→Yν(−)(其中X,Y被保护),实例化的结果是ν和μ的推出P[Y](在MA的规范Th的范畴中):XµP[X]δ٨vvJJµJν(−)JP[Y]由于推出的定义仅限于同构,因此结果不一定是PDT。在不深入细节的情况下(可以在[4]中找到),我们在这里只声明,有可能对pushout对象进行规范选择,这需要以下两个事实。引理2.18给定一个PDT(μ,X,P [X],δ),一个app ν:X−→Yν(−),如在Def. 2.17和正则推出对象:则νJ:P [X] −→P[Y]ν(−)是一个实pa rame terpassing。还选择诱导的δJ与μJ相同,我们得到:命题2.19对于一个具有app ν:X − → Y ν(−)的PDT(μ,X <$,P[X]<$,δ),我们可以根据定义2.17选择规范推出对象P [Y]<$,使得(μJ,Y<$,P [Y]<$,μJ)是一个PDT。2.4实例化语义这在Prop. 2.19中表达了一个方面-然而,还有另一个方面,我们称之为给定一个语义函子F:Mod(X)→Mod(P[X])和一个appν:−Y拉莫和瓦立基207→→、、J马X−Yν(−),我们想导出一个函子FJ:Mod(Y <$)Mod(P [Y]<$)。这个函子应该满足PDT的语义条件(Prop。2.14)。定义2.20给定一个PDT(μ,X,P[X],δ),语义函子F:Mod(X)→Mod(P[X])及其对应的i,以及一个appν−:X−→Yν(−)。一个函子<$J:Mod(Y)→Mod(Yν ( − ))由<$i导出,对于所有 的Y∈Mod(Y):(i) 存在紧单态iJY :Y→IJ(Y),以及(ii) i(Y |v)= IJ(Y)|v(和i(h|v)= iJ(h)|ν对于Mod(Y)中的同态第二点使用了v的重载概念,这是引理2.16所允许的。它意味着最左边的正方形2的交换性Mod(X),|,,,,¸,,,,,,,,ν、、I,F,1 .一、、、、Mod二、 国防部,,|µz_(Y),(X−)Mod(P[X])...... . . ¸IJ,,,,,F,,J,3.. . . . .J,|ν,z. .. .|νJMod(Yν(−)),,|µJMod(P[Y])通过半精确的广场3。 是回撤,因为相应的规范是根据定义2.17构造的推出。并合用来定义函子FJ,给定诱导的iJ。然后下面的命题完成了确保导出语义函子Fj存在的图。命题2.21给定一个i:Mod(X−)→Mod(X−)与一个PDT的一个自洽函子和一个app ν:X−→Yν(−),存在一个函子iJ:由i诱导的Mod(Yν)→Mod(Yν(−))。3修饰和合成PDT是对特定程序施加特定结构的设计规范因此,它们的改进并不意味着仅仅限制模型类,而是引入了附加的结构。定义3.1 PDTPJ =(μJ,XJ,P[X]J,δJ)定义P=(μ,X,P[X],δ),PPJ,如果存在函子RX:Mod(X)→Mod(Xj)和RP[X]:Mod(P[X]J)→Mod(P[X]j),使得对于PJ的任何语义函子FJ,、、拉莫和瓦立基208|µ莫oo oo、、. ..|→→函子RX;FJ;RP[X]是P的语义函子。Mod(X)RXoooooO,osoJ,,RX;FJ;RP[X]z_Mod(Xj), Mod(X−)d(P[X]π),,J. . .. ¸,F,J,,z_. .. . . RP[X]Mod(XJ),,Mod(P[X]J)-|µJ٨在精化定义中,参数侧RX的逆变性给出了精化PJ比精化的PDTP具有更少的语义函子,即PDT的精化函子这意味着,我们的修饰概念很好地符合将修饰视为子类关系的传统观点。然而,请注意PDT的改进和可编程技术规范的改进之间的差异。假设X为X,即,M od(X)<$M od(XJ).如果这个定义是严格的,即,M od(X)Mod(XJ),一个具有源Mod(XJ)的语义函子F j一般不能用在假定一个具有源Mod(X)的函子的地方。我们现在将回顾PDT的垂直和水平组成的概念,这将实际提供细化的示例 改进将在于沿着ρ把一个构造分成几个步骤ρ1;. ;ρn=ρ不会产生与沿ρ直接构造相同的结果,但其在上述意义上的完善。我们展示了组合性定理,并讨论了它们与经典概念的关系。第3.1和3.2小节讨论了纵向组成,第3.3小节讨论了横向组成。回想一下,给定一个参数传递图(如1.(见下图1),(μJ,Y−,P[Y]−,μJ)可以由Prop. 2.19选择为PDT,因此μJ:Y−→P[Y]−是Prop.2.19的一个特殊态射。两点十分3.1垂直构图GiventwoappYν(−)和ρ:Y−Zρ(−),(如图1所示。和2.在图1中),我们希望垂直地组合它们,即,我们想证明al so(ν;ρ):X−→Z(ν;ρ)(−)是一个应用程序。Zρ(−)和Z(ν;ρ)(−)的定义不必相同可能比前者有更多的全球警卫一般来说,我们只有Z(ν;ρ)(−)=Zρ(−)。在可能的差异中,以下提议至少确保应用程序的组成仍 然 是 应用 程 序 。3.我的朋友2Ifν:X−→Yν(−)andρ:Y−→Zρ(−)a reapp's,thensois(ν;ρ):X−→Z(ν;ρ)(−)(Fig. ①的人。现在,一般来说,所得的P[Z]和P[Z]J也可以是不同的。 在经典的情况下,这是因为推出的定义仅限于同构。但是,我们也可以在ι拉莫和瓦立基209--→Ss−XµP[X]v1.νJJµJJYν(−)P[Y]ν;ρY−µJP[Y](v;ρ)Jρ2。ρJJµJJJZρ(−)P[Z]键简体中文Z(ν;ρ)(−)P[Z]<$图1.一、我也是。在Zρ(-)和Z(ν;ρ)(-)的例子中,唯一的区别可能涉及全局保护的存在/不存在(因为所有其他公理都涉及到推出构造),所以这些是我们在下面的例子。例3.3考虑两个实例ν:X−→Yν(−)和ρ:Y−Zρ(−)。 (Twoline s inYν(−),Y−,etc. 表示由第二个实例化ρ标识的两个不同的排序。)X*µp*联系我们P[X]键νJJµJJJνJJJYν(−)*p*x*P[Y]y*1*1µJ*1y*1Y−*1,,µJ*1y*1P[Y]、、、sssρ,*、、、J,,µJ ps*Ssx*ρJJJZρ(−)zJzµJJ*JJS*J*Jy*Jxj*P[Z]键现在沿着(ν;ρ)直接实例化:X−(v;ρ)*µp*联系我们P[X]键(v;ρ)JJJµJJJJJJJZ(ν;ρ)(−)*J*J*x*P[Z]j重要的区别在于P [Z]具有µJJ(*)的全局保护,即yy*J源自P[Y]。Tushere*={*,*J}和C={*,*j}。 在P[Z]j中,另一方面,这保证d不存在,因此e*J={*},而C*J={*J}。所以(μJJ,Z,P [Z],whoever)禁止扩展载体 *J,而(μJJJ,Z,P [Z] J,whoever)不禁止。因此,P[Z]和P[Z]j不需要同构。我们只有:٨S拉莫和瓦立基210⊇|⊆命题3.4用图1和Ex. 3.3:(i) P [Z]键|= P [Z] j(ii) 如果P [Z] J≠| = P [Z],那么它只是因为对于一些(子)排序常数(s)p:P [Z]|= p(x)和P [Z] J|= p(x)。逐步实例化(沿着ν,然后沿着ρ,导致P[Z]n)产生的结果与直接实例化(沿着(ν;ρ)导致P[Z]Jn)产生的结果不同,这一事实看起来像是我们设置的一个严重弱点。毕竟,这两者的平等表明了任何熟悉传统的,基于推出的理论的人所期望的理想的组合性。参数化规格。然而,我们不是在开发参数化规范的理论,而是在开发参数化数据类型的规范。因此,我们有兴趣从其他数据类型中构造新的数据类型。执行不同的结构,或在垂直合成的情况下,以不同的方式执行结构,可能会产生不同的结果。逐步实例化,首先沿着ν,然后沿着ρ,表示与沿着η=ν;ρ的直接实例化稍微不同的构造。事实上,根据定义3.1,前者是后者的一种细化。后者是一 沿η的一步构造。从这个意义上说,将这个结构分为两步,首先沿着ν,然后沿着ρ,是一个更详细的、精炼的结构,它可能会引入新的方面。我们当然希望这种精化构造的结果与一步构造所规定的结果“相容”。这在Prop. 3.4.1中有所说明,现在我们来说明这种修饰的语义方面。3.2垂直组合如前所述,实例化的语义可以从两个角度来看:一方面,作为一个新的PDT与其语义函子类,另一方面,作为一个实现:一个由实例化PDT的特定函子。我们现在将这种区别应用于垂直组合的语义。3.2.1垂直组合作为PDT的细化。一个微不足道的,但绝不是唯一的例子,从国防部的PDT细化3.1是当P[X]J≤P[X]j时,即,Mod(P[X]J)Mod(P[X]j),而其他分量相等。实际上,垂直合成就是这种情况。 如果我们将P[Z]i和P[Z]J视为两个独立的PDT(即,“忘记”它们都源自同一PDT的实例化),我们看到,通过Prop. 3.4,P [ Z ] n = P [ Z ] j n,即,,其中包括:Mod(P[Z]∞)Mod(P[Z]n,J)。我们对于P=(μJJ,Z,P[Z],δJJ),任何语义函子F给出一个语义函子,PJ=(μJJJ,Z,P[Z]J,δJJJ),简单地通过组合F;i。两种PDT的其他成分基本相同,因此我们得到拉莫和瓦立基211命题3.5对于P=(μJJ,Z<$,P[Z]<$,μJJ)和PJ=(μJJJ,Z<$,P[Z]J<$,μJJJ)(as在Ex. 3.3),PjP.此细化的准确性由Ex. 3.3:虽然PJ可以允许一些载波的扩展(对应于示例中的*J),但是P可以通过引入额外的全局保护来禁止它。3.2.2垂直构图的经典概念经典的概念是不同的,但是,尽管如此,从上面得出。参考图1,认为PY=(μJ,Y,P[Y],δJ)是PX=(μ,X,P[X],δ)的实现,并且PZ=(μJJ,Z,P[Z],δJJ)也是PY的实现。这说明PZ也是一个简单的PX的心理状态。然而,实施的概念与我们对过程驱动理论的细化概念并不一致,因为它允许对来源和目标类别进行限制。这将是图1的语义对应物的一个特例,此时ν和ρ诱导各自的归约函子,它们是包含。然后,我们得到结果PDTPZ的任何语义函子都有一个源和目标,分别包含在PX的语义函子的源和目标中。3.2.3纵向构图作为一种实现然而,在逐步例示和直接例示之间有一种更具体的关系。 根据Prop.2.21,任何语义函子FX(μ,X,P[X],δ)对于形式参数X通过实际参数Y的任何实例化,导出语义函子FY。如果我们现在考虑各自实现的结果,即,函子FZ(通过Y首先沿着ν然后沿着ρ逐步实现而获得)和FJZ(通过直接(1)两人都是从同一个给定FX,则证明语义是完全组合的,即, 两个函子是相等的。 图1的语义对应物在图2中示出。(M(X)取代Mod(X)。)拉莫和瓦立基212、、,J−,,Z、| JJJµSM|ssss¸,,,,,,FνsssssIXX、、、MsJ,,|µz(Y)|νM(X−)M(P[X]<$)(v;ρ)、、|sss¸,|sss¸¸,,=1Y1,,s,s,sνJsssJssss ss ,FYssss男(女)zsM(Yν(−)),,M(P[Y]),J|µJ|ρIY,,=,,FYJ,s|µJ,zM(Z)ρM(Y−),,M(P[Y]<$)、、|好,好,好,=iZ、、、sssJ ,FZss ss|ρJM(Z)M(Zzs),,M|(ν;ρ)J你好,、、、ρ()你好,|µJJ(P[Z])JIZ1 J,,,FJiz,sM(Z(v;ρ)(−)),M(P[Z]j)图二、给定一个语义函子FX(在图的最上面的图2),Prop.2.21给出函子FY,同样,给定任何FJY,可以构造FZ。因此,利用沿ν对FjY的实化得到的FY,我们可以从给定的FX构造FZ。注意,关联的ιZ保证了M od(Zρ)的像包含dinM od(Zρ(−))。类似地,对于直接实现,我们可以从给定的 FX得到FjZ。根据命题3.4,我们也有包含(函子)i:Mod(P[Z]<$)<$Mod(P[Z]J<$)。因此,合成我们得到FZ;i:Mod(Z)→Mod(P[Z]J),它给出了一个可能的语义函子FJZ,其中PJ=(μJJJ,Z,P[Z]j,μJJJ)。实现的组合性表现为:命题3.6用图2中的符号,所有函子都由FX(特别地,FY= FJY且iY= iY1),我们有:FZ; i = FJZ。3.3横向构图定义3.7PDTP =(μ,X,P[X],δ)和PJ=(μJ,P[X],W[P[X]],δJ)的水平组成为((μ;μJ),X,W[P[X]],(δ;δJ))。我们用P;PJ表示它。 这样的组合物产生新的PDT。命题3.8水平组合(同构于)PDT(W[P[X]]J<$)W[P[X]]<$,使得((μ;μJ),X<$,W[P[X]]<$J,(δ;δJ))是PDT。定义2.9的前四点是平凡满足的,而第v点的验证主要是基于形式为v.b的公理的存在在语义方面,下面的命题指出,给定(水平组合的)成分PDT的语义函子,它们的组合拉莫和瓦立基213为组合的PDT生成语义函子。命题3.9给定定义3.7中的P,PJ和语义函子FX:Mod(X)→Mod(P[X])和FP[X]:Mod(P [X])→Mod(W [P [X]])-则F X ; F P [ X ]:X → W [ P [ X ]]是P ; P J的语义函子。3.3.1横向组合作为PDT的细化。同样,横向构图提供了更多的结构。根据Prop.3.8,水平组合两个PDT,我们得到一个新的PDT与相关的语义函子类。 然而,通过逐步水平合成PDTP和PJ获得的PDT的语义是对相应组成的PDTP;PJ的语义。前者,拥有更多以中间阶段P[X]的形式的结构,可以放置额外的对可容许函子的限制。下面的例子说明了这一事实例3.10下面的PDTP=(μ,X<$,P[X]<$,δ)需要用一个新的函数f来扩展参数代数A,并允许用新元素(其中一个可以是d)来扩展AP[X]=SJ:ElJ:d:→Elf:E1→E1ΦJ:1。 f(d)=stecdSJ:*,ok:ElJ:3。联系我们X=٨S:Elµ(*)=ok中文(简体)δ(*)=*r:x*令语义函子发送A∈Mod(X)到F(A),由下式给出:• |为|一|{ d } - d是一个新的元素,| {d}–disane w elementaddedtothecarrierofA,• fF(A)(x)= d,对所有x ∈ |F(A)|、• o kF(A)=|一|根据语义功能要求,• *F(A)= |F(A)|,默认情况下。让我们引入一个中间参数,即,我们现在有两个PDTPJ =(μJ,X,W[X],δJ)和PJJ=(μJJ,W[X],P[W[X]],δJJ),其中P[W[X]]=拉莫和瓦立基214∈联系我们、、、ModRP[X]键:µJ(*)=*XδJ(*)=*µJJ(*)=okδJJ(*)=* P[X]显然,我们有P=PJ;PJJ.但是,从最后一个图的逐步复合是P为后两个构造任意两个函子对于任意语义函子FJ:Mod(X<$)→Mod(W [X]<$)不能扩充任意A ∈ Mod(X <$)的载体,而只是增加了一个函数f. 进一步地,任何语义函子FJJ:Mod(W [X ]<$)→Mod(P [W [X]]<$)可以在参数代数B的载体上添加新元素dMod(W[X])和力f(d)= d.然而,FJJ必须 对于x okFJJ(B),我们必须有fFJJ(B)(x)okFJJ(B)。如果dokFJJ(B)(与F的情况一样),它将永远不会从ok F jj(B)“由f可达“。因此,我们不能得到原始F作为任何FJ和FJJ的合成。3.3.2水平构图这 个 经 典 的 概 念 是 : 如 果 X1<$X2 和 P1[X1]<$P2[X1] , 那 么P1[X1]<$P2[X2],其中所有的n表示模型类包含(在相反的方向上)。这意味着P2[X2]的函子可能有一个源Mod(X2)→Mod(X1),这使得它过于特殊,无法用于获得具有参数X1的原始PDT的语义函子。 然而,这种“实现与参数化交换”的事实虽然这个属性并不反映我们的细化概念,但它仍然在我们的环境中获得。如果P1[X1]小于P2[X1],则如3.2.1节所述,我们得到相应PDT的细化。此外,如果我们有X1<$$>X2 <$$>,则(μ21,X2<$,P2[X2]<$,δ21)的任何语义函子都是(μ1,X1<$,P1[X1]<$,δ1)的语义的限制,也就是说,在经典意义上的实现,因为语义的源和目标类别前者的函子分别是后者的语义函子的源类别Mod(P1[X1])Mod(X1mm),,F1,_、,,|ν1F21、Mod(P2[X1]m),,|νFJ、(P1[X2])|ν2,1,_,r,FJ21,rMod(X2)Mod(P2[X2]),W[X]=SJJ:ElJJ:f:El→El S- JJ:3.联系我们拉莫和瓦立基215该图说明了这种情况,其中,给定app ν:X 1→X 2,使得|ν:Mod(X2<$)→Mod(X 1<$)是一个包含,|通过拉回得到的ν 2也是一个包含。4结论我们已经总结了最初在[5]中提出的指定PDT的框架。该框架的语法提供了一种方法,用于指示扩展参数代数的载体的可能性,以及限制参数指定的公理(仅适用于“旧”元素)。PDT的语义由一类函子定义,这些函子满足经典持久性要求的一般化将PDT视为设计规范,不仅对实现的抽象(输入-输出)属性提出要求,而且对其实际结构提出要求,我们引入了PDT的细化概念,这与引入更多结构相对应。通过这种方式,我们的PDT给出了来自[9]的“构造函数规范”的更一般概念的具体实现。PDT的细化可以很自然地被看作是基于构造器规范的程序开发的一个例子,其中连续的阶段相当于根据预期实现的期望结构将原始的松散规范分割成更小的部分这种细化概念已经通过垂直和水平合成的例子得到了说明。结果已提出使用机构的多重代数。然而,尽管不是完全独立于机构,但它们可以很容易地为许多共同机构重复,只要它们满足一些要求:它们是半精确的(承认合并引理);签名包含在模型类中被解释为一元谓词的符号只在这样的符号上发送这样的谓词符号;模型类是单态是单射的具体范畴虽然这个列表看起来很有限制性,但最常用的instrumu-这些要求都满足了。结果,特别是Prop。2.21,不仅适用于MA,而且适用于全代数(带谓词),部分代数(带谓词),成员代数的机构。有一点需要进一步研究,那就是关于过程驱动疗法的推理。我们期望增加表示参数代数的闭包的通用公理模式(即,应用于“旧”元素的操作另一方面,我们希望使用过程动力学来进行研究,也许还可以在实现层面上设计更具体的结构化机制。我们还认为,目前的工作可以为设计更详细的结构提供有用的基础,例如,拉莫和瓦立基216像CASL这样的引用[1] 哈特穆特·埃里希和贝恩德·马尔。代数规范基础1。Springer,1985年。[2] 哈拉尔德·甘辛格 参数规范、参数传递和优化实现。技术报告TUM-18110,慕尼黑工业大学,1981年。[3] 英格芙·拉莫和迈克尔·瓦里克多重代数的介绍。技术报告209,信息学系,卑尔根大学,2000年。[4] 英格芙·拉莫和迈克尔·瓦里克参数化数据类型的规范。技术报告210,信息学系,卑尔根大学,2000年。[5] 英格芙·拉莫和迈克尔·瓦里克参数化数据类型的规范:Persistence revisited。Nordic Journal of Computing,8:278[6] 斧头没了。没有一个日志文件是使用具有备份或备份的算法块进行的。在MFPC的会议记录中,LNCS的第176卷。Springer,1984年。[7] 斧头没了。错误和遗漏是为了防止数据类型化。在第三届WADT的出版物中,LNCS第116卷。Springer,1984年。[8] Donald Sanella,Stefan Sokol-owski,and Andrzej Tarlecki.从代数规范走向程序的形式化开发:参数化再访。Acta Informatica,29:689[9] 唐纳德·萨内拉和安杰伊·塔勒基。 从代数规范走向程序的形式化开发:实现再访。Acta Informatica,25:233[10] J.W. Thatcher,E.G. Wagner,and J.B.赖特数据类型规范:参数化和规范技术的力量在POPL的诉讼中。ACM,1979年。
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功