Posts tagged ‘functions’

Dwukierunkowe funkcje i obiekty proxy

2010-06-01 16:07

Jedną z pierwszych rzeczy poznawanych w trakcie nauki programowania jest sposób działania funkcji. Mam tu na myśli zupełnie elementarny fakt, iż funkcje przyjmują zero lub więcej argumentów na wejściu i produkują co najwyżej jeden rezultat na wyjściu. Niezachwiana pewność w tę własność funkcji może być potem mocno nadwątlona, jeśli poznamy języki o bardziej egzotycznym sposobie działania, jak na przykład Prolog; tam wszystkie parametry funkcji mogą przekazywać dane w obu kierunkach, dzięki czemu np. za dzielenie i łączenie ciągów lub list odpowiada jedna i ta sam funkcja.
Nie trzeba jednak uciekać tak daleko od starego dobrego programowania imperatywnego, żeby zaobserwować odstępstwa od reguły. Parametry mogą przecież służyć do zwracania wartości – dzieje się to przy pomocy słów kluczowych ref/out w C# lub zwykłych wskaźników/referencji w C++. Często zdarza się wtedy, że “normalny” rezultat zwracany przez funkcję służy jedynie przekazaniu informacji o ewentualnym błędzie.

Rzadsza sytuacja polega na tym, że wynik funkcji staje się jej argumentem wejściowym. Technicznie nie jest nawet możliwe, ale można tak traktować sytuacje, gdy rezultatem jest l-wartość (l-value), tj. obiekt, do którego można przypisywać:

  1. vector<int> v(10);
  2. v.at(5) = 25;

Typowo jest to referencja (tutaj int&), a powyższa konstrukcja – poprzez swojej podobieństwo do indeksowania zwykłej tablicy – nie należy do wielce zaskakujących. Co jednak można powiedzieć o tej:

  1. Dim S as String = "Ala ma kota"
  2. Mid(S, 4, 2) = "nie ma" ' Ala nie ma kota

poza widocznym od razu faktem, że pochodzi ona z języka, którego rozwlekłość składni przyprawia o niestrawność? :) Mianowicie tutaj nie ma już oczywistych przesłanek co do tego, czym jest lewa strona. Widać bowiem, że możemy jej przypisać dłuższy podciąg niż oryginalny i zostanie on mimo wszystko poprawnie zastąpiony – nie jest to więc żaden prosty “wyrób wskaźnikopodobny”. Może więc to po prostu feature akurat tego języka, którego nie da się zreplikować?…

Odpowiedź jest – jak można się domyślać, skoro o tym piszę – oczywiście negatywna :) Ażeby podobny efekt osiągnąć w C++, konieczne jest jednak zastosowanie techniki znanej jako obiekt pośredniczącyproxy. Powinien on zachowywać się jak zwykły rezultat funkcji, ale w razie potrzeby dawać również możliwość przypisywania do siebie. Naturalnie efekt takiego działania jest specyficzny dla konkretnej funkcji, która swoją drogą może być często zredukowana do samego tworzenia obiektu proxy:

  1. inline Mid_Proxy Mid(std::string& s, size_t off, size_t len)
  2.     { return Mid_Proxy(s, off, len); }

Minimum, jakie rzeczony obiekt musi zapewniać, to operator przypisania oraz jakiś operator rzutowania, który pozwoli na “wyciągnięcie” rezultatu funkcji, gdy jest ona użyta w zwykły sposób:

  1. class Mid_Proxy
  2. {
  3.     private:
  4.         std::string& s;
  5.         size_t off, len;
  6.     public:
  7.         Mid_Proxy(std::string& _s, size_t _off, size_t _len)
  8.             : s(_s), off(_off), len(_len) { }
  9.  
  10.         void operator = (const std::string& str)
  11.             { s.replace (off, len, str); }
  12.         operator std::string () const
  13.             { return s.substr(off, len); }
  14. };

Widzimy tutaj, że przy takim proxy nasza funkcja Mid użyta w zwykły sposób zachowuje się jak metoda substr. Gdy jednak umieścimy jej wywołanie po lewej stronie przypisania, zadziała metoda replace, służąca do zastępowania podciągu innym. W sumie więc poniższy kod:

  1. std::string s("Ala ma kota");
  2. Mid(s, 4, 2) = "nie ma";

