piątek, 24 lutego 2012

Erlang - szybki kurs. Część 2. Funkcje, pliki, kompilacja.

Czas na pierwszy program. Przy okazji poznacie podstawy składni języka Erlang.

Na początek kilka punktów ogólnych:
  • Komentarze w listingach zaczynają się od znaku %
  • Źródła zapisujemy do plików z rozszerzeniem .erl
  • Każdy plik źródłowy musi należeć do pakietu, który nazywa się tak jak plik z pominięciem rozszerzenia. Tak więc plik test.erl powinien zawierać pakiet test. To trochę jak w Javie, gdzie każda funkcja musi należeć do klasy, a w ogólnym przypadku nazwa pliku z klasą musi się nazywać tak jak zawarta w nim klasa z rozszerzeniem .java.
  • Funkcje opisuje się jako funkcja/liczba, np node/0. Wartość po znaku łamania to liczba argumentów funkcji (tzw. arity) - tutaj na przykład mowa o funkcji node nie przyjmującej żadnych argumentów. Arity jest częścią uogólnionej nazwy funkcji (nazwałem to Fully Qualified Function Name, w skrócie FQFN), więc funkcje o tej samej nazwie bazowej a różnej ilości argumentów to zupełnie różne obiekty. test/0 i test/1 to różne funkcje, nie mające (potencjalne) nic ze sobą wspólnego. Trochę działa to na zasadzie przeciążania funkcji w C++.
  • Każda funkcja należy do pakietu i jest wywoływana (jak już wiecie) przez pakiet:funkcja(argumenty). Wyjątek stanowią tzw. funkcje wbudowane (tzw BIF-y od built-in function), które nie należą do żadnego pakietu i  wywołuje się je przez "gołą" nazwę. Poznaliście już dwa BIF-y - to funkcje node/0 i nodes/0.
  • Na początku pliku źródłowego musimy dać listę eksportowanych funkcji. Funkcje nie eksportowane dają się wywołać tylko z poziomu własnego modułu z jednym wyjątkiem - BIFy z rodziny spawn wymagają, aby funkcja będąca ich argumentem była wyeksportowana.
  • Polecenia dla samego kompilatora (i preprocesora) poprzedzamy minusem (odpowiednik # z C/C++) i kończymy kropką.

Teraz przykład, na początek coś prostego. Inaczej, niż w innych podręcznikach - zaczniemy nie od silni a od ciągu Fibonacciego :)

% Plik fib.erl
-module(fib).

-export([fibonacci/1]).

fibonacci(1)-> 1;
fibonacci(2)-> 1;
fibonacci(N)-> fibonacci(N-1)+fibonacci(N-2).

Pokazuję i objaśniam:
  • Moduł nazwaliśmy 'fib'.
  • Eksportujemy z tego modułu funkcję fibonacci przyjmującą jeden argument. Argumentem "funkcji" export jest lista (stąd znowu nawiasy kwadratowe) eksportowanych FQFNów.
  • Definicja funkcji fibonacci/1 składa się z 3 klauzul. Wszystkie klauzule muszą mieć to samo arity, w przeciwnym wypadku pojawi się mało intuicyjny błąd kompilacji "head mismatch". Klauzule oddziela się znakiem średnika, całą definicje kończy się kropką.

O co chodzi z klauzulami? Klauzule, a właściwie wchodzące w ich skład dopasowania stanowią clou Erlanga - wszystkie prawie konstrukcje na nich bazują. A co z naszą definicją funkcji? Sprawa wygląda tak:

  • Wszystkie klauzule przyjmują tą samą ilość argumentów (pamiętasz wspomniany błąd  "head mismatch"?).
  • Jako argumenty mogą wystąpić stałe, zmienne i don't care'y (o tym, że zmienne są nie do końca zmienne za chwilę).
  • Przy wywołaniu funkcji kompilator przegląda klauzule od pierwszej na liście. Parametry aktualne wywołania funkcji porównywane są z odpowiednimi parametrami klauzuli:
    • Jeżeli w klauzuli występują stałe, to muszą się zgadzać z wywołaniem (ta sama wartość liczby, ten sam atom, itd)
    • Jeżeli w klauzuli występują zmienne (zawsze zaczynają się od dużej litery), zostają odpowiednio podstawione parametrem aktualnym. Jeżeli ta sama zmienna występuje kilka razy w klauzuli, to odpowiednie parametry muszą mieć jednakowe wartości.
    • Jeżeli w klauzuli występuje _ (podkreślnik) bądź zmienna zaczynająca się od podkreślnika (np _Zmienna), to dany parametr jest ignorowany ( przypisanie nie następuje)
    • Do argumentów będących listami jeszcze dojdziemy :)
  • Wywoływana jest pierwsza pasująca klauzula.
  • Jeżeli żadna klauzula nie pasuje, to Erlang zgłosi błąd (coś w deseń nieistniejąca funkcja).
  • Znak -> czytamy "jeżeli wywołam tak, to zrób tak"

