Archive for Programming

Quine-tesencja dziwności

2008-04-01 20:22

Jak powszechnie wiadomo, obchodzimy dzisiaj tak zwany Prima Aprilis. Dosłownie mówiąc, świętujemy więc fakt, że dzisiejsza data to 1 kwietnia. To oczywiście nie jedyny dziwny akcent tego dnia – na przykład dlatego, iż nie omieszkam przy tej okazji zająć się pewną interesującą oraz dziwną (to słowo zdecydowanie kluczowe) ciekawostką. Chodzi o quines.

Quine to program napisany w dowolnym języku (i nie tylko), którego jedynym zadaniem wyprodukowanie pewnego specyficznego rezultatu. Wypisuje on bowiem na wyjściu… swój własny kod źródłowy. Na pierwszy rzut oka można pomyśleć, że takie programy nie istnieją – albo że wręcz nie mogą istnieć! Bo przecież jeśli kod ma coś wypisywać, to “coś” musi być w tym kodzie zawarte. Czyli każda instrukcja typu print "a" implikuje konieczność wypisania na wejściu tekstu "print \"a\"". Ale instrukcja, która ten tekst pokazuje, sama też musi być wyświetlona… Mamy więc print "a", print "print \"a\"", print "print \"print \\\"a\\\"\"", i tak dalej. Błędne koło!
Lecz quines istnieją. Każdy program tego typu składa się zasadniczo z dwóch części:

  1. Napisu zawierającego stałe elementy programu, takich jak różnorakie dyrektywy #include, using, import, nagłówki funkcji main i inne podobne konstrukcje
  2. Pewnej sztuczki, pozwalającej to błędne koło przerwać: popularne jest na przykład zmyślne użycie znaczników formatujących w funkcjach typu printf

Krótkim, bo niezawierającym dużej ilości zbędnych śmieci pierwszego typu przykładem jest poniższy quine napisany w Pythonie:

  1. a='a=%s;print a%%`a`';print a%`a`

Jak widać, cała treść programu jest zapisana w pojedynczej zmiennej. W miejscu, gdzie w tym “wewnętrznym” kodzie powinna wystąpić wartość owej zmiennej, unikamy sprzężenia zwrotnego poprzez wstawienie znacznika formatującego (czyli %s). Zostanie on potem zastąpiony dopiero w instrukcji drukującej print a%`a` (w Pythonie print a%b to odpowiednik printf(a, b) z C).
Potrzebny jest jeszcze jeden trik, który pozwoli wypisać cudzysłowy (albo apostrofy) bez konieczności ich espace‘owania (które prowadziłoby do nieskończonego ciągu: ", \", \\\", \\\\\\\"…). Tutaj użyto operatora ` (backtick) specyficznego dla Pythona; inną możliwością jest wydrukowanie cudzysłowu przy pomocy jego kodu ANSI (34).

Widać więc, że quines wcale nie przeczą związkom przyczynowo-skutkowym, następstwu zdarzeń, nie powodują paradoksu dziadka ani zniszczenia Wszechświata :] Oczywiście nie mieszczą się też w nawet najszerzej pojętej kategorii rzeczy przydatnych – ale na dzisiejszą okazję są jak znalazł :)

Tags:
Author: Xion, posted under Programming » 1 comment

Nagłówki i przestrzenie nazw

2008-03-30 16:11

Niestety, przestrzenie nazw w C++ nie mają takiego wdzięku jak pakiety w Javie czy assemblies w .NET. Zwłaszcza w połączeniu z plikami nagłówkowymi potrafią one sprawić nieco problemów. Jeśli bowiem nie będziemy uważali, to możemy dość łatwo zniwelować korzyści, jakie płyną z ich używania.

