Niektóre języki programowania dopuszczają przeciążanie funkcji, tzn. można zadeklarować wiele wersji funkcji które różnią się tylko typami argumentów (czy zwracanych wartości). Inne dopuszczają niejawne konwersje, np. liczby z mniejszego zakresu można użyć wszędzie tam gdzie dopuszczalne są liczby z większego zakresu. Celem zadań niżej jest przypatrzenie się temu jak tego typu konstrukcje wpływają na budowę kompilatora.

Zadanie 1

W języku który dopuszcza konwersje domyślne (np. liczby z mniejszego zakresu można użyć wszędzie tam gdzie dopuszczalne są liczby z większego zakresu) i przeciążanie funkcji przy sprawdzaniu poprawności wywołania trzeba uwzględniać potencjanie dużą ilość konwersji. Jedna taktyka polega na przeglądaniu wszystkich możliwych konwersji i sprawdzaniu czy dla danych typów argumentów dostępna jest odpowiednia wersja funkcji. Inna taktyka polega na przeglądaniu listy dostępnych wersji funkcji i sprawdzaniu czy można skonwertować argumenty tak by pasowały dla danej wersji. Porównać te taktyki, w szczególności oczekowaną liczbę operacji.

Zadanie 2

Niektóre języki programowania dopuszczają przeciążanie funkcji, tzn. można zadeklarować wiele wersji funkcji które różnią się tylko typami argumentów (czy zwracanych wartości). W kompilatorze dla pojedynczego wywołania zwykle stosuje się taktykę pełnego przeglądania dostępnych (zadeklarowanych) możlowości. Dla większych fragmentów mozliwe są taktyki rekursywnego dopasowania z nawracaniem (najpierw próbujemy dobrać typ najbardzej zewnętrznie występującej funkcji, potem dobieramy typy dla wyrażeń dających argumentym jak argumenty nie pasują to wracamy do najwyższego poziomu) i strategia "z dołu do góry" (najpierw patrzymy na możliwości dla najprostszych podwyrażeń, potem dla bardziej skomplikowanych, w szczególności możliwe typy dla wywołania funkcji badamy po zbadaniu możliwości dla argumentów). Jakie są wady a jakie zalety obu tych podejść. Oszacować złożoność obliczeniową.

Zadanie 3

Niskopoziomowo program składa się z ciągów instrukcji obliczeniowych zaczynających się od etykiety a kończących się skokiem. Od czasów programowania strukturalnego zaleca się unikanie skoków. Jeśli nie przejmujemy się wielkością i szybkością programu to istnieje bardzo prosta metoda przekształcenia programu ze skokami na program bez jawnych skoków. Mianowicie, wprowadzamy zmienną pomocnią s (której niskopoziomowo odpowadały licznik rozkazów procesora), dla każdej etykiety ei wprowadzamy nową wartość wi tej zmiennej, skok do etykiety ei zastępujemy podstawieniem wi do s, ciąg od etykiety ei do skoku zastępujemy instrukcją 'if' która wykonuje się tylko wtedy gdy wartość s to ei, cały program otaczemy pętlą 'while' kończącą się gdy zmienna pomocnicza ma wartość odpowiadającą zakończeniu programu. Np. program:

l0:
if (a>=b) {
   goto l1;
} else {
   goto l2;
}
l2:
  tmp = b;
  b = a;
  a = tmp;
  goto l1;
l1:
  if (a == b) {
      goto koniec;
  } else {
      goto l3;
  }
l3:
  tmp = b;
  b = a % b;
  a = tmp;
  goto l1;

zastępujmy przez:

enum {l0, l1, l2, l3, koniec} s;
s = l0;
while(s != koniec) {
    if (s == l0) {
        if ((a>=b) {
            s = l1;
        } else {
            s = l2;
        }
    }
    if (s == l1) {
        if (a == b) {
            s = koniec;
        } else {
            s = l3;
        }
    }
    if (s == l2) {
        tmp = b;
        b = a;
        a = tmp;
        s = l1;
    }
    if (s == l3) {
        tmp = b;
        b = a % b;
        a = tmp;
        s = l1;
    }
}

Jeśli stosujemy naiwny kompilator to "strukturalna" wersja często wykonuje więcej operacji niż wersja ze skokami. Dokładniej, można oczekiwać rzędu połowy okrążenia głownej pętli aby uzyskać efekt skoku. Wspólczesne kompilatory mają szereg optymalizacji które mogą poprawić sytuację, w szczególności jeśli skok prowadzi do skoku warunkowego i wynik sprawdzania waruneku jest znany w trakcie kompilacji to pierwszy skok modyfikuje się tak by prowadził prosto do celu, omijając sprawdzanie warunku w tracie wykonania i drugi skok. Pokazać że używając odpowiednie optymalizacje kompilator może z wersji "strukturalnej" odtworzyć kod równoważny wersji ze skokami, bez dodatkowych zmiennych czy zbędnych operacji. Komentarz: powyższe zadanie jest trochę sztuczne, ale w praktyce często mamy wybór między ładniejszym kodem który przy naiwnej kompilacji byłby mało wydajny, a mniej ładnym kodem. Wtedy pojawia się problem dobrania optymalizacji tak, by ładniejszy kod dawał tak dobrą wydajność jak mniej ładny.