oop - ¿Por qué los tipos de datos algebraicos Haskell "están cerrados"?
types functional-programming (8)
Corrígeme si me equivoco, pero parece que los tipos de datos algebraicos en Haskell son útiles en muchos de los casos en los que usarías clases y herencia en los lenguajes OO. Pero hay una gran diferencia: una vez que se declara un tipo de datos algebraicos, no se puede extender a otro lado. Está cerrado". En OO, puede extender clases ya definidas. Por ejemplo:
data Maybe a = Nothing | Just a
No hay manera de que de alguna manera agregue otra opción a este tipo más adelante sin modificar esta declaración. ¿Cuáles son los beneficios de este sistema? Parece que el modo OO sería mucho más extensible.
Algunas respuestas excelentes a esta pregunta (ciertamente vieja), pero siento que tengo que invertir mis pocos centavos.
No hay manera de que de alguna manera agregue otra opción a este tipo más adelante sin modificar esta declaración. ¿Cuáles son los beneficios de este sistema? Parece que el modo OO sería mucho más extensible.
La respuesta a esto, creo, es que el tipo de extensibilidad que ofrecen las sumas abiertas no siempre es una ventaja, y que, en consecuencia, el hecho de que OO te obligue a hacerlo es una debilidad.
La ventaja de uniones cerradas es su exhaustividad : si ha arreglado todas las alternativas en tiempo de compilación, puede estar seguro de que no habrá casos imprevistos que su código no pueda manejar. Esta es una propiedad valiosa en muchos dominios problemáticos, por ejemplo, en árboles sintácticos abstractos para idiomas. Si está escribiendo un compilador, las expresiones del lenguaje se encuentran en un conjunto predefinido y cerrado de subcausas: no desea que las personas puedan agregar nuevas subcajas en tiempo de ejecución que su compilador no comprenda.
De hecho, los AST compiladores son uno de los ejemplos motivadores de la Gang of Four clásica para Visitor Pattern, que es la contraparte de OOP para sumas cerradas y concordancia exhaustiva de patrones. Es instructivo reflexionar sobre el hecho de que los programadores de OO terminaron inventando un patrón para recuperar sumas cerradas.
Del mismo modo, los programadores procedimentales y funcionales han inventado patrones para obtener el efecto de las sumas. El más simple es la codificación "registro de funciones", que corresponde a las interfaces OO. Un registro de funciones es, de hecho, una tabla de envío . (¡Nótese que los programadores C han estado usando esta técnica durante siglos!) El truco es que a menudo hay una gran cantidad de funciones posibles de un tipo dado, a menudo infinitamente muchas. Entonces, si tiene un tipo de registro cuyos campos son funciones, entonces eso puede respaldar fácilmente un conjunto de alternativas astronómicamente grande o infinito. Y lo que es más, dado que los registros se crean en tiempo de ejecución y se pueden realizar de forma flexible en función de las condiciones de tiempo de ejecución, las alternativas se envían tarde .
El último comentario que haré es que, en mi opinión, OO ha hecho creer a muchas personas que la extensibilidad es sinónimo de vinculación tardía (por ejemplo, la posibilidad de agregar nuevas subcategorías a un tipo en tiempo de ejecución), cuando esto simplemente no es generalmente verdad. La unión tardía es una técnica para la extensibilidad. Otra técnica es la composición: construir objetos complejos a partir de un vocabulario fijo de bloques de construcción y reglas para ensamblarlos. El vocabulario y las reglas son idealmente pequeños, pero diseñados para que tengan interacciones ricas que te permitan construir cosas muy complejas.
La programación funcional -y los sabores estáticos ML / Haskell en particular- han enfatizado durante mucho tiempo la composición sobre la unión tardía. Pero en realidad, ambos tipos de técnicas existen en ambos paradigmas, y deberían estar en el juego de herramientas de un buen programador.
También vale la pena señalar que los lenguajes de programación en sí mismos son fundamentalmente ejemplos de composición. Un lenguaje de programación tiene una sintaxis finita, con suerte simple, que le permite combinar sus elementos para escribir cualquier programa posible. (De hecho, esto se remonta al ejemplo anterior de Compiladores / Patrón de visitante y lo motiva).
De acuerdo, con "abrir" aquí quieres decir "se puede derivar de" y no abrir en el sentido de Ruby y Smalltalk, donde puedes extender una clase con nuevos métodos en tiempo de ejecución, ¿verdad?
En cualquier caso, tenga en cuenta dos cosas: en primer lugar, en la mayoría de los lenguajes de OO que se basan principalmente en la herencia, hay una forma de declarar una clase para restringir su capacidad de heredarse. Java tiene "final", y hay hacks para esto en C ++. Entonces, con eso, solo está haciendo una opción por defecto en otros lenguajes OO.
En segundo lugar, puede crear un tipo nuevo que use el ADT cerrado y agregue otros métodos o implementaciones diferentes. Entonces no estás realmente restringido de esa manera. Nuevamente, parecen tener formalmente la misma fuerza; lo que puedes expresar en uno puede expresarse en el otro.
Lo real es que la programación funcional realmente es un paradigma diferente ("patrón"). Si lo hace con la expectativa de que debería ser como un lenguaje OO, se sorprenderá con regularidad.
El hecho de que ADT esté cerrado hace que sea mucho más fácil escribir funciones totales. Estas son funciones que siempre producen un resultado, para todos los valores posibles de su tipo, ej.
maybeToList :: Maybe a -> [a]
maybeToList Nothing = []
maybeToList (Just x) = [x]
Si Maybe estuviera abierto, alguien podría agregar un constructor adicional y la función maybeToList se rompería de repente.
En OO esto no es un problema, cuando se usa la herencia para extender un tipo, porque cuando se llama a una función para la cual no existe una sobrecarga específica, solo puede usar la implementación para una superclase. Es decir, puede llamar a printPerson(Person p) con un objeto de Student si el Student es una subclase de Person .
En Haskell, normalmente usaría encapsulación y clases de tipos cuando necesita extender sus tipos. Por ejemplo:
class Eq a where
(==) :: a -> a -> Bool
instance Eq Bool where
False == False = True
False == True = False
True == False = False
True == True = True
instance Eq a => Eq [a] where
[] == [] = True
(x:xs) == (y:ys) = x == y && xs == ys
_ == _ = False
Ahora, la función == está completamente abierta, puede agregar sus propios tipos haciéndolo una instancia de la clase Eq .
Tenga en cuenta que se ha trabajado en la idea de los tipos de datos extensibles , pero definitivamente aún no es parte de Haskell.
La respuesta tiene que ver con la forma en que el código es fácil de extender, una tensión entre clases y tipos de datos algebraicos que Phil Wadler apodó "el problema de la expresión":
Con tipos de datos algebraicos,
Es muy barato agregar una nueva operación en las cosas : simplemente define una nueva función. Todas las funciones anteriores en esas cosas continúan sin cambios.
Es muy costoso agregar un nuevo tipo de cosas : debe agregar un nuevo constructor a un tipo de datos existente, y debe editar y recompilar cada función que use ese tipo .
Con clases,
Es muy barato agregar un nuevo tipo de cosa : simplemente agregue una nueva subclase, y según sea necesario, defina métodos especializados, en esa clase, para todas las operaciones existentes. La superclase y todas las demás subclases continúan sin cambios.
Es muy costoso agregar una nueva operación en cosas : debe agregar una nueva declaración de método a la superclase y potencialmente agregar una definición de método a cada subclase existente . En la práctica, la carga varía según el método.
Por lo tanto, los tipos de datos algebraicos se cierran porque un tipo cerrado admite bien ciertos tipos de evolución del programa. Por ejemplo, si sus tipos de datos definen un idioma, es fácil agregar nuevos pasos de compilación sin invalidar los antiguos o cambiar los datos.
Es posible tener tipos de datos "abiertos", pero excepto bajo circunstancias cuidadosamente controladas, la verificación de tipos se vuelve difícil. Todd Millstein hizo un trabajo muy hermoso en un diseño de lenguaje que admite tipos algebraicos abiertos y funciones extensibles, todo con un comprobador de tipos modular. Su lectura me pareció un gran placer de leer.
Marque "Abrir tipos de datos y abrir funciones" http://lambda-the-ultimate.org/node/1453
En los lenguajes orientados a objetos, es fácil ampliar los datos definiendo nuevas clases, pero es difícil agregar nuevas funciones. En los lenguajes funcionales, la situación se invierte: agregar funciones nuevas no plantea problemas, pero ampliar los datos (agregar nuevos constructores de datos) requiere modificar el código existente . El problema de apoyar ambas direcciones de extensibilidad se conoce como el problema de expresión . Presentamos tipos de datos abiertos y funciones abiertas como una solución ligera para el problema de expresión en el lenguaje Haskell. La idea es que los constructores de tipos de datos abiertos y las ecuaciones de funciones abiertas puedan aparecer dispersos por un programa. En particular, pueden residir en diferentes módulos. La semántica prevista es la siguiente: el programa debe comportarse como si los tipos de datos y las funciones estuvieran cerradas, definidas en un solo lugar. El orden de las ecuaciones de funciones se determina mediante la coincidencia de patrones de mejor ajuste, donde un patrón específico tiene prioridad sobre uno inespecífico. Mostramos que nuestra solución es aplicable al problema de expresión, programación genérica y excepciones. Dibujamos dos implementaciones. Una simple, derivada de la semántica, y una basada en módulos mutuamente recursivos que permite la compilación por separado.
Otra forma (más o menos) intuitiva de ver los tipos de datos y las clases de tipos frente a las clases orientadas a objetos es la siguiente:
Un Foo de clase en un lenguaje OO representa tanto un Foo de tipo concreto como la clase de todos los tipos Foo : aquellos que derivan directa o indirectamente de Foo .
En los lenguajes OO, sucede que programa implícitamente contra la clase de los tipos Foo que le permite "extender" Foo .
Primero, como contrapunto a la respuesta de Charlie, esto no es intrínseco a la programación funcional. OCaml tiene el concepto de uniones abiertas o variantes polimórficas , que esencialmente hacen lo que quieres.
En cuanto a por qué , creo que esta elección fue hecha por Haskell porque
- esto permite que los tipos sean predecibles; solo hay un número finito de constructores para cada uno
- es fácil definir sus propios tipos.
- muchas funciones de Haskell son polimórficas, y las clases le permiten extender tipos personalizados para ajustarse a los parámetros de la función (piense en las interfaces de Java).
Entonces, si prefiere tener un data Color rbg = Red r | Blue b | Green g data Color rbg = Red r | Blue b | Green g Tipo de data Color rbg = Red r | Blue b | Green g , es fácil de hacer, y puedes hacer que actúe fácilmente como una mónada o un funtor o como lo necesiten otras funciones.
Si escribes una función como
maybeToList Nothing = []
maybeToList (Just x) = [x]
entonces sabes que nunca va a producir un error de tiempo de ejecución porque cubriste todos los casos. Esto deja de ser cierto tan pronto como el tipo Maybe sea extensible. En los casos en que necesite un tipo extensible (y son más raros de lo que cree), la solución canónica de Haskell es usar una clase de tipo.