程序变换过程的分析与设计*


                            张 乃 孝

               （北京大学计算机科学系  北京 100871）

                     ANALYSES AND DESIGNS FOR
              THE PROCESS OF PROGRAM TRANSFORMATION

               Naixiao Zhang  ( Peking University )


ABSTRACT

   In this paper, the process of program transformation introduced by
transformational  languages  is analysed. The  concept of“consistent
attributes*is proposed to define the pattern matching in this process.
Some  algorithm framworks  used to implement the process are given in
the later part of the paper.

KEYWORDS : Program transformation, Transformational language,
           Pattern matching,       Consistent attributes.

摘要

    本文讨论了用变换型语言描述的程序变换过程，重点分析了这一过程中的*
模式匹配问题, 引入属性相容匹配的概念，并在此基础上，给出了实现变换过
程的几种算法框架。

关键字 : 程序变换, 变换型语言，模式匹配, 属性相容。








* 本项研究得到国家自然科学基金和863-306主题的资助。
  张乃孝，教授，目前主要从事程序设计方法学与新型语言的研究。



娗把*

    程序变换的算法研究是实现变换型语言及其开发环境的关键. 本文以 [1]
中定义的“变换模块”和“变换控制命令”为背景, 分析了程序变换的实现过
程, 引入属性相容匹配的概念, 并成功地把它用于对程序变换过程的描述, 给
出了几种控制变换的算法框架.

§1 变换过程的初步分析

    (1)  不确定性
    从文 [1]中Bool-Int变换的例子可以看出在变换处理的过程中存在不确定
性, 其主要表现在两个方面:第一,变换时选择源程序中哪个成分先进行处理是
不确定的;第二,变换时选择模块中哪条规则先进行匹配也是不确定的.
    (2)  多解性
    由于不确定性,便产生多解性.这种多解性为变换的实现提出了更高的要求,
例如什么是较好的解,如何求得较好的解,以及能否求出全部解等等.
    (3)  表示规则的作用
    表示规则提供了抽象类型表达式和它的具体表示之间的关系. 使用表示规
则可以从操作对象的具体表示直接构造出操作结果的具体表示, 而这种表示是
使用重写规则和置换规则实现变换的前提。抽象类型上的运算主要靠表示规则
来实现, 引入表示规则使变换模块的定义更加简洁（参看[1]）。

§2 与逻辑语言解释过程的比较

    虽然程序变换的处理过程从总体上讲类似于逻辑型语言prolog的解释执行
过程(参考[2]). 但是也有明显的差别:

    (1) 在prolog中规则(和事实)未被分类, 更不存在表示规则所带来的麻烦,
所以处理比较简单。
    (2) 在prolog中使用消解原理进行一步推理时, 为了判断某规则(或事实)
能否与某一(子)目标匹配, 采用了合一置换, 这种处理本质上是一种形式上的
变量换名, 具体匹配时, 只要看置换后的两个“字符串”是否相等即可。而在
变换型语言中, 无论抽象程序还是规则的左(右)部都是一种树形结构, 规则中
的抽象变量, 一般总是与抽象程序中的一个(树形)子表达式匹配, 所以在变换
时所考虑的是更一般的“树形结构”上的匹配问题。
    (3) 在程序变换过程中不仅要考虑语法的匹配问题, 还必须考虑许多非语
法的属性。例如, 由于运算符的重载和类型的多态性在考虑匹配时不能仅考虑*
语法上的一致性，还必须考虑语义上的“相容性”。

§3 树形结构的属性相容匹配

    现在我们就来进一步分析在实现程序变换时要考虑的主要属性及判断这些
属性相容的条件。

  3.1 结点的属性

    在下面的讨论中,我们将变换的源程序 T 按其语法结构自然地表示为一棵
树,一个变换规则 Pi 也用同样的方法表示为一个树的偶对,记为(Pil,Pir),其
中Pil表示规则Pi的左部,Pir表示规则Pi的右部. 为了判断规则Pi能否用于对T
的某子树t的变换,首先要用Pil作为模式与t进行匹配. 对树中的每个结点我们
定义以下“属性”:

  (1) 结点的语法性质
    对于每个内部结点,可自然地与一个语法的非终结符对应,而模式中的叶结
点则可以代表一个终结符(例如常数),也可以代表一个非终结符(例如表达式).
  (2) 结点的种类(kind)
    在我们讨论的语言中, 一个结点可以属于以下不同的种类: id, var, exp
和 stmt.
  (3) 结点的类型(type)
    代表常量,变量,表达式以及函数的结点都具有类型的属性.
  (4) 变量结点的其他属性
    对于表示变量的结点, 我们特别关心的是这个变量在模式中是否要变换的
抽象变量, 以及是提供地址(也称左值)的变量,还是提供值的变量等等.

  3.2 相容条件

    为了描述程序变换过程中所要求的匹配,我们引入“属性相容”的概念.一
