Paradygmaty programowania/Wykład 4: Podprogramy

Wstęp

Podprogramy realizują jedną z dwóch podstawowych abstrakcji programowania, mianowicie abstrakcję procesu. O ile abstrakcja danych rozpowszechniła się dopiero w latach 80-tych XX wieku, abstrakcja procesu wydawała się czymś oczywistym od zarania dziejów algorytmiki i programowania. Któż nie chciałby budować programów z gotowych fragmentów, realizujących dobrze określone zadania w sposób szybki i niezawodny? By uświadomić sobie, jak daleka droga dzieli tworzenie wielkich systemów informatycznych od pisania drobnych programów w asemblerze, przytoczmy prosty przykład programu asemblerowego i jego odpowiednik w języku C (a przecież od owego programu w C do wielkiego systemu jest wciąż ogromnie daleko...).

     petla:
       pushl %ebp
       movl %esp,%ebp
       movl 8(%ebp),%ecx
       movl 12(%ebp),%edx
       xorl %eax,%eax
       cmpl %edx,%ecx
       jge .L1
     .L2:
       incl %ecx
       decl %edx
       incl %eax
       cmpl %edx,%ecx
       jl .L2
     .L1:
       incl %eax
       movl %ebp,%esp
       popl %ebp
       ret

Odpowiednik w języku C:

     int petla(int x, int y)
     {
       int wyn;
       
       for (wyn = 0; x < y; wyn++) {
         x++;
         y--;
       }
       return wyn + 1;
     }

Pamiętajmy, że abstrakcja danych i związana z nią metodologia tworzenia programów, rozpowszechniona wraz z językami obiektowymi, nie zastępuje abstrakcji procesu, lecz ją uzupełnia. Przyjrzenie się podprogramom i sposobom ich implementacji odsłania wiele dalece nieoczywistych szczegółów (by nie rzec — tajemnic) języków programowania. Tak jak dotychczas, podprogramy będziemy rozumieli szeroko, obejmując tym pojęciem wszelkie procedury, funkcje, metody itp.

Mówiąc o podprogramach będziemy zakładali, że:

• Każdy podprogram posiada jeden punkt wejścia.
• Program wywołujący podprogram zostaje zawieszony na czas działania podprogramu.
• Sterowanie zawsze powraca do programu wywołującego w momencie zakończenia działania podprogramu.

Sprawy składniowe

• Definicja podprogramu opisuje sposób komunikowania się podprogramu z otoczeniem oraz sposób działania podprogramu.
• Nagłówek podprogramu mówi o tym, że następujący po nim fragment kodu jest definicją podprogramu, podaje jego nazwę oraz (niekoniecznie) wyszczególnia parametry.
• Sygnatura podprogramu to liczba, porządek i typ jego parametrów formalnych.
• Protokół podprogramu to opis parametrów formalnych (czyli sygnatura) oraz typ wyniku (o ile taki istnieje).
• Podprogramy mogą mieć definicje i oddzielne deklaracje. Te drugie są używane w niektórych językach programowania (np. w C i C++, gdzie nazywane są prototypami i umieszczane są zwykle w plikach .h).

Przekazywanie parametrów

Podprogram nie będący metodą ma dostęp do danych na dwa sposoby: przez zmienne nielokalne (zgodnie z zasadami zakresu widoczności) oraz przez przekazane parametry. Oczywiście drugi sposób jest znacznie lepszy, gdyż pozwala na jasne zdefiniowanie sprzężenia podprogramu z otoczeniem, bez polegania na trudnych często do uchwycenia efektach ubocznych. Metoda ma dodatkowo dostęp do danych obiektu, z którego jest wołana.

W pewnych sytuacjach chcielibyśmy przekazać do podprogramu nie tyle dane, co sposób obliczeń. Pewne języki na to pozwalają. Szerzej zajmiemy się tą sprawą w przedstawionych poniżej przykładach.

Wypunktujmy podstawowe definicje dotyczące przekazywania parametrów:

• Parametry w nagłówku nazywane są parametrami formalnymi.
• Parametry w instrukcji wywołania podprogramu, które zostaną przypisane parametrom formalnym, nazywane są parametrami aktualnymi.
• W większości języków, odpowiedniość pomiędzy parametrami formalnymi a aktualnymi ustalana jest poprzez zestawienie ich położenia w liście. Mówi się, że są to parametry pozycyjne.
• Stosuje się też wiązanie parametrów formalnych z aktualnymi na podstawie nazw podanych wraz z parametrami aktualnymi. Są to parametry z kluczem.
• Niektóre języki pozwalają na użycie parametrów z wartością domyślną, np. Ada, C++, PHP. Wówczas liczba parametrów aktualnych może być mniejsza niż liczba parametrów formalnych.
• Niektóre języki programowania posiadają mechanizmy przekazywania zmiennej liczby parametrów, np. params w C++. Wróćmy teraz do przekazywania przez parametr sposobu obliczeń. Załóżmy, że piszemy funkcję, która służy do całkowania funkcji na liczbach rzeczywistych. Chcielibyśmy, by jej parametrami były: funkcja do scałkowania oraz granice przedziału całkowania. Innymi słowy, chcielibyśmy móc używać naszej funkcji np. tak:

     wynik = całkuj(sin, 0, 0.123)

Pierwszym parametrem jest tu funkcja sin. Typem takiego parametru jest cały protokół przekazywanej funkcji(tu np.: jeden parametr double i wynik double). Nie każdy język na to pozwala. W Pascalu można przekazywać funkcje i procedury bezpośrednio. W C i C++ można przekazywać wskaźniki do funkcji, co daje podobny efekt. W C# można używać delegatów instancjonowanych dla żądanej metody.

Przykład przekazywania wskaźnika do funkcji w języku C

• Rozważmy następującą funkcję:

     double calkuj(double f(double), double a, double b)
     {
       ...
       x = f(...);
       ...
     }

• Wywołanie może wyglądać tak, jak opisano powyżej.
• W „klasycznej” składni języka C nagłówek wyglądałby tak:

     double calkuj(double (*f)(double), double a, double b)

Przykład użycia delegatów w C#

• Deklarujemy odpowiedni typ delegata:

     delegate double dtype(double, double);

• Metoda służąca do całkowania może mieć postać:

     double calkuj(dtype f, double a, double b)
     {
       ...
       x = f(...);
       ...
     }

• Załóżmy, że jako parametr chcemy przekazać metodę f z klasy C. Tworzymy zatem delegata:

     dtype dfun = new dtype(C.f);

• Możemy teraz wykorzystać delegata w wywołaniu, np.

     wynik = A.calkuj(dfun, 1.2, 3.4);

Rozważmy teraz rozróżnienie pomiędzy procedurami a funkcjami. Pod względem technicznym, procedury i funkcje różnią się jedynie zwracaniem wartości, tzn. procedury jej nie zwracają. Semantycznie jednak różnica jest istotna. Procedury są zestawem instrukcji, które definiują sparametryzowane obliczenia. Są one uruchamiane poprzez pojedyncze wywołanie. Można zatem powiedzieć, że procedury definiują nowe instrukcje. Funkcje natomiast przypominają funkcje matematyczne. Są wywoływane poprzez użycie ich nazwy w wyrażeniu. Nie powinny dawać żadnych efektów ubocznych (typowych w przypadku procedur). Funkcje definiują zatem nowe operatory. Języki programowania oparte na języku C formalnie nie posiadają procedur, ale funkcje typu void zachowują się tak jak procedury.

Kolejna sprawa: sprawdzanie zgodności typów parametrów

• Niewątpliwie jest korzystne...
• Wczesne wersje Fortranu i C nie sprawdzały.
• Większość współczesnych języków to czyni.
• Są jednak wyjątki: JavaScript, Perl, PHP.
• Język C w wersji z końca lat 80-tych dawał wybór.
• Jeśli typy parametrów były zadeklarowane poza listą parametrów, to zgodność typów nie była sprawdzana:

     int f(x)
       double x;
       {...}

• Jeśli typy były wymienione w owej liście, to ich zgodność była sprawdzana:

     int f(double x)
       {...}

• W C i C++ można uniknąć sprawdzania typów za pomocą nagłówka z wielokropkiem, np.

     int printf(const char *format, ...)

Problemy implementacyjne

