programming language theory

programming language theory (tsz. programming language theories)

1. (informatika) Programozási nyelvek elmélete (Programming Language Theory) a számítástudomány azon ága, amely a programnyelvek formális megfogalmazását, elemzését és megvalósítását vizsgálja. Célja, hogy megértsük, hogyan definiáljuk, hogyan értelmezzük és hogyan tervezünk nyelveket, valamint miként garantálható a programok helyessége, biztonsága és teljesítménye.

• Kontextus‐mentes grammatika (CFG): a nyelv szerkezetét írja le szabályokkal, például

  $${\displaystyle {\text{Expr}}\to {\text{Expr + Expr}}\mid {\text{Expr * Expr}}\mid {\text{(Expr)}}\mid {\text{num}}.}$$

• Lexikális elemzés: a forráskód karaktereit tokenekre bontjuk (azonosító, kulcsszó, literál, operátor).

• Operacionális szemantika: egy program végrehajtását lépésről lépésre leíró átmeneti rendszer—megadja, hogyan változik a futási állapot.
• Denotációs szemantika: minden nyelvi szerkezethez matematikai függvényt rendel a bemenet és a kimenet között.
• Axiomatizáló szemantika: Hoare‐logika pre‐ és post‐feltételekkel írja le, hogy egy utasítás milyen feltételek esetén teljesíti a specifikációt.

• Lambda‐kalkulus: a függvény­definíció és alkalmazás minimális formális rendszere.
  • Untyped λ‐calculus: csak absztrakció (${\textstyle \lambda x.M}$) és alkalmazás (${\textstyle M\ N}$).
  • Typed λ‐calculus: egyszerű típusok (${\textstyle A\to B}$), később dependens és polimorf típusok bővítik.
• Curry–Howard‐korrespondencia: a típus a logikai tétel, a program a bizonyítás; összehozza a típuselméletet és a programozást.

• Statikus típusellenőrzés: fordításkor, típusellenőrző algoritmussal eldöntjük, hogy a kód típushelyes-e (pl. ML, Haskell).
• Dinamikus típusellenőrzés: futásidőben ellenőrizzük a típusokat (pl. Python, JavaScript).
• Fejlett típusosztályok:
  • Paraméterezett (generikus) típusok: List<T>.
  • Adatfüggő típusok (dependens típusok): típusszinten használható értékparaméterek (Agda, Idris).
  • Alkategóriák: afffin, linear típusok erőforráskezeléshez.

• A típusellenőrzés formális leírása inferencia‐rendszerrel, mondjuk Judgement-ekkel és dedukciós szabályokkal:

  $${\displaystyle {\frac {\Gamma ,\,x:A\vdash e:B}{\Gamma \vdash (\lambda x.e):A\to B}}\quad {\frac {\Gamma \vdash f:A\to B\quad \Gamma \vdash a:A}{\Gamma \vdash f\,a:B}}}$$

• Type inference: például Hindley–Milner rendszer automatikusan kitalálja a kifejezés típusát ML‐ben.

• Köztes reprezentáció (IR): a compiler-front‐end által előállított absztrakt kód (pl. SSA-forma LLVM‐ben).
• Optimalizációs átírások: halhatatlan kód eltávolítása, konstanteszközlés, ciklus‐unrolling, Dead‐Code Elimination stb.
• Formális bizonyítás: egyes rendszerek (CompCert) garantálják, hogy az optimalizációk nem változtatják meg a program viselkedését.

• Műveletek hatásai (effects): állapotváltozások, I/O, kivételkezelés.
• Monádok (Haskell): hatások típusos és kompozíciós kerete.
• Effektrendszerek: algebrai effektusok és kezelők (algebraic effects), finomabb hatás‐kezelés.

1. Absztrakció legfelsőbb foka: magasabb szintű beépített szerkezetek (listák, generátorok, comprehensions).
2. Egyszerűségi elv (Simplicity): könnyen tanulható és megérthető.
3. Kibővíthetőség: makrók, plugin‐rendszer (Lisp makrók, Rust procedural macros).
4. Biztonság és hatékonyság: memória­biztonság (Rust ownership), típusbiztonság, futási sebesség.

• Konkurens és párhuzamos nyelvek: aktormodell (Erlang, Akka), CSP (Go csatornák).
• Verifikálható nyelvek: dependens típusos rendszerek, formálisan bizonyított futtatók (seL4).
• Domain Specific Languages (DSL): belső (embedded) és külső DSL‐ek, parser‐ és interpreter‐generálás.

A programozási nyelvek elmélete a nyelvek formális leírását (szintaxis, szemantika), típusrendszereket, hatáskezelést, valamint a fordítási és optimalizációs technikákat egyaránt magába foglalja. Alapját a lambda‐kalkulus, a formális szemantika és a típuselmélet adja, a gyakorlatban pedig a modern fordítók, tételbizonyító asszisztensek és DSL‐keretrendszerek építéséhez és fejlesztéséhez nyújt létfontosságú eszközöket.

• programming language theory - Szótár.net (en-hu)
• programming language theory - Sztaki (en-hu)
• programming language theory - Merriam–Webster
• programming language theory - Cambridge
• programming language theory - WordNet
• programming language theory - Яндекс (en-ru)
• programming language theory - Google (en-hu)
• programming language theory - Wikidata
• programming language theory - Wikipédia (angol)