21/22 Logikai és Funkcionális Programozás

Niklaus E. Wirth
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.

Deklaratív programozási nyelvek

R. Kowalski
"Algoritmus = Logikai rész + Kontroll rész"

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 esetében egy "tudásrendszert" specifikálunk, majd a rendszert - SQL-szerűen - arról kérdezzük, hogy adott lekérdezést milyen feltételek mellett tud teljesíteni. Példák "lekérdezésekre":
• egy élek és csúcsok által reprezentált gráfban melyek az olyan csúcs értékek, melyek egy másik, de adott csúcsnak az ősei.
• ugyancsak egy gráfban, mely ezúttal városok közötti kapcsolatokat ábrázol, találjuk meg az összes utat A város és B város között. Az így létrejött utak listából válasszuk ki ezek közül a legrövidebbet.
• adott környezetben navigáljunk el egy robottal egy célállapotba. Itt a feltett kérdés a következő: melyik az a mozgás-primitívekből álló lista, mely a robotot a célállapotba viszi. Itt általában a bemenő paraméter a kezdőállapot.
• a funkcionális programozás esetén függvényeket - lásd C/C++ - "rakunk" össze, melyek adott számítási feladatot megvalósítanak. Ebben az esetben nagyon fontosak a következő jellemzői a funkcionális nyelvnek illetve az adott programkörnyezetnek:
• minden függvény: amit egy programnyelvben "1" -- vagy általában egy numerikus konstanssal -- jelölünk, az egy függvény, melyet amikor meghívunk, mindig ugyanazt az értéket téríti vissza. Most egyet.
• mivel minden függvény, ezeket át lehet adni argumentumként is más függvényeknek. Pl. ha egy listát szeretnénk átalakítani úgy, hogy az összes elemét négyzetre emeljük, akkor meghívhatjuk a map függvényt a "négyzetre emelés" argumentummal:
  

  map (\ x -> x*x) [1,2,3,4,5,6,7]

  mely a kiemelt -- és név nélküli -- függvényt alkalmazza egy lista minden elemére.
• a funkcionális nyelvek lusták: pl. felépíthetjük a Fibonacci-számok listáját a következőképp:
  

  fibs  = 1 : 1 : zipWith (+) fibs (tail fibs)

  ahol egy háromelemű listát látunk, melynek harmadik eleme egy lista. Egy rekurzív definíció tehát, melynek nincs utolsó eleme. Ezt a típusú kódot le tudjuk futtatni funkcionális nyelveknél, ugyanis ezek a nyelvek "lustán" értékelik ki a kifejezéseket: előbb kiszámítják a lista első elemét, majd -- ha szükség -- a másodikat, stb. Látjuk, hogy ez lehetséges.

Látjuk, hogy a fordítóra bízzuk azt, hogy az egyes függvényeket -- műveleteket -- hogyan hajtja végre a fordító. Azt jelenti, hogy a fordítóra bízzuk az esetleges konkurrens futtatást, illetve más -- a program futását befolyásoló -- optimalizációs módszerek beiktatását.

A tárgy a hangsúlyt ezen jellemzők bemutatására illetve a programozási elvek -- például a "lusta programozás" elve -- gyakorlására helyezi.

A Prolog programozási nyelv

A Prolog nyelv a programming logic rövidítése, melyben tényeket és érvényes levezetési szabályokat jelentünk ki. A rendszer ezeket használja fel és keres lehetőségeket a lekérdezésünk teljesítésére. Például egy közvetlenül szomszédos városokat tartalmazó tudásbázist kielégítve egy gráfkereső algoritmussal, megtudhatjuk, hogy két város között mekkora a legrövidebb út illetve azt, hogy mely városok közbeiktatásával tudjuk azt elérni.

A Prolog rendszer alapja tehát egy tényhalmaz illetve az azok fölött értelmezett szabályhalmaz. Ezeket nevezzük együttesen tudásbázisnak. Egy példa a tényekre a következő:

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ályok a következő formájúak:

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).

A Prolog a backtracking algoritmust használja: az illeszkedő tényeket és szabályokat illeszti a lekérdezésünkhöz minták segítségével. Egy példa az illeszkedésre két listának az összefűzése, melyeket a következő tény-szabály páros ír le:

append([],Lista,Lista).
append([Fej|Mar],Lista,[Fej|FMar]):-
 append(Mar,Lista,FMar).

A fentiekben azt jelentjük ki, hogy egy üres lista bármely listához fűzve nem változtat a listán. A második axiómában egy nem üres lista első argumentumot bontunk fel Fej-re és Maradékra, majd a Mar és a Lista összefűzött változata elé illesszük a Fejet. A predikátummal össze tudunk fűzni két listát - ha az első és a második argumentumot specifikáljuk, a harmadikat üresen hagyjuk - de le is tudjuk választani a harmadik listáról az első argumentumot a lista elejéről; vagy a listának a végét is le tudjuk vágni. Az append(X,Y,[a,b,c,d,e]) megadja a listának az összes bontási lehetőségét.