Tak więc:

  • Jeżeli wywołasz funkcję fib:fibonacci(1) , to Erlang przeprowadzi takie dopasowanie:
    • Szukamy funkcji fibonacci/1 (bo jest jeden argument)
    • Mamy taką funkcję, przeglądamy klauzule.
    • Klauzula 1 ma stałą jako argument. Stała ma wartość 1, argument wywołania ma wartość 1, jest dopasowanie - funkcja zwraca 1 jako rezultat.
  • Jeżeli wywołasz funkcję fib:fibonacci(2) , to Erlang przeprowadzi takie dopasowanie:
    • Szukamy funkcji fibonacci/1 (bo jest jeden argument)
    • Mamy taką funkcję, przeglądamy klauzule.
    • Klauzula 1 ma stałą jako argument. Stała ma wartość 1, argument wywołania ma wartość 2, nie ma dopasowania.
    • Klauzula 2 ma stałą jako argument. Stała ma wartość 2, argument wywołania ma wartość 2,  jest dopasowanie - funkcja zwraca 1 jako rezultat.
  • Jeżeli wywołasz funkcję fib:fibonacci(3) , to Erlang przeprowadzi takie dopasowanie:
    • Szukamy funkcji fibonacci/1 (bo jest jeden argument)
    • Mamy taką funkcję, przeglądamy klauzule.
    • Klauzula 1 ma stałą jako argument. Stała ma wartość 1, argument wywołania ma wartość 3, nie ma dopasowania.
    • Klauzula 2 ma stałą jako argument. Stała ma wartość 2, argument wywołania ma wartość 3, nie ma dopasowania.
    • Klauzula 3 ma zmienną N jako argument. Argument wywołania ma wartość 3, pasuje jak ulał. Przypisujemy N wartość 3 i uruchamiamy ciało funkcji. Funkcja zwraca sumę wartości wywołania samej siebie z argumentami N-1 i N-2 (zgodnie z definicją ciągu Fibonacciego).
    • Ważne - do klauzuli 3 pasuje każdy argument wywołania: liczba, krotka (o nich później), atom, string, whatever. Ale tylko dla liczb da  się wykonać operację odejmowania jedynki, więc podanie innych typów argumentów zakończy się błędem.

Czas zatem na próbę wykonania:

Erlang R14B02 (erts-5.8.3) [source] [64-bit] [smp:8:8] [rq:8] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.8.3  (abort with ^G)
1> c(fib).
{ok,fib}
2> fibonacci(1).
** exception error: undefined shell command fibonacci/1
3> fib:fibonacci(1).
1
4> fib:fibonacci(10).
55
5> fib:fibonacci(20).
6765
6> fib:fibonacci(30).
832040
7> fib:fibonacci(40).
102334155
8> fib:fibonacci(45).
1134903170
9>

Co się dzieje:

  • W linii 1 kompilujemy nasz skrypt (powinien pojawić się na dysku plik fib.beam)
  • W linii 2 próbujemy go uruchomić. Błąd - shell nie na BIF-a fibonacci/1... Słusznie!
  • W linii 3 uruchamiamy funkcję poprawnie, z kwalifikacją modułu.
  • W liniach 4..9 próbujemy dla większych N. Idzie mu to coraz bardziej opornie... Ale taka uroda definicyjnego, rekurencyjnego liczenia ciągu. Każde wywołanie funkcji z N>2 powoduje wywołanie 2 kopii samej siebie.
Metoda rekurencyjna, w tym przypadku to NIE jest rekurencja końcowa (tail-recursion), gdyż wywołanie nie jest ostatnią czynnością przez zapętleniem. Są dwa wywołania rekurencyjne, więc z definicji to nie może być rekurencja końcowa.

Ta funkcja wywołuje się depth-first, czyli wołamy dla (N-1), czekamy aż się wyliczy i wołamy dla (N-2), więc w szczycie rekurencji mamy co najwyżej N ramek stosu. Niestety, z faktu, że liczyliśmy fib(X) dla "lewego" wywołania nie wynika, że nie będziemy go jeszcze raz liczyć w drzewie dla "prawego", co w sumie oznacza, że funkcję wywołamy w sumie 2^N razy. Rozsądne pamięciowo, ale nie do zaakceptowania czasowo.

Metoda rekurencyjna wykorzystująca rekurencję końcową - do obliczeń wykorzystywany jest sposób z "wędrującym oknem". Wyraz liczymy tylko na podstawie dwóch poprzednich, więc
będziemy je przechowywać:

  1. 1 1 [ 2 3 ] -> 5
  2. 1 1 2 [ 3 5 ] -> 8
  3. 1 1 2 3 [ 5 8 ] -> 13
  4. 1 1 2 3 5 [ 8 13 ] -> 21
Czyli nowy lewy parametr (N2') jest starym prawym (N1), a nowy prawy (N1') jest sumą obu parametrów N2+N1. Dodatkowo potrzebujemy licznik pozostałych do końca iteracji.

% plik fibt.erl
-module(fibt).

-export([fibonaccit/1]).

% Pierwsze dwa wyrazy oblatujemy guardem
fibonaccit(N) when (N < 3) -> 1;

% Wyrazy od 3 w górę liczymy inizjalizując okno na [1 1] i pamiętając, że 2 pierwsze są już policzone
fibonaccit(N)              -> fibonaccit(1,1,N-2).

% Ostatnia rekurencja to po prostu suma okna.
fibonaccit(N2,N1,1)        -> N1+N2;

% Tutaj robimy transformację okna: [N2,N1] -> [N1,N2+N1]
fibonaccit(N2,N1,L)        -> fibonaccit(N1,N2+N1,L-1).

Czas zatem na sprawdzenie, czy nowa funkcja jest lepsza:

Erlang R15B (erts-5.9) [source] [64-bit] [smp:8:8] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.9  (abort with ^G)
1> c(fibt).
{ok,fibt}
2> fibt:fibonaccit(100).
354224848179261915075
3> fibt:fibonaccit(500).
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125
4> 

Jak widać teraz funkcja daje sobie radę z nieprzyzwoicie dużymi liczbami.

Jeżeli chcesz poprawnie programować w Erlangu, musisz nauczyć się zauważać złamanie zasady rekurencji końcowej i sposoby jej przywracania. Prawie zawsze wiąże się to z wprowadzeniem dodatkowych parametrów funkcji (tzw. akumulatorów) i dopisaniem funkcji fasadowej (tutaj jest to fibonaccit/1) ukrywającej tą technologię i poprawnie inicjalizującej akumulatory.