Question

lambda 演算表达式完全由 procs 的创建和调用组成，部分递归函数与其大致相同，由四个部分组合构成。前两部分叫作 zero 和 increment，我们可以使用 Ruby 实现它们。

def zero
  0
end

def increment(n)
  n + 1
end

这两个方法很直观，分别返回数字 0 和往一个数字上加 1：

>> zero
=> 0
>> increment(zero)
=> 1
>> increment(increment(zero))
=> 2

下面使用#zero 和 #increment 来定义一些新方法：

>> def two
    increment(increment(zero))
  end
=> nil
>> two
=> 2
>> def three
    increment(two)
  end
=> nil
>> three
=> 3
>> def add_three(x)
      increment(increment(increment(x)))
  end
=> nil
>> add_three(two)
=> 5

第三个方法 #recurse 更为复杂：

def recurse(f, g, *values)
  *other_values, last_value = values

  if last_value.zero?
    send(f, *other_values)
  else
    easier_last_value = last_value - 1
    easier_values = other_values + [easier_last_value]

    easier_result = recurse(f, g, *easier_values)
    send(g, *easier_values, easier_result)
  end
end

方法 #recurse 用两个方法的名字 f 和 g 作为参数，并且使用它们对一些输入值执行递归计算。根据最后的输入值，调用 #recurse 的直接结果是通过委托给 f 或者 g 计算得出的。

· 如果最后的输入值是零，#recurse 把其他值作为参数，调用名为 f 的方法。

· 如果最后的输入不是零，#recurse 使其递减，并用修改之后的输入值作为参数调用自身，然后用那些相同的值和递归调用的结果调用名为g 的方法。

这听起来比实际复杂；#recurse 只不过是定义某种递归函数的模板。比如，我们可以用其定义一个函数 #add，这个函数带有两个参数 x 和 y，它把它们加到一起。为了使用#recurse 构建此函数，我们需要实现两个其他的函数，以回答下面这些问题。

· 给定 x 的值，add(x, 0) 的值是多少？

· 给定x、y-1 和 add(x, y-1) 的值，add(x,y)的值是多少？

第一个问题简单：一个数字加零不会有变化，所以如果我们知道 x 的值，add(x, 0) 的值将是相同的。我们可以将其实现为一个叫 #add_zero_to_x 的函数，这个函数只返回它的参数：

def add_zero_to_x(x)
  x
end

第二个问题要难一点，但是回答起来仍然足够简单：如果已经有了 add(x, y-1) 的值，我们只要将其递增就能得到 add(x, y) 的值4。这意味着需要一个能增加其第三个参数值的函数（#recurse 用x、y-1 和 add(x, y-1)作为参数来调用它）。我们管这个函数叫#increment_easier_result：

4因 为减法是加法的 逆 运 算， 所以(x+(y-1))+1=(x+(y+-1))+1。 因为加法的结合律，所以(x+(y+-1))+1=(x+y)+(-1+1)。而因为-1+1=0，这在加法中是恒等式，所以(x+y)+(-1+1)=x+y。

def increment_easier_result(x, easier_y, easier_result)
  increment(easier_result)
end

把这些放到一起我们就得到了#add 的定义，它由#recurse 和 #increment 构造出来：

def add(x, y)
  recurse(:add_zero_to_x, :increment_easier_result, x, y)
end

第 6 章的思路同样适用于这里：为了给表达式取方便的名字，我们只使用函数的定义，而不会偷偷地递归进它们5。如果想要写一个递归函数，我们需要使用 #recurse。

5当然 #recurse 本身的实现从根本上使用了递归方法的定义，但这是允许的，因为我们是把 #recurse当成系统的 4 个内建原语而不是用户定义方法来处理的。

来确认一下#add 在做它该做的事情：

>> add(two, three)
=> 5

看起来很好。我们可以用同样的策略来实现其他熟悉的例子，比如 #multiply...：

def multiply_x_by_zero(x)
  zero
end

def add_x_to_easier_result(x, easier_y, easier_result)
  add(x, easier_result)
