MRJP Wykład 5

Realizacja funkcji i procedur

Instrukcja wywołania funkcji (dla procedur obowiązuje ten sam mechanizm) nakazuje rozpoczęcie wykonania funkcji a po jej zakończeniu powrót do instrukcji za wywołaniem. Historię obliczeń w programie można przedstawić w postaci tzw. drzewa aktywacji, którego węzły reprezentują wcielenia (wykonania) funkcji (korzeń to program główny) a węzeł F ma synów G1...Gn jeśli wcielenie funkcji F wywołało G1, później G2 itd. Podczas wykonania programu odwiedzamy węzły tego drzewa w porządku obejścia w głąb, od lewej do prawej. Na ścieżce od korzenia do aktualnego węzła są wcielenia funkcji, które w danej chwili wykonują się, na lewo już zakończone a na prawo te, które jeszcze się nie rozpoczęły. Jeśli istnieje ścieżka, na której występuje wiele wcieleń tej samej funkcji (nie koniecznie obok siebie), mówimy że funkcja ta jest rekurencyjna.

Z każdym wcieleniem funkcji wiążemy pewne informacje. Obszar pamięci, w którym są zapisywane nazywamy rekordem aktywacji (albo „ramką”). W językach takich jak Pascal lub C rekordów aktywacji dla wcieleń funkcji, które już się zakończyły nie trzeba przechowywać – potrzebne są tylko te, które znajdują się na aktualnej ścieżce w drzewie aktywacji.

Gdyby nie było rekurencji, dla każdej funkcji w programie moglibyśmy z góry zarezerwować obszar pamięci na jeden rekord, gdyż wiemy, że tylko tyle będzie potrzebnych. W językach dopuszczających rekurencję miejsce na rekordy aktywacji trzeba przydzielać w chwili wywołania funkcji a zwalniać je, gdy funkcja się skończy. Rekordy aktywacji przechowujemy więc na stosie.

Zawartość rekordu aktywacji

Informacje pamiętane w rekordzie aktywacji zależą m. in. od języka. Mogą tam być:

• parametry
• zmienne lokalne zadeklarowane przez programistę i zmienne tymczasowe
• ślad powrotu – informacja, do której instrukcji przekazać sterowanie po zakończeniu funkcji
• kopia rejestrów (w zależności od kompilatora przechowujemy wszystkie, niektóre lub żaden)
• łącze dynamiczne (DL, dynamic link) – wskaźnik na poprzedni rekord aktywacji. Ciąg rekordów połączonych wskaźnikami DL tworzy tzw. łańcuch dynamiczny, czyli aktualną zawartość stosu. Można uniknąć przechowywania DL w rekordzie, ale zwykle się tego nie robi.
• łącze statyczne (SL, static link) (tylko, jeśli język ze strukturą blokową) – opis poniżej miejsce na wynik

Adresowanie rekordu aktywacji

Aby funkcja podczas działania miała dostęp do swojego rekordu aktywacji, jego adres jest zwykle przechowywany w wybranym rejestrze. Pola rekordu aktywacji są adresowane przez określenie ich przesunięcia względem miejsca wskazywanego przez ten rejestr. Dzięki temu każde wcielenie funkcji, niezależnie od miejsca w pamięci, w którym znajduje się rekord aktywacji, w ten sam sposób korzysta z jego zawartości (czyli wszystkie wcielenia mają wspólny kod). Adresem rekordu aktywacji (punktem, względem którego adresowane są pola) może być jego początek lub miejsce w środku (wówczas niektóre pola będą miały przesunięcie dodatnie a inne ujemne). Można też adresować zawartość rekordu aktywacji względem czubka stosu (dzięki temu nie byłby potrzebny dodatkowy rejestr), ale to jest niewygodne, gdyż czubek stosu przesuwa się podczas obliczeń, a więc zmianie ulegałyby odległości pól rekordu aktywacji od czubka.

Protokół wywołania i powrotu z funkcji

Protokół wywołania i powrotu z funkcji opisuje czynności, które w związku z wywołaniem funkcji ma wykonać wołający (zarówno przed przekazaniem sterowania do wołanego jak i po powrocie) oraz to, co wołany (czyli każda funkcja) ma robić na początku i na końcu. Podstawowym zadaniem jest zbudowanie rekordu aktywacji oraz usunięcie go. Niektóre czynności z tym związane musi wykonywać wołający (np. liczenie parametrów), inne wołany (np. zarezerwowanie miejsca na zmienne lokalne) a jeszcze inne może wykonać zarówno wołany jak i wołający.

Zaprojektujemy protokół wywołania i powrotu z funkcji na maszynie stosowej opisanej powyżej. Założymy, że w rekordzie aktywacji znajdują się kolejno: miejsce na wynik, parametry, ślad, DL oraz zmienne. Wskaźnikiem rekordu aktywacji będzie FP, zawierający adres pola DL.

wołający
0 ; miejsce na wynik
<parametry na stos>
adres_wołanego CALL
{DROP} (tyle razy, ile jest parametrów)

wołany
FP LOAD ; DL na stos
SP LOAD FP STORE ; aktualizacja wskaźnika rekordu aktywacji
{0} (tyle razy, ile jest zmiennych)
... ; tłumaczenie treści funkcji
{DROP} (tyle razy, ile jest zmiennych)
FP STORE ; przywracamy wskaźnik rekordu aktywacji
GOTO

