Question

为了理解如何使用最小语言编程，我们不打算使用Ruby 诸多有用的特性来解决问题。很自然，这意味着没有gem，没有标准库，没有模块（module）、方法、类或者对象，既然我们试图尽可能地做到最小，那还将避免使用控制结构、赋值、数组、字符串、数字和布尔值。

当然，如果我们避免使用Ruby 的所有特性，那就没有语言可用来编程了，因此下面是将要保留的：

· 对变量进行引用；

· 创建 proc；

· 调用 proc。

这意味着只能写出如下样子的Ruby 代码：

-> x { -> y { x.call(y) } }

这大致就是无类型lambda 演算程序的样子，足以接近我们的目的了。6.2 节会详细讨论lambda 演算。

为了让代码更简短并且更容易阅读，我们还将使用常量作为缩写：如果创建了一个复杂的表达式，可以把它赋值给一个常量，给它一个短名字以便以后再次使用。引用这个名字与重新输入原始表达式没有区别（名字只是让代码更加简洁），因此我们会依赖于Ruby 的赋值特性。任意时刻都可以通过替换每一个常量所引用的proc 来取消缩写，这样做的代价是会让程序变得更长。

6.1.1　使用proc工作

既然要用proc 构建整个程序，让我们在深度使用它们之前花一分钟看看它们的属性。

目前，我们将使用完整特性的Ruby 来描绘proc 的一般行为。在我们开始写代码来解决 6.12 节的“问题”时，才会施加这些限制。

1. 管道

proc 是值在程序中进行移动的管道。考虑调用下面的proc 时会发生什么：

-> x { x + 2 }.call(1)

作为参数提供给调用的值1，传入代码块x 的参数中，然后把参数传给用到它的所有地方，因此Ruby 最后会对1+2求值。语言的其他部分会做实际的工作，proc 只是把一部分程序连接在一起并让值流向需要它的地方。

对使用最小化Ruby 的实验来说这已经有了不好的兆头。如果proc 只能在实际使用值的Ruby 片段之间移动值，那怎么才能只用proc 就能构建有用的程序呢？探索完proc 的其他属性之后，我们就会理解。

2. 参数

proc 可以带有多个参数，但这不是一个本质特性。如果得到一个能处理多个参数的proc……

-> x, y {
  x + y
}.call(3, 4)

……我们总是可以将其重写为嵌入式的单参数proc：

-> x {
  -> y {
    x + y
  }
}.call(3).call(4)

这里，外部proc 的参数是x，而且会返回内部的proc，内部的proc 也带有一个参数y。我们可以使用x 的一个值调用外部的proc，然后使用y 的一个值调用内部的proc，而且我们会得到与多参数时同样的结果。1

1这叫作curry 化，并且我们可以使用Proc#curry 自动进行这个转换。

既然我们在尽可能多地去掉Ruby 的特性，那就限制自己只创建和调用单参数的proc 吧。这不会让事情变得更糟糕。

3. 等价

查明一个proc 内部代码的唯一途径就是调用它，因此如果使用同样的参数调用两个proc，会产生相同结果的话，那么即使它们的内部代码不同，它们也是可交换的。这种根据外部可见行为判断两者相等的思想叫作外延等价（extensional equality）。

比如说我们有一个叫p 的proc：

>> p = -> n { n * 2 }
=> #<Proc (lambda)>

我们可以再创建一个叫q 的proc，它带有一个参数并且只是用这个参数调用p：

>> q = -> x { p.call(x) }
=> #<Proc (lambda)>

p和q明显是两个不同的proc，但它们外延相等，因为它们对任何参数来讲都会做同样的事情：

>> p.call(5)
=> 10
>> q.call(5)
=> 10

知道p与-> x { p.call(x) } 等价，这就为重构提供了新的机会。如果在我们的程序里看到-> x { p.call(x) }这种一般模式，我们可以选择用p 替换整个表达式来消除它，而在某些情况下（后面会看到），我们可能会决定采用相反的方式。

4. 语法

对于创建和调用proc，Ruby 提供了一个语法选择。从现在开始，我们会使用-> arguments{ body} 创建一个proc，然后使用方括号调用它：

>> -> x { x + 5 }[6]
=> 11

这样无需额外的语法就很容易看到 proc 的主体和参数。

6.1.2　问题

我们的目标是写出著名的 FizzBuzz 程序：

写一个程序输出数字 1 到 100。但如果数字是 3 的倍数，就不输出数字而是输出“Fizz”，如果是 5 的倍数就输出“Buzz”。对于那些 3 和5 的公倍数，就输出“FizzBuzz”。

—— Imran Ghory，“用FizzBuzz 找到热爱编码的开发者” （Using FizzBuzz to Find Developers who Grok Coding，http://imranontech.com/2007/01/24/using-fizzbuzz-to-find-developers-who-grok-coding/）

这是故意挑选的一个简单问题，用来测试一个面试者是否有编程经验。任何知道如何编程的人应该都能毫无困难地解决这个问题。

下面是使用完整特性Ruby 的一个实现：

(1..100).each do |n|
  if (n % 15).zero?
    puts 'FizzBuzz'
  elsif (n % 3).zero?
    puts 'Fizz'
  elsif (n % 5).zero?
    puts 'Buzz'
  else
    puts n.to_s
  end
end

这不是FizzBuzz 最聪明的一个实现（还存在着大量更聪明的实现，http://redd.it/10d7w），但它很直接，任何人都可以不用思考就写出来。

但是，这个程序含有一些puts语句，而我们没法只使用 proc 就把文本输出到控制台，2 因此我们把它替换成一个大致等价的程序，这个程序只返回一个字符串数组而不是输出它们：

2我们当然可以对向控制台输出进行建模，引入一个proc 来表示标准输出，然后设计如何向它发送文本，但那会让我们的练习复杂化，而且变得没意思。FizzBuzz 不是关于输出的，而是关于算数和控制流的。

(1..100).map do |n|
  if (n % 15).zero?
    'FizzBuzz'
  elsif (n % 3).zero?
    'Fizz'
  elsif (n % 5).zero?
    'Buzz'
  else
    n.to_s
  end
end

对FizzBuzz 问题来说这仍然是一个有意义的解决方案，但现在的这个版本我们有可能只用proc 就实现了。

不管它多简单，如果没有一种编程语言的任何特性的话，这仍然是要求非常高的程序：它创建一个范围，对其做映射，对一个大的条件求值，使用取模操作进行算数运算，使用Fixnum#zero? 预测，使用一些字符串，而且还用Fixnum#to_s把数字转换成字符串。这用到了很多Ruby 内建功能，而我们将要把它们全部去除再用proc 重新实现。

6.1.3　数字

我们准备从关注FizzBuzz 中出现的数字开始。怎么才能不用Fixnum或者Ruby提供的任何其他数据类型，就表示出数字呢？

如果打算从头开始实现数字3，我们最好对要实现的东西有个透彻的理解。到底什么是数字呢？如果不对试图定义的东西的某个方面进行假设，就很难给出一个具体的定义。例如，“某个东西告诉我们有多少……”没有用，因为“多少”只是“数字”的另一种表述方式。

3具体说来，我们这里想要实现的是非负整数：0、1、2、3 等。

下面是描绘数字特征的一种方式：想象我们有一袋子苹果和一袋子橘子。我们从一个袋子里取出一个苹果，从另一个袋子里取出一个橘子，然后把它们放到一起。之后我们不断地取出一个苹果和一个橘子，直到至少其中有一个袋子变成空的。

如果两个袋子同时变成空的，我们就学到了一件有趣的事情：尽管含有不同的东西，但这两个袋子有一个共有的属性，这个属性意味着它们同时变空了；在不断从每个袋子里取出水果的每一个时刻，两个袋子都不是空的或者两个袋子都是空的。袋子共有的这个抽象性质就是我们可以叫作数字的东西（尽管不知道是哪个数字！），而且我们可以把这两个袋子与世界上的任何其他袋子做比较，来看看跟它们是不是有着同样的“数”。

因此描绘数字特征的一种方式是某个动作的重复（或者叫迭代），在这个例子中动作是从袋子里取一个物体。每一个数字都与重复一个动作的唯一方式对应：数字1 对应的是只执行这个动作；数字 2 对应的是执行这个动作然后再次执行；以此类推。并不奇怪，数字0对应着根本不执行这个动作。

既然创建和调用proc 是这里程序唯一可以执行的“动作”，我们可以尝试用代码实现一个数字n，在代码里对调用proc 这个动作重复n 次。

