Sob a cena, é proposta uma descriptografia do relatório de Stefan Karpinsky, um dos principais desenvolvedores da linguagem Julia. No relatório, ele discute os resultados inesperados do envio múltiplo conveniente e eficiente, considerado o principal paradigma de Julia.
De um tradutor : o título do relatório refere-se a um artigo de Eugene Wigner, "A incompreensível eficácia da matemática nas ciências naturais" .
A programação múltipla é um paradigma fundamental da linguagem Julia e, durante sua existência, nós, os desenvolvedores da linguagem, percebemos algo esperado, mas ao mesmo tempo intrigante. Pelo menos não esperávamos isso na medida em que vimos. Isso é algo - um nível impressionante de reutilização de código no ecossistema Julia, que é muito maior do que em qualquer outro idioma que eu conheça.
Vimos constantemente que algumas pessoas escrevem código generalizado, outras pessoas definem um novo tipo de dados, essas pessoas não estão familiarizadas e, em seguida, alguém aplica esse código a esse tipo de dados incomum ... E tudo simplesmente funciona. E isso acontece surpreendentemente com frequência .
Eu sempre pensei que esse comportamento deveria ser esperado da programação orientada a objetos, mas usei muitas linguagens orientadas a objetos, e acontece que geralmente tudo não funciona nelas. Portanto, em algum momento pensei: por que Julia é uma linguagem tão eficaz nesse sentido? Por que o nível de reutilização de código é tão alto lá? E também - que lições podem ser aprendidas disso que outras línguas poderiam emprestar de Julia para se tornarem melhores?
Às vezes, quando digo isso, o público não acredita em mim, mas você já está no JuliaCon, então você está ciente do que está acontecendo, então vou me concentrar no por que, na minha opinião, isso acontece.
Mas para iniciantes - um dos meus exemplos favoritos.
No slide está o resultado do trabalho de Chris Rakaukas. Ele escreve todos os tipos de pacotes muito generalizados para resolver equações diferenciais. Você pode alimentar números duplos , ou BigFloat, o que quiser. E de alguma maneira ele decidiu que quer ver o erro do resultado da integração. E havia um pacote Measurements que pode rastrear o valor de uma quantidade física e a propagação de um erro através de uma sequência de fórmulas. Este pacote também suporta sintaxe elegante para valores de incerteza usando o caractere Unicode ± . Aqui no slide é mostrado que a aceleração da gravidade, o comprimento do pêndulo, a velocidade inicial, o ângulo de desvio são todos conhecidos com algum tipo de erro. Então, você define um pêndulo simples, passa suas equações de movimento através do solucionador ODE e - bam! tudo funciona . E você vê um gráfico com imprecisões de bigode. E ainda não mostro que o código para desenhar um gráfico também é generalizado, e você apenas insere o valor com um erro de Measurements.jl e obtém um gráfico com erros.
O nível de compatibilidade de diferentes pacotes e a generalização do código são simplesmente empolgantes. Como isso funciona ? Acontece que sim.
Bem, não que não esperássemos isso. Afinal, incluímos o conceito de despacho múltiplo na linguagem precisamente porque nos permite expressar algoritmos generalizados. Portanto, todas as opções acima não são tão loucas. Mas uma coisa é saber isso na teoria e outra é ver na prática que a abordagem realmente funciona. Afinal, despacho único e sobrecarga de operador em C ++ também devem fornecer um resultado semelhante - mas, na realidade, eles geralmente não funcionam como gostariam.
Além disso, estamos testemunhando algo mais do que havíamos previsto no desenvolvimento da linguagem: não apenas o código generalizado está sendo escrito. Em seguida, tentarei dizer o que, na minha opinião, é mais.
Portanto, existem dois tipos de reutilização de código e são bem diferentes. Um é algoritmos generalizados, e esta é a primeira coisa que eles lembram. O segundo aspecto, menos óbvio, mas parece ser mais importante, é a simplicidade com a qual Julia usa os mesmos tipos de dados em uma ampla variedade de pacotes. Até certo ponto, isso acontece porque os métodos de tipo não se tornam um obstáculo ao seu uso: você não precisa concordar com o autor do tipo sobre as interfaces e métodos que ele herda; você pode simplesmente dizer: "Ah, eu gosto desse tipo de RGB. Vou criar minhas próprias operações, mas gosto da estrutura".
Prefácio Programação múltipla versus sobrecarga de função
Agora, tenho que mencionar a sobrecarga de funções em C ++ ou Java, pois sempre são feitas perguntas sobre eles. À primeira vista, não é diferente do agendamento múltiplo. Qual é a diferença e por que a sobrecarga de função é pior?
Vou começar com um exemplo em 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"
Definimos o tipo abstrato de Pet , apresentamos os subtipos de Dog e Cat para ele, eles têm um campo de nome (o código se repete um pouco, mas é tolerável) e define uma função generalizada de "reunião" que aceita dois objetos do tipo Pet argumentos. Nele, primeiro calculamos a “ação” determinada pelo resultado da chamada da função meet() generalizada e, em seguida, imprimimos a frase que descreve a reunião. Na função meets() , usamos vários despachos para determinar a ação que um animal executa quando encontra outro.
Adicione alguns cães e gatos e veja os resultados da reunião:
fido = Dog("Fido") rex = Dog("Rex") whiskers = Cat("Whiskers") spots = Cat("Spots") encounter(fido, rex) encounter(rex, whiskers) encounter(spots, fido) encounter(whiskers, spots)
Agora vamos "traduzir" o mesmo para C ++ o mais literalmente possível. Defina a classe Pet com o campo name - em C ++, podemos fazer isso (a propósito, uma das vantagens do C ++ é que os campos de dados podem até ser adicionados a tipos abstratos. Depois, definimos a função base meets() , definimos a função encounter() para dois objetos do tipo Pet e, finalmente, defina as classes derivadas Dog e Cat e sobrecarregue o meets() para elas:
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"; }
A função main() , como no código Julia, cria cães e gatos e os faz conhecer:
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; }
Portanto, despacho múltiplo contra sobrecarga de função. Gong!
O que você acha que retornará código com vários despachos?
$ julia pets.jl Fido meets Rex and sniffs Rex meets Whiskers and chases Spots meets Fido and hisses Whiskers meets Spots and slinks
Os animais se encontram, cheiram, assobiam e brincam - como foi planejado.
$ g ++ -o pets pets.cpp && ./pets Fido meets Rex and FALLBACK Rex meets Whiskers and FALLBACK Spots meets Fido and FALLBACK Whiskers meets Spots and FALLBACK
Em todos os casos, a opção "fallback" é retornada.
Porque Porque é assim que a sobrecarga de funções funciona. Se o envio múltiplo funcionasse, os meets(a, b) dentro do encounter() seriam chamados com os tipos específicos que a e b tinham no momento da chamada. Mas a sobrecarga é aplicada; portanto, meets() é chamado para os tipos estáticos b , que nesse caso são Pet .
Portanto, na abordagem C ++, a "tradução" direta do código Julia genérico não fornece o comportamento desejado devido ao fato de o compilador usar tipos derivados estaticamente no estágio de compilação. E o ponto principal é que queremos chamar uma função baseada em tipos concretos reais que as variáveis possuem em tempo de execução. As funções de modelo, embora melhorem um pouco a situação, ainda exigem conhecimento de todos os tipos incluídos estaticamente na expressão em tempo de compilação, e é fácil criar um exemplo em que isso seria impossível.
Para mim, esses exemplos mostram que o despacho múltiplo faz a coisa certa, e todas as outras abordagens simplesmente não são uma aproximação muito boa ao resultado correto.
Agora vamos ver essa tabela. Espero que você ache significativo:
Em idiomas sem despacho, basta escrever f(x, y, ...) , os tipos de todos os argumentos são fixos, ou seja, uma chamada para f() é uma chamada para uma única função f() , que pode estar no programa. O grau de expressividade é constante: chamar f() sempre faz uma e apenas uma coisa. O envio único foi um grande avanço na transição para a OOP nas décadas de 1990 e 2000. A sintaxe do ponto é geralmente usada, da qual as pessoas realmente gostam. E uma oportunidade expressiva adicional aparece: a chamada é despachada de acordo com o tipo de objeto x 1 . Uma oportunidade expressiva é caracterizada pelo poder do conjunto | X 1 | tipos com o método f() . No despacho múltiplo, no entanto, o número de opções possíveis para a função f() é igual ao poder do produto cartesiano de conjuntos de tipos aos quais os argumentos podem pertencer. Na realidade, é claro, quase ninguém precisa de tantas funções diferentes em um programa. Mas o ponto chave aqui é que o programador recebe uma maneira simples e natural de usar qualquer elemento dessa variedade, e isso leva a um crescimento exponencial de oportunidades.
Parte 1. Programação geral
Vamos falar sobre código generalizado - a principal característica do envio múltiplo.
Aqui está um exemplo (completamente artificial) de código genérico:
using LinearAlgebra function inner_sum(A, vs) t = zero(eltype(A)) for v in vs t += inner(v, A, v)
Aqui A é algo parecido com matriz (embora eu não tenha indicado os tipos e posso adivinhar algo pelo nome), vs é o vetor de alguns elementos semelhantes a vetores e, em seguida, o produto escalar é considerado por meio dessa "matriz", para o qual é dada uma definição generalizada sem especificar nenhum tipo. A programação generalizada aqui consiste nessa mesma chamada da função inner() em um loop (conselho profissional: se você deseja escrever código generalizado - basta remover quaisquer restrições de tipo).
Então, "olha, mãe, funciona":
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
Nada de especial, ele calcula algum valor. Mas - o código é escrito em um estilo generalizado e funcionará para todos os A e vs , se ao menos for possível executar as operações correspondentes neles.
Quanto à eficiência em tipos de dados específicos - que sorte. Quero dizer que, para vetores e matrizes densos, esse código o fará "como deveria" - ele gerará código de máquina com a invocação de operações BLAS, etc. etc. Se você passar matrizes estáticas, o compilador levará isso em conta, expandirá os ciclos, aplicará a vetorização - tudo está como deveria.
Mais importante, porém, o código funcionará para novos tipos, e você pode torná-lo não apenas supereficiente, mas super eficiente! Vamos definir um novo tipo (este é o tipo de dados real usado no aprendizado de máquina), um vetor unitário (vetor quente). Este é um vetor em que um dos componentes é 1 e todos os outros são zero. Você pode imaginar isso de maneira muito compacta: tudo o que precisa ser armazenado é o comprimento do vetor e o número do componente diferente de zero.
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)
De fato, esta é realmente a definição de tipo completa do pacote que a adiciona. E com esta definição, inner_sum() também funciona:
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
Mas para um produto escalar, uma definição geral é usada aqui - para esse tipo de dados é lento, não é legal!
Portanto, as definições gerais funcionam, mas nem sempre da maneira ideal, e você pode ocasionalmente encontrar isso ao usar Julia: "bem, uma definição geral é chamada, é por isso que esse código da GPU está funcionando pela quinta hora ..."
Em inner() por padrão, é chamada a definição geral do produto da matriz por um vetor, que quando multiplicado por um vetor unitário retorna uma cópia de uma das colunas do tipo Vector{Float64} . Em seguida, a definição geral do produto escalar dot() é chamada com o vetor unitário e esta coluna, que faz muito trabalho desnecessário. De fato, para cada componente é verificado "você é igual a um? E você?" etc.
Podemos otimizar bastante esse procedimento. Por exemplo, substituindo a multiplicação de matrizes por OneHotVector simplesmente selecionando uma coluna. Tudo bem, defina esse método, e é isso.
*(A::AbstractMatrix, v::OneHotVector) = A[:, v.ind]
E aqui está o poder : dizemos "queremos despachar o segundo argumento " , não importa o que esteja no primeiro. Essa definição simplesmente puxa a linha para fora da matriz e será muito mais rápida que o método geral - a iteração e a soma das colunas são removidas.
Mas você pode ir além e otimizar diretamente inner() , porque multiplicar dois vetores unitários por meio de uma matriz simplesmente extrai um elemento dessa matriz:
inner(v::OneHotVector, A, w::OneHotVector) = A[v.ind, w.ind]
Essa é a prometida eficiência do super-duper. E tudo o que é necessário é definir esse método inner() .
Este exemplo mostra um dos aplicativos de agendamento múltiplo: existe uma definição geral de uma função, mas para alguns tipos de dados ela não funciona da melhor maneira. E, em seguida, adicionamos um método que preserva o comportamento da função para esses tipos, mas funciona com muito mais eficiência .
Mas há outra área - quando não há definição geral de uma função, mas quero adicionar funcionalidade para alguns tipos. Em seguida, você pode adicioná-lo com o mínimo esforço.
E a terceira opção - você só quer ter o mesmo nome de função, mas com comportamento diferente para diferentes tipos de dados - por exemplo, para que uma função se comporte de maneira diferente ao trabalhar com dicionários e matrizes.
Como obter comportamento semelhante em idiomas de despacho único? É possível, mas difícil. Problema: ao sobrecarregar a função * era necessário despachar no segundo argumento, e não no primeiro. Você pode fazer o despacho duplo: primeiro, despache pelo primeiro argumento e chame o método AbstractMatrix.*(v) . E esse método, por sua vez, chama algo como v.__rmul__(A) , ou seja, o segundo argumento na chamada original agora se tornou o objeto cujo método está realmente sendo chamado. __rmul__ aqui retirado do Python, onde esse comportamento é um padrão padrão, mas parece funcionar apenas para adição e multiplicação. I.e. o problema do envio duplo será resolvido se quisermos chamar uma função chamada + ou * , caso contrário - infelizmente, não nos dias de hoje. Em C ++ e outras línguas - você precisa construir sua bicicleta.
OK, e quanto a inner() ? Agora existem três argumentos, e o envio continua no primeiro e no terceiro. O que fazer em idiomas com envio único não está claro. "Expedição tripla" eu nunca conheci ao vivo. Não há boas soluções. Geralmente, quando surge uma necessidade semelhante (e em códigos numéricos aparece com muita frequência), as pessoas acabam implementando seu sistema de envio múltiplo. Se você olhar para grandes projetos para cálculos numéricos em Python, ficará surpreso com quantos deles são assim. Naturalmente, essas implementações funcionam situacionalmente, mal projetadas, cheias de bugs e lentas ( referência à décima regra de Greenspan - aprox. Transl. ), Porque Jeff Besancon não trabalhou em nenhum desses projetos (o autor e o principal desenvolvedor do sistema de envio de tipos em Julia - aprox. tradução ).
Parte 2. Tipos Gerais
Vou passar para o lado oposto do paradigma de Julia - os tipos gerais. Este, na minha opinião, é o principal "cavalo de batalha" da linguagem, porque é nessa área que observo um alto nível de reutilização de código.
Por exemplo, suponha que você tenha um tipo RGB, como o ColorTypes.jl. Não há nada complicado, apenas três valores são reunidos. Por uma questão de simplicidade, assumimos que o tipo não é paramétrico (mas poderia ter sido), e o autor definiu várias operações básicas para ele que achou úteis. Você pega esse tipo e pensa: "Hmm, eu gostaria de adicionar mais operações nesse tipo". Por exemplo, imagine RGB como um espaço vetorial (que, estritamente falando, está incorreto, mas se resume a uma primeira aproximação). Em Julia, você simplesmente pega e adiciona no seu código todas as operações que estão faltando.
A questão surge - e cho? Por que estou me concentrando tanto nisso? Acontece que em linguagens orientadas a objetos baseadas em classes, essa abordagem é surpreendentemente difícil de implementar. Como as definições de método nessas linguagens estão dentro da definição de classe, existem apenas duas maneiras de adicionar um método: edite o código da classe para adicionar o comportamento desejado ou crie uma classe herdada com os métodos necessários.
A primeira opção aumenta a definição da classe base e também força o desenvolvedor da classe base a cuidar do suporte de todos os métodos adicionados ao alterar o código. O que um dia poderia tornar essa classe sem suporte?
A herança é uma opção clássica "recomendada", mas também não sem falhas. Primeiro, você precisa alterar o nome da classe - deixe que agora não seja RGB , mas MyRGB . Além disso, novos métodos não funcionarão mais para a classe RGB original; se quiser aplicar meu novo método a um objeto RGB criado no código de outra pessoa, preciso convertê-lo ou quebrá-lo no MyRGB . Mas isso não é o pior. Se eu fiz uma aula MyRGB com algumas funcionalidades adicionais, outra pessoa OurRGB , etc. - então, se alguém quiser uma classe com todas as novas funcionalidades, será necessário usar herança múltipla (e isso é apenas se a linguagem de programação permitir!).
Então, ambas as opções são mais ou menos. Existem, no entanto, outras soluções:
- Coloque o funcional em uma função externa em vez do método de classe - vá para
f(x, y) vez de xf(y) . Mas então o comportamento generalizado é perdido. - Cuspir na reutilização de código (e, parece-me, em muitos casos, isso acontece). Apenas copie uma classe
RGB alienígena e adicione o que está faltando.
O principal recurso de Julia em termos de reutilização de código é quase completamente reduzido ao fato de o método ser definido fora do tipo . Só isso. Faça o mesmo em idiomas de envio único - e os tipos podem ser reutilizados com a mesma facilidade. A história toda com “vamos fazer parte dos métodos da classe” é uma idéia mais ou menos, na verdade. É verdade que há um bom argumento - o uso de classes como namespaces. Se eu escrever que xf(y) - f() não precisa estar no espaço para nome atual, ele deverá ser pesquisado no espaço para nome x . Sim, isso é uma coisa boa - mas vale a pena todos os outros problemas? Eu não sei Na minha opinião, não (embora minha opinião, como você possa imaginar, seja um pouco tendenciosa).
Epílogo. O problema da expressão
Há um problema de programação que foi notado nos anos 70. Está amplamente relacionado à verificação de tipo estático, porque apareceu nesses idiomas. É verdade que acho que isso não tem nada a ver com a verificação de tipo estático. A essência do problema é a seguinte: é possível alterar o modelo de dados e o conjunto de operações nos dados ao mesmo tempo, sem recorrer a técnicas duvidosas.
O problema pode ser mais ou menos reduzido ao seguinte:
- é possível adicionar novos tipos de dados com facilidade e sem erros aos quais os métodos existentes são aplicáveis e
- É possível adicionar novas operações em tipos existentes .
(1) facilmente realizado em linguagens orientadas a objetos e difícil em funcional, (2) - vice-versa. Nesse sentido, podemos apenas falar sobre o dualismo das abordagens OOP e FP.
Nos idiomas de despacho múltiplo, as duas operações são fáceis. (1) , (2) — . , . ( https://en.wikipedia.org/wiki/Expression_problem ), . ? , , . , " , " — " " . " , " , , .
, . , , — .
, Julia ( ), . .