Plankalkül - Plankalkül

Plankalkül

Paradigme	De procédure
Conçu par	Konrad Zuse
Première apparition	1948 ; Il y a 73 ans – concept publié pour la première fois ( 1948 )
Les principales mises en œuvre
Plankalkül-Compiler par la FU Berlin en 2000
Influencé par
Begriffsschrift
Influencé
Superplan de Heinz Rutishauser , ALGOL 58

Plankalkül ( prononciation allemande : [ˈplaːnkalkyːl] ) est un langage de programmation conçu à des fins d'ingénierie par Konrad Zuse entre 1942 et 1945. C'était le premier langage de programmation de haut niveau conçu pour un ordinateur.

Kalkül est le terme allemand pour un système formel - comme dans Hilbert-Kalkül , le nom original du système de déduction de style Hilbert - donc Plankalkül fait référence à un système formel de planification.

Histoire de la programmation

Dans le domaine de la création de machines informatiques, Zuse était autodidacte, et les développa sans connaître les autres machines informatiques mécaniques qui existaient déjà - bien que plus tard (construire le Z3 ) s'inspirant du livre de Hilbert et Ackermann sur l'élémentaire logique mathématique (cf. Principes de logique mathématique ). Pour décrire les circuits logiques, Zuse a inventé son propre système de diagramme et de notation, qu'il a appelé « combinatoire des conditions » ( allemand : Bedingungskombinatorik ). Après avoir terminé le Z1 en 1938, Zuse a découvert que le calcul qu'il avait conçu indépendamment existait déjà et était connu sous le nom de calcul propositionnel . Ce que Zuse avait en tête, cependant, devait être beaucoup plus puissant (le calcul propositionnel n'est pas Turing-complet et n'est pas capable de décrire même des calculs arithmétiques simples). En mai 1939, il décrit ses plans pour le développement de ce qui deviendra Plankalkül. Il a écrit ce qui suit dans son carnet :

Près d'une demi-année d'introduction progressive dans la logique formelle. J'y ai redécouvert beaucoup de mes pensées précédentes. (combinatoire des conditionnelles = calcul propositionnel ; étude des intervalles = théorie des réseaux ). Maintenant, je prévois la création de "Calcul des plans". Il y a une série de concepts nécessaires pour clarifier cela.	Seit etwa einem halben Jahr allmähliches Einführen in die formale Logik. Viele meiner früheren Gedanken habe ich dort wieder gefunden. (Bedingungskombinatorik = Aussagenlogik ; Lehre von den Intervallen = Gebietenkalkül). Ich plane jetzt die Aufsetzung des 'Plankalküls'. Hierzu sind eine Reihe von Begriffen zu klären.
	— Le carnet de Konrad Zuse

Tout en travaillant sur sa thèse de doctorat, Zuse a développé le premier système formel connu de notation d'algorithme capable de gérer les branches et les boucles. En 1942, il commença à écrire un programme d' échecs en Plankalkül. En 1944, Zuse a rencontré le logicien et philosophe allemand Heinrich Scholz , qui a exprimé son appréciation pour l'utilisation du calcul logique par Zuse . En 1945, Zuse décrit Plankalkül dans un livre inédit. L'effondrement de l'Allemagne nazie l'a cependant empêché de soumettre son manuscrit.

À cette époque, les deux seuls ordinateurs fonctionnels au monde étaient ENIAC et Harvard Mark I , dont aucun n'utilisait de compilateur, et ENIAC devait être reprogrammé pour chaque tâche en changeant la connexion des fils.

Bien que la plupart de ses ordinateurs aient été détruits par les bombes alliées, Zuse a pu sauver une machine, la Z4 , et la déplacer vers le village alpin de Hinterstein (qui fait partie de Bad Hindelang ).

La toute première tentative de concevoir un langage algorithmique a été entreprise en 1948 par K. Zuse. Sa notation était tout à fait générale, mais la proposition n'a jamais atteint la considération qu'elle méritait.

—  Heinz Rutishauser , créateur d' ALGOL

Incapable de continuer à construire des ordinateurs - ce qui était également interdit par les puissances alliées - Zuse a consacré son temps au développement d'un modèle et d'un langage de programmation de niveau supérieur. En 1948, il publia un article dans les Archiv der Mathematik et le présenta à la réunion annuelle du GAMM . Son travail n'a pas attiré beaucoup d'attention. Dans une conférence de 1957, Zuse a exprimé son espoir que Plankalkül, "après un certain temps en tant que Belle au bois dormant , revienne encore à la vie". Il a exprimé sa déception que les concepteurs d' ALGOL 58 n'aient jamais reconnu l'influence de Plankalkül sur leur propre travail.

