线性语义和表达能力：异步COM编程语言的定量比较

《理论计算机科学电子札记》59卷第3期（2002年）网址：http://www.elsevier.nl/locate/entcs/volume59.html31页语言表达性Antonio Brogi，Alessandra Di Pierro意大利比萨大学计算机科学系赫伯特·维克利茨基英国伦敦帝国理工学院计算机系摘要我们引入了线性嵌入的概念，这是Shapiro的嵌入概念，通过在基于线性空间的语义设置中对其进行重铸。我们使用这个概念来比较一类采用异步COM的语言的表达能力琳达式的交流方式。 采用线性语义，语言的可观测量是表示程序的线性算子（矩阵），转移图使我们能够对语言的不同表达能力给出定量的1介绍计算机科学的发展伴随着大量不同编程语言的产生。引用[9]：所有合理的编程语言都是等价的，因为它们都是图灵完备的.然而，如果它们之间的差异不是物质上的，我们就不会发明这么多。另一方面，在编程实践中，某些语言被认为比其他语言更“强大”，因为它们能够表达控制和数据结构。当考虑并发语言时，比较语言的表达能力变得更加复杂。非决定论和不成功的计算在这里起着至关重要的作用，而且没有对应的图灵完备性概念来衡量一种语言的绝对表达能力。形式上比较语言的表达能力的问题一直是相当大的研究对象（见[2]的介绍）。 比较两种语言表达能力的一种自然方法是验证在CC BY-NC-ND许可下开放访问。Brogi，Di Pierro，Wiklicky2LO2观察结果1 -1 16CD？L观察结果2-氧气Fig. 1. 嵌入是否所有用一种语言编写的程序都可以“容易地”和“等价地”翻译成另一种语言。这个想法是形式化的概念嵌入介绍[9]：设L1，L2是两种语言.假设给定观察标准Obs1：L1 7！O1和Obs2：L27！其中O1和O2是一些合适的域。然后L2嵌入L1，如果存在从L1到L2的映射C（编译器）和从O2到O1的映射D（解码器），换句话说，对于每个程序P2L1：观察结果1（P）= D（观察结果2（C（P）：嵌入的概念和模嵌入的概念[2]通过建立定性的分离结果（L1）来比较不同语言的相对表达能力L2和L2 6 L1）以及等效性结果（L1 L2和L2L1）。我们的目的是在语言表达性的比较中引入定量方面。我们将提出一种方法来分配定量的估计分离结果，以估计“多少”一种语言比另一种更有表现力。我们的方法可概括如下：我们引入了线性嵌入的概念作为定量比较语言表达能力的基础。我们从Shapiro [9]引入的嵌入的标准概念开始，并通过将线性空间作为语义域来将其重新塑造在线性环境中。此外，我们还要求C和D的“组合性”在程序结构上，D是线性映射。观察标准是根据线性语义来定义的，该线性语义将每个程序与适当定义的线性代数中的线性算子相关联。线性嵌入的概念诱导偏序的语言，并允许我们建立分离（L1L2）和等价（L1 = L2）的结果之间的语言。然后，我们用一个代表表达能力差异的量来注释每个分离结果。这个数量取决于与这两种语言相关的代数的维数。Brogi，Di Pierro，Wiklicky3直觉上，代数的维数给出了用该语言可表达的不同可能行为我们将线性嵌入和定量比较的概念应用于一族Linda类语言，并将结果与[1]中建立的结果进行比较。在下一节中，我们将介绍一个简单的类Linda语言族，我们将用它来描述线性语义，线性嵌入的概念和基于后者的定量比较。 然后在第3节中介绍线性嵌入的一般定义，而在第4节中讨论定量估计。2类琳达语言2.1关于L（X）的在[1]之后，我们考虑一族语言L（X），它们对于所使用的通信原语的集合X彼此不同这些原语对应于用于将令牌添加到共享数据空间、从数据空间获取令牌以及检查令牌在数据空间中的存在或不存在的基本Linda原语语言L（X）还包括标准的pre x和choice运算符。L（X）的语法形式上由以下文法定义：P：：= stopj C：Pj P+ PC：：= ask（t）jnask（t）jtell（t）jget（t）其中t是可枚举集合T中称为token的类属元素，P是进程，C是通信动作（或pre x）。定义我们的Linda类语言的参数X是C定义的原语的子集因此，L（X）中的程序要么是一个不活动的平凡程序停止，要么是一个顺序组合C：P或一个选择P + P。像往常一样，我们省略了一个尾随止损，如果它前面有一个非空的基本动作序列C。还要注意的是，对于当前的处理，我们不考虑并行构造。2.2L（X）的线性语义L（X）中的计算由一组进程组成，这些进程共享一个表示为多组令牌的公共存储，并在其上执行通信操作。我们将这样的计算建模为状态（初始存储）到另一状态（最终存储）的转换。我们将状态表示为自由向量空间V（S）中所有可能存储的集合S上的向量（即多组令牌）。S上的自由向量空间V（S）被定义为S的元素的所有形式线性组合的集合：V（S）=（Xxs~sxs2IR）：s2SBrogi，Di Pierro，Wiklicky4不S我S例2.1考虑一个语言L2（X）.L2（X）的存储集S可以i=0时其思想是将程序P在状态x下执行的结果编码，状态x由V（S）上的线性算子的向量x表示。 也就是说，如果M（P）表示程序P，并且~x表示其执行的状态，则结果状态由y~xM=~y表示，即， y乘以矩阵M得到的向量。如果S是基数为n的nite集，则这些线性算子是nite维的，或者更精确地说，它们是n n矩阵。对于可数的悬挂物集合，我们不得不转而考虑有限维线性算子。虽然我们假设我们的语言L（X）一般是在一个可数的存储集上定义的，但在我们的推理和整篇论文中所示的例子中，我们总是引用nite集。特别地，我们将用Ls（X）表示语言L（X）在t个标记和至多s个存储上定义的nite近似。 可以用t个令牌构造的大小为s的所有可能存储的数量由以下基本组合公式给出（例如[6，Sect. 1.4]）：n（s; t）=Xi + t1为 s +t：对于0和最大存储大小s之间的每一个数字i，我们计算包含t种不同类型的标记的可能的多集（即重复组合）的数量，并将它们相加。3 3列举如下：fjjg;fjt1jg;fjt2jg;fjt3jg;fjt1;t1jg;fjt1;t2jg;fjt1;t3jg;fjt2;t2jg;fjt2;t3jg;fjt3;t3jg：自由向量空间V（S）是10维的，因此同构于IR10。在这个向量空间中，ff jjg;fjt2jg;fjt1;t2jg;fjt1;t3jgg用向量（1; 0; 1; 0; 0; 1; 1; 0; 0; 0）：为了正确地模拟程序的行为，nite近似n商店，我们必须引入一个额外的过流状态！这允许我们处理这样的情况，即向存储添加另一个令牌使其大小大于n。这样的状态具有这样的性质，即一旦达到该状态，就不可能有离开该状态的进一步的转换与基本通信动作相关联的线性算子定义如下（我们用M ij表示线性算子M的第i行和第j列的元素）。我们用[[P]]或M（P）表示表示程序P的运算符。 所有商店的16=！运算符中的条目表示Brogi，Di Pierro，Wiklicky5<8n1，如果s2=s1[ f] t] g且ks2k n基本动作或命令被定义为：（[[ask（t）]]）s1;s2=0 否则1 如果t2s1且s2=s10 否则（[[get（t）]]）s1;s2（[[nask（t）]]）s1;s2=8：=8：1 如果t2s1和s2= s1nfjtjg0 否则1 如果t62为s1且s2=s10 否则其中，[1]和[n]分别表示多个集合，[n]和[n]。 F或s1=！、所有四个基本命令tell（t）、ask（t）、get（t）和nask（t）的条目都以相同的方式定义：（[[C（t）]]）第1条;第2 =1 if s 2 =！0否则。用乘法和加法来模拟预测和非确定性选择在线性算子的代数上：[[C：P]]=[[C]][[P]]和[[P + Q]]=[[P]]+[[Q]]：最后，stop由C（S）上的恒等运算符表示，即（[[stop]]）s1;s2=1 如果s1 = s20 否则，请执行以下操作。语言L（X）的这种线性语义可以看作是一个向量L（X）的标准操作语义的空间编码，如[1]中的示例所示。线性算子M = M（P）在e ∈ C上对转移关系hP js 0 i！如果hP j s0 i可以转换为多个hQi j s ii，对于i=1; ：;k，则可以表明M~s0=i=0~si.换句话说，M（P）中的每一行都对P的可观测量进行编码，在对应于该行的存储中执行。 如果程序P在某个存储器中死锁，则对应的行是“空”，即仅包含零。在这个意义上，我们可以区分成功终止hP js 0 i|如果M（P）中的行s0包含非零项|失败或死锁|如果M（P）中的行s 0只包含零。在下文中，我们将称两个程序P和Q等价，如果它们具有相同的语义，即如果[[P ]]=[[Q]]。0>BA（tel1（t））=>=>：@：a+b+b+cA并且基本动作tell（t）由下式表示：：1：：* 1：M =[[tell（t）]]=* 1B：1C我们可以使用M生成两个额外的线性无关算子，即和* 1：2：1M = M M = [[tell（t）：tell（t）]]=* 1@B：1CA0：11M = M M M = [[告诉（t）：告诉（t）：告诉（t）]]=* 1B@：1CA对于所有i > 3，我们有Mi=Mi1。因此，代数A（tell（t））的维数是4。更确切地说，tell（t）生成的代数具有以下形式：a b c d：a b c + d* a b + c + d>B19Ca; b; c; d2 IR ：C>为了确定类琳达语言的维度，考虑以下因素将是足够的：|如上例所示|只有由基本动作产生的单词（cf.提案4.6）。很明显，L（tell）、L（ask; tell）等中的每一个程序都是在ask、nask、get和tell的顺序组合中进行选择。使用表示程序语义的矩阵代数中的分布性，我们假设只有“顶级”选择，例如：[[P1：（P2 + P3）]]=[[P1]]（[[P2]]+[[P3]]）=[[P1]][[P2]]+[[P1]][[P3]]由于和，即线性组合，不有助于生成的代数的维数，我们可以限制自己，以确定有多少（纯）顺序程序在一个特定的语言L（X），具有线性无关的矩阵相关联的语义。这些顺序程序Brogi，Di Pierro，Wiklicky16L（nask，tell）L（tell）HHHHHjHL（问，说）？九岁？L（ask，nask，tell）L（get，tell）-L（问，得到，告诉）？L（ask，nask，get，tell）？L（nask，get，tell）图五. 语言的等级显然，每个都由基本动作生成的一个词来表示，即M中的生成元。4.2测量Linda类语言通过命题3.3，在[1]中建立的关于模嵌入的Linda-like语言的相同层次也适用于线性嵌入。图5总结了分离和等价结果的整个集合，其中从语言L1到语言L2的箭头表示L2嵌入L1，即L1 L2。请注意，由于嵌入的传递性，图中只包含极少量的箭头。然而，除了这些归纳的关系，没有其他关系成立。特别地，当有一个从L1到L2的箭头但没有从L2到L1的箭头时，则L1严格地比L2表达性低，即L1L2。我们现在应用4.2节中描述的技术，用描述两种语言表达能力差异的数量来注释这个层次，这两种语言在层次中是定性分离的。如4.2节所解释的，这些量是根据与语言相关的代数维数的增长率给出的，当存储器的数量n（s; t）增加时。我们将证明，这种表达性的定量概念在语言集L（X）上导出了一个等价关系，它比图5中表示的等价关系更粗糙：它识别出被模嵌入分离的语言。特别地，我们将证明语言集L（X）可以通过下面定义的等价关系划分为三类。这种关系表明，两种语言的规模有相同的增长率。通过使用[4，（9.8）]中的符号，可以对两个类属函数f（n）和g（n）定义如下：f（n）g（n）i jf（n）jk jg（n） j和 jg（n）jk jf（n） j;-Brogi，Di Pierro，Wiklicky17不01BCBCmn1m n2：m nnm n;n+1对于某个常数k和所有足够大的n。定义4.8设L1和L2是两个Linda类语言，（L1）n和（L2）n是它们在n1个存储上的近似。然后L1L2i dim（（L1）n）dim（（L2）n）：严格地说，我们考虑L（X）n= L（X）n（s;t）=L（X）s取决于两个参数，即存储大小s和不同元组的数量t。为了简化我们对语言比较的处理，我们将集中讨论“对角线增长”，即s = t的情况。这相当于假设当n趋于无穷大时，s和t以相同的速度趋于无穷大，即s=t的比值为1。命题4.9商集L（X）=由以下三类组成：[L（tell）]== fL（tell）g;[L（ask; tell）]== fL（ask; tell）; L（nask; tell）; L（ask; nask;tell）g;[L（get; tell）]== fL（get; tell）; L（ask; get; tell）; L（ nask; get; tell ） ; L （ ask; nask; get;tell）g：这个命题的证明将通过计算L（X）中每种语言的维数来给出。一般来说，很容易看出，所有（L（X））n的维数都有上限，由（n+1）2给出，即在（L（X））n中建模程序的所有n +1 n + 1-矩阵的代数的维数。这是一种特殊的性质！可以让我们收紧这个上限：命题4.10对于所有的语言（L（X））n，我们有：dim（L（X））nn（n + 1）+1：证据表示（L（X））n中的程序的矩阵的一般形式，其中n = n（s; t）为：男性11例 M12 *m1nm1;n+1男性21例 男性22例 *m2nm2;n+1M=：：：：：：：：：：：：：：B C@0 0：0 1A项mij的值取决于由M表示的程序然而最后一行，对应于过低状态！， 对于表示（L（X））n中的任何程序的所有矩阵都是相同的，并且表示一旦达到它就不可能过渡到任何其他状态的事实。2Brogi，Di Pierro，Wiklicky18不4.2.1语言L（tell）在本节中，我们计算语言的维数Ls（tell）近似-交配L（tell）。Brogi，Di Pierro，Wiklicky19不不不X不不不B0C1M =[[P：Q]]=：对于表示L s（tell）中两个程序的两个算子[[P]]和[[Q]]的乘积[[P ]][[Q]]，下面的观察通常是有帮助的。引理4.11设[[P]]=（P）ij和[[Q]]=（Q）ij是表示Ls（tell）中两个程序P和Q的两个算子，设S是存储集。然后，它们的乘积矩阵PQ中的项（PQ）lk由下式给出(PQ)LK=1 如果存在R2L（X）和sm2S：hP;s l i！hR; s mi ^hR; s mi！hP; s ki0否则，在哪里！ 是定义LS（tell）的小步长操作语义的转移关系。证据 线性算子的乘法定义为：（PQ）lk= PlmQm由于[[P]]=（P）ij和[[Q]]=（Q）ij具有0=1个条目，条目（PQ）lk是非零的，当且仅当存在至少一个被加数Plm Q = 0。这意味着必须有一个存储器sm2S，使得Plm6 =0且Qm 2=6 0，这就是转换hP; s l i！hR; sm i和hR; s m i！ 这是必须发生的。2在Ls（tell）中，我们把形式为P tell（t1）：tell（t2）：tell（ti）的程序称为长度为i的前缀x。对于每对值（s; t），语言Ls（tell）sat-设置以下属性命题4.12对于语言Ls（tell），我们有：(i) 所有长度为i> s的前缀P都是等价的。(ii) 长度为i的pre x P的所有排列，其中1我s等于P。证据(i) 考虑一个长度为s的pre x P。由于存储器的大小有限，任何数量的tell（t0），t02 T跟随P只能产生一个超低。因此，根据引理4.11，对于P：Q的所有矩阵，其中Q是长度为x的前一个1将采用以下形式：0 0：0 10 0：0 1B C0 0：0 1@B0 0：01AC(ii) 设Ptel l（t1）：tel l（t2）：tel l（ti），设f1; ：;i g的任意变换，Brogi，Di Pierro，Wiklicky20设Q tell（t（1））：tell（t（2））：tell（t（i））。