例如，如果允许定义方法——这是不允许的，不过我们只是玩一玩——那么我们可以把#one 定义成一个方法，它带有一个proc 参数以及另一个任意的参数，而且它会用该任意参数调用proc：

def one(proc, x)
  proc[x]
end

我们还可以定义#two，它会调用一次proc，然后用第一次调用的结果对其再次调用：4

4这叫作“迭代这个函数”。

def two(proc, x)
  proc[proc[x]]
end

以此类推：

def three(proc, x)
  proc[proc[proc[x]]]
end

按照这种模式，可以很自然地把#zero定义为一个带有proc 和另一个参数的方法，这个方法完全忽略proc（换句话说，对其调用零次），并且会原封不动地返回第二个参数：

def zero(proc, x)
  x
end

所有这些实现都可以转换成无方法的表示。例如，我们可以用带有两个参数5 的proc 替换方法#one，然后用第二个调用参数调用第一个参数。它们看起来是这样：

5实际上，“带有两个参数”并不准确，因为我们已经限制自己只使用单参数的proc 了（参见6.1.1 节中“参数”部分）。准确的说法是“带有一个参数并且返回一个带有另一个参数的新的proc”，但那太绕嘴了，所以我们采用这种简略的说法，只是要记住真正的意思是什么。

ZERO = -> p { -> x { x } }
ONE = -> p { -> x { p[x] } }
TWO = -> p { -> x { p[p[x]] } }
THREE = -> p { -> x { p[p[p[x]]] } }

这避免了不允许我们使用的功能，而且通过把它们赋值给常量还给了proc 名字。把数据表示为纯代码的技术称为邱奇编码（Church encoding）， 它是以lambda 演算（http://dx.doi.org/10.2307/2371045）的发明者阿隆佐·邱奇的名 字命名的。这些数字是邱奇数（Church numeral），而且我们很快将会看到邱奇布尔值（Church Boolean）和邱奇有序对（Church pair）的例子。

尽管在FizzBuzz 解决方案里我们回避了Ruby 的特性，但是一旦超出了我们的代码范围，把数字的这些外部表示转换成Ruby 值会很有用，这样它们就能在控制台进行检查和在测试中断言，或者至少能让我们相信它们确实本来代表数字。

幸运的是，可以写一个#to_integer 方法执行这个转换：

def to_integer(proc)
  proc[-> n { n + 1 }][0]
end

这个方法带有表示一个数字的 proc 并用另一个 proc 和原始的Ruby 数字 0 来调用它（这个 proc 只是递增它的参数）。如果我们使用ZERO调用#to_integer，那么因为ZERO的定义，递增的 proc 不会得到调用，这样我们会原封不动得到0：

>> to_integer(ZERO)
=> 0

而如果用THREE调用#to_integer，递增的 proc 将会被调用三次，这样我们得到Ruby 的3：

>> to_integer(THREE)
=> 3

因此基于proc 的表示只是在对数字进行编码，并且我们可以根据需要把它们转成更实用的表示。

对于FizzBuzz，需要数字5、15 和100，它们都可以用同样的技术实现：

FIVE = -> p { -> x { p[p[p[p[p[x]]]]] } }
FIFTEEN = -> p { -> x { p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[x]]]]]]]]]]]]]]] } }
HUNDRED = -> p { -> x { p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[
p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[
p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[x]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
]]]]]]]]]]]]]]]]]]]]]]] } }

这些都不是很简洁的定义，但它们确实可以工作，就像用#to_integer 确认的那样：

>> to_integer(FIVE)
=> 5
>> to_integer(FIFTEEN)
=> 15
>> to_integer(HUNDRED)
=> 100

因此，回到 FizzBuzz 程序，所有的 Ruby 数字都可以用基于 proc 的实现替换：

(ONE..HUNDRED).map do |n|
  if (n % FIFTEEN).zero?
    'FizzBuzz'
  elsif (n % THREE).zero?
    'Fizz'
  elsif (n % FIVE).zero?
    'Buzz'
  else
    n.to_s
  end
end

我们写成 ONE 而不是-> p { -> x { p[x] } }等，这是为了让代码更清晰。

遗憾的是，这个程序不再工作了，因为我们在对基于proc 的数字实现上使用了像.. 和% 这样的运算符。因为不知道如何处理，所以Ruby 将会这样报错：TypeError: can't iterate from Proc, NoMethodError: undefined method%' for #`。为了使用这些表示，我们需要替换掉所有运算，并且只能使用 proc 完成。

但是在我们能重新实现任何一个操作之前，需要实现true 和false。

6.1.4　布尔值

我们怎样才能只用proc 表示布尔值呢？布尔值只会存在于条件语句当中，而且通常情况下，一个条件会说“if 某个布尔值then这样else那样”：

>> success = true
=> true
>> if success then 'happy' else 'sad' end
=> "happy"
>> success = false
=> false
>> if success then 'happy' else 'sad' end
=> "sad"

所以一个布尔值的真正工作是允许在两个选项中做选择，因此我们可以利用这一点，把布尔值表示成在两个值中选择其一的proc。我们不是把一个布尔值看成一段无生命的代码，它被将来的代码读取并能决定选择两个选项中的哪一个，而只是直接把它实现为一段代码，这段代码在用两个选项进行调用的时候，要么选择第一个选项要么选择第二个。

实现成方法的#true 和#false 可能是：

def true(x, y)
  x
end

def false(x, y)
  y
end

#true 是一个带有两个参数并返回第一个参数的方法，而#false 带有两个参数并返回第二个。这足够提供给我们粗线条的条件行为了：

>> success = :true
=> :true
>> send(success, 'happy', 'sad')
=> "happy"
>> success = :false
=> :false
>> send(success, 'happy', 'sad')
=> "sad"

像以前一样直接把这些方法转换成proc：

TRUE = -> x { -> y { x } }
FALSE = -> x { -> y { y } }

就像之前定义了#to_integer 方法作为检查，以便能够把基于proc 的数字转换成Ruby 数字一样，我们可以定义#to_boolean 方法，以便能把TRUE 和FALSE 的proc 转换成Ruby 原始的true 和false 对象：

def to_boolean(proc)
  proc[true][false]
end

这个函数带有一个表示布尔值的参数，然后使用true 作为第一个参数而false 作为第二个参数调用它。TRUE 只是会返回它的第一个参数，因此to_boolean（TRUE）将会返回true，而FALSE 会返回false：

>> to_boolean(TRUE)
=> true
>> to_boolean(FALSE)
=> false

因此用proc 表示布尔值出奇地简单，但对于FizzBuzz，我们不只需要布尔值，还需要用proc 实现Ruby 的if-elseif-else。事实上，由于这些布尔值实现的工作方式，很容易写出#if 方法：

def if(proc, x, y)
  proc[x][y]
end

而这很容易转换成一个proc：

IF =
  -> b {
    -> x {
      -> y {
        b[x][y]
      }
    }
  }

很明显IF 不需要做什么有用的工作，因为布尔值自己就会找到合适的参数——IF 只是添加的糖——但看起来比直接调用布尔值更自然：

>> IF[TRUE]['happy']['sad']
=> "happy"
>> IF[FALSE]['happy']['sad']
=> "sad"

这还意味着我们可以修改#to_boolean 方法以使用IF：

def to_boolean(proc)
  IF[proc][true][false]
end

尽管我们在重构，但值得一提的是，像6.1.1 节中“相等”部分讨论的那样，IF 的实现含有与更简单的proc 等价的proc，所以IF 的实现能被显著简化。例如看一下IF的最内层实现：

-> y {
  b[x][y]
}

这段代码的意思是：

1.带上一个参数y； 2.用参数x 调用b 得到一个proc； 3.用参数y 调用这个proc。

第1步和第3步没什么用：在我们使用一个参数调用这个proc 的时候，它只是把这个参数传给另一个proc。因此整个proc 只是与第2步等价，也就是b[x]，而我们可以把无用的代码从IF的实现中移除，以便让它更简洁：

IF =
  -> b {
    -> x {
      b[x]
    }
  }

在最内层我们又看到了同样的模式：

-> x {
  b[x]
}

基于同样的原因，这个proc与b相同，因此我们可以进一步简化IF：

IF = -> b { b }

我们不能再进一步简化了。

IF 没做什么有用的事情（是TRUE 和FALSE 在做全部的工作），因此我们可以去掉它以做进一步的简化。但我们的目标是把原始的FizzBuzz 程序尽可能忠实地转换成proc，因此尽管IF仅仅起到装饰作用，但使用IF提醒我们ifelsif-else 表达式在原始程序中出现的位置会很方便。

