Julia Language
Combinateurs

Remarques

Le combinateur Y ou Z

Bien que Julia n'est pas un langage purement fonctionnel, il a un support complet pour la plupart des pierres angulaires de la programmation fonctionnelle: première classe fonctions , portée lexicale et fermetures .

Le combinateur en virgule fixe est un combinateur de clés en programmation fonctionnelle. Étant donné que Julia a une sémantique d' évaluation (comme le font de nombreux langages fonctionnels, y compris Scheme, dont Julia est fortement inspirée), le combinateur Y original de Curry ne fonctionnera pas immédiatement:

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

Cependant, un proche parent du combinateur Y, le Z-combinator, fonctionnera bien:

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

Ce combinateur prend une fonction et retourne une fonction qui, lorsqu'elle est appelée avec l'argument x , se fait passer et x . Pourquoi serait-il utile qu'une fonction soit transmise elle-même? Cela permet la récursivité sans faire référence au nom de la fonction du tout!

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

Par conséquent, Z(fact) devient une implémentation récursive de la fonction factorielle, bien qu'aucune récursivité ne soit visible dans cette définition de fonction. (La récursivité est évidente dans la définition du combinateur Z , bien sûr, mais cela est inévitable dans un langage avide.) Nous pouvons vérifier que notre fonction fonctionne bien:

julia> Z(fact)(10)
3628800

Non seulement cela, mais il est aussi rapide que nous pouvons attendre d'une implémentation récursive. Le code LLVM montre que le résultat est compilé dans une ancienne branche, soustrait, appelle et multiplie:

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

Le système de combinaison SKI

Le système de combinaison SKI est suffisant pour représenter tous les termes de calcul lambda. (En pratique, bien sûr, les abstractions lambda atteignent une taille exponentielle lorsqu'elles sont traduites en SKI.) En raison de la simplicité du système, l'implémentation des combinateurs S, K et I est extrêmement simple:

Une traduction directe du calcul Lambda

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

Nous pouvons confirmer, à l'aide du système de test unitaire , que chaque combinateur a le comportement attendu.

Le combinateur I est le plus facile à vérifier; il devrait retourner la valeur donnée inchangée:

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

Le combinateur K est également assez simple: il doit ignorer son deuxième argument.

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

Le combinateur S est le plus complexe; son comportement peut être résumé en appliquant les deux premiers arguments au troisième argument, en appliquant le premier résultat au second. Nous pouvons tester le plus facilement le combinateur S en testant certaines de ses formes curry. S(K) , par exemple, devrait simplement renvoyer son deuxième argument et rejeter son premier, comme on le voit:

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

S(I)(I) devrait appliquer son argument à lui-même:

@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) applique son second argument à son premier:

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

Le combinateur décrit ci-dessus porte un nom dans la Base standard Julia: identity . Ainsi, nous aurions pu réécrire les définitions ci-dessus avec la définition alternative suivante de I :

const I = identity

Affichage des combinateurs SKI

Une des faiblesses de l’approche ci-dessus est que nos fonctions ne s’affichent pas aussi bien que nous le souhaiterions. Pouvons-nous remplacer

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

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

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

avec quelques affichages plus informatifs? La réponse est oui! Relançons le REPL, et définissons cette fois comment chaque fonction doit être affichée:

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

Il est important d'éviter de montrer quoi que ce soit avant d'avoir fini de définir les fonctions. Sinon, nous risquons d’invalider le cache de la méthode et nos nouvelles méthodes ne semblent pas prendre effet immédiatement. C'est pourquoi nous avons mis des points-virgules dans les définitions ci-dessus. Les points-virgules suppriment la sortie de la REPL.

Cela rend les fonctions bien affichées:

julia> S
S

julia> K
K

julia> I
I

Cependant, nous rencontrons toujours des problèmes lorsque nous essayons d'afficher une fermeture:

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

Il serait plus intéressant de l’afficher comme S(K) . Pour ce faire, nous devons exploiter le fait que les fermetures ont leur propre type. Nous pouvons accéder à ces types et leur ajouter des méthodes par réflexion, en utilisant typeof et le champ primary champ de name du type. Redémarrez le REPL à nouveau; nous allons faire d'autres changements:

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)

Et maintenant, enfin, les choses s'affichent comme nous aimerions qu'elles:

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