Hispanopedia Wiki
Articulo de referencia

Problema de expresión

El problema de la expresión es un problema en lenguajes de programación que concierne a la extensibilidad y modularidad de las abstracciones de datos con tipado estático. El obj...

Hispanopedia WikiContenido en espanolLectura gratuita

El problema de la expresión es un problema en lenguajes de programación que concierne a la extensibilidad y modularidad de las abstracciones de datos con tipado estático. El objetivo es definir una abstracción de datos que sea extensible tanto en sus representaciones como en sus comportamientos, donde se puedan agregar nuevas representaciones y nuevos comportamientos a la abstracción de datos sin recompilar el código existente y manteniendo la seguridad de tipos estáticos (por ejemplo, sin conversiones de tipo). El planteamiento del problema expone deficiencias en los paradigmas y lenguajes de programación . Philip Wadler, uno de los coautores de Haskell, fue quien acuñó el término.

Historia

Philip Wadler formuló el desafío y lo denominó "El problema de la expresión" [ 1 ] en respuesta a una discusión con el Equipo de Lenguajes de Programación (PLT) de la Universidad Rice . También citó tres fuentes que definieron el contexto de su desafío:

El problema fue observado por primera vez por John Reynolds en 1975. [ 2 ] Reynolds analizó dos formas de abstracción de datos: los tipos definidos por el usuario, ahora conocidos como tipos de datos abstractos (TDA) (que no deben confundirse con los tipos de datos algebraicos ), y las estructuras de datos procedimentales, que ahora se entienden como una forma primitiva de objetos con un solo método. Argumentó que son complementarios, ya que los tipos definidos por el usuario podrían extenderse con nuevos comportamientos, y las estructuras de datos procedimentales podrían extenderse con nuevas representaciones. También analizó trabajos relacionados que se remontan a 1967. Quince años después, en 1990, William Cook [ 3 ] aplicó la idea de Reynolds en el contexto de los objetos y los tipos de datos abstractos, que habían crecido considerablemente. Cook identificó la matriz de representaciones y comportamientos implícitos en una abstracción de datos, y analizó cómo los TDA se basan en el eje del comportamiento, mientras que los objetos se basan en el eje de la representación. Ofrece un análisis exhaustivo del trabajo sobre tipos de datos abstractos (TDA) y objetos relevantes para el problema. También revisó implementaciones en ambos estilos, analizó la extensibilidad en ambas direcciones e identificó la importancia del tipado estático. Lo más importante es que abordó situaciones en las que existía mayor flexibilidad de la que Reynolds había considerado, incluyendo la internalización y la optimización de métodos.

En ECOOP '98, Shriram Krishnamurthi et al. [ 4 ] presentaron una solución de patrón de diseño al problema de extender simultáneamente un lenguaje de programación orientado a expresiones y su conjunto de herramientas. Lo denominaron el "problema de la expresividad" porque pensaron que los diseñadores de lenguajes de programación podrían usar el problema para demostrar el poder expresivo de sus creaciones. Para PLT, el problema había aparecido en la construcción de DrScheme, ahora DrRacket , y lo resolvieron [ 5 ] mediante un redescubrimiento de mixins . [ 6 ] [ 7 ] Para evitar usar un problema de lenguaje de programación en un artículo sobre lenguajes de programación, Krishnamurthi et al. usaron un antiguo problema de programación geométrica para explicar su solución orientada a patrones. En conversaciones con Felleisen y Krishnamurthi después de la presentación de ECOOP, Wadler entendió la naturaleza centrada en PL del problema y señaló que la solución de Krishnamurthi usó una conversión para eludir el sistema de tipos de Java. La discusión continuó en la lista de correo de tipos, donde Corky Cartwright (Rice) y Kim Bruce (Williams) mostraron cómo los sistemas de tipos para lenguajes orientados a objetos podrían eliminar esta casta. En respuesta, Wadler formuló su ensayo y planteó el desafío: "que un lenguaje pueda resolver el problema de la expresión es un indicador clave de su capacidad de expresión". La etiqueta "problema de la expresión" juega con las palabras "expresión" = "cuánto puede expresar tu lenguaje" y "expresión" = "los términos que intentas representar son expresiones del lenguaje".