Ale po kolei. Jeśli mamy do czynienia z modułem kodu (plikiem .cpp), to możemy bez żadnych skrupułów umieszczać w nim deklaracje using lub using namespace. Jeśli tylko nie prowadzi to do niejednoznaczności, wszystko jest w porządku, bowiem zasięg tych deklaracji ogranicza się tylko i wyłącznie do tego jednego pliku.
Gorzej jest niestety z plikami nagłówkowymi. Ponieważ włączane są one tu i ówdzie przy pomocy dyrektywy #include, nie można tak po prostu wpisywać w nich deklaracji using namespace. Zostałyby one bowiem rozpropagowane do wszystkich plików, które dany nagłówek włączają, efektywnie niwelując wszelkie korzyści zamknięcia fragmentów kodu w przestrzeń nazw. Bo co to za namespace, który wszyscy “rozpakowują” i przenoszą jego zawartość do przestrzeni globalnej?…

Dlatego nie ma rady: w plikach nagłówkowych można używać wyłącznie nazw kwalifikowanych – poprzedzonych wszystkimi nazwami przestrzeni, jak np. XC::Base::GC::BlockInfo. W przeciwnym wypadku na pewno zaśmiecimy sobie którąś z przestrzeni (najczęściej globalną) identyfikatorami, które do niej nie należą – co będzie widoczne w systemach podpowiadania takich jak IntelliSense.

Tags: , ,
Author: Xion, posted under Programming » 4 comments

Trzy funkcje semaforów

2008-03-28 18:10

Podobno programowanie równoległe jest trudne: fakt, że kilka czynności może być wykonywanych “jednocześnie”, wprowadzać ma duże zamieszanie i komplikować życie. Nie zgadzam się! Nawet jeśli procesy lub wątki działają w tym samym czasie, to jeszcze nie jest powód do zmartwień. Prawdziwe problemy zaczynają się przecież dopiero wtedy, gdy trzeba ich działanie zsynchronizować :-)
A do tego przydają się na przykład semafory. Przy ich pomocy których można zresztą zrealizować większość popularnych mechanizmów blokowanej synchronizacji, jak choćby sekcje krytyczne. Jednak cała sztuka polega zawsze na tym, żeby użyć ich w sposób odpowiedni do danego zastosowania i nie nabawić się przy tym zagłodzenia, zakleszczenia (deadlock) lub innych “równoległych” błędów.

Semafor (kolejowy)Istnieją oczywiście tzw. schematy synchronizacji, lecz ich przydatność jest mniej więcej kilkukrotnie mniejsza niż chociażby wzorców projektowych dla programowania obiektowego. Zauważyłem jednak, że sytuacje, w których używa się semaforów (lub podobnych obiektów) można zakwalifikować do jednej z trzech grup, z których każda następna jest ugólnieniem poprzedniej:

  • Prostym i częstym przypadkiem jest wykorzystanie semafora do ochrony jakiegoś zasobu. Wówczas każdy proces (lub wątek – na tym poziomie nie ma to znaczenia) musi sprawdzić semafor przed dostępem do tego zasobu – czyli np. przed zapisem do współdzielonej pamięci.
    1. Wait (S);   // czekamy na semaforze
    2. /* praca z zasobem */
    3. Release (S);   // zwalniamy semafor

    W ten sposób tworzy się oczywiście sekcja krytyczna, bo tylko jeden proces uzyska do naszego zasobu dostęp. Wygodne jest tutaj myślenie o semaforze jako obiekcie ochraniającym zasób, a nie fragment kodu. Oczywiście na samym początku taki semafor jest zwykle opuszczony.

  • Niekiedy semafor służy do oczekiwania na spełnienie jakiegoś warunku. Weźmy na przykład serwer sieciowy, który na jednym wątku nasłuchuje połączeń (operacja blokująca), a w kolejnym wykonuje już jakieś czynności przygotowawcze dla nowego klienta. Gdy ów klient faktycznie się połączy, ten drugi wątek powinien się zająć jego obsługą, a pierwszy nadal nasłuchiwać nowych połączeń.
    Skąd ten drugi wątek we, że jest już nowy klient? Ano “wisi” on na (początkowo podniesionym) semaforze. Wątek nasłuchujący podniesie go wtedy, gdy połączenie z klientem zostanie nawiązane. Semafor sluży więc do sprawdzania pewnego warunku: czy klient jest już połączony.
  • W najbardziej ogólnej wersji semaforem kontrolujemy dostęp do różnych “miejsc” w kodzie. Każde takie miejsce można sobie wyobrazić jako pokój. Semafory będą wtedy drzwiami, stopień ich uchylenia – wartością licznika, zaś procesy będą osobami, które próbują się przez rzeczone drzwi przeciskać celem przejścia z jednego miejsca do drugiego. Wtedy wystarczy “tylko” ustalić warunki zamykania i odmykania drzwi – i już :) Rzecz w tym, że konstrukcja całego układu tych pomieszczeń nie jest w ogólności rzeczą prostą.