będzie działał analogicznie do prezentowanego wyżej fragmentu w języku Visual Basic.

Opisana tu sztuczka nie jest oczywiście doskonała. Do pełni możliwości potrzebna jest jeszcze wersja read-only funkcji Mid, przyjmująca stałą referencję do stringa i wywołująca substr bezpośrednio, z pominięciem obiektu proxy. To jednak da się łatwo zauważyć.
Mniej widoczny jest natomiast fakt, że obiekt proxy, dodając kolejną warstwę niejawnych konwersji (tutaj: z siebie na string) może spowodować kłopoty tam, gdzie jedna niestandardowa konwersja jest już wykorzystywana. Dobry przykład to interakcja ze strumieniem:
std::cout << Mid(s, 0, 3) << std::endl;[/cpp] która nie powiedzie, bo operator strumienowy << nie posiada wersji dla lewego prawego argumentu będącego std::stringiem, a jedynie dla const char* (co swoją drogą jest dość dziwne). Rozwiązaniem jest napisanie takowego dla samego obiektu proxy.

Co może udawać obiekt w C++

2010-05-06 14:56

Możliwości przeciążania operatorów w C++ dla własnych typów obiektów sprawiają, że mogą one (tj. te obiekty) zachowywać się w bardzo różny sposób. Mogą na przykład “udawać” pewne wbudowane konstrukcje językowe, nierzadko wykonując ich zadania lepiej i wygodniej. Przykładów na to można podać co najmniej kilka – oto one:

  • Obiekt może zachowywać się jak funkcja, czyli udostępniać możliwość “wywołania” siebie z określonymi parametrami. Takie twory często nazywa się funktorami i bywają używane podczas pracy ze standardową biblioteką STL.
    Działają one przy tym w bardzo prosty sposób, zwyczajnie przeciążając operator nawiasów okrągłych (). Jest on na tyle elastyczny, że może przyjmować dowolne parametry i zwracać dowolne rezultaty, co pozwala nawet na stworzenie więcej niż jednego sposobu “wywoływania” danego obiektu. Jednym z bardziej interesujących zastosowań dla tego operatora jest implementacja w C++ brakującego mechanizmu delegatów, czyli wskaźników na metody obiektów.
  • Na podobnej zasadzie obiekt może udawać tablicę – wie o tym każdy, kto choć raz używał klas STL typu vector. Wymagane jest tu przeciążenie operatora indeksowania []. Daje ono wtedy dostęp do elementów obiektu-pojemnika, który zresztą nie musi być wcale indeksowany liczbami, jak w przypadku tablic wbudowanych (dowodem jest choćby kontener map). Ograniczeniem jest jedynie to, że indeks może być (naraz) tylko jeden, bo chociaż konstrukcja typu:
    1. v[3,4] = 5;

    jest składniowo najzupełniej poprawna, to działa zupełnie inaczej niż można by było się spodziewać :)

  • Obiekty mogą też przypominać wskaźniki, które wtedy określa się mianem ‘sprytnych’ (smart pointers). Dzieje się tak głównie za sprawą przeciążenia operatorów * (w wersji jednoargumentowej) i ->. Normalnie te operatory nie mają zastosowania wobec obiektów, ale można nadać im znaczenie. Wtedy też mamy obiekt, który zachowuje się jak wskaźnik, czego przykładem jest choćby auto_ptr z STL-a czy shared_ptr z Boosta.
  • Wreszcie, obiekt może też działać jako flaga boolowska i być używany jako część warunków ifów i pętli. Sprytne wskaźniki zwykle to robią, a innymi wartymi wspomnienia obiektami, które też takie zachowanie wykazują, są strumienie z biblioteki standardowej. Jest to spowodowane przeciążeniem operatora logicznej negacji ! oraz konwersji na bool lub void*.

Reasumując, w C++ dzięki przeciążaniu operatorów możemy nie tylko implementować takie “oczywiste” typy danych jak struktury matematyczne (wektory, macierze, itp.), ale też tworzyć własne, nowe (i lepsze) wersje konstrukcji obecnych w języku. Szkoda tylko, że często jest to wręcz niezbędne, by w sensowny sposób w nim programować ;)

Ostatnia wartość zwracana przez funkcję

