que - historia del algebra

¿Qué es un "álgebra multigrado" y cómo lo uso para resolver "problemas reales"? (3)

Creo que hablaba de programación genérica ( acuñó el término ), ya sea en el contexto de esta charla sobre el STL, o ''en general'', en el sentido de:

programación en una especie de interfaz que describe algo que podría adaptarse a todos (y con suerte a varios) tipos (por lo tanto, varios ordenados), ...
... siempre que tengan algunas propiedades , a menudo algo sobre la naturaleza de algunas operaciones en elementos de ese tipo (por lo tanto, álgebras).

Para hacer (1), necesita tener una manera de especificar un programa que tome un tipo como parámetro , es decir, polimorfismo , y para hacer (2), necesita una manera de decir que también desea que ese tipo lleve a cabo operaciones específicas (y, siempre que pueda expresarlas, propiedades ). En efecto, estás parametrizando tu programa por la estructura de los datos que manipula. El paradigma se llama en algunos lugares polimorfismo delimitado, programación de tipos de datos genéricos, ... que refleja que los lenguajes tienen diferentes nociones de cómo implementar esa idea, de ahí el ''tipo de'' en cursiva anterior.

Para C ++, parece que, al menos para Stepanov, esto corresponde a las plantillas (aunque las ideas sobre cómo hacerlo mejor todavía están evolucionando ).
Para los lenguajes de OO (Java genérico, C #), las restricciones en los parámetros de tipo se expresan típicamente utilizando límites de subtipo (''comodines delimitados'' ...).
Para Haskell o Scala, usted tiene (respectivamente, y de manera similar) clases de tipo o implícitas .
La familia de idiomas ML prefiere hacer esto usando módulos .
tenga en cuenta que un número de asistentes de prueba (que pueden expresar propiedades de "honesto a dios" como tipos) han desarrollado un sabor de clases de tipo: Isabelle, Coq, Matita son tales ejemplos

Tenga en cuenta que Stepanov acaba de co-escribió un libro completo dando un desarrollo exhaustivo de una biblioteca que encarna exactamente lo que (creo) que quiere decir. Entonces, si quieres ejemplos en C ++ , este es definitivamente el lugar donde debes buscar. Tenga en cuenta también que esto está mucho más evolucionado que el consejo ahora común de codificación contra una interfaz, en lugar de un objeto .

Por ''ejemplo práctico'', no sé si te refieres a ''cómo'' o ''por qué'' uno lo usa. Para dar una respuesta caricaturalmente rápida al ''por qué'', la genérico es agradable porque, un poco como el polimorfismo ordinario, te permite reutilizar el código . Pero mas importante:

El código polimórfico que tiene que funcionar con todos los tipos a menudo no puede hacer nada interesante, mientras que tener una interfaz restringida para jugar le permite escribir programas más ricos.
al especificar cómo esa interfaz se ajusta a algunos de sus datos, tiene una forma segura para seleccionar solo aquellos elementos que se adapten a sus necesidades. Por ejemplo, probablemente sepa que el operador de reducción (la reduce de Python y Hadoop, fold de un montón de lenguajes funcionales) es paralelizable solo si el orden en el que aplica la función de reducción no importa ( + , x , min , and trabajar, pero establecer la diferencia no lo hace). Si tiene una noción de ''tipo equipado con una operación asociativa '', sabe que podrá realizar una reducción paralela.
cualquier sobrecarga incurrida por genericidad ocurre en tiempo de compilación. Por ejemplo, las plantillas son legendariamente rápidas.

Si has visto algún Java genérico, mira, por ejemplo, la interfaz genérica Comparable . Define solo una operación, pero el contrato que hace, aunque básico, es muy de sabor algebraico. Yo cito:

Para los matemáticamente inclinados, la relación que define el orden natural en una clase dada C es:
{(x, y) such that x.compareTo((Object)y) <= 0}.
El cociente para este orden total es:
{(x, y) such that x.compareTo((Object)y) == 0}.
Se deduce inmediatamente del contrato para compareTo que el cociente es una relación de equivalencia en C,> y que el orden natural es un pedido total en C.

Ahora, puedo escribir un método que selecciona el mínimo, una vez, y usarlo para cualquier tipo que se adapte a esta interfaz :

public static <T extends Comparable<T>> T min (T x, T y) { if (x.compare(y) < 0) x; else y; }

Naturalmente, dado que la forma en que las construcciones programativas implementan esa noción varía enormemente, lo que obtendrá en términos de usabilidad y expresividad también variará. Tal vez no debería juzgar la programación genérica de datos solo por lenguajes OO como C ++ o Java, pero ya he escrito demasiado para comenzar con la asignación del módulo o la generación automática de instancias de clases de tipos.

Aparentemente, Alexander Stepanov declaró lo siguiente en una interview :

"Me parece que la programación orientada a objetos (OOP [programación orientada a objetos)] es técnicamente errónea. Intenta descomponer el mundo en términos de interfaces que varían en un solo tipo. Para hacer frente a los problemas reales, necesita álgebras multisordas: familias de interfaces que abarcan varios tipos. " [Énfasis agregado.]

Ignorando su afirmación con respecto a OOP por un momento, ¿qué son las "álgebras multirresidentes", más allá de su definición breve, y puede dar un ejemplo práctico de cómo se usan (en el idioma de su elección)?

Llego tarde, pero quizás te sea útil. El usuario huitseeker escribió una excelente respuesta desde el punto de vista del diseño de software. Quiero responder su pregunta desde el punto de vista de las matemáticas. Antes de sumergirse en el mundo del software, Alex Stepanov era matemático y estudió álgebra abstract y universal . Y a menudo trató de aportar fundamentos matemáticos rigurosos en el mundo del software y el diseño de algoritmos. En sus libros De Matemáticas a Programación Genérica y Elementos de Programación , defiende esta práctica de diseño. Sus ideas sobre la mezcla de conceptos de estructuras algebraicas y diseño de software se realizaron en la noción de generic programming . Y ahora hablemos de su cita:

Para lidiar con los problemas reales, necesitas álgebras multirresortadas: familias de interfaces que abarcan varios tipos

En mi opinión, hay dos conceptos principales que quería mencionar aquí: la idea del tipo de datos abstracto ( ADT ) y la estructura algebraica . Primer concepto: ADT . ADT - es un modelo matemático para un tipo de datos donde un tipo de datos se define solo por su semántica. Stepanov contrastó la idea de ADT con la idea de object en el sentido de OOP. Los objetos contienen datos y estados, mientras que los ADT no . ADT: es una behavioural abstraction , un operation cluster que describe la interacción con los datos. La abstracción conductual se describe por completo mediante la especificación algebraica del tipo de datos abstractos. Puede leer más sobre esto en el documento original de Liskov y Zilles ; también le recomiendo un documento orientado a objetos frente a tipos de datos abstractos de William R. Cook .

( Discalímero : puede omitir este párrafo, porque es más "matemático y no tan importante" ) Al principio, quiero aclarar algunos términos. Cuando hablo de la algebraic structure es lo mismo que el álgebra. La palabra algebra también se usa a menudo para una estructura algebraica. Para ser más precisos cuando hablamos de estructuras algebraicas (álgebras), generalmente nos referimos a álgebra sobre una teoría algebraica . Hay un concepto de la variedad de álgebras , porque hay varias nociones de una estructura algebraica en un objeto de alguna categoría. Por definición, una algebraic theory (álgebra sobre ella) consiste en una especificación de operaciones y leyes que estas operaciones deben cumplir: esta es una definición de trabajo de la estructura algebraica que usaremos, y esta definición, creo, Stepanov mencionó implícitamente en el citar.

El segundo concepto que Stepanov quería mencionar es la propiedad más interesante de los ADT: pueden modelarse formalmente directamente como many-sorted algebraic structures . Hablemos de eso más formalmente. Una estructura algebraica: es una carrier set con una o más operaciones finitarias definidas en ella. Estas operaciones generalmente se definen no en un conjunto sino en múltiples. Por ejemplo, definamos y álgebra que modela la concatenación de cadenas. Este álgebra se definirá no sobre un conjunto de cadenas, sino sobre dos conjuntos: series de cadenas S y números naturales de N , porque podemos definir una operación que puede concatenar una cadena consigo misma un número finito de veces. Entonces, esta operación tomará dos operandos, que pertenecen a diferentes conjuntos subyacentes (portadores): S y N Set que define estos diferentes operandos (sus tipos) en álgebra llamados un conjunto de sorts . Sort es un análogo algebraico del tipo. Álgebra con múltiples géneros llamados álgebra multigrupo. En el álgebra universal, una signature enumera las operaciones que caracterizan una estructura algebraica. Una estructura algebraica ordenada por muchos puede tener un número arbitrario de dominios. Los géneros son parte de la firma, y desempeñan el papel de nombres para los diferentes dominios. Las firmas ordenadas también prescriben en qué tipo se definen las funciones y las relaciones de una estructura algebraica ordenada. Para una variedad ordenada de álgebras, una firma es un conjunto, cuyos elementos se denominan operaciones, a cada uno de los cuales se le asigna un número cardinal (0,1,2, ...) llamado aridad. Una firma de álgebra de orden múltiple se puede definir como Σ = (S,OP,A) , donde S - conjunto de nombres de clasificación (tipos), OP - conjunto de nombres de operación y A - aridades como antes, excepto que ahora una aridad es una lista ( sequence o, en general, monoides libres ) de clasificaciones de entrada en lugar de simplemente un número natural (la longitud de la lista) junto con una clasificación de salida. Ahora podemos crear una especificación algebraica de un tipo de datos abstractos ADT como un triple:

ADT = (N, Σ, E)

, donde N - nombre del tipo de datos abstracto, Σ = (S,OP,A) - firma de estructura algebraica con ordenación múltiple, E = {e1, e2, …,en} - es una colección finita de igualdades en la firma. Como puede ver ahora, tenemos una descripción matemática rigurosa de ADT. En matemáticas, las estructuras algebraicas de muchos ordenamientos se utilizan a menudo como una herramienta conveniente, incluso cuando podrían evitarse con un pequeño esfuerzo. Las estructuras algebraicas ordenadas por muchos raras veces se definen de manera rigurosa, porque es sencillo llevar a cabo la generalización explícitamente. Es por eso que la teoría de álgebras clasificadas se puede aplicar con éxito al diseño de software.

Entonces, Alex Stepanov quiso decir que prefiere ADT y la programación genérica a OOP, porque así podemos crear programas con bases matemáticas / algebraicas rigurosas. Aprecio mucho sus esfuerzos. Todos sabemos que el diseño algebraico es siempre correcto, riguroso, bello, simple y nos da mejores abstracciones.

No es que sea un experto en la teoría de ninguno de ellos, pero echemos un vistazo a la cita para poder tratar de comprender mejor la discusión.

Para lidiar con los problemas reales, necesita álgebras multirresortables: familias de interfaces que abarcan varios tipos.

A partir de mis lecturas, creo que las familias de interfaces que abarcan múltiples tipos se parecen mucho a las clases de tipos de Haskell, que es similar a los conceptos de C ++. Tome una clase de tipo como Foldable en realidad es una interfaz de tipo parametrizada, es decir. Una familia de interfaces que abarcan múltiples tipos. Por lo que respecta a su pregunta sobre cómo resolver problemas con álgebras multisordas, la programación genérica tiene que ver con eso si lo toma para significar clases de tipo o conceptos.