Teoria limbajului de programare (PLT ) este o secțiune a informaticii dedicată proiectării, analizei, caracterizării și clasificării limbajelor de programare și studiului caracteristicilor lor individuale [1] . Strâns legate de alte ramuri ale informaticii, rezultatele teoriei sunt utilizate în matematică , în ingineria software și în lingvistică .
Într-un fel, istoria teoriei limbajului de programare precede chiar și dezvoltarea limbajelor de programare în sine. În special, λ-calcul , dezvoltat de Alonzo Church și Stephen Kleene în anii 1930, este de fapt primul limbaj de programare, chiar dacă a fost destinat mai mult pentru probleme teoretice de calculabilitate decât ca instrument pentru programatori; multe limbaje de programare funcționale moderne sunt variante ale calculului λ. Istoria ulterioară a teoriei este strâns împletită cu istoria limbajelor de programare , în timp ce în cadrul cercetării teoretice au fost create noi paradigme , construcții și metode, iar rezultatele implementării lor în limbaje practice de programare au oferit feedback pentru dezvoltarea teorie.
Primul limbaj de programare care a fost inventat pentru a fi utilizat într-un computer electronic existent este Plankalkulul lui Konrad Zuse , dar nu și-a câștigat faima în rândul contemporanilor (a fost studiat abia în anii 1970 și implementat în anii 1990). Primul limbaj de programare cunoscut și de succes a fost Fortran (1954-1957), dezvoltat de o echipă de cercetători IBM condusă de John Backus . Succesul Fortran a dus la formarea unui comitet de oameni de știință care au încercat să dezvolte un limbaj informatic „universal”; rezultatul efortului lor a fost Algol-58 . În paralel , John McCarthy de la MIT a dezvoltat limbajul de programare Lisp (bazat pe λ-calcul), care este primul limbaj de succes cu un cadru teoretic dezvoltat academic. Anii 1950 includ dezvoltarea ierarhiei Chomsky , care a influențat direct teoria limbajelor de programare.
În 1964, Peter Landin a implementat pentru prima dată o variantă a calculului λ care ar putea fi folosită pentru a modela limbaje de programare ( mașina SECD și operatorul J , în esență un tip de continuare ). În 1966 Landin a dezvoltat limbajul abstract de programare ISWIM .
În 1966, Corrado Böhm și Giuseppe Jacopini ( italianul Giuseppe Jackopini ) au demonstrat o teoremă , conform căreia un algoritm poate fi convertit într-o formă care folosește doar trei structuri de control - secvențială, ramificată și buclă, ulterior acest rezultat a devenit fundamentul teoretic al structurii structurate. programare . Creat de Ole-Johan Dahl și Kristen Nygor în 1967, limbajul Simula a dezvoltat ceea ce se crede a fi primul exemplu de limbaj de programare orientat pe obiecte și a introdus noțiunea de corutine . O etapă importantă în dezvoltarea direcției a fost cursul de curs Concepte fundamentale în limbaje de programare de Christopher Strachey , lansat în 1967 , unde, pe lângă sistematizarea cunoștințelor despre teoria limbajelor de programare, conceptul de polimorfism a fost profund studiat . O contribuție semnificativă la dezvoltarea conceptului de tipuri în limbaje de programare este asociată cu munca din 1969 a lui Roger Hindley , ale cărei rezultate au dus la un algoritm de inferență de tip generalizat .
În 1969, Tony Hoare a dezvoltat logica lui Hoare , primul exemplu de semantică axiomatică pentru limbaje de programare care oferă verificarea formală a codului programului. Semantica denotațională a fost dezvoltată în 1970 de Dana Scott .
În 1972, au fost create paradigma de programare logică și limbajul Prolog , în care programul constă direct dintr-un set de clauze Horn . Un alt domeniu de interes pentru teoreticienii limbajului de programare la începutul anilor 1970 a fost introducerea tipurilor de date abstracte la nivelul constructelor de limbaj, Clu (1974, Barbara Liskov ) considerat a fi primul astfel de limbaj .
O etapă importantă pe calea formării paradigmei de programare funcțională a fost dezvoltarea independentă de către Girard ( fr. Jean-Yves Girard ; 1971) și Reynolds ( ing. John C. Reynolds ; 1974) a sistemului F - un tip λ -calcul de ordinul doi, care oferă capacitatea de a construi termeni care depind de din tipuri. De asemenea, o contribuție semnificativă la dezvoltarea programării funcționale la mijlocul anilor 1970 a avut-o dezvoltatorii limbajului de programare Scheme , un dialect Lisp care includea sferă lexicală , un spațiu de nume unificat și elemente din modelul actorului , inclusiv continuări . Creșterea interesului larg răspândit pentru programarea funcțională este asociată cu prelegerea Turing a creatorului Fortran Backus din 1977, în care a analizat critic starea limbajelor de programare care erau populare la acea vreme și au ajuns la paradigma funcțională.
În 1980, William Alvin Howard , referindu-se la scrierile logicianului Haskell Curry din anii 1950, a identificat o corespondență structurală între programele de calculator și dovezile matematice, care a devenit cunoscută sub numele de izomorfismul Curry-Howard și a devenit baza teoretică a clasei automate . limbaje de probă .
În prima jumătate a anilor 1980, s-a acordat o atenție considerabilă cercetărilor privind implementarea paralelismului în limbaje de programare și dezvoltării variantelor de calcul al proceselor : a fost creat calculul sistemelor care interacționează ( Milner , 1980), limbajul de interacțiune. procese secvențiale ( Hoare , 1985 ) s- a format în sfârșit modelul actoric Hewitt ( ing . ) Carl Hewitt
Lansarea limbajului Miranda în 1985 a alimentat interesul academic pentru limbajele de programare funcționale pur și lene , ceea ce a dus la formarea unui comitet pentru a defini un standard deschis pentru un astfel de limbaj, rezultând versiunea Haskell 1.0 în 1990 .
În 1986, ca parte a lucrării de creare a limbajului Eiffel , a fost creată paradigma de programare prin contract ( Bertrand Meyer , 1986).
Teoria studiază aspectele limbajelor de programare, pe cât posibil, ca un set, folosind ca exemplu unul sau altul limbaj particular, dar în același timp folosind mijloace de un nivel suficient de înalt de generalitate încât rezultatele să poată fi aplicate la o anumită clasă de limbi. Adesea, în evoluțiile teoretice, se creează un limbaj de programare specializat, „ academic ”, care, dintr-un motiv sau altul, nu este potrivit pentru implementarea practică, dar demonstrează anumite rezultate teoretice, care sunt ulterior aplicate limbajelor utilizate în industrie. Pentru cercetarea teoretică, sunt folosite instrumentele de bază ale matematicii și logicii matematice , inclusiv teoria mulțimilor , teoria modelelor , teoria computabilității , precum și secțiuni abstracte precum teoria categoriilor , algebra universală , teoria grafurilor și depinde în mod semnificativ de rezultatele domenii aplicate, inclusiv teoria complexității, calcul , teoria codificării .
Semantica formală este o descriere atât de formală a limbajelor de programare care permite cuiva să interpreteze matematic „sensul” unui program de calculator scris în limba respectivă. Există trei abordări generale pentru a descrie semantica unui limbaj de programare: semantica denotațională , semantica operațională și semantica axiomatică .
Teoria tipurilor este studiul sistemelor de tip ; este „o metodă sintactică obedientă pentru a demonstra defectele în comportamentul unui anumit program prin clasificarea frazelor după nivelul valorilor pe care le calculează” [2] . Multe limbaje de programare diferă prin caracteristicile sistemelor lor de tip.
Analiza programului este problema generală a examinării unui program și a stabilirii principalelor caracteristici (cum ar fi absența erorilor în program).
Conversia programului este procesul de conversie a unui program dintr-o formă (limbă) în altă formă.
Analiza comparativă a limbajului de programare urmărește să clasifice limbajele de programare în diferite tipuri, în funcție de caracteristicile acestora; ideile și conceptele generale ale limbajelor de programare sunt cunoscute ca paradigme de programare .
Programarea generică este o paradigmă de programare care constă într-o astfel de descriere a datelor și a algoritmilor care pot fi aplicați diferitelor tipuri de date fără a modifica această descriere în sine.
Metaprogramarea este generarea de programe de ordin superior care, atunci când sunt executate, produc programe (poate într-o altă limbă sau într-un subset al limbajului original) ca rezultat al muncii lor.
Limbile specifice domeniului sunt limbi care sunt concepute pentru a rezolva eficient problemele dintr-un anumit domeniu.
Teoria compilatorului este teoria scrierii compilatorilor (sau mai general a traducătorilor); programe care traduc un program scris într-o limbă într-o altă formă.
Acțiunile compilatorului sunt în mod tradițional împărțite în:
Sistemele de execuție se referă la dezvoltarea timpilor de execuție a limbajului de programare și a componentelor acestora, inclusiv mașinile virtuale , colectarea gunoiului și interfețele funcționale externe