L (linguaggio)

Il linguaggio L è un linguaggio di programmazione ideato da Albert R. Meyer e da Dennis Ritchie che calcola solamente funzioni ricorsive primitive.[1] I programmi scritti in linguaggio L prendono il nome di "programmi Loop" (Loop programs).

IstruzioniModifica

Il linguaggio L prevede cinque tipi di istruzioni:

  1. azzeramento: V = 0
  2. incremento: V = V + 1
  3. assegnazione: V = V'
  4. ciclo: LOOP V
  5. termine del ciclo: END

Le istruzioni 4 e 5 si comportano come le parentesi.

Un blocco di codice inserito tra un LOOP-END viene eseguito esattamente il numero di volte del valore assunto dalla variabile V all'inizio del ciclo, indipendentemente dal fatto che tale valore possa variare nel corso dell'iterazione. Questo assicura la terminazione dei programmi Loop.

Profondità di nidificazioneModifica

È possibile inserire cicli all'interno dei blocchi LOOP-END. Un programma che presenta n cicli annidati ha profondità n ed appartiene alla classe  . Un programma che utilizza solo le istruzioni 1, 2 e 3 ha profondità 0 ed appartiene alla classe  .

Se   è la classe delle funzioni calcolabili dai programmi appartenenti alla classe  ,   è la classe delle funzioni calcolabili in L.

Funzioni ricorsive primitiveModifica

Il linguaggio L calcola tutte le funzioni ricorsive primitive essendo le funzioni base calcolabili utilizzando programmi di profondità 0 ed essendo la classe   chiusa per composizione e ricorsione.

Tempo di esecuzioneModifica

Il tempo di esecuzione di un programma Loop è il numero d'istruzioni eseguite per calcolare la funzione. La funzione   di un programma P   appartiene a  .

NoteModifica

  1. ^ (EN) Eric W. Weisstein, Primitive Recursive Function, in MathWorld, Wolfram Research.

BibliografiaModifica

  • (EN) Albert R. Mayer, Ritchie Dennis M., The complexity of loop programs (PDF), in ACM Annual Conference/Annual Meeting, Proceedings of the 1967 22nd national conference, gennaio 1967, pp. 465 - 469. URL consultato il 2 ottobre 2014 (archiviato dall'url originale il 6 marzo 2016).
  • Martin D. Davis, Elaine J. Weyuker, Loop Programs, in Computability, Complexity, and Languages, Londra, Academic Press, 1983.

Voci correlateModifica

  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica