Pułapka

Pisałem ostatnio program wykonujący dość długo skomplikowane obliczenia. Przy pewnych danych wejściowych program przepełniał stos i się wysypywał. Po kilku godzinach frustracji postanowiłem przepisać każdą funkcję na wersję ogonową.
W trakcie tego jak to robiłem zacząłem się zastanawiać nad programowaniem funkcyjnym. Generalnie to jego główną ideą jest to, że piszemy w nim nie jak coś policzyć (tak jak to jest w programowaniu imperatywnym) tylko czym wynik danej funkcji ma być. I to jest bardzo przyjemne i bardzo fajnie się tak pisze - wszystkie funkcje wklepuje się niemal intuicyjnie. Problem jest jak dojdzie do funkcji ogonowych. Funkcje ogonowe (zwłaszcza nieco bardziej skomplikowanych obliczeń) są w ogóle nie intuicyjne. Trzeba zacząć się zastanawiać co ma być akumulatorem (może trzeba dać dwa akumulatory?) jakie dodatkowe informacje należy przekazać itp. itd.
Na szczęście udało mi się wszystkie funkcje przepisać na wersje ogonowe (Teraz jak ktoś spojrzy na kod to już się nie dowie co to a to robi :) ). Nie udało się przepisać tylko jednej. Może ktoś z was będzie miał pomysł. Funkcja dostaje długość listy l oraz sumę s i generuje wszystkie listy o długości l zawierające liczby dodatnie sumujące się co najwyżej do s. Na przykład: funkcja 3 5 = [[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,3,1][2,1,1],[2,1,2],[2,2,1],[3,1,1]]. Kolejność list nie jest ważna.
Gdy już miałem prawie wszystkie funkcje ogonowe i sprawdziłem ręcznie, że program nie wywiesza się na tej funkcji nie ogonowej... program dalej się wywieszał :-) Zasięgnąłem zatem opinii dokumentacji i okazało się... że standardowa funkcja map nie jest ogonowa... Troszeczkę się zdenerwowałem. Gdzie kolejność elementów nie była dla mnie ważna użyłem funkcji rev_map. W innych sytuacjach napisałem własną funkcję map:

let mymap l p = rev (map l p);;

Program wciąż nie działa - typ razem już na mojej funkcji (opisanej wyżej). Przepisałem program do C++ działa i to sto razy szybciej ;)

Fresh i Reset bez użycia zmiennych globalnych

Rozważmy następujący problem. Mamy stworzyć dwie funkcje: fresh i reset. Pierwsza z nich ma generować kolejne liczby naturalne dodatnie, druga ma nam posłużyć do zerowania naszego stanu liczniki. Przykładowa sesja programu może wyglądać na przykład tak:

# fresh ();;
- : int = 1
# fresh ();;
- : int = 2
# fresh ();;
- : int = 3
# fresh ();;
- : int = 4
# reset ();;
- : unit = ()
# fresh ();;
- : int = 1
# fresh ();;
- : int = 2

Cały problem w napisaniu tej funkcji polega na tym, że w implementacji nie możemy korzystać ze zmiennych globalnych. Polecam, abyś sam przez chwilę zastanowił się jak ten problem rozwiązać zanim przeczytasz moje rozwiązanie.

Zmienna w OCamlu "żyje" tak długo aż istnieje wskaźnik na tą wartość. I nie ważne czy zmienna ta została zdefiniowana globalnie czy lokalnie w funkcji.

Pierwszy pomysł to stworzenie funkcji, która jako argument bierze unit, a zwraca parę funkcji (fresh, reset). Zadeklaruje ona lokalnie zmienną, która będzie użyta do zdefiniowania funkcji. Po wyjściu zmienna ta nie będzie już nigdzie widoczna poza zwróconą parą funkcji.

type r = { mutable x : int };;

let create () =
    let y = ref {x = 0} in
    ((fun () -> (ignore (!y.x <- !y.x + 1) ; (!y.x))),
      fun () -> ignore (!y.x <- 0));;

let x = create () ;;
let fresh = fst x and reset = snd x;;

Takie rozwiązanie ma swoje wady i zalety. Zaletą jest to że możemy tworzyć wiele par fresh-reset, wadą to, że pozwalamy na korzystanie ze zmiennej x bez konieczności użycia funkcji fresh i reset.

Edit: W komentarzach pojawiły się inne (imho lepsze) rozwiązania tego zadania. Polecam lekturę tych komentarzy ;)

Błędy w OCamlu

Programy w OCamlu pisze się bardzo przyjemnie. Schody zaczynają się gdy OCaml chce nas poinformować, że zrobiliśmy błąd. Często robi to tak nieudolnie, że bardzo trudno jest błąd nawet zlokalizować. Dziś przez pół godziny szukałem z Maćkiem błędu w implementacji Grafu. Błąd znaleźliśmy, ale w zupełnie innym module niż ten na który wskazywał OCaml.
Dziś rano z kolei OCaml powitał mnie komunikatem

File "Database.ml", line 54, characters 17-25:
This pattern matches values of type punkt
but is here used to match values of type punkt

Bardzo zdziwiłem się widząc ten komunikat. I chyba nie znalazłbym błędu, gdybym nie widział podobnego błędu wcześniej. Troszkę starań i OCaml wypluje nam taki komunikat:

