Drugi problem, czyli API do wyrażeń regularnych

Napotykając problem, niektórzy ludzie myślą: “Użyję wyrażeń regularnych!”
W rezultacie mają dwa problemy.

Jamie Zawinski @ alt.religion.emacs

Ten słynny cytat jest, według mnie, lekkim niedoszacowaniem. Decydując się na skorzystanie z wyrażeń regularnych, z miejsca dostajemy bowiem dwa problemy z nimi samymi :) Pierwszych z nich jest sama składnia, która dla nieprzyzwyczajonego oka jest cokolwiek nietrywialna. To głównie ona jest wskazywana jako główna trudność w sprawnym i efektywnym używaniu regexów.
Dzisiaj jednak chciałem zwrócić uwagę na ten drugi, rzadziej zauważany problem. Otóż samo wyrażenie to nie wszystko, trzeba je jeszcze odpowiednio użyć w naszym kodzie. I tutaj mogą zacząć się schody, bo w różnych językach programowania sprawa ta wygląda często odmiennie. Na szczęście jest da się tu też wskazać podobieństwa i spróbować dokonać uogólnienia.

Podstawowym elementem interfejsu programistycznego do wyrażeń regularnych jest zwykle obiekt wzorca (pattern), czyli samego wyrażenia. Zawiera on jego postać skompilowaną, którym jest mniej lub bardziej skomplikowana (w zależności od składni) konstrukcja przypominająca automat stanów. Zbudowanie tej wewnętrznej reprezentacji jest konieczne, aby przeprowadzić jakąkolwiek operację (np. wyszukiwania czy dopasowania). Jeśli więc planujemy skorzystać z jednego wyrażenia w celu przetworzenia większej liczby tekstów, dobrze jest posługiwać się gotowym, skompilowanym obiektem.
Ten ogólny opis dobrze przenosi się na rzeczywiste języki programowania, w których możemy znaleźć takie klasy jak:

• boost::regex/wregex w C++ z biblioteką Boost.Regex
• System.Text.RegularExpressions.Regex w C#/.NET
• java.util.regex.Pattern w Javie
• re.RegexObject w Pythonie

Tekstową postać wyrażeń regularnych podajemy zwykle do konstruktorów wyżej wymienionych klas, względnie używamy jakichś statycznych lub globalnych funkcji z odpowiednich pakietów. Przy okazji warto też wspomnieć o problemie escape‘owania znaków specjalnych w wyrażeniach, który w mocno niepożądany sposób interferuje z analogicznym mechanizmem w samych językach programowania. Ponieważ w obu przypadkach używa się do tego znaku backslash (\), w wyrażeniach wpisywanych do kodu należy go podwoić:

W C# i Pythonie można tego uniknąć, stosując mechanizm surowych napisów (raw strings). Programiści C++ i Javy nie mają niestety tego szczęścia ;)

Gdy mamy już obiekt skompilowanego wyrażenia, możemy użyć go do jakichś pożytecznych celów. Jeśli są one proste – jak choćby sprawdzenie, czy jakiś ciąg ma formę określoną regeksem – to możemy zazwyczaj obejść się jednym prostym wywołaniem:

Bardziej skomplikowane jest wyszukiwanie wszystkich dopasowań wyrażenia w danym tekście, zwłaszcza jeśli przy okazji chcemy dobrać się do fragmentów znalezionych podciągów. Tutaj zaczynają objawiać się pewne różnice między poszczególnymi językami, ale ogólny schemat pozostaje ten sam. Opiera się on na skonstruowaniu odpowiedniej pętli przelatującej po kolejnych dopasowaniach i operowaniu na obiekcie, który takie dopasowanie (match) reprezentuje:

• boost::match_results w C++ z Boost.Regex
• System.Text.RegularExpressions.Match w C#/.NET
• java.util.regex.Matcher w Javie (klasa ta kontroluje też iterację po kolejnych dopasowaniach)
• re.MatchObject w Pythonie

Obiekt dopasowania udostępnia zazwyczaj kilka przydatnych metod i właściwości, jak choćby zakres indeksów znalezionego ciągu. Są też tam fragmenty, które “wpadły” w podgrupy strukturalne (subsequences, subgroups, capture groups, itp.), na które nasze wyrażenie było podzielone. Chodzi tu o jego części ujęte w nawiasy okrągłe; to, jakie konkretne znaki zostały dopasowane do każdego z nich zostaje bowiem zapamiętane w obiekcie match.
Między innymi dzięki temu faktowi możliwe jest określanie bardzo ogólnych wzorców do wyszukania w tekście, a następnie przeglądanie tego, co udało nam się znaleźć i podejmowanie decyzji na podstawie jakichś znaczących elementów dopasowania. W ten sposób możemy przetwarzać teksty o stopniu skomplikowania znacznie przekraczającym to, co w teorii daje się opisać wyrażeniami regularnymi. Żeby nie pozostać gołosłownym, zaprezentuję na przykład prosty sposób na konwersję tekstu zawierającego często spotykane na forach znaczniki BBCode (takie jak [url] czy [img]) na jego odpowiednik HTML-owy, gotowy do wyświetlenia.