不管怎样，现在有了IF，可以回到FizzBuzz 程序把Ruby 的if-elsif-else替换成对IF的嵌套调用了：

(ONE..HUNDRED).map do |n|
  IF[(n % FIFTEEN).zero?][
    'FizzBuzz'
  ][IF[(n % THREE).zero?][
    'Fizz'
  ][IF[(n % FIVE).zero?][
    'Buzz'
  ][
    n.to_s
  ]]]
end

6.1.5　谓词

我们下一步的工作是用基于 proc 的实现替换Fixnum#zero?，这个实现将会与基于 proc 的数字一起工作。处理 Ruby 值的#zero? 的基本算法像下面这样：

def zero?(n)
  if n == 0
    true
  else
    false
  end
end

（这有些冗余，但它明确了所发生的事情：把这个数字与0 比较；如果相等就返回true，否则返回false。）

我们如何才能让它处理proc 而不是Ruby 数字呢？请再看一下数字的实现：

ZERO = -> p { -> x { x } }
ONE = -> p { -> x { p[x] } }
TWO = -> p { -> x { p[p[x]] } }
THREE = -> p { -> x { p[p[p[x]]] } }
.
.
.

注意，ZERO 是唯一不调用p 的数字——它只是返回x——但所有其他的数字至少会调用p一次。我们可以利用这一点：如果用TRUE作为第二个参数调用一个未知的数字，则如果数字是ZERO，它将立即返回TRUE。如果不是ZERO，它会返回调用p 返回的东西，因此如果我们让p 成为一个总是返回FLASE 的proc，就会得到想要的行为：

def zero?(proc)
  proc[-> x { FALSE }][TRUE]
end

把它重写成一个proc 还是很容易：

IS_ZERO = -> n { n[-> x { FALSE }][TRUE] }

我们可以使用#to_boolean 在控制台上检查它的工作情况：

>> to_boolean(IS_ZERO[ZERO])
=> true
>> to_boolean(IS_ZERO[THREE])
=> false

这工作得很好，所以在FizzBuzz 里，我们可以把所有对#zero? 的调用替换成IS_ZERO：

(ONE..HUNDRED).map do |n|
  IF[IS_ZERO[n % FIFTEEN]][
    'FizzBuzz'
  ][IF[IS_ZERO[n % THREE]][
    'Fizz'
  ][IF[IS_ZERO[n % FIVE]][
    'Buzz'
  ][
    n.to_s
  ]]]
end

6.1.6　有序对

我们已经有了数字和布尔值形式的可用数据，但还没有能有条理地存储超过一个值的任何数据结构。为了实现更复杂的功能，我们将很快需要某种数据结构，因此先来介绍一个。

最简单的数据结构是有序对（pair），它跟二元数组类似。有序对实现起来非常容易：

PAIR = -> x { -> y { -> f { f[x][y] } } }
LEFT = -> p { p[-> x { -> y { x } } ] }
RIGHT = -> p { p[-> x { -> y { y } } ] }

一个有序对的作用是存储两个值，并在之后根据需要再次提供。为了构建一个有序对，我们用两个值（一个x和一个y）调用PAIR，然后返回它的内部proc：

-> f { f[x][y] }

这个proc 在用另一个为f的proc 调用时，会用较早的x和y的值作为参数回调它。LEFT和RIGHT会从一个有序对中分别选出左边和右边的元素，它们会调用一个proc，这个proc分别返回其第一个和第二个参数。它足够简单：

>> my_pair = PAIR[THREE][FIVE]
=> #<Proc (lambda)>
>> to_integer(LEFT[my_pair])
=> 3
>> to_integer(RIGHT[my_pair])
=> 5

这个非常简单的数据结构足够我们使用了；6.1.8 节中将使用有序对，将其作为更复杂结构的一个基础结构。

6.1.7　数值运算

现在有了数字、布尔值、条件、谓词以及有序对，我们几乎准备好重新实现模运算符了。

在对两个数进行模运算之前，我们需要能够执行更简单的运算，如递增和递减一个数。递增相当直接：

INCREMENT = -> n { -> p { -> x { p[n[p][x]] } } }

看一下INCREMENT 如何工作：我们用基于proc 的数字n调用它，它会返回一个新的proc，这个proc 像数字那样带有某个其他proc p 和某个任意的第二参数x。

我们调用这个新的proc 的时候它会做什么呢？首先它会以p和x作为参数调用n——因为n是一个数字，所以这意味着就像原始的数字那样，“在x上对p进行n次调用”——然后对结果再调用一次p。那么总体说来，这个proc 的第一个参数会在它的第二个参数上调用n+1次，这恰好是表示数字n+1的方法。

但递减呢？这看起来是个更难的问题：一旦一个proc 已经调用了n次，再额外增加一次调用以便成为n+1次调用是相当容易的，但没有明显的方法可以撤销一次调用以便成为n-1次调用。

一个解决办法就是设计一个proc，在对某个初始参数调用n次的时候返回数字n-1。幸运的是，有序对正好可以帮助我们实现这种方法。思考一下这个Ruby 方法所做的：

def slide(pair)
  [pair.last, pair.last + 1]
end

在我们用数字组成的二元数组为参数调用slide时，它会返回一个新的二元数组，这个二元数组包含第二个数字还有比第二个数字大1 的数字；如果输入的数组包含的是连续数字，那么效果就是向上“滑动”一个数字窗口：

>> slide([3, 4])
=> [4, 5]
>> slide([8, 9])
=> [9, 10]

这很有用，因为通过在-1处开始一个窗口，我们可以安排一种情况，让数组里的第一个数字比我们调用slide的次数小1，即使我们只是在递增数据:

>> slide([-1, 0])
=> [0, 1]
>> slide(slide([-1, 0]))
=> [1, 2]
>> slide(slide(slide([-1, 0])))
=> [2, 3]
>> slide(slide(slide(slide([-1, 0]))))
=> [3, 4]

我们不能只用基于proc 的数字完成，因为没法表示-1，但side的有趣之处是不管怎样它只关注数组中的第二个数，因此我们可以放入任意的哑值（dummy value）——比如说0——替换掉-1，这样仍然能得到同样的结果：

>> slide([0, 0])
=> [0, 1]
>> slide(slide([0, 0]))
=> [1, 2]
>> slide(slide(slide([0, 0])))
=> [2, 3]
>> slide(slide(slide(slide([0, 0]))))
=> [3, 4]

这是让DECREMENT工作的关键：我们可以把slide转成一个proc，使用数字n的proc 表示对由ZERO组成的有序对调用slide n次，然后使用LEFT从结果的有序对中拉出左边的数来：

SLIDE = -> p { PAIR[RIGHT[p]][INCREMENT[RIGHT[p]]] }
DECREMENT = -> n { LEFT[n[SLIDE][PAIR[ZERO][ZERO]]] }

下面是DECREMENT的作用：

>> to_integer(DECREMENT[FIVE])
=> 4
>> to_integer(DECREMENT[FIFTEEN])
=> 14
>> to_integer(DECREMENT[HUNDRED])
=> 99
>> to_integer(DECREMENT[ZERO])
=> 0

DECREMENT[ZERO]的结果实际上只是最初的PAIR[ZERO][ZERO]值的左边元素，在这种情况下根本就没有对其调用过SLIDE。既然没有负值，0 就是我们能提供DECREMENT[ZERO]的最合理的答案，因此使用0 作为哑值是个好主意。

既然我们有了INCREMENT和DECREMENT，就可能实现类似加法、减法、乘法和取幂这样的数字运算了：

ADD = -> m { -> n { n[INCREMENT][m] } }
SUBTRACT = -> m { -> n { n[DECREMENT][m] } }
MULTIPLY = -> m { -> n { n[ADD[m]][ZERO] } }
POWER = -> m { -> n { n[MULTIPLY[m]][ONE] } }

这些实现在很大程度上是自解释的。如果我们想要m加n，只需要“从m开始对其递增n次”，同样这也适用于减法；有了ADD之后，我们可以进行m乘n，方法是“从ZERO开始，对其进行n次ADD m”，使用MULTIPLY 和ONE 进行幂运算也类似。

DECREMENT[ZERO]在6.2.2 节“规约表达式”部分中，我们将用Ruby 完成ADD[ONE][ONE] 的小步求值，以便展示它如何产生TWO。