Twórca języka programowania musi podjąć wiele decyzji, których skutki sięgają niejednokrotnie znacznie dalej niż mogłoby się wydawać. Przykładowo, stworzenie kompilatora dla zbyt wyrafinowanego języka może być trudne. Ta przypadłość spotkała niektóre języki, np. Adę. A to — być może — dopiero początek kłopotów, jakie będą spotykały programistów, zmuszonych do uczenia się zawiłych konstrukcji. Tak było z... Adą. Decyzje odnoszące się do implementacji podprogramów są o tyle ważne, że wchodzą tu w grę bardzo złożone mechanizmy.

Wymieńmy zatem niektóre kwestie związane z podprogramami:

• Wybór sposobów przekazywania parametrów.
• Czy typ parametrów aktualnych będzie sprawdzany z typem parametrów formalnych?
• Czy lokalne zmienne będą alokowane statycznie, czy dynamicznie?
• Czy definicje podprogramów mogą być zagnieżdżone?
• Jeżeli podprogramy mogą być zagnieżdżane i mogą być przekazywane jako parametry, to co jest środowiskiem przekazywanego podprogramu?
• Czy podprogramy mogą być przeciążane?
• Czy podprogramy mogą być uniwersalne (rodzajowe)?

Konsekwencją istnienia podprogramów jest m.in. powstanie lokalnego środowiska odwołań. Powiedzmy zatem parę słów o zmiennych lokalnych. Lokalne zmienne w podprogramach mogą być statyczne bądź dynamiczne alokowane na stosie. Te pierwsze są szybkie i niezależne od historii wywołań (co może być użyteczne na przykład w generowaniu liczb pseudolosowych). Te drugie umożliwiają wywołania rekurencyjne. W języku C oraz C++, lokalne zmienne są dynamiczne, chyba że jawnie zadeklarowano, że mają być statyczne. Języki C++, C# i Java nie zezwalają na użycie zmiennych statycznych w metodach.

Sposoby przekazywania parametrów

Na początku zajmiemy się różnymi modelami semantycznymi, a następnie rozważymy modele i decyzje implementacyjne.

• Parametr formalny charakteryzuje jeden z trzech modeli semantycznych:
  • Może otrzymać dane poprzez odpowiadający mu parametr aktualny (tryb wejściowy, in).
  • Może przekazywać dane do parametru aktualnego (tryb wyjściowy, out).
  • Może też używać obu trybów (tryb wejściowo-wyjściowy, in-out).
• Przekazanie danych może następować na dwa sposoby:
  • Kopiowana jest faktyczna wartość (do wywoływanego podprogramu, do programu wołającego lub w obie strony).
  • Dostęp do danych przekazywany jest pośrednio (np. przez wskaźnik).

Modele przekazywania parametrów można implementować jako:

• Przekazywanie przez wartość.
• Przekazywanie przez wynik.
• Przekazywanie przez wartość i wynik.
• Przekazywanie przez referencję.
• Przekazywanie przez nazwę.

Przekazywanie przez wartość

• Wartość parametru aktualnego jest używana do zainicjowania odpowiadającego mu parametru formalnego.
• Parametr formalny funkcjonuje następnie w podprogramie jako zmienna lokalna.
• Tak implementujemy semantykę trybu wejściowego.
• Dane przekazuje się zwykle przez kopiowanie wartości, ale można też użyć dostępu pośredniego (z dodatkowym zabezpieczeniem przed zmianą wartości parametru aktualnego).
• Przekazywanie przez wartość jest kosztowne, gdy trzeba przekazać duże struktury danych.

Przekazywanie przez wynik

• Nie przekazujemy wartości do podprogramu.
• Parametr formalny działa jak zmienna lokalna.
• Tuż przez przekazaniem sterowania z powrotem do wywołującego, wartość parametru formalnego jest przesyłana do parametru aktualnego w programie wywołującym.
• Parametr aktualny musi zatem być zmienną (a nie np. wyrażeniem arytmetycznym).
• Tak implementujemy semantykę trybu wyjściowego.
• Dane przekazuje się zwykle przez kopiowanie.
• Przy przekazywaniu przez wynik może dojść do kolizji parametrów aktualnych, np. przy wywołaniu subp(x, x). Załóżmy, że formalne parametry podprogramu subp to a i b. Jaka powinna być wartość x, jeśli subp zawiera podstawienia a := 1; b := 2?
• Inny problem: Załóżmy, że parametr aktualny to T[i]. Jeśli podprogram zmieni wartość zmiennej i, gdzie powinna znaleźć się zwrócona wartość, tzn. czy powinniśmy użyć starej czy nowej wartości indeksu?