Plankalkül a été publié de manière plus complète en 1972. Le premier compilateur a été mis en œuvre par Joachim Hohmann dans sa thèse de 1975. D'autres implémentations indépendantes ont suivi en 1998 et 2000 à l' Université libre de Berlin .

La description

Plankalkül a établi des comparaisons avec le langage APL et avec l' algèbre relationnelle . Il comprend des instructions d'affectation, des sous - routines , des instructions conditionnelles, des itérations, des calculs à virgule flottante , des tableaux, des structures d'enregistrement hiérarchiques, des assertions, la gestion des exceptions et d'autres fonctionnalités avancées telles que l' exécution dirigée par un objectif . Le Plankalkül fournit une structure de données appelée graphe généralisé ( verallgemeinerter Graph ), qui peut être utilisée pour représenter des structures géométriques.

Plankalkül partageait une notation idiosyncratique utilisant plusieurs lignes avec le Begriffsschrift de Frege de 1879 (traitant de la logique mathématique ).

Quelques caractéristiques du Plankalkül :

• uniquement des variables locales
• les fonctions ne prennent pas en charge la récursivité
• ne prend en charge que l' appel par valeur
• les types composites sont des tableaux et des tuples
• contient des expressions conditionnelles
• contient une boucle for et une boucle while
• pas de goto

Types de données

Le seul type de données primitif dans le Plankalkül est un seul bit ou booléen ( allemand : Ja-Nein-Werte - valeur yes-no dans la terminologie Zuses). Il est désigné par l'identifiant . Tous les autres types de données sont composites et construits à partir de primitives au moyen de « tableaux » et « enregistrements ». ${\style d'affichage S0}$

