Inconcevable efficacité d'envoi multiple

Sous la cinématique, un décryptage du rapport de Stefan Karpinsky, l'un des principaux développeurs du langage Julia, est proposé. Dans le rapport, il discute des résultats inattendus de la répartition multiple pratique et efficace, considérée comme le paradigme principal de Julia.

De l'interprète: titre du rapport fait référence à l'article de Eugene Wigner « l' efficacité inconcevable des mathématiques dans les sciences de la nature » .

envoi multiple - un paradigme clé langue Julia, et au cours de son existence, nous, les développeurs de la langue, remarqué quelque chose prévu, mais en même temps déconcertant. Du moins, nous ne nous y attendions pas dans la mesure où nous l'avons vu. C'est quelque chose - un niveau stupéfiant de réutilisation de code dans l'écosystème Julia, qui est beaucoup plus élevé que dans n'importe quelle autre langue que je connais.

Nous voyons constamment que certaines personnes écrivent du code généralisé, quelqu'un d'autre définit un nouveau type de données, ces personnes ne se connaissent pas, puis quelqu'un applique ce code à ce type de données inhabituel ... Et tout fonctionne. Et cela arrive étonnamment souvent .
J'ai toujours pensé qu'un tel comportement devrait être attendu d'une programmation orientée objet, mais j'ai apprécié les nombreuses langues orientées objet, et il se trouve qu'ils sont en général si simple ne fonctionne pas. Par conséquent, à un moment donné, je me demandais pourquoi Julia est la langue si efficace à cet égard? Pourquoi y at-il si haut niveau de réutilisabilité du code? Et aussi - quelles leçons peut-on en tirer que d'autres langues pourraient emprunter à Julia pour devenir meilleures?

Parfois, quand je dis cela, le public ne me croit pas, mais vous êtes déjà sur JuliaCon, donc vous êtes au courant de ce qui se passe, donc je vais me concentrer sur pourquoi, à mon avis, cela se produit.

Mais pour commencer - l'un de mes exemples préférés.

La diapositive - le résultat de Chris Rakaukasa. Il écrit toutes sortes de packages très généralisés pour résoudre des équations différentielles. Vous pouvez nourrir le nombre double ou BigFloat, - mais ce que vous voulez. Et en quelque sorte, il a décidé qu'il voulait voir l'erreur du résultat de l'intégration. Et il y avait un package de mesures qui peut suivre à la fois la valeur d'une grandeur physique et la propagation d'une erreur à travers une séquence de formules. Ce package prend également en charge une syntaxe élégante pour les valeurs d'incertitude à l'aide du caractère Unicode ± . Ici, sur la diapositive, il est montré que l'accélération de la gravité, la longueur du pendule, la vitesse initiale, l'angle de déviation sont tous connus avec une sorte d'erreur. Par exemple, vous définissez un pendule simple, manquant ses équations du mouvement à travers le solveur ODE et - patatras! - tout fonctionne . Et vous voyez un graphique avec des inexactitudes de moustache. Et je ne montre pas toujours le code pour dessiner des graphiques - trop générique et que vous venez de commencer à la valeur avec une erreur de Measurements.jl et obtenir un graphique avec les erreurs.

niveau de compatibilité des différents packages et le code de généralisation mozgovynosyaschy facile. Comment ça marche ? Il s'avère que oui.

Eh bien, pas que nous nous attendons à ne vraiment pas. Après tout, nous avons inclus le concept de répartition multiple dans le langage précisément parce qu'il nous permet d'exprimer des algorithmes généralisés. Donc, tout ce qui précède n'est pas si fou. Mais c'est une chose de savoir cela en théorie, et une autre de voir en pratique que l'approche fonctionne vraiment. Après tout, la répartition unique et la surcharge des opérateurs en C ++ devraient également donner un résultat similaire - mais en réalité, ils ne fonctionnent souvent pas comme ils le souhaitent.

De plus, nous assistons à quelque chose de plus que ce que nous avions prévu lors du développement du langage: pas seulement du code généralisé est en cours d'écriture. Ensuite, je vais essayer de dire ce qui, à mon avis, est plus.

