Celem pracowni jest zaznajomienie studentów z działaniem języków programowania od środka. Ostatecznym celem będzie napisanie kompilatora wysoko-poziomowego, ale prostego języka programowania, generującego kod działający na platformie .NET.
Plan działania jest następujący (w ogólnym zarysie):
Część uczymy się odbywa się w czwartek od 18 do 20. Część implementujemy odbywa się raczej w domu.
Szczęśliwie napisanie kompilatora nie będzie warunkiem koniecznym zaliczenia, będzie to natomiast warunek konieczny zaliczenia na ocenę bdb. Wbrew pozorom jest to zadanie wykonalne dla większości studentów.
Ocena dst będzie gdzieś w okolicy pretty-printera.
Zmiany: pretty-printera i syntax-checkera nie będzie, zamiast nich będzie interpreter.
Programy (z wyj. tych pierwszych) mogą być napisane w dowolnym języku programowania pod warunkiem, że będą działać pod Linuxem. Generowany kod (lub źródła pierwszych programów) ma działać w środowisku mono pod Linuxem.
Linux/mono:
# assemblacja ilasm foobar.il # weryfikacja pedump --verify all foobar.exe # uruchomienie mono foobar.exe # kompilacja programu w C# mcs barqux.cs # uruchomienie mono barqux.exe # disassemblacja monodis barqux.exe
Windows/MS.NET
# assemblacja ilasm foobar.il # weryfikacja PEVerify foobar.exe # uruchomienie foobar # kompilacja programu w C# csc barqux.cs # uruchomienie barqux # disassemblacja ildasm /text barqux.exe
Zadania mają być rozwiązane w IL-u "ręcznie" i samodzielnie. Disassemblacja ma służyć tylko celom edukacyjnym. Nadużycia będą ścigane.
dlaczego środowisko zarządzane? to przyszłość łatwiej dlaczego .NET - wielojęzykowość 1.1 słabo, tylko: tail calle, brak limitów na rozmiary metod itd, unsafe code, metadane, value types 2.0 lepiej - gernicsy, szybkie delegaty 3.0 kto to wie... podobno języki dynamiczne dlaczego .NET - OSS CLR model stosowy maszyny brak rejestrów, zmienne lokalne, nie tracimy struktury wyrażeń języka źródłowego dostępne typy: i4, i8, r4, r8, o, value types model obiektowy odśmiecaniePrzykład:
.assembly extern mscorlib { }
.assembly zad1 { }
.module zad1.exe
.method public static bool divides (int32 a, int32 b) cil managed
{
.maxstack 20
ldarg a
ldarg b
rem
// a%b
ldc.i4 0
ceq
// a%b == 0
ret
}
.method public static default void main () cil managed
{
.entrypoint
.maxstack 20
.locals init (int32 n,
int32 divisors,
int32 i)
call string class [mscorlib]System.Console::ReadLine()
call int32 int32::Parse(string)
stloc n
ldc.i4 0
stloc divisors
ldc.i4 2
stloc i
cond:
ldloc i
ldloc n
// if i < n goto loop
blt loop
// else goto end
br end
loop:
ldloc n
ldloc i
call bool divides(int32, int32)
// if !divides(n,i) goto skip_add
brfalse skip_add
ldloc divisors
ldc.i4 1
add
stloc divisors
skip_add:
ldloc i
ldc.i4 1
add
stloc i
br cond
end:
ldloc divisors
call void class [mscorlib]System.Console::WriteLine(int32)
ret
}
Wysyłanie zadań: zadania proszę wysyłać przez WWW. Hasło brzmi "programowanie". Ci którzy już wysłali, nie muszą wysyłać ponownie. Programy nie powinny czytać ani pisać niczego, oprócz tego co jest napisane w treści (będą testowane automatycznie).
Termin: 9 marca 2003.
Update: Sun Mar 12 16:48:53 CET 2006
Dzisiejsze szczęśliwe numerki to: 151054, 151057, 151057, 151059, 151061, 159093, 159100, 159184, 159191, 169825, 169842, 169848, 170666, 170668, 170671, 170673, 170674, 170691, 170697, 175577, 175596, 186755, 186756, 186757, 186761, 186764, 186767, 186769, 186770, 186772, 186773, 186776, 186777, 186779, 186780, 186785, 186788, 186790, 186793, 186794, 186797, 186799, 186803, 186807, 186812, 186816, 186820, 186824, 186827, 186835, 186837, 186839, 186841, 186842, 186844, 186846, 186850, 186851, 186855, 186861, 186863, 186865, 186866, 186901, 186902, 186910, 186914, 186916.
186818 oraz 102686 przysłali po dwóch poprawnych i jednym nie-do-końca-poprawnym zadaniu, w związku z czym mogą się spodziewać utraty około 16.66% punktów.
Pliki:
W liniach poprzedzonych ## znajduje się porawne wyjście danego testu. Jeśli po ## występuje napis ERROR oznacza to, że dany test powinien spowodować błąd. W takich testach występują dodatkowo dwie linie zaczynające się od # typing-error: która opisuje błąd typowania w danym teście (który jest nieistotny w przypadku interpretera), oraz # interp-error:, która opisuje błąd wykonania. Jeśli linia # interp-error: jest pusta, to dany błąd jest tylko błędem typowania i efekty działania interpretera na tym kodzie są nie zdefiniowane.
Wasze interpretery będą oceniane na tym właśnie zestawie testów (+ kilka dodatkowych, niezbyt różniących się od tych). Testy będą jednak pozbawione informacji o spodziewanym wyjściu/błędzie.
Wasz interpreter powinien wyjść ze statusem różnym od zera, jeśli napotka błąd lub zero w przeciwnym wypadku. Jeśli wychodzi z zerem, nie powinien wyświetlać innych komunikatów, oprócz wyjścia programu. Jeśli wychodzi z błędem, może (a nawet jest to mile widziane) podać jego opis, aczkolwiek nie będzie to wymagane. W szczególności opis może być inny niż podany w teście.
Interpreter będzie uruchamiany bez argumentów, z testem przekierowanym na standardowe wejście.
Programy będą oceniane automatycznie.
Interpreter może być napisany w dowolnym języku pod warunkiem, że uda się go łatwo uruchomić na pod systemem Linux, architektura i386. W razie wątpliwości proszę kontaktować się mailowo.
W najbliższy czwartek (16 marca) odbędą się konsultacje ogólne, w trakcie których odpowiem na pytania. W związku z tym można zgłaszać pytania mailowo do mnie lub też zapytać po prostu w trakcie wykładu.
Zgodnie z zapowiedzią umieszczam.
Jeśli zauważycie, że tu jest napisane co innego niż w testach, to testy mają rację.
Środowisko (Context) jest trawałe, tzn. raz zrobionego środowiska się nie zmienia, można tylko na jego podstawie zrobić nowe. Zapis tej operacji to: ctx[x = e], co oznacza nowe środowisko, równe ctx wszędzie z wyjątkiem pola x, gdzie ma wartość e.
Środowisko można zorganizować jako listę, i zawsze tylko dodawać do niej elementy od przodu, a nigdy nie zmieniać wskaźników w środku. Lepiej jako trwała drzewo czerowo-czarne czy inne, ale nie jest to konieczne.
Obiekty nie są trawałe, tzn. można zmieniać ich pola. Podobnie komórki (Cell) pamięci, którym można zmieniać pole val.
Operatory logiczne zwracają 0 lub 1.
Value is either
Number
String
Object
Null
LambdaValue
struct Cell {
val : Value
}
new_cell (v : Value) : Cell
let c = allocate Cell
c.val := v
return c
eval_stmt (ctx : Context, stmt : Stmt) : Context
case stmt of
| "var" n "=" e =>
let v = eval_expr (ctx, e)
return ctx[n := new_cell (v)]
| "print" e =>
let v = eval_expr (ctx, e)
write_line (v)
return ctx
| "{" stmts "}" =>
let lctx = ctx
foreach (s in stmts)
lctx := eval_expr (lctx, s)
return ctx
| n "=" e =>
if (ctx contains n)
let c = ctx[n]
c.val := eval_expr (ctx, e)
return ctx
else error!
| e1 "." f "=" e2 =>
let v1 = eval_expr (ctx, e1)
if (v1 is Object (o))
let v2 = eval_expr (ctx, e2)
o[f] := v2
return ctx
else error!
| e1 "=" e2 => error!
| "skip" =>
return ctx
| "if" "(" e1 ")" s1 "else" s2 =>
let v = eval_expr (ctx, e)
if (v == 0)
return eval_stmt (ctx, s2)
else if (v is number)
return eval_stmt (ctx, s1)
else error!
| "while" "(" e1 ")" s =>
let v = eval_expr (ctx, e)
if (v == Number (0))
return ctx
else if (v is Number)
let dummy = eval_stmt (ctx, s)
return eval_stmt (ctx, stmt)
else error!
| "fun" n ( n1, ..., nK ) s =>
let c = new_cell (Null)
let lctx = ctx[n := c]
c.val := LambdaValue (lctx, [n1, ..., nK], s)
return lctx
eval_expr (ctx : Context, expr : Expr) : Value
case expr of
| e1 OPERATOR e2 =>
let v1 = eval_expr (ctx, e1)
let v2 = eval_expr (ctx, e2)
if (v1 is Number (k1) and v2 is Number (k2))
return Number (k1 OPERATOR k2)
else error!
| "is_null" e1 =>
let v = eval_expr (e1)
if (v is Object (_))
return Number (1)
else if (v is Null)
return Number (0)
else error!
| "new" =>
let o = allocate object
return Object (o)
| "null" =>
return Null
| INT => return Number (INT)
| STRING => return String (STRING)
| n => // identifier
if (ctx contains n)
return ctx[n].val
else error!
| e1 "." f =>
let v = eval_expr (ctx, e1)
if (v is Object (o))
return o[f]
else error!
| e0 (e1, ..., eK) =>
let v1 = eval_expr (ctx, e1)
if (v1 is LambdaValue (lctx, [p1, ..., pL], s))
if (K != L) error!
else
let cctx = lctx
for i = 1 ... K do
cctx := cctx[pi := eval_expr (ctx, ei)]
done
let res = new_call (Null)
cctx := cctx["value" := res]
let dummy = eval_stmt (cctx, s)
return res.val
else error!
Opiszemy system typów Żółwia i być może schemat translacji na IL-a.
Notacje:
[f(x) | x in lista] oznacza aplikację funkcji f do wszystkich elementów
listy i zwraca listę wyników.
Przykładowo [x + 7 | x in [1, 3, 10]] = [8, 10, 17].
[] oznacza pustą listę.
Length(lista) oznacza długość listy.
typ SUBST [v1 := t1, ..., vN = tN] ma zwrócić nowy typ (nie ruszać
tego przekazanego), w którym za zmienną v1 podstawiono t1 itd.
Konstrukcja foreach (e in lista) oznacza pętlę przechodzącą po wszystkich
elementach listy.
1. sprawdzamy czy nazwy struktur i pól w nich są unikalne (jak nie to błąd)
2. zapmiętujemy sobie żółwiowe struktury w jakis
drzewach/hashtablicach/czy na listach, tak, żeby jeśli mamy strukturę:
"struct" name "[" var_1 "," ... "," var_N "]" "{"
field_1 ":" type_1 ";"
field_2 ":" type_2 ";"
...
field_K ":" type_K ";"
"}"
to funkcje tyargs() oraz field() mają się zachowywać następująco:
tyargs(name) = [var_1, ..., var_N]
bare_field(name, field_M) = type_M
oraz, żeby dla niezdefiniowanych nazw i pól zwracały NULL.
3. definujemy:
field(name, field_M) = bind_type(tyargs(name), bare_field(name, field_M))
i próbujemy wywołać field() dla każdej struktury i pola (tak, żeby
od razu odkryć błędy w typach w strukturach)
Type is either
| Int
| String
| Fun (list[Type], Type)
| TyVar (string)
| TyCon (string, list[Type])
LocalValue is either
| SimpleName (Type)
| NamedFunction (list[string], Type)
type_stmt(vars, names, stmt) : list[string] * map[string,LocalValue]
env = (vars, names)
case stmt of
| "skip" =>
return env
| "print" expr =>
case type_expr (env, expr) of
| Int
| String => return env
| _ => error!
end
| "var" name "=" expr =>
t = type_expr(env, expr)
return (vars, names[name := SimpleName (t)])
| "{" stmts "}" =>
inenv := env
foreach (s in stmts)
inenv := type_stmt (inenv, s)
return env
| expr1 "." fld "=" expr2 =>
case type_expr(env, expr1) of
| TyCon (name, types) =>
if (field (name, fld) == NULL) error!
else
[var_1, ..., var_N] = tyargs(name)
if (N == M)
t1 = field (name, fld) SUBST [var_1 := t_1, ... var_N := t_N]
t2 = type_expr (env, expr2)
if (t1 == t2)
return env
else error!
else error! // to nie powinno się zdarzyć!
| _ => error!
end
| name = expr =>
case env.names(name) of
| SimpleName (t1) =>
t2 = type_expr(env, expr)
if (t1 == t2) return env
else error!
| NamedFunction (_, _) =>
error! // nie można podstawić pod funkcję
end
| "if" "(" expr ")" stmt1 "else" stmt2 =>
if (type_expr(env, expr) != Int) error!
else
dummy1 = type_stmt(env, stmt1)
dummy2 = type_stmt(env, stmt2)
return env
| "while" "(" expr ")" stmt
if (type_expr(env, expr) != Int) error!
else
dummy = type_stmt(env, stmt)
return env
| "fun" name "[" var_1, ..., var_N "]"
"(" parm_1 : tparm_1, ..., parm_K : tparm_K ")" ":" ret_type stmt =>
vars' = env.vars + [var_1, ..., var_N]
fun_type = Fun ([bind_type (vars', tparm_1), ..., bind_type (vars', tparm_K)],
bind_type (vars', ret_type))
names' = env.names [name := NamedFunction ([], fun_type),
parm_1 := SimpleName (bind_type (vars', tparm_1)),
...,
parm_K := SimpleName (bind_type (vars', tparm_K)),
"value" := SimpleName (bind_type (vars', ret_type))]
dummy = type_stmt ((vars', names'), stmt)
return (vars, names[name := NamedFunction ([var_1, ..., var_N], fun_type)])
type_expr(vars, names, expr) : Type
env = (vars, names)
case expr of
| INT => return Int
| STRING => return String
| "is_null" "(" expr ")" =>
case type_expr(env, expr) of
| TyCon (_, _) => return Int
| _ => error!
end
| name "[" type_1, ..., type_N "]" =>
case names(name) of
| SimpleName (type) =>
if (N == 0) return type
else error!
| NamedFunction ([var_1, ..., var_M], type) =>
if (N == M)
return type SUBST [var_1 := bind_type (vars, type_1),
...,
var_N := bind_type (vars, type_N)]
else error!
end
| expr "(" exprs ")" =>
case type_expr(env, expr) of
| Fun (types, ret_type) =>
expr_types = [type_expr (env, e) | e in exprs]
if (exprs_types == types) // porownujemy dlugosc i zawartosc list
return ret_type
else error!
| _ => error!
end
| expr "." fld =>
case type_expr(env, expr) of
| TyCon (name, [t_1, ... t_M]) =>
if (field (name, fld) == NULL) error!
else
[var_1, ..., var_N] = tyargs(name)
if (N == M)
return field (name, fld) SUBST [var_1 := t_1, ... var_N := t_N]
else error! // to nie powinno się zdażyć!
| _ => error!
end
| "new" name "[" types "]"
| "null" name "[" types "]" =>
if (tyargs(name) == NULL || Length(types) != Length(tyargs(name)))
error!
else return TyCon (name, [bind_type(vars, t) | t in types])
| expr1 "+" expr2
| expr1 "-" expr2
| expr1 "*" expr2
| expr1 "/" expr2
| expr1 "%" expr2
| expr1 "<" expr2
| expr1 ">" expr2
| expr1 "<=" expr2
| expr1 ">=" expr2
| expr1 "==" expr2
| expr1 "!=" expr2 =>
case (type_expr(env, expr1), type_expr(env, expr2)) of
| (Int, Int) =>
return Int
| _ => error!
end
bind_type(vars, type)
case type of
| "int" => Int
| "string" => String
| "(" types ")" "->" ret_type =>
Fun ([bind_type (vars, t) | t in types], bind_type (vars, ret_type))
| name =>
if (tyargs(name) == []) // name jest typem bez argumentow
TyCon (name, [])
else if (name jest na liście vars)
TyVar (name)
else error!
| name "[" types "]" =>
if (tyargs(name) == NULL || Length(tyargs(name)) != Length(types))
error!
else
TyCon (name, [bind_type (vars, t) | t in types])
Interpreter będzie testowany pod Linuxem. Należy go wysłać jako archiwum tar.gz. Archiwum ma zawierać plik compile.sh z poleceniami służącymi do kompilacji. Plik wynikowy ma się nazywać zolw lub zolw.exe (w wypadku .NET-u). Najlepiej w archiwum od razu zamieścić wygenerowane antlrem pliki, ale koniecznie należy również zamieścić pliki *.g.
Przykładowy plik compile.sh:
gmcs Parser.cs Lexer.cs Main.cs -out:zolw.exe -r:antlr.runtime.dll
Inny przykład:
g++ -c Parser.cpp Lexer.cpp Main.cpp g++ Parser.o Lexer.o Main.o -o zolw
Jeszcze inny:
make
Program ma się skompilować po wykonaniu polecenia: sh compile.sh
Wersje oprogramowania: mono 1.1.10 (w nowszych są problemy z antlr!), java 1.5, gcc 3.4.
Wasz interpreter powinien wyjść ze statusem różnym od zera, jeśli napotka błąd lub zero w przeciwnym wypadku. Jeśli wychodzi z zerem, nie powinien wyświetlać innych komunikatów, oprócz wyjścia programu. Jeśli wychodzi z błędem, może (a nawet jest to mile widziane) podać jego opis, aczkolwiek nie będzie to wymagane. W szczególności opis może być inny niż podany w teście.
Interpreter będzie uruchamiany bez argumentów, z testem przekierowanym na standardowe wejście.
Programy będą oceniane automatycznie.
Archiwum należy wysłać przez interface www. Hasło brzmi "programowanie". Jeśli ktoś wysłał zadanie przed 21 kwietnia to nie musi tego robić ponownie.
Dla ułatwienia zamieszczam program testujący. Jest napisany w perlu. Po uruchomieniu (perl zolwtest) wypisuje komunikat z instrukcją obsługi.
Zasady oceniania: 1 pkt za każdy test (testow jest ok. 45), dodatkowo 10 pkt za przejście wszystkich testów, dodatkowo 5 pkt za terminowe oddanie (oddać można jeszcze do następnego poniedziałku i nie dostać tych 5 punktów). Za stare zadania z IL-a można dostać 12 punktów.
Próg zaliczenia (na 3.0) nie będzie wyższy niż 64 punkty.
