Julia Language
combinatori

Osservazioni

Il Y o Z Combinator

Anche se Julia non è un linguaggio puramente funzionale, ha il pieno supporto per molti dei capisaldi della programmazione funzionale: prima classe funzioni , scope lessicale, e chiusure .

Il combinatore a virgola fissa è un combinatore chiave nella programmazione funzionale. Poiché Julia ha una semantica di valutazione entusiasta (come molti altri linguaggi funzionali, tra cui Scheme, di cui Julia è fortemente ispirata), il combinatore Y originale di Curry non funzionerà immediatamente:

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

Tuttavia, un parente stretto del combinatore Y, il combinatore Z, funzionerà davvero:

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

Questo combinatore accetta una funzione e restituisce una funzione che quando viene chiamata con argomento x , viene passata a se stessa e x . Perché sarebbe utile che una funzione venga approvata da sola? Ciò consente la ricorsione senza in realtà fare riferimento al nome della funzione!

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

Quindi, Z(fact) diventa un'implementazione ricorsiva della funzione fattoriale, nonostante nessuna ricorsione sia visibile in questa definizione di funzione. (La ricorsione è evidente nella definizione del combinatore Z , ovviamente, ma ciò è inevitabile in un linguaggio desideroso.) Possiamo verificare che la nostra funzione funzioni effettivamente:

julia> Z(fact)(10)
3628800

Non solo, ma è veloce quanto possiamo aspettarci da un'implementazione ricorsiva. Il codice LLVM dimostra che il risultato è compilato in un semplice vecchio ramo, sottrarre, chiamare e moltiplicare:

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

Il sistema di combinazione SKI

Il sistema combinatore SKI è sufficiente per rappresentare qualsiasi termine di calcolo lambda. (In pratica, naturalmente, le astrazioni lambda esplodono in dimensioni esponenziali quando vengono tradotte in SCI.) A causa della semplicità del sistema, l'implementazione dei combinatori S, K e I è straordinariamente semplice:

Una traduzione diretta dal Lambda Calculus

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

Possiamo confermare, utilizzando il sistema di test delle unità , che ciascun combinatore ha il comportamento previsto.

Il combinatore I è più semplice da verificare; dovrebbe restituire il valore dato invariato:

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

Il combinatore K è anche abbastanza semplice: dovrebbe scartare il suo secondo argomento.

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

Il combinatore S è il più complesso; il suo comportamento può essere riassunto applicando i primi due argomenti al terzo argomento, applicando il primo risultato al secondo. Possiamo facilmente testare il combinatore S testando alcune delle sue forme al curry. S(K) , per esempio, dovrebbe semplicemente restituire il secondo argomento e scartare il suo primo, come vediamo succede:

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

S(I)(I) dovrebbe applicare la sua argomentazione a se stessa:

@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) applica il suo secondo argomento al primo:

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

Il combinatore I descritto sopra ha un nome in Base Julia standard: identity . Pertanto, avremmo potuto riscrivere le definizioni di cui sopra con la seguente definizione alternativa di I :

const I = identity

Mostrando Combinatori SKI

Una debolezza con l'approccio di cui sopra è che le nostre funzioni non mostrano quanto vorremmo. Potremmo sostituire

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

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

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

con alcuni display più informativi? La risposta è si! Riavvia il REPL, e questa volta definiamo come ogni funzione deve essere mostrata:

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

È importante non mostrare nulla finché non abbiamo finito di definire le funzioni. Altrimenti, rischiamo di invalidare la cache dei metodi, e i nostri nuovi metodi non sembrano avere effetto immediato. Questo è il motivo per cui abbiamo inserito il punto e virgola nelle definizioni precedenti. Il punto e virgola sopprime l'output di REPL.

Questo rende le funzioni ben visualizzate:

julia> S
S

julia> K
K

julia> I
I

Tuttavia, ci sono ancora problemi quando proviamo a visualizzare una chiusura:

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

Sarebbe più bello mostrarlo come S(K) . Per fare ciò, dobbiamo sfruttare il fatto che le chiusure hanno i loro tipi individuali. Siamo in grado di accedere a questi tipi e aggiungere loro dei metodi attraverso la riflessione, usando typeof e il campo primary campo name del tipo. Riavvia di nuovo REPL; faremo ulteriori cambiamenti:

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)

E ora, finalmente, le cose si mostrano come vorremmo che:

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