Otros codescubrieron variantes del problema de la expresión casi al mismo tiempo que el PLT de la Universidad de Rice, en particular Thomas Kühne [ 8 ] en su disertación, y Smaragdakis y Batory [ 9 ] en un artículo paralelo de ECOOP 98.

Algunos trabajos posteriores utilizaron el problema de la expresión para mostrar el poder de los diseños de lenguajes de programación. [ 10 ] [ 11 ]

El problema de la expresión es también un problema fundamental en el diseño de líneas de productos de software multidimensionales y, en particular, como una aplicación o caso especial de los cubos de programas FOSD .

Soluciones

Existen diversas soluciones al problema de la expresión. Cada solución varía en la cantidad de código que el usuario debe escribir para implementarla y en las características del lenguaje que requiere.

Ejemplo

Descripción del problema

Podemos imaginar que no disponemos del código fuente de la siguiente biblioteca, escrita en C# , que deseamos ampliar:

interfaz IEvalExp{int Eval ();}Clase Lit : IEvalExp{Literatura interna ( int n ){N = n ;}interno int N { obtener ; }público entero Eval (){devolver N ;}}Clase Agregar : IEvalExp{Agregar internamente ( IEvalExp izquierda , IEvalExp derecha ){Izquierda = izquierda ;Derecha = derecha ;}internal IEvalExp Left { obtener ; }interno IEvalExp Derecha { obtener ; }público entero Eval (){devolver Izquierda.Eval ( ) + Derecha.Eval ( ) ;​}}clase estática ExampleOne{static IEvalExp AddOneAndTwo () => new Add ( new Lit ( 1 ), new Lit ( 2 ));static int EvaluateTheSumOfOneAndTwo () => AddOneAndTwo (). Eval ();}

Usando esta biblioteca podemos expresar la expresión aritmética 1 + 2como lo hicimos anteriormente ExampleOne.AddOneAndTwo()y evaluarla llamando a .Eval(). Ahora imaginemos que deseamos extender esta biblioteca; agregar un nuevo tipo es fácil porque estamos trabajando con un lenguaje de programación orientado a objetos . Por ejemplo, podríamos crear la siguiente clase:

clase Mult : IEvalExp{Multiplicador interno ( IEvalExp izquierda , IEvalExp derecha ){Izquierda = izquierda ;Derecha = derecha ;}internal IEvalExp Left { obtener ; }interno IEvalExp Derecha { obtener ; }público entero Eval (){devolver Izquierda.Eval ( ) * Derecha.Eval ( ) ;​}}