这些算数足够我们起步了，但在能用proc 实现% 之前，我们需要了解一个执行模运算的算法。下面是其对Ruby 数字的处理：

def mod(m, n)
  if n <= m
    mod(m - n, n)
  else
    m
  end
end

例如，为了计算17 模5 可以进行如下操作：

· 如果 5 小于等于17，这是事实，那么就用17 减去5，然后在结果上调用#mod方法，也就是说12模5；

· 5小于等于12，因此尝试7模5；

· 5小于等于7，因此尝试 2模5；

· 5不再小于等于2，因此返回结果2。

但我们还不能用proc 实现#mod，因为它使用了另一个运算符<=，我们还没有实现它，因此需要暂时先用proc 实现<=。

可以从看起来不相干的对Ruby 数的#less_or_equal? 实现开始：

def less_or_equal?(m, n)
  m - n <= 0
end

这没什么用，因为它依赖于<=，但至少它把问题分解成了两个我们已经解决的其他问题了：减法和与零作比较。减法我们已经处理过了，与零的相等性我们也完成了，但我们如何实现小于等于零的判断呢？

碰巧我们不需要担心，因为零已经是我们知道如何实现的最小的数了。回忆一下，我们基于proc 的数字都是非负的，因此“小于零”在我们的数字系统里是无意义的概念。

如果从一个小一点的数里用SUBSTRACT减去一个大一点的数，将只会返回ZERO，因为没法返回一个负数，并且ZERO是能得到的最接近的值了6：

6你可能会抗议3-5=0不叫“减法”，你是对的：这种运算的专业名称叫“monus”，因为加法之下的非负整数形成的是可交换幺半群而不是一个合适的阿贝尔群。

>> to_integer(SUBTRACT[FIVE][THREE])
=> 2
>> to_integer(SUBTRACT[THREE][FIVE])
=> 0

我们已经写了IS_ZERO，并且因为如果m小于等于n（也就是说n至少与m一样大）的话SUBTRACT[m][n]会返回ZERO，所以足可以用proc 实现#less_or_equal?了：

def less_or_equal?(m, n)
  IS_ZERO[SUBTRACT[m][n]]
end

让我们把这个方法转成proc：

IS_LESS_OR_EQUAL =
  -> m { -> n {
    IS_ZERO[SUBTRACT[m][n]]
} }

它能正常工作吗？

>> to_boolean(IS_LESS_OR_EQUAL[ONE][TWO])
=> true
>> to_boolean(IS_LESS_OR_EQUAL[TWO][TWO])
=> true
>> to_boolean(IS_LESS_OR_EQUAL[THREE][TWO])
=> false

看起来不错。

这补上了#mod实现中缺少的部分，因此可以用proc 重写它：

def mod(m, n)
  IF[IS_LESS_OR_EQUAL[n][m]][
    mod(SUBTRACT[m][n], n)
  ][
    m
  ]
end

并用一个proc 替换掉方法定义：

MOD =
  -> m { -> n {
    IF[IS_LESS_OR_EQUAL[n][m]][
      MOD[SUBTRACT[m][n]][n]
    ][
      m
  ]
} }

太好了！它能工作吗？

>> to_integer(MOD[THREE][TWO])
SystemStackError: stack level too deep

不能。

Ruby 在调用MOD的时候进入了无限递归循环，因为我们把Ruby 的原始功能转换成proc 时漏掉了条件语义中一些重要的东西。在像Ruby 这样的语言里，if-else语句是非严格的（或者说是懒的）：我们给它一个条件和两个代码块，然后它会对条件求值以决定对哪个代码块求值并返回——它从来也不会对两个代码块都求值。

IF 实现的问题是我们无法利用构建到Ruby 的if-else里的懒性行为。我们只能说“调用一个proc，IF，其参数是两个其他的proc”，因此Ruby冲出来，在IF有机会决定返回哪个之前就对两个参数都进行求值。

再看一下MOD：

MOD =
  -> m { -> n {
    IF[IS_LESS_OR_EQUAL[n][m]][
      MOD[SUBTRACT[m][n]][n]
    ][
      m
  ]
} }

在我们对m和n调用MOD， 而Ruby 开始对内部proc 的代码体求值时， 它会对MOD[SUBTRACT[m][n]][n] 进行递归调用并立即开始把它当作传递给IF 的参数求值，不管IS_LESS_OR_EQUAL[n][m]是TRUE还是FALSE。对MOD第二次调用的结果是又一次无条件的递归调用，以此类推，从而会无限递归下去。

为了修正，我们需要一种方式告诉Ruby 延迟对IF第二个参数的求值，直到确定需要对其求值为止。Ruby 中任何表达式的求值都可以通过封装到一个proc 里延迟，但在一个proc内封装一个任意的Ruby 值通常会改变其含义（如1+2 的结果并不等于->{1+2}），因此我们可能需要做得更聪明一些。

幸运的是没必要这样做，因为这是一个特殊情况：我们知道因为所有的值都是单参数的proc，所以调用MOD的结果也将会是一个单参数的proc，并且我们已经知道（参见6.1.1 节中“相等”部分），对于任意的proc p，另一个proc 将其封装，它与p参数相同并立即用此参数调用p，它们将会产生同样的值，因此我们可以使用这个技巧延迟递归调用而不影响传递给IF 的值的含义：

MOD =
  -> m { -> n {
    IF[IS_LESS_OR_EQUAL[n][m]][
      -> x {
        MOD[SUBTRACT[m][n]][n][x]
      }
    ][
      m
  ]
} }

这把递归的MOD调用封装到-> x { ...[x] }以对其延迟。Ruby 现在不会在调用IF的时候试图对这个proc 的代码体求值了，但如果这个proc 被IF选中并作为结果返回，它就能被接受者调用，最终触发（现在肯定是需要的）对MOD的递归调用。

MOD现在能工作吗？

>> to_integer(MOD[THREE][TWO])
=> 1
>> to_integer(MOD[
    POWER[THREE][THREE]
  ][
    ADD[THREE][TWO]
  ])
=> 2

是的，太好啦！

但是先别庆祝，因为还有一个更棘手的问题：我们在用常量MOD 定义常量MOD，因此这个定义不只是一个缩写。这次我们不仅仅在把一个复杂的proc 赋值给一个常量以便之后重用。事实上，我们在依赖Ruby 的赋值语义，尽管仍然在定义MOD，但它很明显还没有被定义，然而我们可以在MOD的实现中引用它，并期望在之后对其求值的时候它已经被定义了。

那是在欺骗，因为原则上我们应该能撤销掉所有的缩写——“我们提到MOD的地方，实际的意思是这个长长的proc”——但只要MOD由其自身定义这就不可能。

我们可以使用Y 组合子解决此问题，这些著名的辅助代码恰恰是为此目的：无欺骗地定义一个递归函数。下面是它的样子：

Y = -> f { -> x { f[x[x]] }[-> x { f[x[x]] }] }

三言两语很难解释Y 组合子，但下面是一个梗概（技术上不准确）：当我们使用一个proc调用Y 组合子的时候，它会用proc本身作为第一个参数对proc 进行调用。因此，如果我们写了一个需要一个参数的proc 并用那个proc 调用这个Y 组合子，那么这个proc 将会把自身作为参数，从而只要它想要调用自身的时候就可以使用那个参数。

悲剧的是，由于和MOD永远循环一样的原因，Y 组合子在Ruby 中也会永远循环下去，因此我们需要一个修订后的版本。是表达式x[x]引起了这个问题，而我们可以再次修正这个问题，方法是每次这个表达式出现，就把它封装到-> y { ...[y] }内部以延迟它们的求值：

Z = -> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }

这是Z 组合子，它是Y 组合子对于像Ruby 这样严格语言的变换。

最后我们可以创建MOD 的一个满意实现了，方法是给MOD提供一个额外的参数f，封装对围绕它的Z 组合子的调用，这样在我们之前调用MOD的地方都可以调用f：

MOD =
  Z[-> f { -> m { -> n {
    IF[IS_LESS_OR_EQUAL[n][m]][
      -> x {
        f[SUBTRACT[m][n]][n][x]
      }
    ][
      m
    ]
  } } }]

谢天谢地，MOD的这个无欺骗的版本仍然能工作：

>> to_integer(MOD[THREE][TWO])
=> 1
>> to_integer(MOD[
    POWER[THREE][THREE]
  ][
    ADD[THREE][TWO]
  ])
=> 2

现在我们可以把FizzBuzz 程序中%出现的地方都替换成MOD的调用：

