Algorithm Animation Pages
WinSANAL System Home Page

Streszczenie: W artykule omawiany jest system animacji algorytmow WinSanal. Umozliwia on dokonywanie wizualizacji ilustrujacych sposob dzialania algorytmow i programow komputerowych. Pozwala osiagnac dobra jakosc wizualizacji przy stosunkowo niewielkim nakladzie pracy. Zawiera mechanizmy, dzieki ktorym moze sluzyc nie tylko jako pomoc dydaktyczna, lecz i program wspomagajacy uruchamianie (debugger).

1. WSTEP

Zrozumienie sposobu dzialania algorytmow jest jednym z najwazniejszych wymagan stawianych tworcom oprogramowania. Technika ulatwiajaca zrozumienie algorytmow, uzyteczna zarowno dla osob przygotowujacych sie do zawodu informatyka, jak i dla profesjonalistow, jest wizualizacja, czyli uwidocznienie wybranych cech algorytmow za pomoca odpowiednio dobranych srodkow graficznych. Odmiana wizualizacji jest animacja — jej efektem jest obraz plynnie zmieniajacy sie w czasie. Metodom i technikom animacji algorytmow poswiecono w ostatnich latach wiele uwagi; opracowano szereg systemow animacji, z ktorych do najbardziej znanych naleza Balsa [1, 3] i XTango [10]. System WinSanal [6, 7], ktorym zajmujemy sie w tym artykule, projektowany byl jako narzedzie do tworzenia zarowno wyrafinowanych wizualizacji o przeznaczeniu dydaktycznym, jak i dobrej jakosci, czytelnych wizualizacji roboczych, tworzonych doraznie przez osoby piszace i uruchamiajace nowe algorytmy i programy.

2. CHARAKTERYSTYKA SYSTEMU

System WinSanal stanowi nowa, gruntownie zmieniona wersje systemu Sanal opracowanego w Instytucie Informatyki Politechniki Slaskiej w 1989 i rozwijanego do 1996 roku [4, 5]. Pracuje pod kontrola systemu operacyjnego MS-Windows i umozliwia wizualizacje programow napisanych w jezyku C++.

W systemie WinSanal starano sie pogodzic postulaty istotne dla dwoch grup uzytkownikow. Jakosc wizualizacji ma duze znaczenie dla obserwatora, ogladajacego przebieg wizualizowanego algorytmu, tj. jego projekcje. Natomiast cecha istotna dla uzytkownika — wizualizatora jest latwosc przygotowania projekcji, a w szczegolnosci — mozliwosc przynajmniej czesciowego zautomatyzowania tej czynnosci. Stasko i Patterson [11], a niezaleznie od nich Roman i Cox [8] twierdza, ze wymienione tu postulaty wzajemnie sie wykluczaja. Istniejace dotad systemy wizualizacji badz to wymagaja znacznego nakladu pracy ze strony wizualizatora, badz tez oferuja jedynie stosunkowo proste wizualizacje. System WinSanal pozwala na tworzenie dosc wyrafinowanych projekcji, a przy tym sposob ich przygotowania nie jest uciazliwy, aczkolwiek — jak dotychczas — jeszcze dosc zmudny; oczywiscie, pracochlonnosc wzrasta wraz ze stopniem wyrafinowania wizualizacji. Juz wkrotce system zostanie wyposazony w modul automatyzujacy znaczna czesc czynnosci zwiazanych z przygotowaniem projekcji.

2.1. AKWIZYCJA DANYCH WEJSCIOWYCH

WinSanal jest systemem sterowanym danymi. Oznacza to, ze wartosci danych poddawanych wizualizacji sa podczas projekcji pobierane samoczynnie. Wszystkie obserwowane dane musza byc wczesniej zarejestrowane w systemie. W systemach sterowanych zdarzeniami (np. w systemie Sanal) wartosci danych byly jawnie przekazywane do systemu wizualizacji.

W trakcie projekcji system musi byc powiadamiany o zmianach wartosci obserwowanych zmiennych. Obecnie jest to realizowane poprzez wstawienie do tekstu zrodlowego wywolan specjalnych funkcji. Czynnosc te da sie latwo zautomatyzowac; implementacje prostego preprocesora tekstow programow wykonujacego to zadanie planujemy na najblizsza przyszlosc. Preprocesor ma rowniez zautomatyzowac czynnosci zwiazane ze wstepna rejestracja danych przeznaczonych do wizualizacji.

2.2. TRANSLACJA I UZUPELNIANIE DANYCH — GENEROWANIE ABSTRAKCJI

