MRJP Wykład 4

Klasyfikacja realizacji języków programowania

Realizacje języków programowania można podzielić na kilka kategorii:

• kompilator - tłumaczy program w języku źródłowym na program w języku docelowym

• translator - jak wyżej, ale tłumaczenie konstrukcji języka źródłowego na konstrukcje języka docelowego odbywa się w dużym stopniu jeden do jednego

• interpreter - wykonuje program posługując się jakąś jego reprezentacją

Podział ten nie jest ścisły - wiele realizacji można zaliczyć do kilku kategorii. W szczególności, realizacje języków programowania tradycyjnie nazywane interpreterami składają się zwykle z dwóch części: program źródłowy jest kompilowany do postaci pośredniej, która następnie trafia na wejście interpretera.

Język docelowy, maszyny wirtualne

Język docelowy kompilatora zwykle nie pokrywa się z językiem maszyny rzeczywistej, na której programy mają działać. Po pierwsze, niektórych cech maszyny kompilator nie wykorzystuje. Ponadto, ponieważ podczas wykonania programu mogą być potrzebne operacje, które nie są realizowane bezpośrednio przez sprzęt (np. zarządzanie pamięcią), wygenerowany kod jest uzupełniany o tzw. system czasu wykonania (ang. run-time system), który można traktować jako rozszerzenie maszyny docelowej.

Często stosowanym rozwiązaniem jest też tworzenie maszyny docelowej od podstaw, z myślą o realizacji konkretnego języka. Instrukcje tej maszyny zwykle nie są bezpośrednio rozumiane przez sprzęt, więc nazywamy ją maszyną wirtualną (abstrakcyjną). Kod wygenerowany na maszynę wirtualną może być wykonywany przez interpreter lub przekazany na wejście kolejnego kompilatora, który przetłumaczy go na kod maszyny rzeczywistej. Spotyka się też rozwiązania pośrednie - połączenie interpretera i kompilatora uruchamianego podczas wykonania programu, by przetłumaczyć fragmenty szczególnie istotne dla jego efektywności. Technika ta nosi nazwę JIT (ang. just-in-time compilation).

Zaprojektowanie uniwersalnej maszyny wirtualnej, mimo wielu prób, jak dotąd nie udało się. Te, które powstają, są przeznaczone dla realizacji określonego języka lub rodziny podobnych języków, np. maszyny wirtualne Javy, Smalltalka, Prologu. Maszynę stworzoną w latach 70 dla realizacji języka Pascal nazywano p-code i określenie to bywa do dziś używane jako synonim języka maszyny wirtualnej. W p-code i maszynach do niej podobnych większość instrukcji pobiera argumenty ze stosu i tam odkłada wynik. Maszyny te nazywamy maszynami stosowymi (ang. stack machine) w odróżnieniu od maszyn wykorzystujących do tego celu rejestry (ang. register machine).

Stosowanie maszyn wirtualnych

Głównym powodem stosowania maszyn wirtualnych w realizacjach języków programowania jest uproszczenie kompilatora. Znacznie łatwiej napisać generator kodu na zaprojektowaną przez nas maszynę, niż generator kodu maszynowego rzeczywistego procesora. Szczególnie dobrze widać to na przykładzie procesorów x86, których nieregularna lista instrukcji i trybów adresowania połączona z bardzo małą liczbą dostępnych rejestrów sprawia wiele problemów autorom generatorów kodu.

Oprócz względnej łatwości implementacji generatora kodu, zastosowanie maszyny wirtualnej w realizacji języka programowania ma i inne zalety - ułatwia przenoszenie kompilatora, a nawet wygenerowanego przez niego kodu, na inne systemy, ułatwia też kontrolowanie programu podczas jego wykonania.

Maszyn wirtualnych zwykle nie stosuje się w realizacji języka programowania, gdy bardzo zależy nam na efektywności kodu wynikowego. Choć istnieją techniki efektywnej realizacji maszyny wirtualnej, jak np. wspomniana wyżej JIT, autorzy kompilatorów sięgaja raczej po klasyczny model kompilacji, w którym generuje się kod pośredni, który następnie podlega optymalizacji.

Przykład prostej maszyny wirtualnej

Najprostszym modelem maszyny wirtualnej dla realizacji języków proceduralnych jest maszyna stosowa. W przykładach w dalszej części tekstu będziemy się posługiwali maszyną wirtualną, którą nazwiemy Naszą Maszyną Wirtualną (w skrócie NMW). Poniżej przedstawiamy jej definicję.

Pamięć NMW składa się ze słów, z których każde mieści liczbę całkowitą lub adres. Adresy kolejnych słów w pamięci różnią się o 1.

W pamięci znajduje się stos, który rośnie w kierunku malejących adresów. W chwili rozpoczęcia wykonania programu stos jest pusty.