Bo programowanie równoległe – którego synchronizacja jest nieodłączną częścią – to jednak ciężki kawałek chleba ;]

Tags:
Author: Xion, posted under Programming » Comments Off on Trzy funkcje semaforów

Wiosenne porządki #2 – Ujednolicanie interfejsu

2008-03-26 21:45

Jedną z bardziej denerwujących cech bibliotek, z jakimi można się zetknąć, jest ich wewnętrzna niespójność pod względem interfejsu. Dotyczy to na przykład drobnych kruczków związanych z postacią wywołań funkcji i metod. Znanym przedstawicielem tego gatunku “kwiatków” są chociażby standardowe funkcje C(++) od zapisu do plików – fprintf i fputs:

  1. int fprintf (FILE* stream, const char* format, ...);
  2. int fputs (const char* str, FILE* stream);

Obie działają podobnie (z dokładnością do formatowania w fprintf), lecz różnią się irytującym szczegółem: miejscem parametru określającego plik (typ FILE*), do którego zapisujemy. Nietrudno się tu pomylić i to niekoniecznie wtedy, gdy korzystamy z obu funkcji w tym samym kodzie.

Podobna niejednolitość jest na szczęście w miarę łatwa do wykrycia i usunięcia – oczywiście pod warunkiem, że mówimy tutaj o bibliotece, której nie wykorzystuje jeszcze nikt postronny. Oprócz niespójnych prototypów funkcji powinniśmy jeszcze zwrócić uwagę na:

  • Nazwy metod wykonujących podobne czynności. Dotyczy to na przykład metod dostępowych, służących symulowaniu właściwości. Powinny one być zgodne z jednym szablonem nazewnictwa, np. Get/SetSomething, IsEnabled, itd. Podobnie metody z nazwami zawierającymi czasowniki “znaczące”, takie jak load, create, read, write powinny przede wszystkim robić to, co owe czasowniki wyrażają.
  • Sensownie dobrane przeciążenia funkcji i parametry domyślne. Wypadałoby bowiem, aby w typowych sytuacjach możliwe było użycie krótszych wywołań z mniejszą ilością parametrów niż wtedy, gdy musimy zrobić coś specjalnego i bardziej skomplikowanego. Zazwyczaj osiągnięcie tego nie jest trudne i sprowadza się do nadania jakimś parametrom rozsądnych wartości domyślnych (przy ich ewentualnym przestawieniu) lub dopisaniu prostych wersji przeciążonych dla danej funkcji.
  • Nazwy parametrów w deklaracjach i definicjach funkcji. W C(++) nie musimy ich pisać w deklaracjach, ale jest to bardzo wskazane, gdyż ułatwia korzystanie z plików nagłówkowych jako swego rodzaju “spisu treści”. Jednak z drugiej strony musimy wtedy dbać, żeby w obu miejscach były one ze sobą zgodne. W przeciwnym razie możemy bowiem napotkać bardzo przykre błędy, jeśli zmienimy kolejność argumentów funkcji tego samego typu.

