Logikai és funkcionális programozás


Tartalomjegyzék:


Tematika

Deklaratív programozási nyelvek

Niklaus E. Wirth wikipédia link
Program = adatstruktúra + algoritmus
A programozási nyelveket fel tudjuk osztani imperatív és deklaratív nyelvekre. Az imperatív programozási nyelvek -- ilyen például a Pascal, C, Fortran -- esetében a számítógép által végrehajtott minden utasítást a programozónak kell megadnia. A deklaratív programok esetében "magasabb szintű" programokat írunk. Vagyis, az immár klasszikus szófordulattal élve, nem a feladat elvégzésének hogyan-jával törődünk, hanem azt programozzuk, hogy MIT szeretnénk a programmal elvégeztetni.
Egy klasszikus példa a faktoriális kiszámítására írt program. A program egy imperatív programnyelven, a C-ben a következő:
int fact(int n){int f=1; while(n>1)f*=n--; return f;}
Vegyük észre, hogy a programkód során specifikáljuk a program minden műveletét, beleértve azon változó(ka)t is, melyeket használunk a futtatás során.
A deklaratív programoknál a szabályt mondjuk meg:
fakt 0 = 1
fakt n | n>0 = n * fakt n-1
Ez utóbbi esetben a pusztán a definíciót mondjuk meg, az implementációt a programra bíztuk (a példa a CLEAN funkcionális programozási nyelvben íródott).
Ilyen programnyelveket általános feladatokra írni nehéz. A kurzus során két programozási paradigmával ismerkedünk, melyekkel jól-definiált feladatok osztályát lehet hatékonyan megoldani - azaz programozni.

Logikai programozás

A logikai programozás esetében a programokat relációkkal specifikáljuk. A program futása az logikai következtetésen alapszik.
Alternatív programozási paradigmák:
R. Kowalski
Algoritmus = Logika + Kontroll

J. A. Robinson
"A program egy logikai rendszer."
"A program futása -- a műveletek -- az ebben a rendszerben végzett dedukciók, következtetések."
A logikai programozás alapjai a tények és az ezeket jellemző szabályok, melyeket együttesen tudásbázisnak nevezünk.
A tényeket prologban a következőképp adjuk meg:
ferfi(adam).
ferfi(ferenc).
ferfi(peter).
ferfi(pali).
ferfi(endre).
%------------------
no(eva).
no(marika).
no(julia).
no(agnes).
%------------------
gyereke(ferenc,adam).
gyereke(ferenc,eva).
%
gyereke(marika,adam).
gyereke(marika,eva).
gyereke(peter,marika).
gyereke(peter,jozsef).
%
gyereke(julia,ferenc).
gyereke(julia,agnes).
%
gyereke(endre,julia).
gyereke(endre,pali).
A szabályokat:
nagyszulo(Unoka,Nagyszulo) :- gyereke(Unoka,Szulo) , gyereke(Szulo,Nagyszulo).
A fenti szabály jelentése a következő: Az "Unoka" akkor áll nagyszulo kapcsolatban a "Nagyszulo"vel, ha van egy "Szulo", akinek egyrészt gyereke az "Unoka", másrészt "Szulo" gyereke "Nagyszulo"-nek.

Tehát a :- a következtetés jele. Néhány további szabály:
apa(Apa) :- gyereke(_,Apa),ferfi(Apa).

anya(Anya) :- gyereke(_,Anya),no(Anya).
Programozás ebben a környezetben olyan lekérdezések megalkotása, melyek adott felhasználói kérdésre felelnek. Például keressük azon személyeket, melyeknek nincsenek ősei, azaz az adatbázisban nincsenek predikátum, mely szülőt rendel az illető személyhez (lásd első feladatcsoport).
Az előadásokhoz Ulle Endriss slide-jait használom. Lokális kópia: ITT.

Funkcionális programozás