Przekazywanie przez wartość i wynik

• Jest to kombinacja dwóch wcześniejszych sposobów implementacji, dająca semantykę trybu wejściowo-wyjściowego.
• Zwane niekiedy przekazywaniem przez kopiowanie, jako że parametr aktualny jest kopiowany do parametru formalnego, a następnie kopiowany z powrotem przy zakończeniu podprogramu.

Przekazywanie przez referencję

• Jest to alternatywna implementacja semantyki trybu wejściowo-wyjściowego.
• Dostęp do danych przekazywany jest pośrednio, czyli przekazywany jest w istocie wskaźnik do wartości a nie sama wartość.
• Podprogram zyskuje więc faktyczny dostęp do parametru aktualnego.
• Taki sposób przekazania jest efektywny.
• Przekazywanie przez referencję może powodować aliasowanie, np. w przypadku wywołań subp(x, x) lub subp(T[i], T[j]) przy i = j.
• Aliasowanie może również się pojawić na skutek kolizji między parametrami formalnymi a zmiennymi nielokalnymi.
• Zauważmy, że rzecz jest podobna (choć nie identyczna...) do kolizji parametrów aktualnych przy przekazywaniu przez wynik.

Przekazywanie przez nazwę

• Ten sposób implementuje semantykę trybu wejściowo-wyjściowego.
• Parametr aktualny jest wstawiany (tekstowo) w miejsce odpowiadającego mu parametru formalnego, we wszystkich wystąpieniach w podprogramie.
• W poprzednio omówionych sposobach było inaczej — parametry formalne były wiązane z aktualnymi wartościami (lub adresami) w chwili wywołania podprogramu.
• Przy przekazywaniu przez nazwę parametr formalny jest wiązany z metodą dostępu do danych w chwili wywołania podprogramu, ale właściwe wiązanie z wartością lub adresem następuje dopiero w momencie odwołania lub przypisania do owego parametru formalnego.
• Jest to „późne wiązanie” — kosztowne...

Sposoby przekazywania parametrów w różnych językach

Omówimy teraz pokrótce przekazywanie parametrów w kilku popularnych językach.

Fortran

• Używał trybu wejściowo-wyjściowego od zarania dziejów.
• Implementacja jako przekazywanie przez referencję lub wartość i wynik.
• Nowsze wersje pozwalają na wybranie trybu (in, out, inout), podobnie jak w Adzie.

Język C

• Stosuje zawsze przekazywanie przez wartość.
• Można jednak przekazywać (przez wartość) wskaźniki, co daje efekt taki jak tryb wejściowo-wyjściowy z przekazywaniem przez referencję.
• W szczególności, wskaźniki do stałych pozwalają uzyskać tryb wejściowy (niejawne zabezpieczenie przed zmianą wartości parametru w wywoływanej funkcji) z efektywnością właściwą dla przekazywania przez referencję.
• Nie ma bezpośredniego sposobu przekazania tablicy inaczej niż przez przekazanie wskaźnika do niej, gdyż nazwa tablicy jest traktowana jako wskaźnik. Stąd tablice są w istocie przekazywane przez referencję. Mechanizm ten można ominąć, umieszczając tablicę jako fragment rekordu (struct) i przekazując ów rekord.
• Zwróćmy uwagę na różnicę między „przekazywaniem wskaźnika do x przez wartość” a „przekazywaniem x przez referencję”. W pierwszym przypadku programista musi (jawnie) pobrać i przekazać wskaźnik; w drugim — programista nie musi pobierać wskaźnika.

Język C++