end

def multiply(x, y)
  recurse(:multiply_x_by_zero, :add_x_to_easier_result, x, y)
end

还有 #decrement：

def easier_x(easier_x, easier_result)
  easier_x
end

def decrement(x)
  recurse(:zero, :easier_x, x)
end

还有 #subtract：

def subtract_zero_from_x(x)
  x
end

def decrement_easier_result(x, easier_y, easier_result)
  decrement(easier_result)
end

def subtract(x, y)
  recurse(:subtract_zero_from_x, :decrement_easier_result, x, y)
end

这些实现运行得都和预期一样：

>> multiply(two, three)
=> 6
>> def six
    multiply(two, three)
  end
=> nil
>> decrement(six)
=> 5
>> subtract(six, two)
=> 4
>> subtract(two, six)
=> 0

我们从 #zero、#increment 和 #recurse 组合出来的程序叫原始递归函数。

所有的原始递归函数都是完全的：不管输入什么，它们总是可以停止并返回一个结果。这是因为 #recurse 是定义递归函数的唯一合法方式，而 #recurse 是总能停止的：每一个递归调用都会使其最后一个参数更接近零，而在它最后不可避免地成为零时，递归就会停止。

方法 #zero、#increment 以及 #recurse 足以构造许多有用的函数，这其中包括图灵机执行单独一步的所有操作：一个图灵机纸带的内容可以表示成一个大数，可以用原始递归函数来读纸带头当前位置的字符、往纸带上写新的字符以及左右移动纸带头。但是，因为有些图灵机是永远循环的，所以我们没法使用原始递归函数模拟任意一台图灵机的完整运行，因此原始递归函数并不是通用的。

为了得到真正的通用系统，我们可以增加第四个基础操作——#minimize：

def minimize
  n = 0
  n = n + 1 until yield(n).zero?
  n
end

方法 #minimize 接受一个块，并不断地使用一个数字作为参数重复调用它。第一次调用时，参数是 0，然后是 1，然后是 2，之后一直用越来越大的值做参数调用块，直到返回零为止。

通过在 #zero、#increment 和 #recurse 中加入 #minimize，我们可以构造更多的函数——所有的部分递归函数——包括那些永远不会停止的函数。例如，#minimize 让我们很容易实现 #divide：

def divide(x, y)
  minimize { |n| subtract(increment(x), multiply(y, increment(n))) }
end

把表达式subtract(increment(x), multiply(y, increment(n)))设计成如果y*(n+1)大于x就返回零。如果试图用 13 除以4（x=13，y=4），我们来看一下随着n 的增长 y*(n+1) 的值的变化：

n	x	y*(n+1)	y*(n+1)比x大吗?
0	13	4	否
1	13	8	否
2	13	12	否
3	13	16	是
4	13	20	是
5	13	24	是

第一个满足条件的 n 值是 3，这样在 n 到达 3 的时候我们传给 #mimimize 的块会返回零，所以得到了 divide(13,4) 的结果 3。

就像原始递归函数一样，#divide 收到有意义的参数时总会返回一个结果：

>> divide(six, two)
=> 3
>> def ten
    increment(multiply(three, three))
  end
=> nil
>> ten
=> 10
>> divide(ten, three)
=> 3

但是因为 #minimize 能永远循环，所以 #divide 不一定要返回一个结果。被零除是未定义的：

>> divide(six, zero)
SystemStackError: stack level too deep

因为 #minimize 的实现是迭代的，而且没有直接增加调用栈，所以这里看到栈溢出有点奇怪，但是溢出发生在 #divide 对递归函数#multiply 的调用期间。#multiply 的递归深度由它的第二个参数 increment(n) 决定，而随着#minimize 的循环试图一直运行下去，n 的值变得很大，最终导致了栈溢出。

有了 #minimize，通过重复调用原始递归函数来执行模拟中的一步，就可能完全模拟一台图灵机。在停机之前模拟一直运行——如果永远不停机，那模拟就会永远运行。