进化场景下的基于规则的基于数据库的功能实现的演化笔记

理论计算机科学电子笔记128（2005）61-79www.elsevier.com/locate/entcs基于规则的基于数据库的功能实现的演化场景RalfLüammel1荷兰阿姆斯特丹自由大学计算机科学系摘要我们的工作通过一系列的进化方案，基于语言的功能实现为基于规则的程序。我们确定并说明了不同的维度，沿着这些功能可以发展，包括以下内容：（i）编码风格;（ii）编码细节;（iii）数据模型;（iv）横切关注点;和（v）补丁。我们将语言解释器作为基于语言的功能的例子，但是对于类型检查器，静态分析，程序转换和其他类型的基于语言的功能也存在类似的情况。我们选择Prolog作为基于规则的编程语言，用于实现基于语言的功能。我们采用基于Prolog的规则进化工具包（REK）的操作化的进化方案，通过进化转换。我们编制了一个练习列表，旨在帮助消化场景和进一步探索整个主题。关键词：进化，进化转换，基于规则的编程，语言解释器，基于语言的功能，SOS，元编程，Prolog，REK1前导码我们将研究基于语言的功能的演变。基于语言的功能性是指解释器、类型检查器、程序分析和程序转换的实现。在本文中，我们将专注于语言解释器的进化场景。关于进化论，我们特别感兴趣的是关于程序的转换观点1电子邮件地址：ralf@cs.vu.nl1571-0661 © 2005由Elsevier B. V.出版，CC BY-NC-ND许可下开放获取。doi：10.1016/j.entcs.2004.09.03962R. Lämmel/Electronic Notes in Theoretical Computer Science 128（2005）61−适应性和扩展性。也就是说，我们将从进化转型的角度来操作进化情景。我们将在Prolog中编码基于语言的功能。基于规则的编程语言Prolog在这方面有着很好的记录。例如，人们可以或多或少地直接在Prolog中编码SOS规范，以便免费获得语言解释器[3]。也可以在Prolog中编码属性语法（但有一些限制）[2]。我们也将在Prolog中对进化转换进行编码。同样，Prolog在元编程方面有很强特别是，我们采用了规则演化工具包（REK [26]），这是一个Prolog库，它提供了在Prolog程序上执行演化转换的操作符。注：本文补充了2004年8月30日在伦敦举行的结构操作语义研讨会上的特邀演讲。这篇文章的一些片段摘自[12]。2最初的口译员后续章节中的演化场景都将处理解释器对一种简单的面向表达式的语言（我们称之为PURE）的适配或扩展。为了清楚起见，我们将详细说明这个解释器下面的Prolog会话记录了计算表达式的尝试letx= 2in lety = 3inxy：%rek/examples/pure/main.pl编译0.17秒，287，140字节欢迎使用SWI-Prolog（Version 5.3.18）版权所有（c）1990-2004阿姆斯特丹大学。？- evaluate（let（x，const（2），let（y，const（3），binary（var（x），*，var（y）Val = 6是？- 停止百分比，[]，Val）。谓词evaluate/3解释PURE表达式。第一个参数是上述表达式的术语表示。第二个参数是[]，它表示空变量环境。第三个参数Val通过表达式求值绑定到6谓词evaluate/3的类型如下，使用REK：-profile evaluate（+exp，+varenv，-val）。[2]这个符号是从[14]中采用的。每个谓词位置都由一个模式和一个排序类型化。模式排序是预定义的类型（例如，数字）、别名或代数数据类型。R. Lämmel/Electronic Notes in Theoretical Computer Science 128（2005）6163REK根据这些配置文件对谓词进行类型检查。REK还在演化转换中使用类型。表达式语法由以下代数数据类型定义：：-data exp = const（number）%Number constants| binary(exp,op,exp)% Binary operations| if(exp,exp,exp)% If-then-else| var(varid)% Read a variable| let(varid,exp,exp).%Bind a variable in a scope：-data op=（+）|......这是什么？.% 算术运算：-alias varid = atom。%变量标识符值（即， 表达式求值的结果）是数字：：- alias val = number.环境是标识符-值对的列表：：-alias varenv=[（varid，val）]。我们现在将给出解释器规则，这些规则非常简单。常量被这个Prolog事实简单地解释为evaluate（const（Number），_VarEnv，Number）.二进制表达式产生了以下Prolog规则，它类似于Kahn的自然语义模符号转换中的大步骤SOS规则evaluate（binary（Exp0，Op，Exp1），VarEnv，Val2）：-evaluate（Exp 0，VarEnv，Val 0），%计算左操作数evaluate（Exp 1，VarEnv，Val 1），%计算右操作数applyBop（Op，Val 0，Val 1，Val 2）。%应用二进制运算(We省略平凡的辅助谓词applyBop/4。）If-then-else表达式由两个规则解释，这取决于条件的值;数字0表示False;所有其他的True：evaluate（if（Exp0，Exp1，_Exp2），VarEnv，Val1）：-evaluate（Exp0，VarEnv，Val0），% Compute the conditionisNotZero（Val0），% Succeed for non-zero conditionevaluate（Exp1，VarEnv，Val1）. %Compute then表达式evaluate（if（Exp0，_Exp1，Exp2），VarEnv，Val1）：-evaluate（Exp0，VarEnv，Val0），% Compute thecondition isZero（Val0），% Succeed for zero conditionevaluate（Exp2，VarEnv，Val1）. %Compute else表达式(We省略平凡的辅助谓词isZero/1和isNotZero/1。）从环境中查找变量：evaluate（var（Varid），VarEnv，Val）：-lookupVarEnv（VarEnv，Varid，Val）.(We省略环境查找的谓词lookupVarEnv。）let绑定通过环境传播：evaluate（let（Varid，Exp0，Exp1），VarEnv0，Val1）：-evaluate（Exp0，VarEnv0，Val0），modifyVarEnv（VarEnv0，Varid，Val0，VarEnv1），evaluate（Exp1，VarEnv1，Val1）.64R. Lämmel/Electronic Notes in Theoretical Computer Science 128（2005）61(We省略谓词modifyVarEnv进行环境修改。）下面的部分关注PURE解释器的发展3风格转换意义上的进化最初的解释者是以大步的风格给出的当选择小步风格时，一些语言扩展更容易适应，例如，异常处理或并发性属于这种类型。因此，我们将把PURE解释器从大步长风格转换为小步长风格。让我们再次考虑二进制表达式的解释器规则：evaluate（binary（Exp0，Op，Exp1），VarEnv，Val2）：-evaluate（Exp0，VarEnv，Val0），evaluate（Exp1，VarEnv，Val1 ） ， applyBop （ Op ，Val0，Val1，Val2）.这条规则显然是大步长风格的，因为所有的子表达式都是通过递归应用evaluate/3来减少的。甚至谓词的类型也不适合小步骤。我们对比evaluate/3的当前配置文件和所需配置文件：：-profile evaluate（+exp，+varenv，-val）。%固有的大步风格：-profile evaluate（+exp，+varenv，-exp）。采取小步骤百分比(We倾向于在如上所示的改编的节目片段下面加下划线）。也就是说，对于小步长样式，谓词将描述两个表达式（包括约简值）上的关系，而不是表达式和值。我们通过使用一个新的函子val 2 exp/1将值嵌入到表达式中来适应evaluate/3的类型。我们将函子添加到表达式语法中，如下所示：：-data exp= val2exp（val）。为了保持可输入性，对evaluate/3类型的修改需要修改所有使用或定义evaluate/3的规则。也就是说，我们用val 2 exp/1系统地包装其结果位置。例如，二进制表达式的规则修改如下：evaluate（binary（Exp0，Op，Exp1），VarEnv，val2exp（Val2））：- evaluate（Exp0，VarEnv，val2exp（ Val0 ） ） ， evaluate （ Exp1 ，VarEnv ， val2exp （ Val1 ） ） ，applyBop（ Op， Val0，Val1，Val2）.事实上，REK提供了一个操作符，它可以自动完成这一任务。以下othertype应用程序将所有PURE规则转换为启用小步的类型：：-othertype（evaluate，val2exp）。这个目标子句说明了记录进化跨-R. Lämmel/Electronic Notes in Theoretical Computer Science 128（2005）6165阵也可以直接从Prolog会话中发出这样的转换。还可以设想用于进化转换的交互式工具支持我们注意到，操作数的类型evaluate和val2exp控制了othertype运算符的应用。也就是说，函子val2exp的域val和共域exp指定了变换前后相关谓词位置的类型从大步骤到小步骤转换的困难部分是分解大步骤规则。看看二元表达式的规则，很明显，我们希望最终得到三个小步规则：一个用于两个操作数中的每一个，另一个用于二元运算的实际应用下面是第一个小步骤规则，它使左操作数取得进展：evaluate（binary（Exp0，Op，Exp1），VarEnv，binary（Exp2，Op，Exp1））：-evaluate（Exp0，VarEnv，Exp2）.有一个类似的规则，它使用右操作数进行处理：evaluate（binary（Exp0，Op，Exp1），VarEnv，binary（Exp0，Op，Exp2））：-Exp0 = val2exp（_Val），evaluate（Exp1，VarEnv，Exp2）.这个规则是这样的，左操作数必须在右操作数被考虑之前是简化形式。我们假设大步骤规则中前提的顺序暗示了这样一种确定性的求值顺序。一旦两个操作数都是简化形式，我们就可以计算最终值：evaluate（binary（val2exp（Val0），Op，val2exp（Val1）），_VarEnv，val2exp（Val2））：-applyBop（Op，Val0，Val1，Val2）.同样，REK提供了一个操作符big2small来自动化这一点。以下应用程序将所有：-big2small（evaluate，exp）.big2small算子执行系统分析以从大步规则恢复结构归纳和相关数据流3为了完成这个场景，我们通过一个额外的谓词来补充所获得的小步作为辅助步骤，我们将新谓词evaluate/3重命名为evaluateSmall/3，更好地说明它的地位。 REK为此提供了一个合适的重命名操作符目的：：-rename（pred（evaluate/3），pred（evaluateSmall/3））。下面是Prolog谓词，它接受传递闭包：：- profile evaluateBig（+exp，+varenv，-val）。3当前REK中操作符的实现是特别的。定义一个普遍的、明显合理的、透明的大步骤到小步骤的转换是一个研究挑战。66R. Lämmel/Electronic Notes in Theoretical Computer Science 128（2005）61evaluateBig（Exp0，VarEnv，Val）：-evaluateSmall（Exp 0，VarEnv，Exp 1），%执行一步！（evaluateBig（Exp 1，VarEnv，Val）%如果可能，执行更多步骤！; Exp1 = val2exp（Val））。完成所有步骤的百分比;找 到 值。我们把它作为练习留给读者来添加利用已建立的小步风格的语言结构。我们还注意到，实际上还有许多其他的风格转换可以在程序演化过程中提供帮助：从小步风格到大步风格的转换，相互递归谓词的混合风格变体，CPS转换等等。此外，特定的基于规则的编程语言或特定于领域的基于语言的功能会产生相应的特定风格转换;我们提到monad引入（或monadication）作为从函数式编程中采用的类似解释器的例子[10，5]。另一个例子是删除语法中的左递归，甚至是属性语法中的左递归，这与前端实现有关[19]。我们将回到大跨步风格的其余部分的文件。4数据模型假设我们想在PURE语言中加入面向对象的结构。扩展表达式形式的sortexp很简单：-data exp=call（exp，meth，[exp]）%方法调用| get(exp,field)% Reading field access| set(exp,field,exp)% Writing field access| new(class)% Object construction| this.%活动对象：- aliasclass = atom。%类别ID：- alias field= atom。%字段ID：-aliasmeth = atom。%方法ID然而，事实证明，这些构造的解释不能仅仅通过向原始PURE解释器添加规则来完成这个解释器不适合这样一个保守的扩展。一个问题是，到目前为止，评价结果的类型是硬编码的，以符合数量。现在我们需要区分数字和对象引用。事实上，问题的关键是val到目前为止是一个类型别名：-alias val = number.%令人反感的封闭世界假设作为中间步骤，我们需要将val转换为数据类型：：-data val = num（number）. 稍 后 添 加 的对象引用百分比然而，如图所示，仅仅重新定义价值是不够的。原始规则需要修改以反映类型的变化。例如，如果没有进一步的规定，常量的正常求值将不会进行类型检查：evaluate（const（Number），_VarEnv，Number）. % Type error！R. Lämmel/Electronic Notes in Theoretical Computer Science 128（2005）6167无论何时，只要预先存在的PURE规则提交数字，就需要对它们进行调整。用于常量求值的Prolog事实需要调整，以使返回的number被函子num/1包装：evaluate（const（Number），_VarEnv，num（Number））.REK操作员操作员newtype和relax，可以联合使用来自动化这种进化转型：：-newtype（val，num）.%将别名转换为数据类型：-relax（val）.%消除空匹配和建筑这个序列提供了所需的数据类型val，并且在必要时，类型val的所有位置都被包装在num中。newtype操作符的应用实际上将val类型的所有位置都包含在num中，而relax操作符的应用则消除了num的空值。为了理解这个细节，让我们考虑一下let表达式的规则，就像它看起来一样，在应用relax运算符evaluate（let（Varid，Exp0，Exp1），VarEnv0，num（Number1））：-evaluate（Exp0，VarEnv0，num（Number0）），modifyVarEnv（VarEnv0，Varid，num（Number0），VarEnv1），evaluate（Exp1，VarEnv1，num（Number1））.所有出现的num都是空的，因为匹配的数字永远不会按原样使用，但它们总是重新包装在num中。 因此，该规则可以简化如下，这实际上是由relax运算符自动化evaluate（let（Varid，Exp0，Exp1），VarEnv0，Val1）：-evaluate（Exp0，VarEnv0，Val0），modifyVarEnv（VarEnv0，Varid，Val0，VarEnv1），evaluate（Exp1，VarEnv1，Val1）.这种简化反映了let表达式对于数字和对象引用都很有用从技术上讲，松弛算子支持由Plotkin和Reynolds [24，27，18]开创的某种形式的反统一接下来需要添加对象引用：：-data val = ref（ref）. %为对象引用添加：-alias ref = integer。%对象引用为整数为了完整起见，我们还添加了面向对象语言扩展的解释器规则最终需要的所有语义域：：-alias this = maybe（ref）.%当前对象：-alias vmt=[（class，meth，[varid]，exp）]。%方法表：-alias store =[（ref，class，obj）].%对象存储：-alias obj=[（field，val）].%字段-值对到目前为止，我们已经进化了PURE语言的原始解释器，至少它的数据模型适合面向对象语言扩展。要完成实际的语言扩展，需要更多的扩展，我们现在将讨论68R. Lämmel/Electronic Notes in Theoretical Computer Science 128（2005）615贯穿各领域的问题面向对象语言扩展还需要一个增强的谓词来进行表达式求值。到目前为止，我们只在方法参数和临时结果的意义上传递了变量的环境（参见。let）。我们需要为虚方法表、当前对象和对象存储添加参数原始规则必须进行调整，以便它们参与这些新语义组件的数据流这种分散的数据流或计算（它会影响许多或所有现有的规则）最好被看作是面向方面编程意义上的横切关注点的实现（面向方面编程、基于规则的编程和程序转换之间的这种联系在[9]中有详细的探讨。）为了比较，下面是evaluate谓词的原始类型：-profile evaluate（+exp，+varenv，-val）。所需的谓词必须属于以下类型：：- profile evaluate（+exp，+varenv，+vmt，+this，+store，-val，-store）.(By默认情况下，我们将参数关联到左侧，将结果关联到右侧。REK在将位置添加到谓词时也使用此约定为了比较，下面是二元表达式的原始规则evaluate（binary（Exp0，Op，Exp1），VarEnv，Val2）：-evaluate（Exp0，VarEnv，Val0），evaluate（Exp1，VarEnv，Val1 ） ， applyBop （ Op ，Val0，Val1，Val2）.增强的规则如下所示evaluate（binary（Exp0，Op，Exp1），VarEnv，Vmt，This，Store0，Val2，Store2）：-evaluate（Exp0，VarEnv，Vmt，This，Store0，Val0 ， Store1 ） ， evaluate （ Exp1 ， VarEnv ，Vmt，This，Store1，Val1，Store2），applyBop（Op，Val0，Val1，Val2）.我们注意到虚方法表是只读的：Vmt从规则的头部传播到求值谓词的所有递归出现;对于当前对象This也是如此。相比之下，对象存储受状态传递机制的影响：Store 0通过头部进入规则;它使用Store 1和Store 2穿过规则;后者通过头部返回REK再次提供了使这些增强功能自动化的操作员。第一波转换添加所有必需的谓词位置：：-add（+vmt，evaluate）.%传递虚方法表：-add（+this，evaluate）. %传递当前对象：-add（+store，evaluate）.%接收对象存储：-add（-store，evaluate）.% 返回对象存储库最重要的是，这些转换会导致预期的类型。也就是说，REK确实为evaluate谓词报告了以下类型：R. Lämmel/Electronic Notes in Theoretical Computer Science 128（2005）6169：- profile evaluate（+exp，+varenv，+vmt，+this，+store，-val，-store）.然而，这些规则处于瞬态：新的变量被添加为所有evaluate事件的参数，但尚未编码特定的数据流因此，我们面临着以下中间结果：evaluate（binary（Exp0，Op，Exp1），VarEnv，_Vmt0，_This0，_Store0，Val2，_Store5）：-evaluate（Exp0，V arE nv，_V mt 1，_Th is 1，_St ore1，Val0，_Store 2），evaluate（Exp1，V arE nv，_Vmt 2 ， _Th is 2 ， _St ore 3， Val1 ， _Store 4），applyBop（Op，Val0，Val1，Val2）.REK使用下面的第二波转换，我们增强了所有的解释器规则，就像前面针对二进制表达式所展示的那样：：-thread（vmt）. %安排虚拟方法表的传播thread（thread） %安排当前对象的传播thread（store）.%安排对象 存储 的状态传递从概念上讲，线程操作符支持环境和状态传递机制的通用组合。从技术上讲，线程操作符通过统一规则中的变量来建立数据流。为此，给定排序的所有参数（参见vmt、this和store）以一定的从左到右的顺序排序，使得每个unfined、using的出现可以被与最近的、定义性的事件相统一;我们参考[12]了解详细信息。使用转换实现横切关注点的总体好处是不需要编写混乱的代码。同样，原始的（简单的）规则可以被重用，横切关注点被单独描述-作为转换操作符的应用。这显然是关注点分离的一种形式。我们注意到，横切关注点以外的线程可以受到基于规则的程序的演变。所谓的Prolog程序逐步增强技术[8，28，7]和基于规则编程的相关转换框架[9，13，15]促进了其他横切三角洲。例如，在规则集中有一种monoidal计算的技术，其中monoid的操作用于合成子计算贡献的信息（例如输出）。 另一种横切关注点的一个重要方面是响应启用基于规则的程序，即，程序被增强以使其能够内省其自身的执行。最后，当横切关注点的当前实现被认为是不合适的时候，也有用于切割横切关注点的 例如，存在运算符add和add的（近似）逆运算符。螺纹. add的逆操作允许删除位置和相关的数据流线程的近似逆允许刷新预测位置，使得它们不携带相同的变量，从而随后可以建立不同的数据流70R. Lämmel/Electronic Notes in Theoretical Computer Science 128（2005）616保守扩张我们现在可以为面向对象的构造添加规则了。数据模型和数据流的先前进展使得最终执行真正保守的扩展成为可能：要添加的规则并不影响仅引用PURE构造的程序的减少[1]。这种进化非常简单，因为它基本上意味着将两个规则集“放在一起”，而不是对规则进行侵入式转换。为了简洁起见，我们只提供一个面向对象构造的细节不会有意外的。以下规则计算方法调用：evaluate（call（Exp0，Meth，Exps），VarEnv0，Vmt，This0，Store0，Val，Store3）：- evaluate（Exp0，VarEnv0，Vmt，This0，Store0，ref（Ref），Store1），evaluatelist（Exps，VarEnv0，Vmt，This0，Store1，Vals，Store2），lookupVmt（Vmt，Store2，Ref，Meth，Args，Exp1），zip（Args，Vals，VarEnv1），evaluate（Exp1，VarEnv1，Vmt，just（Ref），Store2，Val，Store3）.为了清楚起见，我们逐一解释这些前提• 评价（...）：确定被调用对象。• evaluatelist（.）：计算实际参数。• lookupVmt（.）：查找方法。• zip（.）：形式参数映射到实际参数。• 评价（...）：方法体被求值。通过添加此规则以及get/set字段访问和其他构造的进一步规则，我们完成了面向对象语言扩展。在我们看来，基于规则的程序的进化是一个连续的过程，其中以下类型的活动交替进行：• 重组以准备延期或修订。• 通过模块化组合或编织来添加新关注点的扩展。• 修改以删除或更换不适当的部件。7逐点重构从第二节开始的风格转换。3是高度系统化的重组转换，几乎不需要用户干预。显然，基于规则的程序也可以进行更具体的重构转换，程序员指出感兴趣的位置。我们将改进目前为止获得的解释器的一个特定细节也就是说，我们要减少表达式计算谓词的参数数量。为了比较，当前的配置文件是这样的：：- profile evaluate（+exp，+varenv，+vmt，+this，+store，-val，-store）.似乎有三个位置+varenv，+vmt，+这有点离谱，因为这些位置都与环境有关，如在-R. Lämmel/Electronic Notes in Theoretical Computer Science 128（2005）6171阵所有这些信息都传递给子计算。因此，我们的目标是包含以下组件的复合：-alias env=（varenv，vmt，this）。用于评价的同品种器械的特征简化如下：：- profile evaluate（+exp，+env，+store，-val，-store）。为了进行比较，下面是两个需要简化的详细规则：evaluate（const（Number），_VarEnv，_Vmt，_This，Store，num（Number），Store）. evaluate（binary（Exp0，Op，Exp1），VarEnv，Vmt，This，Store0，Val2，Store2）：-evaluate（Exp0，VarEnv，Vmt，This，Store0，Val0 ， Store1 ） ， evaluate （ Exp1 ， VarEnv ，Vmt，This，Store1，Val1，Store2），applyBop（Op，Val0，Val1，Val2）.上述规则并不真正涉及任何类似环境的信息.因此，通过使用单个类似环境的参数，这些规则变得更加简洁：evaluate（const（Number），_Env，Store，num（Number），Store）.evaluate（binary（Exp0，Op，Exp1），Env，Store0，Val2，Store2）： - evaluate （ Exp0 ， Env ， Store0 ，Val0，Store1），evaluate（Exp1，Env ， Store1 ， Val1 ， Store2 ） ，applyBop （ Op ， Val0 ， Val1 ，Val2）.对于与环境组件有关的规则，元组模式足以访问组件。事实上，元组模式取代了原始规则中多个位置的使用。例如，方法调用的规则被重新构造如下：evaluate（call（Exp0，Meth，Exps），（VarEnv0，Vmt，This），Store0，Val，Store3）：- evaluate（Exp0，（VarEnv0，Vmt，This），Store0，ref（Ref），Store1），evaluatelist（Exps，（VarEnv0，Vmt，This），Store1，Vals，Store2），lookupVmt（Vmt，Store2，Ref，Meth，Vids，Exp1），zip（Vids，Vals，VarEnv1），evaluate（Exp1，（VarEnv1，Vmt，just（Ref）），Store2，Val，Store3）.REK的组运算符简单地自动化了分组：-group（env）.也就是说，元组类型env被视为应该分组的位置的枚举。组运算符搜索所有谓词配置文件，添加到tuple类型的位置。每个这样的位置组被元组类型的单个位置所示的分组变换在谓词位置的级别上操作。还可以考虑在其他层面进行的重组形式，例如，函子位置的级别或规则体的级别。在规则体级别的转换的可折叠示例是折叠和展开，其中展开意味着象征性地执行谓词应用，而折叠是相反的[23]。72R. Lämmel/Electronic Notes in Theoretical Computer Science 128（2005）618修补意义上的进化我们将再执行一个解释器扩展。也就是说，我们启用了方法调用的日志记录。从而，我们得到一个简单的调试设施的解释面向对象的语言。下面的日志文件让一切都变得清晰;我们展示了3的计算！：调用：1.fac（[（x，num（3））]）调用：1.fac（[（x，num（2））]）调用：1.fac（[（x，num（1））]）调用：1.fac（[（x，num（0））]）返回：num（1）返回：num（1）返回：num（2）返回：num（6）对于每个方法调用，我们显示被调用方的对象引用、被调用方法的名称和参数环境。这里我们假设Factorial方法是由一个引用为1的对象提供的。缩进表示呼叫者与被呼叫者之间的关系。方法调用完成后，将显示返回值。为此目的调整OO解释器是相对简单的。方法调用的解释器规则如下：evaluate（call（Exp0，Meth，Exps），（VarEnv0，Vmt，This），Store0，Val，Store3）：- evaluate（Exp0，（VarEnv0，Vmt，This），Store0，ref（Ref），Store1），evaluatelist（Exps，（VarEnv0，Vmt，This），Store1，Vals，Store2），lookupVmt（Vmt，Store2，Ref，Meth，Vids，Exp1），zip（Vids，Vals，VarEnv1），printCall（Ref，Meth，VarEnv1），evaluate（Exp1，（VarEnv1，Vmt，just（Ref）），Store2，Val，Store3），printReturn（Val）.因此，我们基本上已经向规则的主体添加了两个字面值。 谓词printCall/3应该打印日志行“Call：.” 并增加缩进，而谓词printReturn/1应该打印日志行“Return：...”并减小缩进。（我们省略了printCall/3和printReturn/1的简单定义。REK操作注入操作符，它允许增强给定规则的主体。我们可以使用这个操作符将日志记录功能描述为方法调用规则上的增量：- inject（（evaluate（call（_，Meth，_），_））：-evaluate（_，ref（Ref），_），_，_，zip（_，_，VarEnv），{ printCall（Ref，Meth，VarEnv）}，evaluate（_，Val，_），{printReturn（Val）}））。R. Lämmel/Electronic Notes in Theoretical Computer Science 128（2005）6173也就是说，inject操作符获取规则的新的文字被{... . }。通过将草图与现有规则进行基地 匹配的和附加的文字可以共享变量，如Ref、Meth和上面的其他变量与手动编辑因为原始规则和附加功能在源代码中保持分离。这是关注点分离的另一种形式。9演习我们现在将编制一个练习列表，旨在帮助理解前面章节中的演化场景，并进一步探索整个主题。对一些练习的良好处理可能需要进一步阅读，在这种情况下，我们提供了一些提示和指针。有些练习更像是挑战。让我们首先通过放弃对Prolog的限制来概括讨论。其他形式的基于规则的编程也同样有意义，例如，一阶函数编程、条件项重写或属性语法编程。我们还想看看基于语言的功能，而不是解释器。练习1（非Prolog，非解释器示例）a) 选择一个属性语法系统，并研究以下前端的进化方案，包括静态语义和ab-语法树的构造：a.1) 为具有赋值的语言指定属性语法。a.2) 从a.1）扩展属性语法以涵盖记录和数组。a.3) 把从a.1）到a.2）的转变描述为一种进化的转变。为此，确定一些在此上下文中似乎有用的进化转换（关于属性语法系统的调查，以及对模块化、可扩展性和适应性技术的讨论，可以在[13]中找到。b) 选择一个提供某种遍历策略的重写框架[16]（例如，Strafungo，Strafunski，ASF+SDF），并研究Java度量工具的以下演变场景：b.1) 计算条件语句的嵌套深度。(The一组Java语句包括if-then-else、while、try和其他几个语句。一些相关的文献可以在[17]中找到74R. Lämmel/Electronic Notes in Theoretical Computer Science 128（2005）61b.2) 调整解决方案，以便分别为每种形式的条件语句计算嵌套深度。确定至少两个不同的适应性设计。b.3) 把从b.1）到b.2）的转变描述为一种进化的转变。c)选择一个图转换引擎，比如Progres [25]，并研究以下在元建模和MDA上下文中（简化的）UML类图的模型转换的演化场景[21]：c.1) 为一组给定的类指定死类消除，这些类被一组公共类限定为被明确保留c.2) 调整解决方案，以便区分两相。首先，不可达类被标记为消除。第二，所有标记类都被删除。c.3) 把从c.1）到c.2）的转变描述为一种进化的转变。Q我们现在将研究进化转换的语义保持。有两种类型的语义保持转换：重构转换与扩展。例如，组操作符以语义保持的方式进行重构：它对谓词的参数进行分组，而不改变或扩展基于规则的程序的行为，手下面的练习涉及其他REK操作符是否保持语义的状态为了具体的语义，我们假设这些练习是指定义子句程序（即，纯Prolog）：练习2（语义保持与否？）a) 解释为什么从第二节开始的大步到小步的转换。3是语义保持。b) a）问c)确定第2节中注入前提的充足条件。8，这样这种进化转换就变成了语义保持。d) c）假设e)是添加额外的参数，如在第二节。五是结构调整？添加参数是否仍然保持语义？解释你的答案。f) 从严格意义上讲，线程操作符不是语义保持的。提供一个简单的Prolog片段来说明线程化导致的统一不是语义保持的。g) 论证了加法位置与加法位置的顺序组合运营商，并随后对他们实施数据流制度，R. Lämmel/Electronic Notes in Theoretical Computer Science 128（2005）6175线程操作符是语义保持的。提供一个简单的Prolog片段来说明你的解释。(The[12]应该是有用的。Q虽然我们在上面强调了语义保持，但我们应该注意到，进化转换不能局限于语义保持;为此，我们也参考了[4，12]。语义保持是软件维护中的一种错觉。我们上面所说的重构转换，与Opdyke和Fo