Il existe donc deux types de réutilisation de code, et ils sont assez différents. L'un est l'algorithme généralisé, et c'est la première chose dont ils se souviennent. Le deuxième aspect, moins évident, mais qui semble être le plus important, est la simplicité avec laquelle Julia utilise les mêmes types de données dans une grande variété de packages. Dans une certaine mesure, cela se produit car les méthodes de type ne deviennent pas un obstacle à son utilisation: vous n'avez pas besoin de vous mettre d'accord avec l'auteur du type sur les interfaces et les méthodes dont il hérite; vous pouvez simplement dire: "Oh, j'aime ce type de RVB. Je proposerai mes propres opérations dessus, mais j'aime sa structure."

Préface Ordonnancement multiple contre surcharge de fonction

Maintenant, je dois mentionner la surcharge de fonctions en C ++ ou Java, car on me pose constamment des questions à leur sujet. À première vue, ce n'est pas différent de la planification multiple. Contrairement à ce qui est là et ce qui est pire fonctions de surcharge?

Je vais commencer par un exemple sur Julia:

 abstract type Pet end struct Dog <: Pet; name::String end struct Cat <: Pet; name::String end function encounter(a::Pet, b::Pet) verb = meets(a, b) println("$(a.name) meets $(b.name) and $verb") end meets(a::Dog, b::Dog) = "sniffs" meets(a::Dog, b::Cat) = "chases" meets(a::Cat, b::Dog) = "hisses" meets(a::Cat, b::Cat) = "slinks" Dog) = "siffle" abstract type Pet end struct Dog <: Pet; name::String end struct Cat <: Pet; name::String end function encounter(a::Pet, b::Pet) verb = meets(a, b) println("$(a.name) meets $(b.name) and $verb") end meets(a::Dog, b::Dog) = "sniffs" meets(a::Dog, b::Cat) = "chases" meets(a::Cat, b::Dog) = "hisses" meets(a::Cat, b::Cat) = "slinks" 

Nous définissons un type abstrait pour Pet , lui présenter des sous - types de Dog et de Cat , ils ont un nom de champ (bit de code est répété, mais tolérable) et définir une fonction généralisée « de rencontre » qui prend deux objets d'arguments de type Pet . Dans ce document , on calcule d' abord la « action » est défini par le résultat de l' appel de la fonction générique meet() , puis imprimer une phrase décrivant une réunion. Dans la fonction meets() , nous utilisons la répartition multiple pour déterminer l'action qu'un animal effectue lorsqu'il en rencontre un autre.

Ajoutez un couple de chiens et un couple de chats et voyez les résultats de la réunion:

 fido = Dog("Fido") rex = Dog("Rex") whiskers = Cat("Whiskers") spots = Cat("Spots") encounter(fido, rex) encounter(rex, whiskers) encounter(spots, fido) encounter(whiskers, spots) 

