Julia Language
コンビネーション

備考

YまたはZ結合子

Juliaは純粋に関数型言語ではありませんが、ファーストクラスの関数 、レキシカルスコープ、 クロージャなど、関数型プログラミングの基盤の多くを完全にサポートしています。

固定小数点コンビネータは、関数型プログラミングの主要なコンビネータです。 Juliaは評価のセマンティクスが非常に優れているため（Juliaの影響を受けているSchemeを含む多くの関数型言語がそうであるように）、CurryのオリジナルのY-combinatorはそのままでは動作しません。

Y(f) = (x -> f(x(x)))(x -> f(x(x)))

しかし、Y-コンビネータ、Z-コンビネータの親族は、実際には動作します：

Z(f) = x -> f(Z(f), x)

このコンビネータは関数をとり、引数xで呼び出されるとそれ自身とx渡す関数を返します。関数自体が渡されるのはなぜ有用なのでしょうか？これにより、関数の名前を実際に参照することなく、再帰が可能になります。

fact(f, x) = x == 0 ? 1 : x * f(x)

したがって、 Z(fact)は、この関数定義で再帰が可視ではないにもかかわらず、階乗関数の再帰的な実装になります。 （再帰はZコンビネータの定義で明らかですが、それは必然的な言葉では避けられません）。我々の関数が実際に動作することを検証することができます：

julia> Z(fact)(10)
3628800

それだけでなく、再帰的な実装から期待できるほど高速です。 LLVMコードは、結果が単純な古い分岐、減算、呼び出し、および乗算にコンパイルされることを示します。

julia> @code_llvm Z(fact)(10)

define i64 @"julia_#1_70252"(i64) #0 {
top:
  %1 = icmp eq i64 %0, 0
  br i1 %1, label %L11, label %L8

L8:                                               ; preds = %top
  %2 = add i64 %0, -1
  %3 = call i64 @"julia_#1_70060"(i64 %2) #0
  %4 = mul i64 %3, %0
  br label %L11

L11:                                              ; preds = %top, %L8
  %"#temp#.0" = phi i64 [ %4, %L8 ], [ 1, %top ]
  ret i64 %"#temp#.0"
}

SKIコンビネーションシステム

SKIコンビネータシステムは、任意のラムダ計算項を表現するのに十分である。 （実際には、ラムダ抽象化はSKIに変換されるときに指数関数的なサイズに吹き飛ばされます。）システムの単純さのために、S、K、Iコンバイナを実装することは非常に簡単です：

ラムダ微積分からの直接変換

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

ユニットテストシステムを使用して、各コンビネータが予想される動作をしていることを確認できます。

私のコンビネータは最も簡単に検証できます。与えられた値をそのまま返します。

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

Kコンビネータもかなり簡単です：それは2番目の引数を破棄する必要があります。

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

Sコンビネータは最も複雑です。その振る舞いは、最初の2つの引数を3番目の引数に適用し、最初の結果を2番目の引数に適用することとして要約できます。私たちは、カッティングされたフォームのいくつかをテストすることによって、Sコンビネータを最も簡単にテストすることができます。たとえば、 S(K) 、2番目の引数を返すだけで、最初の引数を破棄する必要があります。

@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)は、その第2引数を最初の引数に適用します。

@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コンビネータを表示

上記のアプローチの弱点の1つは、私たちの機能が好きかもしれないほどうまく表示されないということです。私たちは

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