Zapach algorytmu

Od informatyki wymaga się przede wszystkim efektywności. Komputer ma być szybki, program - poprawny, a dialog z maszyną cyfrową - ergonomiczny. Czy jest w tej dziedzinie miejsce na pierwiastki estetyczne?

Od informatyki wymaga się przede wszystkim efektywności. Komputer ma być szybki, program - poprawny, a dialog z maszyną cyfrową - ergonomiczny. Czy jest w tej dziedzinie miejsce na pierwiastki estetyczne?

Funkcjonalna kostka

Tworzenie oprogramowania opiera się na dwóch fundamentach: naukowo udokumentowanej teorii i rzemieślniczej perfekcji praktyki. Tak dzieje się zresztą niemal w każdej dziedzinie ludzkiej działalności. Architekci projektują domy, powierzając ich wykonawstwo murarzom. Prawdą jest, że dobry rzemieślnik postawiłby dom i bez architekta. Oczywiście, byłaby to konstrukcja wykonana wg planów bardzo przeciętnej natury. Powiedzmy prostopadłościan przykryty dwoma prostokątami, tworzącymi dach. Zapewne i architekt mógłby nabrać wprawy w robieniu kielnią i (pomijając ograniczenia czysto fizyczne) obyć się bez robotników.

Jedni i drudzy są oczywiście potrzebni, choć granica między teorią a praktyką nie zawsze jest tak wyraźna, jak w tym przykładzie.

Pozostańmy jeszcze chwilę w architektonicznym kręgu. Dom typu "kostka" może być znakomicie funkcjonalny, a jednak chcemy, aby otaczała nas bardziej elegancka architektura. Dlaczego nie wymagać tego od innych wytworów techniki? Elegancja nie musi przecież oznaczać braku efektywności, wręcz przeciwnie: trudno sobie wyobrazić, że program napisany "ze smakiem" zwyczajnie się "wiesza". Jest zatem i w informatyce miejsce na jeszcze jeden pierwiastek: piękna i sztuki. W kontekście bitów i bajtów twierdzenie takie może w pierwszej chwili zaskakiwać. Zresztą, gdyby było głoszone przez teoretyków estetyki nie znających tajników oprogramowania, brzmiałoby niezbyt przekonywająco. Ale właśnie tu, na łamach fachowego tygodnika, możemy otwarcie poruszać i takie kwestie.

Niejeden praktyk zapyta: właściwie po co ta filozofia? Program ma "chodzić" i wszystko. Ba. Wszak chodzić można z gracją albo poruszać się jak słoń. Warto dążyć do informatycznego ideału, gdyż doskonałość po prostu się opłaca, również finansowo. Przecież koniecznym warunkiem jej osiągnięcia jest profesjonalizm, a obok tego wymogu nikt nie ośmieli się postawić znaku zapytania.

Forma bez treści

Jak się ubrać, by jednocześnie być eleganckim i praktycznym? Rzeczywistość nie szczędzi informatykom takich dylematów i to nie w związku z ich strojami, ale przedmiotem pracy. W branży odzieżowej przerost formy nad treścią sprawdza się na pokazach mody, ale nie na ulicy. Czy podobne analogie można znaleźć w metodologii programowania? Ależ tak! Jakże zgrabna jest np. teoria relacji Codda. Właś-ciwie na tej garści reguł opiera się większość współczesnych systemów bazodanowych. Dopowiedzmy jednak rzecz do końca: w praktyce z owych reguł nierzadko pozostaje garść wiórów, no może z pewnymi dodatkami prawdziwych "drew".

Przyjrzyjmy się zatem bliżej bazom danych w tym kontekście. Ilu programistów zna, a co ważniejsze stosowało, algorytm dekompozycji Codda-Fagina do projektowania schematu bazy danych? Bez nerwów, nie ma potrzeby gwałtownego rzucania się do fachowej literatury. Zarówno ta metoda, jak i jej podobne (np. Rissanena czy Bernsteina) wykazują wiele wad i ograniczeń. Wiadomo że w praktyce brutalnie "przycina się" wygląd relacyjnych tabel do aplikacji z nich korzystających. Co tam postaci normalne (3NF i inne) - ważne, żeby użytkownik szybko dostał dane na ekran. Takie są realia. Tylko algorytmu żal.

Perły i cegły

