Teoría de lenguajes de programación

La teoría de lenguajes 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 . La teoría de lenguajes de programación está estrechamente relacionada con otros campos, como las matemáticas , la ingeniería de software y la lingüística . Hay una serie de conferencias y revistas académicas en el área.

En cierto modo, 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 estaba destinado a modelar la computación en lugar de ser un medio para que los programadores describieran algoritmos para un sistema informático. Muchos lenguajes de programación funcional modernos han sido descritos como si proporcionaran una "capa fina" sobre el cálculo lambda, ^[2] y muchos se describen fácilmente en términos de él.

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 entre 1954 y 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 otra parte, John McCarthy del MIT desarrolló Lisp , el primer lenguaje con orígenes en el ámbito 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:

Década de 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.

Década de 1960

• En 1962, Ole-Johan Dahl y Kristen Nygaard desarrollaron el lenguaje Simula ; se considera ampliamente 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 puede utilizarse para modelar lenguajes de programación. Presenta la máquina SECD , que "interpreta" expresiones lambda.
• En 1965, Landin introduce el operador J , esencialmente una forma de continuación .
• En 1966, Landin presenta ISWIM , un lenguaje de programación de computadoras 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). ^[3]
• En 1967, Christopher Strachey publica su influyente conjunto de notas de clase Conceptos fundamentales en lenguajes de programación , introduciendo la terminología valores R , valores L , polimorfismo paramétrico y polimorfismo ad hoc .
• En 1969, J. Roger Hindley publica El esquema de tipos principal de un objeto en lógica combinatoria , posteriormente generalizado como el algoritmo de inferencia de tipos Hindley-Milner .
• En 1969, Tony Hoare introduce la lógica Hoare , una forma de semántica axiomática .
• En 1969, William Alvin Howard observó que un sistema de demostración de "alto nivel" , conocido como deducción natural , puede interpretarse directamente en su versión intuicionista como una variante tipificada del modelo de computación conocido como cálculo lambda . Esto se conoció como la correspondencia Curry-Howard .

Década de 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 innovador entorno de desarrollo.
• En 1974, John C. Reynolds descubre el Sistema F. Éste 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 alcance léxico , un espacio de nombres unificado y elementos del modelo de actor , incluidas 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 ahora conocidos como lenguajes de programación a nivel de función .
• En 1977, Gordon Plotkin introduce Programming Computable Functions , un lenguaje funcional de tipado abstracto.
• En 1978, Robin Milner presenta el algoritmo de inferencia de tipos Hindley-Milner para ML . La teoría de tipos se aplicó como disciplina a los lenguajes de programación y esta aplicación ha llevado a enormes avances en la teoría de tipos a lo largo de los años.

Década de 1980

• En 1981, Gordon Plotkin publica su artículo sobre semántica operacional 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 actores de Carl Hewitt .
• En 1985, el lanzamiento de Miranda despertó un interés académico en los lenguajes de programación funcional puros evaluados de forma diferida. Se formó un comité para definir un estándar abierto, lo que dio como resultado el lanzamiento del estándar Haskell 1.0 en 1990.
• Bertrand Meyer creó la metodología Diseño por contrato y la incorporó al lenguaje de programación Eiffel .

Década de 1990

• Gregor Kiczales , Jim Des Rivieres y Daniel G. Bobrow publicaron el libro El arte del protocolo metaobject .
• Eugenio Moggi y Philip Wadler introdujeron el uso de mónadas para estructurar programas escritos en lenguajes de programación funcional .

Existen varios campos de estudio que se encuentran dentro de la teoría de los lenguajes de programación o que tienen una profunda influencia en ella; muchos de ellos tienen una superposición considerable. Además, PLT hace uso de muchas otras ramas de las matemáticas , incluidas la teoría de la computabilidad , la teoría de categorías y la teoría de conjuntos .

La semántica formal es la especificación formal del comportamiento de los programas informáticos y los lenguajes de programación. Tres enfoques comunes para describir la semántica o el "significado" de un programa informático son la semántica denotacional , la semántica operacional y la semántica axiomática .

La teoría de tipos es el estudio de los sistemas de tipos , que son "un método sintáctico manejable para demostrar la ausencia de ciertos comportamientos del programa clasificando frases según los tipos de valores que calculan". ^[4] Muchos lenguajes de programación se distinguen por las características de sus sistemas de tipos.

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 forma.

El análisis comparativo de lenguajes de programación busca clasificar los lenguajes de programación en diferentes tipos según sus características; las categorías amplias de lenguajes de programación a menudo se conocen como paradigmas de programación .

La metaprogramación es la generación de programas de orden superior que, cuando se ejecutan, producen programas (posiblemente en un lenguaje diferente o en un subconjunto del lenguaje original) como resultado.

Los lenguajes específicos de dominio son lenguajes construidos para resolver eficientemente problemas de una parte particular del dominio.

La teoría de compiladores es la teoría de la escritura de compiladores (o, de manera más general, traductores ); programas que traducen un programa escrito en un lenguaje a otro formato. Las acciones de un compilador se dividen tradicionalmente en análisis sintáctico ( escaneo y análisis sintáctico ), análisis semántico (determinación de lo que debería hacer un programa), optimización (mejora del rendimiento de un programa según lo indicado por alguna métrica; típicamente la velocidad de ejecución) y generación de código (generación y salida de un programa equivalente en algún lenguaje de destino; a menudo el conjunto de instrucciones de una CPU).

Los sistemas de tiempo de ejecución se refieren al desarrollo de entornos de ejecución de lenguajes de programación y sus componentes, incluidas máquinas virtuales , recolección de basura e interfaces de funciones externas .

Los congresos son el principal foro para presentar investigaciones sobre lenguajes de programación. Entre los congresos más conocidos se encuentran el Simposio sobre Principios de Lenguajes de Programación (POPL), el 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 la Conferencia Internacional sobre Soporte Arquitectónico para Lenguajes de Programación y Sistemas Operativos (ASPLOS) .

Entre las revistas destacadas que publican investigaciones sobre PLT se incluyen ACM Transactions on Programming Languages ​​and Systems (TOPLAS), Journal of Functional Programming (JFP), Journal of Functional and Logic Programming y Higher-Order and Symbolic Computation .

• PLAN DE SEGURIDAD
• Lenguaje de programación de muy alto nivel

• Abadi, Martín y Cardelli, Luca . Una teoría de 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 . MIT Press.
• Harper, Robert . Fundamentos prácticos para lenguajes de programación . Versión borrador.
• 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). Lenguajes tipo Algol . Progreso en la ciencia informática teórica. Birkhauser, Boston.
• Pierce, Benjamin C. (2002). Tipos y lenguajes de programación . MIT Press.
• Pierce, Benjamin C. Temas avanzados en tipos y lenguajes de programación .
• Pierce, Benjamin C. et al. (2010). Fundamentos del software .

• Lambda the Ultimate, un blog comunitario para debates profesionales y repositorio de documentos sobre teoría de lenguajes de programación.
• Grandes obras sobre lenguajes de programación. Recopilado por Benjamin C. Pierce ( Universidad de Pensilvania ).
• Artículos clásicos sobre lenguajes de programación y lógica. Recopilados por Karl Crary ( Universidad Carnegie Mellon ).
• Investigación sobre lenguajes de programación. Directorio de Mark Leone.
• λ-Calculus: Then & Now por Dana S. Scott para la celebración del centenario de Turing de la ACM
• Grandes desafíos en los lenguajes de programación. Sesión de panel en POPL 2009.