Nanoszenie podobnych poprawek jest oczywiście dość skomplikowaną operacją, ale wciąż nie ingeruje ona ani w projekt biblioteki, ani – z grubsza – w sposób, w jaki końcowy programista ma jej używać. Mimo to podejrzewam, że w przypadku mojego siln… tj. kodu będzie to dosyć czasochłonne. Całkiem często zmieniałem bowiem swoje upodobania odnośnie kwestii, które wymieniłem powyżej (i których lista nie jest też pewnie kompletna).
Ale cóż, wiosna dopiero się zaczyna, więc czasu – przynajmniej teoretycznie – jest dużo ;-)


Author: Xion, posted under Programming » 2 comments

Wiosenne porządki #1 – Odprzedrostkowywanie klas

2008-03-22 18:21

Przez ostatnich kilkanaście tygodni nie zaglądałem właściwie do kodu swojego siln… tzn. biblioteki (;P). I chociaż entropia kodu, którym nikt się nie zajmuje, nie powinna w zasadzie rosnąć, od czasu do czasu przydadzą się większe lub mniejsze porządki. Zwłaszcza jeśli w międzyczasie zmieniły się nasze poglądy dotyczące tego, jak programować trzeba, a jak nie należy.

Mniej więcej coś takiego przytrafiło mi się jakiś czas temu. Dość długo byłem zwolennikiem tzw. notacji węgierskiej. Jest to pewna reguła odnosząca się do nazw wprowadzanych do kodu źródłowego – takich jak nazwy zmiennych, klas, funkcji, itd. – która postuluje, aby poprzedzać je pewnymi przedrostkami. Prefiksy te mają dostarczać pewnych informacji, mówiąc na przykład, czy mamy do czynienia z klasą, strukturą czy ze zmienną. W tym ostatnim przypadku dodatkowo rozróżniamy też zmienne lokalne od pól klas, a także wprowadzamy przedrostki identyfikujące ich typy. Produktem tych zasad mogą być ostatecznie nazwy typu CFoo::m_pstrVar.
Prawdopodobnie cała ta zabawa była przydatna wtedy, gdy nie dysponowało się zintegrowanymi środowiskami programistycznymi (IDE). Teraz nietrudno jest poznać typ zmiennej: wystarczy najechać kursorem na dowolną nazwę w kodzie, a w podpowiedzi dostaniemy jego deklarację. Proste i praktyczne.

Podejrzewam, że nadmierna sympatia do notacji węgierskiej wzięła się u mnie stąd, że stykałem się z nią dawno temu w kodach napisanych w C i C++, z których – nie ukrywajmy – niewiele wtedy rozumiałem :) Tym więc mogę usprawiedliwić fakt, że bezmyślnie przejąłem ten poroniony w gruncie rzeczy sposób nazewnictwa. Na szczęście nigdy nie jest za późno, aby nawrócić się na właściwą drogę, co też niniejszym czynię ;]
Wyrzucenie wszystkich prefiksów chociażby z nazw zmiennych byłoby sporym zadaniem, zwłaszcza że mówimy o kodzie liczącym przecież 30 tysięcy linii (co jest, przy okazji, bardzo dziwne, jeśli się weźmie pod uwagę jego mizerię funkcjonalną :)). Dlatego rozpoczynam skromnie: od poprawienia nazw wszystkich klas i struktur tak, aby nie były opatrzone żadnymi “ozdobnikami”. Nie ukrywam, że w ten sposób staram się upodobnić do konwencji stosowanej w .NET i JVM. Bo przecież dobre wzorce są po to, aby je naśladować…


Author: Xion, posted under Programming » 12 comments

Przekierowanie standardowych strumieni

2008-03-21 10:33

