Algol (langage)

Le premier rapport décrivant le langage date de 1958 et a donc donné lieu à Algol 58. Présentant des ambiguïtés sévères, il fut stabilisé sous le nom d'Algol 60, langage largement adopté dans les universités, et qui fit faire des progrès importants à la compilation.

Algol 60 a été publié en 1960. John Backus et Peter Naur faisaient partie du comité de conception et spécification qui l'a créé. Plus précisément, le comité qui s'est réuni à Paris du 11 au 16 janvier 1960 était composé des treize experts européens et américains suivants :

• Friedrich L. Bauer, Peter Naur, Heinz Rutishauser, Klaus Samelson, Bernard Vauquois, Adriaan van Wijngaarden, Mike Woodger (représentants européens) ;
• John Backus, Julien Green, Charles Katz, John McCarthy, Alan Perlis, Joseph Henry Wegstein (représentants américains).

Algol 60 a inspiré beaucoup de langages. C. A. R. Hoare a déclaré à son sujet : « Voici un langage très en avance de son temps, il n'a pas seulement été une amélioration de ses prédécesseurs mais aussi une amélioration de presque tous ses successeurs^[2] ».

Hormis un succès universitaire certain, Algol 60 sera peu utilisé dans des programmes commerciaux. Cela est dû au manque de fonctions standards d'entrée-sortie (corrigé en 1965 et surcorrigé dans Algol 68), et à une mauvaise adaptation aux programmes de gestion. Sur le plan scientifique, il était moins efficace que Fortran, tout en permettant des traitements a priori impossibles dans ce langage.

Ses trois principaux descendants sont :

• Algol 68, conçu au Centre de Mathématiques Appliquées d'Amsterdam, et défini en décembre 1968 ; langage universel basé sur un système de 2 grammaires orthogonales (engendrant une grammaire potentiellement infinie) il permet de construire de nouveaux types et de nouveaux opérateurs, facilitant une approche très algébrique des applications ; jouant sur la puissance des mécanismes plutôt que sur leur nombre, il a été souvent perçu comme l'antithèse de PL/I ;
• Algol W, créé peu après selon les propositions plus statiques de Niklaus Wirth, membre du groupe de travail sur Algol 68 dont les propositions avaient été refusées. Wirth s'inspirera d'Algol W pour créer le langage Pascal, puis Modula 2 ;

•  

  Simula (1967), conçu à Oslo, sur-ensemble d'Algol 60, ancêtre des langages objet (comme C++, Modula 3, Oberon) permettant de définir des classes et des processus facilitant la simulation à événements discrets.

La suite de cet article est principalement consacrée au langage Algol 60. En effet, sans mention de millésime, le terme Algol désigne le langage Algol 60, tandis que les Algols désigne l'ensemble de la famille.

Algol 60 est un langage typé, procédural récursif et à structure de blocs. Il permet un emploi dynamique des types mais ne permet pas à l'utilisateur d'en définir de nouveaux. Algol 60 a été défini sans instructions d'entrées/sorties ; une implémentation sur une machine donnée en comportait nécessairement, mais elles variaient de l'une à l'autre. En réaction à cette situation, Algol 68 les a sur-spécifiées.

Algol 60 permet deux types de passage de paramètres lors de l'appel de procédure : passage par valeur et le « passage par nom », proche de la macro-substitution. Le passage par nom possède des propriétés, mal comprises du fait d'une confusion avec le passage par référence, plus répandu ; aussi a-t-il été abandonné dans les successeurs d'Algol 60. Par exemple, on a reproché à ce mode Algol 60 l'impossibilité d'écrire une procédure échangeant deux valeurs si un des paramètres est un entier et l'autre un tableau indexé par ce même entier.

En réaction contre le manque de formalisme dans le projet Fortran, John Backus a conçu la BNF pour Backus Normal Form permettant la spécification de Algol 58. Cette méthode de description d'un langage a été révisée et étendue par Peter Naur sous le nom Backus Naur Form avec le même acronyme pour spécifier Algol 60, ainsi muni d'une grammaire indépendante du contexte.

