La teoría del lenguaje de programación (PLT ) es una sección de las ciencias de la computación dedicada al diseño, análisis, caracterización y clasificación de los lenguajes de programación y al estudio de sus características individuales [1] . Estrechamente relacionado con otras ramas de la informática, los resultados de la teoría se utilizan en matemáticas , en ingeniería de software y en lingüística .
En cierto sentido, la historia de la teoría de los lenguajes de programación es anterior incluso al desarrollo de los propios lenguajes de programación. En particular, el cálculo λ , desarrollado por Alonzo Church y Stephen Kleene en la década de 1930, es en realidad el primer lenguaje de programación, aunque estaba destinado más a cuestiones teóricas de computabilidad que como una herramienta para programadores; muchos lenguajes de programación funcionales modernos son variantes del cálculo λ. La historia posterior de la teoría está estrechamente entrelazada con la historia de los lenguajes de programación , mientras que en el marco de la investigación teórica se crearon nuevos paradigmas , construcciones y métodos, y los resultados de su implementación en lenguajes de programación prácticos proporcionaron retroalimentación para el desarrollo de teoría.
El primer lenguaje de programación que se inventó para su uso en una computadora electrónica existente es Plankalkul de Konrad Zuse , pero no ganó fama entre los contemporáneos (se estudió solo en la década de 1970 y se implementó en la década de 1990). El primer lenguaje de programación ampliamente conocido y exitoso fue Fortran (1954-1957), desarrollado por un equipo de investigadores de IBM dirigido por John Backus . El éxito de Fortran condujo a la formación de un comité de científicos que intentaron desarrollar un lenguaje informático "universal"; el resultado de su esfuerzo fue Algol-58 . Paralelamente , John McCarthy del MIT desarrolló el lenguaje de programación Lisp (basado en cálculo λ), que es el primer lenguaje exitoso con un marco teórico desarrollado académicamente. La década de 1950 incluye el desarrollo de la jerarquía de Chomsky , que influyó directamente en la teoría de los lenguajes de programación.
En 1964, Peter Landin implementó por primera vez una variante del cálculo λ que podría usarse para modelar lenguajes de programación (la máquina SECD y el operador J , esencialmente un tipo de continuación ). En 1966, Landin desarrolló el lenguaje de programación abstracto ISWIM .
En 1966, Corrado Böhm y Giuseppe Jacopini ( el italiano Giuseppe Jackopini ) demostraron un teorema , según el cual un algoritmo se puede convertir a una forma que usa solo tres estructuras de control: secuencial, ramificación y bucle, más tarde este resultado se convirtió en la base teórica de estructurado . programación _ Creado por Ole-Johan Dahl y Kristen Nygor en 1967, el lenguaje Simula desarrolló lo que se cree que es el primer ejemplo de un lenguaje de programación orientado a objetos e introdujo la noción de rutina . Un hito importante en el desarrollo de la dirección fue la cátedra Conceptos Fundamentales en Lenguajes de Programación de Christopher Strachey , estrenada en 1967 , donde, además de sistematizar conocimientos sobre la teoría de los lenguajes de programación, se trató el concepto de polimorfismo . profundamente estudiado . Una contribución significativa al desarrollo del concepto de tipos en los lenguajes de programación está asociada con el trabajo de 1969 de Roger Hindley , cuyos resultados dieron como resultado un algoritmo de inferencia de tipo generalizado .
En 1969, Tony Hoare desarrolló la lógica de Hoare , el primer ejemplo de semántica axiomática para lenguajes de programación que proporciona verificación formal del código del programa. La semántica denotacional fue desarrollada en 1970 por Dana Scott .
En 1972 se creó el paradigma de programación lógica y el lenguaje Prolog , en el que el programa consiste directamente en un conjunto de cláusulas de Horn . Otra área de interés para los teóricos del lenguaje de programación a principios de la década de 1970 fue la introducción de tipos de datos abstractos a nivel de construcciones de lenguaje, con Clu (1974, Barbara Liskov ) considerado como el primer lenguaje de este tipo .
Un hito importante en el camino hacia la formación del paradigma de programación funcional fue el desarrollo independiente por parte de Girard ( fr. Jean-Yves Girard ; 1971) y Reynolds ( ing. John C. Reynolds ; 1974) del sistema F - un tipo λ -cálculo de segundo orden, que proporciona la posibilidad de construir términos que dependen de tipos. Además, los desarrolladores del lenguaje de programación Scheme , un dialecto Lisp que incluía un alcance léxico , un espacio de nombres unificado y elementos del modelo actor , incluidas las continuaciones , hicieron una contribución significativa al desarrollo de la programación funcional a mediados de la década de 1970 . El auge del interés generalizado por la programación funcional está asociado con la conferencia de Turing del creador de Fortran Backus en 1977, en la que analizó críticamente el estado de los lenguajes de programación que eran populares en ese momento y llegaron al paradigma funcional.
En 1980, William Alvin Howard , refiriéndose a los escritos del lógico Haskell Curry en la década de 1950, identificó una correspondencia estructural entre los programas de computadora y las pruebas matemáticas, que se conoció como el isomorfismo de Curry-Howard y se convirtió en la base teórica de la clase de automáticos . lenguajes de prueba .
En la primera mitad de la década de 1980, se prestó una atención considerable a la investigación sobre la implementación del paralelismo en los lenguajes de programación y el desarrollo de variantes del cálculo de procesos : se creó el cálculo de sistemas que interactúan ( Milner , 1980), el lenguaje de los sistemas que interactúan . procesos secuenciales ( Hoare , 1985), finalmente se formó el modelo del actor Hewitt ( ing. ) Carl Hewitt
El lanzamiento del lenguaje Miranda en 1985 alimentó el interés académico en los lenguajes de programación funcionales puros perezosos , lo que resultó en la formación de un comité para definir un estándar abierto para dicho lenguaje, lo que resultó en la versión 1.0 de Haskell en 1990 .
En 1986, como parte del trabajo para crear el lenguaje Eiffel , se creó el paradigma de programación por contrato ( Bertrand Meyer , 1986).
La teoría estudia aspectos de los lenguajes de programación, en la medida de lo posible, como un conjunto, usando uno u otro lenguaje particular como ejemplo, pero al mismo tiempo usando medios de un nivel de generalidad suficientemente alto para que los resultados puedan ser aplicados a alguna clase de idiomas A menudo, en los desarrollos teóricos se crea algún lenguaje de programación especializado, “ académico ”, que por una u otra razón no es apto para la implementación práctica, pero demuestra ciertos resultados teóricos, que posteriormente son aplicados a los lenguajes utilizados en la industria. Para la investigación teórica, se utilizan las herramientas de los fundamentos de las matemáticas y la lógica matemática , incluida la teoría de conjuntos , la teoría de modelos , la teoría de la computabilidad , así como secciones abstractas como la teoría de categorías , el álgebra universal , la teoría de grafos , y depende significativamente de los resultados de áreas aplicadas, incluida la teoría de la complejidad informática , la teoría de la codificación .
La semántica formal es una descripción tan formal de los lenguajes de programación que permite interpretar matemáticamente el "significado" de un programa de computadora escrito en ese lenguaje. Hay tres enfoques generales para describir la semántica de un lenguaje de programación: semántica denotacional , semántica operativa y semántica axiomática .
La teoría de tipos es el estudio de los sistemas de tipos ; es "un método sintáctico obediente para probar fallas en el comportamiento de un programa en particular clasificando frases por el nivel de valores que calculan" [2] . Muchos lenguajes de programación difieren en 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 principales (como la ausencia de errores en el programa).
La conversión de programas es el proceso de convertir un programa de una forma (idioma) a otra forma.
El análisis comparativo de lenguajes de programación busca clasificar los lenguajes de programación en diferentes tipos, dependiendo de sus características; las ideas y conceptos generales de los lenguajes de programación se conocen como paradigmas de programación .
La programación genérica es un paradigma de programación que consiste en tal descripción de datos y algoritmos que se pueden aplicar a varios tipos de datos sin cambiar esta descripción en sí.
La metaprogramación es la generación de programas de orden superior que, cuando se ejecutan, producen programas (quizás en otro idioma o en un subconjunto del idioma original) como resultado de su trabajo.
Los lenguajes específicos de dominio son lenguajes que están diseñados para resolver problemas de manera eficiente en un área temática en particular.
La teoría del compilador es la teoría de escribir compiladores (o, más generalmente, traductores); programas que traducen un programa escrito en un idioma a otra forma.
Las acciones del compilador se dividen tradicionalmente en:
Los sistemas de tiempo de ejecución se refieren al desarrollo de tiempos de ejecución del lenguaje de programación y sus componentes, incluidas las máquinas virtuales , la recolección de elementos no utilizados y las interfaces funcionales externas