Maintenant, nous allons "traduire" la même chose en C ++ aussi littéralement que possible. Nous définissons la classe Pet avec le champ name - en C ++, nous pouvons le faire (en passant, l' un des avantages de C ++ -. Champ même dans les types abstraits peuvent être ajoutées aux données puis définir la fonction de base meets() , définir la fonction encounter() pour deux objets de type Pet et enfin, définissez les classes dérivées Dog et Cat et faites une surcharge meets() pour eux:

 class Pet { public: string name; }; string meets(Pet a, Pet b) { return "FALLBACK"; } void encounter(Pet a, Pet b) { string verb = meets(a, b); cout << a.name << " meets " << b. name << " and " << verb << endl; } class Cat : public Pet {}; class Dog : public Pet {}; string meets(Dog a, Dog b) { return "sniffs"; } string meets(Dog a, Cat b) { return "chases"; } string meets(Cat a, Dog b) { return "hisses"; } string meets(Cat a, Cat b) { return "slinks"; } ) {return "REPLI"; class Pet { public: string name; }; string meets(Pet a, Pet b) { return "FALLBACK"; } void encounter(Pet a, Pet b) { string verb = meets(a, b); cout << a.name << " meets " << b. name << " and " << verb << endl; } class Cat : public Pet {}; class Dog : public Pet {}; string meets(Dog a, Dog b) { return "sniffs"; } string meets(Dog a, Cat b) { return "chases"; } string meets(Cat a, Dog b) { return "hisses"; } string meets(Cat a, Cat b) { return "slinks"; } 

La fonction main() , comme dans le code Julia, crée des chiens et des chats et les fait se rencontrer:

 int main() { Dog fido; fido.name = "Fido"; Dog rex; rex.name = "Rex"; Cat whiskers; whiskers.name = "Whiskers"; Cat spots; spots.name = "Spots"; encounter(fido, rex); encounter(rex, whiskers); encounter(spots, fido); encounter(whiskers, spots); return 0; } 

Donc, répartition multiple contre la surcharge de fonctions. Gong!

Selon vous, qu'est-ce qui retournera du code avec plusieurs répartitions?

 Fido meets Rex and sniffs Rex meets Whiskers and chases Spots meets Fido and hisses Whiskers meets Spots and slinks 

 Fido meets Rex and FALLBACK Rex meets Whiskers and FALLBACK Spots meets Fido and FALLBACK Whiskers meets Spots and FALLBACK 

Ainsi, dans une approche directe, C ++ « traduction » du Code généralisé Julia ne donne pas le comportement souhaité du fait que les utilisations du compilateur types dérivés statiquement au moment de la compilation. Et le fait est que nous voulons appeler une fonction sur la base du type de béton réel que les variables sont le moteur d'exécution. Les fonctions de modèle, bien qu'elles améliorent quelque peu la situation, nécessitent toujours la connaissance de tous les types inclus dans l'expression statiquement au moment de la compilation, et il est facile de trouver un exemple où cela serait impossible.

Pour moi, de tels exemples montrent que la répartition multiple fait la bonne chose, et toutes les autres approches ne sont tout simplement pas une très bonne approximation du résultat correct.

Voyons maintenant un tel tableau. J'espère que vous le trouverez significatif:

Dans les langues sans répartition, vous écrivez simplement f(x, y, ...) , les types de tous les arguments sont fixes, c'est-à-dire un appel à f() est un appel à une seule fonction f() , qui peut être dans le programme. Le degré d'expressivité est constant: appeler f() toujours une et une seule chose. L'envoi unique a été une percée majeure dans la transition vers la POO dans les années 1990 et 2000. La syntaxe des points est généralement utilisée, ce que les gens aiment vraiment. Et une opportunité expressive supplémentaire apparaît: l'appel est réparti selon le type d'objet x ₁ . La puissance expressive se caractérise par la possibilité de l'ensemble | X ₁ | types ayant la méthode f() . Dans le même ordonnancement multiple certain nombre de modes de réalisation possibles pour la fonction f() est égale à la puissance du produit cartésien de types d'ensembles dont les arguments peuvent appartenir. En réalité, bien sûr, presque personne n'a besoin d'autant de fonctions différentes dans un seul programme. Mais le point clé ici est que le programmeur dispose d'un moyen simple et naturel d'utiliser n'importe quel élément de cette variété, ce qui conduit à une croissance exponentielle des opportunités.

Partie 1. Programmation générale

Parlons du code généralisé - la principale caractéristique de la répartition multiple.

Voici un exemple (complètement artificiel) de code générique:

 using LinearAlgebra function inner_sum(A, vs) t = zero(eltype(A)) for v in vs t += inner(v, A, v) #  ! end return t end inner(v, A, w) = dot(v, A * w) #    en using LinearAlgebra function inner_sum(A, vs) t = zero(eltype(A)) for v in vs t += inner(v, A, v) #  ! end return t end inner(v, A, w) = dot(v, A * w) #    , v) # using LinearAlgebra function inner_sum(A, vs) t = zero(eltype(A)) for v in vs t += inner(v, A, v) #  ! end return t end inner(v, A, w) = dot(v, A * w) #    

Ici, A est quelque chose comme une matrice (bien que je n'aie pas indiqué les types, et je peux deviner quelque chose par son nom), vs est le vecteur de certains éléments de type vecteur, puis le produit scalaire est considéré à travers cette "matrice", pour laquelle une définition généralisée est donnée sans spécifier de types. La programmation généralisée consiste ici en cet appel même de la fonction inner() en boucle (conseil professionnel: si vous voulez écrire du code généralisé - supprimez simplement les restrictions de type).

Alors, "regarde maman, ça marche":

 julia> A = rand(3, 3) 3×3 Array{Float64,2}: 0.934255 0.712883 0.734033 0.145575 0.148775 0.131786 0.631839 0.688701 0.632088 julia> vs = [rand(3) for _ in 1:4] 4-element Array{Array{Float64,1},1}: [0.424535, 0.536761, 0.854301] [0.715483, 0.986452, 0.82681] [0.487955, 0.43354, 0.634452] [0.100029, 0.448316, 0.603441] julia> inner_sum(A, vs) 6.825340887556694 

Rien de spécial, il calcule une certaine valeur. Mais - le code est écrit dans un style généralisé et fonctionnera pour tout A et vs , si seulement il était possible d'effectuer les opérations correspondantes sur eux.

Quant à l'efficacité sur des types de données spécifiques - quelle chance. Je veux dire que pour les vecteurs et matrices denses, ce code le fera «comme il se doit» - il générera du code machine avec invocation des opérations BLAS, etc. etc. Si vous passez des tableaux statiques, le compilateur en tiendra compte, étendra les cycles, appliquera la vectorisation - tout est comme il se doit.

Mais plus important encore, le code fonctionnera pour les nouveaux types, et vous pouvez le rendre non seulement super-efficace, mais super-efficace! Tendons la définition d'un nouveau type (ce qui est le vrai type de données qui est utilisé dans l'apprentissage de la machine), un vecteur unitaire (vecteur un chaud). Il s'agit d'un vecteur dans lequel l'un des composants est 1 et tous les autres sont nuls. Soumettez, vous pouvez très compact: tout ce dont vous avez besoin pour stocker - est la longueur du vecteur et le nombre de composants non nul.

 import Base: size, getindex, * struct OneHotVector <: AbstractVector{Int} len :: Int ind :: Int end size(v::OneHotVector) = (v.len,) getindex(v::OneHotVector, i::Integer) = Int(i == v.ind) 

En fait, c'est vraiment toute la définition de type du package qui l'ajoute. Et avec cette définition, inner_sum() fonctionne également:

 julia> vs = [OneHotVector(3, rand(1:3)) for _ in 1:4] 4-element Array{OneHotVector,1}: [0, 1, 0] [0, 0, 1] [1, 0, 0] [1, 0, 0] julia> inner_sum(A, vs) 2.6493739294755123 

Mais pour un produit scalaire, une définition générale est utilisée ici - pour ce type de données, c'est lent, pas cool!

Ainsi, les définitions générales fonctionnent, mais pas toujours de manière optimale, et vous pouvez parfois rencontrer ce problème lorsque vous utilisez Julia: "eh bien, une définition générale est appelée, c'est pourquoi ce code GPU fonctionne depuis la cinquième heure ..."

Dans inner() par défaut, la définition générale du produit matriciel par un vecteur est appelée, qui, multipliée par un vecteur unitaire, renvoie une copie de l'une des colonnes de type Vector{Float64} . Ensuite, la définition générale du produit scalaire dot() est appelée avec le vecteur unitaire et cette colonne, ce qui fait beaucoup de travail inutile. En fait, pour chaque composant, il est vérifié "êtes-vous égal à un? Et vous?" etc.

Nous pouvons grandement optimiser cette procédure. Par exemple, remplacer la multiplication matricielle par OneHotVector simplement en sélectionnant une colonne. Très bien, définissez cette méthode, et c'est tout.

 *(A::AbstractMatrix, v::OneHotVector) = A[:, v.ind] 

Et voilà, nous pourrions dire « nous voulons que la planification au second argument, » peu importe ce qui est dans le sol. Une telle définition extraira simplement la ligne de la matrice et sera beaucoup plus rapide que la méthode générale - l'itération et la sommation sur les colonnes sont supprimées.

Mais vous pouvez aller plus loin et optimiser directement inner() , car la multiplication de deux vecteurs unitaires à travers une matrice extrait simplement un élément de cette matrice:

 inner(v::OneHotVector, A, w::OneHotVector) = A[v.ind, w.ind] 

C'est l'efficacité super-duper promise. Et tout ce qui est nécessaire est de définir cette méthode inner() .

Cet exemple illustre l'un des multiples envoi des candidatures: il y a une définition commune de la fonction, mais pour certains types de données il fonctionne sous-optimale. Ensuite, nous ajoutons ponctuellement une méthode qui préserve le comportement de la fonction pour ces types, mais fonctionne beaucoup plus efficacement .

Mais il y a un autre domaine - quand il n'y a pas de définition générale d'une fonction, mais je veux ajouter des fonctionnalités pour certains types. Ensuite, vous pouvez l'ajouter avec un minimum d'effort.

Et la troisième option - vous voulez juste avoir le même nom de fonction, mais avec un comportement différent pour différents types de données - par exemple, pour qu'une fonction se comporte différemment lorsqu'elle travaille avec des dictionnaires et des tableaux.

Comment obtenir un comportement similaire dans les langues avec un seul envoi? C'est possible, mais difficile. Problème: lors de la surcharge de la fonction * il fallait répartir sur le deuxième argument, et non sur le premier. Vous pouvez faire une double répartition: d'abord, répartir par le premier argument et appeler la méthode AbstractMatrix.*(v) . Et cette méthode, à son tour, appelle quelque chose comme v.__rmul__(A) , c'est-à-dire le deuxième argument de l'appel d'origine est maintenant devenu l'objet dont la méthode est réellement appelée. __rmul__ ici est tiré du Python, où un tel comportement - un modèle standard, mais cela fonctionne, il semble, que pour l' addition et la multiplication. C'est-à-dire le problème de la double répartition est résolu si nous voulons appeler une fonction appelée + ou * , sinon - hélas, pas de nos jours. En C ++ et dans d'autres langages - vous devez construire votre vélo.

OK, qu'en est-il de inner() ? Maintenant, il y a trois arguments, et la répartition continue le premier et le troisième. Que faire dans les langues avec envoi unique n'est pas clair. "Triple expédition" que je n'ai jamais rencontré en direct. Il n'y a pas de bonnes solutions. Habituellement, lorsqu'un besoin similaire survient (et dans les codes numériques, il apparaît très souvent), les gens finissent par mettre en œuvre leur système de répartition multiple. Si vous regardez de grands projets pour des calculs numériques en Python, vous serez étonné de voir combien d'entre eux vont de cette façon. Naturellement, ces implémentations fonctionnent de manière situationnelle, mal conçues, pleines de bogues et lentes ( référence à la dixième règle de Greenspan - environ la traduction ), parce que Jeff Besancon n'a travaillé sur aucun de ces projets (l' auteur et développeur en chef du système de répartition des types dans Julia - env. trad. ).

