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ą stosową, którą nazwiemy Naszą Maszyną Stosową (w skrócie NMS). Poniżej przedstawiamy jej definicję.

Pamięć NMS 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.

• 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

• 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łą.