A mintaillesztéssel és a listákkal való műveletekkel sok algoritmust meg tudunk valósítani, ezeket mutatjuk be az előadás első részében.

A Haskell programnyelv

A Haskell programnyelv egy modern funkcionális programnyelv. A Prolog-gal a kapcsolata a deklaratív jelleg: a Prolog-hoz hasonlóan itt sem jelentünk ki változókat; itt is az új függvények - a Prolog-ban predikátumok - hívásánál vezetjük be azokat. Például kijelenthetünk egy segédváltozót egy lista elemeinek az összeadásánál:

sum lista = sum_ lista 0

sum_ [] acc = acc
sum_ (x:xs) acc = sum_ xs (x+acc)

A fenti példában az acc változót vezetjük a sum_ függvény második argumentumaként és a változó kezdeti értéke nulla. A definícióban azt látjuk, hogy egy lista elemeinek összegéhez kijelentettünk egy segédfüggvényt, melyet definiáltunk utána. Látjuk, hogy a definíciónál mintákat használtunk: a előbb lekezeltük az esetet, amikor a lista már üres, majd a nem üres esetet is definiáltuk. A Prolog-gal ellentétben a Haskell mintaillesztése mohó: amikor talált egy első mintát, melyre illeszkedik, a rendszer továbblép, tehát nincs backtracking rendszerszinten.

A Haskell jobban strukturált, mint a Prolog, lehetőség van függvények lokális kijelentésére is. Például a fenti kódban elrejthetjük a sum_ függvény kijelentését:

sum lista = sum_ lista 0
 where
 sum_ [] acc = acc
 sum_ (x:xs) acc = sum_ xs (x+acc)

ahol a where kulcsszóval jeleztük a rendszernek, hogy a sum_ függvény hol van definiálva.

A deklaratív jelleget őrzi a minták által történő függvénykijelentés: a függvényeket változók bizonyos mintáira lehet hívni. A listák összefűzésére használt appM (az elnevezés tükrözi, hogy a függvényt mi írjuk) függvény a következő:

appM [] lista = lista
appM (x:xs) lista = x : appM xs lista

ahol használtuk az "üres lista" mintát - [] - illetve azt a mintát, ahol a lista fejét leválasztottuk a lista többi részétől a ":" segítségével.

Különlegessége a HASKELL nyelvnek - a Prolog és a régebbi funkcionális nyelvekkel ellentétben - a típusrendszer. A függvényeknek és azok paramétereinek típusa van, hasonlóan a Pascal, C, C++, C#, illetve az imperatív függvények esetében. A HASKELL képes a típusokat levezetni a függvények kijelentéseiből és ehhez használja a saját típusosztályait.

A fenti appM függvény típuslevezetését illusztráljuk: az első definícióból az appM első argumentuma lista, a második argumentum típusa megegyezik a kimenő értékkel. A második kijelentésből látjuk, hogy a kimenő érték is egy lista - ott van a lista felbontását jelző ":" - és azt is, hogy az első listában szereplő elemek típusa megegyezik a kimenő lista elemeinek a típusával. A következtetés, hogy a három entitás azonos típusú: egy-egy lista, melynek elemei tetszőleges típusúak lehetnek. A levezetett típus tehát:

appM:: [a] -> [a] -> [a]

Figyeljük meg az implicit polimorfizmust: egy listaösszefűzéssel megírtuk a listák összefűzését minden típusú listára.

Az előadások második felében a funkcionális nyelvek jellegzetességeiről, a típuslevezetés hasznáról és annak a részleteiről, illetve különböző algoritmusok funkcionális megírásáról lesz szó.

Jegyadás

A tárgyból a vizsga kollokvium. ami azt jelenti, hogy az oktatási periódus vége előtt le kell záródnia a tárgynak. A LOG-FUNK félév közben lesz kiértékelve. A pontozások lebontása az FELADATOK részben van, alább egy összefoglalót találtok:

Megjegyzések:

1. A táblázat második oszlopa azt jelenti, hogy az illető csoportból ennyi pontszámot el kell érni, hogy a kollokviumon tudjunk vizsgázni.
2. A Funkcionális rész pontszámai esetén a codingame* pontok nem számítanak a minimum pontszám számításánál.
3. A kollokvium minimum pontszáma azt jelenti, hogy ez - azaz 24 pont - alatt nem átmenő a féléves vizsga (minimum-követelmény).
4. Az összes minimum pontszáma azt jelenti, hogy a három résznek az összege el kell érje a 70-et ahhoz, hogy a tárgyból megkapjuk az átmenőt.
5. A jegyadás: 100-96 => 10; 95-90 => 9; ... 75-70 => 5.