Julia Language
Kombinatory

Uwagi

Kombinator Y lub Z

Chociaż Julia nie jest językiem czysto funkcjonalnym, ma pełne wsparcie dla wielu podstawowych elementów programowania funkcjonalnego: pierwszorzędnych funkcji , zakresu leksykalnego i zamknięć .

Kombinator stałoprzecinkowy jest kluczowym kombinatorem w programowaniu funkcjonalnym. Ponieważ Julia ma chętną semantykę oceny (podobnie jak wiele języków funkcjonalnych, w tym Schemat, którym Julia jest mocno zainspirowana), oryginalny kombinator Y Curry nie będzie działać od razu:

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

Jednak bliski krewny kombinatora Y, kombinator Z, rzeczywiście będzie działał:

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

Kombinator przyjmuje funkcję i zwraca funkcję, która po wywołaniu z argumentem x , przechodzi sama i x . Dlaczego miałoby być użyteczne przekazywanie funkcji? Pozwala to na rekurencję bez konieczności odwoływania się do nazwy funkcji!

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

Stąd Z(fact) staje się rekurencyjną implementacją funkcji silniowej, pomimo braku rekurencji w tej definicji funkcji. (Rekurencja jest oczywiście widoczna w definicji kombinatora Z , ale jest to nieuniknione w chętnym języku.) Możemy zweryfikować, czy nasza funkcja rzeczywiście działa:

julia> Z(fact)(10)
3628800

Nie tylko to, ale jest tak szybkie, jak możemy oczekiwać od rekurencyjnej implementacji. Kod LLVM pokazuje, że wynik jest kompilowany do zwykłej starej gałęzi, odejmowania, wywoływania i mnożenia:

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

System SKI Combinator

System sumatora SKI jest wystarczający do przedstawienia dowolnych warunków rachunku lambda. (W praktyce oczywiście abstrakcje lambda powiększają się do wykładniczej wielkości, kiedy są tłumaczone na SKI.) Ze względu na prostotę systemu, implementacja kombinacji S, K i I jest niezwykle prosta:

Bezpośrednie tłumaczenie z Lambda Calculus

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

Za pomocą systemu testów jednostkowych możemy potwierdzić, że każdy kombinator ma oczekiwane zachowanie.

Kombinator I jest najłatwiejszy do zweryfikowania; powinien zwrócić podaną wartość bez zmian:

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

Kombinator K jest również dość prosty: powinien odrzucić swój drugi argument.

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

Kombinator S jest najbardziej złożony; jego zachowanie można podsumować jako zastosowanie dwóch pierwszych argumentów do trzeciego argumentu, zastosowanie pierwszego wyniku do drugiego. Najłatwiej możemy przetestować kombinator S, testując niektóre z jego curry. S(K) powinien po prostu zwrócić drugi argument i odrzucić pierwszy, jak widzimy, co się dzieje:

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

S(I)(I) powinien zastosować swój argument do siebie:

@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) stosuje swój drugi argument do pierwszego:

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

Kombinator I opisany powyżej ma nazwę w standardowej Base Julii: identity . Zatem moglibyśmy przepisać powyższe definicje na następującą alternatywną definicję I :

const I = identity

Pokazuje SKI Kombinatory

Jedną słabością powyższego podejścia jest to, że nasze funkcje nie pokazują się tak ładnie, jak byśmy chcieli. Czy możemy wymienić?

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

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

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

z kilkoma bardziej pouczającymi wyświetlaczami? Odpowiedź brzmi tak! Zrestartujmy REPL, a tym razem określmy, jak ma być wyświetlana każda funkcja:

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

Ważne jest, aby unikać pokazywania czegokolwiek, dopóki nie zakończymy definiowania funkcji. W przeciwnym razie ryzykujemy unieważnienie pamięci podręcznej metod, a nasze nowe metody nie będą natychmiast działać. Dlatego umieściliśmy średniki w powyższych definicjach. Średniki tłumią moc wyjściową REPL.

To sprawia, że funkcje wyświetlają się ładnie:

julia> S
S

julia> K
K

julia> I
I

Jednak nadal występują problemy, gdy próbujemy wyświetlić zamknięcie:

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

Lepiej byłoby wyświetlić to jako S(K) . Aby to zrobić, musimy wykorzystać to, że zamknięcia mają swoje indywidualne typy. Możemy uzyskać dostęp do tych typów i dodawać do nich metody poprzez odbicie, używając typeof i pola primary pola name typu. Uruchom ponownie REPL; dokonamy dalszych zmian:

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)

A teraz wreszcie rzeczy wyglądają tak, jak chcielibyśmy:

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