(ONE..HUNDRED).map do |n|
  IF[IS_ZERO[MOD[n][FIFTEEN]]][
    'FizzBuzz'
  ][IF[IS_ZERO[MOD[n][THREE]]][
    'Fizz'
  ][IF[IS_ZERO[MOD[n][FIVE]]][
    'Buzz'
  ][
    n.to_s
  ]]]
end

6.1.8　列表

对于FizzBuzz 我们只遗留了几个Ruby 特性要重新实现：范围（range）、#map、字符串字面量以及Fixnum#to_s。对于已经实现的值和运算我们已经看到了大量细节，因此我们将会快速浏览其余的特性并尽可能地减少细节。（不要担心需要理解所有的东西，我们只是浅尝辄止。）

为了能够实现范围和#map，我们需要实现列表（list），而构建列表的最简单方法就是使用有序对（pair）。这个实现像链表一样工作，其中每个有序对都保存一个值和一个指向链表中下一个有序对的指针。在这里，我们不使用指针而是使用嵌入式的有序对。标准的列表运算看起来是这样：

EMPTY   = PAIR[TRUE][TRUE]
UNSHIFT = -> l { -> x {
      PAIR[FALSE][PAIR[x][l]]
} }
IS_EMPTY = LEFT
FIRST  = -> l { LEFT[RIGHT[l]] }
REST   = -> l { RIGHT[RIGHT[l]] }

它们像这样工作：

>> my_list =
    UNSHIFT[
      UNSHIFT[
        UNSHIFT[EMPTY][THREE]
      ][TWO]
    ][ONE]
=> #<Proc (lambda)>
>> to_integer(FIRST[my_list])
=> 1
>> to_integer(FIRST[REST[my_list]])
=> 2
>> to_integer(FIRST[REST[REST[my_list]]])
=> 3
>> to_boolean(IS_EMPTY[my_list])
=> false
>> to_boolean(IS_EMPTY[EMPTY])
=> true

使用FIRST和REST取出列表中的单个元素相当笨拙，因此就像处理数字和布尔值那样，我们可以写一个#to_array方法以便在控制台上提供帮助：

def to_array(proc)
  array = []

  until to_boolean(IS_EMPTY[proc])
    array.push(FIRST[proc])
    proc = REST[proc]
  end

  array
end

这让监视列表更为容易：