• Oprócz tego, co w języku C, dostępne są parametry referencyjne, dające przekazywanie przez referencję.
• Zauważmy różnicę między parametrami stałymi (deklarowanymi z użyciem const) a parametrami w trybie wejściowym w ogóle. Te pierwsze realizują oczywiście semantykę trybu wejściowego, z dodatkową cechą: nie mogą być zmieniane nawet w obrębie podprogramu. W większości języków natomiast parametry wejściowe funkcjonują jako zmienne lokalne — ich wartość można zmieniać, choć nie ma ona wpływu na parametry aktualne.

Java

• Stosuje zawsze przekazywanie przez wartość.
• Ponieważ jednak obiekty są dostępne tylko przez zmienne referencyjne, w istocie obiekty są przekazywane przez referencję.

Ada

• Używa trzech trybów: in, out, in out.
• W ten sposób jawnie stosujemy trzy modele semantyczne.
• Dodatkowo, pod parametry in nie można podstawiać, a do parametrów out nie można się odwołać inaczej niż po lewej stronie podstawienia.

C#

• Podobnie do C++, z dodatkowymi cechami opisanymi poniżej.
• Jawne przekazywanie przez referencję jest możliwe przy użyciu słowa kluczowego ref (trzeba je umieścić i w nagłówku podprogramu, i w wywołaniu, tzn. przy parametrze formalnym i przy aktualnym).
• Użycie czystego trybu wyjściowego jest możliwe przy użyciu słowa kluczowego out. Tryb ten jest implementowany za pomocą przekazywania przez referencję.

PHP

• Podobnie do C#, z tym że przekazanie przez referencję wystarczy wskazać w jednym miejscu (za pomocą znaku &) — przy parametrze formalnym lub przy aktualnym.

Per1

• Wszystkie parametry aktualne są umieszczane w predefiniowanej tablicy @_.
• Jej elementy są aliasami dla parametrów aktualnych.
• Jeśli element @_ zostanie zmieniony, zmiana ta jest odzwierciedlana w odpowiadającym mu parametrze aktualnym (o ile jest to zmienna).

Implementacja przekazywania parametrów

Zakładamy, że przekazywanie parametrów odbywa się za pośrednictwem stosu — tak jest w zdecydowanej większości języków programowania.

Przekazywanie przez wartość i/lub wynik jest realizowane poprzez kopiowanie wartości na stos/ze stosu. Odpowiednia komórka pamięci na stosie jest alokowana w chwili wywołania podprogramu. W trakcie działania podprogramu funkcjonuje ona jako zmienna lokalna.

Przekazywanie przez referencję jest realizowane poprzez umieszczenie odpowiedniego adresu na stosie. Jeśli parametr aktualny jest stałą (a w szczególności literałem, np. „abc”, 12.34), to na stosie trzeba umieścić jej adres. Kompilator nie może pozwolić, by parametr taki był zmieniany. Jeśli parametr aktualny jest wyrażeniem, na stosie trzeba umieścić adres komórki pamięci z wynikiem wyrażenia.

Przekazywanie wielowymiarowych tablic

To jest trudne, jeśli kompilator ma generować kod podprogramu oddzielnie, tzn. nie znając wymiarów tablicy

• Przykładowo, znajomość liczby kolumn jest konieczna, by prawidłowo odwoływać się do elementów tablicy dwuwymiarowej, gdyż adres(A[i, j]) = adres(A[0, 0]) + i * (liczba kolumn) + j.
• Zatem np. w C/C++ liczba kolumn musi być jawnie podana, int f(int matrix[][88]).
• Inny sposób to przekazanie wskaźnika i rozmiaru tablicy, np.

     int f(int *wsk, int wiersze, int kolumny)
     {...
      x = *(wsk + i*kolumny + j);
     ...}

• W innych językach rozmiar przekazywanej do podprogramu tablicy jest ustalany w czasie kompilacji (np. w Adzie).
• Co więcej, Ada pozwala na używanie jako parametrów formalnych tablic nieoznaczonych, bez podanego rozmiaru. Parametry aktualne mogą wówczas mieć różne rozmiary, a kod podprogramu określa ów rozmiar za pomocą atrybutu range.
• Podobnie jest w C# i Javie. Parametrem formalnym może być tablica bez określenia rozmiaru. Rozmiar określa się sprawdzając własność Length obiektu stanowiącego tablicę (tablice są obiektami; tablice wielowymiarowe są tablicami tablic).

