Obiekty vs. struktury danych

    Jestem właśnie w trakcie lektury "Czystego kodu" Roberta C. Martina (polecam wszystkim programistom). Chciałbym podzielić się pewnym spostrzeżeniem autora tej książki. Otóż jako zupełne przeciwieństwa stawia on kod obiektowy oraz kod proceduralny operujący na strukturach danych. Zasadnicza różnica polega na tym, że klasy ukrywają swoją implementację komunikując się ze światem zewnętrznym wyłącznie przez metody, podczas gdy struktury danych mają zupełnie jawną postać, przez co nie potrzebują żadnych metod.
Przykład kodu obiektowego:

interface IShape
{
    double Area();
}

class Square: IShape
{
    private Point topLeft;
    private double side;
        
    public double Area()
    {
        return side*side;
    }
}

class Circle: IShape
{
    private Point center;
    private double radius;
    
    public double Area()
    {
        return Math.PI*radius*radius;
    }
}

Przykład kodu używającego struktur danych:

class Square
{
    public Point TopLeft;
    public double Side;
}

class Circle
{
    public Point Center;
    public double Radius;
}

class AreaCalculator
{
    public double Area(object shape)
    {
        if(shape is Square)
        {
            var s = (Square)shape;
            return s.Side * s.Side;
        }
        if(shape is Circle)
        {
            var c = (Circle)shape;
            return Math.PI * c.Radius * c.Radius;
        }
        throw new NoSuchShapeException();
    }
}

    Autor zauważa przy tym, że łatwo jest dodać nową klasę obiektu albo nową operację na strukturach danych (wystarczy dopisać nowy kod, a w starym nie trzeba wprowadzać żadnych zmian), natomiast trudno jest dodać nową metodę obiektów albo nowy typ struktury danych (stary kod trzeba będzie zmienić w każdym miejscu). Ponadto zauważa, że gdy używa się hybrydowych typów, które mają jawną implementację (gettery i settery) oraz zbiór metod, to mamy kod posiadający wady obu styli programowania - wtedy jakakolwiek zmiana jest utrudniona.
    Trudno nie zgodzić się z Robertem Martinem. Chciałbym do tego wszystkiego dorzucić jeszcze swoje trzy grosze. Zwróćmy uwagę, że istnieje wiele sytuacji, gdy ukrycie implementacji jest mniej naturalnym rozwiązaniem niż jej ujawnienie. W sytuacjach, gdy potrzeba funkcjonalności np.:

• przechowania danych odczytanych z bazy,
• przechowania danych odczytanych z XMLa,
• przechowywania danych wyświetlanych użytkownikowi na formularzu,
• przesyłania danych przez sieć,
• itp.

ujawnienie implementacji jest co najmniej bardziej naturalne, jeśli nie konieczne. Gdy korzystamy z mechanizmów takich, jak serializacja XML, to sam mechanizm wymusza na nas ujawnienie implementacji - wszystkie zmienne instancyjne muszą wtedy mieć gettery i settery. I nie łudźmy się w tym miejscu, że gettery / settery ukrywają implementację - to nie prawda. Dam konia z rzędem temu, kto powie mi, jaką cechą istotną z punktu widzenia projektowania różni się kod:

class Person
{
    public string FirstName { get; set; }
    public string LastName { get; set; }
}

od kodu:

class Person
{
    public string FirstName;
    public string LastName;
}

Widzicie jakąś różnicę? Ja nie widzę (i nie ma tutaj znaczenia, że w przykładzie powyżej użyłem właściwości automatycznych, a nie zwyczajnych z prywatnym polem pod spodem - to nic nie zmienia - implementacja jest ujawniona).
    Jaki praktyczny wniosek płynie z powyższych obserwacji? Według mnie, po pierwsze taki, że nie należy kurczowo trzymać się żadnego z góry określonego paradygmatu, tylko dostosować swój styl programowania do danego kontekstu. Jak pokazuje praktyka, nie każdy kontekst zachęca do stylu obiektowego. Ale gdy w danym module aplikacji obierze się dany styl, to należy być konsekwentnym i nie należy mieszać dwóch różnych styli (ani oszukiwać się, że klasa w stylu bean jest obiektowa).

