21/22 Logikai és Funkcionális Programozás
21/22 Logikai és Funkcionális Programozás
Niklaus E. WirthProgram = 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 deklaratív programnyelvek segítségével hatékonyan tudunk bonyolult programokat írni. Ezen programnyelvek esetében a programírás nagy része a specifikáció formális leírása. A címben szereplő két deklaratív programozási paradigma a célfejlesztéseknél különbözik:
- 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). |
%------------------ |
gyereke(ferenc,adam). |
gyereke(peter,marika). |
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:
Csoport | Minimum Pontszámok |
Pontszám |
Logikai programozás (lab + kvíz) |
15 | 25 (9 + 9 + 7) |
Funkcionális programozás (lab + kvíz) |
12 | 21 (11 + 10 + 7sikertelen) |
Codingame* | - | 8 (+2opc) |
Kollokvium: LOG+FUNK | 24 | 38 + 8 (funk kérdések) |
Összesen | (min. átmenő) 70 | 100 |
Megjegyzések:
- 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.
- 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.
- A kollokvium minimum pontszáma azt jelenti, hogy ez - azaz 24 pont - alatt nem átmenő a féléves vizsga (minimum-követelmény).
- 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.
- A jegyadás: 100-96 => 10; 95-90 => 9; ... 75-70 => 5.