考虑这个非常简单的问题. 你想要定义一个函数来判定一个给定字符串是否是一个回文. 一个回文是一个自左向右读和自右向左读相同的字符串. 存在两种显然的方式可以使得这个定义更加精确. 第一种方式是定义一个反转字符串的过程, 然后将反转的字符串和初始的字符串进行比较. 显然, 以这种定义为基础的算法不会是最高效的. 如果一个字符串以一个不同于开头字符的字符作结, 那么它肯定不是回文, 而这种定义无需反转即可建立. 因此, 我们将采取这另外的定义, 其可以写成通常的数学形式:
让我们称想要定义的函数为Pal, 并且当参数是回文时取True值, 否则的话则取False. Refal中的定义紧贴数学定义:
Pal { = True;
s.1 = True;
s.1 e.2 s.1 = <Pal e.2>;
e.1 = False; }这个程序以函数名开始, 后面跟着由括号括起的块. 一个块是一列由分号隔开的句子. 在我们的这种情况下块有着四个句子, 分别对应于以上由文字描述的数学定义的每个分句. 每个句子都是一个替换规则. 其左边代表函数的参数的模式; 而由相等符号=隔开的右边, 则是对于函数调用的替换.
第一个句子里, 函数Pal的参数为空(字符串), 因而值必然为True.
第二个句子里, 参数以一个符号的自由变量s.1的形式给出. 其匹配任意的符号, 例如一个字符, 但只是一个符号. 因此, 这个句子应该读作: 如果参数是一个单独的符号, 那么将调用替换为True.
第三个句子代表的情形是参数以某个符号s.1开头和作结, 并且表达式e.2夹在中间. 表达式是Refal中最一般的数据结构; 具体地说, 它可以是一个符号的串. 这个句子的右边是以e.2为参数的对于函数Pal的调用. 我们使用圆括号来创建数据结构, 但是尖括号用来表示函数调用. <Pal e.2>在数学上的类似记号为.
最后一个句子的参数是一个任意的表达式 (字符串). Refal中的函数定义里的每个句子只会在前述句子均不可应用时才会使用, 因此最后一个句子应该读作: 如果以上均不可行, 那么不论什么参数, 这个函数调用的值应该是False.
Refal程序的算法意义的精确定义是通过定义执行Refal程序 (即对于定义在Refal里的函数求值) 的抽象Refal机器完成的 (见第1.5节). Refal机器按步骤运行, 每一步都是应用一个句子. 例如, 如果利用Refal机器以参数'revolver'调用Pal, 即对于<Pal 'revolver'>求值, 那么Refal的工作空间 (我们称之为view field) 将会经历以下阶段:
<Pal 'revolver'>
<Pal 'evolve'>
<Pal 'volv'>
<Pal 'ol'>
False现在我们开始系统地定义Refal. 对于语言句法的总结也作为参考手册的B部分附于末尾.
Refal中的符号是数据结构的最小句法元素. 我们使用以下种类的符号:
字符以单引号围住, 例如'a'和'+'. 一串字符被引号围成一个整体. 因此, 'a+b'是由三个符号构成的一个序列: 'a', '+'和'b'. 一个串可能仅包含零个字符, 即''. 这是一个空表达式, 代表什么都没有, 但它当然不是一个符号.
Mu