Lisp 系的语言比起编程更像数学一点——过程是名副其实的「函数」表达式，程序的运行是在对其求值；整个程序可以按照求值的代换模型展开成一棵树。从这个角度来编程解决问题，不考虑变量和循环之类的，是一种全新的思路；比如对过程定义产生的新理解。

问题

《计算机程序的构造和解释》中的 1-28 题为了使用 Miller-Rabin 检验来确定数 $n$ 是否是素数，要求修改之前使用过的，用于计算 $base^{exp} \bmod m$ 的递归过程 expmod ：

(define (expmod base exp m)
    (cond
        ((= exp 0) 1)
        ((even? exp)
            (remainder
                (square (expmod base (/ exp 2) m))
                m
            )
        )
        (else
            (remainder
                (* base (expmod base (- exp 1) m))
                m
            )
        )
    )
)

这个过程在 exp 为奇数时将结果乘以 base， exp 为偶数时对结果求平方；求平方的方法使得它计算同余幂只需要 $\log m$ 的步骤。

修改这个过程，使其在求平方的步骤中检查是否遇到了「 $1 \bmod n$ 的非平凡平方根」，即是否

$$\exists x (x \neq 1 \land x \neq n - 1 \land x ^ {2} \equiv 1 \pmod m)$$

若上式对某一 $x$ 成立，那么 $m$ 就不是素数；若在任一时刻找到了这样的平方根，过程应当返回 0 ，否则返回 $base^{exp} \bmod m$ ．

变量

很容易就能写出满足上面的条件的、递归的 C 语言函数：

int expmod (int base, int exp, int m)
{
    if (exp == 0) {
        return 1;
    } else if (exp % 2 == 0) {
        int r = expmod (base, exp / 2, m);
        int x = (r * r) % m;
        if (r == 1 || r == m - 1) {
            return x;
        } else {
            if (x == 1) {
                return 0;
            } else {
                return x;
            }
        }
    } else {
        return (expmod (base, exp - 1, m) * base) % m;
    }
}

在上面的函数中，一个很重要的部分就是使用了变量 r 和 x 来保存递归返回的结果 。如果不保存，就需要多次调用函数。

如果在 Scheme 中，不使用中间变量而只考虑代换求值，会得到下面的树：

上图的过程在所有需要的地方都重新递归调用了所需的过程，这导致了在指数 exp 为偶数的分支上，有一棵子树 remainder 被反复求值。图中在条件判断过程中求值的 remainder 子树被标为蓝色，在结果计算过程中求值的 remainder 子树被标为红色。

remainder 子树的反复求值增加了递归函数的时间复杂度：一个函数要调用自身 7 次，这是不可接受的。在 C 中这个函数只被调用了一次，在此之后用变量存储它的返回值以便继续使用。但是如果不使用变量呢？

过程定义

Scheme 给出的解法是，在所有重复的 remainder 子树的公共祖先上，将它的后代重新定义为过程；这个新定义的过程作为原来的 expmod 的参数，而递归调用的 expmod 作为这个新定义的过程的参数。例如，将公共祖先 (even? exp) 结点的下方的分支定义为过程 get-result（这个过程可以理解为当 exp 为偶数时，取得所返回的结果），而 remainder 子树的值作为传给 get-result 过程的参数 r：

通过这种方式，改写后的 expmod 是这样的：

在这个 expmod 中，由于调用了 get-result ，使得 remainder 子树的求值次数从 7 次变回了 1 次。这就是「过程定义」的解法。

这样的方法还可以继续使用，比如在 get-result 中求值了两次的remainder 和 square 过程，可以通过再重新定义过程 test（测试平方是否与 1 同余）来优化。

如果一个程序意义上的函数调用只允许传参数，而不在函数内部定义变量或更改变量的值（与此同时也禁用了循环——因为循环要求「状态」的改变），那它就类似数学意义上的函数：传入参数的类型是函数的定义域，返回值的类型是函数的值域。类似 if 和 cond 的条件选择则是对输入进行分段。函数调用的嵌套只不过是复合函数而已。

附录

正经解法的 Scheme 代码（使用我流括号缩进）：

(define (expmod base exp m)
    (define (get-result r)
        (define (test x)
            (if (= x 1)
                0
                x
            )
        )
        (cond
            ((= r 0) 0)
            ((or (= r 1) (= r (- m 1)))
                (remainder (square r) m)
            )
            (else
                (test
                    (remainder (square r) m)
                )
            )
        )
    )
    (cond
        ((= exp 0) 1)
        ((even? exp)
            (get-result
                (expmod base (/ exp 2) m)
            )
        )
        (else
            (remainder
                (* base (expmod base (- exp 1) m))
                m
            )
        )
    )
)

如果人们学习 Lisp 系的障碍只是括号堆一起看着烦的话，让它们不要堆一起就可以了