Par certains aspects, l'histoire de la théorie des langages de programmation est antérieure au développement des langages de programmation eux-mêmes. Le lambda-calcul, développé par Alonzo Church et Stephen Cole Kleene dans les années 1930, est considéré par certains comme le premier langage de programmation au monde, même s'il était destiné à « modéliser » le calcul plutôt qu'à être un moyen pour les programmeurs de « décrire » des algorithmes à un système informatique. Pourtant, de nombreux langages de programmation fonctionnels modernes sont désormais aisément décrits en termes de lambda-calcul.
Le premier langage de programmation à être inventé fut Plankalkül, conçu par Konrad Zuse dans les années 1940, mais inconnu du public avant 1972 (et pas implémenté avant 1998). Le premier langage de programmation de haut niveau largement connu et populaire fut Fortran, développé entre 1954 et 1957 par une équipe de chercheurs d'IBM dirigée par John Backus. Le succès de FORTRAN a conduit à la formation d'un comité de scientifiques pour développer un langage informatique «universel», dont les efforts menèrent à la création d'Algol 58. Par ailleurs, John McCarthy du MIT a développé Lisp, le premier langage d'origine universitaire à connaître le succès. Avec le succès de ces efforts initiaux, les langages de programmation sont devenus un sujet de recherche actif dans les années 1960 et au-delà.
Quelques autres événements clés dans l'histoire de la théorie des langages de programmation depuis :
Années 1950
Noam Chomsky a développé la hiérarchie de Chomsky dans le domaine de la linguistique, une découverte qui a eu un impact direct sur la théorie des langages de programmation et d'autres branches de l'informatique.
En 1965, Landin introduit l'opérateur J, essentiellement une forme de continuation. En 1966, Landin introduit ISWIM, un langage de programmation informatique abstrait dans son article The Next 700 Programming Languages. Il sera influent dans la conception des langages menant au langage de programmation Haskell. En 1966 toujours, Corrado Böhm introduit le langage de programmation CUCH (Curry-Church)[2]. En 1967, Christopher Strachey publie son ensemble influent de notes de cours Fundamental Concepts in Programming Languages, introduisant la terminologie des R-values, L-values, polymorphisme paramétrique et polymorphisme ad hoc. En 1969, J. Roger Hindley publie The Principal Type-Scheme of an Object in Combinatory Logic, plus tard généralisé dans l'algorithme d'inférence de type Hindley-Milner. La même année, Tony Hoare introduit la logique de Hoare, une forme de sémantique axiomatique. Toujours en 1969, William Alvin Howard a observé qu'un système de preuve « de haut niveau », appelé déduction naturelle, peut être directement interprété dans sa version intuitionniste comme une variante typée du modèle de calcul connu sous le nom de lambda-calcul. Cela est désormais connu sous le nom de correspondance de Curry-Howard.
À partir de 1975, Gerald Jay Sussman et Guy Steele développent le langage de programmation Scheme, un dialecte Lisp incorporant une portée lexicale, un espace de noms unifié et des éléments du modèle d'acteur comprenant des continuations de première classe. Backus, lors de la conférence du prix Turing de 1977, a attaqué l'état actuel des langages industriels et a proposé une nouvelle classe de langages de programmation maintenant connus sous le nom de langages de programmation niveau fonction. En 1977, Gordon Plotkin introduit Programming Computable Functions, un langage fonctionnel typé abstrait. En 1978, Robin Milner introduit l'algorithme d'inférence de type Hindley-Milner pour ML. La théorie des types est devenue une discipline appliquée aux langages de programmation, ce qui l'a conduit à d'énormes progrès au fil des ans.
En 1985, la sortie du langage de programmation Miranda suscite un intérêt académique pour les langages de programmation fonctionnels purs à évaluation paresseuse. Un comité a été formé pour définir une norme ouverte aboutissant à la publication de la norme Haskell 1.0 en 1990. Bertrand Meyer a créé la méthodologie Design by contract et l'a intégrée au langage de programmation Eiffel.
Années 1990
Gregor Kiczales, Jim Des Rivieres et Daniel G. Bobrow ont publié le livre The Art of the Metaobject Protocol. Eugenio Moggi et Philip Wadler ont introduit l'utilisation des monades pour structurer les programmes écrits dans des langages de programmation fonctionnels.
Sous-disciplines et domaines connexes
Il existe plusieurs domaines d'études qui soit relèvent de la théorie des langages de programmation, soit ont une profonde influence sur celle-ci. Beaucoup d'entre eux se chevauchent considérablement. En outre, la théorie des langages de programmation utilise de nombreuses autres branches des mathématiques, notamment la théorie de la calculabilité, la théorie des catégories et la théorie des ensembles.
Sémantique formelle
La sémantique formelle est la spécification formelle du comportement des programmes informatiques et des langages de programmation. Trois approches courantes pour décrire la sémantique ou la « signification » d'un programme informatique sont la sémantique dénotationnelle, la sémantique opérationnelle et la sémantique axiomatique.
Théorie des types
La théorie des types est l'étude des systèmes de types, qui sont « une méthode syntaxique conciliante pour prouver l'absence de certains comportements de programme en classant les phrases selon les types de valeurs qu'elles calculent »[3]. De nombreux langages de programmation se distinguent par les caractéristiques de leurs systèmes de types.
Analyse et transformation de programme
L'analyse de programme est le processus d'examen d'un programme et la détermination de ses caractéristiques clés (telles que l'absence de certaines erreurs informatiques). La transformation de programme est le processus de transformation d'un programme d'une forme (langage) à une autre.
Analyse comparative
L'analyse comparative des langages de programmation vise à classer les langages de programmation en différents types en fonction de leurs caractéristiques; les grandes catégories de langages de programmation sont souvent appelées paradigmes de programmation.
Programmation générique et métaprogrammation
La métaprogrammation est la génération de programmes d'ordre supérieur qui, lorsqu'ils sont exécutés, produisent des programmes (éventuellement dans un langage différent ou dans un sous-ensemble du langage d'origine).
Langages dédiés
Les langages dédiés sont des langages conçus pour résoudre efficacement certains problèmes d'un domaine spécifique.
Construction de compilateur
La théorie des compilateurs est la théorie des « compilateurs » d'écriture (ou plus généralement, des « traducteurs »). Ce sont des programmes qui traduisent un programme écrit dans un langage en une autre forme. Les actions d'un compilateur sont traditionnellement décomposées en « analyse syntaxique » ( analyse et parsing ), « analyse sémantique » (détermination de ce qu'un programme doit faire), « optimisation » (amélioration des performances d'un programme comme indiqué par une métrique ; généralement vitesse d'exécution) et « génération de code » (génération d'un programme équivalent dans un langage cible ; souvent le jeu d'instructions d'un processeur).
Les conférences sont le principal lieu de présentation de la recherche dans les langages de programmation. Les conférences les plus connues incluent le Symposium on Principles of Programming Languages (POPL), Programming Language Design and Implementation (PLDI), l'International Conference on Functional Programming (ICFP), l'International Conference on Object Oriented Programming, Systems, Languages and Applications (OOPSLA) et la Conférence internationale sur le support architectural des langages de programmation et des systèmes d'exploitation (ASPLOS) .
(en) Michael JC Gordon, Programming Language Theory and Its Implementation, Prentice Hall
(en) Carl Gunter et John C. Mitchell (éd. ), Theoretical Aspects of Object Oriented Programming Languages: Types, Semantics, and Language Design, The MIT Press
(en) John C. Mitchell, Foundations for Programming Languages
(en) John C. Mitchell, Introduction to Programming Language Theory
(en) Peter O'Hearn et Robert. D. Tennent, Algol-like Languages, Boston, Birkhauser, coll. « Progress in Theoretical Computer Science », .
(en) Benjamin C. Pierce, Types and Programming Languages, MIT Press, (ISBN0-262-16209-1).
(en) Benjamin C. Pierce, Advanced Topics in Types and Programming Languages.
(en) Benjamin C. Pierce et al., Fondations logicielles, (lire en ligne).
Liens externes
Lambda the Ultimate, un blog communautaire pour des discussions professionnelles et un ensemble de documents sur la théorie des langages de programmation.