Wizualizacja zadowalajaca dla uzytkownika-obserwatora nie moze sie ograniczac do izomorficznego odwzorowania struktur danych lub kodu na odpowiednia postac graficzna. Powinna ona stanowic wizualna ilustracje semantyki algorytmu: oprocz elementow wynikajacych ze stanu, w jakim znajduje sie algorytm w danej chwili, moze obejmowac inne, zwiazane bezposrednio lub posrednio z procesem wykonania algorytmu; zadaniem ich wszystkich jest pomoc w zrozumieniu sposobu dzialania oprogramowania. Mowimy, ze wizualizacja powinna sie odznaczac wysokim poziomem abstrakcji [8, 9].

Dobrym przykladem moze byc potraktowanie procesu wykonywania algorytmu jako uporzadkowanego przeplywu danych; zobrazowaniu podlega ten przeplyw. Jedynym mierzalnym skutkiem wykonywania algorytmu sa dyskretne (skokowe) zmiany wartosci danych, ktore latwo mozna zaobserwowac przy pomocy tradycyjnych programow uruchamiajacych (debugerow). Dla zrozumienia algorytmu znacznie latwiejszy jest model, w ktorym stylizowane dane przeplywaja pomiedzy poszczegolnymi strukturami, przechodzac przez kontinuum polozen posrednich. Takich polozen nie obserwujemy w systemach komputerowych, chyba ze na poziomie ukladow elektronicznych.

System WinSanal dostarcza srodki pozwalajace na stosunkowo latwe konstruowanie projekcji o wysokim poziomie abstrakcji. Umozliwia to warstwowa struktura systemu. Dane pobrane z obserwowanego programu sa poddawane szeregowi transformacji zdefiniowanych przez uzytkownika. Po przetworzeniu dane moga oddzialywac na jeden lub na wiele aspektow obrazu koncowego, i odwrotnie, na kazdy aspekt obrazu wplywac moga dane pochodzace z jednego lub z wielu zrodel w obrebie obserwowanego programu. Szczegolna uwage poswiecono stworzeniu mechanizmow umozliwiajacych plynna animacje polozen posrednich. Wymagalo to wlaczenia do lancucha (sciezki) transformacji danych tzw. generatorow sekwencji, wprowadzajacych do strumienia danych dodatkowe informacje, nie majace odpowiednikow w strukturach obserwowanego programu, a umozliwiajace realizacje kolejnych etapow plynnego ruchu elementow graficznych. Generatory te stanowia tez poczatek pomocniczych sciezek przeplywu danych, wykorzystywanych do zdefiniowania trajektorii, wzdluz ktorych przesuwaja sie elementy obrazu.

W powiazaniu ze swoboda doboru koncowej reprezentacji graficznej opisane srodki pozwalaja na realizacje wyrafinowanych projekcji bez koniecznosci modyfikowania tekstu zrodlowego programu (abstrahujac od opisanych wczesniej uzupelnien zwiazanych z akwizycja danych wejsciowych).

2.3. REPREZENTACJA GRAFICZNA

Jednym z najistotniejszych czynnikow wplywajacych na jakosc wizualizacji jest bogactwo jej formy graficznej. W systemie WinSanal zaimplementowano podsystem graficzny, stanowiacy wyspecjalizowana biblioteke graficzna, pozwalajaca na tworzenie elementow wizualnych, zwanych grelami. Parametry charakteryzujace grel, takie jak polozenie, kolor, tekstura czy ksztalt moga byc w trakcie projekcji zmieniane w sposob skokowy lub ciagly. W tym ostatnim przypadku uzyskujemy efekt plynnej wizualizacji. Otwarta, obiektowa architektura biblioteki greli pozwala na latwa rozbudowe repertuaru dostepnych reprezentacji graficznych stosownie do potrzeb; biblioteke, jaka dysponujemy, wzbogacamy obecnie m. in. o srodki do przedstawiania struktur grafowych.

2.4. INTERAKCJA Z SYSTEMEM

W czasie projekcji uzytkownik moze wchodzic w interakcje z systemem. Wartosci danych mozna precyzyjnie badac i ustawiac za pomoca okienek inspekcyjnych lub bezposrednio manipulujac obiektami graficznymi na ekranie. Istnieje rowniez mozliwosc zatrzymywania i ponownego uruchamiania projekcji, a takze sterowania tempem pokazu.

2.5. PRACA WIZUALIZATORA

Z natury rzeczy systemy sterowane danymi, w porownaniu z systemami sterowanymi zdarzeniami, wymagaja mniejszego nakladu pracy zwiazanej z uzupelnianiem tekstu programu.

Przygotowanie wizualizacji w systemie WinSanal zaczynamy od wyboru danych, ktore maja byc poddane wizualizacji. Nastepnie dla kazdej z nich definiujemy koncowa reprezentacje graficzna oraz ciag transformacji, ktore do niej prowadza. Dobieramy je z obszernego repertuaru wzorcow i schematow obslugiwanych przez moduly biblioteczne. Wreszcie dokonujemy niezbednych uzupelnien tekstu zrodlowego programu poddawanego wizualizacji.

