Julia Language
kombinatorer

Anmärkningar

Y eller Z Combinator

Även om Julia inte är ett rent funktionellt språk, har det fullt stöd för många av hörnstenarna i funktionell programmering: förstklassiga funktioner , lexikalisk omfattning och stängningar .

Fastpunktskombinatorn är en nyckelkombinator i funktionell programmering. Eftersom Julia har ivriga utvärderingssemantik (liksom många funktionella språk, inklusive Scheme, som Julia är starkt inspirerad av), kommer Currys ursprungliga Y-kombinator inte att fungera ur lådan:

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

Men en nära släkting till Y-kombinatorn, Z-kombinatorn, kommer verkligen att fungera:

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

Denna kombinator tar en funktion och returnerar en funktion som när den kallas med argument x , får passera sig själv och x . Varför skulle det vara användbart att en funktion passeras själv? Detta tillåter rekursion utan att faktiskt hänvisa till funktionens namn alls!

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

Därför blir Z(fact) en rekursiv implementering av faktorfunktionen, trots att ingen rekursion syns i denna funktionsdefinition. (Rekursion är självklart tydligt i definitionen av Z kombinatorn, men det är oundvikligt på ett ivrigt språk.) Vi kan verifiera att vår funktion verkligen fungerar:

julia> Z(fact)(10)
3628800

Inte bara det, utan det är så snabbt som vi kan förvänta oss av en rekursiv implementering. LLVM-koden visar att resultatet sammanställs i en vanlig gammal gren, subtrahera, ringa och multiplicera:

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 Combinator System

SKI-kombinationssystemet är tillräckligt för att representera alla lambda-beräkningsvillkor. (I praktiken spränger naturligtvis lambda-abstraktioner till exponentiell storlek när de översätts till SKI.) På grund av systemets enkelhet är implementeringen av S-, K- och I-kombinationerna extremt enkel:

En direkt översättning från Lambda Calculus

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

Vi kan bekräfta med hjälp av enhetstestningssystemet att varje kombination har förväntat beteende.

I-kombinatorn är lättast att verifiera; det ska returnera det givna värdet oförändrat:

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

K-kombinatorn är också ganska enkel: den borde bortskaffa sitt andra argument.

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

S-kombinatorn är den mest komplexa; dess beteende kan sammanfattas som att de två första argumenten tillämpas på det tredje argumentet, det första resultatet på det andra. Vi kan lätt testa S-kombinatorn genom att testa några av dess curryformer. S(K) , till exempel, bör helt enkelt returnera sitt andra argument och kassera det första, som vi ser hända:

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

S(I)(I) bör tillämpa sitt argument på sig själv:

@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) tillämpar det andra argumentet på det första:

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

I-kombinatorn som beskrivs ovan har ett namn i Standard Base Julia: identity . Således kunde vi ha skrivit om ovanstående definitioner med följande alternativa definition av I :

const I = identity

Visar SKI-kombinationer

En svaghet med tillvägagångssättet ovan är att våra funktioner inte visas så bra som vi kanske vill. Kan vi ersätta

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

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

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

med några mer informativa skärmar? Svaret är ja! Låt oss starta om REPL och definiera den här gången hur varje funktion ska visas:

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

Det är viktigt att undvika att visa något tills vi har definierat funktioner. Annars riskerar vi att ogiltigställa metodcachen och våra nya metoder verkar inte omedelbart träda i kraft. Det är därför vi har lagt semikolon i definitionerna ovan. Semikolon undertrycker REPL: s utdata.

Detta gör att funktionerna visas fint:

julia> S
S

julia> K
K

julia> I
I

Men vi har fortfarande problem när vi försöker visa en stängning:

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

Det skulle vara trevligare att visa det som S(K) . För att göra det måste vi utnyttja att stängningarna har sina egna individuella typer. Vi kan få tillgång till dessa typer och lägga metoder för dem genom reflektion, genom att använda typeof och primary fältet i name fältet av typen. Starta om REPL igen; vi kommer att göra ytterligare förändringar:

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)

Och äntligen visas saker som vi vill att de ska:

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