Ainsi, une séquence de huit bits (qui dans l'informatique moderne pourrait être considérée comme octet ) est notée , et une matrice booléenne de taille par   est décrite par . Il existe aussi une notation abrégée, on pourrait donc écrire à la place de . ${\style d'affichage 8\fois S0}$${\style d'affichage m}$${\style d'affichage n}$${\displaystyle m\fois n\fois S0}$${\displaystyle S1\cdot n}$${\style d'affichage n\fois S0}$

Type peut avoir deux valeurs possibles et . Ainsi, une séquence de 4 bits pourrait être écrite comme L00L, mais dans les cas où une telle séquence représente un nombre, le programmeur pourrait utiliser la représentation décimale 9. ${\style d'affichage S0}$${\style d'affichage 0}$${\style d'affichage L}$

Enregistrement de deux composants et s'écrit . ${\style d'affichage \sigma }$${\style d'affichage \tau }$${\style d'affichage (\sigma ,\tau )}$

Le type ( allemand : Art ) dans Plankalkül se compose de 3 éléments : valeur structurée ( allemand : Struktur ), sens pragmatique ( allemand : Typ ) et restriction possible sur les valeurs possibles ( allemand : Beschränkung ). Les types définis par l'utilisateur sont identifiés par la lettre A avec un numéro, comme - premier type défini par l'utilisateur. ${\style d'affichage A1}$

Exemples

Zuse a utilisé de nombreux exemples de la théorie des échecs :

${\style d'affichage A1}$	${\style d'affichage S1\cdot 3}$	Coordonnée de l'échiquier (il a la taille 8x8 donc 3 bits suffisent)
${\style d'affichage A2}$	${\style d'affichage 2\fois A1}$	carré du plateau (par exemple L00, 00L désigne e2 en notation algébrique )
${\style d'affichage A3}$	${\style d'affichage S1\cdot 4}$	pièce (par exemple, 00L0 - roi blanc)
${\style d'affichage A4}$	${\style d'affichage (A2,A3)}$	pièce sur un échiquier (par exemple L00, 00L ; 00L0 — roi blanc sur e2)
${\style d'affichage A5}$	${\displaystyle 64\fois A3}$	plateau (positions des pièces, décrit quelle pièce chacune des 64 cases contient)
${\style d'affichage A10}$	${\style d'affichage (A5,S0,S1\cdot 4,A2)}$	état du jeu (  — plateau,  — qui se déplace,  — possibilité de roquer (2 pour les blancs et 2 pour les noirs), A2 — informations sur la cellule sur laquelle le déplacement en passant est possible ${\style d'affichage A5}$${\style d'affichage S0}$${\style d'affichage S1\cdot 4}$

Identifiants

Les identifiants sont des caractères alphanumériques avec un nombre. Il existe les types d'identifiants suivants pour les variables :

• Valeurs d'entrée ( allemand : Eingabewerte, Variablen ) — marquées d'une lettre V.
• Valeurs intermédiaires et temporaires ( allemand : Zwischenwerte ) — marquées d'une lettre Z.
• Constantes ( allemand : Constanten ) — marquées d'une lettre С.
• Valeurs de sortie ( allemand : Resultatwerte ) — marquées d'une lettre R.

Une variable particulière d'un certain type est identifiée par un nombre, écrit sous le type. Par exemple:

${\displaystyle {\begin{matrice}V\\0\end{matrice}}}$, , etc${\displaystyle {\begin{matrice}Z\\2\end{matrice}}}$${\displaystyle {\begin{matrix}C\\31\end{matrix}}}$

Les programmes et sous-programmes sont marqués d'une lettre P, suivie d'un numéro de programme (et éventuellement d'un sous-programme). Par exemple , . ${\style d'affichage P13}$${\displaystyle P5\cdot 7}$

La valeur de sortie du programme enregistré dans la variable est disponible pour d'autres sous-programmes sous l'identifiant , et la lecture de la valeur de cette variable signifie également l'exécution du sous-programme associé. ${\style d'affichage P13}$${\displaystyle {\begin{matrice}R\\0\end{matrice}}}$${\displaystyle {\begin{matrice}R17\\0\end{matrice}}}$

Accéder aux éléments par index

Plankalkül permet l'accès à des éléments séparés de la variable en utilisant "l'index des composants" ( allemand : Komponenten-Index ). Lorsque, par exemple, le programme reçoit une entrée dans une variable de type (état du jeu), alors  — donne l'état du plateau,  — la pièce sur le carré numéro i et le bit numéro j de cette pièce. ${\displaystyle {\begin{matrice}V\\0\end{matrice}}}$${\style d'affichage A10}$${\displaystyle {\begin{matrice}V\\0\\0\end{matrice}}}$${\displaystyle {\begin{matrice}V\\0\\0\cdot i\end{matrice}}}$${\displaystyle {\begin{matrice}V\\0\\0\cdot i\cdot j\end{matrice}}}$

Dans les langages de programmation modernes, cela serait décrit par une notation similaire à V0[0], V0[0][i], V0[0][i][j](bien que pour accéder à un seul bit dans les langages de programmation modernes, un masque de bits soit généralement utilisé).

Syntaxe à deux dimensions

Étant donné que les index des variables sont écrits verticalement, chaque instruction Plankalkül nécessite plusieurs lignes à écrire.

La première ligne contient le type de variable, puis le numéro de variable marqué par la lettre V ( allemand : Variablen-Index ), puis les index des sous-composants variables marqués par K ( allemand : Komponenten-Index ), puis ( allemand : Struktur-Index ) marqué par S, qui décrit le type de variable. Le type n'est pas obligatoire, mais Zuse note que cela aide à lire et à comprendre le programme.

Dans les types de ligne et pourrait être raccourci à et . ${\style d'affichage S}$${\style d'affichage S0}$${\style d'affichage S1}$${\style d'affichage 0}$${\style d'affichage 1}$

Exemples:

${\displaystyle {\begin{array}{r|l}&V\\V&3\\K&\\S&m\times 2\times 1\cdot n\end{array}}}$	variable V3 — liste de paires de valeurs de type${\style d'affichage m}$${\displaystyle S1\cdot n}$
${\displaystyle {\begin{array}{r|l}&V\\V&3\\S&m\times 2\times 1\cdot n\end{array}}}$	La ligne K peut être ignorée lorsqu'elle est vide. Par conséquent, cette expression signifie la même chose que ci-dessus.
${\displaystyle {\begin{array}{r|l}&V\\V&3\\K&i\cdot 0\cdot 7\\S&0\end{array}}}$	La valeur du bit huit (index 7), de la première paire (index 0), du -ième élément de la variable V3, est de type booléen ( ). ${\style d'affichage S0}$

Les index peuvent être non seulement des constantes. Les variables peuvent être utilisées comme index pour d'autres variables, et cela est marqué d'une ligne, qui montre dans quel index de composant la valeur de la variable serait utilisée :

Z5-ème élément de la variable V3. Équivalent à l'expression V3[Z5]dans de nombreux langages de programmation modernes.

Opération d'affectation

Zuse a introduit dans son calcul un opérateur d'affectation, inconnu en mathématiques avant lui. Il l'a marqué avec « », et l'a appelé signe de cession ( allemand : Ergibt-Zeichen ). L'utilisation du concept d'affectation est l'une des principales différences entre les mathématiques et l'informatique. ${\displaystyle \Rightarrow }$

Zuse a écrit cette expression :

${\displaystyle {\begin{array}{r|lll}&Z+1&\Rightarrow &Z\\V&1&&1\\\end{array}}}$

est analogue à une équation mathématique plus traditionnelle :

${\displaystyle {\begin{array}{r|lll}&Z+1&=&Z\\V&1&&1\\K&i&&i+1\\\end{array}}}$

Certains prétendent que Konrad Zuse a initialement utilisé le glyphe comme signe d'affectation et a commencé à l'utiliser sous l'influence de Heinz Rutishauser . Knuth et Pardo pensent que Zuse a toujours écrit , et cela a été introduit par les éditeurs de «Über den allgemeinen Plankalkül als Mittel zur Formulierung schematisch-kombinativer Aufgaben» en 1948. Lors de la conférence ALGOL 58 à Zurich, les participants européens ont proposé d'utiliser pour l'affectation le caractère introduit par Zuse, mais la délégation américaine a insisté sur . ${\displaystyle \Rightarrow }$${\displaystyle \Rightarrow }$:=

La variable qui stocke le résultat d'une affectation ( l-value ) est écrite à droite de l'opérateur d'affectation. La première affectation à la variable est considérée comme une déclaration.

Le côté gauche de l'opérateur d'affectation est utilisé pour l'expression ( allemand : Ausdruck ), qui définit la valeur qui sera affectée à la variable. Les expressions peuvent utiliser des opérateurs arithmétiques, des opérateurs booléens et des opérateurs de comparaison ( etc.). ${\displaystyle =,\neq ,\leq }$

L'opération d'exponentiation est écrite de la même manière que l'opération d'indexation - en utilisant des lignes en notation 2D :

Flux de contrôle

Terminologie

Zuse a appelé un programme unique un Rechenplan ("plan de calcul"). Il a imaginé ce qu'il a appelé un Planfertigungsgerät (« dispositif d'assemblage de plans »), qui traduirait automatiquement la formulation mathématique d'un programme en un film perforé lisible par machine .

Exemple

La notation originale était en deux dimensions. Pour une implémentation ultérieure dans les années 1990, une notation linéaire a été développée.

L'exemple suivant définit une fonction max3(dans une transcription linéaire) qui calcule le maximum de trois variables :

P1 max3 (V0[:8.0],V1[:8.0],V2[:8.0]) → R0[:8.0]
max(V0[:8.0],V1[:8.0]) → Z1[:8.0]
max(Z1[:8.0],V2[:8.0]) → R0[:8.0]
END
P2 max (V0[:8.0],V1[:8.0]) → R0[:8.0]
V0[:8.0] → Z1[:8.0]
(Z1[:8.0] < V1[:8.0]) → V1[:8.0] → Z1[:8.0]
Z1[:8.0] → R0[:8.0]
END

Voir également

• Histoire des langages de programmation
• Chronologie des langages de programmation
• Liste des langages de programmation

Remarques

Les références

Liens externes

• Le "Plankalkül" de Konrad Zuse : un précurseur des langages de programmation d'aujourd'hui par Friedrich L. Bauer ( source alternative )
• Rojas, Raul , et al. (2000). « Plankalkül : Le premier langage de programmation de haut niveau et sa mise en œuvre ». Institut für Informatik, Freie Universität Berlin, Rapport technique B-3/2000. (texte intégral) (archivé)
• Mauerer, Wolfgang (2016-06-03). "Der Plankalkül von Konrad Zuse" (en allemand). Mise en œuvre en allemand. Archivé de l'original le 2016-06-03 . Récupéré le 03/10/2017 .
• "Plankalkül" . Archives Internet Konrad Zuse . Page archivée avec les applets java Plankalkül (non fonctionnels) et plusieurs documents (allemand/anglais). 2014-08-21. Archivé de l'original le 2014-08-21 . Récupéré le 04/10/2017 .CS1 maint: autres ( lien )
• Bram Bruines : Plankalkul (2010) - Plankalkül décrit de manière formelle