oop - programacion - que es poo
¿Hay algún modelo matemático o teoría detrás de los lenguajes de programación? (11)
¿Tenemos [un modelo subyacente] para lenguajes de programación?
Cielos, sí. Y como hay tantos lenguajes de programación, hay múltiples modelos para elegir. Lo más importante primero:
El cálculo lambda no tipificado de Church es un modelo de cálculo que es tan poderoso como una máquina de Turing (ni más ni menos). La famosa "hipótesis de Church-Turing" es que estos dos modelos equivalentes representan el modelo de computación más general que sabemos cómo implementar. El cálculo lambda es extremadamente simple; en su totalidad el lenguaje es
e ::= x | e1 e2 | /x.eque constituyen variables , aplicaciones de función y definiciones de función . El cálculo lambda también viene con una colección bastante grande de "reglas de reducción" para simplificar expresiones. Si encuentra una expresión que no se puede reducir, se denomina "forma normal" y representa un valor.
El cálculo lambda es tan general que puede tomarlo en varias direcciones.
Si desea utilizar todas las reglas disponibles, puede escribir herramientas especializadas como evaluadores parciales y partes de compiladores.
Si evita reducir cualquier subexpresión bajo un lambda, pero de lo contrario usa todas las reglas disponibles, terminará con un modelo de lenguaje funcional perezoso como Haskell o Clean. En este modelo, si una reducción puede terminar, está garantizado, y es fácil representar estructuras de datos infinitas. Muy poderoso.
Si evita reducir cualquier subexpresión bajo un lambda, y también insiste en reducir cada argumento a una forma normal antes de aplicar una función, entonces tiene un modelo de un lenguaje funcional ávido como F #, Lisp, Objective Caml, Scheme, o Estándar ML.
También hay varios sabores de cálculos lambda mecanografiados , de los cuales los más famosos se agrupan bajo el nombre Sistema F , que fueron descubiertos independientemente por Girard (en lógica) y por Reynolds (en informática). System F es un excelente modelo para lenguajes como CLU, Haskell y ML, que son polimórficos pero tienen verificación de tipos en tiempo de compilación. Hindley (en lógica) y Milner (en ciencias de la computación) descubrieron una forma restringida del Sistema F (ahora llamado sistema de tipo Hindley-Milner) que permite inferir expresiones del Sistema F a partir de algunas expresiones del cálculo lambda sin tipo . Damas y Milner desarrollaron un algoritmo para hacer esta inferencia, que se utiliza en Standard ML y se ha generalizado en otros idiomas.
El cálculo lambda solo está empujando símbolos alrededor. El trabajo pionero de Dana Scott en semántica denotacional mostró que las expresiones en el cálculo lambda en realidad corresponden a funciones matemáticas, y él identificó cuáles. El trabajo de Scott es especialmente importante para dar sentido a las "definiciones recursivas", que son comunes en la informática, pero no tienen sentido desde el punto de vista matemático. Scott y Christopher Strachey demostraron que una definición recursiva es equivalente a la solución menos definida para una ecuación de recursión, y además mostraron cómo se podría construir esa solución. Cualquier lenguaje que permita la recursión, y especialmente los idiomas que permiten la recursión en un tipo arbitrario (como Haskell y Clean) debe algo al modelo de Scott.
Existe toda una familia de modelos basados en máquinas abstractas . Aquí no hay tanto un modelo individual como una técnica. Puede definir un idioma utilizando una máquina de estados y definiendo transiciones en la máquina. Esta definición abarca todo, desde máquinas de Turing hasta máquinas de Von Neumann y sistemas de reescritura de términos, pero en general la máquina abstracta está diseñada para estar "lo más cerca posible del lenguaje". El diseño de tales máquinas, y el negocio de probar teoremas sobre ellas, están bajo el título de semántica operacional .
¿Qué pasa con la programación orientada a objetos?
No estoy tan bien educado como debería ser sobre modelos abstractos utilizados para la POO. Los modelos con los que estoy más familiarizado están muy relacionados con las estrategias de implementación. Si quisiera investigar más a fondo esta área, comenzaría con la semántica de denotación de William Cook para Smalltalk. (Smalltalk como lenguaje es muy simple, casi tan simple como el cálculo lambda, por lo que es un buen estudio de caso para modelar lenguajes orientados a objetos más complicados).
Wei Hu me recuerda que Martin Abadi y Luca Cardelli han reunido un ambicioso trabajo sobre cálculos fundamentales (análogo al cálculo lambda) para lenguajes orientados a objetos. No entiendo el trabajo lo suficientemente bien como para resumirlo, pero aquí hay un pasaje del Prólogo de su libro, que creo que vale la pena citar:
Los lenguajes de procedimiento son generalmente bien entendidos; sus construcciones son ya estándar, y sus bases formales son sólidas. Las características fundamentales de estos lenguajes se han convertido en formalismos que resultan útiles para identificar y explicar problemas de implementación, análisis estático, semántica y verificación.
Todavía no ha surgido una comprensión análoga para los lenguajes orientados a objetos. No existe un acuerdo generalizado sobre una colección de construcciones básicas y sobre sus propiedades ... Esta situación podría mejorar si tuviéramos una mejor comprensión de los fundamentos de los lenguajes orientados a objetos.
... tomamos los objetos como primitivos y nos concentramos en las reglas intrínsecas que los objetos deben obedecer. Introducimos los cálculos de objetos y desarrollamos una teoría de los objetos a su alrededor. Estos cálculos de objetos son tan simples como los cálculos de funciones, pero representan objetos directamente.
Espero que esta cita le dé una idea del sabor del trabajo.
RDBMS se basa en el álgebra relacional y en el modelo de Codd. ¿Tenemos algo similar a eso para lenguajes de programación u OOP?
Como sé, las gramáticas formales se utilizan para la descripción de la sintaxis.
Hay muchas dimensiones para abordar su pregunta, dispersándose en las respuestas.
En primer lugar, para describir la sintaxis de un lenguaje y especificar cómo funcionaría un analizador, usamos gramáticas sin contexto.
Entonces necesitas asignar significados a la sintaxis. La semántica formal es útil; Los principales actores son la semántica operacional, la semántica denotacional y la semántica axiomática.
Para descartar malos programas tienes el sistema de tipos.
Al final, todos los programas informáticos pueden reducirse a (o compilarse, si se quiere) modelos de computación muy simples. Los programas imperativos se asignan más fácilmente a las máquinas de Turing, y los programas funcionales se asignan al cálculo lambda.
Si está aprendiendo todas estas cosas por su cuenta, le recomiendo http://www.uni-koblenz.de/~laemmel/paradigms0910/ , porque las conferencias se graban en video y se ponen en línea.
La analogía más cercana que puedo pensar es en las álgebras evolutivas de Gurevich que, hoy en día, son más conocidas con el nombre de "Máquinas de estado abstracto de Gurevich" (GASM).
Durante mucho tiempo he esperado ver más aplicaciones reales de la teoría cuando Gurevich se uniera a Microsoft, pero parece que muy pocas están saliendo. Puede consultar la página ASML en el sitio de Microsoft.
El punto positivo sobre GASM es que se parecen mucho a un pseudocódigo incluso si su semántica se especifica formalmente. Esto significa que los practicantes pueden comprenderlos fácilmente.
Después de todo, creo que parte del éxito del Álgebra Relacional es que es la base formal de los conceptos que se pueden comprender fácilmente, a saber, tablas, claves externas, combinaciones, etc.
Creo que necesitamos algo similar para los componentes dinámicos de un sistema de software.
Lisp se basa en Lambda Calculus y es la inspiración de gran parte de lo que vemos en los idiomas modernos de hoy.
Las máquinas de Von-Neumann son la base de las computadoras modernas, que se programaron por primera vez en lenguaje ensamblador, luego en FORmula TRANslator. Luego se aplicó la teoría lingüística formal de las gramáticas libres de contexto, que subyace a la sintaxis de todas las lenguas modernas.
La teoría de la computabilidad (autómata formal) tiene una jerarquía de tipos de máquina que se asemeja a la jerarquía de las gramáticas formales, por ejemplo, regular-grammar = finite-state-machine, context-free-grammar = pushdown-autómata, context-sensible-grammar = máquina de Turing.
También existe la teoría de la información, de dos tipos, Shannon y Kolmogorov, que puede aplicarse a la computación.
Existen modelos de computación menos conocidos, como la teoría de la función recursiva, las máquinas de registro y las máquinas posteriores.
Y no olvide la lógica predicada en sus diversas formas.
Agregado: olvidé mencionar la matemática discreta, la teoría de grupos y la teoría de celosías. Las celosías en particular son (IMHO) un concepto particularmente ingenioso que subyace a toda lógica booleana, y algunos modelos de computación, como la semántica de la denotación.
Los lenguajes funcionales como lisp heredan sus conceptos básicos de los "lambda calculs" de Church (artículo de wikipedia here ). Saludos
No hay un modelo matemático para la POO.
Álgebra relacional en el modelo matemático para SQL. Fue creado bt EF Codd. CJ Date también fue un reconocido científico que ayudó con esta teoría. La idea general es que puede hacer cada operación como una operación de conjunto, afectando a muchos valores al mismo tiempo. Por supuesto, esto significa que hay que decirle al motor de la base de datos QUÉ debe salir, y la base de datos puede optimizar su consulta.
Tanto Codd como Date criticaron a SQL porque estaban involucrados en la teoría, pero no estaban involucrados en la creación de SQL.
Vea este video: http://player.oreilly.com/videos/9781491908853?toc_id=182164
Hay mucha información de Chris Date. Recuerdo que Date criticó el lenguaje de programación SQL como un lenguaje terrible, pero no puedo encontrar el documento.
La crítica fue básicamente que la mayoría de los lenguajes permiten escribir expresiones y asignar variables a esas expresiones, pero SQL no.
Ya que SQL es un tipo de lenguaje lógico, creo que podrías escribir álgebra relacional en Prolog. Al menos tendrías un lenguaje real. Para que puedas escribir consultas en Prolog. Y como en Prolog tiene muchos programas para interpretar el lenguaje natural, puede consultar su base de datos en lenguaje natural.
Según el tío Bob, las bases de datos no serán necesarias cuando todos tengan SSD, porque la arquitectura de los SSD significa que el acceso es tan rápido como la memoria RAM. Así podrás tener todos tus objetos en la memoria RAM.
https://www.youtube.com/watch?feature=player_detailpage&v=t86v3N4OshQ#t=3287
El único problema con el abandono de SQL es que terminaría sin un lenguaje de consulta para la base de datos.
Así que sí y no, el álgebra relacional se usó como inspiración para SQL, pero SQL no es realmente una implementación del álgebra relacional.
En el caso del Lisp, las cosas son diferentes. La idea principal era que al implementar la función eval en Lisp, se podía implementar todo el lenguaje. Esa es la primera implementación de Lisp en solo media página de código.
http://www.michaelnielsen.org/ddi/lisp-as-the-maxwells-equations-of-software/
Para reírnos un poco: https://www.youtube.com/watch?v=hzf3hTUKk8U
La importancia de la programación funcional se reduce a las funciones al curry y las llamadas perezosas. Y nunca olvidemos ambientes y cierres. Y reducir el mapa. Todo esto significa que estaremos codificando en lenguajes funcionales en 20 años.
Ahora volviendo a la POO, no hay formalización de la POO.
Curiosamente, el segundo lenguaje OO jamás creado, Smalltalk, solo tiene objetos, no tiene primitivos ni nada de eso. Y el creador, Alan Kay, creó bloques explícitamente para trabajar exactamente como las funciones de Lisp.
Algunas personas afirman que la OOP podría formalizarse utilizando la teoría de categorías, que es una especie de teoría de conjuntos pero con morfismos. Un morfismo es una estructura que preserva el mapa entre objetos. Por lo tanto, en general, podría tener map (f, collection) y recuperar una colección con todos los elementos aplicados.
Estoy bastante seguro de que Lisp tiene eso, pero Lisp también tiene funciones que devuelven un elemento en una colección, que destruye la estructura, por lo que un morfismo es un tipo especial de función y debido a eso, tendría que reducir y limitar las funciones. En Lisp para que todos sean morfismos.
https://www.youtube.com/watch?feature=player_detailpage&v=o6L6XeNdd_k#t=250
El principal problema con esto es que las funciones no existen independientemente de los objetos en OOP, pero sí en la teoría de categorías. Por lo tanto son incompatibles. Podrías desarrollar un nuevo lenguaje en el que expresar la teoría de categorías.
Un lenguaje teórico experimental creado explícitamente para tratar de formalizar la POO es Z. Z se deriva del formalismo de requisitos.
Otro intento es el formalismo de Luca Cardelli:
Java http://lucacardelli.name/Papers/PrimObjImp.pdf Java http://lucacardelli.name/Papers/PrimObj1stOrder.A4.pdf Java http://lucacardelli.name/Papers/PrimObjSemLICS.A4.pdf
No puedo leer y entender esa notación. Parece un ejercicio inútil, ya que por lo que sé, nadie lo ha implementado de la misma manera que se implementó el cálculo de lamba en Lisp.
Se ha mencionado mucho sobre la aplicación de las matemáticas a la teoría computacional y la semántica. Me gusta la mención de la teoría de tipos y me alegro de que alguien haya mencionado la teoría de celosía. Aquí hay algunos más.
Nadie ha mencionado explícitamente la teoría de categorías, que se muestra más en lenguajes funcionales que en otras partes, como a través de los conceptos de mónadas y funtores. Luego está la teoría del modelo y las diversas encarnaciones de la lógica que realmente aparecen en los probadores de teoremas o el lenguaje lógico Prolog. También hay aplicaciones matemáticas a los fundamentos y problemas en lenguajes concurrentes.
Si estudias lenguajes de programación (p. Ej., En una universidad), hay mucha teoría y no un poco de matemáticas involucradas.
Algunos ejemplos son:
- Máquinas de estados finitos
- Lanugages formales (y gramáticas libres de contexto como el BNF se utiliza para describirlos)
- La construcción de tablas parser LRish.
Un concepto puede ser la máquina de Turing .