Julia Language
combinators

Opmerkingen

De Y- of Z-combinatie

Hoewel Julia geen puur functionele taal is, biedt het volledige ondersteuning voor veel van de hoekstenen van functioneel programmeren: eersteklas functies , lexicale scope en sluitingen .

De vaste-puntcombinator is een belangrijke combinator in functioneel programmeren. Omdat Julia gretige evaluatiesemantiek heeft (net als veel functionele talen, waaronder Scheme, waarop Julia zich sterk door laat inspireren), werkt Curry's originele Y-combinator niet uit de doos:

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

Een naaste verwant van de Y-combinator, de Z-combinator, zal echter wel werken:

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

Deze combinator neemt een functie en retourneert een functie die, wanneer deze wordt aangeroepen met argument x , zelf en x wordt doorgegeven. Waarom zou het nuttig zijn als een functie zelf zou worden doorgegeven? Dit maakt recursie mogelijk zonder daadwerkelijk naar de naam van de functie te verwijzen!

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

Daarom wordt Z(fact) een recursieve implementatie van de faculteit, ondanks dat er geen recursie zichtbaar is in deze functiedefinitie. (Recursie is duidelijk zichtbaar in de definitie van de Z combinator, maar dat is onvermijdelijk in een gretige taal.) We kunnen verifiëren dat onze functie inderdaad werkt:

julia> Z(fact)(10)
3628800

Niet alleen dat, maar het is net zo snel als we kunnen verwachten van een recursieve implementatie. De LLVM-code laat zien dat het resultaat is gecompileerd in een gewone oude branch, aftrekken, aanroepen en vermenigvuldigen:

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

Het SKI-combinatorsysteem

Het SKI-combinatorsysteem is voldoende om alle lambda-calculustermen weer te geven. (In de praktijk, natuurlijk, worden lambda-abstracties opgeblazen tot exponentiële grootte wanneer ze worden vertaald in SKI.) Vanwege de eenvoud van het systeem is de implementatie van de S-, K- en I-combinators buitengewoon eenvoudig:

Een directe vertaling van Lambda Calculus

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

We kunnen met behulp van het eenheidstestsysteem bevestigen dat elke combinator het verwachte gedrag heeft.

De I-combinator is het gemakkelijkst te verifiëren; het zou de gegeven waarde onveranderd moeten retourneren:

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

De K-combinator is ook vrij eenvoudig: hij moet zijn tweede argument negeren.

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

De S-combinator is het meest complex; zijn gedrag kan worden samengevat als het toepassen van de eerste twee argumenten op het derde argument, het toepassen van het eerste resultaat op het tweede. We kunnen de S-combinator het gemakkelijkst testen door enkele van de gecurryde vormen te testen. S(K) zou bijvoorbeeld gewoon zijn tweede argument moeten teruggeven en zijn eerste moeten weggooien, zoals we zien gebeuren:

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

S(I)(I) moet zijn argument op zichzelf toepassen:

@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) past zijn tweede argument toe op zijn eerste:

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

De hierboven beschreven I-combinator heeft een naam in standaard Base Julia: identity . We hadden dus de bovenstaande definities kunnen herschrijven met de volgende alternatieve definitie van I :

const I = identity

SKI-combinaties weergeven

Een zwakte van de bovenstaande benadering is dat onze functies niet zo mooi worden weergegeven als we zouden willen. Kunnen we vervangen

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

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

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

met wat meer informatieve displays? Het antwoord is ja! Laten we de REPL opnieuw starten en deze keer definiëren hoe elke functie moet worden weergegeven:

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

Het is belangrijk om niets te laten zien totdat we klaar zijn met het definiëren van functies. Anders lopen we het risico de methodecache ongeldig te maken en lijken onze nieuwe methoden niet onmiddellijk van kracht te worden. Daarom hebben we puntkomma's in de bovenstaande definities geplaatst. De puntkomma's onderdrukken de uitvoer van de REPL.

Hierdoor worden de functies mooi weergegeven:

julia> S
S

julia> K
K

julia> I
I

We komen echter nog steeds problemen tegen wanneer we proberen een afsluiting weer te geven:

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

Het zou mooier zijn om dat als S(K) . Om dat te doen, moeten we misbruiken dat de sluitingen hun eigen individuele types hebben. We kunnen toegang krijgen tot deze soorten en methoden toe te voegen aan hen door reflectie, met behulp van typeof en het primary veld van de name veld van het type. Start de REPL opnieuw; we zullen verdere wijzigingen aanbrengen:

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)

En nu, eindelijk, worden dingen weergegeven zoals we zouden willen dat ze:

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