2010-01-19 9:23

Debugując program w pracy krokowej w Visual Studio, możemy podglądać wartości wszystkich zmiennych, jakie są dostępne w zasięgu punktu wykonania. Jest to możliwe za pośrednictwem okienka tzw. czujek (watches). Automatycznie wypełnia się ono zmiennymi lokalnymi oraz ewentualnym wskaźnikiem this, pozwalającym podejrzeć wartości pól obiektu, jeśli znajdujemy się akurat w jego metodzie.
Jednak oprócz rzeczywistych zmiennych możemy śledzić też pewne specjalne “pseudozmienne”, udostępniane przez debuger VS. Mają one nazwy zaczynające się od znaku dolara $ i potrafią być bardzo przydatne, co pokażę na przykładzie.

Powiedzmy, że mamy kod składający się z wielu następujących po sobie wywołań funkcji bibliotecznych. Każda z nich zwraca rezultat liczbowy, informujący o (nie)powodzeniu operacji, którego jednak w kodzie nie sprawdzamy – pewnie dlatego, że nie chciało nam się pisać tych wszystkich ifów :) Taka sytuacja może wystąpić chociażby przy ciągu wywołaniach DirectX: ogromna większość funkcji z tej biblioteki zwraca wynik typu HRESULT, który jest liczba zawierającą kod błędu, jeśli takowy wystąpił.
Zauważamy teraz, że ów ciąg wywołań najpewniej zawiera jakiś błąd. Objawem w DX może być chociażby słynne “nic nie widać” :) Jak teraz dojść, które z wielu wywołań zwraca błąd, jeśli w żadnym z nich nie tylko nie sprawdzamy wyniku, ale wręcz w ogóle go nie zapisujemy?…

Podejrzenie wartości EAX w VS

Istnieje na szczęście proste i wygodne rozwiązanie, które nie wymaga żadnych zmian w kodzie. Otóż przy pomocy debugera VS i jego pseudozmiennych możemy podejrzeć wartość rejestrów procesora. Wystarczy użyć symbolu $nazwa_rejestru, jak np. $eax. I właśnie $eax jest tutaj świetnym przykładem, bo rozwiązuje nasz problem. Otóż przez rejestr EAX przekazywany jest zawsze 32-bitowy rezultat zwracany przez każdą porządną funkcję. Przechodząc więc krokowo po naszym kodzie możemy sprawdzić, jak zmienia się ten rejestr po każdym wywołaniu, podglądając w ten sposób wartość, jaką zwróciła w nim funkcja. Wystarczy więc tylko znaleźć to, w którym rezultat informuje o niepowodzeniu… i voila – mamy nasz błąd :)

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

W matematyce jest odwrotnie

2009-10-19 23:53

Współrzędne biegunoweW pewnych sprawach kiedyś występowała alternatywa dwóch równoważnych możliwości i trzeba było w końcu zdecydować się na wybór jednej z nich. Matematycy często ustalają w ten sposób coś “dla porządku” lub dla tzw. ustalenia uwagi. Jak na ironię zauważyłem jednak, że zwykle to właśnie w matematyce niektóre powszechnie obowiązujące umowy wcale nie wprowadzają porządku, gdyż są dokładnie odwrotne względem intuicji lub codziennego doświadczenia. Oto przykłady:

  • Kąty w kartezjańskim układzie współrzędnych na płaszczyźnie – ze szczególnym uwzględnieniem współrzędnych biegunowych – są tak określone, że większe ich wartości oznaczają coraz większe przesunięcie w kierunku przeciwnym do ruchu wskazówek zegara.
  • Tzw. główna przekątna macierzy przy jej zwykłej reprezentacji tablicowej obejmuje komórki od lewego górnego do prawego dolnego rogu. Linia, która jest pochylona w ten sposób, przypomina znak backslash :)
  • Wykres funkcji wypukłej
    Ta funkcja jest wypukła :)

    Funkcje rzeczywiste nazywane wypukłymi narysowane w postaci wykresu przyjmują postać krzywej wygiętej do dołu, co sugeruje nazywać je raczej… wklęsłymi (obrazuje to rysunek po prawej).

  • Tradycyjnie wektory w matematyce zapisuje się jako kolumnowe (czyli macierze n \times 1), a nie wierszowe (1 \times n). To niby nic specjalnego, ale skutek “uboczny” jest taki, że macierze przekształceń (obrotu, translacji, itp.) w stosunku do takich wektorów należy aplikować w kolejności odwrotnej względem rzeczywistej kolejności transformacji, którą chcemy uzyskać (kiedyś już pisałem więcej na ten temat).