个模式Pil中的结点np与目标t中的结点nt属性相容的含义如下:

  (1) 语法结构一致
    若np为内部结点代表非终结符,则nt只能是相同的内部结点;若np为叶结点
代表非终结符（包括抽象变量）,则nt可以为一个内部结点也可以为叶结点;若
np为叶结点代表终结符,则nt只能为相同的叶结点.
  (2) 关于种类的相容
    原则上某一种类的结点只能与同种类结点匹配,但表示exp的np可以与表示
var的nt相容,而表示抽象变量的np又可以与表示exp的nt相容.
  (3) 关于类型的相容
    np的类型必须是nt的超类型或者nt的类型可以通过强制(coercion)转换成
np类型的子类型.
  (4) 关于变量的其它相容
    表示抽象变量的np与nt匹配时要求已知nt(变量或表达式)的具体表示. 表
示左值的变量np只能与表示左值的变量nt相容.

  3.3 匹配、生成和一步变换

    根据属性相容的含义, 我们可以定义模式树P与目标树T在 t(t∈T)处匹配
(成功),如果对所有P中与非终结符对应的叶结点存在一组属性相容的子树, 使
得用这些子树对P作合一替换便得到t。

    若某表示规则左部Pil与源程序T中某子树t相容匹配成功, 根据匹配信息,
可以按该规则右部Pir的结构生成t的一个表示子树t′,生成的方法是:

  (1) Pir中的表示变量, 用与之对应的(Pil中的)抽象变量属性相容的子树的
表示形式来置换.
  (2) Pir中其它非终结符的叶结点(也是Pil中的非终结符的叶结点)用与之对
应的子树置换.

    若匹配使用的是置换规则或重写规则,则用上述方法生成的是一个与t等价
的语句或表达式 ,记作t′,用t′代换t便完成将源程序树T变成T′的一步变换,
记为 T′≡ T(t\t′).

§4 程序变换的算法框架

    变换过程的控制主要包含两个方面,一是选择变换规则的策略,二是选择目
姳曜邮鞯牟呗*.

  4.1 变换规则的选择

  （1） 分类控制：即将变换模块中的规则按不同类(表示规则,重写规则和置
换规则)分组,根据不同的目标子树选择不同规则.
  （2） 高度控制：即将变换规则按Pil的高度排序,高者优先匹配.
  （3） 优先级控制：即通过用户给规则一定的优先级说明或隐式地按规则出
现的顺序理解其优先级.

  4.2 目标子树的选择

  4.2.1 自顶向下的回溯算法

    从源程序树T的根结点开始, 按先根顺序依次取一个子树t与一个重写规则
或置换规则左部Pil匹配,结果有三种可能:

  (1) 匹配失败,则取下一个规则与这个子树匹配.
  (2) 匹配成功,则用匹配信息,根据Pir生成实例化的子树t′,并用它置换T中
t得T′,然后继续按先根次序处理.
  (3) 有条件的匹配成功,这种情况来自于与Pil中的抽象变量相容的子树要求
有相应的具体表示,而T中与之相应的子树还未处理,所以需要进入相应子树,用
表示规则与之匹配,可得到相应表示,然后才确认本匹配成功,执行与(2)中相同*
工作.

    这种算法思想朴素,回溯自然, 但每次只能得到一个变换结果,若要得到所
有结果必须进行回溯,时间代价较高.

   4.2.2 自底向上的动态规划算法

    这是一种企图同时求得所有变换结果的策略.它从源程序树的叶结点开始,
按后根顺序依次取一个子树与各个规则匹配, 对代表表达式的子树首先考虑各
表示规则,得到所有可能的表示形式,然后再考虑重写规则,对代表语句的子树,
仅需考虑置换规则. 这种算法在处理每个子树时,这个子树的所有真子树均已处
理完毕, 并且将它们所有可能的表示形式和变换结果均保存在有关文件中, 为
此可能要付出较大的空间代价.

   4.2.3 自顶向下与自底向上的结合算法

    先用自顶向下的策略, 待找到一个有条件的匹配成功后,在局部的子树内,
采用动态规划的算法找出这一子树的所有可能的变换结果,然后跳出这个子树,
仍按自顶向下的顺序找下一个子树继续处理.这种策略也能一次求出全部结果,
但空间代价比前一种为省, 不过在全部处理完后,要多一次扫描,将所有可能的
变换结果组装出来.


后记

    本文首次提出树形结构上属性相容的匹配概念, 并用它成功地描述了程序
变换中规则的匹配问题. 从本质上讲属性相容的概念已超出语法范畴, 因为它
不仅要考虑语法属性, 同时也要考虑语义和语用属性的要求。由于对不同问题
可以考虑不同的属性及其具体的相容条件, 因此这一概念有可能应用到许多复
杂的智能问题中去.


参考文献

[1] 张乃孝  程序变换在程序语言中的一种表示
    软件学报 1993年 第三期
[2] 张乃孝  知识结构的三叉树表示和逻辑推理的实现
    计算机学报 Vol.13 No.1 1990