>> to_array(my_list)
=> [#<Proc (lambda)>, #<Proc (lambda)>, #<Proc (lambda)>]
>> to_array(my_list).map { |p| to_integer(p) }
=> [1, 2, 3]

如何实现范围呢？事实上，与其找到一种方式显式地把范围表示成proc，不如只写一个proc，它可以构建范围内的所有元素的列表。对于原始的Ruby 数字和“列表”（如数组），我们可以这么写：

def range(m, n)
  if m <= n
    range(m + 1, n).unshift(m)
  else
    []
  end
end

在预期可用的列表操作方面，这个算法稍嫌做作，但能讲得通：由m到n所有数字组成的列表与由m+1到n组成的列表（并在前头放上m）一样；如果m比n大，那这个由数字组成的列表就是空的。

幸运的是，我们已经有了把这个方法直接转换成proc 所需要的一切：

RANGE =
  Z[-> f {
    -> m { -> n {
      IF[IS_LESS_OR_EQUAL[m][n]][
        -> x {
          UNSHIFT[f[INCREMENT[m]][n]][m][x]
        }
      ][
        EMPTY
    ]
  } }
}]

注意Z 组合子对递归的使用，以及条件语句的TRUE分支周围的-> x { ...[x] }。

它能正常工作吗？

>> my_range = RANGE[ONE][FIVE]
=> #<Proc (lambda)>
>> to_array(my_range).map { |p| to_integer(p) }
=> [1, 2, 3, 4, 5]

是的，可以正常工作，所以让我们在FizzBuzz 中使用：

RANGE[ONE][HUNDRED].map do |n|
  IF[IS_ZERO[MOD[n][FIFTEEN]]][
    'FizzBuzz'
  ][IF[IS_ZERO[MOD[n][THREE]]][
    'Fizz'
  ][IF[IS_ZERO[MOD[n][FIVE]]][
    'Buzz'
  ][
    n.to_s
  ]]]
end

为了实现#map，我们可以使用一个叫FOLD的辅助方法，它有点像Ruby 中的Enumerable#inject：

FOLD =
  Z[-> f {
    -> l { -> x { -> g {
      IF[IS_EMPTY[l]][
        x
      ][
        -> y {
          g[f[REST[l]][x][g]][FIRST[l]][y]
        }
      ]
  } } }
}]

FOLD令写出能处理列表中每一项元素的proc 变得更简单：

>> to_integer(FOLD[RANGE[ONE][FIVE]][ZERO][ADD])
=> 15
>> to_integer(FOLD[RANGE[ONE][FIVE]][ONE][MULTIPLY])
=> 120

一旦有了FOLD，我们就可以简洁地写出MAP来：

MAP =
  -> k { -> f {
    FOLD[k][EMPTY][
      -> l { -> x { UNSHIFT[l][f[x]] } }
    ]
  } }

MAP能正常工作吗？

>> my_list = MAP[RANGE[ONE][FIVE]][INCREMENT]
=> #<Proc (lambda)>
>> to_array(my_list).map { |p| to_integer(p) }
=> [2, 3, 4, 5, 6]

是的，可以正常工作。因此我们可以替换掉FizzB 中的#map了：

MAP[RANGE[ONE][HUNDRED]][-> n {
  IF[IS_ZERO[MOD[n][FIFTEEN]]][
    'FizzBuzz'
  ][IF[IS_ZERO[MOD[n][THREE]]][
    'Fizz'
  ][IF[IS_ZERO[MOD[n][FIVE]]][
    'Buzz'
  ][
    n.to_s
  ]]]
}]

差不多完成了！就剩下处理字符串了。

6.1.9　字符串

字符串很容易处理：我们可以只是把它们表示成由数字组成的列表，只要对哪个数字表示哪个字符的编码达成一致就可以。

我们可以选择任何编码，因此不使用像ASCII 这样的通用目的的编码，而是设计一种对于FizzBuzz 更方便的新型编码。只需要对数字和字符串'FizzBuzz'、'Fizz' 以及'Buzz' 进行编码就可以，因此可以使用0 到9表示字符'0' 到'9'，而把字符'B'、'F'、'i'、'u'和'z' 编码成10 ～ 14。

这样我们就有了一种方式来表示需要的字符串字面量（注意不要截断Z 组合子）：

TEN = MULTIPLY[TWO][FIVE]
B = TEN
F = INCREMENT[B]
I = INCREMENT[F]
U = INCREMENT[I]
ZED = INCREMENT[U]

FIZZ = UNSHIFT[UNSHIFT[UNSHIFT[UNSHIFT[EMPTY][ZED]][ZED]][I]][F]
BUZZ = UNSHIFT[UNSHIFT[UNSHIFT[UNSHIFT[EMPTY][ZED]][ZED]][U]][B]
FIZZBUZZ = UNSHIFT[UNSHIFT[UNSHIFT[UNSHIFT[BUZZ][ZED]][ZED]][I]][F]

为了检查其是否能正常工作，可以写一些外部的方法，把它们转换成Ruby 字符串：

def to_char(c)
  '0123456789BFiuz'.slice(to_integer(c))
end

def to_string(s)
  to_array(s).map { |c| to_char(c) }.join
end

好了，字符串能工作了吗？

>> to_char(ZED)
=> "z"
>> to_string(FIZZBUZZ)
=> "FizzBuzz"

太好啦。那么可以在FizzBuzz 中使用它们了：

MAP[RANGE[ONE][HUNDRED]][-> n {
  IF[IS_ZERO[MOD[n][FIFTEEN]]][
    FIZZBUZZ
  ][IF[IS_ZERO[MOD[n][THREE]]][
    FIZZ
  ][IF[IS_ZERO[MOD[n][FIVE]]][
    BUZZ
  ][
    n.to_s
  ]]]
}]

最后要实现的是Fixnum#to_s。为此，我们需要能把数分割成组成它的数字，下面是一种用Ruby 实现的方法：

def to_digits(n)
  previous_digits =
    if n < 10
      []
    else
      to_digits(n / 10)
    end

  previous_digits.push(n % 10)
end

还没有实现<，但可以通过使用n <= 9而不是n < 10来规避这个问题。遗憾的是，我们没法回避实现Fixnum#/和Array#push，下面是它们的实现：

DIV =
  Z[-> f { -> m { -> n {
    IF[IS_LESS_OR_EQUAL[n][m]][
      -> x {
        INCREMENT[f[SUBTRACT[m][n]][n]][x]
      }
    ][
      ZERO
    ]
  } } }]
PUSH =
  -> l {
    -> x {
      FOLD[l][UNSHIFT[EMPTY][x]][UNSHIFT]
    }
  }

现在可以把#to_digits转换成一个proc 了：

TO_DIGITS =
  Z[-> f { -> n { PUSH[
    IF[IS_LESS_OR_EQUAL[n][DECREMENT[TEN]]][
      EMPTY
    ][
      -> x {
        f[DIV[n][TEN]][x]
      }
    ]
  ][MOD[n][TEN]] } }]

它能工作吗？

>> to_array(TO_DIGITS[FIVE]).map { |p| to_integer(p) }
=> [5]
>> to_array(TO_DIGITS[POWER[FIVE][THREE]]).map { |p| to_integer(p) }
=> [1, 2, 5]

是的，可以工作。而且因为我们已经预见性地设计了一种字符串编码，在这种字符串编码里，1代表'1'，以此类推，所以由TO_DIGITS产生的数组已经是有效的字符串了：

>> to_string(TO_DIGITS[FIVE])
=> "5"
>> to_string(TO_DIGITS[POWER[FIVE][THREE]])
=> "125"

因此我们可以在FizzBuzz 中用TO_DIGITS替换#to_s：

MAP[RANGE[ONE][HUNDRED]][-> n {
  IF[IS_ZERO[MOD[n][FIFTEEN]]][
    FIZZBUZZ
  ][IF[IS_ZERO[MOD[n][THREE]]][
    FIZZ
  ][IF[IS_ZERO[MOD[n][FIVE]]][
    BUZZ
  ][
    TO_DIGITS[n]
  ]]]
}]

6.1.10　解决方案

我们最终完成了！（这可能是有史以来最长的、最笨拙的工作面试了。）现在我们已经有了完全由proc 写成的FizzBuzz 的实现。来运行一下以确保它正常工作：

>> solution =
    MAP[RANGE[ONE][HUNDRED]][-> n {
      IF[IS_ZERO[MOD[n][FIFTEEN]]][
        FIZZBUZZ
      ][IF[IS_ZERO[MOD[n][THREE]]][
        FIZZ
      ][IF[IS_ZERO[MOD[n][FIVE]]][
        BUZZ
      ][
        TO_DIGITS[n]
      ]]]
  }]
=> #<Proc (lambda)>
>> to_array(solution).each do |p|
    puts to_string(p)
    end; nil
1
2
Fizz
4
Buzz
Fizz
7
.
.
.
94
Buzz
Fizz
97
98
Fizz
Buzz
=> nil

经历了这么多麻烦以确保每一个常量只是某个更长表达式的一个缩写，我们认为有必要把每一个常量用它的定义替换，因此可以看到完整的程序了：

-> k { -> f { -> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }
[-> f { -> l { -> x { -> g { -> b { b }[-> p { p[-> x { -> y { x } }] }[l]][x]
[-> y { g[f[-> l { -> p { p[-> x { -> y { y } }] }[-> p { p[-> x { -> y { y } }] }
[l]] }[l]][x][g]][-> l { -> p { p[-> x { -> y { x } }] }[-> p { p[-> x { -> y
{ y } }] }[l]] }[l]][y] }] } } } }][k][-> x { -> y { -> f { f[x][y] } } }[-> x
{ -> y { x } }][-> x { -> y { x } }]][-> l { -> x { -> l { -> x { -> x { -> y
{ -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }
[x][l]] } }[l][f[x]] } }] } }[-> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y
{ x[x][y] }] }] }[-> f { -> m { -> n { -> b { b }[-> m { -> n { -> n { n[-> x
{ -> x { -> y { y } } }][-> x { -> y { x } }] }[-> m { -> n { n[-> n { -> p { p[-
> x { -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p { p[-> x
{ -> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x { ->
y { y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x { x } }][-
> p { -> x { x } }]]] }][m] } }[m][n]] } }[m][n]][-> x { -> l { -> x { -> x { -
> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }
[x][l]] } }[f[-> n { -> p { -> x { p[n[p][x]] } } }[m]][n]][m][x] }][-> x { ->
y { -> f { f[x][y] } } }[-> x { -> y { x } }][-> x { -> y { x } }]] } } }][-> p
{ - > x { p [ x ] } } ] [ - > p { - > x
{ p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[
p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[
p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[x]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]] } }]][->
n { -> b { b }[-> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-
> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> m
{ -> n { -> b { b }[-> m { -> n { -> n { n[-> x { -> x { -> y { y } } }][-> x
{ -> y { x } }] }[-> m { -> n { n[-> n { -> p { p[-> x { -> y { x } }] }[n[-> p
{ -> x { -> y { -> f { f[x][y] } } }[-> p { p[-> x { -> y { y } }] }[p]][-> n
{ -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x { -> y { y } }] }[p]]] }][-> x
{ -> y { -> f { f[x][y] } } }[-> p { -> x { x } }][-> p { -> x { x } }]]] }]
[m] } }[m][n]] } }[n][m]][-> x { f[-> m { -> n { n[-> n { -> p { p[-> x { -> y
{ x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p { p[-> x { -> y
{ y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x { -> y
{ y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x { x } }][-> p
{ -> x { x } }]]] }][m] } }[m][n]][n][x] }][m] } } }][n][-> p { -> x
{ p[p[p[p[p[p[p[p[p[p[p[p[p[p[p[x]]]]]]]]]]]]]]] } }]]][-> l { -> x { -> x { -
> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }
[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }]
[-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f
{ f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }
[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -
> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x]
[y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-
> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { ->
y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x]
[y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-
> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { ->
y { -> f { f[x][y] } } }[x][l]] } }[-> x { -> y { -> f { f[x][y] } } }[-> x { -
> y { x } }][-> x { -> y { x } }]][-> n { -> p { -> x { p[n[p][x]] } } }[-> n
{ -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -
> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { ->
x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x
{ p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]]]][-> n { -> p { -> x
{ p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x
{ p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m
{ -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x
{ x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]]]]
[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-
> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { ->
p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x
{ p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]]][-> m { -> n { n[-> m { -
> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }
[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]][-> n { -> p
{ -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -
> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-
> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x
{ x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]]]]
[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-
> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> m
{ -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-
> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x
{ p[p[p[p[p[x]]]]] } }]]]]]]][-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p
{ -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x
{ p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }]
[-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]][-> n { -> p { -> x { p[n[p][x]] } } }
[-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }
[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x
{ p[p[p[p[p[x]]]]] } }]]]][-> b { b }[-> n { n[-> x { -> x { -> y { y } } }][-
> x { -> y { x } }] }[-> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x]
[y] }] }] }[-> f { -> m { -> n { -> b { b }[-> m { -> n { -> n { n[-> x { -> x
{ -> y { y } } }][-> x { -> y { x } }] }[-> m { -> n { n[-> n { -> p { p[-> x
{ -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p { p[-> x { -
> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x { -> y
{ y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x { x } }][-> p
{ -> x { x } }]]] }][m] } }[m][n]] } }[n][m]][-> x { f[-> m { -> n { n[-> n { -
> p { p[-> x { -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p
{ p[-> x { -> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-
> x { -> y { y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x
{ x } }][-> p { -> x { x } }]]] }][m] } }[m][n]][n][x] }][m] } } }][n][-> p { -
> x { p[p[p[x]]] } }]]][-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x
{ -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { ->
x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x]
[y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -
> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x
{ -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x]
[y] } } }[x][l]] } }[-> x { -> y { -> f { f[x][y] } } }[-> x { -> y { x } }][-
> x { -> y { x } }]][-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x
{ p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x
{ p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p]
[x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p
{ -> x { p[p[p[p[p[x]]]]] } }]]]]]]][-> n { -> p { -> x { p[n[p][x]] } } }[-> n
{ -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -
> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { ->
x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x
{ p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]]]][-> n { -> p { -> x
{ p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m
{ -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x
{ x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]]
[-> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -
> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x
{ p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]][-> b { b }[-> n { n[-> x
{ -> x { -> y { y } } }][-> x { -> y { x } }] }[-> f { -> x { f[-> y { x[x]
[y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> m { -> n { -> b { b }[-> m
{ -> n { -> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> m { -
> n { n[-> n { -> p { p[-> x { -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x]
[y] } } }[-> p { p[-> x { -> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }
[-> p { p[-> x { -> y { y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[->
p { -> x { x } }][-> p { -> x { x } }]]] }][m] } }[m][n]] } }[n][m]][-> x { f[-
> m { -> n { n[-> n { -> p { p[-> x { -> y { x } }] }[n[-> p { -> x { -> y { -
> f { f[x][y] } } }[-> p { p[-> x { -> y { y } }] }[p]][-> n { -> p { -> x
{ p[n[p][x]] } } }[-> p { p[-> x { -> y { y } }] }[p]]] }][-> x { -> y { -> f
{ f[x][y] } } }[-> p { -> x { x } }][-> p { -> x { x } }]]] }][m] } }[m][n]][n]
[x] }][m] } } }][n][-> p { -> x { p[p[p[p[p[x]]]]] } }]]][-> l { -> x { -> x { -
> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }
[x][l]] } }[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }]
[-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-> l { -> x { -> x { -> y { -> f
{ f[x][y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }
[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -
> y { -> f { f[x][y] } } }[x][l]] } }[-> x { -> y { -> f { f[x][y] } } }[-> x
{ -> y { x } }][-> x { -> y { x } }]][-> n { -> p { -> x { p[n[p][x]] } } }[->
n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n
{ -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { -
> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x
{ p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]]]][-> n { -> p { -> x
{ p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x
{ p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m
{ -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x
{ x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]]]]
[-> n { -> p { -> x { p[n[p][x]] } } }[-> n { -> p { -> x { p[n[p][x]] } } }[-
> n { -> p { -> x { p[n[p][x]] } } }[-> m { -> n { n[-> m { -> n { n[-> n { ->
p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x
{ p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]]]]][-> m { -> n { n[-> m { -
> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-> p { -> x { x } }] } }
[-> p { -> x { p[p[x]] } }][-> p { -> x { p[p[p[p[p[x]]]]] } }]]][-> f { -> x
{ f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f { -> n { -> l { -
> x { -> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-> y { x[x][y] }] }] }[-> f
{ -> l { -> x { -> g { -> b { b }[-> p { p[-> x { -> y { x } }] }[l]][x][-> y
{ g[f[-> l { -> p { p[-> x { -> y { y } }] }[-> p { p[-> x { -> y { y } }] }
[l]] }[l]][x][g]][-> l { -> p { p[-> x { -> y { y } }] }[-> p { p[-> x { -> y
{ y } }] }[l]] }[l]][y] }] } } } }][l][-> l { -> x { -> x { -> y { -> f { f[x]
[y] } } }[-> x { -> y { y } }][-> x { -> y { -> f { f[x][y] } } }[x][l]] } }[-
> x { -> y { -> f { f[x][y] } } }[-> x { -> y { x } }][-> x { -> y { x } }]][x]]
[-> l { -> x { -> x { -> y { -> f { f[x][y] } } }[-> x { -> y { y } }][-> x { -
> y { -> f { f[x][y] } } }[x][l]] } }] } }[-> b { b }[-> m { -> n { -> n { n[-
> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> m { -> n { n[-> n { -> p
{ p[-> x { -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p { p[-
> x { -> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x
{ -> y { y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x { x } }]
[-> p { -> x { x } }]]] }][m] } }[m][n]] } }[n][-> n { -> p { p[-> x { -> y
{ x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p { p[-> x { -> y
{ y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x { -> y
{ y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x { x } }][-> p
{ -> x { x } }]]] }[-> m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p]
[x]] } } }][m] } }[m]][-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p
{ -> x { p[p[p[p[p[x]]]]] } }]]]][-> x { -> y { -> f { f[x][y] } } }[-> x { ->
y { x } }][-> x { -> y { x } }]][-> x { f[-> f { -> x { f[-> y { x[x][y] }] }[-
> x { f[-> y { x[x][y] }] }] }[-> f { -> m { -> n { -> b { b }[-> m { -> n { -
> n { n[-> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> m { -> n { n[-
> n { -> p { p[-> x { -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }
[-> p { p[-> x { -> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p
{ p[-> x { -> y { y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -
> x { x } }][-> p { -> x { x } }]]] }][m] } }[m][n]] } }[n][m]][-> x { -> n { -
> p { -> x { p[n[p][x]] } } }[f[-> m { -> n { n[-> n { -> p { p[-> x { -> y
{ x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p { p[-> x { -> y
{ y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x { -> y
{ y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x { x } }][-> p
{ -> x { x } }]]] }][m] } }[m][n]][n]][x] }][-> p { -> x { x } }] } } }][n][->
m { -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]]
[-> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x
{ p[p[p[p[p[x]]]]] } }]]][x] }]][-> f { -> x { f[-> y { x[x][y] }] }[-> x { f[-
> y { x[x][y] }] }] }[-> f { -> m { -> n { -> b { b }[-> m { -> n { -> n { n[-
> x { -> x { -> y { y } } }][-> x { -> y { x } }] }[-> m { -> n { n[-> n { -> p
{ p[-> x { -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }[-> p { p[-
> x { -> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p { p[-> x
{ -> y { y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -> x { x } }]
[-> p { -> x { x } }]]] }][m] } }[m][n]] } }[n][m]][-> x { f[-> m { -> n { n[-
> n { -> p { p[-> x { -> y { x } }] }[n[-> p { -> x { -> y { -> f { f[x][y] } } }
[-> p { p[-> x { -> y { y } }] }[p]][-> n { -> p { -> x { p[n[p][x]] } } }[-> p
{ p[-> x { -> y { y } }] }[p]]] }][-> x { -> y { -> f { f[x][y] } } }[-> p { -
> x { x } }][-> p { -> x { x } }]]] }][m] } }[m][n]][n][x] }][m] } } }][n][-> m
{ -> n { n[-> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }[m]][-
> p { -> x { x } }] } }[-> p { -> x { p[p[x]] } }][-> p { -> x
{ p[p[p[p[p[x]]]]] } }]]] } }][n]]]] }]

太漂亮了。

6.1.11　高级编程技术

构建完全由proc 组成的程序需要很多努力，但我们已经明白只要不介意应用一些技巧，完成实际工作是可能的。来快速看一下用这个最小环境写代码的其他几个技术。

1. 无限流

使用代码表示数据有一些有趣的优点。我们基于proc 的列表不一定是静态的：列表也是代码，在我们传递它给FIRST 和REST 时它能做正确的事情，因此很容易实现能动态计算自身内容的列表，也就是流（stream）。事实上，流没有理由是有限的，因为计算只需要根据需要生成列表的内容就可以了，所以它可以一直无限产生新的值。

例如，下面是一个零组成的无限流的实现：

ZEROS = Z[-> f { UNSHIFT[f][ZERO] }]

这是ZEROS = UNSHIFT[ZEROS][ZERO]的“无欺骗”版本，即用它自身定义的数据结构。作为一个程序员，我们通常会觉得用自身定义一个递归函数的思想很舒服，但用自身定义一个数据结构看起来很怪异；在这种情况下，它们几乎是同样的东西，而Z 组合子让两者都完全合理了。

在控制台上，我们可以看到ZEROS 表现得就像一个列表，尽管这个列表看不到尽头：

>> to_integer(FIRST[ZEROS])
=> 0
>> to_integer(FIRST[REST[ZEROS]])
=> 0
>> to_integer(FIRST[REST[REST[REST[REST[REST[ZEROS]]]]]])
=> 0

能有一个辅助方法把这个流转成一个Ruby 的数组会很方便，但to_array会永远运行下去，直到我们明确地让这个转换进程停下来为止。一个可选的“最大数”的参数可以做到这一点：

def to_array(l, count = nil)
  array = []

  until to_boolean(IS_EMPTY[l]) || count == 0
    array.push(FIRST[l])
    l = REST[l]
    count = count - 1 unless count.nil?
end

  array
end

这让我们可以从流中获取任意数目的元素并把它们转成一个数组：

>> to_array(ZEROS, 5).map { |p| to_integer(p) }
=> [0, 0, 0, 0, 0]
>> to_array(ZEROS, 10).map { |p| to_integer(p) }
=> [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
>> to_array(ZEROS, 20).map { |p| to_integer(p) }
=> [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

ZEROS不会每次都对一个新的元素进行计算，但做起来也非常简单。下面是一个从给定值累加的流：

>> UPWARDS_OF = Z[-> f { -> n { UNSHIFT[-> x { f[INCREMENT[n]][x] }][n] } }]
=> #<Proc (lambda)>
>> to_array(UPWARDS_OF[ZERO], 5).map { |p| to_integer(p) }
=> [0, 1, 2, 3, 4]
>> to_array(UPWARDS_OF[FIFTEEN], 20).map { |p| to_integer(p) }
=> [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34]

下面是一个包含一个给定数字所有倍数的流：

>> MULTIPLES_OF =
    -> m {
      Z[-> f {
        -> n { UNSHIFT[-> x { f[ADD[m][n]][x] }][n] }
        }][m]
    }
=> #<Proc (lambda)>
>> to_array(MULTIPLES_OF[TWO], 10).map { |p| to_integer(p) }
=> [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
>> to_array(MULTIPLES_OF[FIVE], 20).map { |p| to_integer(p) }
=> [5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100]

我们可以像其他列表一样操纵这些无限流。例如，可以通过对已有的proc 映射一个新的proc 得到一个新的流：

>> to_array(MULTIPLES_OF[THREE], 10).map { |p| to_integer(p) }
=> [3, 6, 9, 12, 15, 18, 21, 24, 27, 30]
>> to_array(MAP[MULTIPLES_OF[THREE]][INCREMENT], 10).map { |p| to_integer(p) }
=> [4, 7, 10, 13, 16, 19, 22, 25, 28, 31]
>> to_array(MAP[MULTIPLES_OF[THREE]][MULTIPLY[TWO]], 10).map { |p| to_integer(p) }
=> [6, 12, 18, 24, 30, 36, 42, 48, 54, 60]

甚至可以写一个proc 把两个流组合成第三个流：

>> MULTIPLY_STREAMS =
Z[-> f {
-> k { -> l {
UNSHIFT[-> x { f[REST[k]][REST[l]][x] }][MULTIPLY[FIRST[k]][FIRST[l]]]
} }
}]
=> #<Proc (lambda)>
>> to_array(MULTIPLY_STREAMS[UPWARDS_OF[ONE]][MULTIPLES_OF[THREE]], 10).
map { |p| to_integer(p) }
=> [3, 12, 27, 48, 75, 108, 147, 192, 243, 300]

因为流的内容能由任何计算生成，所以我们创建斐波那契数列的无限列表，或者质数，或者按字母顺序的所有可能的字符串，或者任何其他可计算的东西都已经没有障碍了。这个抽象非常强大，除了已有的特性之外不需要任何智能的特性了。

原始Ruby 流

Ruby 有一个Enumerator类可以用来构建无限的流，而不需要依赖proc。下面是“给定数的倍数”的流的实现方法：

def multiples_of(n)
  Enumerator.new do |yielder|
    value = n
    loop do
      yielder.yield(value)
      value = value + n
    end
  end
end

这个方法返回一个Enumerator，每次我们对其调用#next，它都会执行loop的一个迭代并返回获得的值：

> multiples_of_three = multiples_of(3)
=> #<Enumerator: #<Enumerator::Generator>:each>
> multiples_of_three.next
=> 3
> multiples_of_three.next
=> 6
> multiples_of_three.next
=> 9

Enumerator类包括了Enumerable模块，因此我们可以调用#first、#take和#detect这样的方法：

> multiples_of(3).first
=> 3
> multiples_of(3).take(10)
=> [3, 6, 9, 12, 15, 18, 21, 24, 27, 30]
> multiples_of(3).detect { |x| x > 100 }
=> 102

其他的Enumerable方法，如#map和#select，在这个Enumerator上没法正常工作，因为它们会尝试处理这个无限流中的每一项。但是，Ruby 2.0 的Enumerator::Lazy类重新实现了一些Enumerable方法，这样它们在依赖的Enumerator继续计数时仍然可以工作。我们可以通过在一个Enumerator上调用#lazy 来获得一个Enumerator::Lazy，然后可以像之前操纵proc 版本一样操纵这些无限流：

> multiples_of(3).lazy.map { |x| x * 2 }.take(10).force
=> [6, 12, 18, 24, 30, 36, 42, 48, 54, 60]
> multiples_of(3).lazy.map { |x| x * 2 }.select { |x| x > 100 }.take(10).force
=> [102, 108, 114, 120, 126, 132, 138, 144, 150, 156]
> multiples_of(3).lazy.zip(multiples_of(4)).map { |a, b| a * b }.take(10).force
=> [12, 48, 108, 192, 300, 432, 588, 768, 972, 1200]

与基于proc 的列表相比，这不是很整洁（为了处理无限流，我们得写一些特殊的代码，而不能只是像通常的Enumerable那样处理），但它表明Ruby 确实含有处理这些不寻常数据结构的内建方式。

2. 避免随意递归

在FizzBuzz 练习里，我们使用MOD和RANGE这样的递归函数展示了Z 组合子的用法。这很方便，因为它让我们从一个没有约束的递归的Ruby 实现转换成一个基于proc 的实现，而不必改变代码结构，但是从技术上讲，没有Z 组合子我们也可以利用邱奇数的行为来实现这些函数。

例如，MOD[m][n]的实现方法是，只要n<=m就不断地从m中减去n，并且总是检查这个条件以决定是否进行下一次的递归调用。但如果只是对“如果n <= m就从m中减去n”这个动作执行固定的次数，而不是使用递归动态控制这个重复的过程，也可以得到同样的结果。我们不知道需要重复的确切次数，但知道m次肯定够了（最差情况就是n为1），而且多做几次也无碍：

def decrease(m, n)
  if n <= m
    m - n
  else
    m
  end
end
>> decrease(17, 5)
=> 12
>> decrease(decrease(17, 5), 5)
=> 7
>> decrease(decrease(decrease(17, 5), 5), 5)
=> 2
>> decrease(decrease(decrease(decrease(17, 5), 5), 5), 5)
=> 2
>> decrease(decrease(decrease(decrease(decrease(17, 5), 5), 5), 5), 5)
=> 2

因此我们可以重写MOD以利用一个proc，这个proc 的参数是一个数，它或是从这个数中减去m（如果它比n 大）或是直接返回这个数。这个proc 对m本身调用m次，以便获得最终的答案：

MOD =
  -> m { -> n {
    m[-> x {
      IF[IS_LESS_OR_EQUAL[n][x]][
        SUBTRACT[x][n]
      ][
        x
      ]
    }][m]
  } }

MOD的这个版本与递归版本工作得一样出色：

>> to_integer(MOD[THREE][TWO])
=> 1
>> to_integer(MOD[
    POWER[THREE][THREE]
  ][
    ADD[THREE][TWO]
  ])
=> 2

尽管这个实现比原来的实现简单，但它不仅难以阅读而且通常效率更低，因为它总是会执行重复调用的最差情况下的次数而不是尽可能早地停下来。在外延上它也与原来的实现不等价，因为老版本的MOD如果被要求除零的话会永远循环下去（条件n<=m永远不会为false），而这个实现只是返回它的第一个参数：

>> to_integer(MOD[THREE][ZERO])
=> 3

RANGE更有挑战一些，但我们可以使用与让DECREMENT工作时类似的技巧：设计一个函数，在对某个初始参数调用n次时，它会从预想的范围里返回n个数的列表。就像DECREMENT一样，秘诀是使用一个有序对存储结果的列表和在下一个迭代中需要的信息：

def countdown(pair)
  [pair.first.unshift(pair.last), pair.last - 1]
end

>> countdown([[], 10])
=> [[10], 9]
>> countdown(countdown([[], 10]))
=> [[9, 10], 8]
>> countdown(countdown(countdown([[], 10])))
=> [[8, 9, 10], 7]
>> countdown(countdown(countdown(countdown([[], 10]))))
=> [[7, 8, 9, 10], 6]

重写proc 很容易：

COUNTDOWN = -> p { PAIR[UNSHIFT[LEFT[p]][RIGHT[p]]][DECREMENT[RIGHT[p]]] }

现在我们只需要实现RANGE 以便它调用COUNTDOWN正确的次数（从m到n 的范围内总是有m-n+1个元素）并从最终的有序对中取出结果列表：

RANGE = -> m { -> n { LEFT[INCREMENT[SUBTRACT[n][m]][COUNTDOWN][PAIR[EMPTY][n]]] } }

这个无组合子的版本工作得也很好：

>> to_array(RANGE[FIVE][TEN]).map { |p| to_integer(p) }
=> [5, 6, 7, 8, 9, 10]
`

可以通过执行事先决定好次数的迭代来实现MOD和RANGE`——而不是执行一个会一直运行直到条件变为true 才停止的任意的循环——因为它们是原始递归函数。参见7.2节可以了解更多内容。