Rapport Algol-60

Le rapport Algol-60 a été rédigé entre 1959 et 1960 par une équipe d’experts en langage de programmation composée de l’éditeur Peter Naur et de plusieurs éducateurs et praticiens d’Europe et des États-Unis. L’objectif du rapport était de développer une description complète d’un langage algorithmique international pour exprimer des processus numériques sous une forme adaptée à la traduction dans des langages de programmation informatique. Il n’était pas destiné à être un langage de programmation, bien qu’il ait été par la suite mis en œuvre comme un langage et soit devenu populaire en Europe.

De nombreuses versions du langage de programmation Algol ont été mises en œuvre dans les années 1960 et au début des années 1970. Il a également conduit au développement de plusieurs autres langages de programmation, comme le Pascal, implémenté par Niklaus Wirth au début des années 1970, et le C.

Le rapport a introduit les notions de langage de référence, de langage de publication et de représentation matérielle. Le langage de référence était la norme pour le rapport, les auteurs de compilateurs et l’implémentation matérielle. Il dictait la forme du langage et sa syntaxe . Le langage de publication utilisait le langage de référence avec des ajustements mineurs pour tenir compte des variations de publication entre les pays et des variations d’impression et d’écriture telles que la manipulation des indices, des exposants et d’autres notations. La représentation matérielle tenait compte des caractéristiques de la machine. Le langage de référence était le langage de définition, et le langage de publication et la représentation matérielle devaient pouvoir être traduits en lui.

Le but du rapport et du langage était de donner une représentation non ambiguë à divers concepts informatiques – en particulier, la conception d’algorithmes, ou ALGOrithmic Language 1960. Une version ultérieure, Algol68, n’a pas été aussi populaire ou largement mise en œuvre que l’Algol-60, bien qu’elle ait été plus puissante.

Algol est un langage structuré, incorporant des instructions while, des instructions if-then-else, et d’autres constructions qui mettent en œuvre la sélection, l’itération, les instructions de base, la structure de bloc, et la récursion. Bien qu’il ait été développé seulement quelques années après le FORTRAN (FORmula TRANslator), publié en 1957 par IBM, il incorporait des caractéristiques absentes du FORTRAN – à savoir la récursion et le langage structuré – et constituait une avancée majeure dans le domaine de la programmation.

L’un des descendants d’Algol et du FORTRAN était le langage BASIC (Beginner’s All-purpose Symbolic Instruction Code), développé par John Kemeny et Thomas Kurtz de l’université de Dartmouth. BASIC était une sorte de version du FORTRAN sans déclaration de format, destinée à l’informatique interactive et au débutant. BASIC a joui d’un long règne des années 1970 aux années 1980 et a récemment été implémenté sous une forme tout à fait différente, Visual Basic.

Un descendant d’Algol était Pascal, qui a également joui d’un long règne en tant que langage populaire pour l’implémentation de structures de données et l’étude de compilateurs . Ce n’était pas un langage de production, mais un outil d’enseignement. C était le langage d’un système et a conduit au développement de C, un langage orienté objet qui est toujours populaire.

Le langage Algol était décrit dans une notation appelée forme normale de Backus ou Backus-Naur (BNF). Cette notation a été suggérée par John Backus, qui l’a basée sur une notation d’E. L. Post, un célèbre logicien des années 1930. Elle était similaire à la notation développée par Noam Chomsky en 1957 pour la linguistique, qui était utilisée pour implémenter des grammaires. Une grammaire est une manière succincte et non ambiguë de décrire les langues. L’utilisation d’une notation formelle dans la théorie des langages a constitué une avancée majeure.

L’évolution des langages de programmation a été frappante, mais pas aussi étonnante que celle de la théorie des compilateurs. Peu après le rapport Algol-60, plusieurs théoriciens du compilateur ont utilisé la notation grammaticale pour implémenter des compilateurs de manière « automatique ». Ces compilateurs étaient connus sous le nom de compilateurs-compilateurs. Des efforts similaires ont été le développement de Lex, un analyseur lexical, et de Yacc (« Yet another compiler-compiler ») aux Laboratoires Bell au milieu des années 1970.

Comprendre le langage de programmation

La grammaire anglaise a certaines constructions, comme un syntagme nominal, qui est composé d’autres constructions, comme un nom et un modificateur. Les langages de programmation ont des constructions telles que les déclarations while, et les expressions arithmétiques. Ces constructions sont indiquées par des symboles spéciaux appelés les symboles non terminaux ou méta du langage.

Les symboles qui apparaissent réellement dans le langage sont appelés symboles terminaux. La terminologie provient des structures de données, ou arbres d’analyse, utilisées pour implémenter le langage.

Un exemple est :

Cette grammaire indique qu’une expression arithmétique, E, est constituée d’autres expressions arithmétiques et de termes, T, additionnés (E–>E T). Un terme, T, est composé d’un terme multiplié par un facteur, F, de sorte que T–>T*F. Enfin, un facteur, F, est l’expression la plus basique, composée d’expressions entre parenthèses (les E entre parenthèses), d’identifiants (identifiants ou variables définis par l’utilisateur), id, et de constantes numériques (num). La grammaire donne la forme des expressions arithmétiques.

L’exemple donne une saveur de la notation. Les éléments à gauche de la flèche sont composés des éléments à droite. Dans ce cas, les E, T, et F sont les méta-symboles. Les autres symboles, *, (, ), et, dans ce cas, id et num, apparaissent dans le langage. Ils sont les mots de la langue. Dans ce cas, E est le symbole de départ ou le premier symbole non-terminal. C’est l’expression la plus générale qui est définie. Bien que la notation puisse sembler maladroite au début, elle est utile dans la conception du langage, la théorie du compilateur et la mise en œuvre.

Le développement des grammaires en informatique a donné une grande impulsion à la conception et à la mise en œuvre des langages de programmation.

Voir aussi Algorithmes ; Langages procéduraux ; Programmation.

Roger R. Flynn

Bibliographie

Naur, Peter, ed. « Rapport révisé sur le langage algorithmique Algol-60 ». Communications ACM 6, no. 1 (1963) : 1-17.

Wexelblat, Richard L., ed. Histoire des langages de programmation. New York : Academic Press, 1981.