Dawno, dawno temu miałem dość oryginalny pomysł na program użytkowy. Miała to być (o wiele) lepsza wersja konsoli Windows, której wyższość miała się objawiać w wyglądzie oraz możliwościach; pewne inspiracje czerpałem tutaj z terminali linuksowych oraz basha (nie, nie chodzi tu o serwis z cytatami z IRC-a ;P). Jak większość “genialnych” pomysłów, także i ten nie doczekał się realizacji. Przyczyną było to, iż nie za bardzo wówczas wiedziałem, jak można zapewnić, aby aplikacje konsolowe funkcjonowały w ramach projektowanego terminala tak, jak to robią w domyślnym oknie konsoli w Windows. Większość problemu rozbijała się o to, jak pobierać dane przez ów program produkowane i jak przekazywać do niego te wpisywane przez użytkownika.

Przekierowane standardowe wyjście
Konsolka mała i ciasna, ale własna

Jako że było to bardzo dawno temu, nie znałem wtedy jeszcze takich terminów jak ‘standardowe wejście/wyjście’, ‘proces potomny’ czy ‘pipe‘, które byłyby tutaj bardzo pomocne. Dowiedziałem się o nich więcej dopiero znacznie później, przy czym wiedza ta w większości odnosiła się do systemu zgoła innego niż Windows :)
Pomyślałem jednak, że do problemu można by wrócić – zwłaszcza, że pytanie o to, jak uruchomić program z przekierowanym wejściem i wyjściem, pojawia się stosunkowo często. Okazało się, że nie jest to specjalnie trudne i sprowadza się właściwie do trzech kroków – z których tylko pierwszy może być nieco zakręcony. Cała procedura (w Windows) może wyglądać na przykład tak:

  1. Tworzymy dwie lub trzy jednokierunkowe rury (pipe, tworzone funkcją CreatePipe), które posłużą nam do odbierania wyjścia od i dostarczania wejścia do procesu potomnego. Należy przy tym zwrócić uwagę na dwie rzeczy:
    • Kij ma dwa końce i rura też, więc trzeba uważać, aby właściwie je zidentyfikować. Jeden koniec każdego pipe‘a podamy do procesu potomnego, zaś drugi zachowamy dla siebie. Ważne jest, aby były to właściwe końce pod względem kierunku przepływu danych – i tak w przypadku przekierowywania standardowego wejścia, powinniśmy podać procesowi potomnemu uchwyt do czytania, zaś po stronie naszej aplikacji wykorzystywać uchwyt do pisania.
    • Powstałe uchwyty będziemy chcieli dziedziczyćw procesie potomnym, zaś Windows dopuszcza to tylko wtedy, kiedy wyraźnie taką chęć określimy przy tworzeniu danego uchwytu. Robi się to, wypełniając jedno pole struktury SECURITY_ATTRIBUTES (tak, tej którą w 95% przypadków się ignoruje) i przekazując ją do funkcji tworzącej pipe.
    • Oprócz standardowego wejścia (STDIN) i wyjścia (STDOUT), istnieje jeszcze standardowe wyjście błędów (STDERR), które również możemy chcieć przekierować. Stąd może być konieczny trzeci pipe, o takim samym przypisaniu końców jak ten od STDOUT.
  2. Tworzymy proces potomny (CreateProcess). Musimy mu podać właściwe końce rurek w strukturze STARTUPINFO oraz poinstruować Windows, by były one wykorzystywane (flaga STARTF_USESTDHANDLES). Ponadto musimy wskazać, że chcemy dziedziczyć uchwyty i że utworzony proces konsolowy nie powinien pokazywać okienka (CREATE_NO_WINDOW) – to już przekazujemy w parametrach CreateProcess.
  3. Obsługujemy wejście i wyjście procesu potomnego. Na to drugie (oraz na zakończenie procesu potomnego) możemy czekać przy pomocy funkcji w rodzaju WaitForMultipleObjects. Natomiast organizacja wejścia zależy już od naszej aplikacji. Warto pamiętać, że w standardowej konsoli jest ono buforowane wierszami, zatem i my powinniśmy wysyłać coś do procesu potomnego dopiero wtedy, gdy zbierzemy całą linijkę danych wejściowych.

