LOOP (langage de programmation) - LOOP (programming language)

LOOP est un langage de registre simple qui capture précisément les fonctions récursives primitives . Le langage est dérivé du modèle de la contre-machine . Comme les compteurs, le langage LOOP comprend un ensemble d'un ou plusieurs registres non bornés , chacun pouvant contenir un seul entier non négatif. Quelques instructions arithmétiques (comme 'Clear', 'INCrement', 'DECrement', 'CoPY', ...) opèrent sur les registres. La seule instruction de flux de contrôle est ' LOOP x DO ... END' . Il provoque la répétition x fois des instructions comprises dans son champ d'application. (Les modifications du contenu du registre x pendant l'exécution de la boucle n'affectent pas le nombre de passes.)

Histoire

Le langage LOOP a été formulé dans un article de 1967 par Albert R. Meyer et Dennis M. Ritchie . Ils ont montré la correspondance entre le langage LOOP et les fonctions récursives primitives .

La langue était également le sujet de la thèse de doctorat non publiée de Ritchie.

Il a également été présenté par Uwe Schöning , avec GOTO et WHILE .

Philosophie de conception et fonctionnalités

Contrairement aux programmes GOTO et WHILE, les programmes LOOP se terminent toujours . Par conséquent, l'ensemble des fonctions calculables par les programmes LOOP est un sous-ensemble approprié de fonctions calculables (et donc un sous- ensemble des fonctions calculables par les programmes WHILE et GOTO).

Meyer & Ritchie ont prouvé que chaque fonction récursive primitive est calculable en BOUCLE et vice versa.

Un exemple d'une fonction calculable totale qui n'est pas calculable en boucle est la fonction Ackermann .

Définition formelle

Syntaxe

Les programmes LOOP se composent des symboles LOOP, DO, END, :=, +et ;ainsi que d'un nombre quelconque de variables et de constantes. Les programmes LOOP ont la syntaxe suivante sous la forme Backus–Naur modifiée :

${\displaystyle {\begin{array}{lrl}P&::=&x_{i}:=0\\&|&x_{i}:=x_{i}+1\\&|&P;P\\&| &{\mathtt {LOOP}}\,x_{i}\,{\mathtt {DO}}\,P\,{\mathtt {END}}\end{array}}}$

Ici, sont des noms de variables et sont des constantes. ${\displaystyle Var :=\{x_{0},x_{1},...\}}$${\displaystyle c\in \mathbb {N} }$

Sémantique

Si P est un programme LOOP, P est équivalent à une fonction . Les variables à travers dans un programme LOOP correspondent aux arguments de la fonction , et sont initialisées avant l'exécution du programme avec les valeurs appropriées. Toutes les autres variables reçoivent la valeur initiale zéro. La variable correspond à la valeur qui prend lorsqu'on lui donne les valeurs d'argument de à . ${\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$${\style d'affichage x_{1}}$${\style d'affichage x_{k}}$${\style d'affichage f}$${\style d'affichage x_{0}}$${\style d'affichage f}$${\style d'affichage x_{1}}$${\style d'affichage x_{k}}$

Un énoncé de la forme

xi := 0

