A programozási nyelvelmélet (PLT ) a számítástechnikának egy olyan része , amely a programozási nyelvek tervezésével, elemzésével, jellemzésével és osztályozásával , valamint egyedi jellemzőik tanulmányozásával foglalkozik [1] . A számítástechnika más ágaihoz szorosan kapcsolódó elmélet eredményeit a matematikában , a szoftverfejlesztésben és a nyelvészetben hasznosítják .
Bizonyos értelemben a programozási nyelvelmélet története még maguknak a programozási nyelveknek a fejlődését is megelőzi. Konkrétan az Alonzo Church és Stephen Kleene által az 1930-as években kifejlesztett λ-számítás valójában az első programozási nyelv, jóllehet inkább a kiszámíthatóság elméleti kérdéseire szánták, semmint programozói eszköznek; sok modern funkcionális programozási nyelv a λ-kalkulus változata. Az elmélet további története szorosan összefonódik a programozási nyelvek történetével , miközben az elméleti kutatások keretében új paradigmák , konstrukciók és módszerek születtek, amelyek gyakorlati programozási nyelvekben való megvalósításának eredményei visszajelzést adtak a programozási nyelvek fejlődéséhez. elmélet.
Az első programozási nyelv, amelyet egy létező elektronikus számítógépben való használatra találtak ki, Konrad Zuse Plankalkulja , de nem szerzett hírnevet a kortársak körében (csak az 1970-es években tanulmányozták, és az 1990-es években vezették be). Az első széles körben ismert és sikeres programozási nyelv a Fortran (1954-1957) volt, amelyet John Backus vezette IBM kutatócsoport fejlesztett ki . A Fortran sikere egy tudósokból álló bizottság megalakulásához vezetett, akik megpróbáltak egy "univerzális" számítógépes nyelvet kifejleszteni; erőfeszítésük eredménye az Algol-58 . Ezzel párhuzamosan John McCarthy , az MIT -től kifejlesztette a Lisp programozási nyelvet (λ-számítás alapján), amely az első sikeres nyelv akadémiailag kidolgozott elméleti kerettel. Az 1950-es évekhez tartozik a Chomsky-hierarchia kialakulása , amely közvetlenül befolyásolta a programozási nyelvek elméletét.
1964-ben Peter Landin először implementálta a λ-számítás egy olyan változatát, amely programozási nyelvek modellezésére használható (az SECD gép és a J-operátor , lényegében egyfajta folytatás ). 1966-ban Landin kifejlesztette az ISWIM absztrakt programozási nyelvet .
1966- ban Corrado Böhm és Giuseppe Jacopini ( olasz Giuseppe Jackopini ) bebizonyítottak egy tételt , amely szerint egy algoritmus olyan formára alakítható, amely csak három vezérlőstruktúrát - szekvenciális, elágazó és hurok - használ, később ez az eredmény lett a strukturált elméleti alapja. programozás . Az Ole-Johan Dahl és Kristen Nygor által 1967-ben létrehozott Simula nyelv kifejlesztette az objektum-orientált programozási nyelv első példáját, és bevezette a korutin fogalmát . Az irányvonal fejlődésének fontos mérföldköve volt Christopher Strachey 1967 - ben kiadott Fundamental Concepts in Programming Languages előadása , ahol a programozási nyelvelméleti ismeretek rendszerezése mellett a polimorfizmus fogalma is megjelent. mélyen tanulmányozott . Jelentős hozzájárulást jelent a programozási nyelvekben a típusok fogalmának kidolgozásához Roger Hindley 1969-es munkája , amelynek eredményei egy általánosított típuskövetkeztető algoritmust eredményeztek .
1969-ben Tony Hoare kifejlesztette a Hoare-féle logikát , amely a programozási nyelvek axiomatikus szemantikájának első példája, amely a programkód formális ellenőrzését biztosítja. A denotációs szemantikát Dana Scott fejlesztette ki 1970-ben .
1972-ben létrehozták a logikai programozási paradigmát és a Prolog nyelvet , amelyben a program közvetlenül Horn-klózok halmazából áll . Az 1970-es évek elején a programozási nyelv teoretikusainak másik érdeklődési területe az absztrakt adattípusok bevezetése volt a nyelvi konstrukciók szintjén, és a Clu (1974, Barbara Liskov ) volt az első ilyen nyelv .
A funkcionális programozási paradigma kialakulásához vezető úton fontos mérföldkő volt, hogy Girard ( fr. Jean-Yves Girard ; 1971) és Reynolds ( angol. John C. Reynolds ; 1974) egymástól függetlenül kifejlesztette az F rendszert - a tipizált λ-t. -másodrendű kalkulus, amely lehetőséget biztosít a típusoktól függő kifejezések összeállítására. Az 1970-es évek közepén jelentős mértékben hozzájárultak a funkcionális programozás fejlesztéséhez a Scheme programozási nyelv, a lexikális hatókört , egységes névteret és az aktormodell elemeit tartalmazó Lisp dialektus fejlesztői , beleértve a folytatásokat is . A funkcionális programozás iránti széleskörű érdeklődés a Fortran Backus alkotójának 1977-es Turing-előadásához köthető , amelyben kritikusan elemezte az akkoriban népszerű programozási nyelvek állapotát, és eljutott a funkcionális paradigmáig.
1980-ban William Alvin Howard Haskell Curry logikus 1950-es írásaira hivatkozva strukturális megfelelést azonosított a számítógépes programok és a matematikai bizonyítások között, amely Curry-Howard izomorfizmus néven vált ismertté, és az automatika osztályának elméleti alapjává vált. bizonyító nyelvek .
Az 1980-as évek első felében jelentős figyelmet fordítottak a párhuzamosság programozási nyelvekben való megvalósításának kutatására és a folyamatkalkulus változatainak kidolgozására : megalkották az kölcsönható rendszerek kalkulusát ( Milner , 1980), az interakció nyelvét. szekvenciális folyamatok ( Hoare , 1985), végül kialakult a Hewitt színészmodell ( eng. ) Carl Hewitt
A Miranda nyelv 1985-ös kiadása felkeltette az akadémikus érdeklődést a lusta , tisztán funkcionális programozási nyelvek iránt, aminek eredményeként egy bizottság alakult egy ilyen nyelv nyílt szabványának meghatározására, aminek eredményeként 1990-ben a Haskell 1.0-s verziója készült el .
1986-ban, az Eiffel -nyelv létrehozására irányuló munka részeként létrehozták a szerződéses programozási paradigmát ( Bertrand Meyer , 1986).
Az elmélet a programozási nyelvek szempontjait, amennyire csak lehetséges, halmazként vizsgálja, egyik vagy másik nyelvet példaként használva, ugyanakkor kellően magas szintű általánosságot használva ahhoz, hogy az eredményeket a programozási nyelvek valamelyik osztályára alkalmazni lehessen. nyelvek. Az elméleti fejlesztések során gyakran valamilyen speciális, „ akadémiai ” programozási nyelvet hoznak létre, amely ilyen vagy olyan okból nem alkalmas a gyakorlati megvalósításra, de bizonyos elméleti eredményeket mutat fel, amelyeket utólag alkalmaznak a programban használt nyelvekre. ipar. Az elméleti kutatáshoz a matematika és a matematikai logika alapjainak eszköztárát használják , beleértve a halmazelméletet , a modellelméletet , a kiszámíthatóságelméletet , valamint az olyan absztrakt szakaszokat, mint a kategóriaelmélet , az univerzális algebra , a gráfelmélet , és jelentős mértékben függnek az eredményektől. alkalmazott területek, beleértve a komplexitáselmélet számítástechnikát , kódoláselméletet .
A formális szemantika a programozási nyelvek olyan formális leírása, amely lehetővé teszi az adott nyelven írt számítógépes program „jelentésének” matematikai értelmezését. Három általános megközelítés létezik a programozási nyelv szemantikájának leírására: denotációs szemantika , műveleti szemantika és axiomatikus szemantika .
A típuselmélet a típusrendszerek tanulmányozása ; "egy engedelmes szintaktikai módszer egy adott program viselkedésének hibáinak bizonyítására a kifejezések besorolásával az általuk kiszámított értékek szintje szerint" [2] . Sok programozási nyelv különbözik típusrendszereik jellemzőiben.
A programelemzés a program vizsgálatának és a főbb jellemzők meghatározásának általános problémája (például a hibák hiánya a programban).
A programkonverzió a program egyik formáról (nyelvről) egy másik formára való konvertálásának folyamata.
Az összehasonlító programozási nyelv elemzés célja a programozási nyelvek különböző típusokba sorolása, jellemzőiktől függően; a programozási nyelvek általános elképzelései és koncepciói programozási paradigmákként ismertek .
Az általános programozás egy olyan programozási paradigma , amely az adatok és algoritmusok olyan leírásából áll, amelyek különféle típusú adatokra alkalmazhatók anélkül, hogy magát a leírást megváltoztatnák.
A metaprogramozás magasabb rendű programok generálása, amelyek végrehajtása során munkájuk eredményeként (talán egy másik nyelven vagy az eredeti nyelv egy részhalmazán) programokat állítanak elő.
A tartományspecifikus nyelvek olyan nyelvek, amelyeket arra terveztek, hogy hatékonyan oldják meg a problémákat egy adott témakörben.
A fordítóelmélet a fordítók (vagy általánosabban fordítók) írásának elmélete; olyan programok, amelyek az egyik nyelven írt programot egy másik formára fordítják.
A fordítóműveletek hagyományosan a következőkre oszlanak:
A futásidejű rendszerek a programozási nyelv futtatókörnyezetének és összetevőinek fejlesztésére utalnak, beleértve a virtuális gépeket , a szemétgyűjtőt és a külső funkcionális interfészeket