Na pewno nie są to wszystkie przypadki podobnych “niefortunnych” rozstrzygnięć; z pewnością dałoby się znaleźć ich więcej. Na pewno też każdy z nich daje się w zadowalający sposób uzasadnić (jak chociażby przekątną macierzy – jest ona po prostu definiowana przez te komórki, których numer wiersza jest równy numerowi kolumny). I paradoksalnie to właśnie jest w nich najgorsze: nie da się z nimi nic zrobić, jak tylko zwyczajnie zapamiętać :)

Tags: , ,
Author: Xion, posted under Math » 7 comments

Typ zwracany funkcji wirtualnej

2009-08-04 16:42

Kiedy w klasie pochodnej piszemy nową wersję funkcji wirtualnej, to w C++ powinniśmy zawsze uważać na to, żeby jej nagłówek był identyczny z tym, który zdeklarowano w klasie bazowej. To dlatego, że składnia języka nie wymaga w tej sytuacji żadnego słowa kluczowego w rodzaju override. Jeśli więc coś nieopatrznie zmienimy, to nie uzyskamy nowej wersji funkcji, tylko zupełnie nową funkcję przeciążoną:

  1. class Foo
  2. {
  3.     public: virtual void Do(int x, int y, int z) { }
  4. };
  5.  
  6. class Bar : public Foo
  7. {
  8.     // to *nie* jest nowa wersja Foo::Do, tylko zupełnie inna funkcja
  9.     public: void Do(int x, int y, string z) { }
  10. };

Taki efekt jest jest w gruncie rzeczy oczywisty i łatwy do zrozumienia. Pewnie więc będzie nieco zaskakujące dowiedzieć się, że tak naprawdę postać funkcji wirtualnej w klasie pochodnej może się trochę różnić, a mimo to wciąż będziemy mówili o tej samej funkcji.

Jak to jest możliwe?… Dopuszcza się mianowicie różnicę w typie zwracanym przez nową wersję funkcji wirtualnej. Może on być inny od typu zwracanego przez wersję z klasy bazowej – ale tylko pod warunkiem, że:

  • pierwotny typ był wskaźnikiem lub referencją do klasy (a nie chociażby typem podstawowym, jak int)
  • nowy typ zwracany jest – odpowiednio – wskaźnikiem lub referencją do klasy pochodnej od tej z typu pierwotnego
  • nowy typ posiada tę samą kwalifikację const/volatile co typ pierwotny

Przykładowo więc, jeśli w klasie bazowej funkcja wirtualna zwraca const A*, to w klasie pochodnej może zwracać const B*, o ile klasa B dziedziczy publicznie po A. Nie może za to zwracać samego B* (niestałego) lub const X*, gdy klasa X jest niezwiązana z A.

Do czego taki “myk” może się przydać? Najczęściej chodzi tutaj o sytuacje, gdy mamy do czynienia z równoległym dziedziczeniem kilku klas, które na każdym poziomie są związane ze sobą. Mogę sobie na przykład wyobrazić ogólny menedżer zasobów w grze, którego metoda wirtualna Get zwraca wskaźnik na bazową klasę Resource, a następnie bardziej wyspecjalizowany TextureManager, który w tej sytuacji podaje nam wskaźnik na Texture. (Oczywiście klasa Texture w założeniu dziedziczy tu po Resource). Czasami coś takiego może być potrzebne, aczkolwiek takie równoległe hierarchie dziedziczenia nie są specjalnie eleganckie ani odporne na błędy.
Lepszym przykładem jest wirtualny konstruktor kopiujący: metoda, która pozwala na wykonanie kopii obiektu bez dokładnej znajomości jego typu. Zwyczajowo nazywa się ją Clone:

  1. class Object
  2. {
  3.     public:
  4.         virtual Object* Clone() const { return new Object; }
  5. };
  6.  
  7. class Foo : public Object
  8. {
  9.     public:
  10.         // nowa wersja metody Object::Clone
  11.         Foo* Clone() const { return new Foo; }
  12. };