Dawno, dawno temu, w epoce kart perforowanych, co poważniejsze (grubsze) programy siłą rzeczy przypominały swym wyglądem papierowe cegiełki. Te proste formy czasami kryły jednak prawdziwe rarytasy algorytmiczne. Aby się o tym przekonać, wystarczy sięgnąć po książkę Johna Bentleya "Programming Pearls". Rzecz dostępna jest również w tłumaczeniu na jęz. polski i ukazała się w ostatnich latach nakładem WNT. Autor podaje przykłady eleganckich algorytmów sprzed ćwierć wieku, czyli odległych o kilka informatycznych epok wstecz. To najlepszy dowód odporności piękna na ząb czasu, również piękna software'owego. Zresztą owo piękno objawia się w dobrze znanych informatykowi wymiarach:

  • prawidłowym projektowaniu programów

  • poprawności specyfikacji problemów

  • wyborze odpowiedniego algorytmu

  • spójności struktur danych

  • poprawności programu wraz z jej dowodzeniem.

    Nie odbierając czytelnikowi przyjemności indywidualnego zapoznawania się z "perełkami", spróbujmy odpowiedzieć na pytanie, co można znaleźć u źródeł elegancji oprogramowania. Aby odpowiedzieć na to pytanie, wystarczy przyjrzeć się podstawowym konstrukcjom, na których opiera się każdy algorytm. Jedną z nich jest instrukcja wyboru - case. Do ustalenia uwagi przyjmijmy składnię pascalową (podobne możliwości ma switch/case w C, miłośnikom Cobola warto zaś przypomnieć o istnieniu operacji evaluate). Zapoznajmy się teraz z dwoma prostymi fragmentami kodu, ustalającymi numer kwartału w roku dla zadanego numeru miesiąca.

    Najpierw schodkowa konstrukcja if-then-else:

    if (miesiąc >= 1) and (miesiąc <= 3)

    then write ("I kwartał")

    else

    if (miesiąc >= 4) and (miesiąc <= 6)

    then write ("II kwartał")

    else

    if (miesiąc >= 7) and (miesiąc <= 9)

    then write ("III kwartał")

    else

    write ("IV kwartał");

    Z kolei wariant korzystający z case:

    case miesiąc of

    1..3: write ("I kwartał");

    4..6: write ("II kwartał");

    7..9: write ("III kwartał")

    else write ("IV kwartał");

    end;

    Prawda, że prościej? Ale czy na pewno bardziej elegancko? W tym przypadku nie warto "czepiać się" wariantu drugiego i szybciej się go "czyta", gdyż nie musimy się zastanawiać, jak przebiega sterowanie - inaczej niż w przypadku zagnieżdżających się operacji "jeżeli-to". Mechaniczne preferowanie instrukcji wyboru może być jednak niebezpieczne (mało eleganckie). W ogólnym przypadku mamy bowiem do czynienia ze schematem:

    case S of

    O1;

    O2;

    ...

    else

    Ok;

    end;

    Wynika z tego, że taka struktura soft- ware'owa zachęca do nadużywania jej jako swego rodzaju wytrychu czy chwytu programistycznego. Oto bowiem wartość selektora S, decydującego o wykonaniu określonych instrukcji wewnątrz selekcji, ustalana jest na zewnątrz jej, co tworzy znaki zapytania co do wykonania się (bądź nie) poszczególnych gałęzi selekcji tylko na podstawie badania jej poprawności. Oczywiście, w praktyce niewielu informatyków zastanawia się nad takimi kwestiami, już jednak te niewielkie przykłady wskazują na łatwy do przewidzenia wniosek, że dążenie do zachowania elegancji oprogramowania wymusza kompromisy wobec jego innych cech.

    Na okrągło

    Pozostając na poziomie podstawowych "zwrotów i wyrażeń" języków programowania, nie sposób pominąć rekursji (rekurencji). Zróbmy wcześniej tylko mały wtręt lingwistyczny. Otóż matematyka tradycyjnie operuje wzorami rekurencyjnymi (łac. recurrens = powracający), natomiast rekursja pochodzi od innego określenia łacińskiego - recursus - co ongiś oznaczało odwołanie się od decyzji instytucjonalnej. Jak wiadomo, piśmiennictwo informatyczne śmiało posługuje się dwoma wyrazami. Wróćmy na chwilę do matematyki, tej informatyki bez komputerów, i cofnijmy się do roku 1202, do czasów Leonarda z Pizy zwanego Fibonaccim.

    Wtedy to ów genialny Włoch (jemu m.in. zawdzięczamy stosowanie cyfr arabskich) określił ciąg liczb naturalnych nazwany jego imieniem. Przytaknie tu nie tylko matematyk, ale i... biolog! Wiadomo bowiem, że liczby pędów rosnącej rośliny w kolejnych latach tworzą ten właśnie ciąg, definiowany jako: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55... No dobrze i co z tego? Widać, że każda kolejna liczba jest sumą dwóch poprzednich (nie dotyczy to dwóch pierwszych liczb). Wielka filozofia! Spokojnie, zaraz będzie i wielka elegancja. Oto poprzednio przytaczane cyferki da się zapisać w bardzo zwarty sposób:

    an = an-2 + an-1

    A to już jest czysta rekurencja. Definicja sama od siebie zależna i samo się definiująca. Czyż może być coś piękniejszego? Toż to piękno przyrodniczych cudów, jawiące się fraktalami śnieżynek czy liści. Uporządkowany chaos i chaotyczny porządek. A więc najnowocześniejsze teorie szukające opisu dla procesów otaczających nas w mikro- i makroświecie.

    Cząstką tych procesów jest także bieg programu i jego elegancja. Przyjrzyjmy się temu na podstawie żelaznego przykładu algorytmiki - silni. Jeśli spojrzymy na jej rekurencyjny wzór:

    N! = 1 dla N = 0 albo N(N-1)! dla N > 0

    to algorytm rekurencyjny aż się prosi, żeby go napisać (zróbmy to w algolopodobnym języku publicystycznym):

    procedure SILNIA (N)

    SILNIA :=

    if N = 0 then 1

    else N x SILNIA (N - 1)

    end

    Oczywiście, ten sam efekt można uzyskać nierekurencyjnie i należy zakładać, że taki algorytm będzie liczył szybciej, ale wersja rekurencyjna jest bardziej zrozumiała, czyli bardziej elegancka.

    Warto jednak zauważyć, że prześledzenie przebiegu sterowania wersji rekurencyjnej może być (w szczegółach) trudniejsze. Właściwie nie obejdzie się tu bez operowania stosem i wektorami wywołań parametrów. Wystarczy powiedzieć, iż podczas konkretnych obliczeń procedura będzie wielokrotnie sama siebie wywoływać, po to by wracając z kolejnych poziomów wywołań, dojść do żądanego wyniku niejako od końca. Mimo to możliwość korzystania z procedur (funkcji) samo się wywołujących jest kusząca. Jest w takim programie pewien pierwiastek informatycznego ideału: algorytmu samouczącego się.

    Dochodzimy przy tym do cechy stanowiącej fundament technologii informatycznych. Cechy, bez której nie mogą się obejść rozważania dotyczące elegancji oprogramowania. Jest nią powtarzalność. Nihil novi sub sole (nic nowego pod słońcem) czy panta rhei - chciałoby się powiedzieć. Wszystko płynie. Ale jak?! Heraklit z Efezu był przekonany, że nie wchodzi się dwa razy do tej samej rzeki. Czy ważyłby się i dzisiaj na takie stwierdzenie, gdyby przyjrzał się komputerowym programom, biegnącym tysiące razy w tak samo zdefiniowany sposób? Zawierającym w swych "trzewiach" pętle, na okrągło i do znudzenia, po miliony razy, pożerające liczby, bity i bajty.

    Potęga nudy

    Na kursach programowania powiada się adeptom tej sztuki, że algorytm jest pewną receptą. Niczym przepis z książki kucharskiej. Wykonuje się nawet schematy blokowe algorytmu gotowania kartofli. Słusznie. Różne, mądre skądinąd, definicje algorytmów rzadko odpowiadają na pytanie: Po co pisze się takie "książki kucharskie"? Po co właś-ciwie pisze się program? Mówi się o wykonywalności algorytmu, ale czy wykonywalność oznacza i opłacalność? To prawda, że mistrzowie eleganckiego programowania zalecają rozbicie prostej sekwencyjności programu modularyzacją i pisanie procedur (podprogramów) nawet wtedy, gdyby miały się wykonać tylko jeden jedyny raz.

    Ale tak naprawdę usprawiedliwieniem napisania programu jest możliwość jego wielokrotnego wykonywania. Powtarzalność! Powtarzalność! Nawet gdyby program wykonał się tylko jeden jedyny raz, wyrzucając pierwszy milion liczb pierwszych, znajdziemy ją na poziomie pętli języka wyższego poziomu, nie mówiąc o poziomie maszynowym. Piękno i elegancja oprogramowania są zatem nierozerwalnie związane z powtarzalnością. Tak, powiedzmy wprost: ze swego rodzaju monotonią. Z takiego stwierdzenia wieje nudą. Jak to, ciągle to samo? Powiedzmy: ciągle na nowo po staremu, jeśli ktoś woli takie dictum.

    Nie ma co się zżymać. Od powtarzalności i tak nie uciekniemy. To fundamentalna cecha otaczającej nas rzeczywistości, naszej cywilizacji, ewolucji, pracy, procesów społecznych czy biologicznych. Zauważmy teraz, że, paradoksalnie, elegancja oprogramowania bierze się właśnie z chęci odejścia od owej powtarzalności! A owe pętle i rekursje, o których wspomnieliśmy? To właśnie jest "dyskretny urok" algorytmu. Wykonywalny program jest powtarzalny. Tak. Ale miast powtarzać w kółko to co jest do wykonania, wiążemy kosmos obliczeń jedną zgrabną pętelką. Czyż to nie piękne? Zatem piszemy programy dla ich powtarzalności, ale i ucieczki od niej. Właśnie na granicy kompromisu między tymi dwoma różnymi uwarunkowaniami powinniśmy szukać elegancji oprogramowania.

    Miary elegancji

    Program o dużej czy wręcz nieograniczonej powtarzalności (powielarności) musi być elegancki. Musi być odpowiednio stabilny i odporny na ewentualne zakłócenia. Musi być poprawny i jednoznaczny. Czy musi być ergonomiczny? Oczywiście. W przeciwnym razie użytkownik nie zechce, aby powtarzały się jego negatywne wrażenia związane z określoną aplikacją. Elegancka powtarzalność nie oznacza wszakże prostej reprodukcji, ale właś-nie tworzenie otwartych, wielowariantowych, elastycznych algorytmów, które w systemowych ramach potrafią zamknąć dynamikę heterogenicznych wymagań rzeczywistości. A co z szybkością? Przecież program może "powtarzać się" wolno.

    To prawda, tyle że z dwóch podobnych programów, ten szybszy jest po prostu "bardziej powtarzalny". Tu dochodzimy do związków elegancji oprogramowania z miarami złożoności, które da się definiować znacznie dokładniej niż wiele cech wymienionych poprzednio. Przypomnijmy, że istnieją dwa klasyczne rodzaje złożoności oprogramowania: czasowa i pamięciowa. W pierwszym przypadku mówimy o funkcji określającej czas wykonania się algorytmu w zależności od rozmiaru zadania. Złożoność pamięciową definiuje się analogicznie w odniesieniu do pamięci, aczkolwiek w praktyce odgrywa ona na ogół mniejsze znaczenie.

    W gruncie rzeczy problematyka roku 2000 jest efektem optymalizowania złożoności pamięciowej algorytmów w przeszłości. Ale dziś nie zwykliśmy przesadnie liczyć się z pamięcią. Prawo Moore'a powoduje, że w podobnie radosny sposób podchodzimy do szybkości komputerów. Maszyna za wolna? "Za chwilę" i tak wymieni się ją na nową, szybszą. Albo można dokładać procesor po procesorze, aż do uzyskania pożądanego efektu. W taki właśnie sposób komputer IBM "położył na łopatki" najlepszego szachistę świata. Czy warto wymyślać coraz bardziej inteligentne i eleganckie algorytmy, skoro wystarczy "brutalna siła"?

    No cóż, prawu Moore'a można by przeciwstawić prawo Amdahla, opisujące granice złożoności, poza którymi opłacalność zwiększania liczby procesorów w konfiguracji zaczyna szybko maleć. Niezależnie od tego, o szybkości wykonania się wielu algorytmów, rozwiązujących kompleksowe problemy, nadal decyduje ich złożoność obliczeniowa. Zaproponowany przez naszego wybitnego matematyka i twórcę teorii grafów Kazimierza Kuratowskiego algorytm ich planaryzacji (1930 r.) ma złożoność rzędu n6. Oznacza to, że musi on wykonać milion podstawowych (umownych) operacji dla splanaryzowania grafu o dziesięciu wierzchołkach. Jeśli na każdą z tych operacji (może to być np. określona procedura) potrzeba jednej sekundy, to całość zajmie ponad 10 dni nieprzerwanych obliczeń.

    W latach 60. Goldstein zaproponował szybszy algorytm o złożoności n3. Łatwo wyliczyć, że przy podobnych założeniach program wykonałby się już po niespełna 17 minutach. Nowsze algorytmy tego typu mają liniową złożoność obliczeniową i są wprost proporcjonalne do n. A to oznacza dalsze skrócenie czasu wykonania się zadania do 10 sekund. W tym przypadku i graf o 1000 wierzchołkach nie byłby straszny. To tylko 1000 sekund, o czasach wykonania się bardziej złożonych obliczeniowo algorytmów lepiej już nie mówmy - to się po prostu w kalkulatorze nie mieści.

    Poza wymienionymi metrykami oprogramowania istnieje wiele innych, np. cyklomatyczne, APF (Analiza Punktów Funkcyjnych), COCOMO (Boehma), złożoność struktury modułowej, złożoność otwartych cykli komunikacyjnych i inne.

    Czysta elegancja oprogramowania, jako wartość silnie kontekstowa czy wręcz estetyczna, pozostaje niemierzalna. Podobnie zresztą dzieje się z innymi rodzajami informacji (program jest rodzajem informacji) i zapewne długo jeszcze będziemy czekać na wyjaśnienie, słabo jak dotąd poznanej, istoty samej informacji.

  • W celu komercyjnej reprodukcji treści Computerworld należy zakupić licencję. Skontaktuj się z naszym partnerem, YGS Group, pod adresem [email protected]

    TOP 200