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