Programozási nyelvelmélet - Programming language theory
A programozási nyelv elmélete ( PLT ) a számítástechnika olyan ága, amely foglalkozik a programozási nyelvek néven ismert formális nyelvek és azok egyedi jellemzőinek tervezésével, megvalósításával, elemzésével, jellemzésével és osztályozásával . A számítástechnika tudományterületébe tartozik, mind a matematikától , mind a szoftvertechnikától , a nyelvtudománytól , sőt a kognitív természettől függ és befolyásolja azokat . A számítástechnika elismert ágává és aktív kutatási területté vált, eredményeit számos, a PLT-nek szentelt folyóiratban , valamint általános számítástechnikai és mérnöki publikációkban publikálták.
Történelem
Bizonyos szempontból a programozási nyelv elméletének története még a programozási nyelvek fejlődését is megelőzi. A lambda-kalkulus által kifejlesztett Alonzo Church és Stephen Cole Kleene 1930, megítélése szerint bizonyos, hogy a világ első programozási nyelv, bár ez volt a célja, hogy a modell számítási ahelyett, hogy egy eszközt programozók írják algoritmusok számítógépes rendszer . Számos modern funkcionális programozási nyelvről leírták, hogy "vékony burkolatot" biztosítanak a lambda számításán, és sokukat egyszerűen leírják annak szempontjából.
Az első programozási nyelv, amelyet kitaláltak, a Plankalkül volt, amelyet Konrad Zuse tervezett az 1940-es években, de 1972-ig nyilvánosan nem ismert (és csak 1998-ban hajtották végre). Az első széles körben ismert és sikeres magas szintű programozási nyelv a Fortran volt , amelyet 1954 és 1957 között fejlesztett ki az IBM kutatói csoport John Backus vezetésével . A FORTRAN sikere egy tudósok bizottságának megalakulásához vezetett egy "egyetemes" számítógépes nyelv kifejlesztésére; erőfeszítésük eredménye az ALGOL 58 volt . Külön-külön, John McCarthy, az MIT fejlesztette ki a Lisp-t , az első nyelvet, amelynek eredete az egyetemeken sikeres volt. E kezdeti erőfeszítések sikerével a programozási nyelvek az 1960-as években és azon túl is aktív kutatási témává váltak.
Néhány további fontos esemény a programozási nyelvelmélet történetében azóta:
1950-es évek
- Noam Chomsky kidolgozta a Chomsky hierarchiát a nyelvészet területén, egy olyan felfedezés, amely közvetlenül befolyásolta a programozási nyelv elméletét és a számítástechnika egyéb ágait.
1960-as évek
- A szimulai nyelvet Ole-Johan Dahl és Kristen Nygaard fejlesztette ki ; széles körben az objektum-orientált programozási nyelv első példájának tekintik ; Simula bevezette a koroutin fogalmát is .
- 1964-ben Peter Landin volt az első, aki rájött, hogy Church lambda számításával programozási nyelvek modellezhetők. Bemutatja a SECD gépet, amely "értelmezi" a lambda kifejezéseket.
- 1965-ben Landin bemutatta a J operátort , lényegében a folytatás egyik formáját .
- 1966-ban Landin A következő 700 programozási nyelv című cikkében bemutatja az ISWIM-et , egy absztrakt számítógépes programozási nyelvet . Hatással van a Haskell programozási nyelvhez vezető nyelvek tervezésére .
- 1966-ban Corrado Böhm bevezette a CUCH (Curry-Church) programozási nyelvet .
- 1967-ben Christopher Strachey közzéteszi az Alapfogalmak a programozási nyelvekben című előadásjegyzetek halmazát , bemutatva az R-értékeket , az L-értékeket , a parametrikus polimorfizmust és az ad hoc polimorfizmust .
- 1969-ben J. Roger Hindley publikálja az objektum fő típus-sémáját a kombinációs logikában , később a Hindley – Milner típusú következtetési algoritmusba általánosítva.
- 1969-ben Tony Hoare bevezeti a Hoare logikát , az axiomatikus szemantika egyik formáját .
- 1969-ben William Alvin Howard megfigyelte, hogy a "magas szintű" bizonyítási rendszert , amelyet természetes dedukciónak neveznek, intuíciós változatában közvetlenül értelmezhetjük, mint a lambda calculus néven ismert számítási modell tipizált változatát . Ez Curry – Howard levelezés néven vált ismertté .
1970-es évek
- 1970-ben Dana Scott először publikálja a denotációs szemantikáról szóló munkáját .
- 1972- ben kifejlesztették a logikai programozást és a Prolog- ot, ezáltal lehetővé téve a számítógépes programok matematikai logikaként való kifejezést.
- A Xerox PARC tudóscsoportja, Alan Kay vezetésével fejleszti a Smalltalk nevű objektum-orientált nyelvet, amely széles körben ismert innovatív fejlesztési környezetéről.
- 1974-ben John C. Reynolds felfedezi az F rendszert . Jean-Yves Girard matematikai logikus már 1971-ben felfedezte .
- Gerald Jay Sussman és Guy Steele 1975-től fejlesztik a Scheme programozási nyelvet , egy lisp dialektust, amely magában foglalja a lexikális hatókört , az egységes névteret és a színész modell elemeit, beleértve az első osztályú folytatásokat .
- Backus az 1977-es Turing-díj előadásán felmérte az ipari nyelvek jelenlegi helyzetét, és javaslatot tett egy új programozási nyelv osztályra, amelyet ma funkció-szintű programozási nyelvként ismerünk .
- 1977-ben Gordon Plotkin bevezeti a Computing Computing Funkciók programozását , egy absztrakt tipizált funkcionális nyelvet.
- 1978-ban Robin Milner bevezeti a Hindley-Milner típusú következtetési algoritmust az ML . A típuselméletet diszciplinaként alkalmazták a programozási nyelveken, ez az alkalmazás az évek során a típuselmélet óriási fejlődéséhez vezetett.
1980-as évek
- 1981-ben Gordon Plotkin kiadja a strukturált operatív szemantikáról szóló cikkét .
- Gilles Kahn 1988-ban publikálta a természetes szemantikáról szóló cikkét .
- Ott alakult folyamat calculi , mint például a Calculus kommunikációs rendszerek a Robin Milner , és a kommunikáció szekvenciális folyamatok modellje CAR Hoare , valamint a hasonló modellek konkurencia, mint például a színész modell a Carl Hewitt .
- 1985-ben a Miranda kiadása tudományos érdeklődést váltott ki a lusta értékű tiszta funkcionális programozási nyelvek iránt. A nyílt szabvány meghatározására bizottságot hoztak létre, amelynek eredményeként 1990-ben megjelent a Haskell 1.0 szabvány.
- Bertrand Meyer létrehozta a Design by method módszertant és beépítette az Eiffel programozási nyelvbe .
1990-es évek
- Gregor Kiczales , Jim Des Rivieres és Daniel G. Bobrow kiadta a The Art of the Metaobject Protocol című könyvet .
- Eugenio Moggi és Philip Wadler bemutatták a monádok használatát a funkcionális programozási nyelveken írt programok strukturálásában .
Számos olyan terület létezik, amelyek vagy a programozási nyelv elméletén belül találhatók, vagy amelyek mélyreható hatást gyakorolnak rá; ezek közül sok jelentős átfedésben van. Ezenkívül a PLT a matematika számos más ágát is felhasználja , beleértve a kiszámíthatóság elméletét , a kategóriaelméletet és a halmazelméletet .
Formális szemantika
A formális szemantika a számítógépes programok és a programozási nyelvek viselkedésének formális meghatározása. A számítógépes program szemantikájának vagy "jelentésének" leírására három általános megközelítés a denotációs , az operatív és az axiomatikus szemantika .
Típuselmélet
A típuselmélet a típusú rendszerek tanulmányozása ; amelyek "kezelhető szintaktikai módszerek bizonyos programmagatartások hiányának bizonyítására azáltal, hogy a kifejezéseket az általuk kiszámított értékek szerint osztályozzák." Számos programozási nyelvet megkülönböztetnek a típusrendszereik jellemzői.
Programelemzés és átalakítás
A programelemzés a program megvizsgálásának és a legfontosabb jellemzők (például a programhibák osztályainak hiánya) meghatározásának általános problémája . A programtranszformáció az a folyamat, amikor a programot egy formában (nyelven) átalakítják egy másik formává.
Összehasonlító programozási nyelv elemzése
Az összehasonlító programozási nyelv elemzés arra törekszik, hogy a programozási nyelveket jellemzőik alapján különböző típusokba sorolja; a programozási nyelvek széles kategóriáit gyakran programozási paradigmának nevezik .
Általános és metaprogramozás
A metaprogramozás a magasabb rendű programok generálása, amelyek végrehajtásuk eredményeként programokat hoznak létre (esetleg egy másik nyelven, vagy az eredeti nyelv egy részhalmazában).
Tartományspecifikus nyelvek
A tartományspecifikus nyelvek olyan nyelvek, amelyek a tartomány egy adott részének problémáinak hatékony megoldására készültek.
Fordító szerkesztése
A fordítóelmélet a fordítók (vagy általánosabban a fordítók ) írásának elmélete ; olyan programok, amelyek az egyik nyelven írt programot más formába fordítják. A fordító műveletei hagyományosan szintaxis elemzésre ( szkennelés és elemzés ), szemantikai elemzésre (a program tennivalójának meghatározása), optimalizálásra (a program teljesítményének javítására, ahogyan azt néhány mutató mutatja; jellemzően végrehajtási sebesség) és kódgenerálásra bontják fel. (egyenértékű program létrehozása és kimenete valamilyen célnyelven; gyakran egy CPU utasításkészlete ).
Futásidejű rendszerek
A futásidejű rendszerek a programozási nyelv futásidejű környezeteinek és azok összetevőinek fejlesztésére utalnak , ideértve a virtuális gépeket , a szemétszállítást és az idegen funkciós interfészeket .
Folyóiratok, publikációk és konferenciák
A konferenciák az elsődleges helyek a kutatások bemutatására a programozási nyelvekben. A legismertebb konferenciák a Symposium on Principles of Programming Languages (POPL), a programozási nyelv tervezésének és megvalósításának (PLDI), a funkcionális programozással foglalkozó nemzetközi konferencia (ICFP), az objektumorientált programozásról, rendszerekről, nyelvekről és alkalmazásokról szóló nemzetközi konferencia ( OOPSLA) és a programozási nyelvek és operációs rendszerek építészeti támogatásáról szóló nemzetközi konferencia (ASPLOS) .
A PLT kutatásokat közzétevő jelentős folyóiratok között szerepel az ACM tranzakciók a programozási nyelveken és rendszereken (TOPLAS), a funkcionális programozás folyóirata (JFP), a funkcionális és logikai programozás folyóirata , valamint a magasabb rendű és szimbolikus számítás .
Lásd még
Hivatkozások
További irodalom
- Abadi, Martín és Cardelli, Luca . A tárgyak elmélete . Springer-Verlag.
- Michael JC Gordon . Programozási nyelvelmélet és megvalósítása . Prentice Hall.
- Gunter, Carl és Mitchell, John C. (szerk.). Az objektumorientált programozási nyelvek elméleti vonatkozásai: típusok, szemantika és nyelvtervezés . MIT Press.
- Harper, Robert . Gyakorlati alapok a nyelvek programozásához . Piszkozat verzió.
- Knuth, Donald E. (2003). Válogatott dolgozatok a számítógépes nyelveken . Stanford, Kalifornia: Nyelvi és Információs Tanulmányok Központja.
- Mitchell, John C. . A programozási nyelvek alapjai .
- Mitchell, John C. . Bevezetés a programozási nyelv elméletébe .
- O'Hearn, Peter. W. és Tennent, Robert. D. (1997). Algol-szerű nyelvek . Haladás az elméleti számítástechnikában. Birkhauser, Boston.
- Pierce, Benjamin C. (2002). Típusok és programozási nyelvek . MIT Press.
- Pierce, Benjamin C. Haladó témák a típusokban és a programozási nyelvekben .
- Pierce, Benjamin C. és mtsai. (2010). Szoftver alapítványok .
Külső linkek
- A Lambda the Ultimate , egy közösségi webnapló a szakmai beszélgetésekhez és a programozási nyelv elméletéről szóló dokumentumok tárháza.
- Nagy művek a programozási nyelvekben . Benjamin C. Pierce ( Pennsylvaniai Egyetem ) gyűjtötte össze .
- Klasszikus dokumentumok a programozási nyelvek és logika területén . Gyűjtötte: Karl Crary ( Carnegie Mellon Egyetem ).
- Programozási nyelvkutatás . Könyvtár: Mark Leone .
- Programozási nyelvelméleti szövegek online . Az Utrechti Egyetemen .
- λ-kalkulus: Akkor és Most by Dana S. Scott az ACM Turing Centenáriumi Ünnepség
- Nagy kihívások a programozási nyelvekben . Panel ülés a POPL 2009-ben.
