5 添加函数

下面尝试将其变成真正的语言。比如说可以添加诸如条件语句这个特性，但是一个语言要真正变得有意思，它需要函数或者某种等价于函数的东西。所以我们就直接来添加函数好了。

练习

给语言添加条件语句。你可以选择添加布尔类型，或者方便起见，你的条件语句可以将0视作false，其他值视作 true。

想象一下，我们要构造一个类似于DrRacket的系统。程序员在定义（definitions）窗口中定义函数，然后在交互（interactions）窗口中使用它们。我们先假设函数只能在定义窗口定义；交互窗口中只能出现表达式（这些限制会随着内容的深入被解除）。按此假定，当运行程序时，函数已经被解析可供使用。所以，我们给解释器添加一个参数——函数定义的集合。

注意这里我们说的是函数的集合，也就是说，任何函数的定义中可以引用任意其它函数。这是我有意的设计。当你设计自己的语言时，记住注意考虑这一点。

5.1 定义函数的数据表示

简单起见，我们仅考虑只有一个参数的函数。下面是一些Racket函数的例子：

(define (double x) (+ x x))

(define (quadruple x) (double (double x)))

(define (const5 _) 5)

练习

如果函数可以带有多个参数呢？参数名之间有什么限制？

函数的定义包含哪些内容？它包含名字（上文中的double，quadruple，const5），我们将使用符号（symbol）类型表示（'double等）；形参（formal parameter，形式参数的简写）（例如x），也使用符号类型表示（'x）；最后还有函数体。我们后面会一步一步完善函数体的表示法，现阶段函数定义的数据类型如下：

<fundef> ::=  ;函数定义

    (define-type FunDefC
      [fdC (name : symbol) (arg : symbol) (body : ExprC)])

所以函数体是什么呢？显然它可以是算术表达式，且有时候应该可以使用ArithC语言来表示：例如，函数const5的函数体可以使用(numC 5)表示。但是要表示double函数的函数体需要更多东西：不仅需要加法（我们已经定义了），还需要“x”。你可能会称它变量（variable），但是现在我们不使用该术语，我们叫它标识符（identifier）。

后文我还会进一步解释这两个命名。

思考题

还有别的吗？

最后，我们看看quadruple的函数体，它包含另一种结构：函数调用（application）。要特别注意函数定义和调用的区别。函数定义描述了函数是什么，而调用则是对函数的使用。里面一层的double 函数调用使用的实参（actual parameter，实际参数的简写）是x；外面的那层的double调用使用的参数是(double x)。可以看到，参数可以是任意表达式。

下面我们尝试把上面所有的东西糅合到一个数据类型中。显然我们需要扩展已有的语法（因为我们还想保留算术运算）。我们给新的数据类型一个新名字以示区别：

<exprC> ::=  ;表达式

    (define-type ExprC
      [numC (n : number)]
      <idC-def>  ;标识符的定义
      <app-def>  ;调用的定义
      [plusC (l : ExprC) (r : ExprC)]
      [multC (l : ExprC) (r : ExprC)])

标识符与形参关系紧密。当调用函数时，我们传给它某个值，从效果来说是将函数体中出现的形参实例——所有同名标识符——替换为该值。【注释】为了简化这个搜索——替换过程，不妨使用与形参相同的数据类型来表示标识符。形参的数据类型已经定好了，于是：

<idC-def> ::=  ;标识符的定义

    [idC (s : symbol)]

这里我们忽略了几个问题：“值”是什么？何时替换？后文会继续讨论。

最后，函数调用。它包含两个部分：函数名和（实际）参数。上面已经说过参数可以为任意表达式（包括标识符和函数调用）。至于函数名，让其和函数定义中的函数名类型一致符合直觉，就这样做吧：

<app-def> ::=  ;调用的定义

    [appC (fun : symbol) (arg : ExprC)]

该定义简单明了，函数名指明要调用哪个函数，然后后面提供函数调用所需参数。

有了定义，看看之前的三个函数该怎么表示：

