Bajo la escena, se propone un descifrado del informe de Stefan Karpinsky, uno de los desarrolladores clave del lenguaje Julia. En el informe, analiza los resultados inesperados del despacho múltiple conveniente y eficiente, tomado como el paradigma principal de Julia.
De un traductor : el título del informe hace referencia a un artículo de Eugene Wigner, "La eficacia incomprensible de las matemáticas en las ciencias naturales" .
La programación múltiple es un paradigma clave del lenguaje Julia, y durante su existencia, nosotros, los desarrolladores del lenguaje, notamos algo esperado, pero al mismo tiempo desconcertante. Al menos no esperábamos esto en la medida en que lo vimos. Esto es algo: un asombroso nivel de reutilización de código en el ecosistema de Julia, que es mucho más alto que en cualquier otro idioma que conozco.
Constantemente vemos que algunas personas escriben código generalizado, otra persona define un nuevo tipo de datos, estas personas no están familiarizadas entre sí, y luego alguien aplica este código a este tipo de datos inusual ... Y todo simplemente funciona. Y esto sucede sorprendentemente a menudo .
Siempre pensé que ese comportamiento debería esperarse de la programación orientada a objetos, pero utilicé muchos lenguajes orientados a objetos, y resulta que generalmente no todo funciona en ellos. Por lo tanto, en algún momento pensé: ¿por qué Julia es un lenguaje tan efectivo en este sentido? ¿Por qué el nivel de reutilización del código es tan alto allí? Y también: ¿qué lecciones se pueden aprender de esto que otros idiomas podrían tomar prestados de Julia para mejorar?
A veces, cuando digo esto, el público no me cree, pero usted ya está en JuliaCon, por lo que sabe lo que está sucediendo, por lo que me centraré en por qué, en mi opinión, esto está sucediendo.
Pero para empezar, uno de mis ejemplos favoritos.
En la diapositiva es el resultado del trabajo de Chris Rakaukas. Escribe todo tipo de paquetes muy generalizados para resolver ecuaciones diferenciales. Puedes alimentar números duales o BigFloat, lo que quieras. Y de alguna manera decidió que quería ver el error del resultado de integración. Y había un paquete de Mediciones que puede rastrear tanto el valor de una cantidad física como la propagación de un error a través de una secuencia de fórmulas. Este paquete también admite una sintaxis elegante para valores de incertidumbre utilizando el carácter Unicode ± . Aquí en la diapositiva se muestra que la aceleración de la gravedad, la longitud del péndulo, la velocidad inicial, el ángulo de desviación se conocen con algún tipo de error. Entonces, usted define un péndulo simple, pasa sus ecuaciones de movimiento a través del ODE solucionador y - ¡bam! Todo funciona . Y ves un gráfico con inexactitudes de bigote. Y todavía no demuestro que el código para dibujar el gráfico también está generalizado, y simplemente ingresas el valor con un error de Measurements.jl y obtienes un gráfico con errores.
El nivel de compatibilidad de los diferentes paquetes y la generalización del código es simplemente una carga de cerebro. ¿Cómo funciona ? Resulta que si.
Bueno, no es que no esperáramos esto en absoluto. Después de todo, incluimos el concepto de despacho múltiple en el lenguaje precisamente porque nos permite expresar algoritmos generalizados. Entonces, todo lo anterior no es tan loco. Pero una cosa es saber esto en teoría y otra ver en la práctica que el enfoque realmente funciona. Después de todo, el despacho único y la sobrecarga del operador en C ++ también deberían dar un resultado similar, pero en realidad a menudo no funcionan como les gustaría.
Además, estamos presenciando algo más de lo que habíamos previsto al desarrollar el lenguaje: no solo se está escribiendo un código generalizado. A continuación, intentaré decir qué, en mi opinión, es más.
Entonces, hay dos tipos de reutilización de código, y son bastante diferentes. Uno es algoritmos generalizados, y esto es lo primero que recuerdan. El segundo aspecto, menos obvio, pero que parece ser más importante, es la simplicidad con la que Julia usa los mismos tipos de datos en una amplia variedad de paquetes. Hasta cierto punto, esto sucede porque los métodos de tipo no se convierten en un obstáculo para su uso: no es necesario estar de acuerdo con el autor del tipo sobre las interfaces y los métodos que hereda; simplemente puede decir: "Oh, me gusta este tipo de RGB. Desarrollaré mis propias operaciones, pero me gusta su estructura".
Prólogo Programación múltiple versus sobrecarga de funciones
Ahora tengo que mencionar la sobrecarga de funciones en C ++ o Java, ya que constantemente me hacen preguntas sobre ellas. A primera vista, no es diferente de la programación múltiple. ¿Cuál es la diferencia y por qué es peor la sobrecarga de funciones?
Comenzaré con un ejemplo sobre 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 un tipo abstracto de Pet , le presentamos los subtipos de Dog y Cat , tienen un campo de nombre (el código se repite un poco, pero es tolerable) y define una función generalizada de "reunión" que toma dos objetos de tipo Pet argumentos. En él, primero calculamos la "acción" determinada por el resultado de llamar a la función generalizada meet() , y luego imprimimos la oración que describe la reunión. En la función meets() , utilizamos el envío múltiple para determinar la acción que realiza un animal cuando se encuentra con otro.
Agregue un par de perros y un par de gatos y vea los resultados de la reunión:
fido = Dog("Fido") rex = Dog("Rex") whiskers = Cat("Whiskers") spots = Cat("Spots") encounter(fido, rex) encounter(rex, whiskers) encounter(spots, fido) encounter(whiskers, spots)
Ahora "traduciremos" lo mismo a C ++ lo más literalmente posible. Defina la clase Pet con el campo de name : en C ++ podemos hacer esto (por cierto, una de las ventajas de C ++ es que los campos de datos pueden incluso agregarse a tipos abstractos. Luego definimos la función de meets() , definir la función de encounter() para dos objetos de tipo Pet y, Finalmente, defina las clases derivadas Dog y Cat y realice una sobrecarga para ellos meets() :
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 función main() , como en el código de Julia, crea perros y gatos y los hace cumplir:
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; }
Entonces, despacho múltiple contra sobrecarga de funciones. Gong!
¿Qué crees que devolverá el código con despacho múltiple?
$ julia pets.jl Fido meets Rex and sniffs Rex meets Whiskers and chases Spots meets Fido and hisses Whiskers meets Spots and slinks
Los animales se encuentran, huelen, silban y se ponen al día, como se pretendía.
$ g ++ -o mascotas pets.cpp && ./pets Fido meets Rex and FALLBACK Rex meets Whiskers and FALLBACK Spots meets Fido and FALLBACK Whiskers meets Spots and FALLBACK
En todos los casos, se devuelve la opción "reserva".
Por qué Porque así es como funciona la sobrecarga de funciones. Si el despacho múltiple funcionó, entonces se meets(a, b) en el encounter() interno encounter() con los tipos específicos que a y b tenían en el momento de la llamada. Pero se aplica una sobrecarga, por lo tanto, se llama a meets() para los tipos estáticos b , que en este caso son Pet .
Entonces, en el enfoque de C ++, la "traducción" directa del código genérico de Julia no proporciona el comportamiento deseado debido al hecho de que el compilador utiliza tipos que se derivan estáticamente en la etapa de compilación. Y el punto es que queremos llamar a una función basada en tipos concretos reales que las variables tienen en tiempo de ejecución. Las funciones de plantilla, aunque mejoran un poco la situación, aún requieren conocimiento de todos los tipos incluidos en la expresión estáticamente en tiempo de compilación, y es fácil encontrar un ejemplo en el que esto sería imposible.
Para mí, tales ejemplos muestran que el despacho múltiple hace lo correcto, y todos los demás enfoques no son una muy buena aproximación al resultado correcto.
Ahora veamos una tabla así. Espero que lo encuentres significativo:
En lenguajes sin despacho, simplemente escribe f(x, y, ...) , los tipos de todos los argumentos son fijos, es decir una llamada a f() es una llamada a una sola función f() , que puede estar en el programa. El grado de expresividad es constante: llamar a f() siempre hace una y solo una cosa. El despacho único fue un gran avance en la transición a la OOP en los años 90 y 2000. La sintaxis de puntos generalmente se usa, lo que a la gente realmente le gusta. Y aparece una oportunidad expresiva adicional: la llamada se despacha de acuerdo con el tipo de objeto x 1 . Una oportunidad expresiva se caracteriza por el poder del conjunto | X 1 | tipos que tienen el método f() . Sin embargo, en el despacho múltiple, el número de posibles opciones para la función f() es igual a la potencia del producto cartesiano de conjuntos de tipos a los que pueden pertenecer los argumentos. En realidad, por supuesto, casi nadie necesita tantas funciones diferentes en un solo programa. Pero el punto clave aquí es que el programador recibe una forma simple y natural de usar cualquier elemento de esta variedad, y esto conduce a un crecimiento exponencial de oportunidades.
Parte 1. Programación general
Hablemos del código generalizado, la característica principal del despacho múltiple.
Aquí hay un ejemplo (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)
Aquí A es algo similar a una matriz (aunque no indiqué los tipos, y puedo adivinar algo por su nombre), vs es el vector de algunos elementos similares a vectores, y luego el producto escalar se considera a través de esta "matriz", para lo cual se da una definición generalizada sin especificar ningún tipo. La programación generalizada aquí consiste en esta llamada de la función inner() en un bucle (consejo profesional: si desea escribir código generalizado, simplemente elimine cualquier restricción de tipo).
Entonces, "mira, mamá, 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 especial, calcula algún valor. Pero , el código está escrito en un estilo generalizado y funcionará para cualquier A y vs , si solo fuera posible realizar las operaciones correspondientes en ellos.
En cuanto a la eficiencia en tipos de datos específicos, qué suerte. Quiero decir que para vectores y matrices densas este código lo hará "como debería", generará código de máquina con la invocación de operaciones BLAS, etc. etc. Si pasa matrices estáticas, el compilador lo tendrá en cuenta, ampliará los ciclos, aplicará la vectorización: todo es como debería.
Pero lo que es más importante, el código funcionará para nuevos tipos, ¡y puede hacerlo no solo súper eficiente, sino súper eficiente! Definamos un nuevo tipo (este es el tipo de datos real que se utiliza en el aprendizaje automático), un vector unitario (vector de un solo hot). Este es un vector en el que uno de los componentes es 1, y todos los demás son cero. Puede imaginarlo de manera muy compacta: todo lo que necesita almacenarse es la longitud del vector y el número del componente distinto de cero.
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 hecho, esta es realmente la definición de tipo completo del paquete que lo agrega. Y con esta definición, inner_sum() también 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
Pero para un producto escalar, aquí se usa una definición general: ¡para este tipo de datos es lento, no genial!
Entonces, las definiciones generales funcionan, pero no siempre de manera óptima, y ocasionalmente puede encontrar esto cuando se usa a Julia: "bueno, se llama a una definición general, es por eso que este código GPU ha estado funcionando durante la quinta hora ..."
En inner() por defecto, se llama a la definición general del producto matricial por un vector, que cuando se multiplica por un vector unitario devuelve una copia de una de las columnas del tipo Vector{Float64} . Luego, la definición general del producto escalar dot() se llama con el vector unitario y esta columna, que hace mucho trabajo innecesario. De hecho, para cada componente está marcado "¿eres igual a uno? ¿Y tú?" etc.
Podemos optimizar en gran medida este procedimiento. Por ejemplo, reemplazando la multiplicación de matrices con OneHotVector simplemente seleccionando una columna. Bien, define este método, y eso es todo.
*(A::AbstractMatrix, v::OneHotVector) = A[:, v.ind]
Y aquí está, poder : decimos "queremos enviarnos al segundo argumento " , sin importar lo que haya en el primero. Tal definición simplemente sacará la fila de la matriz y será mucho más rápido que el método general: se elimina la iteración y la suma de columnas.
Pero puede ir más allá y optimizar directamente inner() , porque multiplicar dos vectores unitarios a través de una matriz simplemente extrae un elemento de esta matriz:
inner(v::OneHotVector, A, w::OneHotVector) = A[v.ind, w.ind]
Esa es la prometida eficiencia súper duper. Y todo lo que se necesita es definir este método inner() .
Este ejemplo muestra una de las aplicaciones de la programación múltiple: existe una definición general de una función, pero para algunos tipos de datos no funciona de manera óptima. Y luego agregamos un método que preserva el comportamiento de la función para estos tipos, pero funciona de manera mucho más eficiente .
Pero hay otra área: cuando no hay una definición general de una función, pero quiero agregar funcionalidad para algunos tipos. Luego puede agregarlo con un mínimo esfuerzo.
Y la tercera opción: solo desea tener el mismo nombre de función, pero con un comportamiento diferente para diferentes tipos de datos, por ejemplo, para que una función se comporte de manera diferente cuando se trabaja con diccionarios y matrices.
¿Cómo obtener un comportamiento similar en los idiomas de despacho único? Es posible, pero difícil. Problema: al sobrecargar la función * era necesario despachar el segundo argumento y no el primero. Puede hacer doble despacho: primero, despachar por el primer argumento y llamar al método AbstractMatrix.*(v) . Y este método, a su vez, llama a algo como v.__rmul__(A) , es decir El segundo argumento en la llamada original se ha convertido en el objeto cuyo método se llama realmente. __rmul__ toma __rmul__ de Python, donde dicho comportamiento es un patrón estándar, pero parece funcionar solo para la suma y la multiplicación. Es decir El problema del doble despacho se resuelve si queremos llamar a una función llamada + o * , de lo contrario, por desgracia, no es nuestro día. En C ++ y otros lenguajes, debes construir tu bicicleta.
OK, ¿qué hay de inner() ? Ahora hay tres argumentos, y el despacho continúa con el primero y el tercero. Qué hacer en idiomas con despacho único no está claro. "Triple despacho" que nunca conocí en vivo. No hay buenas soluciones. Por lo general, cuando surge una necesidad similar (y en los códigos numéricos aparece con mucha frecuencia), las personas eventualmente implementan su sistema de despacho múltiple. Si observa proyectos grandes para cálculos numéricos en Python, se sorprenderá de cuántos de ellos van de esta manera. Naturalmente, tales implementaciones funcionan situacionalmente, mal diseñadas, llenas de errores y lentas ( referencia a la décima regla de Greenspan - aprox. Transl. ), Porque Jeff Besancon no trabajó en ninguno de estos proyectos (el autor y jefe de desarrollo del sistema de despacho tipo en Julia - aprox. transl. ).
Parte 2. Tipos generales
Pasaré al reverso del paradigma de Julia: los tipos generales. Este, en mi opinión, es el principal "caballo de batalla" del lenguaje, porque es en esta área donde observo un alto nivel de reutilización de código.
Por ejemplo, suponga que tiene un tipo RGB, como lo que tiene ColorTypes.jl. No hay nada complicado, solo se unen tres valores. En aras de la simplicidad, suponemos que el tipo no es paramétrico (pero podría haber sido), y el autor definió varias operaciones básicas para él que le resultaron útiles. Tomas este tipo y piensas: "Hmm, me gustaría agregar más operaciones en este tipo". Por ejemplo, imagine RGB como un espacio vectorial (que, estrictamente hablando, es incorrecto, pero se reducirá a una primera aproximación). En Julia, simplemente toma y agrega en su código todas las operaciones que faltan.
Surge la pregunta, ¿ y cho? ¿Por qué me estoy centrando tanto en esto? Resulta que en lenguajes orientados a objetos basados en clases, este enfoque es sorprendentemente difícil de implementar. Dado que las definiciones de métodos en estos lenguajes están dentro de la definición de clase, solo hay dos formas de agregar un método: edite el código de clase para agregar el comportamiento deseado o cree una clase heredera con los métodos necesarios.
La primera opción infla la definición de la clase base y también obliga al desarrollador de la clase base a cuidar el soporte de todos los métodos agregados al cambiar el código. ¿Qué podría algún día hacer que tal clase no sea compatible?
La herencia es una opción clásica "recomendada", pero no sin fallas. Primero, debe cambiar el nombre de la clase; deje que ahora no sea RGB , sino MyRGB . Además, los nuevos métodos ya no funcionarán para la clase RGB original; si deseo aplicar mi nuevo método a un objeto RGB creado en el código de otra persona, necesito convertirlo o envolverlo en MyRGB . Pero esto no es lo peor. Si hice una clase MyRGB con alguna funcionalidad adicional, alguien más OurRGB , etc. - entonces, si alguien quiere una clase que tenga todas las nuevas funcionalidades, debe usar herencia múltiple (¡y esto es solo si el lenguaje de programación lo permite!).
Entonces, ambas opciones son más o menos. Sin embargo, hay otras soluciones:
- Coloque lo funcional en una función externa en lugar del método de clase: vaya a
f(x, y) lugar de xf(y) . Pero luego se pierde el comportamiento generalizado. - Escupe sobre la reutilización del código (y, me parece, en muchos casos esto sucede). Simplemente copie una clase
RGB alienígena y agregue lo que falta.
La característica clave de Julia en términos de reutilización de código se reduce casi por completo al hecho de que el método se define fuera del tipo . Eso es todo. Haga lo mismo en los idiomas de envío único, y los tipos se pueden reutilizar con la misma facilidad. Toda la historia con "hagamos que los métodos sean parte de la clase" es una idea regular, de hecho. Es cierto que hay un buen punto: el uso de clases como espacios de nombres. Si escribo xf(y) - no se requiere que f() esté en el espacio de nombres actual, debe buscarse en el espacio de nombres x . Sí, esto es algo bueno, pero ¿vale la pena todos los demás problemas? No lo se En mi opinión, no (aunque mi opinión, como se puede adivinar, es ligeramente parcial).
Epílogo El problema de la expresion
Hay un problema de programación que se notó en los años 70. Está relacionado en gran medida con la verificación de tipos estáticos, porque apareció en dichos idiomas. Es cierto, creo que no tiene nada que ver con la verificación de tipos estáticos. La esencia del problema es la siguiente: ¿es posible cambiar el modelo de datos y el conjunto de operaciones en los datos al mismo tiempo, sin recurrir a técnicas dudosas?
El problema se puede reducir más o menos a lo siguiente:
- ¿Es posible agregar fácilmente y sin errores nuevos tipos de datos a los que los métodos existentes son aplicables y
- ¿Es posible agregar nuevas operaciones en los tipos existentes ?
(1) hecho fácilmente en lenguajes orientados a objetos y difícil en funcional, (2) - viceversa. En este sentido, podemos hablar sobre el dualismo de los enfoques OOP y FP.
En lenguajes de despacho múltiple, ambas operaciones son fáciles. (1) , (2) — . , . ( https://en.wikipedia.org/wiki/Expression_problem ), . ? , , . , " , " — " " . " , " , , .
, . , , — .
, Julia ( ), . .