Nazwy podprogramów w roli parametrów

Materia jest delikatna... Dobrze, by sprawdzany był cały protokół przekazywanej funkcji. W jęzuku C/C++ osiąga się to przekazując wskaźniki do funkcji, jako że typ takiego wskaźnika to właśnie protokół funkcji. Ada nie pozwala na przekazywanie podprogramów jako parametrów. W zamian za to można używać podprogramów rodzajowych (o czym będzie później). W C# mamy do dyspozycji delegatów. Mechanizm ten pozwala nie tylko na przekazywanie metod statycznych, ale również metod z konkretnych instancji.

Jakie środowisko powinno być użyte do wykonywania przekazanego przez parametr podprogramu? Są trzy możliwości:

• Środowisko instrukcji (w podprogramie), wywołującej przekazany podprogram. Jest to wiązanie płytkie.
• Środowisko definicji przekazanego podprogramu. W tym przypadku mówimy o wiązaniu głębokim.
• Środowisko instrukcji, która przekazała podprogram jako parametr. Jest to wiązanie ad hoc.
• Wydaje się, że w językach z zakresem wiązanym statycznie najbardziej naturalne jest wiązanie głębokie.

Podprogramy przeciążone i rodzajowe

Operator przeciążony to operator, który ma więcej niż jedno znaczenie. Wybór konkretnego znaczenia dokonywany jest na podstawie typów operandów. Przykładowo, x + y oznacza dodawanie całkowite, jeśli i x, i y są typu całkowitego. W przeciwnym razie jest to dodawanie zmiennopozycyjne. Tak jest w wielu popularnych językach.

Przeciążony podprogram to taki, który ma więcej niż jedną definicję w tym samym środowisku odwołań. By dało się je odróżnić, każda wersja musi mieć inny protokół. Niektóre języki wymagają, by wersje przeciążonego podprogramu różniły się sygnaturą, tzn. nie mogą różnić się jedynie typem wyniku. Jest to m.in. konsekwencja stosowania niejawnych konwersji typów, sprawiających, że np. w podstawieniu double x = f(...) nie da się powiedzieć, czy f daje wynik typ double, float, czy int. Tak jest w C++, C# i w Javie. W Adzie inny typ wyniku wystarcza do rozróżnienia.

Podprogram rodzajowy (zwany też polimorficznym) to podprogram, któremu w różnych wywołaniach można przekazać parametry różnych typów. Podprogramy przeciążone są szczególnym rodzajem podprogramów polimorficznych. Mówimy tu o polimorfizmie ad hoc. Mówimy o polimorfizmie parametrycznym, jeśli podprogram ma parametr rodzajowy, którego używa się do opisu typu parametrów. Chodzi tu o mechanizm taki jak np. szablony definiowane za pomocą template w C++. Ada oferuje jednostki rodzajowe (o których będzie mowa za chwilę). Wszystkie wspomniane powyżej rodzaje polimorfizmu można określić mianem polimorfizmu statycznego — decyzja o użyciu konkretnej wersji podprogramu zapada w czasie kompilacji. Z polimorfizmem dynamicznym mamy do czynienia w niektórych językach, które dopuszczają sparametryzowane abstrakcyjne typy danych (o czym mówiliśmy w poprzednim wykładzie), oraz przy dynamicznym wiązaniu wywołań metod (o czym powiemy w wykładzie poświęconym programowaniu obiektowemu).

Omówimy teraz kilka kwestii związanych z polimorfizmem.

Polimorfizm statyczny i dynamiczny

• Jednostki rodzajowe w Adzie i funkcje zdefiniowane w C++ za pomocą template wymagają oddzielnej wersji kodu podprogramu dla każdego użytego typu parametrów. Wiązanie wywołań podprogramu z poszczególnymi wersjami kodu jest statyczne.
• Jeśli wiązanie typu parametrów formalnych z typem parametrów aktualnych jest dynamiczne (lub jeśli język nie ma typów...), wystarcza jedna wersja kodu.
• Instancjonowanie dynamiczne w C# można uznać za rozwiązanie pośrednie.

Jednostki rodzajowe w Adzie