Partie 2. Types généraux

Déplacera au paradigme Julia côté arrière - types généraux. C'est, à mon avis, le principal «cheval de bataille» du langage, car c'est dans ce domaine que j'observe un haut niveau de réutilisation du code.

Par exemple, supposons que vous ayez un type RVB, comme celui de ColorTypes.jl. Il n'y a rien de compliqué, seulement trois valeurs sont réunies. Par souci de simplicité, nous supposons que le type est paramétrique (mais pourrait être), et l'auteur a identifié plusieurs tâches de base pour celui qui a été utile. Vous prenez ce type et pensez: "Hmm, je voudrais ajouter plus d'opérations sur ce type." Par exemple, imaginez RGB comme un espace vectoriel (qui est, strictement parlant, n'est pas vrai, mais viendra dans la première approximation). Dans Julia, il vous suffit de prendre et d'ajouter dans votre code toutes les opérations manquantes.

La question se pose - et Cho? Pourquoi est-ce que je me concentre tellement là-dessus? Il se trouve que dans les langages orientés objet basés sur les classes, cette approche est étonnamment difficile à mettre en œuvre. Étant donné que ces méthodes de détermination des langues sont dans la définition de la classe, ajoutez une méthode ne peut être de deux façons - soit à modifier le code de la classe, en ajoutant le comportement souhaité ou créer une classe dérivée avec les bonnes méthodes.

La première option gonfle la définition de la classe de base et oblige également le développeur de la classe de base à prendre en charge toutes les méthodes ajoutées lors de la modification du code. Qu'est-ce qui pourrait un jour rendre une telle classe non prise en charge.

L'hérédité est une option «recommandée» classique, mais pas non plus sans défauts. Tout d'abord, vous devez changer le nom de la classe - que ce ne soit plus RGB , mais MyRGB . De plus, les nouvelles méthodes ne fonctionneront plus pour la classe RGB origine; si je veux appliquer ma nouvelle méthode à un objet RGB créé dans le code de quelqu'un d'autre, je dois le convertir ou l' MyRGB dans MyRGB . Mais ce n'est pas le pire. Si j'ai créé une classe MyRGB avec des fonctionnalités supplémentaires, quelqu'un d'autre OurRGB , etc. - alors si quelqu'un veut une classe qui a toutes les nouvelles fonctionnalités, vous devez utiliser l'héritage multiple (et ce n'est que si le langage de programmation le permet!).