Moze sie okazac, ze same srodki dostepne w systemie sa niewystarczajace dla potrzeb zamierzonej wizualizacji. I tak, w braku wyspecjalizowanego modulu prezentujacego grafowe struktury danych, aby moc zrealizowac jedna z wizualizacji w [6] do programu wprowadzono pomocnicza strukture danych przechowujaca niektore parametry istotne przy konstruowaniu obrazu, i dodano niezbedny dla jej obslugi kod programu. W pewnych przypadkach moze okazac sie celowe rozszerzenie repertuaru srodkow graficznych lub schematow translacji, a w konsekwencji — uzupelnienie bibliotek systemowych.

W chwili pisania tego artykulu przygotowanie wizualizacji wykonywane jest recznie. Wizualizator moze skorzystac z zawartosci wzorcowych plikow konfiguracyjnych, zawierajacych ciagi instrukcji do wstepnego ustawienia parametrow poszczegolnych greli, a takze do konfigurowania sciezek transformacji danych. Instrukcje nakazujace systemowi odczytanie aktualnych wartosci wizualizowanych danych i zobrazowanie biezacej sytuacji trzeba rozmiescic osobiscie. Sytuacja zmieni sie po zakonczeniu realizacji modulu wspomagajacego przygotowanie projekcji. W sklad modulu bedzie wchodzic wspomniany w p. 1.a preprocesor rozmieszczajacy w tekscie programu zrodlowego instrukcje sterujace przebiegiem projekcji, bazujacy na analizie przeplywu danych. Druga czesc modulu umozliwi konfigurowanie w trybie interaktywnym parametrow wplywajacych na postac projekcji.

3. ZASTOSOWANIA

Systemy wizualizacji algorytmow znalazly szerokie zastosowanie w dydaktyce [2, 5]. Ilustracje sa powszechnie stosowanym narzedziem w nauczaniu algorytmiki; by sie o tym upewnic, wystarczy spedzic kilka minut na dowolnym wlasciwie wykladzie prowadzonym dla studentow informatyki (nauka programowania, analiza algorytmow, konstrukcja translatorow).

Ze wzgledu na znaczna pracochlonnosc przygotowania projekcji, zastosowanie systemow wizualizacji algorytmow w inzynierii programowania nie zdolalo sie, jak dotad, rozpowszechnic. Wzgledna prostota i latwosc obslugi systemu WinSanal (przynajmniej po zaimplementowaniu planowanych modulow automatyzujacych prace wizualizatora) moga zachecic programistow do siegniecia do tego narzedzia w praktyce inzynierskiej. System moze stac sie odmiana graficznie sterowanego programu uruchamiajacego (debuggera).

4. PRZYKLAD DZIALANIA

Dzialanie systemu WinSanal zademonstrujemy na przykladzie wizualizacji algorytmu tlumaczenia wyrazen arytmetycznych z postaci infiksowej na odwrotna notacje polska (rys. 1). W gornej czesci okienka graficznego wyswietlana jest zawartosc ciagu wejsciowego. Kolejno analizowane znaki sa przenoszone badz to do ciagu wyjsciowego, polozonego w dolnej czesci okienka, badz tez na umieszczony po prawej stronie stos operatorow. Ilustracja przedstawia moment, w ktorym kolejnym analizowanym elementem ciagu wejsciowego jest nawias zamykajacy; operatory umieszczone na szczycie stosu zostaja przeniesione do ciagu wyjsciowego.

W przedstawionej wizualizacji bierze udzial zestaw elementow graficznych (greli), ktore na poczatku projekcji reprezentuja poszczegolne znaki ciagu wejsciowego. W toku wykonywania algorytmu znaki ciagu wejsciowego sa przepisywane do ciagu wyjsciowego lub ewentualnie na stos; obrazujemy to zmieniajac polozenie greli na ekranie. Wizualizacja elementarnej operacji przypisania jest realizowana za pomoca funkcji bibliotecznej _PlayFlow. Przygotowanie algorytmu do projekcji polegalo na umieszczeniu w tekscie programu odpowiednich wywolan tej funkcji (uzyta rowniez funkcja _Play umozliwia zobrazowanie wartosci zmiennych). Uzupelniony tekst algorytmu zamieszczamy ponizej.

