Funkcionális és logikai programozás { Márton Gyöngyvér, 2012} { Sapientia, Erdélyi Magyar Tudományegyetem } http://www.ms.sapientia.ro/~mgyongyi `
1
Követelmények, osztályozás Jelenlét:
Az első 4 előadáson való részvétel plusz 1 pontot jelent a vizsgán. A laborgyakorlat kötelező, hiányzás esetén kötelező az óra pótlása, ellenkező esetben csak a fizetéses vizsgán lehet részt venni.
Vizsga (Kollokvium):
A vizsga 9 pontos elméleti tételsorból áll. A vizsgázás időpontja megegyezik az utolsó előadás időpontjával. Az összes laborfeladat bemutatása (max 2 hetes késéssel) 10-es vizsgajegyet jelent. A vizsgán való részvétel követelménye, hogy a kitűzött labor feladatok 50%-ban legyenek leadva. Akik nem érik el a 7-es osztályzatot az elméleti vizsgán, azok kötelező gyakorlati vizsgát kell tegyenek, mely közvetlenül az írásbeli után következik. A fizetéses vizsgán való részvételhez nem kötelező a laborfeladatok bemutatása. 2
Könyvészet Funkcionális programozás:
Horváth Zoltán: Programnyelvek/ A funkcionális programozási nyelvek elemei http://www.cs.ru.nl/~clean/ http://people.inf.elte.hu/csz/0506/funkimp.html
Logikai programozás:
Szeredi Péter, Benkő Tamas: Deklaratív programozás, oktatási segédlet Ásványi Tibor: A logikai programozás és a Prolog Peter Flach: Logikai programozás J.M.Spivey: An introduction to logic programming through Prolog http://www.swi-prolog.org/ http://aszt.inf.elte.hu/~asvanyi/pl/jegyzetek
ELTE:http://people.inf.elte.hu/divip/ BME: http://dp.iit.bme.hu 3
Funkcionális és logikai programozáshoz szükséges install állományok, windows alá, a belső hálózaton, az alábbi szerveren Funkcionális programozás ( Clean2.1.1 ) \\kelemen\Kit\Programozás\Clean2.1.1
Logikai programozás ( Prolog ) \\kelemen\Kit\Programozás\Prolog
Funkcionális és logikai programozáshoz szükséges segédanyag, a belső hálózaton: \\kelemen\TanaroktolDiakoknak\MartonGy\Funkcionális \\kelemen\TanaroktolDiakoknak\MartonGy\Logikai 4
Témakörök Bevezető Funkcionális programozás Clean 2.1. 1. környezetben Jellemzők Listák Magasabb rendű függvények Operátorok Adatszerkezetek, algoritmusok I/O műveletek Algoritmusok hatékonysága Eseménykezelés, grafikus felület Hálózati kommunikáció Logikai programozás Prolog környezetben, bevezető Alapfogalmak: aritmetika, listák, operátorok Algoritmusok I/O műveletek
5
Bevezető Programozási módszerek: imperatív programozás programozási nyelvek: assembly, Java, C, C++, alapeszköze: a ciklus utasítás
deklaratív programozás Funkcionális programozás programozási nyelvek: Lisp, Haskell, Clean alapeszköze: a függvény
Logikai programozás programozási nyelvek: Prolog, SQL alapeszköze: a reláció -tények, szabályok 6
az imperatív programozás sajátosságai: felszólító mód: parancsok, utasítások a lényeg az algoritmus megtalálása ( hogyan oldjuk meg a feladatot) pontosan követhetőek a végrehajtott lépések a változó: egy adott memória helyen tárolt aktuális érték, mely ismételten újabb és újabb értéket vesz fel
7
a deklaratív programozás sajátosságai:
kijelentő mód: állítások, egyenletek a lényeg: az algoritmus leírása ( mit kell megoldanunk ) a végrehajtás, a nyelv értelmező, fordító programjától függ nem mindig követhetőek a végrehajtott lépések a változó: a matematikából ismert fogalomnak felel meg, tulajdonképpen egy ismeretlen, ami segítségével felírjuk az adott relációt, rekurzív összefüggést alkalmazási terület: Cad rendszerek, telekommunikáció, mesterséges intelligencia
8
C kód: 1 változat : int fakt0 ( int n ) { int i, res; if ( n<0 ) return -1; if ( n==0 ) return 1; for( i=1, res=1; i<=n; i++) res *= i; return res; }
2 változat: int fakt1 ( int n ) { if ( n<0 ) return -1; if ( n==0 ) return 1; else return n * fakt1(n-1); }
3 változat: int fakt2 ( int res, int n) { if ( n<0 ) return -1; if ( n==0 ) return res; return fakt2(n*res , n-1); } függvény hívások: X = fakt0 (10); X = fakt1 (10); X = fakt2 (1, 10);
9
Clean kód: 1 változat : fakt1 fakt1 fakt1
:: Int -> Int 0 = 1 n = n * fakt1 (n-1)
függvény hívás: Start = fakt1 10
2 változat :
3 változat: fakt3 :: Int Int -> Int fakt3 res n | n < 0 = -1 | n == 0 = res = fakt3 (n*res) (n-1) függvény hívás: Start = fakt3 1 10
fakt2 :: Int -> Int fakt2 n | n < 0 = -1 | n == 0 = 1 = n * fakt2 (n-1) függvény hívás: Start = fakt2 10
10
Prolog kód: fakt(0, 1). fakt(N, Res) :N >0, N1 is N - 1, fakt(N1, Res1), Res is N * Res1. a formula kiértékelése: fakt(10, X).
11
Funkcionális programozás Clean 2.1.1. környezetben
12
Jellemzők feltételek megadása ( definition by cases ) : a függvény értékét az első, igaz egyenlőséghez tartozó kifejezés adja, mely kifejezést az aktuális paraméter értéke alapján kapjuk Pl: az argumentum előjelének a meghatározása alapok1.icl module alapok1 import StdEnv signum :: Int -> Int signum x | x < 0 = -1 | x > 0 = 1 | x == 0 = 0 Start = signum -10 13
rekurzivitás ( definition by recursion ): a függvények hivatkozhatnak önmagukra és kölcsönösen egymásra Pl: két egész szám legnagyobb közös osztójának a meghatározása lnko :: Int Int -> Int lnko a b | a > b = lnko (a-b) b | a < b = lnko a (b-a) | a == b = a Start = lnko 18 56
14
az argumentumok mintaillesztése ( definition by patterns ): a függvény értékét az a függvénytörzs határozza meg, amelyre a formális paraméter egy megadott minta alapján illeszkedik Pl1: egy három elemű lista elemeinek összeadása
Pl2: egy szám számjegyeinek összege
osszeg osszeg osszeg osszeg osszeg
isum :: Int -> Int isum 0 = 0 isum szam = ( szam rem 10 ) + isum (szam /10)
:: [Int] -> Int [] = 0 [x] = x [x,y] = x+y [x,y,z] = x+y+z
Start = isum 123 //futási hibát ad Start = osszeg [2,3,4,5]
a mintaillesztést és a feltételek megadását lehet együttesen alkalmazni 15
szigorú, statikus típusosság : a kifejezések típusát a fordítóprogram meghatározza úgy is, ha nincs az feltüntetve Pl: az argumentum abszolut értékének a meghatározása abszolut x | x < 0 = ~x //az x értékének a negáltja = x Start = abszolut -10 abszolut :: Int -> Int abszolut x | x < 0 = ~x = x
abszolut :: Real -> Real abszolut x | x < 0.0 = ~x = x
abszolut :: a -> a | zero, <, ~ a abszolut x | x < zero = ~x = x 16
Zermelo-Fraenkel halmazkifejezések: iteratív adatszerkezetek (listák, halmazok, sorozatok) elemeinek megadására alkalmazott jelölésrendszer Pl: egy szam osztóink a sorozata osztok :: Int -> [ Int ] osztok n = [ i \\ i <- [1..n] | n rem i ==0] Start = osztok 100
17
speciális kifejezések: #, (let-before expression) az imperatív programozási stílushoz hasonló szerkezet egy feltétel, vagy a függvénytörzs előtt definiálható alkalmazható amikor a kiértékelési sorrend jól meghatározott Pl. gyok :: Real Real Real -> (Real, Real) gyok a b c #delta = sqrt(b*b-4.0*a*c) #d = 2.0*a = ( (~b + delta) / d, (~b - delta) / d ) Start = gyok 1.0 2.0 1.0
Megjegyzés: az sqrt könyvtárfüggvény
18
margó szabály: az összetartozó kifejezések meghatározására a baloldali margó változtatását kell alkalmazni PL.: másodfokú egyenlet gyökeinek a meghatározása gyok :: Real Real Real -> (Real, Real) gyok a b c = ( (~b + delta) / d, (~b - delta) / d ) where delta = sqrt(b*b-4.0*a*c) d = 2.0*a delta a = 3*a Start = gyok 1.0 2.0 1.0
Melyik delta kifejezés értékelődik ki? Start = delta 2
19
különböző típusok együttes alkalmazása Pl. gyok :: Real Real Real -> (String, [Real]) gyok a b c #delta = sqrt(b*b-4.0*a*c) #d = 2.0*a |delta < 0.0 = ("komplex gyokok", []) |delta == 0.0 = ("egy gyok", [~b/d]) = ("ket gyok", [ (~b + delta) / d, (~b - delta) / d ]) Start = gyok 1.0 3.0 1.0
20
magasabb rendű függvények ( high order function ) I argumentumuk lehet függvény visszatérítési értékük lehet függvény, mely más függvénynek is szolgálhat argumentumul Pl 1. my_inc x = x+1 my_twice f x = f (f x) Start = my_twice my_inc 0 Pl 2. Start = map sqrt [ 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0 ]
Megjegyzés: a map könyvtárfüggvény, két argumentuma van: az első egy függvény, melyet alkalmaz a listaként megadott második argumentumára 21