Najważniejsza jego część to wykonywane w funkcji _bbtag_to_html przetwarzanie obiektu typu re.MatchObject zawierającego dane o znalezionym, pojedynczym tagu. Pobieramy tam jego nazwę i zawartość, które zostały dopasowane jako odpowiednio: pierwsza i druga podgrupa wyrażenia. Samo przeglądanie tekstu w poszukiwaniu tagów i ich zastępowanie jest wykonywane wbudowaną funkcją re.RegexObject.sub, która ukrywa szczegóły wspomnianej wcześniej pętli.

Mam nadzieję, że powyższy przykład dowodzi, że możliwe jest zastosowanie wyrażeń regularnych bez znaczącego wzrostu liczby problemów do rozwiązania :) Jakkolwiek dziwnie to zabrzmi, korzystanie z regeksów może bowiem niekiedy przyczynić się do wzrostu czytelności wynikowego kodu, przynajmniej dla bardziej doświadczonych programistów. Jest tak ze względu na duże podobieństwa nie tylko między różnymi wariantami składni wyrażeń, ale też między bibliotekami do ich obsługi w różnych językach programowania, które to dzisiaj starałem się przedstawić.

Formatowanie tekstu

Tematem budowania łańcuchów znaków zajmowałem się już kiedyś, badając efektywność tej operacji w C++ dla trzech różnych sposobów. Tym razem przyjrzę się sprawie z perspektywy bardziej niezależnej od języka. Ostatnio poczyniłem bowiem pewną obserwację. Zauważyłem mianowicie, że “tradycyjne” podejście do składania stringów – przez konkatenację kolejnych podciągów – staje się… hmm… niemodne, jeśli można tu użyć takiego określenia.

Ci, którzy kodują nieco dłużej niż ja pewnie zwrócą mi zaraz uwagę, że takie naprawdę tradycyjne podejście do problemu to to, które implementują funkcje z języka C podobne do printf:

Polega ono na uprzednim zdefiniowaniu wzorca tekstu (tzw. formatu, tutaj jest to drugi argument fprintf), zawierającego symbole zastępcze takie jak %s czy %d. Są one następnie zastępowane podanymi wartościami (tutaj: tag oraz errno) w celu wyprodukowania finalnego ciągu. Nie ma tu jawnej operacji łączenia dwóch napisów. Zamiast tego mały parser przegląda podany wzorzec i w miejscu symboli zastępczych wstawia do wyniku podane wartości, przepisując bez zmian resztę znaków.
Wkrótce jednak nadszedł C++ z klasami string i ostream, oferującymi podobne możliwości bez użycia wzorców. Zamiast tego posługiwały się operatorami + i << w celu wyprodukowania tekstowego wyjścia:
cerr << "[" << tag << "] Error (errno=" << errno << ")" << endl;[/cpp] To działa, ale - jak można zobaczyć w porównaniu - wygląda często znacznie mniej przejrzyście. Nie dziwi więc, że w tym względzie historia zdaje się zatoczyć koło. Obecnie bowiem operacja formatowania napisów (w sensie powyższej funkcji fprintf, a nie określania czcionki czy stylu tekstu) jest wbudowana w wiele nowoczesnych, popularnych języków programowania, jak choćby C#, Pythona czy Javę. Najczęściej też, co ciekawe, trzyma się ona z grubsza oryginalnej składni wzorców pochodzącej jeszcze z C, dodając oczywiście jakieś własne, bardziej zaawansowane rozszerzenia:

Czasami jednak – jak widać wyżej – tak nie jest :) Na obecność mechanizmu formatowania łańcuchów znaków możemy aczkolwiek liczyć w każdym szanującym się języku. I to łącznie z C++, gdzie wszystko prawie wszystko, czego w nim pierwotnie nie ma, zawiera się w jakiejś bibliotece boost – w tym przypadku jest to boost::format.

C++ i tablice asocjacyjne

Zwykłe tablice (jednowymiarowe) w “normalnych” językach programowania to po prostu ciągłe obszary pamięci, do których pierwszego elementu posiadamy odwołanie. Dostęp do kolejnych polega na korzystaniu z arytmetyki wskaźników, więc niedziwne jest, że takie tablice indeksuje się wyłącznie liczbami – i to z określonego zakresu.
Ci, którzy programowali w na przykład w Pythonie lub PHP znają jednak koncepcję tablic asocjacyjnych, dla których to ograniczenie nie obowiązuje. W C++ do ich symulowania używa się często map z STL-a:

Jest to oczywiście odpowiednie przeciążenie operatora [], a map jest rodzajem pojemnika. Skoro jednak ma to udawać tablicę, to dobrze by było, żeby narzut na obsługę dostępu do elementów nie różnił się zbytnio od tego z prawdziwych tablic. A ten, jak wiemy, jest stały.

Jak to osiągnąć?… Przede wszystkim powinniśmy – jeśli tylko możemy – nie korzystać z kontenera map. Problem z nim polega na tym, że poświęca on dużo uwagi sortowaniu elementów według ich kluczy (“indeksów”). Gdy klucze te są złożone – bo są nimi np. łańcuchy znaków – może to zająć trochę czasu i jednocześnie nie dawać nam żadnej korzyści. Dla tablicy asocjacyjnej najważniejsze są bowiem operacje wyszukiwania wartości (“indeksowania”) i dodawania nowych elementów, względnie ich usuwania. To one muszą działać szybko; wewnętrzny porządek elementów nie jest dla nas istotny.
Dlatego też lepsza jest mapa korzystająca z dobrodziejstw mechanizmu haszowania. W Visual C++ (podobnie zresztą jak w GCC) takie cudo dostępne jest od dawna jako klasa hash_map. Długo było ono niestandardowym rozszerzeniem biblioteki STL, ale wraz z nową wersją standardu staje się ono jego częścią. Poza tym “od zawsze” istnieje też rozwiązanie z Boosta w postaci klasy unordered_map. Przyjemną cechą wszystkich tych implementacji jest niemal jednolity interfejs, tożsamy ze standardową klasą map.

Oprócz używania właściwego pojemnika powinniśmy też wiedzieć, jak go z niego korzystać – a dokładniej mówiąc, czego unikać. Felerną operacją jest próba dodania elementu poprzez zwykłe indeksowanie z przypisaniem:

Skutkuje to stworzeniem na chwilę obiektu domyślnego dla danego typu wartości, a potem jego zastąpieniem (przypisaniem) tym właściwym, który ma się w ‘tablicy’ znaleźć. W przypadkach, gdy konstruktor i operator przypisania nie są trywialne, będzie to strata na wydajności. Powinniśmy więc używać raczej metody insert do wstawiania. Może jest to niezupełnie “tablicowe”, ale cóż – albo rybka, albo akwarium ;P

Cokolwiek, czyli Boost.Any

Zasadniczo w C++ zmienne mają jednoznacznie określone typy, znane w czasie kompilacji. Istnieją oczywiście pewne mechanizmy, które zdają się tę zasadę lekko naciągać (dziedziczenie i polimorfizm, szablony), ale bez znaczącej nieścisłości można przyjąć, że jest ona prawdziwa. W języku kompilowanym nie jest to zresztą nic nadzwyczajnego.
Z kolei w językach skryptowych i interpretowanych dość powszechne jest używanie zmiennych bez określonego (tj. jawnie podanego w deklaracji) typu. To, co obecnie przechowuje liczbę, za chwilę może zawierać ciąg znaków czy odwołanie do obiektu i nie ma z tym specjalnego problemu. Typy w takich językach oczywiście istnieją, ale mają je wartości, nie zaś zmienne.

Czasami coś podobnego – czyli zmienna mogąca przechowywać wartości różnego rodzaju – przydaje się i w C++. Wtedy niektórzy przypominają sobie o void*, ale “ogólny wskaźnik na coś” rzadko jest w tym przypadku szczytem marzeń. Jego podstawową wadą jest to, że wymaga on przechowania gdzieś poza nim informacji o docelowym typie wartości, na którą pokazuje – jeśli chcemy ją później wykorzystać, rzecz jasna. Równie poważną jest fakt, że mamy tu do czynienia z wskaźnikiem; pamięć, na którą on pokazuje, musi być kiedyś zwolniona.
Dlatego też lepszym rozwiązaniem jest biblioteka Any z Boosta, umożliwiająca korzystanie ze zmiennych “typu dowolnego”. Reprezentuje go klasa boost::any, mogąca przechowywać wartości prawie dowolnego rodzaju (wymaganiem jest głównie to, by ich typy posiadały zwykły konstruktor kopiujący):

Ponieważ jednak jest to wciąż C++, a nie język skryptowy, do wartości zapisanych w obiekcie any bezpośrednio dostać się nie da. W szczególności nie można liczyć na niejawne konwersje powyższych zmiennych do typów int, string czy Foo. Zamiast tego korzysta się ze specjalnego operatora rzutowania any_cast, który pozwala na potraktowanie wartości zapisanej w any zgodnie z jej właściwym typem:

W przeciwieństwie do void*, próba jej reinterpretacji na inny typ danych skończy się wyjątkiem. Nie trzeba jednak polegać na jego łapaniu, jeśli docelowego typu nie jesteśmy pewni: boost::any pozwala też pobrać jego type_info (tj. to, co zwraca operator typeid) bez dokonywania rzutowania.

I to w sumie wszystko jeśli chodzi o tę klasę, a jednocześnie i całą bibliotekę. Mimo swej niewątpliwej prostoty jest ona bardzo przydatna tam, gdzie potrzebujemy zmiennych przechowujących różne rodzaje wartości. Warto więc się z nią zapoznać :)

Boost i liczby losowe

Narzekanie na jakość generatorów liczb (pseudo)losowych wbudowanych w języki programowania (takich jak rand() w C/C++) to dość popularne zajęcie wśród programistów gier. Chociaż nierzadko jest ono raczej bezpodstawne (albo ma charakter martwienia się na zapas), to niekiedy faktycznie losowość (czy raczej: nieregularność) uzyskiwanych wyników pozostawia wiele do życzenia.
Oczywiście zagadnienie generowania liczb “losowych” doczekało się mnóstwa opracowań jeszcze na długo przed tym, zanim stały się one potrzebne do wyliczania ruchu piłeczki odbitej od paletki w Pongu :) W praktyce możemy więc znaleźć mnóstwo dobrze działających implementacji różnego rodzaju generatorów liczb pseudolosowych dla większości znanych we Wszechświecie języków programowania.

Wspominam o tym, bo ostatnio sam potrzebowałem czegoś podobnego w C++. A gdzie zagląda każdy programista tego języka, gdy czegoś mu brakuje?… Do Boosta naturalnie :) Jako że jest tam (prawie) wszystko, niespecjalnie zdziwiło mnie, że istnieje cała biblioteka od szeroko pojętej losowości – Boost.Random. Zawiera ona rzecz jasna implementacje kilku różnych generatorów liczb pseudolosowych, różniących się nieregularnością wyników, szybkością, wymaganiami pamięciowymi, itd.
Tak naprawdę jednak tym, co czyni tę bibliotekę interesującą, jest sposób łączenia tych generatorów z wieloma dostępnymi tam rozkładami liczb losowych. Jeśli ktoś przysypiał na lekcjach matematyki lub wykładach z rachunku prawdopodobieństwa, to przypomnę, że – najprościej mówiąc – rozkład określa nam, jakie wartości mogą być wylosowane i jakie jest prawdopodobieństwo uzyskania każdej z nich. Przykładowo, standardowy rand teoretycznie oferuje nam liczby losowe o rozkładzie jednorodnym na zbiorze { 0, 1, …, RAND_MAX-1 }. Oznacza to, że – gdyby losowość była tu rzeczywista, a nie udawana – każda z tych wartości ma taką samą szansę na bycie wylosowaną. W przypadków innych rodzajów rozkładów nie musi tak być i niektóre wyniki mogą być bardziej preferowane niż inne (niezależnie od jakości generatora).

Jak więc wygląda to w Boost.Random? Ano całkiem zgrabnie. Najpierw bowiem wybieramy używany generator liczb, a potem pożądany rozkład, i obie te rzeczy możemy połączyć w jeden poręczny obiekt. Oto przykład:
#include

// generator liczb losowych
// (jest to pewna wersja znanego algorytmu Mersenne Twister)
boost::mt19937 rng;

// docelowy rozkład otrzymywanych liczb
// (jednorodny rzeczywisty na przedziale -1…1)
boost::uniform_real dist(-1, 1);

// wynikowy obiekt
boost::variate_generator >
random(rng, dist);

// kilka losowań
for (int i = 0; i < 10; ++i) std::cout << random() << std::endl;[/cpp] Jak nietrudno zauważyć, ten przykład pokazuje, jak bardzo C++ potrzebuje obecnego w C# od wersji 3.0 słowa kluczowego var ;-) Poza tym jednak widzimy, że otrzymany obiekt jest w użyciu bardzo prosty: aby dostać następną losową liczbę, wystarczy po prostu użyć na nim operatora (). Rezultat będzie od razu z właściwego przedziału (nie trzeba żadnych mnożeń czy dzieleń modulo), który określamy, definiując rozkład. Tutaj jest on jednorodny, ale oczywiście w Boost.Random mamy też mnóstwo innych, jak choćby geometryczny, wykładniczy, Gaussa (normalny), Bernoulliego, itp.
Nie to żeby były one jakoś często potrzebne, ale kiedy trafi się – tak jak mi – konieczność użycia któregoś z nich, to dobrze jest mieć tę bibliotekę pod ręką :)