Funkcionális programozás Erlang nyelven
Fehér Gábor órája alapján
Az Erlang története
1985-ben született, az Ericsson egyik fejlesztő központjában. Telefonközpontok programozására fejlesztették ki, de hatékony eszközöket nyújt más elosztott rendszerek programozásához is. A nyelv fontos jellemzője, hogy a különálló programrészeket minél inkább elszigeteli egymástól. Például a párhuzamosan futú szálak csak üzenetküldéssel tarthatnak egymással kapcsolatot, de például közös memórián már nem osztozhatnak. Ez azért jó, mert így nagy, sok komponensből álló rendszerek esetén átláthatóbb és kezelhetőbb marad a komponensek közötti kapcsolatrendszer.
Az Erlang specialitásai
- Egy változó csak egyszer kaphat értéket.
A = 3.
A = 4. HIBA!!!
- A függvényeknek általában nem lehet mellékhatása. Minden mellékhatás, ami a függvényen kívüli világon változtat, kivéve a függvény visszatérési értékét.
VAR
q: INTEGER;
FUNCTION f(a,b : INTEGER): INTEGER;
BEGIN
f := a + b; {visszatérési érték, oké}
q := 5; MELLÉKHATÁS, q külső változó!!!
END;
De például a processzek közötti kommunikáció, képernyőre kiírás, stb. mind mellékhatásnak minősülnek és engedélyezve vannak, mert szűkség van rájuk. Mi viszont ma csak tisztán funkcionális, azaz mellékhatás nélküli függvényekkel fogunk foglalkozni.
Erlang programok futtatása - az Erlang Shell
Legegyszerűbb úgy használni, ha elindítjuk erl nevű parancsértelmezőt, azaz shell-t:
$ erl
Erlang R13B02 ...
Eshell V5.7.3 (abort with ^G)
1> A = 17. % Minden kifejezést egy pont zár le. (ez pedig egy komment)
17 % A kifejezés eredménye a következő sorban jelenik meg.
2> B = 4.
4
3> (A+B)/0.5.
42.0
4> A = 6. % HIBA! A már kapott értéket
** exception error: no match of right hand side value 6
5> f(). % "forget" az összes eddig létrehozott változó törlése
ok
6> A = 6. % most már jó
6
5> X = "Hello, ".
"Hello, "
6> W = "world!".
"world!"
7> X++W. % string összefűzés
"Hello, world!"
Modul
Összetetteb Erlang programokat modulokba írhatunk és a shellből futtathatjuk őket. A változók nagybetűsek, a függvények neve pedig kisbetűs.
hello.erl:
-module(hello).
-export([avg/2]). % a kívülről (pl. shellből) hívható függvények listája
% a /2 a paraméterek számát jelöli
% így néz ki egy függvény
avg(A, B) ->
Sum = A+B, % vessző választja el a kifejezéseket
Sum / 2. % az utolsó kifejezés adja meg a visszatérési értéket
Modulunkat lefordíthatjuk és kipróbálhatjuk az Erlang shellből.
1> c(hello). % modul fordítása (a hello.erl az aktuális könyvtárban legyen)
ok
2> hello:avg(10, 6). % függvényhívás
8
Elágazások
Erlangban egy függvénynek lehet több klóza is. Ezt kihasználva készíthetünk elágazásokat programunkban. A közbülső klózok egy pontosvesszővel vannak lezárva, az utolsó klóz pedig egy ponttal. A klózoknak a when kulcsszó után lehet őrfeltétele. Mindig a legelső olyan klóz fog lefutni, amelyiknek teljesül az őrfeltétele. (Vagy pedig nincsen őrfeltétele.)
-module(hello).
-export([avg/2, max/2]).
avg(A, B) -> ...
max(A,B) when A=<B ->
B; % itt a klózok közötti pontosvessző
max(A,B)->
A.
A második klózban a nem használt B paramétert egy aláhúzással helyettesíthetjük. Ezzel elkerülhetjük a fordítóprogram hibaüzenetét:
max(A,_)->
A.
Használat:
1> c(hello).
2> hello:max(10, 20).
3> hello:max(6, "hat"). % ...
Ciklusok (Fibonacci-számok)
A továbbiakban a modulfejetkihagyjuk a példákból, és mindig csak az aktuális függvények export-ját mutatjuk meg. Ettől függetlenül érdemes lehet az összes programot a hello.erl-be írni.
A ciklusokat rekurzióval helyettesítik a funkcionális programozási nyelvek. Egyszerű példa:
-export([fibo/1]).
fibo(N) when N =:= 0 ->
0;
fibo(N) when N =:= 1 ->
1;
fibo(N) when N > 1 ->
fibo(N-1)+fibo(N-2).
Ez nem hatékony, lásd
1. óra... Ha imperatív nyelven programoznánk, akkor a Fibonacci-számokat valahogy így határoznánk meg:
FUNCTION Fibo(n: INTEGER): INTEGER;
a := 0;
b := 1;
WHILE (n > 1) DO
c := a + b;
a := b; b := c;
n := n - 1;
END;
Erlangban a ciklust egy önmagát meghívó (rekurzív) függvény helyettesítheti:
-export([fibo2/1]).
fibo2(N) ->
A = 0, B = 1,
fibo3(N, A, B).
fibo3(N, _, B) when N =:= 1 ->
B;
fibo3(N, A, B) ->
C = A+B,
A2 = B, B2 = C,
fibo3(N-1, A2, B2). % a ciklus következő iterációja, a változók új értékeivel
Figyeljük meg, hogy az Erlang tetszőleges nagyságú egész számokat tud ábrázolni. Ha viszont csak az utolsó néhány számjegyére vagyunk kíváncsiak az n. Fibonacci számnak, akkor összeadásnál elég ha a számok $10^k$ maradékát nézzük. Pl.:
C = (A+B) rem 1000,
Listák
Erlangban, sok funkcionális nyelvehez hasonlóan, láncolt listákat lehet több elem tárolására használni. A lista első elemét a fejének nevezzük, a maradék részét pedig a farkának. Egy egyelmű lista farka az üres lista. Egy listát elemeinek felsorolásával, szögletes zárójelek közé írva lehet megadni. Az elemek típusa tetszőleges lehet (akár másik lista is):
1> L = [5, 6, 7, 42, "szoveg"].
A fejét és a farkát a hd/1 és tl/1 beépített függvényekkel lehet elérni:
2> hd(L).
5
3> tl(L).
[6, 7, 42, "szoveg"]
4> hd(tl(tl(L))).
7
5> tl([42]). % egyelemű lista farka:
[] % üres lista
Listákat szét lehet szedni és össze lehet rakni a [Fej | Farok] szintaxis használatával is. Szétszedés:
1> [H|T] = [10, 20, 30].
[10, 20, 30]
2> H.
10
3> T.
[20, 30]
Összerakás:
4> Head = 15.
5> Tail = [3.14, pi].
6> L2 = [Head|Tail].
L2 = [15, 3.14, pi]
Listák összefűzése a ++ operátorral lehetséges:
7> L++L2.
[5, 6, 7, 42, szoveg, 15, 3.14, pi]
Négyzetreemelés
Feladat: adott egy lista ami számokat tartalmaz. Készítsük el a másolatát, amiben a számok négyzetei vannak.
negyzet0([]) -> % ez a klóz hívódik meg üres lista esetén
[];
negyzet0(L) -> % ez a klóz hívódik meg nemüres lista esetén
[H1|T1] = L, % szétszedjük a listát fejre és farokra
H2 = H1*H1, % az ereménylista feje, azaz négyzetre emeltük az első elemet
T2 = negyzet0(T1), % elvégezzük a négyzetreemelést a maradék elemekre (azaz a farokar)
[H2|T2]. % összerakjuk az új listát
Vagy ugyanez tömörebben:
-export(negyzet/1).
negyzet([]) ->
[];
negyzet([H1|T1]) ->
[H1*H1|negyzet(T1)] = L.
Próbafuttatás:
1> c(hello).
ok
2> hello:negyzet([1, 2, 3, 4]).
[1, 4, 9, 16]
Gyorsrendezés
A gyorsrendezés algoritmusa:
- Adott egy rendezetlen, számokat tartalmazó lista. Cél egy olyan lista készítése, amiben az eredeti számok növekvő sorrendben vannak.
- Ha a lista üres, akkor készen vagyunk. Különben:
- Választunk és kiveszünk egy véletlenszerű X elemet a listából.
- Két csoportra bontjuk a maradék lista elemeit: az egyik csoportban az X-nél kisebb, a másikban a nála nem kisebb elemek vannak.
- Rekurzívan alkalmazzuk az algoritmust az előző pontban kapott két listára.
- Összefűzzük a két így kapott rendezett listát, közéjük rakva az X-et.
Ennek az algoritmusnak a várható (átlagos) futási ideje $O(n \log n)$. Maximális futási ideje: $O(n^2)$.
Először készítünk két függvényt: kisebb(L, A) eredménye L lista azon elemeinek a listája, amik kisebbek A-nál. nemkisebb(L, A) hasonlóan működik.
kisebbek([], _) ->
[];
kisebbek([B|L], A) when B < A ->
[B|kisebbek(L, A)];
kisebbek([_B|L], A) -> % when B >= A
kisebbek(L, A).
nemkisebbek([], _) ->
[];
kisebbek([B|L], A) when B >= A ->
[B|nemkisebbek(L, A)];
nemkisebbek([_B|L], A) -> % when B < A
nemkisebbek(L, A).
Véletlenszerű elem kiválasztása időigényes lenne láncolt listából, úgyhogy a "véletlenszerű elem" mindig az első lesz. qsort/1 a következőképp valósítható meg a fenti két függvény használatával:
-export([qsort/1]).
qsort([]) ->
[];
qsort([A|L]) ->
% A a "véletlenszerű" első elem
L1 = kisebbek(L, A),
L2 = nemkisebbek(L, A),
qsort(L1)++[A]++qsort(L2).
Generikus függvények
Erlangban egy változónak értékül adhatunk egy függvényt, és ezen a változón keresztül később meg is hívhatjuk azt. A következő példában F-hez hozzárendelünk egy névtelen függvényt, ami egy összeadást végez el:
1> F = fun (A, B) -> A+B end.
2> F(10, 22). % így lehet meghívni
32
Vannak olyan Erlang könyvtári függvények, amik ilyen függvényeket vesznek át paraméterként, majd használják azokat. Ezeket generikus függvényeknek hívjuk. Például a lists:filter(F, L) az L lista összes elemére alkalmazza az F függvényt, és az eredmény azon elemek listája lesz L-ből, amire L igaz értéket adott vissza. Például:
1> F = fun (X) -> X > 10 end.
2> lists:filter(F, [5, 10, 15, 20, 2, 20]).
[15, 20, 20]
Ennek felhasználásval újraírhatjuk a kisebbek/2 és nemkisebbek/2 függvényeinket:
kisebbek2(L, A) ->
F = fun (X) -> X < A end,
lists:filter(F, L).
% még tömörebben:
nemkisebbek2(L, A) ->
lists:filter(fun (X) -> X >= A end, L).
Hasonlóképp, a lists:map/2 segítségével pedig újraírhatjuk a negyzetek/2 függvényt:
negyzetek2(L) ->
F = fun (X) -> X*X end,
lists:map(F, L). % L minden elemére alkalmazza F-et, és az eredmény egy lista,
% ami az F által kiszámított értékeket tartalmazza
És végül a QuickSort továbbfejlesztett változata:
qsort2([]) ->
[];
qsort2([A|L]) ->
L1 = lists:filter(fun (X) -> X < A end, L),
L2 = lists:filter(fun (X) -> X >= A end, L),
qsort2(L1)++[A]++qsort2(L2).
Példák, linkek