Dwa słowa w pamięci, których adresy będziemy oznaczali symbolicznie SP i FP, mają specjalne znaczenie. W komórce o adresie SP jest zapisany wskaźnik czubka stosu, będący adresem wartości znajdującej się aktualnie na czubku stosu. Zawartość tej komórki jest automatycznie modyfikowana przez instrukcje maszyny. Komórką pamięci o adresie FP będziemy się posługiwali podczas realizacji mechanizmu wywołania i powrotu z funkcji/procedury.

Oto instrukcje rozpoznawane przez NMW:

• CONST stała - odkłada na stos wartość stałej przekazanej jako argument

• LOAD - odkłada na stos wartość pobraną spod adresu zdjętego z czubka stosu

• STORE - zdejmuje ze stosu adres, następnie zdejmuje ze stosu wartość i wkłada ją pod ten adres

• ADD - dodawanie, zdejmuje ze stosu najpierw prawy a następnie lewy argument i odkłada na stos ich sumę

• SUB - jak wyżej, ale liczy różnicę

• MUL - jak wyżej, ale liczy iloczyn

• DIV - jak wyżej, ale liczy iloraz

• DUP - odkłada na stos wartość znajdującą się na czubku stosu

• DROP - usuwa wartość z czubka stosu

• SWAP - zamienia kolejość dwóch wartości na czubku stosu

• GOTO - zdejmuje ze stosu adres i skacze do instrukcji znajdującej się pod tym adresem

• CALL - zdejmuje ze stosu adres i skacze do instrukcji znajdującej się pod tym adresem, na stos odkłada adres następnej instrukcji za instrukcją CALL

• IFZERO - zdejmuje ze stosu adres a następnie wartość i skacze pod ten adres, jeśli wartość była równa 0

• IFNOTZERO - zdejmuje ze stosu adres a następnie wartość i skacze pod ten adres, jeśli wartość była różna od 0

• IFMINUS - zdejmuje ze stosu adres a następnie wartość i skacze pod ten adres, jeśli wartość była ujemna

• IFNOTMINUS - zdejmuje ze stosu adres a następnie wartość i skacze pod ten adres, jeśli wartość była nieujemna

• READ - wczytuje z wejścia liczbę całkowitą i wkłada jej wartość na stos

• WRITE - zdejmuje wartość z czubka stosu i wypisuje ją na wyjście

• STOP - zatrzymuje pracę maszyny

W dalszej części tego tekstu, zapisując kod będziemy pomijali słowo CONST w instrukcji odkładającej na stos stałą.

Realizacja wyrażeń

Maszyna stosowa może wykonywać operacje arytmetyczne wyłącznie na wartościach znajdujących się na stosie. Jedynym sensownym sposobem realizacji wyrażeń arytmetycznych jest więc obliczenie obu argumentów (wyniki będą na stosie) a następnie wykonanie na nich operacji, np. „W1+W2” tłumaczymy jako:

[W1]
[W2]
ADD 

Kosztem, jaki płacimy za łatwość generacji kodu dla wyrażeń na maszynę stosową jest nieefektywność kodu. Maszyny rzeczywiste mają zwykle możliwość operowania na wartościach w rejestrach lub pod wskazanymi adresami w pamięci. Na maszynie stosowej z tego nie korzystamy.

Realizacja przypisania

Kod dla przypisania, gdy po lewej stronie jest zwykła zmienna, składa się z instrukcji liczących wartość wyrażenia z prawej strony i z instrukcji STORE zdejmującej wynik na zmienną, np. „x:=E” tłumaczymy na:

[E]
adres_x
STORE

Jeśli język pozwala na złożona postać lewej strony przypisania (elementy tablicy, rekordu itp.), traktujemy ją jak wyrażenie, którego wartość (tzw. l-wartość) określa lokację w pamięci, w którą wpisujemy wartość prawej strony (r-wartość).

Realizacja instrukcji warunkowych i pętli

Pętlę „repeat L until E” możemy tłumaczyć na:

pocz:
[L]
[E]
pocz IFZERO

a dla instrukcji warunkowej „if E then I1 else I2” naturalnym sposobem realizacji jest:

[E]
po_else IFZERO
[I1]
koniec GOTO
po_else:
[I2]
koniec:

Są jednak przypadki, w których dla instrukcji można podać kilka sposobów realizacji, z których każdy jest sensowny. Np. dla pętli „while E do I” mamy trzy różne tłumaczenia:

pocz:
[E]
koniec IFZERO
[I]
pocz GOTO
koniec:

start GOTO
pocz:
[I]
start:
[E]
pocz IFNOTZERO

[E]
koniec IFZERO
pocz:
[I]
[E]
pocz IFNOTZERO
koniec:

Pierwszy wariant jest efektywny, jeśli często warunek pętli jest od razu fałszywy a wariant drugi, jeśli do treści pętli zwykle wchodzi się przynajmniej raz. Wariant trzeci łączy oba rozwiązania, ale daje dłuższy kod (wyrażenie występuje dwa razy), co może spowodować, że będzie działał wolniej.