LOOP (linguaggio di programmazione) - LOOP (programming language)

LOOP è un semplice linguaggio di registro che cattura con precisione le funzioni ricorsive primitive . Il linguaggio è derivato dal modello della contromacchina . Come le macchine contatrici, il linguaggio LOOP comprende un insieme di uno o più registri illimitati , ognuno dei quali può contenere un singolo intero non negativo. Alcune istruzioni aritmetiche (come 'CleaR', 'INCrement', 'DECrement', 'CoPY', ...) operano sui registri. L'unica istruzione del flusso di controllo è ' LOOP x DO ... END' . Fa sì che le istruzioni all'interno del suo ambito vengano ripetute x volte. (Le modifiche al contenuto del registro x durante l'esecuzione del ciclo non influiscono sul numero di passaggi.)

Storia

Il linguaggio LOOP è stato formulato in un articolo del 1967 da Albert R. Meyer e Dennis M. Ritchie . Hanno mostrato la corrispondenza tra il linguaggio LOOP e le funzioni ricorsive primitive .

La lingua è stata anche l'argomento della tesi di dottorato inedita di Ritchie.

È stato presentato anche da Uwe Schöning , insieme a GOTO e WHILE .

Filosofia e caratteristiche del design

A differenza dei programmi GOTO e WHILE , i programmi LOOP terminano sempre . Pertanto, l'insieme delle funzioni calcolabili dai programmi LOOP è un sottoinsieme appropriato di funzioni calcolabili (e quindi un sottoinsieme delle funzioni calcolabili dai programmi WHILE e GOTO).

Meyer e Ritchie hanno dimostrato che ogni funzione ricorsiva primitiva è calcolabile con LOOP e viceversa.

Un esempio di una funzione calcolabile totale che non è calcolabile LOOP è la funzione di Ackermann .

Definizione formale

Sintassi

I programmi LOOP sono costituiti dai simboli LOOP, DO, END, :=, +e ;da qualsiasi numero di variabili e costanti. I programmi LOOP hanno la seguente sintassi nella forma Backus–Naur modificata :

${\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}}}$

Qui ci sono nomi di variabili e sono costanti. ${\displaystyle Var:=\{x_{0},x_{1},...\}}$${\displaystyle c\in \mathbb {N} }$

Semantica

Se P è un programma LOOP, P è equivalente a una funzione . Le variabili passanti in un programma LOOP corrispondono agli argomenti della funzione e vengono inizializzate prima dell'esecuzione del programma con i valori appropriati. A tutte le altre variabili viene assegnato il valore iniziale zero. La variabile corrisponde al valore che assume quando vengono forniti i valori dell'argomento da a . ${\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N}}$${\displaystyle x_{1}}$${\displaystyle x_{k}}$${\displaystyle f}$${\displaystyle x_{0}}$${\displaystyle f}$${\displaystyle x_{1}}$${\displaystyle x_{k}}$

Una dichiarazione della forma

xi := 0

significa che il valore della variabile è impostato su 0. ${\displaystyle x_{i}}$

Una dichiarazione della forma

xi := xi + 1

significa che il valore della variabile viene incrementato di 1. ${\displaystyle x_{i}}$

Una dichiarazione della forma

P1; P2

rappresenta l'esecuzione sequenziale di sottoprogrammi e , in quest'ordine. ${\displaystyle P_{1}}$${\displaystyle P_{2}}$

Una dichiarazione della forma

LOOP x DO P END

indica l'esecuzione ripetuta del programma parziale per un totale di volte, dove viene utilizzato il valore che ha all'inizio dell'esecuzione dell'istruzione. Anche se cambia il valore di , non influenzerà quante volte viene eseguito nel ciclo. Se ha valore zero, allora non viene eseguito all'interno dell'istruzione LOOP . Ciò consente diramazioni nei programmi LOOP, in cui l'esecuzione condizionale di un programma parziale dipende dal fatto che una variabile abbia valore zero o uno. ${\displaystyle P}$${\displaystyle x}$${\displaystyle x}$${\displaystyle P}$${\displaystyle x}$${\displaystyle P}$${\displaystyle x}$${\displaystyle P}$

Creazione di "istruzioni pratiche"