A funkcionális programozásban minden entitás függvény. A program legfőbb jellemzője, hogy nincsenek benne változók - ez nagyon megkönnyíti az illető programozási nyelven írt programok helyességének a bizonyítását illetve megkönnyíti azt, hogy modulokból bizonyítottan helyes programokat rakjunk össze.
A prolog interpreterben egy predikátumot kielégítő változókat keresünk. A Clean-ben a rendszer a
Start = _fv_ _arg_1_ _arg_2_ ...
értékeli ki.
A funkcionális programozás alaptulajdonsága, hogy minden entitás függvény. Tehát egy programban előforduló konstansok is zéró-változós függvényként léteznek a Clean-en belül.
Az, hogy a változók nincsenek, azt jelenti, hogy egy "változó" sem változtatja értékét: minden változó, ha egyszer értéket rendeltünk hozzá, akkor az életciklusa alatt az értéke nem változik. Ez utóbbi tulajdonság nagyon megkönnyíti a funkcionális nyelvekben implementált programok helyességének a bizonyítását.
Mivel a funkcionális nyelven írt programok rendkívül megbízhatóak, a nagy kockázatú rendszereknél (pl. a párizsi metró irányító rendszerénél) használják nagy előszeretettel.
Mivel a rendszerben a változtatott értékeknek kell foglalni erőforrásokat, a funkcionális programnyelvek hatékony implementáláshoz szükség van egy "szemét-gyűjtőre", mely pl. a JAVA nyelvből ismert, mely a dinamikusan foglalt változókat képes kezelni.
A kurzus során a funkcionális programozás főbb jellemzőit ismertetjük - Horváth Zoltán jegyzeteire alapozva. Hangsúlyt helyezünk a hatékony programkódok írására, az algoritmika és a logikai struktúra érvényesítésére, melynek eredménye egy jobb minőségű kód, mely az aktuális programozási nyelvtől független.
Az előadások során írt rövidebb függvények, illetve egy korábbi feladatlap megtalálható alább:

Laborgyakorlatok

A feladatok programozásánál igyekezzünk tiszta és érthető komment-eket írni és értelmezhető neveket adni a predikátumoknak. Egy angol nyelvű útmutatót írt Michael Covington, a PDF formátum letölthető: PDF

Értékelés

A jegy a laborgyakorlatok és félév-végi laborvizsga eredménye.
A végső jegy:
A vizsgán való megjelenés feltétele a laborfeladatok leadása - ezek alatt a logikai és funkcionális feladatcsoportok leadását értem: mindegyik feladatcsoportból 60 százalékot.

Irodalomjegyzék

Logikai programozás:
  1. Ásványi Tibor - ELTE - logikai programozás oldalai: Prolog.
    Itt található egy Prolog jegyzet, melynek lokális kópiája letölthető: Asvanyi_Prolog.pdf
  2. Szeredi Péter és Benkő Tamás jegyzetei: PDF
  3. Hanák Péter, Szeredi Péter, Benkő Tamás előadásainak lokális kópiája: slide-ok
  4. Szeredi Péter és Benkő Tamás "Nagyhatékonyságú Logikai Programozás" jegyzetei: PDF
  5. Prolog könyv - letölthető Mike Spivey oldaláról, itt egy lokális másolata: PDF
  6. Learn Prolog Now! -- letölthető dokumentáció
  7. Ulle Endriss előadása.
    Egy angol nyelvű jegyzet lokális kópiája: PDF.
    Az előadások lokális kópiája: ITT.
  8. Ulf Nilson, Jan Maluszynski Prolog könyve.
    A lokális kópia: PDF.
Funkcionális programozás:
  1. Horvath Zoltan előadása
  2. Csörnyei Zoltán: Funkcionális programnyelvek implementációja, Budapest, 2010.
  3. Programnyelvek könyv fejezete
  4. CleanBook a Clean honlapjáról eredeti verzió a ITT
  5. CleanLangRep.2.1.pdf - a Clean nyelv specifikációja


File-ok

  1. Logikai programozás
    Az SWI-prolog kompilátor és interpreter. A program honlapja: http://www.swi-prolog.org. Install-programok:
    Hasznos file-ok:
    • Hasznos editor Windows alá a beépített emacs szerkesztő, melyet a prolog-ból tudunk hívni.
    • A linux alatt az (X)emacs használható editornak, a prolog.el file-al indíthatjuk a programot prolog módban.
  2. Funkcionális programozás
    A Clean funkcionális programozási nyelv a hollandiai Nijmegen egyetem fejlesztése. A program honlapja: CLEAN. Install-programok:

Levélcím: Lehel _dot_ Csato _at_ cs _dot_ ubbcluj _dot_ ro