Łatwe, prawda? ;-) W innych systemach operacyjnych robi się to minimalnie inaczej (pipe, fork, dup2, …), ale ogólna idea jest podobna. Jak widać, kilkoma małymi rurkami można zdziałać całkiem sporo :]

Tags: , , , ,
Author: Xion, posted under Programming » 1 comment

O testach jednostkowych

2008-03-19 22:06

Kod skompilowany nie musi być kodem działającym poprawnie – tę prawidłowość zna każdy programista. Z drugiej jednak strony dogłębne przetestowanie programu jako całości to proces żmudny, trudny, niepokojący i obarczony sporym ryzykiem niepowodzenia. A przy tym oczywiście konieczny. Można go jednak nieco usprawnić poprzez ograniczenie możliwości występowania błędów w niektórych częściach programu – takich, które wcześniej potraktujemy testami jednostkowymi (unit tests).

Ten rodzaj testów w skrócie polega na tym, aby każdy napisany element kodu – co zależnie od języka i sposobu programowania może oznaczać np. funkcję lub klasę – opatrzyć jedną lub kilkoma procedurami testującymi. Mają one na celu sprawdzanie, czy ów element robi dokładnie to, co założyliśmy, poprzez użycie go “na zewnątrz”, w innym kodzie. Innymi słowy, taka procedura testowa ma na celu uruchomienie funkcjonalności jakiejś klasy/funkcji/itp. i sprawdzenie, czy rezultaty jej działania są zgodne z oczekiwanymi.
Takie procedury można pisać po zakończeniu implementacji testowanego elementu. Niektóre metodyki tworzenia oprogramowania zalecają jednak, aby… najpierw pisać kod testowy, a dopiero potem ten właściwy! Wbrew pozorom ma to całkiem spory sens. Jeśli bowiem zaczniemy od kodu, który ma naszej klasy używać, to istnieje większa szansa, że od początku wyposażymy ją w interfejs, którego rzeczywiście da się używać bez większych problemów. Na koniec zaś będziemy dysponowali też przykładowym kodem, obrazującym sposób korzystania z danej klasy, co zazwyczaj bywa przydatne.

Według mnie największą zaletą testów jednostkowych jest to, że przy pomocy odpowiednich narzędzi możemy je bardzo szybko napisać w postaci nadającej się do natychmiastowego uruchomienia. Brak konieczności tworzenia nowej aplikacji – dla samych tylko testów – jest niezwykle wygodny. Najczęściej bowiem jedyne, co musimy zrobić, to napisać klasę z procedurami testowymi i oznaczyć ją odpowiednio w kodzie, a następnie po prostu uruchomić testy (co często daje się zautomatyzować jako czynność następną po kompilacji) i obserwować wyniki.
Szczegóły mogą się aczkolwiek różnić w zależności od języka, jako że frameworków dla testów jednostkowych jest sporo. Mamy na przykład:

  • JUnit, przeznaczony dla Javy. To również pierwszy szeroko znany mechanizm tego typu i wzór dla licznych naśladowców (również pod względem nazewnictwa :-]).
  • NUnit to z kolei narzędzie dla .NET. Zasadniczo działa on bardzo podobnie do powyższego, również pod względem jego praktycznego użycia.
  • CppUnit to wreszcie próba przystosowania xUnit do języka C++. Wyszła ona całkiem zadowalająca, oczywiście zważywszy na to, co ów język oferuje chociażby w zakresie tak przydatnych tutaj refleksji (czyli mniej więcej tyle, co nic). Na pewno warto się tej bibliotece przyjrzeć.

Tak naprawdę to właściwie dla każdego liczącego się języka istnieje narzędzie tego typu. Polecam więc przyjrzenie się im (i całemu zagadnieniu testów jednostkowych), jeśli wcześniej nie mieliśmy z tym tematem styczności. Bo przecież testowania nigdy dość ;)

Tags: ,
Author: Xion, posted under Programming » 1 comment
 


© 2022 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.