第2章 元程序设计
2.1 元程序介绍
1．元程序概念
在现代程序设计中，程序已经取代数据成为操作对象，变得越来越重要。元级程序设计系统是一种对程序进行操作的有效工具，可用于各种元程序设计。其中，对程序进行处理的基本操作称为元级操作；实现元级操作的语言叫做元语言；所处理的语言叫做目标语言。
元程序（Meta Program）是可以操作目标程序（Object Program）的程序，它可以构造目标程序，也可以将目标程序段组合成更大的目标程序，还可以观察目标程序的结构和其他特性。目标程序是以形式语言书写的一些句子，如常见的高级语言程序等。
一般来说，元程序是处理程序的程序，如编译器、解释器、类型检查器、定理证明器、程序生成器、转换系统和程序分析器等。
2．元程序和元程序设计系统的分类
从功能上看，元程序可分为两大类：程序生成器和程序分析器。程序分析器关注目标程序的结构和环境，并计算出一些值作为结果。这些结果可以是数据流图或控制流图，或者是带有原目标程序属性的另一个目标程序。该类型元级系统的例子有程序转换、优化和部分求值系统等。而程序生成器则为了解决某一类具有相似解的问题，构造另一个可解决该类问题的程序（目标程序）。通常，生成的目标程序专用于一个特定的实例，这样比使用一个一般目的的、非生成的解决方案使用的资源更少。通常，元程序可以是
程序分析器、程序生成器，或者二者的混合体。
从元语言和目标语言的异同来看，元程序设计系统有两种截然不同的种类：元语言和目标语言相同的同类系统，元语言和目标语言不同的异类系统。两种系统对描述自动的程序分析和操作都是非常有用的，但相对于异类系统而言，同类系统具有更好的教学性和实用性，因为用户只需要学习一种语言就可掌握并操作整个系统。而且它还支持反射，能够提供n-level程序概念——一个n-level目标程序自身能够成为一个操作（n+1）-level的目标程序的元程序。然而，异类系统通常扮演更为重要的角色，带有固定的元语言元级系统，无论其构造的是每个系统都具有不同目标语言的多重系统，还是一个带有多重目标语言的单一系统，都非常具有实用价值。
3．元程序的使用
元程序设计为用户提供了很多便利。
1）性能。大多数元程序设计系统中的一个普遍的目标就是性能。元程序提供了这样一种机制，它允许用一种解释的形式书写一个多用途的程序，而不需要其他解释的辅助工具即可执行。显然，比起写一个多用途的但却低效的程序，写一个能够从一个规范生成一个高效结果的程序生成器要好很多。语法分析生成器YACC的使用就是一个非常鲜明的例子，我们可以从一个规范（即语言的文法）生成一个高效的分析器。
2）部分求值。部分求值是用于提高性能的另一种元级程序分析技术，通过对程序输入的部分信息的例化优化该程序，目的是在程序运行之前，识别并执行尽可能多的计算。
3）解释。元程序最普遍的用途就是从一个目标程序到另一个目标程序的解释。源语言（Source Language）和目标语言（Target Language）可以相同也可以不相同，如编译器和程序转换系统。
4）推理。元程序的另一个重要用途就是关于目标程序的推理。由于目标程序是以形式语言书写的句子，因此通过分析能够发现该程序的一些特性。利用这些特性，可以提高目标程序性能，为目标程序的行为提供保障。推理元程序的例子，如各种流分析和类型检查的程序分析。此外，推理元程序还用于构造定理证明系统，如LEGO、HOL、Coq、Isabelle等；逻辑框架的研究与实现，如Elf、Twelf、LF等。
5）移动代码。元程序已逐渐成为程序传送的一种重要手段。不同于以前使用网络传送数据给程序，目前，程序已经成为网络的传输对象。但由于安全的原因，网络传输的内容往往是程序的内在表示，为了确认传送程序的安全性和保险性，需要对其进行分析。这些被传送的程序是目标程序，对传送程序进行分析的是元程序。
4．元程序的应用领域
元程序设计已经出现一段时间，但作为一个正式的研究领域，它才仅仅活跃了十几年。下面是一些领域的概述：
1）表示程序。目标程序是数据，更是复杂的实体。在表示它们时，我们需要隐藏一些不必要的细节，使重要的部分更加明显，并且让一般操作容易被表达和有效实现。
2）表示形式。表示形式是元程序设计系统提供给程序员的到目标语言的接口。表示形式对于一个系统的可用性有着极其重大的影响。后面讲到的树形表示和抽象语法树表示分别为过程式和对象式元程序设计系统提供了有效的表示形式。
3）代码结构的观察。将代码表示为数据有很多种技术，其中大多数是将代码构造成一个抽象类型，目的是为了支持代码的双重性或为其提供一个更为有用的表现形式。由于这样的表现形式隐藏了代码的内部结构，因而如果这些代码需要被拆析或观察的话，必须另外提供某个可以对该代码内部结构进行访问的接口。因此，如何得到这样一个既易于使用，又能够反映用户对于目标代码逻辑结构的接口，是元程序设计中的研究要点。
4）操作绑定结构。许多目标语言包含绑定结构——用于引入并描述局部变量的作用域。就元程序而言，这些变量的实际名字都是不重要的，任何一个合法的名字，只要保持其使用方式一致，都可以被使用。但在元程序设计中，我们通常会遇到这样的问题：生成程序时需要创造一些新的名字，这些名字必须要保证与已经存在的名字不同，否则将会覆盖原有变量的作用域。可见，在程序分析中，必须要注意并处理某些发生概率极小的情况。因此，在处理带有绑定结构的目标语言时，我们面临的问题是：当拆析某一程序时，如何才能确保局部变量不会脱离其作用域而变得没有约束？
5）异类元程序设计系统。在目标语言和元语言不同的异类系统中，我们能做些什么呢？可以说，异类系统给整个元程序的研究带来了新的挑战。其研究的难点在于，在异类系统中，对于每一个目标语言都需定义一套与之对应的类型系统，如果元程序的类型要涉及一些它所产生的目标程序的类型，那么必须将目标语言的类型系统嵌入到元语言的类型系统中。而目标语言的类型系统以何种方式相容或相似于元语言的类型系统是无法保证的，因此，两种类型系统可能是不相适应的。例如，当元语言是多态的lambda演算，而目标语言是Cardelli的对象演算时，一个简单的嵌入通常都是行不通的。
6）元程序理论。只有当我们掌握了希望构建的系统的支撑理论后，才有可能构造一个可靠的系统。由于元程序中包含了很多在一般程序设计中没有的与复杂语义相关的“困难”，因此，一套好的元程序设计系统理论必须要足够丰富，才能解决这些问题并且理解这些复杂的语义。有好的理论才能有好的工具。
在后面的章节中，我们将介绍上述领域中较为基本的表示形式在元程序设计系统中的重要应用及其实现手段。
