Paradygmaty programowania/Ćwiczenia 4: Podprogramy

Zadanie 1

Napisz program w dowolnym języku (niekoniecznie prawdziwym), który pokazywałby różnicę między (a) przekazywaniem parametrów przez wartość i wynik a (b) przekazywaniem przez referencję. Chodzi o to, by program wypisywał inny komunikat, jeśli zostanie uruchomiony przy założeniu (a), a inny przy (b).

Zadanie 2

Zaimplementuj jeden generator liczb pseudolosowych w „czystym” C, a drugi w C# lub Javie. Jak można wykorzystać charakterystyczne cechy tych języków?

Wskazówka:

Typowy generator liczb pseudolosowych działa tak: Pierwszy wyraz ciągu, powiedzmy $x_0$, to konkretna stała lub liczba wzięta „z zewnątrz”, np. końcowe, szybkozmieniające się bity zegara systemowego. Każdy następny wyraz ciągu generowany jest na podstawie poprzedniego według zależności $x_{i+1}=(a{x}_i+b)$ mod c, gdzie a, b i c to odpowiednio dobrane stałe. Generowane są oczywiście liczby całkowite z zakresu od 0 do c – 1.

Zadanie 3

Załóżmy, że mamy kompilator pewnego języka o składni takiej jak C, o którym nie wiemy, czy zmienne lokalne są statyczne, czy dynamiczne na stosie. Napisz program, który pozwoli to sprawdzić.

Wskazówka:

Trzeba sprawdzić, czy wartość zmiennej zachowuje się pomiędzy wywołaniami funkcji.

Zadanie 4

Napisz program w dowolnym języku, który pozwoli zaobserwować różnicę w szybkości przekazywania parametrów przez wartość i przez referencję. By zminimalizować wpływ obsługi wywołań na pomiar, przekazuj w obydwu przypadkach możliwie dużą tablicę.

Wskazówka:

Pamiętaj, że w C i językach pochodnych nie da się przekazać tablicy przez wartość bez użycia pewnej „sztuczki”. Pamiętaj też, że przekazywanie tablicy po elemencie (podobnie jak wielokrotne przekazywanie jednej zmiennej np. całkowitej) da zupełnie inny rezultat.

Zadanie 5

Napisz program w języku, w którym można stosować parametry w „czystym” trybie wyjściowym, tzn. out, a nie in-out. Program ma wykazać, w którym momencie ów parametr jest wiązany z konkretną komórką pamięci — czy w chwili wywołania podprogramu, czy w chwili jego zakończenia, czy może jeszcze kiedy indziej.

Wskazówka:

Rozważ przekazanie parametru będącego odwołaniem do elementu tablicy.

Zadanie 6

Rozważmy następujący program w Adzie:

     function f(n: Integer) return Integer is

       function g(n: Integer) return Integer is
       begin
         if n <= 1 then return 1;
         else return n * f(n - 1);
         end if;
       end g;

     begin
       if n <= 1 then return 1;
       else return n * g(n - 1);
       end if;
     end f;

Jaka będzie największa długość łańcucha dynamicznego i statycznego, jeśli w wyrażeniu wywołano f(5)? Przedstaw schematycznie zawartość stosu w chwili, gdy zostanie wywołane f(1).

Zadanie 7

Jak należy zaimplementować instrukcję goto w języku, który pozwala na zagnieżdżanie podprogramów? Chodzi o sytuację, gdy goto powodowałoby „wyskoczenie” z podprogramu np. tak jak na rysunku poniżej (skok w obrębie podprogramu jest bezproblemowy, natomiast skok do wnętrza podprogramu stwarzałby niejasność co do wartości jego zmiennych lokalnych — więc go nie rozważamy).

     procedure P1

       procedure P2
       begin
       ...
       goto A;
       ...
       end P2;

     begin
     ...
     P2;
     ...
     A: ...
     ...
     end P1;

Zadanie 8

Podaj przykłady programów i sekwencji wywołań podprogramów, przy których długość łańcucha dynamicznego będzie mniejsza, równa i większa od długości łańcucha statycznego.

Zadanie 9

Co wypisuje poniższy program przy założeniu, że parametry przekazywane są przez wartość? Co, jeśli przez referencję? Co, jeśli przez wartość i wynik? Czy jest tu sytuacja, w której nie da się odpowiedzieć jednoznacznie bez ustalenia szczegółów implementacji?

     int a[] = {10, 20};
     int b = 0;

     void f(int x, int y, int z) {
       b = b+1;
       x = x+2;
       y = y+3;
       z = z+4;
       print(a[0], a[1], b, x, y, z);
     }

     void main() {
       f(a[b], b, b);
       print(a[0], a[1], b);
     }