This expression has type t but is here used with type t

Jak zmusić OCamla do wyplucia takiego błędu? Opiszemy za chwilę. Na razie spróbujmy zrozumieć co tak na prawdę OCaml ma na myśli. Rozważmy następującą sesję ewaluatora:

# type typ1 = Konstruktor | Innykonstruktor;;
type typ1 = Konstruktor | Innykonstruktor

# Konstruktor;;
- : typ1 = Konstruktor

# type typ2 = Konstruktor | Jeszczeinnykonstruktor;;
type typ2 = Konstruktor | Jeszczeinnykonstruktor

# Konstruktor;;
- : typ2 = Konstruktor

W trzecim poleceniu do zdefiniowania typu "typ2" użyliśmy ponownie konstruktora "Konstruktor". Przesłoniliśmy w ten sposób konstruktor o tej samej nazwie z typu pierwszego. Nie będziemy mogli już z niego normalnie korzystać. Gdy użyjemy teraz w dowolnym miejscu konstruktora "Konstruktor" zostanie on potraktowany jako konstruktor z typu drugiego (a nie jako konstruktor typu pierwszego).

# type t = Konstruktor of int;;
type t = Konstruktor of int

# let get_int a = match a with Konstruktor b -> b;;
val get_int : t -> int = 

# type t = Konstruktor of int;;
type t = Konstruktor of int

# let osiem = Konstruktor 8;;
val osiem : t = Konstruktor 8

# get_int osiem;;
This expression has type t but is here used with type t

Przeanalizujmy co tutaj się stało. W pierwszej linijce tworzymy nowy typ t. W drugiej linijce definiujemy funkcję, która jako argument bierze typ t - ten z pierwszej linijki (mniejsza o to co ta funkcja robi). W linijce trzeciej tworzymy nowy typ t (ma on nawet tą samą definicję co nasz pierwszy typ t - mimo to będzie traktowany jako nowy typ). Przesłaniamy w ten sposób pierwszy typ t. W linijce czwartej definiujemy wartość "osiem" używając konstruktora "Konstruktor". Jak wiemy z poprzedniego akapitu - będzie to wartość typu t zadeklarowanego w 3 linijce. Na koniec próbujemy wywołać funkcję od wartości "osiem", która jest typu t (zdefiniowanego w linijce 3) podczas gdy funkcja przyjmuje argumenty typu t (zdefiniowane w linijce pierwszej).

Zbiór Mandelbrota w OCamlu

Ostatnio na pracowni z programowania funkcyjnego kazano nam napisać program w OCamlu rysujący zbiór Mandelbrota.
Postanowiłem zamieścić tutaj swoje rozwiązanie dlatego, że niewiarygodne jest jakie piękne efekty możemy otrzymać za pomocą 20-linijkowego programu.

(* Mandelbrot :-) *)

#load "graphics.cma";;
open Graphics;;
open Complex;;

let conve a =
    float_of_int(a) /. (640. /. 4.) -. 2.;;

let rec calc_color p zn k =
    if      k = 0 then 0
    else if norm zn >= 2. then k
    else    calc_color p (add (mul zn zn) p) (k-1);;

let display () =
open_graph " 640x640";
for x = 0 to 640 do
   for y = 0 to 640 do
      let p = {re = conve x; im = conve y} in
      let k = 8 * calc_color p p 31 in
      set_color (rgb k k k);
      plot x y
   done
done;
let _ = read_key () in close_graph();;

Zbiorem Mandelbrota nazywamy zbiór punktów p na przestrzeni zespolonej, który spełnia warunek |z_n| < 2. Przy czym z₀ = p oraz z_n = z_n-1 * z_n-1 + p dla n > 0. Przybliżenie tego zbioru otrzymujemy ustalając pewną liczbę powtórzeń m, a następnie sprawdzając, które punkty płaszczyzny spełniają z₀ < 2, z₁ < 2, ..., z_m < 2.

Funkcja conve zamienia liczbę naturalną z przedziału [0..640] (w oknie o rozdzielczości 640x640 będziemy rysowali zbiór Mandelbrota) na liczbę rzeczywistą z przedziału [-2..2] (jeśli, któraś ze współrzędnych danego punktu jest spoza tego przedziału to punkt ten nie należy do zbioru Mandelbrota).

Funkcja calc_color liczy kolejne wartości ciągu z_n dla n = 0..k i szuka najmniejszego takiego m, że z_m >= 2. Funkcja zwraca k - m. Od tej wartości będzie zależał kolor na jaki pomalujemy dany punkt na płaszczyźnie (stąd nazwa).

Funkcja display tworzy okno o rozmiarach 640 x 640. Następnie dla każdego piksela w tym oknie liczymy jego współrzędne zespolone. Następnie obliczamy kolor w jakim będziemy malować ten piksel, ustawiamy pędzel na ten kolor i na końcu malujemy ten piksel na dany kolor.

O funkcyjnym paradygmacie programowania napiszę słów kilka w niedalekiej przyszłości.
Jeśli coś było niejasnego w tej notce, lub notka zawiera błąd, to będę wdzięczny za komentarze.