Question

就像 lambda 演算一样，SKI 组合子演算是一个处理表达式语法的规则系统。尽管 lambda 演算已经很简单了，但仍然还有三种表达式：变量、函数和调用。我们在 6.2.2 节中看到变量使规约的规则有点复杂。SKI 演算更简单，它只有两种表达式：调用和字母符号，规则也更简单。它所有的能力都源于三个特别的符号 S、K 和I（叫作组合子），它们每一个都有自己的归约规则：

· S[a][b][c] 规约成a[c][b[c]]，其中 a、b 和 c 可以是任意的 SKI 演算表达式；

· K[a][b] 规约成a； -I[a]规约成 a。

例如，下面是规约表达式 I[S][K][S][I[K]] 的一种方式：

I[S][K][S][I[K]] → S[K][S][I[K]] ( 规约 I[S] 为 S)
         → S[K][S][K] ( 规约 I[K] 为 K)
         → K[K][S[K]] ( 规约 S[K][S][K] 为 K[K][S[K]])
         → K (reduce K[K][S[K]] 为 K)

注意，这里没有 lambda 演算那种变量替换，有的只是根据规约规则对符号进行的记录、复制和丢弃。

很容易实现 SKI 表达式的抽象语法：

class SKISymbol < Struct.new(:name)
  def to_s
    name.to_s
  end

  def inspect
    to_s
  end
end

class SKICall < Struct.new(:left, :right)
  def to_s
    "#{left}[#{right}]"
  end

  def inspect
    to_s
  end
end

class SKICombinator < SKISymbol
end

S, K, I = [:S, :K, :I].map { |name| SKICombinator.new(name) }

为了一般性地表示调用和符号，这里我们定义了类 SKICall 和 SKISymbol，然后创建了一次性实例 S、K 和 I 来表示作为组合子的那些特定符号。

我们没有直接让 S、K 和 I 成为 SKISymbol 的实例，而是使用了子类 SKICominator的实例。这对我们现在没有帮助，但是它会简化以后往三个组合子对象中增加方法的工作。

这些类和对象能被用来构建 SKI 表达式的抽象语法树：

>> x = SKISymbol.new(:x)
=> x
>> expression = SKICall.new(SKICall.new(S, K), SKICall.new(I, x))
=> S[K][I[x]]

通过实现 SKI 演算的规约规则并在表达式中应用这些规则可以为 SKI 演算赋予一个小步操作语义。首先，我们将在 SKICombinator 实例上定义一个叫作#call 的方法；S、K 和 I 都有它们自己 #call 的定义，实现了它们的归约规则：

# 规约 S[a][b][c] 为 a[c][b[c]]
def S.call(a, b, c)
  SKICall.new(SKICall.new(a, c), SKICall.new(b, c))
end

# 规约 K[a][b] 为 o a
def K.call(a, b)
  a
end

# 规约 I[a] 为 a
def I.call(a)
  a
end

好了，如果知道调用组合子的参数是什么，我们就有了一种应用演算规则的方式……

>> y, z = SKISymbol.new(:y), SKISymbol.new(:z)
=> [y, z]
>> S.call(x, y, z)
=> x[z][y[z]]

……但要对一个真正的 SKI 表达式使用 #call 方法，我们还需要从中提取出一个组合子和几个参数。因为一个表达式是用一个 SKICall 对象组成的二叉树表示的，所以这有点繁琐：

>> expression = SKICall.new(SKICall.new(SKICall.new(S, x), y), z)
=> S[x][y][z]
>> combinator = expression.left.left.left
=> S
>> first_argument = expression.left.left.right
=> x
>> second_argument = expression.left.right
=> y
>> third_argument = expression.right
=> z
>> combinator.call(first_argument, second_argument, third_argument)
=> x[z][y[z]]

为了让这个结构更容易处理，我们可以在抽象语法树上定义方法 #combinator 和 #arguments：

class SKISymbol
  def combinator
    self
  end

  def arguments
    []
  end
end