Dalla sintassi di base si creano "istruzioni di convenienza". Queste non saranno subroutine nel senso convenzionale, ma piuttosto programmi LOOP creati dalla sintassi di base e dati un mnemonico. In senso formale, per utilizzare questi programmi è necessario (i) "espanderli" nel codice - richiederanno l'uso di variabili temporanee o "ausiliari", quindi questo deve essere preso in considerazione, o (ii) progettare il sintassi con le istruzioni 'integrato'.

Esempio

La funzione di proiezione k-ary estrae la coordinata i-esima da una k-upla ordinata. ${\displaystyle U_{i}^{k}(x_{1},...,x_{i},...,x_{k})=x_{i}}$

Nel loro articolo fondamentale, Meyer & Ritchie hanno fatto dell'incarico una dichiarazione di base. Come mostra l'esempio, l'assegnazione può essere derivata dall'elenco delle istruzioni di base. ${\displaystyle x_{j}:=x_{i}}$

Per creare l' istruzione utilizzare il blocco di codice sottostante. Osservare l'uso del suggerimento sopra menzionato: ${\displaystyle \nomeoperatore {assegna} }$

${\displaystyle x_{j}:=\nomeoperatore {assegna} (x_{i})}$= _equiv

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

Ancora una volta, tutto questo è solo per comodità; niente di tutto questo aumenta il potere intrinseco del modello.

Programmi di esempio

aggiunta

L'addizione è definita ricorsivamente come:

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

Qui, S dovrebbe essere letto come "successore".

Nella sequenza dell'iperoperatore è la funzione${\displaystyle \nomeoperatore {H_{1}} }$

${\displaystyle \nomeoperatore {H_{1}} (x_{1},x_{2})}$può essere implementato dal programma LOOP ADD( x ₁ , x ₂ )

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

Moltiplicazione

La moltiplicazione è la funzione di iperoperazione ${\displaystyle \nomeoperatore {H_{2}} }$

${\displaystyle \nomeoperatore {H_{2}} (x_{1},x_{2})}$può essere implementato dal programma LOOP MULT( x ₁ , x ₂ )

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

Il programma utilizza il programma ADD() come "istruzione di convenienza". Espanso, il programma MULT è un programma LOOP con due istruzioni LOOP annidate. AGGIUNGI conta per uno.

Più iperoperatori

Dato un programma LOOP per una funzione di iperoperazione , si può costruire un programma LOOP per il livello successivo ${\displaystyle \nomeoperatore {H_{i}} }$

${\displaystyle \nomeoperatore {H_{3}} (x_{1},x_{2})}$ad esempio (che sta per elevamento a potenza ) può essere implementato dal programma LOOP POWER( x ₁ , x ₂ )

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

Il programma di elevazione a potenza, espanso, ha tre istruzioni LOOP nidificate.

Predecessore

La funzione predecessore è definita come

${\displaystyle \operatorname {pred} (n)={\begin{casi}0&{\mbox{se }}n=0,\\n-1&{\mbox{altrimenti}}\end{casi}}}$.

Questa funzione può essere calcolata dal seguente programma LOOP, che imposta la variabile su . ${\displaystyle x_{0}}$${\displaystyle pred(x_{1})}$

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

Ampliato, questo è il programma

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

Questo programma può essere utilizzato come subroutine in altri programmi LOOP. La sintassi LOOP può essere estesa con la seguente istruzione, equivalente a chiamare quanto sopra come subroutine:

x0 := x1 ∸ 1

Osservazione : Ancora una volta bisogna pensare agli effetti collaterali. Il programma predecessore modifica la variabile x ₂ , che potrebbe essere utilizzata altrove. Per espandere l'istruzione x ₀  := x ₁ ∸ 1, si potrebbero inizializzare le variabili x _n , x _n+1 e x _n+2 (per un n abbastanza grande) rispettivamente a 0, x ₁ e 0, eseguire il codice su queste variabili e copia il risultato (x _n ) in x ₀ . Un compilatore può farlo.

Sottrazione di cut-off

Se nel programma 'addizione' sopra il secondo ciclo decrementa x ₀ invece di incrementare, il programma calcola la differenza (taglia a 0) delle variabili e . ${\displaystyle x_{1}}$${\displaystyle x_{2}}$

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

Come prima, possiamo estendere la sintassi LOOP con l'istruzione:

x0 := x1 ∸ x2

Se poi altro

Un'istruzione if-then-else con 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;

Guarda anche

• μ-funzione ricorsiva
• funzione ricorsiva primitiva
• BlooP e FlooP

Note e riferimenti

Bibliografia

link esterno

• Ripeti, vai a e mentre