La teoría del lenguaje de programación ( PLT ) es una rama de la informática que se ocupa del diseño, implementación, análisis, caracterización y clasificación de lenguajes formales conocidos como lenguajes de programación y de sus características individuales . Se enmarca dentro de la disciplina de las ciencias de la computación, dependiendo y afectando a las matemáticas , la ingeniería de software , la lingüística e incluso las ciencias cognitivas . Se ha convertido en una rama reconocida de la informática y en un área de investigación activa, con resultados publicados en numerosas revistas. dedicada a PLT, así como en general a publicaciones de informática e ingeniería.
Historia
De alguna manera, la historia de la teoría de los lenguajes de programación es anterior incluso al desarrollo de los propios lenguajes de programación. El cálculo lambda, desarrollado por Alonzo Church y Stephen Cole Kleene en la década de 1930, es considerado por algunos como el primer lenguaje de programación del mundo, a pesar de que tenía la intención de modelar la computación en lugar de ser un medio para que los programadores describieran algoritmos a un sistema informático. . Se ha descrito que muchos lenguajes de programación funcional modernos proporcionan una "fina capa" sobre el cálculo lambda, [1] y muchos se describen fácilmente en términos de este.
El primer lenguaje de programación que se inventó fue Plankalkül , que fue diseñado por Konrad Zuse en la década de 1940, pero no se conoció públicamente hasta 1972 (y no se implementó hasta 1998). El primer lenguaje de programación de alto nivel ampliamente conocido y exitoso fue Fortran , desarrollado de 1954 a 1957 por un equipo de investigadores de IBM dirigido por John Backus . El éxito de FORTRAN llevó a la formación de un comité de científicos para desarrollar un lenguaje informático "universal"; el resultado de su esfuerzo fue ALGOL 58 . Por separado, John McCarthy del MIT desarrolló Lisp (basado en el cálculo lambda), el primer idioma con orígenes en el mundo académico que tuvo éxito. Con el éxito de estos esfuerzos iniciales, los lenguajes de programación se convirtieron en un tema activo de investigación en la década de 1960 y más allá.
Algunos otros eventos clave en la historia de la teoría del lenguaje de programación desde entonces:
1950
- Noam Chomsky desarrolló la jerarquía de Chomsky en el campo de la lingüística, un descubrimiento que ha impactado directamente en la teoría del lenguaje de programación y otras ramas de la informática.
1960
- El lenguaje Simula fue desarrollado por Ole-Johan Dahl y Kristen Nygaard ; es ampliamente considerado como el primer ejemplo de un lenguaje de programación orientado a objetos ; Simula también introdujo el concepto de corrutinas .
- En 1964, Peter Landin es el primero en darse cuenta de que el cálculo lambda de Church se puede utilizar para modelar lenguajes de programación. Introduce la máquina SECD que "interpreta" expresiones lambda.
- En 1965, Landin presenta el operador J , esencialmente una forma de continuación .
- En 1966, Landin presenta ISWIM , un lenguaje de programación de computadora abstracto en su artículo The Next 700 Programming Languages . Es influyente en el diseño de lenguajes que conducen al lenguaje de programación Haskell .
- En 1966, Corrado Böhm introdujo el lenguaje de programación CUCH (Curry-Church). [2]
- En 1967, Christopher Strachey publica su conjunto influyente de conferencia toma nota de conceptos fundamentales de Lenguajes de Programación , la introducción de la terminología valores R , valores L , polimorfismo paramétrico , y polimorfismo ad hoc .
- En 1969, J. Roger Hindley publica The Principal Type-Scheme of an Object in Combinatory Logic , más tarde generalizado en el algoritmo de inferencia de tipo Hindley-Milner .
- En 1969, Tony Hoare introduce la lógica de Hoare , una forma de semántica axiomática .
- En 1969, William Alvin Howard observó que un sistema de prueba de "alto nivel" , denominado deducción natural , puede interpretarse directamente en su versión intuicionista como una variante tipificada del modelo de cálculo conocido como cálculo lambda . Esto se conoció como correspondencia Curry-Howard .
1970
- En 1970, Dana Scott publica por primera vez su trabajo sobre semántica denotacional .
- En 1972, se desarrollaron la programación lógica y Prolog , lo que permitió que los programas de computadora se expresaran como lógica matemática.
- Un equipo de científicos de Xerox PARC dirigido por Alan Kay desarrolla Smalltalk , un lenguaje orientado a objetos ampliamente conocido por su entorno de desarrollo innovador.
- En 1974, John C. Reynolds descubre System F . Ya había sido descubierto en 1971 por el lógico matemático Jean-Yves Girard .
- A partir de 1975, Gerald Jay Sussman y Guy Steele desarrollan el lenguaje de programación Scheme , un dialecto Lisp que incorpora el alcance léxico , un espacio de nombres unificado y elementos del modelo de actor que incluyen continuaciones de primera clase .
- Backus, en la conferencia del Premio Turing de 1977 , atacó el estado actual de los lenguajes industriales y propuso una nueva clase de lenguajes de programación que ahora se conocen como lenguajes de programación a nivel de función .
- En 1977, Gordon Plotkin introduce Programming Computable Functions , un lenguaje funcional de tipo abstracto.
- En 1978, Robin Milner introduce el algoritmo de inferencia de tipo Hindley-Milner para ML . La teoría de tipos se aplicó como una disciplina a los lenguajes de programación, esta aplicación ha dado lugar a enormes avances en la teoría de tipos a lo largo de los años.
Decenio de 1980
- En 1981, Gordon Plotkin publica su artículo sobre semántica operativa estructurada .
- En 1988, Gilles Kahn publicó su artículo sobre semántica natural .
- Surgieron cálculos de procesos , como el cálculo de sistemas de comunicación de Robin Milner , y el modelo de procesos secuenciales de comunicación de CAR Hoare , así como modelos similares de concurrencia como el modelo de actor de Carl Hewitt .
- En 1985, el lanzamiento de Miranda despierta un interés académico en los lenguajes de programación funcionales puros evaluados de forma perezosa. Se formó un comité para definir un estándar abierto que resultó en el lanzamiento del estándar Haskell 1.0 en 1990.
- Bertrand Meyer creó la metodología Design by contract y la incorporó al lenguaje de programación Eiffel .
Decenio de 1990
- Gregor Kiczales , Jim Des Rivieres y Daniel G. Bobrow publicaron el libro The Art of the Metaobject Protocol .
- Eugenio Moggi y Philip Wadler introdujeron el uso de mónadas para estructurar programas escritos en lenguajes de programación funcionales .
Hay varios campos de estudio que se encuentran dentro de la teoría del lenguaje de programación o que tienen una profunda influencia en ella; muchos de estos tienen una superposición considerable. Además, PLT hace uso de muchas otras ramas de las matemáticas , incluida la teoría de la computabilidad , la teoría de categorías y la teoría de conjuntos .
Semántica formal
La semántica formal es la especificación formal del comportamiento de los programas de computadora y los lenguajes de programación. Tres enfoques comunes para describir la semántica o el "significado" de un programa de computadora son la semántica denotacional , la semántica operacional y la semántica axiomática .
Teoría de tipos
La teoría de tipos es el estudio de sistemas de tipos ; que son "un método sintáctico manejable para probar la ausencia de ciertos comportamientos del programa mediante la clasificación de frases de acuerdo con los tipos de valores que calculan". [3] Muchos lenguajes de programación se distinguen por las características de sus sistemas de tipos.
Análisis y transformación de programas
El análisis de programas es el problema general de examinar un programa y determinar las características clave (como la ausencia de clases de errores de programa ). La transformación de programas es el proceso de transformar un programa de una forma (lenguaje) a otra.
Análisis comparativo de lenguajes de programación
El análisis comparativo de lenguajes de programación busca clasificar los lenguajes de programación en diferentes tipos en función de sus características; Las categorías amplias de lenguajes de programación se conocen a menudo como paradigmas de programación .
Genérico y metaprogramación
La metaprogramación es la generación de programas de orden superior que, cuando se ejecutan, producen programas (posiblemente en un idioma diferente o en un subconjunto del idioma original) como resultado.
Idiomas específicos del dominio
Los lenguajes específicos de dominio son lenguajes construidos para resolver de manera eficiente problemas de una parte particular del dominio.
Construcción del compilador
La teoría del compilador es la teoría de la escritura de compiladores (o más generalmente, traductores ); programas que traducen un programa escrito en un idioma a otro formato. Las acciones de un compilador se dividen tradicionalmente en análisis de sintaxis ( escaneo y análisis sintáctico ), análisis semántico (determinar qué debe hacer un programa), optimización (mejorar el rendimiento de un programa según lo indicado por alguna métrica; típicamente velocidad de ejecución) y generación de código. (generación y salida de un programa equivalente en algún idioma de destino; a menudo el conjunto de instrucciones de una CPU).
Sistemas en tiempo de ejecución
Los sistemas de tiempo de ejecución se refieren al desarrollo de entornos de tiempo de ejecución de lenguaje de programación y sus componentes, incluidas las máquinas virtuales , la recolección de basura y las interfaces de funciones externas .
Revistas, publicaciones y conferencias
Las conferencias son el lugar principal para presentar investigaciones en lenguajes de programación. Las conferencias más conocidas incluyen el Simposio sobre principios de lenguajes de programación (POPL), Diseño e implementación de lenguajes de programación (PLDI), la Conferencia internacional sobre programación funcional (ICFP), la Conferencia internacional sobre programación orientada a objetos, sistemas, lenguajes y aplicaciones ( OOPSLA) y el Congreso Internacional de Soporte Arquitectónico para Lenguajes de Programación y Sistemas Operativos (ASPLOS) .
Revistas notables que publican la investigación PLT incluyen las transacciones de ACM en lenguajes de programación y sistemas (TOPLAS), Diario de programación funcional (JFP), Diario de la programación lógica y funcional , y de orden superior y Computación Simbólica .
Ver también
- SIGPLAN
- Cronología de los lenguajes de programación
- Lenguaje de programación de muy alto nivel
Referencias
- ^ http://www.c2.com/cgi/wiki?ModelsOfComputation
- ^ C. Böhm y W. Gross (1996). Introducción al CUCH. En ER Caianiello (ed.), Automata Theory , p. 35-64 /
- ^ Benjamin C. Pierce. 2002. Tipos y lenguajes de programación . MIT Press, Cambridge, Massachusetts, Estados Unidos.
Otras lecturas
- Abadi, Martín y Cardelli, Luca . Una teoría de los objetos . Springer-Verlag.
- Michael JC Gordon . Teoría del lenguaje de programación y su implementación . Prentice Hall.
- Gunter, Carl y Mitchell, John C. (eds.). Aspectos teóricos de los lenguajes de programación orientados a objetos: tipos, semántica y diseño de lenguajes . Prensa del MIT.
- Harper, Robert . Fundamentos prácticos de lenguajes de programación . Versión preliminar.
- Knuth, Donald E. (2003). Artículos seleccionados sobre lenguajes informáticos . Stanford, California: Centro para el estudio del lenguaje y la información.
- Mitchell, John C .. Fundamentos de los lenguajes de programación .
- Mitchell, John C .. Introducción a la teoría del lenguaje de programación .
- O'Hearn, Peter. W. y Tennent, Robert. D. (1997). Idiomas tipo Algol . Progreso en Informática Teórica. Birkhauser, Boston.
- Pierce, Benjamin C. (2002). Tipos y lenguajes de programación . Prensa del MIT.
- Pierce, Benjamin C. Temas avanzados en tipos y lenguajes de programación .
- Pierce, Benjamin C. y col. (2010). Fundamentos de software .
enlaces externos
- Lambda the Ultimate , un weblog comunitario para discusión profesional y repositorio de documentos sobre teoría de lenguajes de programación.
- Grandes trabajos en lenguajes de programación . Recopilado por Benjamin C. Pierce ( Universidad de Pennsylvania ).
- Artículos clásicos en lenguajes de programación y lógica . Recopilado por Karl Crary ( Universidad Carnegie Mellon ).
- Investigación en lenguajes de programación . Directorio de Mark Leone .
- Programación de textos de teoría del lenguaje en línea . En la Universidad de Utrecht .
- λ-Calculus: Then & Now de Dana S. Scott para la celebración del centenario de ACM Turing
- Grandes desafíos en lenguajes de programación . Sesión de panel en POPL 2009.