Ostatnio na Warsztacie pojawił się problem PoKeMoNizacji tekstu. Przykładowe rozwiązanie tego problemu w Common Lispie można zawrzeć w następujących funkcjach:
(defun get-pokemonizer ()
(let ((upkemonize nil))
(lambda (letter)
(setf upkemonize (not upkemonize))
(if upkemonize
(char-upcase letter)
(char-downcase letter)))))
(defun pokemonize-string (string-to-pokemonize)
(map 'string (get-pokemonizer) string-to-pokemonize))
Problem pokemonizacji tekstu sam w sobie nie jest wart poświęcania mu miejsca, ale chciałbym wykorzystać tę okazję by pokazać kilka ciekawych rzeczy w Common Lispie.
Zacznijmy od końca. Funkcja
(defun pokemonize-string (string-to-pokemonize)
(map 'string (get-pokemonizer) string-to-pokemonize))
mogłaby w C++ być napisana jako:
#include <algorithm>
std::string pokemonize_string(std::string input)
{
std::string outStr(input);
std::transform(input.begin(), input.end(), outStr.begin(), pokemonize_letter);
return outStr;
}
std::transform z C++ i map z Common Lispu to przykłady tak zwanych funkcji wyższego rzędu*. Jak nietrudno się domyśleć, zadaniem użytych przez nas funkcji jest przejście przez cały napis znak po znaku i zastosowanie na każdym elemencie funkcji przekazanej jako parametr. Zauważmy, że nie napisaliśmy tutaj żadnej iteracji, żadnej pętli for - myślimy w kategoriach "przejścia funkcją po napisie". Taki przeskok myślowy jest bardzo cenny; w C++ zalecane jest (mniej błędów się robi) używanie algorytmów z biblioteki STL, które umieją w różny sposób stosować przekazane funkcje na elementach pojemników (polecam przeglądnąć nagłówek <algorithm>).
Skoro mamy już trzon naszego rozwiązania, warto pomyśleć nad samą funkcją pokemonizującą. Według oryginalnej definicji problemu funkcja ma sprawiać, że wynikowy tekst będzie miał co drugą literę wielką. Przyjmijmy automatycznie, że pozostałe litery mają być małe. W naszym rozwiązaniu funkcja pokemonizująca musi więc zmieniać swoje zachowanie w kolejnych wywołaniach - powinna zamieniać litery raz na małe, a raz na duże. Musimy więc w funkcji ukryć stan. Dla przypomnienia, w Common Lispie mieliśmy funkcję:
(defun get-pokemonizer ()
(let ((upkemonize nil))
(lambda (letter)
(setf upkemonize (not upkemonize))
(if upkemonize
(char-upcase letter)
(char-downcase letter)))))
Zadaniem funkcji (get-pokemonizer) jest zbudowanie funkcji pokemonizującej pojedynczy znak. Sama funkcja pokemonizująca zaczyna się od wyrażenia (lambda ..., które oznacza po prostu stworzenie funkcji anonimowej (nienazwanej). Zanim uzasadnię, dlaczego potrzebny jest generator takich funkcji, chciałbym znów odnieść się do kodu z C++ i porównać kody odpowiedzialne za samą zmianę znaku.
#include <cctype> //potrzebne do std::tolower() i std::toupper()
bool g_upCase = false;
char pokemonize_letter(char input) {
g_upCase = !g_upCase;
return (g_upCase) ? std::toupper(input) : std::tolower(input); }
W komentarzach zawarty jest odpowiadający kod w Common Lispie. Czytelniku, zastanów się przez chwilkę - co z powyższą funkcją w C++ jest nie tak?
Odpowiedź: stan jest globalny. Wyobraźmy sobie, że chcielibyśmy używać tej samej funkcji wielokrotnie. Do tego jeszcze czasem w osobnych wątkach. Widać wyraźnie, że wiele wywołań funkcji pokemonize_char() będzie pracowało na tej samej zmiennej globalnej, która trzyma stan. Przejście na zmienną statyczną nie rozwiąże problemu - jedynie ograniczy widoczność stanu (co jest dobrą rzeczą). W C++ wypracowano jednak rozwiązanie - jest nim stworzenie obiektu funkcyjnego (inaczej funktora). Jest to obiekt przeciążający operator(), czyli operator wywołania funkcji. Taki obiekt może skutecznie udawać prawdziwą funkcję, a jednocześnie trzymać w sobie stan. Lepsze rozwiązanie naszego problemu w języku C++ wyglądałoby więc tak:
#include <algorithm>
#include <cctype> //potrzebne do std::tolower() i std::toupper()
class Pokemonizer : public std::unary_function<char, char>
{
protected:
bool upCase;
public:
Pokemonizer() : upCase(false) {}
char operator()(char input)
{
upCase = !upCase;
return (upCase) ?
std::toupper(input) :
std::tolower(input);
}
};
std::string pokemonize_string(std::string input)
{
std::string outStr(input);
std::transform(input.begin(), input.end(), outStr.begin(), Pokemonizer());
return outStr;
}
W tym momencie wywołania pokemonize_string() są już thread-safe. Musieliśmy w tym celu napisać kod tak, by przy każdym wywołaniu pokemonizacji napisu tworzony był nowy obiekt funkcyjny z własnym stanem.
Wróćmy teraz do Common Lispu. Powyższy kod C++ jest odpowiednikiem rozwiązania w Lispie, więc możemy je ze sobą dokładnie porównać. Dla przypomnienia:
(defun get-pokemonizer ()
(let ((upkemonize nil))
(lambda (letter)
(setf upkemonize (not upkemonize))
(if upkemonize
(char-upcase letter)
(char-downcase letter)))))
(defun pokemonize-string (string-to-pokemonize)
(map 'string (get-pokemonizer) string-to-pokemonize))
Wspomniałem wcześniej, że zadaniem funkcji (get-pokemonizer) jest stworzenie funkcji pokemonizującej pojedynczy znak. Odpowiednikiem tej funkcji w C++ jest konstruktor funktora Pokemonizer. Jest jednak zasadnicza różnica między funkcjami C++ i Common Lispu - w tym drugim języku funkcję są tzw. obiektami first-class. Oznacza to między innymi, że taką funkcję można przechowywać w zmiennej, przypisywać i zwracać z innych funkcji. Dlatego nasz generator pokemonizerów po prostu zwraca funkcję. Innymi słowy, funkcje w Lispie posiadają te cechy, które w C++ musimy symulować za pomocą obiektów funkcyjnych.
Pozostaje jeszcze powiedzieć, w jaki sposób osadzamy stan w naszej funkcji pokemonizującej. W Lispie możemy zastosować tak zwane domknięcia. Jest to bardzo interesująca technika programistyczna. Zauważmy, że przed stworzeniem samej funkcji pokemonizującej (wyrażenie (lambda ...) definiujemy zmienną ((let ((upkemonize nil)) ...). Mówiąc językiem C++, nasza anonimowa funkcja znajduje się w zakresie zmiennej upkemonize. Co więcej, ona korzysta z tej zmiennej.
Powtórzę jeszcze raz - anonimowa funkcja, która ma zaraz zostać zwrócona z generatora używa zmiennej, która została stworzona w tym generatorze w momencie jego wywołania. upkemonize to zwykła zmienna lokalna. Nowy pokemonizer pracuje na obiekcie, który - według C++'owej intuicji - przestał istnieć tak szybko, jak tylko swoje działanie skończył generator. To może być lekko mind-blowing na początku. Dla mnie było.
Ilekroć generator zostanie wywołany, powstanie nowa zmienna upkemonize, która na stałe zostanie związana ze zwróconym pokemonizerem. Ten ostatni trzyma w niej swój stan; z jego punktu widzenia ta zmienna jest zewnętrzna, 'globalna'. Taką technikę programistyczną nazywamy domknięciem - funkcja "domyka się" nad zmienną zadeklarowaną na zewnątrz niej.
Kilka wniosków, które wynikają z powyższych rozważań:
- Funkcje wyższego rzędu są bardzo eleganckim sposobem krótkiego zapisywania algorytmów dotyczących całego zbioru danych. Zamiast ręcznie pisać pętle kopiujące, zmieniające czy dzielące duże grupy danych możemy użyć funkcji przyjmujących funkcje jako parametr, by w jednym wyrażeniu zapisać nasze rozwiązanie. W C++ spotykamy się z nimi często w STLu.
- Funktory to sposób emulacji mechanizmu funkcji jako obiektów first-class - czyli czegoś, co jest fundamentalną właściwością Lispu. Możliwość traktowania funkcji jak każdego innego typu danych jest bardzo przydatna.
- Common Lisp zawiera mnóstwo cech, które w C++ wymagają strasznego kombinowania - funkcje jako obiekty first-class, wyrażenia Lambda** i domknięcia to tylko niektóre z nich.
- Można pisać bardzo, bardzo długie elaboraty o prostych problemach ;)
* - Ściślej mówiąc, C++ tylko sprytnie emuluje funkcje wyższego rzędu - taka funkcjonalność nie jest wbudowana w język.
** - Wyrażenia Lambda, czyli tworzenie funkcji anonimowych, są elementem nowego standardu języka C++ o nazwie roboczej C++0x.