_InitPlay(); 
char *pIn = in, *pOut = out, *pStack = stack; 
*pStack = '('; _Play(pStack); 
do 
{ 
  if (isalpha(*pIn)) 
    { *pOut++ = *pIn; _PlayFlow(pOut-1, pIn); } 
  else 
  if (isoperator(*pIn)) 
  {
    while (pr(*pStack) >= pr(*pIn)) 
      { *pOut++ = *pStack--; _PlayFlow(pOut-1, pStack+1); } 
    *++pStack = *pIn; _PlayFlow(pStack, pIn); 
  } 
  else 
  if (*pIn == '(') 
    { *++pStack = *pIn; _PlayFlow(pStack, pIn); } 
  else 
  if (*pIn == ')' || *pIn == '\0') 
  { 
    while (*pStack != '(') 
      { *pOut++ = *pStack--; _PlayFlow(pOut-1, pStack+1); } 
    *pStack--; _Play(pStack+1); 
  } 
  else 
    break; // illegal character 
} while (*pIn++); 
*pOut = '\0'; _Play(pOut); 

Omawiana wizualizacja osiagnieta zostala najprostszymi srodkami, poprzez mechaniczne oznakowanie tekstu zrodlowego. W przedstawionym algorytmie znaki otwierajacego i zamykajacego nawiasu nie sa przepisywane do ciagu wyjsciowego; w konsekwencji reprezentujace je grele pozostaja po zakonczeniu projekcji w ciagu wejsciowym lub na stosie, sprawiajac wrazenie „smieci" pozostalych po wykonaniu algorytmu. Dla projektanta algorytmu efekt ten niesie dodatkowe informacje na temat gospodarki zmiennymi; w przypadku wizualizacji dydaktycznej moze jednak nie byc pozadany. Latwo go wowczas usunac wprowadzajac niewielkie modyfikacje.

5. UWAGI KONCOWE

System WinSanal, o ktorym byla mowa w tym artykule, jest produktem nowym i przechodzi obecnie faze probnych zastosowan. Doswiadczenia wynikajace z pierwszych wizualizacji zrealizowanych za jego pomoca (w tej liczbie rowniez zaprezentowanej wizualizacji przykladowej) sklonily nas do doraznego wprowadzenia szeregu zmian i uzupelnien. Dotycza one m.in. repertuaru elementarnych operacji graficznych, jakie mozna wykonywac z udzialem greli i niewidocznych dla obserwatora obiektow wlaczonych w lancuch przeksztalcen, jakim poddawane sa dane przed wyswietleniem. Wnioski i obserwacje wykorzystamy przy realizacji modulu automatyzujacego przygotowanie programow do projekcji, od ktorego bedzie w duzym stopniu zalezec praktyczna przydatnosc calego systemu dla roznych kategorii uzytkownikow.

PISMIENNICTWO

[1] M.H.Brown, Exploring Algorithms Using Balsa-II, Computer, Vol. 21, May 1988, pp. 14-36

[2] M.H. Brown, N. Meyrowits, A. van Dam, Personal Computer Networks and Graphical Animation: Rationale and Practice for Education

[3] M.H.Brown, R.Sedgewick, A System for Algorithm Animation, Computer Graphics, SIGGRAPH’84 Conference Proceedings, 18(3), Minneapolis, Minn., 1984, pp. 177-186

[4] J.Francik, P.Szmal, Wizualizacja synchroniczna algorytmow — realizacja w systemie SANAL, Zeszyty Naukowe Politechniki Slaskiej, seria Informatyka z.27, Gliwice, 1994

[5] J.Francik, P.Szmal, Wizualizacja algorytmow z wykorzystaniem systemu SANAL, X konferencja "Informatyka w szkole", Torun, 1994

[6] J. Francik, P. Szmal, M. Nowak, Systemy wizualizacji algorytmow wspomagajace badania naukowe, III krajowa konferencja Komputery w badaniach naukowych KOWBAN, Polanica Zdroj, 1996

[7] M.Nowak, Mechanizmy prezentowania danych w postaci symbolicznej i interakcyjnego wprowadzania danych dla systemu animacji algorytmow SANAL, Praca dyplomowa magisterska, Politechnika Slaska, Instytut Informatyki, Gliwice 1996

[8] G. C. Roman, K. C. Cox, Program visualization: the art of mapping programs to pictures, International Conference on Software Engineering, New York, 1992, pp. 412-20

[9] G. C. Roman, K. C. Cox, Abstraction in algorithm animation, Proceedings of 1992 IEEE Workshop on Visual Languages, pp. 18-24, 1992, Los Alamitos, CA, USA

[10] J.Stasko, Animating Algorithms with XTANGO, SIGACT News, Vol.23, Iss.2, Spring 1992, pp. 67-71

[11] J. T. Stasko, C. Patterson, Understanding and characterizing software visualization systems, Proceedings of 1992 IEEE Workshop on Visual Languages

[Jaroslaw Francik: strona domowa]

Copyright © 1997 by Jaroslaw Francik.
Revised: April 15, 1997

This site is a part of personal pages of Jaroslaw Francik. Go back to his  home page
Copyright © 2000 by Jaroslaw Francik
Last modified: 21/02/00