class SKICall
  def combinator
    left.combinator
  end

  def arguments
    left.arguments + [right]
  end
end

这样很容易发现要调用哪个组合子以及传给它什么参数：

>> expression
=> S[x][y][z]
>> combinator = expression.combinator
=> S
>> arguments = expression.arguments
=> [x, y, z]
>> combinator.call(*arguments)
=> x[z][y[z]]

这对 S[x][y][z] 工作得很好，但在通常情况下会有一些问题。首先 #combinator 方法只是返回一个表达式最左侧的符号，但那个符号不一定是个组合子：

>> expression = SKICall.new(SKICall.new(x, y), z)
=> x[y][z]
>> combinator = expression.combinator
=> x
>> arguments = expression.arguments
=> [y, z]
>> combinator.call(*arguments)
NoMethodError: undefined method `call' for x:SKISymbol

第二，就算最左侧的符号是一个组合子，它也不一定被用合适数目的参数调用：

>> expression = SKICall.new(SKICall.new(S, x), y)
=> S[x][y]
>> combinator = expression.combinator
=> S
>> arguments = expression.arguments
=> [x, y]
>> combinator.call(*arguments)
ArgumentError: wrong number of arguments (2 for 3)

为了避免这两个问题，我们将定义 #callable? 方法以检测是否适合以方法 #combinator 和#argument 的结果来使用 #call。一个符号永远都无法调用，而一个组合子只有在参数个数正确的情况下才可以调用：

class SKISymbol
  def callable?(*arguments)
    false
  end
end

  def S.callable?(*arguments)
    arguments.length == 3
  end

  def K.callable?(*arguments)
    arguments.length == 2
  end

  def I.callable?(*arguments)
    arguments.length == 1
  end

顺便说一下，Ruby 已经有办法回答一个方法需要多少个参数了（它的参数数量）：

> def add(x, y)
    x + y
  end
=> nil
> add_method = method(:add)
=> #<Method: Object#add>
> add_method.arity
=> 2

因此，我们可以用一个共享 #callable 实现来替换 S、K 和 I 各自的实现：

class SKICombinator
  def callable?(*arguments)
    arguments.length == method(:call).arity
  end
end

现在可以识别归约规则直接适用的表达式了：

> expression = SKICall.new(SKICall.new(x, y), z)
=> x[y][z]
> expression.combinator.callable?(*expression.arguments)
=> false
> expression = SKICall.new(SKICall.new(S, x), y)
=> S[x][y]
> expression.combinator.callable?(*expression.arguments)
=> false
> expression = SKICall.new(SKICall.new(SKICall.new(S, x), y), z)
=> S[x][y][z]
> expression.combinator.callable?(*expression.arguments)
=> true

最后，我们可以为 SKI 表达式实现熟悉的 #reducible? 和 #reduce 方法了：

class SKISymbol
  def reducible?
    false
  end
end

class SKICall def reducible? left.reducible? || right.reducible? || combinator.callable?(*arguments) end

def reduce
  if left.reducible?
    SKICall.new(left.reduce, right)
  elsif right.reducible?
    SKICall.new(left, right.reduce)
  else
    combinator.call(*arguments)
  end
end

end

SKICall#reduce 递归查找我们已经知道如何规约的子表达式（例如正在以三个参数进行调用的 S 组合子），然后使用 #call 应用合适的规则。

那就是它了！我们现在可以对 SKI 表达式不断规约，直到不能规约为止。例如，下面使用符号 x 和 y 调用表达式 S[K[S[I]]][K]，它交换了两个参数的顺序：

>> swap = SKICall.new(SKICall.new(S, SKICall.new(K, SKICall.new(S, I))), K)
=> S[K[S[I]]][K]
>> expression = SKICall.new(SKICall.new(swap, x), y)
=> S[K[S[I]]][K][x][y]
>> while expression.reducible?
    puts expression
    expression = expression.reduce
  end; puts expression
S[K[S[I]]][K][x][y]
K[S[I]][x][K[x]][y]
S[I][K[x]][y]
I[y][K[x][y]]
y[K[x][y]]
y[x]
=> nil

SKI 演算用三个简单的规则就产生了出人意料的复杂行为。事实上，复杂到被证明是通用的了。我们可以证明 SKI 表达式的通用性，方法是展示如何把任意的 lambda 演算表达式转换成做同样事情的一个 SKI 表达式，这实际上也是使用 SKI 演算给了 lambda 演算一个指称语义。我们已经知道 lambda 演算是通用的，因此如果 SKI 能完全模拟它，就能得出SKI 演算也是通用的结论。

转换的核心是一个叫 #as_a_function_of 的方法：

class SKISymbol
  def as_a_function_of(name)
    if self.name == name
      I
    else
      SKICall.new(K, self)
    end
  end
end

class SKICombinator
  def as_a_function_of(name)
    SKICall.new(K, self)
  end
end

class SKICall
  def as_a_function_of(name)
    left_function = left.as_a_function_of(name)
    right_function = right.as_a_function_of(name)

    SKICall.new(SKICall.new(S, left_function), right_function)
  end
end

方法 #as_a_function_of 的工作细节并不重要，但粗略上讲，它把一个 SKI 表达式转成一个新的表达式，这个表达式在用一个参数调用时会转回到原来的表达式。例如，表达式S[K][I] 被转成S[S[K[S]][K[K]]][K[I]]：

>> original = SKICall.new(SKICall.new(S, K), I)
=> S[K][I]
>> function = original.as_a_function_of(:x)
=> S[S[K[S]][K[K]]][K[I]]
>> function.reducible?
=> false

在S[S[K[S]][K[K]]][K[I]] 以一个参数比如说 y 进行调用的时候，它将会规约回 S[K][I]：

>> expression = SKICall.new(function, y)
=> S[S[K[S]][K[K]]][K[I]][y]
>> while expression.reducible?
    puts expression
    expression = expression.reduce
  end; puts expression
S[S[K[S]][K[K]]][K[I]][y]
S[K[S]][K[K]][y][K[I][y]]
K[S][y][K[K][y]][K[I][y]]
S[K[K][y]][K[I][y]]
S[K][K[I][y]]
S[K][I]
=> nil
>> expression == original
=> true

只是在原始表达式也包含有那个名字的符号时参数name 才会用到。在那种情况下，#as_a_function_of 会产生一些更有意思的东西：一个表达式，在使用一个参数进行调用的时候，它会规约成原始表达式，其中那个参数会替换掉符号：

>> original = SKICall.new(SKICall.new(S, x), I)
=> S[x][I]
>> function = original.as_a_function_of(:x)
=> S[S[K[S]][I]][K[I]]
>> expression = SKICall.new(function, y)
=> S[S[K[S]][I]][K[I]][y]
>> while expression.reducible?
    puts expression
    expression = expression.reduce
  end; puts expression
S[S[K[S]][I]][K[I]][y]
S[K[S]][I][y][K[I][y]]
K[S][y][I[y]][K[I][y]]
S[I[y]][K[I][y]]
S[y][K[I][y]]
S[y][I]
=> nil
>> expression == original
=> false

一个 lambda 演算函数在被调用时，函数体内的变量会被替换掉，上面是对这种方式的一个明确的重新实现。本质上说，#as_a_function_of给了我们使用 SKI 表达式作为函数体的方法：它创建了一个新的表达式，这个表达式的行为就像带有一个特定函数体和一个参数名的函数，只不过 SKI 演算没有函数语法而已。

SKI 演算模拟函数的能力把 lambda 演算表达式与 SKI 表达式的转换变得直接。lambda演算变量和调用成为了 SKI 演算的符号和调用，而每一个 lambda 演算函数体用 #as_a_function_of转成了一个 SKI 演算“函数”：

class LCVariable
  def to_ski
    SKISymbol.new(name)
  end
end

class LCCall
  def to_ski
    SKICall.new(left.to_ski, right.to_ski)
  end
end

class LCFunction
  def to_ski
    body.to_ski.as_a_function_of(parameter)
  end
end

让我们通过把数字“2”（参见 6.1.3 节）的 lambda 演算表示转成 SKI 演算来检查一下这个转换：

>> two = LambdaCalculusParser.new.parse('-> p { -> x { p[p[x]] } }').to_ast
=> -> p { -> x { p[p[x]] } }
>> two.to_ski
=> S[S[K[S]][S[K[K]][I]]][S[S[K[S]][S[K[K]][I]]][K[I]]]

SKI 演算表达式S[S[K[S]][S[K[K]][I]]][S[S[K[S]][S[K[K]][I]]][K[I]]] 与->p{->x{p[p[x]]}}做的事情一样吗？应该是在其第二个参数上调用它的第一个参数两次，因此我们可以尝试给它一些参数来看看它实际是怎么做的，就像在 6.2.2 节看到的那样：

>> inc, zero = SKISymbol.new(:inc), SKISymbol.new(:zero)
=> [inc, zero]
>> expression = SKICall.new(SKICall.new(two.to_ski, inc), zero)
=> S[S[K[S]][S[K[K]][I]]][S[S[K[S]][S[K[K]][I]]][K[I]]][inc][zero]
>> while expression.reducible?
    puts expression
    expression = expression.reduce
  end; puts expression
S[S[K[S]][S[K[K]][I]]][S[S[K[S]][S[K[K]][I]]][K[I]]][inc][zero]
S[K[S]][S[K[K]][I]][inc][S[S[K[S]][S[K[K]][I]]][K[I]][inc]][zero]
K[S][inc][S[K[K]][I][inc]][S[S[K[S]][S[K[K]][I]]][K[I]][inc]][zero]
S[S[K[K]][I][inc]][S[S[K[S]][S[K[K]][I]]][K[I]][inc]][zero]
S[K[K][inc][I[inc]]][S[S[K[S]][S[K[K]][I]]][K[I]][inc]][zero]
S[K[I[inc]]][S[S[K[S]][S[K[K]][I]]][K[I]][inc]][zero]
S[K[inc]][S[S[K[S]][S[K[K]][I]]][K[I]][inc]][zero]
S[K[inc]][S[K[S]][S[K[K]][I]][inc][K[I][inc]]][zero]
S[K[inc]][K[S][inc][S[K[K]][I][inc]][K[I][inc]]][zero]
S[K[inc]][S[S[K[K]][I][inc]][K[I][inc]]][zero]
S[K[inc]][S[K[K][inc][I[inc]]][K[I][inc]]][zero]
S[K[inc]][S[K[I[inc]]][K[I][inc]]][zero]
S[K[inc]][S[K[inc]][K[I][inc]]][zero]
S[K[inc]][S[K[inc]][I]][zero]
K[inc][zero][S[K[inc]][I][zero]]
inc[S[K[inc]][I][zero]]
inc[K[inc][zero][I[zero]]]
inc[inc[I[zero]]]
inc[inc[zero]]
=> nil

可以确定了，使用叫 inc 和 zero 的符号调用转换过的表达式求值为 inc[inc[zero]]，这正是我们所想要的。同样的转换对任何其他 lambda 表达式也能成功执行，因此 SKI 组合子演算可以完全模拟 lambda 演算，从而它一定是通用的。

尽管 SKI 演算有三个组合子，但 I 组合子实际上是冗余的。有许多表达式只含有 S和K，它们做的事情和 I 一样；例如 S[K][K]：

> identity = SKICall.new(SKICall.new(S, K), K)
=> S[K][K]
> expression = SKICall.new(identity, x)
=> S[K][K][x]
> while expression.reducible?
    puts expression
    expression = expression.reduce
  end; puts expression
S[K][K][x]
K[x][K[x]]
x
=> nil

可见 S[K][K] 的行为与I一样，这对任何形式为 S[K][ 任意 ] 的 SKI 表达式都成立。I 组合子是我们非必需的语法糖。对于通用性来说，两个组合子 S 和 K 就足够了。