Podprogram otwarty (inline)

Zamiast przekazywać sterowanie między wołającym a wołanym przy pomocy skoku ze śladem, można treść funkcji wołanej wstawić w miejscu wywołania. Rozwiązanie takie nazywamy podprogramem otwartym (makro, inline). Może być bardziej efektywne, niż podprogram zamknięty (wywołanie przez skok) ale wydłuża kod a poza tym nie stosuje się do funkcji rekurencyjnych.

Struktura blokowa, środowisko

Niektóre języki programowania, np. Pascal, pozwalają na zagnieżdżanie funkcji (występuje w nich struktura blokowa). W kodzie funkcji mamy dostęp do jej danych lokalnych a także do danych funkcji, w której jest zagnieżdżona itd. w górę hierarchii zagnieżdżenia aż do poziomu globalnego. Działanie funkcji jest więc określone nie tylko przez jej kod oraz parametry, lecz także przez środowisko, w którym ma się wykonać. Postać środowiska jest w Pascalu wyznaczona statycznie – z kodu programu wynika, w rekordzie aktywacji której funkcji mamy szukać zmiennej nielokalnej. Mówimy, że w Pascalu obowiązuje statyczne wiązanie zmiennych.

Są języki, w których obowiązuje wiązanie dynamiczne – w przypadku odwołania do danej nielokalnej, szukamy jej w rekordzie aktywacji wołającego itd. w górę po łańcuchu dynamicznym.

Łącze statyczne

By korzystać z danych nielokalnych, działająca funkcja musi mieć dostęp do swojego środowiska. W języku z wiązaniem statycznym można je reprezentować przez ciąg rekordów aktywacji funkcji, które są na ścieżce w hierarchii zagnieżdżania. W każdym rekordzie będzie tzw. łącze statyczne (SL, static link) – wskaźnik do jednego z rekordów aktywacji funkcji otaczającej daną. Rekord ten nazywamy poprzednikiem statycznym, a ciąg rekordów połączonych SL to łańcuch statyczny. SL musi być liczony przez wołającego - do jego określenia trzeba znać zarówno funkcję wołaną jak i wołającą. Środowisko dla funkcji wołanej zależy od środowiska wołającej – jeśli obie widzą zmienną „x”, jej wartość ma być dla nich równa. Jeśli funkcja F znajdująca się na poziomie zagnieżdżenia Fp wywołuje G z poziomu zagnieżdżenia Gp, w pole SL wpisze adres rekordu, który odnajdzie przechodząc po własnym łańcuchu statycznym o Fp-Gp+1 kroków w górę. Jeśli np. G jest funkcją lokalną F (Gp=Fp+1), funkcja F w pole SL dla G wpisze adres swojego rekordu; jeśli F i G są na tym samym poziomie zagnieżdżenia, w polu SL dla G będzie to, co w SL dla F itd.

Dostęp do danych

Dane lokalne funkcji są w jej rekordzie aktywacji a dane globalne w ustalonym miejscu w pamięci – można do nich sięgać za pomocą adresów bezwzględnych. Z danych, które nie są ani lokalne ani globalne korzystamy przy pomocy łańcucha statycznego. W funkcji F o poziomie Fp sięgamy do zmiennej z funkcji G o poziomie Gp (oczywiście Fp>=Gp), przechodząc po łańcuchu statycznym Fp-Gp kroków w górę. Tam, pod przesunięciem, znanym podczas kompilacji, jest nasza zmienna. Adres zmiennej jest więc wyznaczony przez poziom zagnieżdżenia i przesunięcie w rekordzie.

Adresy rekordów z łańcucha statycznego można też wpisać do tablicy (tzw. display). Dzięki temu unikniemy chodzenia po łańcuchu statycznym, ale za to trzeba będzie stale aktualizować tablicę.

Mechanizm przekazywania parametrów

Dwa podstawowe tryby przekazywania parametrów:

• przez wartość – jako parametr przekazujemy wartość argumentu, z jakim funkcję wywołano
• przez zmienną (referencję) - jako parametr przekazujemy adres argumentu

Funkcje ze zmienną liczbą argumentów

W niektórych językach (np. C) funkcja może być wywoływana ze zmienną liczbą argumentów. Jeśli nie wie, ile ma parametrów, może mieć trudności z ustaleniem, gdzie w jej rekordzie są np. zmienne lokalne. Byłoby tak, gdyby adresem rekordu był jego początek. Przesunięcia zmiennych względem tego adresu zależałyby od liczby parametrów. Aby tego uniknąć, można przyjąć za adres rekordu miejsce między parametrami a zmiennymi (jak w przykładzie podanym powyżej). Dodatkowo, parametry będą w kolejności od ostatniego do pierwszego. Dzięki temu przesunięcie miejsca, w którym znajduje się K-ty parametr nie będzie zależało od liczby parametrów, tylko od stałej K. Protokół wywołania funkcji ze zmienną liczbą parametrów musi też ustalić, że po zakończeniu funkcji parametry zdejmuje wołający, bo wołany, nie zawsze wie ile ma parametrów.