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 általánosan fel lehet osztani imperatív és deklaratív nyelvekre. Az imperatív programozási nyelvek -- például a PASCAL, a C, FORTRAN -- esetében a számítógépnek 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 műveletet specifikáltuk csak, 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 alap-tulajdonsága, hogy minden entitás függvény. Egy programban előforduló konstansok is zéró-változós függvényként léteznek.
A következmény, hogy a "változók" nem változtatják értéküket: 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 rendkivü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.
A kurzus során a funkcionális programozás főbb jellemzőit ismertetem - Horváth Zoltán jegyzeteire alapozva.
Az előadások során írt rövidke szösszenetek 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.

Vizsgaidőpont: 2010 január 16, 14 óra.

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. Programnyelvek könyv fejezete
  3. CleanBook a Clean honlapjáról eredeti verzió a ITT
  4. 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á: prolog_edit
    • 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