L (limba)

Limbajul L este un limbaj de programare conceput de Albert R. Meyer și Dennis Ritchie care calculează doar funcții recursive primitive . ^[1] Programele scrise în limbaj L se numesc „programe de buclă”.

Instrucțiuni

Limba L are cinci tipuri de instrucțiuni:

zero: V = 0
increment: V = V + 1
misiune : V = V '
bucla : LOOP V
sfârșitul ciclului: END

Instrucțiunile 4 și 5 se comportă ca niște paranteze .

Un bloc de cod inserat între un LOOP-END este executat exact numărul de ori al valorii asumate de variabila V la începutul buclei, indiferent dacă această valoare se poate modifica în timpul iterației. Acest lucru asigură încetarea programelor de buclă.

Adâncimea de cuibărire

Este posibil să introduceți bucle în interiorul blocurilor LOOP-END. Un program care are n bucle imbricate are adâncimea n și aparține clasei $L_{n}$ ${\ displaystyle L_ {n}}$ $L_ {n}$ . Un program care folosește doar instrucțiunile 1, 2 și 3 are adâncimea 0 și aparține clasei $L_{0}$ ${\ displaystyle L_ {0}}$ $L_ {0}$ .

De sine ${\mathcal {L}}_{n}$ ${\ displaystyle {\ mathcal {L}} _ {n}}$ ${\ mathcal {L}} _ {n}$ este clasa de funcții care poate fi calculată de programele aparținând clasei $L_{n}$ ${\ displaystyle L_ {n}}$ $L_ {n}$ , ${\mathcal {L}}=\bigcup _{n=_{0}}^{\infty }{\mathcal {L}}_{n}$ ${\ displaystyle {\ mathcal {L}} = \ bigcup _ {n = _ {0}} ^ {\ infty} {\ mathcal {L}} _ {n}}$ ${\ mathcal {L}} = \ bigcup _ {{n = _ {0}}} ^ {{\ infty}} {\ mathcal {L}} _ {n}$ este clasa funcțiilor calculabile în L.

Funcții recursive primitive

Limbajul L calculează toate funcțiile recursive primitive fiind funcțiile de bază calculabile utilizând programe de adâncime 0 și fiind clasa ${\mathcal {L}}$ ${\ displaystyle {\ mathcal {L}}}$ $\ mathcal {L}$ închis prin compoziție și recursivitate .

Timpul de execuție

Timpul de execuție al unui program Loop este numărul de instrucțiuni executate pentru a calcula funcția. Functia $T_{P}(x_{1},\ldots ,x_{n})$ ${\ displaystyle T_ {P} (x_ {1}, \ ldots, x_ {n})}$ $T_ {P} (x_ {1}, \ ldots, x_ {n})$ a unui program P. $\in L_{n}$ ${\ displaystyle \ în L_ {n}}$ $\ în L_ {n}$ aparține lui ${\mathcal {L}}_{n}$ ${\ displaystyle {\ mathcal {L}} _ {n}}$ ${\ mathcal {L}} _ {n}$ .

Notă

^ (EN) Eric W. Weisstein, Funcția recursivă primitivă , în MathWorld , Wolfram Research.

Bibliografie

( EN ) Albert R. Mayer, Ritchie Dennis M. , Complexitatea programelor de buclă ( PDF ), în ACM Annual Conference / Annual Meeting , Proceedings of the 1967 22 national conference, ianuarie 1967, pp. 465 - 469. Adus la 2 octombrie 2014 (arhivat din original la 6 martie 2016) .
Martin D. Davis , Elaine J. Weyuker, Loop Programs , in Computability, Complexity, and Languages , Londra, Academic Press, 1983.

Elemente conexe

Portal IT : accesați intrările Wikipedia care se ocupă cu IT

[1] (EN) Eric W. Weisstein, Funcția recursivă primitivă , în MathWorld , Wolfram Research.

[1]