signifie que la valeur de la variable est définie sur 0. ${\style d'affichage x_{i}}$

Un énoncé de la forme

xi := xi + 1

signifie que la valeur de la variable est incrémentée de 1. ${\style d'affichage x_{i}}$

Un énoncé de la forme

P1; P2

représente l'exécution séquentielle des sous-programmes et , dans cet ordre. ${\style d'affichage P_{1}}$${\style d'affichage P_{2}}$

Un énoncé de la forme

LOOP x DO P END

signifie l'exécution répétée du programme partiel un total de fois, où la valeur qui a au début de l'exécution de l'instruction est utilisée. Même si change la valeur de , cela n'affectera pas le nombre d' exécutions dans la boucle. Si a la valeur zéro, alors n'est pas exécuté dans l' instruction LOOP . Cela permet des branches dans les programmes LOOP, où l'exécution conditionnelle d'un programme partiel dépend du fait qu'une variable a la valeur zéro ou un. ${\style d'affichage P}$${\style d'affichage x}$${\style d'affichage x}$${\style d'affichage P}$${\style d'affichage x}$${\style d'affichage P}$${\style d'affichage x}$${\style d'affichage P}$

Créer des « instructions de commodité »

A partir de la syntaxe de base, on crée des "instructions de commodité". Ce ne seront pas des sous-programmes au sens conventionnel du terme mais plutôt des programmes LOOP créés à partir de la syntaxe de base et dotés d'un mnémonique. Dans un sens formel, pour utiliser ces programmes, il faut soit (i) les "étendre" dans le code - ils nécessiteront l'utilisation de variables temporaires ou "auxiliaires" donc cela doit être pris en compte, ou (ii) concevoir le syntaxe avec les instructions « intégrées ».

Exemple

La fonction de projection k-aire extrait la i-ième coordonnée d'un k-uplet ordonné. ${\displaystyle U_{i}^{k}(x_{1},...,x_{i},...,x_{k})=x_{i}}$

Dans leur article fondateur, Meyer & Ritchie ont fait de la mission une déclaration de base. Comme le montre l'exemple, l'affectation peut être dérivée de la liste des instructions de base. ${\displaystyle x_{j} :=x_{i}}$

Pour créer l' instruction, utilisez le bloc de code ci-dessous. Observez l'utilisation de l'astuce mentionnée ci-dessus : ${\displaystyle \operatorname {assign} }$

${\displaystyle x_{j}:=\operatorname {assign} (x_{i})}$= _équivalent

xj := 0;
LOOP xi DO
  xj := xj + 1
END

Encore une fois, tout cela est pour plus de commodité seulement ; rien de tout cela n'augmente la puissance intrinsèque du modèle.

Exemples de programmes

Une addition

L'addition est définie récursivement comme :

${\displaystyle {\begin{aligned}a+0&=a,&{\textrm {(1)}}\\a+S(b)&=S(a+b).&{\textrm {(2) }}\end{aligné}}}$

Ici, S doit être lu comme "successeur".

Dans la séquence hyperopérateur, c'est la fonction${\displaystyle \operatorname {H_{1}} }$

${\displaystyle \operatorname {H_{1}} (x_{1},x_{2})}$peut être implémenté par le programme LOOP ADD( x ₁ , x ₂ )

LOOP x1 DO
  x0 := x0 + 1
END;
LOOP x2 DO
  x0 := x0 + 1
END

Multiplication

La multiplication est la fonction d'hyperopération ${\displaystyle \operatorname {H_{2}} }$

${\displaystyle \operatorname {H_{2}} (x_{1},x_{2})}$peut être implémenté par le programme LOOP MULT( x ₁ , x ₂ )

x0 := 0;
LOOP x2 DO
  x0 := ADD( x1, x0)
END

Le programme utilise le programme ADD() comme "instruction de commodité". Développé, le programme MULT est un programme LOOP avec deux instructions LOOP imbriquées. AJOUTER compte pour un.

Plus d'hyperopérateurs

Étant donné un programme LOOP pour une fonction d'hyperopération , on peut construire un programme LOOP pour le niveau suivant ${\displaystyle \operatorname {H_{i}} }$

${\displaystyle \operatorname {H_{3}} (x_{1},x_{2})}$par exemple (qui signifie exponentiation ) peut être implémenté par le programme LOOP POWER( x ₁ , x ₂ )

x0 := 1;
LOOP x2 DO
  x0 := MULT( x1, x0 )
END

Le programme d'exponentiation, développé, comporte trois instructions LOOP imbriquées.

Prédécesseur

La fonction prédécesseur est définie comme

${\displaystyle \operatorname {pred} (n)={\begin{cases}0&{\mbox{if }}n=0,\\n-1&{\mbox{autrement}}\end{cases}}}$.

Cette fonction peut être calculée par le programme LOOP suivant, qui définit la variable sur . ${\style d'affichage x_{0}}$${\displaystyle pred(x_{1})}$

/* precondition: x2 = 0 */
LOOP x1 DO
  x0 := x2;
  x2 := x2 + 1
END

Élargi, c'est le programme

/* precondition: x2 = 0 */
LOOP x1 DO
  x0 := 0;
  LOOP x2 DO
    x0 := x0 + 1
  END;
  x2 := x2 + 1
END

Ce programme peut être utilisé comme sous-programme dans d'autres programmes LOOP. La syntaxe LOOP peut être étendue avec l'instruction suivante, équivalente à l'appel ci-dessus en tant que sous-programme :

x0 := x1 ∸ 1

Remarque : Encore une fois, il faut faire attention aux effets secondaires. Le programme précédent modifie la variable x ₂ , qui pourrait être utilisée ailleurs. Pour développer l'instruction x ₀  := x ₁ 1, on pourrait initialiser les variables x _n , x _n+1 et x _n+2 (pour un n assez grand) à 0, x ₁ et 0 respectivement, exécutez le code sur ces variables et copiez le résultat (x _n ) dans x ₀ . Un compilateur peut le faire.

Soustraction de coupure

Si dans le programme « addition » au-dessus de la deuxième boucle décrémente x ₀ au lieu d'incrémenter, le programme calcule la différence (coupée à 0) des variables et . ${\style d'affichage x_{1}}$${\style d'affichage x_{2}}$

x0 := x1
LOOP x2 DO
  x0 := x0 ∸ 1
END

Comme auparavant, nous pouvons étendre la syntaxe LOOP avec l'instruction :

x0 := x1 ∸ x2

Si alors sinon

Une instruction if-then-else avec if x ₁ > x ₂ then P1 else P2 :

xn1 := x1 ∸ x2;
xn2 := 0;
xn3 := 1;
LOOP xn1 DO
  xn2 := 1;
  xn3 := 0
END;
LOOP xn2 DO
  P1
END;
LOOP xn3 DO
  P2
END;

Voir également

• fonction -récursive
• fonction récursive primitive
• BlooP et FlooP

Notes et références

Bibliographie

Liens externes

• Boucle, Goto & While