Sin embargo, si deseamos agregar una nueva función sobre el tipo (un nuevo método en la terminología de C#), por ejemplo, para formatear una expresión, debemos cambiar la IEvalExpinterfaz y luego modificar todas las clases que la implementan. Otra posibilidad es crear una nueva interfaz que extienda la IEvalExpinterfaz y luego crear subtipos para las clases Lit, Addy Mult, pero la expresión devuelta en ExampleOne.AddOneAndTwo()ya ha sido compilada, por lo que no podremos usar la nueva función sobre el tipo anterior. El problema se invierte en lenguajes de programación funcional como F#, donde es fácil agregar una función sobre un tipo dado, pero extender o agregar tipos es difícil.

Solución de problemas mediante álgebra de objetos

Rediseñemos la biblioteca original teniendo en cuenta la extensibilidad, utilizando las ideas del artículo Extensibilidad para las masas. [ 17 ]

Interfaz ExpAlgebra < T >{T Lit ( int n );T Agregar ( T izquierda , T derecha );}clase ExpFactory : ExpAlgebra < IEvalExp >{público IEvalExp Lit ( int n ){devolver nuevo Lit ( n );}public IEvalExp Add ( IEvalExp left , IEvalExp right ){devolver nuevo Agregar ( izquierda , derecha );}}clase estática ExampleTwo < T >{public static T AddOneToTwo ( ExpAlgebra < T > ae ) => ae . Add ( ae . Lit ( 1 ), ae . Lit ( 2 ));}

Usamos la misma implementación que en el primer ejemplo de código, pero ahora agregamos una nueva interfaz que contiene las funciones sobre el tipo, así como una fábrica para el álgebra. Observa que ahora generamos la expresión usando ExampleTwo.AddOneToTwo()la ExpAlgebra<T>interfaz en lugar de directamente desde los tipos. Ahora podemos agregar una función extendiendo la ExpAlgebra<T>interfaz; agregaremos la funcionalidad para imprimir la expresión:

Interfaz IPrintExp : IEvalExp{Imprimir cadena ();}clase PrintableLit : Lit , IPrintExp{interno PrintableLit ( int n ) : base ( n ){N = n ;}interno int N { obtener ; }public string Imprimir (){devolver N.ToString ( ) ;}}clase PrintableAdd : Agregar , IPrintExp{internal PrintableAdd ( IPrintExp left , IPrintExp right ) : base ( left , right ){Izquierda = izquierda ;Derecha = derecha ;}interno nuevo IPrintExp Izquierda { obtener ; }interno nuevo IPrintExp Derecha { obtener ; }public string Imprimir (){return Izquierda.Imprimir () + " + " + Derecha.Imprimir ( ) ;}}clase PrintFactory : ExpFactory , ExpAlgebra < IPrintExp >{público IPrintExp Agregar ( IPrintExp izquierda , IPrintExp derecha ){devolver nuevo PrintableAdd ( izquierda , derecha );}público nuevo IPrintExp Lit ( int n ){devolver nuevo PrintableLit ( n );}}clase estática ExampleThree{interno estático int Evaluate () => ExampleTwo < IPrintExp > . AddOneToTwo ( new PrintFactory ()). Eval ();cadena estática interna Imprimir () => ExampleTwo < IPrintExp > . AddOneToTwo ( new PrintFactory ()). Print ();}

Observe que ExampleThree.Print()estamos imprimiendo una expresión que ya fue compilada en ExampleTwo, no necesitamos modificar ningún código existente. Observe también que esto sigue siendo fuertemente tipado, no necesitamos reflexión ni conversión de tipos. Si reemplazáramos PrintFactory()con ExpFactory()en ExampleThree.Print()obtendríamos un error de compilación ya que el .Print()método no existe en ese contexto.

Véase también

Referencias

  1. ↑ "El problema de la expresión" .
  2. ↑ Reynolds, John C. (1975). "Tipos definidos por el usuario y estructuras de datos procedimentales como enfoques complementarios a la abstracción de datos". Nuevas direcciones en lenguajes algorítmicos (PDF) . Grupo de trabajo 2.1 de IFIP sobre Algol. págs. 157–168 . 
  3. ↑ Cook, William (1990). "Programación orientada a objetos frente a tipos de datos abstractos" . En Bakker, JW de; Roever, WP de; Rozenberg, G. (eds.). Fundamentos de los lenguajes orientados a objetos (FOOL), REX School/Workshop . Lecture Notes in Computer Science. Vol. 489. Noordwijkerhout, Países Bajos: Springer Berlin Heidelberg. pp. 151–178 . doi : 10.1007/BFb0019443 . ISBN   978-3-540-46450-1.
  4. ↑ "Síntesis del diseño orientado a objetos y el diseño funcional para promover la reutilización" .
  5. ↑ Findler, Robert Bruce; Flatt, Matthew (1999). "Programación orientada a objetos modular con unidades y mixins" . ACM SIGPLAN Notices . 34 : 94–104 . doi : 10.1145/291251.289432 .
  6. ↑ Cook, William (1989). Una semántica denotacional de la herencia (PDF) (PhD). Universidad de Brown.
  7. ↑ Flatt, Matthew; Krishnamurthi, Shriram; Felleisen, Matthias (1998). «Clases y Mixins». Actas del 25.º simposio ACM SIGPLAN-SIGACT sobre principios de lenguajes de programación - POPL '98 . págs. 171–183 . doi : 10.1145/268946.268961 . ISBN  978-0897919791. S2CID 5815257 . 
  8. ↑ Kühne, Thomas (1999). Un sistema de patrones funcionales para el diseño orientado a objetos . Darmstadt: Verlag Dr. Kovac. ISBN 978-3-86064-770-7.
  9. ↑ Smaragdakis, Yannis; Don Batory (1998). Implementación de componentes orientados a objetos reutilizables . Lecture Notes in Computer Science. Vol. 1445. 
  10. ↑ Zenger, Matthias; Odersky, Martin (2001). «Tipos de datos algebraicos extensibles con valores predeterminados». Actas de la sexta conferencia internacional ACM SIGPLAN sobre programación funcional . págs. 241–252 . CiteSeerX 10.1.1.28.6778 . doi : 10.1145/507635.507665 . ISBN   1-58113-415-0.
  11. ↑ Zenger, Matthias; Odersky, Martin (2005). "Soluciones extensibles de forma independiente al problema de la expresión" (PDF) . FOOL 2005. ACM. CiteSeerX 10.1.1.107.4449 . 
  12. ↑ Chambers, Craig; Leavens, Gary T. (noviembre de 1995). "Verificación de tipos y módulos para múltiples métodos" . ACM Transactions on Programming Languages ​​and Systems . 17 (6): 805– 843. doi : 10.1145/218570.218571 .
  13. ↑ Clifton, Curtis; Leavens, Gary T.; Chambers, Craig; Millstein, Todd (2000). "MultiJava: Clases abiertas modulares y despacho múltiple simétrico para Java". Actas de la 15.ª conferencia ACM SIGPLAN sobre programación orientada a objetos, sistemas, lenguajes y aplicaciones (PDF) . págs. 130–145 . doi : 10.1145/353171.353181 . ISBN  978-1-58113-200-7. S2CID 7879645 . 
  14. ↑ Wouter Swierstra (2008). "Data Types à La Carte" . Journal of Functional Programming . 18 (4). Cambridge University Press: 423– 436. doi : 10.1017/S0956796808006758 . ISSN 0956-7968 . S2CID 21038598 .  
  15. ↑ Wehr, Stefan; Thiemann, Peter (julio de 2011). "JavaGI: La interacción de las clases de tipos con las interfaces y la herencia" . ACM Transactions on Programming Languages ​​and Systems . 33 (4): 1– 83. doi : 10.1145/1985342.1985343 . S2CID 13174506 . 
  16. ↑ Carette, Jacques; Kiselyov, Oleg; Chung-chieh, Shan (2009). "Finalmente sin etiquetas, parcialmente evaluado: intérpretes por etapas sin etiquetas para lenguajes tipados más simples" (PDF) . J. Funct. Program . 19 (5): 509– 543. doi : 10.1017/S0956796809007205 . S2CID 6054319 . 
  17. 1 2 Oliveira, Bruno C. d. S.; Cook, William R. (2012). "Extensibilidad para las masas: extensibilidad práctica con álgebras de objetos" (PDF) . Ecoop '12 .
  18. ↑ Garrigue, Jacques (2000). "Reutilización de código mediante variantes polimórficas" (PDF) . Taller sobre fundamentos de la ingeniería de software. Sasaguri, Japón, noviembre de 2000. CiteSeerX 10.1.1.128.7169 . 
  • El problema de la expresión, de Philip Wadler .
  • Conferencia: El problema de la expresión, por Ralf Lämmell .
  • Conferencias del Canal 9: Dr. Ralf Lämmel - Programación funcional avanzada - El problema de la expresión en el Canal 9 .
  • Soluciones extensibles de forma independiente al problema de la expresión, Matthias Zenger y Martin Odersky, EPFL Lausana .