理论计算机科学电子笔记127（2005）49-54www.elsevier.com/locate/entcs语言口译员的演变1RalfLüammel2阿姆斯特丹自由大学信息学中心摘要我们对基于语言的功能的演化场景感兴趣。我们确定了这些功能可以发展的不同维度，包括：（i）编码风格;（ii）编码细节;（iii）数据模型;（iv）横切关注点;（v）补丁。我们将语言解释器作为基于语言的功能的例子，但是对于类型检查器，静态分析，程序转换和其他类型的基于语言的功能也存在类似的情况。我们的经验是基于使用基于规则的编程（与Prolog）实现基于语言的功能，而进化的功能转换被视为元程序。关键词：进化，进化转换，基于规则的编程，语言解释器，基于数据库的功能，元编程，Prolog介绍基于数据库的工具涉及语言的预期语义的一些（ad-hoc）元素采用的语义量取决于工具提供的特定服务。这里有一些例子。分析工具通常实现所谓的抽象解释，它根据抽象的含义域重新表述正常的语义。一个转换工具应该类似于预期的语义，因为它使用了代数法则以及类型和作用域规则。翻译工具实现了注：本扩展摘要从这些出版物中提取了材料：伴随的概念验证实现是基于Prolog的规则演化工具包[12]（REK）。2电子邮件：ralf. cwi.nl1571-0661 © 2005由Elsevier B. V.出版在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2004.08.03250R. Lämmel/Electronic Notes in Theoretical Computer Science 127（2005）49语法到语法映射，其理想地可以被补充到具有用于所涉及语言的两种语法和两种语义的节点的通信图中。类型检查器和语言解释器可以被看作是基于语言的工具的原型示例。这些工具相当直接地实现了语言这种面向语义的程序的可扩展性（以及底层的形式化语义描述）在编程语言社区中得到了充分的关注。存在高度先进的方法来重新使用语言描述或其组成部分，例如，monad风格的指称语义[8]、动作语义[9]、抽象状态机[2]、策略编程[7]、模块化SOS [10]和模块化属性语法[3]。这表明，语言描述的领域是适合于研究一般的基于语言的工具的演变。在我们的工作中，我们的目标是一个简单的，务实的，重新设计的方法，以进化的语言为基础的工具。我们使用元编程的意义上的自动化转换的操作化的进化sce- narios。我们将重点放在语言翻译上。我们假设语言解释器是用基于规则的语言编程的，比如Prolog。我们采用了一个适当设计的运营商套件的进化转换。这些运营商支持以下活动：• 为扩展或修订做准备的重组• 通过模块化组合或编织来添加新关注点的扩展。• 修改以删除或更改不适当的部件。进化的维度我们将为一个简单的面向表达式的语言的解释器完成一些进化场景让我们假设解释器由以下类型的Prolog谓词求值：-profile evaluate（+exp，+varenv，-val）。REK支持基于如上所示的profiles的有类型Prolog编程。分类表达式对应于表达式形式的句法域。sortvarenv对可变环境进行建模。sortval对评估结果的类型进行建模，到目前为止，评估结果都是数字。那就是：：-data exp= const（number）|var（varid）|......这是什么？.%表达形式：-alias varid = atom。% 变量标识符：-alias varenv=[（varid，val）] %变量环境：-alias val= number.评价结果百分比每个表达式形式都有一个Prolog子句。 我们忽略这些规则。R. Lämmel/Electronic Notes in Theoretical Computer Science 127（2005）4951风格转换意义上的进化我们为上面的谓词evaluate提供的类型意味着大步风格。当选择小步长样式时，一些语言扩展更容易适应，例如，异常处理或并发性属于这种类型。一个典型的进化步骤是将解释器从大步转换为小步，步式我们注意到，还有其他类型的转换与进化有关，例如，CPS转换。为了准备小步到大步的转换，我们需要启用与求值类型相关的小步。也就是说，我们必须返回sortexp的表达式，而不是返回sort val的值，这可能会进一步减少。为此，所有规则都需要进行调整，以便通过专用函数将值注入到表达式托尔。REK提供了一个转换操作符othertype，它可以完成这个任务.谓词求值的适配类型如下：：- profile evaluate（+exp，+varenv，-exp）。转换的内在部分是关于规则分解的。也就是说，我们需要分解大步长规则，从而获得许多小步长规则REK提供了一个专用的转换操作符big2small。数据模型的演变让我们假设我们想要适应面向对象的构造。用方法调用、字段访问、对象构造等的表达式形式来扩展语法域exp是很简单的然而，这些构造的解释不能仅仅通过向原始谓词求值添加规则来完成。一个问题是，需要使评价结果的类型适合于不同类型的结果。事实上，在我们的运行示例中，val作为类型别名的定义是一种方式。 我们需要把val转换为正确的数据类型，其中一个是数字，另一个是用于对象引用。REK提供了一个操作符othertype，它支持数据维的这种演化。 修改后的sortval如下所示：-data val = num（number） %结果与之前| oref(integer). 新类型结果%显然，othertype操作符不仅适应了排序值，还适应了实际的解释器规则。也就是说，所有预先存在的val类型的位置都必须用函子num包装数字。52R. Lämmel/Electronic Notes in Theoretical Computer Science 127（2005）49贯穿各领域的问题的演变面向对象语言扩展还需要一个增强的谓词来进行表达式求值。到目前为止，我们只传递了变量的环境。 我们需要为虚方法表添加参数（参见排序vmt下面），对于当前对象（cf.排序），以及对于对象存储（cf.排序商店）。原始规则必须进行调整，以便它们参与这些新语义组件的数据流。这样的数据流或计算，一个考虑到许多或所有现有的规则，最好被视为在面向方面编程的意义上的横切关注点的实现（面向方面编程、基于规则的编程和程序转换之间的这种联系在[4]中进行了探讨。为了比较，下面是谓词求值的原始类型：：-profile evaluate（+exp，+varenv，-val）。启用OO的谓词必须属于以下类型：：- profile evaluate（+exp，+varenv，+vmt，+this，+store，-val，-store）.REK为操作员提供了添加头寸和建立上述所需的适当数据流的功能运算符add增强了谓词的类型，它将新的变量添加到规则中的相关文字中操作符线程调整规则，以便所有相关变量以编码预期数据流的方式统一。保守扩张意义下的演化我们现在可以为面向对象的构造添加规则了。数据模型和数据流的先前进展使得最终执行真正保守的扩展成为可能：要添加的规则不会影响不引用新结构的程序的减少[1]。这种演变非常简单，因为它基本上意味着逐点重构意义上的进化基于规则的程序也可以进行相当具体的重构转换，程序员指出感兴趣的位置。作为示例，我们将改进到目前为止获得的解释器的一个特定细节。也就是说，我们要减少表达式计算谓词的参数数量。为了比较，当前的配置文件是这样的：：- profile evaluate（+exp，+varenv，+vmt，+this，+store，-val，-store）.R. Lämmel/Electronic Notes in Theoretical Computer Science 127（2005）4953似乎有三个位置+varenv，+vmt，+this有点不合理，因为这些位置都与环境类信息有关所有这些信息都传递给子计算。因此，我们的目标是具有以下结构的复合环境：-alias env=（varenv，vmt，this）。用于评价的同品种器械的特征简化如下：：- profile evaluate（+exp，+env，+store，-val，-store）。所需的分组e-排序是简单地自动化的REK同样，这个操作符并不只是简单地改变谓词类型，而且分组也会删除许多规则中的所有相关文字所示的分组变换在谓词位置的级别上操作。还可以考虑在其他层面进行的重组形式，例如，仿函数位置的级别或规则体的级别。在规则体级别上的转换的民间传说的例子是折叠和展开，其中展开意味着象征性地执行谓词应用，而折叠是相反的[11]。更一般地说，可以为语言解释器和其他基于规则的程序实例化所有类型的重构转换.修补意义上的进化我们考虑另一种进化情景。让我们假设我们希望启用方法调用的日志记录因此，我们将获得一个简单的调试设施的解释面向对象的语言。为此目的而调整OO解释器是相对直接的.我们基本上需要调整方法调用的解释器规则，以便记录方法调用。与其打乱现有的规则，我们可以应用一种进化转换，更明确和单独地记录适应的意图。REK操作符提供了一个相应的注入操作符，它允许人们增强通过声明附加的文字来表示给定规则的主体总结发言我们已经为语言解释器描绘了一些进化场景。(For一个深刻的介绍，我们参考[5，6]。这项工作有助于新兴领域对这一领域的兴趣越来越大，这是由于软件开发中与建模和元建模相关的新应用这些应用程序要求更好地理解语言（或元模型）和基于语言的功能（或模型驱动的转换）的演变。54R. Lämmel/Electronic Notes in Theoretical Computer Science 127（2005）49我们的进化转换方法接收来自其他学科的输入，如程序和数据精化、程序合成、转换程序开发（从规范）、数据再工程和语法软件工程。我们已经部署了演化转换作为一种通用方法，用于重构、扩展、收缩和修改基于语言的功能，如解释器。未来的工作对这个问题提供了实际有用的工具支持，基于规则的程序的演变，一个全面的分析，基本的和组成的演变运营商，和一个有意义的，正式的模型的演变，覆盖的转换，不严格的语义保持。引用[1] 阿塞托湖，W. Fokkink和C. Verhoef，Conservative extension in structural operationalsemantics ， Bulletin of the European Association for Theoretical Computer Science69（1999），pp.110[2] Büorger，E. 和河。Stak，[3] 卡斯滕斯大学和W.Waite，属性语法中的模块化和可重用性，Acta Informatica 31（1994），pp.601-627[4] 莱梅尔河，Declarativeaspect-orientdprgramming，在：O. Danvy，editor，ProceedingsPEPM131-146。[5] 莱梅尔河，基于规则的程序设计的演进，逻辑与代数程序设计杂志60-61C（2004），pp. 141L. Aceto和W. Fokkink.[6] Léammel，R. 、Evolutionsénariosforrule-based在L.中，将语言作为一种功能来实现。Aceto ， W. 福 金 克 和 我 。 Ulidowski ， editors ， Proc. of SOS workshop （ StructuredOperational Semantics），ENTCS（2004），20 pages.地出现。[7] 拉 梅 尔 河 、 E. 我 的 名 字 是 J 。Visser ， The EssenceofStrategic Programming（2002http://www.cwi.nl/~ralf。[8] Moggi，E.，计算和单子的概念，信息和计算93（1991），pp。55比92[9] Mosses，P.，“Action Semantics,” Number 26 in Cambridge Tracts in Theoretical ComputerScience, Cambridge University Press,[10] Mosses，P.，模块化SOS的语用学，在：H。Kirchner和C. Ringeissen，editors，AlgestimationMethodology and Software Technology：9th International Conference，AMAST21比40[11] Pettorossi，A.和M. Proietti，Rules and Strategies for Transforming Functional and LogicPrograms，ACM Computing Surveys28（1996），pp. 360-414[12] The Rule Evolution Kit - 下 载 ， 文 档 ， 论 文 ， 在 线 演 示 （ 2004 ） ， 由 R 编 写 。Léammel;http://www.cs.vu.nl/rekwww.example.com/;这两个软件的平均值为0.78。