Ainsi, les deux options sont couci-couça. Il existe cependant d'autres solutions:

• Rendre fonctionnelle la fonction externe à la place d'une méthode de classe - au f(x, y) au lieu xf(y) . Mais alors le comportement généralisé est perdu.
• Cracher sur la réutilisation du code (et, il me semble, dans de nombreux cas, cela se produit). Copiez-vous simplement une classe RGB étrangère et ajoutez ce qui manque.

La caractéristique clé de Julia en termes de réutilisation de code est presque complètement réduite au fait que la méthode est définie en dehors du type . C’est tout. Faites de même dans les langues à envoi unique - et les types peuvent être réutilisés avec la même facilité. Tout ce « nous allons faire les méthodes de la classe » - couci-couça idée, en fait. Certes, il y a un bon point - l'utilisation des classes comme espaces de noms. Si j'écris xf(y) - f() pas obligé d'être dans l'espace de noms courant, il doit être recherché dans l'espace de noms x . Oui, c'est une bonne chose - mais vaut-il tous les autres ennuis? Je ne sais pas. À mon avis, non (bien que mon opinion, comme vous pouvez le deviner, soit légèrement biaisée).

Épilogue. Le problème de l'expression

Il y a un tel problème de programmation qui a été remarqué dans les années 70. Il est en grande partie en raison de la vérification de type statique, parce que dans les langues elle est apparue. Certes, je pense que cela n'a rien à voir avec la vérification de type statique. L'essence du problème est la suivante: est-il possible de changer le modèle de données et l'ensemble d'opérations sur les données en même temps, sans recourir à des techniques douteuses.

Le problème peut être plus ou moins réduit comme suit:

1. est-il possible d'ajouter facilement et sans erreur de nouveaux types de données auxquels les méthodes existantes sont applicables et
2. Est-il possible d' ajouter de nouvelles opérations sur des types existants .

(1) facile à faire dans des langages orientés objet et difficile en fonctionnel, (2) - vice versa. En ce sens, nous pouvons simplement parler du dualisme des approches POO et PF.

Dans les langues multiples avec l'expédition, les deux opérations se font facilement. (1) , (2) — . , . ( https://en.wikipedia.org/wiki/Expression_problem ), . ? , , . , " , " — " " . " , " , , .

, . , , — .

, Julia ( ), . .