• Są to wzorce procedur.
• Kod jest generowany dopiero w chwili instancjonowania podprogramu rodzajowego konkretnym typem.
• Przykład:

     procedure SortowanieCałk is new
       SortowanieRodz(Indeksy => Integer; Elementy => Integer);

• W definicji SortowanieRodz pojawiają się „niedodefiniowane” typy Indeksy i Elementy.
• Ten mechanizm pozwala uzyskać efekt zbliżony do przekazywania podprogramów jako parametrów.
• Należy w tym celu instancjonować niedodefiniowany podprogram (w jednostce rodzajowej) za pomocą konkretnego podprogramu.

Przypomnijmy, jak działają funkcje rodzajowe w C++

• Używa się parametrów „typowych” w nawiasach ostrych < >.
• Przykładowo:

     template <class T>
       T max(T x, T y)
       { return (x > y) ? x : y; }

• Taka funkcja jest niejawnie instancjonowana, gdy odwołanie do niej pojawi się w programie, np.

     int a, b, c;
     float d, e, f;
     a = max(b, c);
     d = max(e, f);

• W powyższym przykładzie kompilator wygeneruje dwie wersje kodu, jedną dla typu int i drugą dla typu float.
• Zauważmy, że do poprawnego działania funkcji potrzebne jest, by dla użytych typów określony był operator porównania >.

Implementacja podprogramów

Semantyka wywołań podprogramów i powrotów z podprogramów

Z wywołaniem podprogramu wiążą się następujące czynności:

• Przekazanie parametrów.
• Alokacja i wiązanie pamięci dla niestatycznych zmiennych lokalnych.
• Przechowanie stanu programu wywołującego.
• Przekazanie sterowania do podprogramu.
• Jeśli dopuszczamy zagnieżdżone podprogramy, trzeba zapewnić (i odpowiednio ustawić) mechanizm dostępu do zmiennych nielokalnych.

Z powrotem z podprogramu wiążą się następujące czynności:

• Skopiowanie parametrów w trybie wyjściowym (o ile są).
• Dealokacja pamięci na zmienne lokalne.
• Przywrócenie stanu programu wywołującego.
• Przywrócenie stanu mechanizmu dostępu do zmiennych nielokalnych.
• Przekazanie sterowania z powrotem do programu wywołującego.

Implementacja podprogramów bez zagnieżdżeń, bez rekurencji i ze statycznymi zmiennymi lokalnymi

W tej sytuacji nie wszystkie czynności wspomniane powyżej są konieczne

• Nie potrzebujemy mechanizmu dostępu do zmiennych nielokalnych, gdyż wszystkie zmienne są statyczne.
• Nie dopuszczamy wywołań rekurencyjnych.
• Taki podprogram składa się z właściwego kodu, zmiennych lokalnych oraz rekordu aktywacyjnego.
• Rekord aktywacyjny zawiera:
  • Informację o stanie podprogramu wywołującego.
  • Parametry.
  • Adres powrotu (dokąd należy wrócić po wykonaniu podprogramu).
  • Wynik, o ile jest potrzebny.

Kod podprogramu jest niezmienny, natomiast zmienne lokalne i rekord aktywacyjny mogą zmieniać się w trakcie wykonania podprogramu

• Struktura rekordu aktywacyjnego jest jednak statyczna.
• Jako że nie dopuszczamy rekurencji, w dowolnej chwili aktywna może być tylko jedna wersja danego podprogramu.
• Tylko jedna może być zatem instancja jego rekordu aktywacyjnego.
• W takim przypadku rekord aktywacyjny może być przechowywany razem z kodem podprogramu.

Implementacja podprogramów bez zagnieżdżeń, ale z rekurencją i z dynamicznymi zmiennymi lokalnymi na stosie

Sprawa jest nieco bardziej skomplikowana

• Kompilator musi wygenerować kod obsługujący niejawną alokację i dealokację zmiennych lokalnych.
• W danej chwili może istnieć więcej niż jedna instancja danego podprogramu.
• Może zatem istnieć więcej instancji zmiennych lokalnych i rekordu aktywacyjnego.
• Rozsądne jest przechowywanie rekordu aktywacyjnego na stosie, razem ze zmiennymi lokalnymi.

