Nowoczesne wyliczanie

W chyba każdy języku posiadającym pojemniki (jak wektory czy listy) istnieje koncepcja iteratorów: obiektów, które pozwalają na przeglądanie kolekcji i są uogólnieniem wskaźników. W najprostszym pozwalają one tylko na pobranie aktualnego elementu i przejście do następnego, ale jest to zupełnie wystarczające do celów wyliczania.
Z wierzchu więc wyglądają one całkiem prosto i przejrzyście – zwłaszcza, jeśli język udostępnia pętlę typu foreach, która ładnie i przezroczyście je opakowuje. Dlatego może wydawać się dziwne, czemu zazwyczaj mechanizm ten jest używany właściwie tylko dla pojemników; w teorii bowiem za pomocą iteratorów (zwanych gdzieniegdzie enumeratorami) można by było przeglądać dosłownie wszystko.
Weźmy chociażby wyszukiwanie plików na dysku – sporo programów w jakimś momencie swojego działania musi znaleźć pliki np. o danej nazwie w określonym katalogu. Wtedy zwykle zakasujemy rękawy i piszemy odpowiednią procedurę rekurencyjną lub bawimy się ze stosem czy kolejką. A czy nie fajniej byłoby, gdyby dało się to zrobić po prostu tak:

oczywiście przeszukując w ten sposób również podkatalogi bez jawnego “wchodzenia” do nich?… Według mnie to by było bardzo fajne :)

Od razu zaznaczę więc, że wbrew pozorom taki iterator jest jak najbardziej możliwy do napisania. Problemem jest jednak to, jak należy przechowywać jego stan. Kiedy wyszukiwanie czy przeglądanie zaimplementowane jest bezpośrednio jako jedna funkcja, robi się to w zasadzie samo: w postaci zmiennych lokalnych (stos/kolejka) albo parametrów (rekurencja). Nikt specjalnie nie zwraca na ten fakt uwagi. Jednak w momencie próby “wyciągnięcia” z algorytmu operacji Next (w celu stworzenia iteratora) okazuje się nagle, że wymaga to jawnego pamiętania tych wszystkich danych, które pozwalają obliczyć następny element. Przy przeszukiwania katalogów trzeba by na przykład pamiętać jakiś systemowy uchwyt wyszukiwania dla aktualnego katalogu, poziom zagnieżdżenia oraz analogiczne uchwyty… dla każdego takiego poziomu!
Zawracanie głowy, prawda? :) Nic dziwnego, że traktowanie wyszukiwania “per iterator” nie jest popularną praktyką. Z punktu widzenia piszącego algorytm wyliczania nieporównywalnie łatwiej jest po prostu wymusić jakiś callback i wywołać go dla każdego elementu; niech się programista-klient martwi o to, jak ten callback wpasować w swój kod. A że ten byłby o wiele czytelniejszy, gdyby w grę wchodziły iteratory? No cóż, iteratorów tak łatwo pisać się nie da…

…chyba że programujemy w Pythonie. Tam bowiem “iteratory” (zwane generatorami) piszemy w zupełnie unikalny, łatwy sposób. Weźmy dla przykładu taką oto klasę drzewa binarnego (BST – Binary Search Tree):

I już – to wystarczy, by poniższa pętla:

rzeczywiście “chodziła” po krawędziach drzewa “w czasie rzeczywistym” – bez żadnego buforowania elementów na liście.

Tajemnica tkwi tutaj w instrukcji yield – działa ona jak “tymczasowe zwrócenie” elementu, który jest przetwarzany przez ciało pętli for. Gdy konieczny jest następny element, funkcja inorder podejmuje po prostu działanie począwszy od kolejnej instrukcji – i tak do następnego yielda, kolejnego cyklu pętli i dalszej pracy funkcji. yield działa więc jak callback, tyle że w obie strony. Całkiem zmyślne, czyż nie?
Aż chciałoby się zapytać, czy w innych językach – zwłaszcza kompilowanych – nie dałoby się zrobić czegoś podobnego. Teoretycznie odpowiedź jest pozytywna: przy pomocy zmyślnych sztuczek na stosie wywołań funkcji (technika zwana ‘nawijaniem stosu’ – stack winding) można uzyskać efekt “zawieszenia funkcji” po zwróceniu wyniku i mieć możliwość powrotu do niej począwszy od następnej instrukcji. Nie jestem jednak przekonany, jak taki feature mógłby współpracować z innymi elementami współczesnych języków programowania, jak choćby wyjątkami. Trudno powiedzieć, czy jest to w ogóle możliwe.

Ale skoro w Pythonie się da, to może już C++2x będzie to miał? ;-)