Dzięki temu że metoda jest wirtualna, można ją wywołać nie znając rzeczywistego typu obiektu (co nie jest możliwe w przypadku zwykłych konstruktorów, które w C++ wirtualne być nie mogą). W wyniku jej wywołania otrzymamy jednak tylko ogólny wskaźnik Object* na powstałą kopię obiektu.
Gdybyśmy teraz nie zmienili typu zwracanego przez metodę w klasie pochodnej, to klonowanie podobne do tego:

  1. void Function(Foo* foo)
  2. {
  3.     Foo* copy = foo->Clone();
  4.     // ...
  5. }

wymagałoby dodatkowego rzutowania w górę, by mogło zostać przepuszczone przez kompilator.

Tags: , , , , ,
Author: Xion, posted under Programming » Comments Off on Typ zwracany funkcji wirtualnej

Płaska wizualizacja funkcji 3D

2009-06-02 18:43

Funkcje, których dziedziną jest podzbiór R2 (czyli płaszczyzna) ciężko jest przedstawić na płaskim ekranie w sposób poglądowy, a jednocześnie pozwalający na odczytanie jakichś wartości. O ile bowiem izometryczny rzut 3D wygląda efektownie, to poza ogólnym kształtem powierzchni nie przedstawia wielkiej ilości informacji. Sprawa wygląda trochę lepiej, jeśli taką figurę możemy jeszcze obracać… co aczkolwiek może być z kolei trudne do zrealizowania np. na wydruku :]

Jednym z wyjść może być tutaj zastosowanie sposobu używanego do map wysokości w grach. Nietrudno zauważyć, że są one niczym innym jak właśnie funkcjami typu R2->R, a reprezentowane są najczęściej jako bitmapy w odcieniach szarości: jasność piksela x,y odpowiada w nich wysokości odpowiedniego punktu terenu.
Takie heightmapy wprawdzie łatwo się rysuje, ale niespecjalnie nadają się do pokazania jako ilustracja czegokolwiek – odcienie szarości są przecież z definicji szare i nieciekawe :) Dlatego bardzo spodobał mi się prosty pomysł na uczynienie tej reprezentacji znacznie ładniejszą, o którym to usłyszałem niedawno.

Idea jest prosta: po co używać samych szarości, skoro mamy do dyspozycji całą paletę kolorów?… Każdy kolor w reprezentacji RGB jest przecież tożsamy z liczbą, co widać najbardziej, jeśli weźmiemy jego typową reprezentację 32-bitową:

W niej “największym” kolorem jest kolor biały (0x00FFFFFF, czyli 224 – 1), zaś “najmniejszym” czarny (0x0), a pomiędzy nimi włącznie występuje każdy z 2563 możliwych kolorów. Jeśli teraz przeskalujemy wartości naszej funkcji do tak określonego przedziału (lub nieco mniejszego), a następnie przekonwertujemy każdą z tych 32-(a właściwie 24-)bitowych liczb na odpowiadający jej kolor RGB, to otrzymamy w ten sposób heightmapę o znacznie bogatszej palecie barw niż poprzednio.
Jeśli ponadto używamy dokładnie takiej reprezentacji liczbowej kolorów, jak powyżej (najmłodsze bity na kolor niebieskie, a najstarsze używane na czerwony), to zauważymy, że rozkład barw w wyniku jest całkiem znajomy. I tak obszary niebieskie odpowiadają wartościom najmniejszym, zielone średnim, żółte – wysokim, a czerwone – najwyższym. Łącznie przypomina mapę hipsometryczną – czyli, jakby nie patrzył, mapę wysokości właśnie :)

Do czego może przydać się takie cudo, oprócz wspomnianej już wizualizacji funkcji R2->R na płaszczyźnie? Pewnie do niewielu rzeczy :) Ja wpadłem jednak na jeszcze jedno potencjalne zastosowanie.
Ponieważ wynikowy obrazek używa tak “geograficznych” barw, może on całkiem dobrze wyglądać jako… tło minimapy pokazywanej w grze, która rozgrywa się na terenie opisanym mapą wysokości. Oczywiście rzecz wymagałaby dopracowania: przede wszystkim bardziej starannego dobrania kolorów brzegowych (niekoniecznie białego i czarnego) oraz być może kolorów pośrednich (np. kolor poziomu morza), a i pewnie zastosowania jakichś filtrów na wynikowym obrazku (np. wygładzania). Efekty mogłyby być jednak interesujące, co widać obok.

