Théorie des langages de programmation

La théorie des langages de programmation (anglais : Programming language theory ou PLT) est une branche de l'informatique qui traite de la conception, de la mise en œuvre, de l'analyse, de la caractérisation et de la classification des langages formels appelés langages de programmation. Elle est étroitement liée à d'autres domaines, notamment les mathématiques, le génie logiciel et la linguistique. Il existe un nombre important de conférences universitaires et de revues sur le sujet.

Histoire

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.

Années 1960

Le langage Simula a été développé par Ole-Johan Dahl et Kristen Nygaard ; il est largement considéré comme le premier exemple de langage de programmation orienté objet ; Simula a également introduit le concept de coroutines. En 1964, Peter Landin est le premier à réaliser que le calcul lambda de Church peut être utilisé pour modéliser les langages de programmation. Il introduit la machine SECD qui «interprète» les expressions lambda.

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.

Années 1970

En 1970, Dana Scott publie pour la première fois ses travaux sur la sémantique dénotationnelle. En 1972, la programmation logique et Prolog sont développés, permettant ainsi aux programmes informatiques d'être exprimés en logique mathématique. Une équipe de scientifiques du Xerox PARC dirigée par Alan Kay développe Smalltalk, un langage orienté objet largement connu pour son environnement de développement innovant. En 1974, John C. Reynolds découvre le Système F ; il avait déjà été découvert en 1971 par le logicien mathématicien Jean-Yves Girard.

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

Années 1980

En 1981, Gordon Plotkin publie son article sur la sémantique opérationnelle structurée.

En 1988, Gilles Kahn publie son article sur la sémantique naturelle. Des algèbres de processus ont émergé, tels que le calcul des systèmes communicants de Robin Milner et le modèle de processus séquentiels communicants de CAR Hoare, ainsi que des modèles similaires de concurrence tels que le modèle d'acteur de Carl Hewitt.

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

Environnements d'exécution

Le développement d'environnements d'exécution de langage de programmation et de leurs composants, y compris les machines virtuelles, les ramasse-miettes et les interfaces de fonctions étrangères.

Revues, publications et conférences

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

Les revues notables qui publient des recherches en théorie des langages de programmation incluent les transactions ACM sur les langages et systèmes de programmation (TOPLAS), le Journal of Functional Programming (JFP), le Journal of Functional and Logic Programming et le journal Higher-Order and Symbolic Computation.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Programming language theory » (voir la liste des auteurs).

↑ Harold Abelson, Structure and Interpretation of Computer Programs, Cambridge, Mass., 2nd, 1996 (ISBN 0-262-01153-0, OCLC 34576857, lire en ligne).
↑ Corrado Böhm et W. Gross, Introduction to the CUCH. In E. R. Caianiello (ed.), Automata Theory, 1996, p. 35-64.
↑ (en) Benjamin C. Pierce, Types and Programming Languages, MIT Press, 4 janvier 2002 (ISBN 978-0-262-16209-8, lire en ligne).

Voir aussi

Articles connexes

SIGPLAN
Chronologie des langages de programmation
Langage de programmation de très haut niveau

Bibliographie

(en) Martín Abadi et Luca Cardelli, A Theory of Objects, Springer Verlag.
(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) Robert Harper, « Practical Foundations for Programming Languages », 2007
(en) Donald Knuth, « Selected Papers on Computer Languages », Stanford, Californie: Center for the Study of Language and Information, 2003, 2003
(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 », 1997.
(en) Benjamin C. Pierce, Types and Programming Languages, MIT Press, 2002 (ISBN 0-262-16209-1).
(en) Benjamin C. Pierce, Advanced Topics in Types and Programming Languages.
(en) Benjamin C. Pierce et al., Fondations logicielles, 2010 (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.
Grands travaux dans les langages de programmation. Recueilli par Benjamin C. Pierce ( Université de Pennsylvanie ).
Articles classiques en langages de programmation et logique. Recueilli par Karl Crary ( Université Carnegie Mellon ).
Recherche en langage de programmation. Annuaire par Mark Leone.
λ-Calculus: Then & Now par Dana S. Scott pour la célébration du centenaire de l'ACM Turing

Portail de la programmation informatique

[1] Harold Abelson, Structure and Interpretation of Computer Programs, Cambridge, Mass., 2nd, 1996 (ISBN 0-262-01153-0, OCLC 34576857, lire en ligne).

[2] Corrado Böhm et W. Gross, Introduction to the CUCH. In E. R. Caianiello (ed.), Automata Theory, 1996, p. 35-64.

[3] (en) Benjamin C. Pierce, Types and Programming Languages, MIT Press, 4 janvier 2002 (ISBN 978-0-262-16209-8, lire en ligne).

[1]

[2]

[3]