Programowanie deklaratywne vs programowanie imperatywne

    Na wstępie skrótowo wytłumaczę, co rozumiem pod pojęciami zawartymi w tytule. Programowanie imperatywne polega na tym, że kod programu składa się z instrukcji (czyli rozkazów). Najbardziej typowe instrukcje to przypisania, wywołania procedur / metod, instrukcje warunkowe czy pętle. W programowaniu imperatywnym zmieniający się stan programu jest czymś naturalnym, a niedeterministyczne działanie procedur i metod - czymś często występującym.

    Zupełnie innym podejściem jest programowanie deklaratywne. W tym przypadku nie pisze się, co po kolei program ma robić, tylko jaką wartość chce się uzyskać. Czyli program deklaratywny nie jest zbiorem instrukcji, tylko zbiorem deklaracji właściwości obiektu, który chcemy uzyskać na wyjściu.

    Wśród powszechnie używanych języków generalnego zastosowania jest niewiele języków czysto deklaratywnych (czyli takich, w których nie ma instrukcji ani skutków ubocznych). Jedynym, jaki ja znam jest Haskell. Niemniej jednak jest cała masa języków prawie :-) deklaratywnych, które preferują deklaracje wartości nad instrukcjami, ale pozostawiają w swojej składni instrukcje np. żeby uprościć operacje I/O. Do takich języków należy cała "rodzina" ML (czyli m.in. OCaml i F#) a także kompilowana do JVM Scala.

    Język C# był na początku czysto imperatywny. Na szczęście, w każdej kolejnej wersji nabierał coraz więcej możliwości programowania funkcjonalnego (czyli deklaratywnego). Programując w najnowszej wersji (C# 4.0) często stoimy przed wyborem, czy zaimplementować coś imperatywnie, czy deklaratywnie.

    Jakiś czas temu zastanawiałem się, jak te dwa style przekładają się na wydajność programu i postanowiłem trochę poeksperymentować...

    Postanowiłem zaimplementować w miarę prosty algorytm na dwa sposoby, a następnie porównać czasy wykonania. Do implementacji wybrałem funkcję, która bierze na wejściu dwie listy i zwraca informację, czy druga lista jest podzbiorem pierwszej.

    Najprostsza implementacja imperatywna byłaby następująca:

public bool IsSubset<T>(List<T> first, List<T> second)
{
    foreach(T elem in second)
    {
        if(!first.Contains(elem))
            return false;
    }
    return true;
}

    Powyższe rozwiązanie ma złożoność kwadratową (a w zasadzie: prostokątną :-) ). Jeśli pierwsza lista będzie miała 100 000 elementów, a druga będzie jej 10 000-elementowym podzbiorem, to na moim komputerze taka metoda wykona się w czasie ok. 39 sekund. Typowy, średnio lubiący swoją pracę programista nawet nie będzie się zastanawiał, czy można to napisać lepiej, bo:

1. "terminy gonią",
2. "nie chce mi się",
3. "czas procesora jest tańszy niż czas programisty",
4. ...

    Trochę lepszy programista pomyśli, że da się napisać implementację działającą w czasie n * log n:

public bool IsSubsetBinarySearch<T>(List<T> first, List<T> second) 
    where T: IComparable<T>
{
    var array = new T[first.Count];
    first.CopyTo(array);
    Array.Sort(array);
    foreach (var elem in second) {
        if(Array.BinarySearch(array, elem) < 0)
            return false;
    }
    return true;            
}

Powyższe rozwiązanie dla tych samych danych "wypluje" wynik po czasie ok. 3,14 sekund. Mało kto szukałby w takiej sytuacji lepszego algorytmu, bo:

    a.  "terminy gonią",

    b.   ...

    z.  "klientowi nic się nie stanie, jak poczeka kilka sekund"

    Nie jest to jednak rozwiązanie optymalne, bo istnieje lepsza, liniowa implementacja:

public bool IsSubsetHashSet<T>(List<T> first, List<T> second)
{
    var hs = new HashSet<T>(first);
    foreach (var elem in second) 
    {
        if(!hs.Contains(elem))
            return false;
    }
    return true;
}

    Kod, który znajduje się powyżej to są już granice moich imperatywnych zdolności :-) Zaimplementowana w taki sposób metoda zakończyła działanie po 0,047 sekundy.

    Teraz przejdźmy do wersji deklaratywnej (używającej Linq to Objects):

public bool IsSubsetLinq<T>(List<T> first, List<T> second)
{
    return second
        .Except(first)
        .Count() == 0;
}

    Powyższa metoda jest wręcz matematyczną definicją problemu, jaki sobie postawiłem. Jest krótsza, prostsza i czytelniejsza nawet od najbardziej naiwnej wersji imperatywnej. A działa zaskakująco dobrze: kończy działanie po 0,063 sekundy! Co prawda, jest to troszkę więcej niż w przypadku optymalnej implementacji imperatywnej, ale:

• wygląda na to, że asymptotyczny czas działania jest taki sam (nieznaczna różnica),
• czas poświęcony na napisanie kodu był bardzo krótki,
• taki kod jest na tyle prosty, że może go napisać nawet słaby programista.

    Ten ostatni argument jest według mnie, szczególnie istotny. Programowanie funkcyjne jest, po przełamaniu początkowych trudności, po prostu łatwiejsze. Jeśli z niego zrezygnujemy na rzecz wyżyłowanych imperatywnych implementacji, to się chyba przejedziemy... Praktyka pokazuje (takie mam wrażenie), że łatwiej jest znaleźć dziewicę w akademiku niż optymalną implementację w dużym, imperatywnie napisanym systemie informatycznym :-)

Darmowe IDE do F#

    Ostatnio szukałem narzędzia, które pozwoli mi programować w domu w F#. Oczywiście, nie chciałem płacić za żadną licencję, ani tym bardziej pisać w kodu w notatniku (interesowało mnie IDE). Na razie w ofercie Microsoftu nie ma czegoś takiego, jak Visual F# Express Edition (pomimo, że F# jest w tej chwili jednym z trzech, obok C# i VB, głównych języków .NETa), więc postanowiłem sprawdzić inne darmowe środowiska.

    Na pierwszy ogień poszedł SharpDevelop. Środowisko to rzeczywiście pozwala na tworzenie projektów F#, ale nie oferuje żadnych narzędzi, do których przyzwyczajony jest każdy programista. Nie ma ani podpowiadania składni, ani dokumentacji funkcji po najechaniu na nią myszką, ani żadnych innych ułatwień. Jedyne, co mamy, to edytor kodu z (zawierającym bugi) kolorowaniem składni oraz integracja z kompilatorem. Według mnie, to zdecydowanie za mało, jak na IDE.

    Później znalazłem informacje, że MonoDevelop ma wtyczkę do F#, która wspiera podpowiadanie składni. Niestety, nie udało mi się jej zainstalować (a próbowałem na wszelkie możliwe sposoby). Z tego, co zdążyłem się zorientować wynika, że do najnowszej windowsowej wersji MonoDevelop wdarł się bug uniemożliwiający instalację wyżej wymienionej wtyczki.

    W zaistniałej sytuacji spróbowałem trzeciej opcji, która polegała na zainstalowaniu Visual Studio 2010 Shell, czyli czystego VS bez wsparcia dla żadnego języka, a następnie zainstalowaniu F#. Po tym zabiegu VS zaczął wspierać F# w pełnym zakresie (identycznie, jak w płatnej wersji), czyli osiągnąłem swój cel :-)

    Podobno można również programować w F# przy użyciu Emacsa, ale tej opcji nawet nie sprawdzałem, bo nie jestem przyzwyczajony do tego środowiska...