Autorzy hymnów na cześć Pascal-a rzadko kiedy dostrzegają jednak pewna inną cechę tego języka, jaka jest możliwość użycia zmiennych dynamicznych. Rzecz to niebanalna, a całkiem obca nawet najwspanialszym wersjom Basic-a czy Fortranu..
O CO CHODZI?
To znaczy — co to są owe zmienne dynamiczne? Otóż wiemy, że w Pascal-u mamy możliwość deklarowania dwóch rodzajów zmiennych — globalnych i lokalnych. Zmienne takie istnieją tylko w trakcie wykonania części programu, w której zostały zadeklarowane. Oznacza to, że w momencie, gdy rozpoczyna się wykonywanie np. procedury, program rezerwuje sobie odpowiedni obszar w pamięci dla przechowywania jej zmiennych lokalnych. Wraz z zakończeniem wykonywania procedury obszar ten jest zwalniany i może być wykorzystany do innych celów. Oczywiście tracimy przy tym wartościowych zmiennych.
W odniesieniu do takich zmiennych ukuto nazwę "statyczne", ponieważ istnieją one w pamięci przez cały czas wykonania tego modułu, w którym je zadeklarowaliśmy. Być może — rozumujemy więc — zmienne dynamiczne to takie zmienne, które możemy tworzyć i usuwać według własnego uznania, w dowolnym momencie trwania programu? Tak, o to właśnie chodzi.
Ale po co?
Oto przykład.
Wyobraźmy sobie zapisany na dysku plik, który zawiera pewne rekordy. Jak wczytać jego zawartość do pamięci? Gdybyśmy dysponowali tylko zmiennymi statycznymi, należałoby umieścić kolejne wczytywane rekordy w tablicy. No tak, ale każdy z łatwością dostrzeże tu dwie kardynalne wady:
1. Rozmiar tablicy określa maksymalną liczbę rekordów, jaka może być wczytana. Plik natomiast może zawierać więcej rekordów;
2. Z drugiej strony, plik może zawierać bardzo mało (nawet zero) rekordów. W takim wypadku duża część naszej tablicy jest bezużyteczna. Nie ma strachu, jeżeli nasz program używa tylko jednej takiej tablicy. Co jednak zrobić, kiedy chcemy jednocześnie operować kilkoma takimi plikami i pomieścić je w pamięci jednocześnie? Na zadeklarowanie kilku wystarczających rozmiarami tablic musielibyśmy poświęcić ogromne ilości pamięci.
Widzimy tu wyraźnie sens użycia zmiennych o rozmiarach, które moglibyśmy regulować w miarę naszych bieżących potrzeb. Zastosowań dla zmiennych dynamicznych można znaleźć wszakże daleko więcej — stwarza je praktyka.
Wiemy już zatem o co chodzi, pozostaje jeszcze pytanie
JAK?
Kluczem do zrozumienia mechanizmu posługiwania się zmiennymi dynamicznymi jest pojęcie (znów termin ukuty dość dawno) wskaźnika. Wyobraźmy sobie następujące typy danych:
TYPE NaszRekord = RECORD
Wys, Szer, Dług: INTEGER:
Masa: REAL:
END;
Wskaźnik = ↑ NaszRekord:
VAR P: Wskaźnik;
Definicja typu NaszRekord jest jasna. Wątpliwości budzi definicja typu Wskaźnik (ta podejrzana strzałka...). Czym jest zmienna P, należąca do tego typu?
Strzałka w definicji typu Wskaźnik oznacza, że zmienne tego typu mogą wskazywać na obiekty typu NaszRekord — wymienionego zaraz za strzałką. Co to znaczy „wskazywać"? To znaczy, że wartością takiej zmiennej może być adres (nie wnikamy w to, jak jest on reprezentowany) pewnego, znajdującego się w pamięci rekordu typu NaszRekord. Możemy tę sytuację przedstawić sobie na rysunku (rys. 1).
Tenże wskaźnik stanowi właśnie narzędzie do posługiwania się zmiennymi dynamicznymi. Jak się to robi? To proste: oto podstawowe operacje, jakich możemy dokonywać na wskaźnikach.
1. Możemy je porównywać, ale tylko przy pomocy operacji = i o. Równość oznacza, że wskaźniki wskazują na ten sam obiekt, nierówność — że na różne.
2. Musimy mieć jakąś możność wyrażenia faktu, że wskaźnik nie wskazuje na żaden obiekt znajdujący się w pamięci. W tym celu Pascal zawiera stałą standardową NIL. Oznacza ona po prostu „adres nieistniejący".
Oto przykłady użycia:
P := NIL;
IF Q = NIL THEN...
3. Na zmienną będącą wskaźnikiem możemy podstawiać NIL lub wartość dowolnej innej zmiennej — byle należała ona do tego samego typu wskaźnikowego (wskaźnik wskaźnikowi nierówny — zależnie od tego, na jakiego typu obiekt wskazuje).
P := Q; Q:= NIL;
4. Ważna operacja:
NEW(P);
jest standardową procedurą Pascal-a. Jej działanie jest następujące: zostaje utworzony w pamięci nowy obiekt typu wskazywanego przez parametr, a następnie parametr zaczyna wskazywać na ów obiekt. W powyższym przykładzie w pamięci zostanie zarezerwowane miejsce na nowy rekord typu NaszRekord, zaś zmienna P zaczyna to miejsce — inaczej: nowo utworzony rekord — wskazywać.
5. No tak, ale ja teraz dostać się do poszczególnych pól nowego rekordu? Skoro P nam go wskazuje, pozostaje tylko użyć następujących oznaczeń:
P ↑ — oznacza obiekt wskazywany przez P, a zatem cały rekord typu NaszRekord.
P .Masa — oto, jak dostajemy się do poszczególnych pól wskazywanego rekordu. Gdyby obiektem wskazywanym była np. tablica, to prawidłowy mógłby być np. zapis P f [10]. Oto kilka przykładów:
P↑ -Masa := 1.05;
WITH P↑ DO BEGIN
Wys := 100;
Szer := 10;
END;
P ↑ Dług := P ↑ .Szer;
6. Musimy jeszcze mieć możność usunięcia wybranych struktur z pamięci. Realizację takiego żądania zapewnia standardowa procedura DIS- POSE. Jej parametrem jest znów wskaźnik.
DISPOSE (P);
Procedura ta powoduje, że zostaje usunięty z pamięci obiekt wskazywany przez P (to znaczy, że zajmowana przezeń pamięć jest zwalniana).
Uzbrojeni w ten zestaw operacji możemy zabrać się do pracy. Na początek zastanówmy się nad problemem przechowywania w pamięci ciągu rekordów, który postawiliśmy na początku.
STRUKTURY LISTOWE
Jak zatem reprezentować w pamięci taki ciąg rekordów, postępując w sposób oszczędny?
Sęk w tym, aby zbudowana struktura danych zajmowała w pamięci tylko tyle miejsca, ile potrzebne jest dla wczytanych rekordów — nie więcej.
Zaproponujemy tu rozwiązanie, które w praktyce okazuje się najbardziej ekonomiczne — mianowicie uszeregowanie naszych rekordów w listę. Czym jest lista? To proste: zauważmy, że wewnątrz rekordu NaszRekord możemy umieścić pola dowolnych typów. Zadeklarujmy tam więc dodatkowo pole typu Wskaźnik. Wtedy rekord typu NaszRekord będzie mógł sam zawierać wskaźnik do innego rekordu, ten zaś do innego, ten do innego... i tak dalej, aż w końcu wskaźnik w którymś rekordzie byłby równy NIL — i na tym lista by się zakończyła. Dla lepszego wyobrażenia sobie takiej sytuacji mamy rysunek 2. Pokazuje on dodatkowo, że zachodzi potrzeba posiadania wskaźnika do pierwszego rekordu takiego ciągu. W przeciwnym wypadku nie mielibyśmy dostępu ani do niego, ani do żadnego z pozostałych rekordów listy.
Spróbujmy zatem zdefiniować odpowiednie typy danych.
TYPE Wskaźnik = ↑NaszRekord;
NaszRekord = RECORD
Wys.Szer.Dlug: INTEGER;
Masa: REAL;
Nast: Wskaźnik
END;
VAR Początek, P, Q: Wskaźnik;
Zaraz, zaraz — powie zaraz spostrzegawczy czytelnik — w tej definicji typów nie jest spełniona zada predefinicji, bo typ NaszRekord jest użyty ZANIM w tekście wystąpi jego definicja. Czytelnik będzie miał rację. więcej, w tym konkretnym przypadku nie jest możliwy taki zapis powyższego fragmentu programu, aby zasada definiowania pojęć przed ich użyciem była zachowana w pełni. Dlatego też mamy tu do czynienia z JEDYNYM dopuszczonym w Pascal-u odstępstwem od zasady predefinicji. Mówiąc ściślej, typ wskaźnikowy wolno w tym języku zdefiniować zanim zdefiniuje się typ obiektu wskazywanego.
Skoro już zdefiniowaliśmy typ takiej struktury — jak ją samą utworzyć?
Potrzebna będzie nam jedna zmienna typu Wskaźnik, która pokazywałaby stale na pierwszy z ciągu rekordów. Do wykonywania operacji na rekordach dalszych możemy użyć pomocniczych zmiennych wskaźnikowych, które wskazywałyby na rekordy aktualnie przez nas przetwarzane. Można też postąpić inaczej i w celu uzyskania dostępu do rekordów wewnątrz listy posłużyć się algorytmami rekurencyjnymi. Program przykładowy zamieszczony obok pokazuje, że ich użycie aż się prosi w tym przypadku.
Program ten stanowi rozwiązanie postawionego na początku artykułu problemu na przykładzie prostego notesu telefonicznego. Do wykonywania wszelkich operacji na liście rekordów użyto procedur rekurencyjnych — warto je przeanalizować. Podobne algorytmy, zapisane nierekurencyjnie, znaleźć można w książce N. Wirtha „Wstęp do programowania systematycznego".
Na zakończenie kilka praktycznych uwag, dotyczących posługiwania się zmiennymi wskaźnikowymi.
1. Trzeba pamiętać, że wskaźnikom nie jest nadawana żadna inicjalna wartość. W szczególności należy pamiętać, aby wskaźnikom nadawać na początku programu wartość NIL. Odwołanie poprzez wskaźnik o nieokreślonej wartości prowadzić może do trudnych do wykrycia błędów.
2. Należy pamiętać o tym, by nie dopuścić do istnienia obiektów dynamicznych nie wskazywanych przez żaden wskaźnik. Do takich obiektów nie sposób się dostać; również nie można ich usunąć procedurą DISPOSE.
3. Jeżeli tworzymy nowy obiekt wskazywany przez NEW (P), to przed następnym wywołaniem NEW (P) musimy zadbać o zachowanie wartości P, które jest wtedy wskaźnikiem do pierwszego utworzonego obiektu. W przeciwnym przypadku ów obiekt znajdzie się w sytuacji z punktu 2.
4. Trzeba uważać, by nie odwoływać się do obiektu wskazywanego przez zmienną, gdy jest ona równa NIL. W wielu przypadkach narzucałoby się np. użycie takiej instrukcji:
IF (P<-NIL) AND (P↑ .Masa = O) THEN...
...nie jest to jednak prawidłowe. Pascal wartościuje bowiem wszystkie człony wyrażenia logicznego i z tego powodu będzie starał się obliczyć Pf .Masa niezależnie od tego, czy P jest równe NIL, czy też nie. Prawidło- wo należy tę instrukcję rozbić na dwie:
IFP<>NIL THEN
IF P↑.Masa = O THEN...
5. Należy uświadomić sobie, że instrukcja przypisania w odniesieniu do wskaźników ma nieco inne skutki, niż do tego przywykliśmy. Normalnie bowiem efektem przypisania
Q:= P;
jest skopiowanie wartości zmiennej P do zmiennej O. W przypadku, gdy P i Q są zmiennymi wskaźnikowymi dzieje się podobnie, ale kopiowane są wskaźniki, a nie obiekty wskazywane! Jeżeli np. P wskazuje pewien rekord, to efektem powyższego przypisania będzie sytuacja jak na rys. 3.
W tej sytuacji instrukcja np.
P .Masa: = O
zmienia jednocześnie wartość pola Q .Masa — bo przecież w gruncie rzeczy są to te same pola! Jeszcze gorzej jest w przypadku, gdy wykonamy DISPOSE (O). Wskaźnik P nie zmienia przy tym oczywiście swojej zawartości, ale dalsze odwoływanie się do wskazywanego przezeń rekordu nie ma sensu i może prowadzić do przykrych błędów. Dlatego też w przypadku usuwania obiektu wskazywanego przez wiele wskaźników należy je wszystkie wyszukać i nadać im wartość NIL.
Sądzę, że publikowany program stanowi przykład rzeczywistej wygody, jaką daje posługiwanie się listami. Dla porównania proponuję przejrzeć artykuł „Naprawdę nie święci garnki lepią" z nru 3/87 „Bajtka". Opisane tam proste bazy danych spełniają funkcje podobne do naszej — ale dla uzyskania podobnego efektu w Basic-u trzeba było uciekać się do niewygodnych metod typu przechowywania rekordów w tablicy — a o wadach tego rozwiązania już wiemy.
Program został napisany w Turbo Pascal-u. Ponieważ opis tego języka był już w „ Bajtku" publikowany, sądzę, że w razie potrzeby da się on bez trudu przełożyć na inny dialekt Pascal-a.
LITERATURA
1. Nikiaus Wirth „Wstęp do programowania systematycznego", wyd. I, WNT 1982 — seria BIO;
2. M. Iglewski, J. Madey, S. Matwin „Pascal", wyd. III, WNT 1984 — seria BIO.
Marek Wyrwidąb
