树型匹配与程序变换[*] 张乃孝 (北京大学) TREE PATTERN MATCHING AND PROGRAM TRANSFORMATION Naixiao Zhang (Peking University) ABSTRACT In this paper, the issuses of tree pattern matching are discussed and the concept of structural consistency matching which is usefull in program transformation is introduced. Tree algorithm framworks on the program transformation are proposed after analizing the procedures of transformation. 摘要 本文讨论了树型匹配的问题,引入结构相容匹配的概念,并把这一概念用于程 序变换之中;本文对程序变换的表示作了简洁的叙述,对变换过程作了深入的分 析,并在此基础上提出三种用于程序变换的算法框架. ------------------------------------- *本项研究得到国家自然科学基金的资助. 1. 树型模式匹配 在计算机科学和人工智能的许多领域中,模式匹配是基本的运算之一. D.Knuth 等人发明的关于字符串的快速匹配算法[1]将匹配的速度提高到线性数量级,但是在 实际问题中碰到的大量模式匹配,并不总要求是两个常量之间的"完全匹配"(例如 D.Knuth 的算法中所处理的在串 T 中找与串 P 完全相同的子串),而只要求"一致 匹配",例如 R.Kowalski 在对逻辑程序作过程解释时,关于一个子目标与一个规则 首部进行匹配,只要求能够通过"合一替换"使它们相同,即匹配成功[2][12].另外在 许多复杂的问题中,匹配的目标和模式自身的结构都不是串所能简单刻画的,在这种 情况下要借助于复杂的结构----树.为了区分于一致匹配,我们引入"结构相容"的概 念.一棵目标子树 Tj 与一个模式 Pi "结构相容"是指 Pi 中的内部结点与 Tj 中 相应内部结点具有相同的结构,且 Pi 中的叶结点与 Tj 中对应成分(可能是叶结点 ,也可能是子树)"相容",关于相容的具体定义可按具体应用的不同而异,这里不作具 体规定.下面举一例以说明. 例 1. 目标子树 T1: x1 and x2, T2: y and not y 和 T3: (a+b)>0 and c < T1 / / \ / \ y + 0 c d T2 / \ a b T3 and and / \ / \ b1 b2 b not P1 / b P2 图 1. 在这个例子中 P1 的 b1 与 x1, y, (a+b)>0 均相容,b2 与 x2, not y, c0 表示 b 为真,从而 b1 and b2 便可用 j1*j2 来表示(前提为:j1 是 b1 的表示,j2 是 b2 的表示)等等.这类规则在抽象类型和表示类型之间建立了一种联 系,但并不直接用于变换. 2.2. 重写规则 它定义了一类表达式在该种变换下等价的重写形式.例如在上 述情况下,源程序中的任何布尔表达式 b ,均可用 j>0 替换,效果相同(前提为: j 已作为 b 的一种表示而在程序中存在). 2.3. 置换规则 它定义了一类语句在该变换下等价的置换形式.例如在上述 用整型实现布尔类型时,赋值语句 b1:=b2 ,可用 j1:=j2 等价地置换(前提同前). 3. 变换的基本过程 将一个变换模块作用于某程序中一个或多个抽象类型的变量时,变换系统的任 务是: (1) 将源程序中所有应变换的抽象变量,包含其定义性说明在内,改用其具体 表示类型的变量来代替; (2) 将所有源程序中与这些抽象变量有关的运算(包含置 初值),改用其具体表示类型的运算来实现.为完成变换的任务(特别是第 2 项任务), 就必须反复使用变换模块中的有关规则,这里不仅要作大量的树型匹配工作,同时也 包含目标树的生成和置换等许多复杂的处理. 按语言的文法,一个源程序 T 自然地被表示为一棵树;而一个规则 P 则可以表 示为两棵树所组成的对偶 ( Pl,Pr ),其中 Pl 为规则左部对应的树,它给出被变换 的语言成分(语句或表达式)的模式, Pr 为规则右部对应的树,它给出变换后的结果 模式. 将规则 P 作用于源程序 T 时,首先要将 Pl 与 T 进行树型模式匹配,一旦 (相容)匹配成功,即若存在 T 的一个子树 Tj 与 Pl 结构相容,则可按匹配时所得 的(相容)信息,将 Pr 进行实例化处理,产生相容的目标子树,记为 Pr',用 Pr' 替 换 T 中的 Tj ,得到 T'= T 对 T' 重复上述过程,直到以下两种情况之一出现时过程结束: (1) 变换任务 已全部完成; (2) 没有规则可以匹配. 4. 变换过程分析 4.1. 不确定性 给定一个待变换的源程序树 T 和一组规则 Pi (i=1,2,...,n),取 T 中哪个子 树与取哪个规则进行匹配都是不确定的,实际上这些匹配过程完全可以并行处理.在 下面的讨论中,我们探索一种确定的顺序的策略来实现变换的过程.首先要对 T 中 的子树规定一个选取顺序(最自然的想法是按先根次序周游 T ,自顶向下地选取子 树,在下一节中我们还将介绍一种按后根次序周游 T ,自底向上的选取子树方法), 同时对 Pi 的使用也要规定一种顺序(最简单的策略是按自然顺序处理,优化的策略 可将规则按性质分类,并按高度排序后使用).需要注意的是无论采用何种顺序策略 都是变换过程的一种具体实现,均应正确完成变换的任务.这里正确的含义有二: 第一:如果该变换有解,则顺序实现必须能得到一个满足要求的变换结果.第二:如果 该变换无解,则具体实现也应无解,换句话说要求顺序实现所得到的结果一定是该变 换的解. 4.2. 多解性 由于不确定性,产生多解性.并行处理所有子树与所有规则的匹配,理论上虽然 可以同时得到所有可能的变换结果,实际上,由于要求的处理机数随匹配成功的次数 按指数增长,所以是任何系统所不能承受的.一般来讲采用顺序处理的策略,把不确 定的过程确定化后,每次仅能得到一种变换结果,并且不同的处理策略所得到的结果 程序往往不相同,在这种情况下如何判别一个变换结果的好坏则比较困难. 例 2. 假设 y and not y 是某源程序中的一个表达式, y 是布尔类型的抽象变 量,用整型变量 yj 表示 y ,并有以下规则 (1) 表示规则 not b ----> if j>0 then 0 else 1 (2) 表示规则 b1 and b2 ----> j1*j2 (3) 表示规则 b and not b ----> 0 (4) 重写规则 b ----> j>0 变换结果有以下几种可能: (a) 对 y 分别使用(4)得 ( yj > 0 ) and not ( yj > 0 ) (b) 对第一个 y 使用(4),对 not y 先使用(1)得到 not y 的表示形式,然 后用(4)得 ( yj > 0 ) and ( if yj > 0 then 0 else 1 ) > 0 (c) 对 not y 用(1),然后对 y and not y 用(2),最后用(4)得 yj * ( if yj > 0 then 0 else 1 ) > 0 (d) 对 y and not y 用(3)得到其整型表示为 0 ,然后用(4)得 0 > 0 (a)和(b)仍包含布尔运算符,所以不是需要的结果,而(c)和(d)都应算变换成功, 但显然结果(d)比(c)要更好,其原因是首先使用了表示规则中高度最大的规则(3). 在下面我们考虑的变换算法中,一方面追求能求得所有的变换结果,另一方面在 不能得到全部解时,力争给出最有价值的变换结果. 4.3. 表示规则的作用 表示规则为构造抽象类型表达式的具体表示提供了规则.使用表示规则可以直 接从抽象操作对象的具体表示构造出抽象运算结果所对应的具体表示形式,而这种 表示是重写规则和置换规则实现变换的前提.(参考例2中表示规则所起的作用). 在表示规则中引用的抽象类型的变量可以与任何类型相同并且其具体表示已知 的表达式相容,正是这一点使一个表示规则可以在变换过程中反复使用或与其它表 示规则结合使用,如同函数复合那样构造出无穷多个需要的表示规则. 例 3. 从例 2 中的规则(1)和(2)便可派生出以下表示规则: (1) b1 and b2 and b3 ----> j1 * j2 * j3 (2) b1 and not b2 ----> j1 * ( if j2 > 0 then 0 else 1 ) (3) not ( b1 and b2 ) ----> if ( j1 * j2 > 0 ) then 0 else 1 (4) not not b ----> if ( if j > 0 then 0 else 1 ) > 0 then 0 else 1 ...... 所有的表示规则(包含派生出的在内)都遵循表示不变式的约束.[13] 引入表示规则使变换模块的定义更加简洁,然而使变换的处理更加复杂,因为这 时变换的过程不仅是: 目标子树与Pl的匹配----生成变换结果子树----替换源子树 三步曲的重复,而且在变换时对每个表达式子树首先要考虑与表示规则可能的匹配 问题,并在表示规则匹配成功后生成该表达式的"表示子树",以供变换较大的目标子 树时使用. 4.4. 变换过程的终止 变换过程终止于以下两种状态之一:(1) 变换成功,这时第3节中所要求的任务已 全部完成; (2) 变换失败,即穷举所有可能的变换,均不能将源程序变成要求的结果. 在变换的某一阶段,有时从局部看用某一规则是可行的,然而从全局看是不可行 的.例如例2中(a),(b)两种结果,这时需要回溯,放弃原来的选择,改用其它规则,这 种回溯是变换过程中的正常处理,不应看为变换失败,只有在所有可能均已试过而无 法成功时才宣告失败. 造成变换失败的原因,除系统因素外,主要是用户定义的变换模块不完全,使得 某些应该消除的抽象类型的运算不能被替换,这时系统应该给出相应提示信息. 5. 控制变换的算法框架 在变换前首先将规则按类型分组,即分成表示规则,重写规则和置换规则三组.变 换时对源程序中代表语句的子树只需考虑置换规则,而代表表达式的子树只需考虑 重写规则,表示规则仅在构造表达式的具体表示时使用.每组内可按规则中 Pl 的高 度排序,高者优先选用.变换开始,先将源程序中待变换的抽象变量的说明用相应的 表示变量的说明代替,并将对应信息记录在有关文件之中. 下面我们重点讨论在用具体类型的运算实现源程序中与抽象变量有关的运算时, 三种不同的控制变换的算法框架. 5.1. 自顶向下的回溯算法 这是最自然的控制算法,即从源程序树的根结点开始,按先根顺序取一个子树与 一个规则(严格讲是规则左部的 Pl )匹配,结果有三种可能: 1. 匹配失败,则取下一个规则与这个子树匹配,若所有规则左部均不能匹配成 功,则取下一个子树与各规则匹配,若所有子树都不能匹配成功则变换以失败而告终. 2. 匹配成功,则用匹配的相容信息,根据相应规则的右部模式,生成实例化的结 果子树,并用它替换源目标子树,然后继续按先根次序处理. 3. 有条件的匹配成功,这种情况主要来自规则左部中的抽象变量要求有相应 的具体表示,而源程序中与之相容的子表达式还未处理,所以不能肯定是否一定能得 到相应的表示形式,这时需进入相应子表达式,用表示规则与之匹配(这也是一个递 归过程),若匹配成功,便可得到相应表示,然后确认本匹配成功,执行与 2 中相同工 作,否则按匹配失败处理. 当所有应变换的子树均完成替换,则变换成功,最后得到的程序即为变换结果. 这种自顶向下的算法是一种穷举的策略,思想朴素,回溯自然,但每次只能得到 一个变换的结果,若要得到所有结果必须在成功将结果输出后,再按匹配失败进行回 溯,直到穷举所有可能为止,其中包含许多重复的工作,时间代价显然较高. 5.2. 自底向上的动态规划算法 这是一种企图同时求得所有变换结果的策略.它从源程序树的叶结点开始,按后 根顺序取一个子树与各个规则匹配,对代表表达式的子树首先考虑各表示规则,得到 所有可能的表示形式,然后再考虑重写规则,对代表语句的子树,仅需考虑置换规则. 这种算法的特点是:在处理每个子树时,这个子树的所有真子树均已处理完毕,并且 将它们所有可能的表示形式和变换结果均保存在有关文件中,所以对一个子树的匹 配不会出现自顶向下时的回溯情况,如果一个子树不能与任何规则匹配,则该子树本 身也是一个(未用任何规则的)变换结果,加上其各子树变换的的结果,很容易组合出 该子树所有可能的变换结果和具体表示形式(如果为表达式时). 这种策略的主要缺点是为保存子树的可能变换结果和表示形式要付出相当大的 空间代价,特别是有多个解的情况下,源程序树的上层结点可能出现大量组合. 5.3. 自顶向下与自底向上的结合算法 考虑到实际的变换主要是对抽象变量和相关运算进行的,所以主要出现在源程 序树的底层,为节省存储开销,可以将上述两种算法结合起来,即先用自顶向下的策 略,待找到一个(有条件的)匹配成功后,在局部的子树内,采用动态规划的算法,找出 这一子树的所有可能的变换结果,然后跳出这个子树,仍按自顶向下的顺序找下一个 子树继续处理.这种策略也能一次求出全部结果,但空间代价比前一种为省,不过在 全部处理完后,要多一次扫描将所有可能的变换结果组合出来. 6. 结束语 本文引入树型结构相容匹配的概念,并在对程序变换的过程作了深入分析的基 础上,提出三种适用的控制树型匹配----生成----替换的策略,比较了它们的优缺 点.限于篇幅对变换过程中变换模块参数实例化的处理,多个变换模块的表示类型之 间的强制转换,以及变换过程的优化策略等问题均未作详细讨论. 基于本文提出的三种策略的实验系统已同时投入运行,并用于布尔的整型表示, 栈的顺序表示,二叉树的链接表示,集合和包(bag)的链接表示等,正确完成了包括哈 夫曼算法和树的周游算法等在内的多个源程序的一系列变换. 本项研究得到国家自然科学基金的资助,杨芙清教授和系其他领导给于本项研 究许多鼓励和支持,许卓群教授,屈婉玲副教授在百忙中一直关心本项研究,并给了 许多具体指导和帮助,陈光,邹欣和汪洪燕同志在方案的讨论和实现中做了大量的工 作,系实验室的同志也给本项研究提供了许多方便,借此机会表示衷心感谢. 参考文献 [1] D.Knuth, J.Morris and V.Pratt Fast Pattern Matching in Strings Stanford Technical Report #74-440 August 1974 [2] R.Kowalski Predicate Logic as a Programming Language IFIP74, 569-574 [3] E.Horowitz, S.Sahni Fundamentals of Data Structures Computer Science Press 1976 [4] A.V.Aho, J.E.Hopcroft and J.D.Ullman Data Structures and Algorithms Addision_Wesley, Reading, 1985 [5] W.Chen and J.T.Udding Towards a Calculus of Data Refinement LNCS 375, Spring Verlag, NY 1989 [6] E.W.Dijkstra A Discipline of Programming Prentice Hall, Englewood Cliffs, New Jersey, 1976 [7] D.Gries and J.Prins A New Notion of Encapsulation Proc. SIGPLAN 85 Sympsium on Language Issues in Programming Environments, 1985 [8] D.Gries and D.Volpano The Transform--A new language construct Tech. Rpt. CS Dept. Cornell Univ. 1989 [9] D.E. Knuth The Art of Programming, Vol I, Fundamental Algorithms Addison_Wesley, Reading, 1963 [10] J.Prins Partial Implementations in Program Derivation Ph.d. Thesis, CS Dept. Cornell Univ, 1987 [11] 许卓群,张乃孝,杨冬青,唐世渭 数据结构 高等教育出版社 1987 [12] 张乃孝,侯世君 逻辑程序中的控制策略及其表示 北京大学学报(自然科学版) Vol.24 No.5 1988 [13] 张乃孝 程序变换在程序语言中的一种表示 软件学报 (即将发表)