Une importante innovation d'Algol 60 était l'introduction de la récursivité, permettant de programmer des algorithmes pour le calcul de fonctions récursives pures (telles que la fonction d'Ackermann-Péter), et plus seulement des fonctions récursives primitives (telles que la factorielle ou la suite de Fibonacci, qui peuvent être calculées avec des boucles for). Ceci distinguait Algol 60 de Fortran, qui ne permettait pas d'implémenter le calcul de fonctions récursives non primitives ; cependant, l'intérêt pratique de cette innovation, qui avait fait l'objet de débats au sein du comité Algol 60, n'est véritablement apparu qu'avec la programmation de compilateurs, pour lesquels cette fonctionnalité simplifie grandement certains éléments algorithmiques^[3],[4].

Algol 68^[5] a été défini comme langage universel basé sur des types et des opérateurs prédéfinis, des procédés de construction de nouveaux types, et de nouveaux opérateurs avec possibilité de surcharge et d'extension des opérateurs prédéfinis, le tout permettant d'adapter le langage à chaque famille d'applications.

Comme une grammaire indépendante du contexte, telle que l'on peut définir avec BNF, s'avère une grammaire simple, que la rigueur demande de compléter par des restrictions sémantiques en langue naturelle, trop souvent ambiguës, l'équipe de Adriaan van Wijngaarden a retenu un système grammatical, dit grammaires de van Wijngaarden (seconde forme) couvrant la syntaxe en rapport avec la sémantique. S'appuyant sur une hyper-grammaire (donnant des schémas de règles ou hyper-règles) interagissant avec une méta-grammaire (reflétant la théorie des types constructibles), le système grammatical produit une infinité de contraintes de BNF sémantiquement adéquates. Le Rapport Révisé a parfaitement illustré l'adéquation de ce dispositif, qui définit une syntaxe sémantiquement correcte. Cette approche totale facilite une compilation « carrée ».

Le B5000 de Burroughs Corporation et ses successeurs étaient des machines à pile conçues pour être programmées avec un Algol étendu ; leur systèmes d'exploitation est écrit dans cet Algol depuis 1961, ouvrant la voie à l'écriture des systèmes d'exploitation en langage symbolique, reprise par Multics puis Unix. Unisys Corporation continue de commercialiser des machines descendant du B5000 supportant plusieurs compilateurs Algol étendus.

Le CAE 510 comportait un compilateur Algol conforme au niveau II de la norme AFNOR FZ 65-010^[6], incluant de plus la récursivité et autorisant les mots-clés en français comme début et fin^[7].

Les programmes Algol 60 sont à format libre, avec le point-virgule comme séparateur principal. Les termes en caractère gras (procedure…) sont des mots réservés du langage. Chaque implémentation du langage peut utiliser sa propre convention lexicale (par exemple 'PROCEDURE').

procedure Absmax(a) Taille:(n, m) Resultat:(y) Indices:(i, k);
    value n, m; array a; integer n, m, i, k; real y;
comment  Dans la procédure Absmax (a, n, m, y, i, k)
         le plus grand élément en valeur absolue de la matrice a de taille
         n par m est transféré à y et les indices de cet élément à i et k ;
begin integer p, q;
    y := 0; i := k := 1;
    for p:=1 step 1 until n do
        for q:=1 step 1 until m do
            if abs(a[p, q]) > y then
                begin
                    y := abs(a[p, q]);
                    i := p; k := q;
                end
end Absmax

• (en) Revised Report on the Algorithmic Language Algol 60 et d'autres documents
• (en) Algol 60 en BNF
• (en) rapport Algol 60
• (fr) « Etude et réalisation d'un compilateur Algol 60 sur calculateur électronique du type IBM 7090/94 et 7040/44 / thèse de J.-C. Boussard, sur la base TEL-CNRS ».
• (en) History of ALGOL

•   Portail de la programmation informatique