Julia Language
Kombinatoren

Bemerkungen

Der Y- oder Z-Kombinator

Obwohl Julia keine rein funktionale Sprache ist, werden viele Eckpfeiler der funktionalen Programmierung vollständig unterstützt: erstklassige Funktionen , lexikalischer Umfang und Schließungen .

Der Festkomma-Kombinator ist ein Schlüsselkombinator für die Funktionsprogrammierung. Da Julia eine begierige Evaluierungssemantik hat (wie viele funktionale Sprachen, darunter auch Scheme, von dem Julia stark inspiriert ist), wird der ursprüngliche Y-Kombinator von Curry nicht sofort funktionieren:

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

Ein enger Verwandter des Y-Kombinators, der Z-Kombinator, wird jedoch tatsächlich funktionieren:

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

Dieser Kombinator akzeptiert eine Funktion und gibt eine Funktion zurück, die bei Aufruf mit Argument x selbst und x . Warum sollte es sinnvoll sein, eine Funktion selbst zu übergeben? Dies ermöglicht eine Rekursion, ohne den Namen der Funktion überhaupt zu referenzieren!

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

Daher wird Z(fact) eine rekursive Implementierung der Faktorfunktion, obwohl in dieser Funktionsdefinition keine Rekursion sichtbar ist. (Rekursion ist natürlich in der Definition des Z Kombinators offensichtlich, aber in einer eifrigen Sprache ist dies unvermeidlich.) Wir können überprüfen, ob unsere Funktion tatsächlich funktioniert:

julia> Z(fact)(10)
3628800

Nicht nur das, aber es ist so schnell, wie wir es von einer rekursiven Implementierung erwarten können. Der LLVM-Code demonstriert, dass das Ergebnis in einen einfachen alten Zweig, Subtrahieren, Aufruf und Multiplizieren kompiliert wird:

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"
}

Das SKI Combinator System

Das SKI-Kombinatorsystem reicht aus, um alle Begriffe der Lambda-Berechnung darzustellen. (In der Praxis werden Lambda-Abstraktionen natürlich auf exponentielle Größe gebracht, wenn sie in SKI übersetzt werden.) Aufgrund der Einfachheit des Systems ist die Implementierung der Kombinatoren S, K und I außerordentlich einfach:

Eine direkte Übersetzung aus dem Lambda-Kalkül

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

Mit dem Unit-Testing- System können wir bestätigen, dass jeder Kombinator das erwartete Verhalten aufweist.

Der I-Kombinator ist am einfachsten zu überprüfen. Der angegebene Wert sollte unverändert zurückgegeben werden:

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

Der K-Kombinator ist auch recht einfach: er sollte sein zweites Argument verwerfen.

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

Der S-Kombinator ist der komplexeste; Sein Verhalten kann als Anwendung der ersten beiden Argumente auf das dritte Argument zusammengefasst werden, wobei das erste Ergebnis auf das zweite angewendet wird. Wir können den S-Kombinator am einfachsten testen, indem wir einige der aktuellen Formen testen. S(K) zum Beispiel sollte einfach das zweite Argument zurückgeben und das erste Argument verwerfen, wie wir sehen:

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

S(I)(I) sollte sein Argument auf sich selbst anwenden:

@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) wendet sein zweites Argument auf das erste an:

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

Die I Kombinator oben beschrieben hat einen Namen in Standard - Base - Julia: identity . Daher könnten wir die obigen Definitionen mit der folgenden alternativen Definition von I umschreiben:

const I = identity

SKI-Kombinatoren anzeigen

Eine Schwachstelle bei dem oben beschriebenen Ansatz ist, dass unsere Funktionen nicht so gut angezeigt werden, wie wir es wünschen. Könnten wir ersetzen?

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

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

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

mit einigen informativen Anzeigen? Die Antwort ist ja! Lassen Sie uns die REPL neu starten, und definieren Sie diesmal, wie die einzelnen Funktionen angezeigt werden sollen:

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

Es ist wichtig zu vermeiden, dass etwas angezeigt wird, bis die Definition der Funktionen abgeschlossen ist. Andernfalls besteht die Gefahr, dass der Methodencache ungültig wird, und unsere neuen Methoden scheinen nicht sofort wirksam zu sein. Deshalb haben wir in den obigen Definitionen Semikola eingefügt. Die Semikolons unterdrücken die Ausgabe der REPL.

Dadurch werden die Funktionen gut angezeigt:

julia> S
S

julia> K
K

julia> I
I

Es gibt jedoch immer noch Probleme, wenn wir versuchen, eine Schließung anzuzeigen:

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

Es wäre schöner, das als S(K) anzuzeigen. Um dies zu erreichen, müssen wir ausnutzen, dass die Verschlüsse ihre eigenen individuellen Typen haben. Wir können diese Arten zugreifen und fügen Sie Methoden , um sie durch Reflexion, mit typeof und das primary Feld des name Feld des Typs. Starten Sie die REPL erneut. Wir werden weitere Änderungen vornehmen:

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)

Und jetzt endlich zeigen sich die Dinge so, wie wir es gerne hätten:

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