• (fdC 'double 'x (plusC (idC 'x) (idC 'x)))
• (fdC 'quadruple 'x (appC 'double (appC 'double (idC 'x))))
• (fdC 'const5 'x (numC 5))

下面还需要选择函数定义集合的表示法。使用链表类型就蛮方便。

小心！你有没有注意到，之前我们说这是函数定义的集合，然而实现却选用了链表。也就是说，我们用有序的数据结构去表达无序的数据。那么，测试时，至少我们应该试用各种不同顺序的函数定义，以确保我们没有不小心引入了（影响结果的）顺序。

5.2 开始实现解释器

于是我们可以开始实现解释器了。首先考虑解释器的输入是什么。之前，只需要传入一个表达式即可，现在它还需要传入函数定义的表。

<interp> ::=  ;解释器

    (define (interp [e : ExprC] [fds : (listof FunDefC)]) : number
      <interp-body>)  ;解释器主体

稍微回顾一下我们前面实现的解释器（第三章）。遇到数，显然还是直接返回该数作为结果；遇到加法和乘法，还是应该一样递归的求值。递归时该用什么作函数定义呢？由于求值过程中，既不需要添加也不需要移除函数定义，即函数定义集合保持不变，在递归时函数定义应该原封不动的往下传递。

<interp-body> ::=  ;解释器主体

    (type-case ExprC e
      [numC (n) n]
      <idC-interp-case>  ;解释之标识符子句
      <appC-interp-case>  ;解释之调用子句
      [plusC (l r) (+ (interp l fds) (interp r fds))]
      [multC (l r) (* (interp l fds) (interp r fds))])

接下来实现函数调用。首先我们需要从函数定义中寻找对应的函数定义，我们可以假设如下的帮助函数可以实现此功能：

; get-fundef : symbol * (listof FunDefC) -> FunDefC

假设我们已经找到了函数的定义，下一步要对其函数体求值。还记得之前说过函数调用该怎么求值？搜索标识符并将其替换为实际参数。这个搜索替换过程足够重要，值得花一小节讨论，5.4节我们再回过来实现解释器。

5.3 替换

替换是将一个表达式（这里是函数体）中某个名字（这里是形参）替换成另一个表达式（这里是实参）的过程。首先确定其类型：

; subst : ExprC * symbol * ExprC -> ExprC

将参数名起的有意义些：

<subst> ::=  ;替换

    (define (subst [what : ExprC] [for : symbol] [in : ExprC]) : ExprC
      <subst-body>)  ;替换函数的主体

在in表达式中，将for替换成what。

思考题

考虑之前几个示例函数的函数体，将参数x替换为3的结果是什么？

对于double函数来说，结果为(+ 3 3)；对于quadruple，结果为(double (double 3))；对于const5，结果就为5（函数体中没有出现x所以也没有替换）。

对于double一个常见的错误是将其替换成(define (double x) (+ 3 3))。替换发生在函数调用时，此时只需要函数体就可以了。函数定义头部的作用是找到函数，还有给出参数的名称；但是计算其值时只需要函数体。如果用整个函数定义进行替换，试试看你会得到哪种类型错误。

这个例子几乎涵盖了所有情况。如果是数的话，无需替换任何东西；如果是标识符，例子没有覆盖标识符不同的情况，你也能想到该怎么做：保留之；其它情况，递归的替换各子表达式。

在开始写代码之前，还有一种重要情况要考虑一下。假设我们要替换的标识符恰巧是某个函数名称，该怎么处理呢？

思考题

该怎么处理呢？

对于这个问题，有多种处理方法。一种方案是从设计上来来考虑：函数名有其自己的“世界”，它和程序中其它标识符都不同。某些语言（例如C和Common Lisp，尽管它们的做法也略有不同）采取这种策略，根据标识符使用的位置将其解析到不同的命名空间。而其他一些语言则不做这样的区分。我们很快会研究这么一种语言（后文）。

现在，我们从务实的角度来处理这个问题。由于这里表达式求值结果是数，这就要问函数名能求值成数不。但是，数不能命名函数，只有符号能。所以进行这种替换是没有意义的，函数名和要替换的符号没有关系。（比如，某个函数的参数可以叫x，其函数体中又可以调用另一个名为x的函数，两者被区别处理。）

决定做完了，是时候写代码了：

<subst-body> ::=  ;替换函数的主体

    (type-case ExprC in
      [numC (n) in]
      [idC (s) (cond
                 [(symbol=? s for) what]
                 [else in])]
      [appC (f a) (appC f (subst what for a))]
      [plusC (l r) (plusC (subst what for l)
                          (subst what for r))]
      [multC (l r) (multC (subst what for l)
                          (subst what for r))])

练习

请注意，在numC子句，解释器返回n，而替换函数返回in（即原始表达式，在这个位置等价于(numC n)）。为什么？

5.4 继续实现解释器

搞定了替换的实现（我们这么认为），我们来完成解释器。替换这步干了很多事，好在函数调用的很多细节都在其中完成了。很自然的想法是：

<appC-interp-case-take-1> ::=  ;解释之调用子句，第一次尝试

    [appC (f a) (let ([fd (get-fundef f fds)])
                  (subst a
                         (fdC-arg fd)
                         (fdC-body fd)))]

但是这是错的。

思考题

看出错在哪里了吗？

从类型角度考察，解释器的函数返回类型是什么？数。替换函数的返回类型呢？表达式。比如说，在替换double的函数体是，可能得到的结果是(+ 5 5)的表达形式。这并不是解释器的合法返回值。需要进一步对其求值。所以应该这么做：

<appC-interp-case> ::=  ;解释之调用子句

    [appC (f a) (let ([fd (get-fundef f fds)])
                  (interp (subst a
                                 (fdC-arg fd)
                                 (fdC-body fd))
                          fds))]

好了，还剩下最后一个子句：标识符。这个能有多复杂呢？看上去标识符类似数那样简单！然而我们把它留到最后处理，这说明到了它的处理可能有点微妙或者说有点复杂。

思考题

请尝试一些例子，从而理解标识符该怎么处理。

假设double函数定义如下：

(define (double x) (+ x y))

我们把x替换成5，得到(+ 5 y)。没毛病，然而剩下的y该怎么替换呢？事实上从一开始我们就应该意识到这个double定义是错误的。标识符y被称为自由的（free），这是个负面的词。

换一种说法，解释器应该永远也遇不到标识符。在解释过程中，所有标识符应该都会被替换掉（被称为被绑定的，这是种正面的说法）。因此，当解释器直面标识符时，只能这么处理：

<idC-interp-case> ::=  ;解释之标识符子句

    [idC (_) (error 'interp "shouldn't get here")]  ;不应执行到这里

这样我们的解释器就完成了！

最后，为了完整，我们还需要实现get-fundef：

;获取函数定义
(define (get-fundef [n : symbol] [fds : (listof FunDefC)]) : FunDefC
  (cond
    [(empty? fds) (error 'get-fundef "reference to undefined function")]  ;引用未定义的函数
    [(cons? fds) (cond
                   [(equal? n (fdC-name (first fds))) (first fds)]
                   [else (get-fundef n (rest fds))])]))

5.5 等等，还没完呢！

之前subst的类型我们说是：

; subst : ExprC * symbol * ExprC -> ExprC

简单起见我们这里用表面语法描述问题，假设我们在解释(double (+ 1 2))。它会将所有x都替换为(+ 1 2)，于是解释器得到表达式(+ (+ 1 2) (+ 1 2))。这是我们想要的吗？

在学习代数时，可能你的老师不是这么教你的：首先应该将参数规约成其结果（在这个例子中就是3），然后将参数替换为这个结果。这么说，替换的类型就应该是：

; subst : number * symbol * ExprC -> ExprC

请注意，我们不能直接把数放入表达式，而是必须先把数放入到numC调用中。所以，一种可行的做法是，subst函数可以把第一个参数用numC包装起来然后调用辅助函数。（事实上，现有的subst函数就可以是这个辅助函数：它接收的第一个参数的类型是ExprC，那么当传给它的数据是numC类型时显然没问题。）

事实上，替换的实现还是不太对！这里的替换函数仅仅能处理我们的示例语言，过了就不行了。这给问题也很微妙，它被称为“名称捕获”。解决这个问题是复杂，巧妙和令人兴奋的智力工作。不过这里我不打算往这个方向发展。所以本书中我们绕过此问题。不过如果你对此感兴趣，请阅读lambda演算方面的书籍，它们会提供帮助正确地实现替换。

练习

修改解释器，用答案而不是表达式替换标识符。

我们这里遇到的问题正是程序语言中一个基本设计抉择。如果在替换前就把参数的值求好，这被称为及早（eager）求值；对应的推迟求值被称为惰性（lazy）求值——它本身又有几种不同变化。我们这里倾向于使用及早求值语义，因为大部分主流语言都采取此方式。后面也会再介绍惰性求值的语义和后果。