Funkcje jako dane wejściowe

2009-05-29 15:56

Sporo algorytmów jako swoje parametry przyjmuje różnego typu funkcje, które potem są wykorzystywane w trakcie ich działania. Prostym przykładem są tu wszelkiego rodzaju sortowania czy wyszukiwania, umożliwiające często podanie własnego predykatu (funkcji zwracającej wartość logiczną). W bardziej skomplikowanej wersji może chodzić chociażby o algorytm genetyczny lub przeszukujący drzewo gry, który wykorzystuje do działania jakąś funkcję oceniającą (np. osobników w populacji).

Na takie okazje różne języki programowania oferują różne narzędzia, lecz w większości przypadków sprowadzają się one do jednego z poniższych:

  • Wskaźniki lub delegaty. Przekazywanie funkcji przez wskaźnik jest proste i naturalne, ale ma pewne ograniczenia. W C(++) na przykład nie da się zwykłym wskaźnikiem pokazać na metodę konkretnego obiektu; docelowo może to być tylko funkcja globalna lub statyczna. Ten problem nie występuje zwykle w przypadku delegatów, którymi często można pokazać właściwie na wszystko – również na anonimową funkcję zdefiniowaną ad hoc:
    1. // sortowanie listy w oparciu o własny predykat (C# 2.0 wzwyż)
    2. objects.Sort (delegate (object a, object b)
    3.     { return a.ToString().Length - b.ToString().Length; });

    Niektóre języki nie mają jednak ani wskaźników, ani delegatów – w nich zwykle stosuje się sposób następny.

  • Interfejsy i metody wirtualne. Ta technika polega na zdefiniowaniu interfejsu (lub klasy abstrakcyjnej) z metodą wirtualną, którą docelowo będzie wywoływać algorytm. Korzystający z niego programista implementuje po prostu wskazany interfejs (lub definiuje klasę pochodną) i nadpisuje wspomnianą metodę własną wersją. Ten sposób jest szczególnie popularny w Javie, gdzie wspomagają go inne mechanizmy językowe – jak choćby niestatyczność klas wewnętrznych lub możliwość ich definiowania inline – np. w wywołaniu funkcji.
    Zauważmy też, że implementacja naszej ‘funkcji’ w postaci klasy pozwala też na dodatkowe możliwości, jak na przykład posiadanie przez nią stanu (co aczkolwiek w wielu przypadkach, np. predykatów sortowania, jest wysoce niezalecane).
  • Funktory. To rozwiązanie jest specyficzne dla C++ i opiera się na dwóch występujących w tym języku feature‘ach: szablonach i przeciążaniu operatorów. Dzięki temu algorytm korzystający z “czegoś co przypomina funkcję” może wyglądać choćby tak:
    template < typename T, typename SearchFunc >
    const T find(const std::vector& v, SearchFunc pred)
    {
    for (int i = 0; i < v.size(); ++i) if (pred(v[i])) return v[i]; // znaleziono element spełniający predykat return T(); }[/cpp] Określenie "coś co przypomina funkcję" jest jak najbardziej na miejscu, gdyż tutaj predykatem może być cokolwiek, co da się jako funkcję potraktować - czyli wywołać operatorem (). Może więc to być zwykły wskaźnik, jakaś ładna zewnętrzna implementacja mechanizmu delegatów (np. FastDelegate) lub jakikolwiek obiekt z przeciążonym operatorem nawiasów (). Właśnie te ostatnie nazywa się zwykle funktorami, a jeśli ktoś nieco bardziej zagłębił się w bibliotekę STL, na pewno nie raz się z nimi spotkał.

Trzeba też powiedzieć, że właściwie istnieje też inny sposób: zamiast samej funkcji przekazywanie jej… nazwy. “I niby jak ją potem wywołać?”, można zapytać. Ano to już indywidualna kwestia każdego języka – w tym przypadku zwykle interpretowanego :)

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


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