SKI 组合系统

Created: November-22, 2018

该 SKI 组合子系统是足以代表任何演算方面。（实际上，当它们被转换成 SKI 时，lambda 抽象会爆炸成指数大小。）由于系统的简单性，实现 S，K 和 I 组合器非常简单：

从 Lambda 微积分直接翻译

const S = f -> g -> z -> f(z)(g(z))
const K = x -> y -> x
const I = x -> x

我们可以使用单元测试系统确认每个组合器具有预期的行为。

I 组合器最容易验证; 它应该返回给定的值不变：

using Base.Test
@test I(1) === 1
@test I(I) === I
@test I(S) === S

K 组合器也相当简单：它应该丢弃它的第二个参数。

@test K(1)(2) === 1
@test K(S)(I) === S

S 组合器是最复杂的; 它的行为可以概括为将前两个参数应用于第三个参数，将第一个结果应用于第二个参数。我们可以通过测试一些咖喱形式来最容易地测试 S 组合器。例如，S(K) 应该简单地返回它的第二个参数并丢弃它的第一个参数，正如我们看到的那样：

@test S(K)(S)(K) === K
@test S(K)(S)(I) === I

S(I)(I) 应该将自己的论点应用于自身：

@test S(I)(I)(I) === I
@test S(I)(I)(K) === K(K)
@test S(I)(I)(S(I)) === S(I)(S(I))

S(K(S(I)))(K) 将第二个参数应用于第一个参数：

@test S(K(S(I)))(K)(I)(I) === I
@test S(K(S(I)))(K)(K)(S(K)) === S(K)(K)

上面描述的 I 组合器在标准 Base Julia：identity 中有一个名字。因此，我们可以用 I 的以下替代定义重写上述定义：

const I = identity

显示 SKI 组合器

上述方法的一个弱点是我们的功能并不像我们想象的那样好。我们可以替换吗？

julia> S
(::#3) (generic function with 1 method)

julia> K
(::#9) (generic function with 1 method)

julia> I
(::#13) (generic function with 1 method)

有一些更丰富的信息显示？答案是肯定的！让我们重新启动 REPL，这次定义每个函数的显示方式：

const S = f -> g -> z -> f(z)(g(z));
const K = x -> y -> x;
const I = x -> x;
for f in (:S, :K, :I)
    @eval Base.show(io::IO, ::typeof($f)) = print(io, $(string(f)))
    @eval Base.show(io::IO, ::MIME"text/plain", ::typeof($f)) = show(io, $f)
end

在完成函数定义之前，避免显示任何内容非常重要。否则，我们可能会使方法缓存失效，并且我们的新方法似乎不会立即生效。这就是为什么我们在上面的定义中加上分号。分号抑制了 REPL 的输出。

这使得函数显示得很好：

julia> S
S

julia> K
K

julia> I
I

但是，当我们尝试显示闭包时，我们仍会遇到问题：

julia> S(K)
(::#2) (generic function with 1 method)

将它显示为 S(K) 会更好。要做到这一点，我们必须利用闭包具有各自的类型。我们可以使用 typeof 和类型的 name 字段的 primary 字段来访问这些类型并通过反射向它们添加方法。再次重启 REPL; 我们会做出进一步的改变：

const S = f -> g -> z -> f(z)(g(z));
const K = x -> y -> x;
const I = x -> x;
for f in (:S, :K, :I)
    @eval Base.show(io::IO, ::typeof($f)) = print(io, $(string(f)))
    @eval Base.show(io::IO, ::MIME"text/plain", ::typeof($f)) = show(io, $f)
end
Base.show(io::IO, s::typeof(S(I)).name.primary) = print(io, "S(", s.f, ')')
Base.show(io::IO, s::typeof(S(I)(I)).name.primary) =
    print(io, "S(", s.f, ')', '(', s.g, ')')
Base.show(io::IO, k::typeof(K(I)).name.primary) = print(io, "K(", k.x, ')')
Base.show(io::IO, ::MIME"text/plain", f::Union{
    typeof(S(I)).name.primary,
    typeof(S(I)(I)).name.primary,
    typeof(K(I)).name.primary
}) = show(io, f)

现在，最后，事情按照我们希望的方式显示：

julia> S(K)
S(K)

julia> S(K)(I)
S(K)(I)

julia> K
K

julia> K(I)
K(I)

julia> K(I)(K)
I