Zauważmy, że nawet jeśli w danej chwili istnieje więcej niż jedna instancja danego podprogramu (jesteśmy „w trakcie” rekurencji), to odwołania do zmiennych lokalnych dotyczą tych z ostatniej instancji

• Dostęp do wszelkich zmiennych obejmuje zatem dwie możliwości: zmienne globalne (alokowane statycznie) lub zmienne lokalne (w rekordzie aktywacyjnym na szczycie stosu).
• Do zmiennej lokalnej sięgamy znając jej położenie względne.
• Położenie względne to położenie zmiennej względem początku rekordu aktywacyjnego. Jest ono statycznie ustalane przez kompilator w trakcie przetwarzania deklaracji zmiennych w podprogramie.

By ułatwić dealokację pamięci na stosie, rekord aktywacyjny podprogramu zawiera łącze dynamiczne

• Jest to adres ostatniej komórki pamięci wykorzystywanej przez rekord aktywacyjny podprogramu wywołującego (czyli poprzednika dynamicznego).
• Gdy podprogram kończy działanie, wierzchołek stosu ustawia się na tę właśnie wartość.
• W ten sposób przywracamy sytuację sprzed wywołania podprogramu.
• Ciąg łączy dynamicznych od rekordu aktywacyjnego danego podprogramu, poprzez kolejne poprzedniki dynamiczne, aż do rekordu aktywacyjnego podprogramu wywołanego najwcześniej (main) to łańcuch dynamiczny.

Implementacja podprogramów z zagnieżdżeniami, z rekurencją i z dynamicznymi zmiennymi lokalnymi na stosie, w językach ze statycznym wiązaniem zakresu

Oprócz dotychczas omówionych czynności, potrzebny jest mechanizm dostępu do zmiennych nielokalnych

• Chodzi o zmienne nielokalne, ale też nieglobalne (te ostatnie są statyczne, więc dostęp jest prosty).
• Dostęp do zmiennych nielokalnych jest dwuetapowy.
• Zmienne te znajdują się gdzieś na stosie...
• W pierwszym etapie trzeba znaleźć instancję rekordu aktywacyjnego, gdzie zmienna została zaalokowana.
• W drugim etapie należy sięgnąć do zmiennej, znając jej położenie względne.
• Podobnie jak poprzednio jest ono znane w czasie kompilacji.

Łącza statyczne

• W rekordzie aktywacyjnym umieszcza się łącze statyczne.
• Jest to adres początku rekordu aktywacyjnego (najpóźniejszej instancji) statycznego poprzednika podprogramu.
• Ciąg łączy statycznych od rekordu aktywacyjnego danego podprogramu do rekordu aktywacyjnego podprogramu najbardziej zewnętrznego (main) to łańcuch statyczny.
• Zagnieżdżenie zakresów widoczności jest znane w czasie kompilacji, zatem dla każdej zmiennej kompilator może statycznie określić długość fragmentu łańcucha statycznego, który należy przejść, by dotrzeć do owej zmiennej.

Implementacja podprogramów z zagnieżdżeniami, z rekurencją i z dynamicznymi zmiennymi lokalnymi na stosie, w językach z dynamicznym wiązaniem zakresu

Mamy do dyspozycji dwie metody

• Dostęp głęboki: Zamiast podążać wzdłuż łańcucha statycznego, idziemy wzdłuż łańcucha dynamicznego.
• Dostęp płytki: Jest to alternatywna metoda implementacji (opisana poniżej), dająca taką samą semantykę.

Dostęp płytki

• Zmienne nie są przechowywane razem z rekordami aktywacyjnymi.
• Dla każdej zmiennej tworzy się osobny stos.
• Za każdym razem, gdy tworzona jest zmienna, alokowana jest dla niej komórka na odpowiednim stosie.
• Przy zakończeniu podprogramu, ze stosów przechowujących zmienne tego podprogramu zdejmuje się ostatnią komórkę.
• Przy odwołaniu do zmiennej odczytuje się wierzchołek odpowiedniego stosu, jako że tam jest „najświeższa” wersja.
• Alternatywnie, można przechowywać globalną tablicę z odsyłaczami do zmiennych, aktualizowaną przy każdym wywołaniu i powrocie z podprogramu.