Zadanie na 15.12.2007 (dla chetnych) Interpreter i maszyna abstrakcyjna dla jezyka Mini-Scheme Zaimplementuj interpreter, a nastepnie przetransformuj go do semantycznie rownowaznej mu maszyny abstrakcyjnej dla jezyka, ktory nazwiemy Mini-Scheme. Mini-Scheme jest beztypowym jezykiem funkcyjnym z aplikatywna (CBV) strategia ewaluacji, rozszerzonym o kontynuacje pierwszej klasy oraz modyfikowalny stan. Minimalny zestaw konstrukcji, ktore jezyk powinien zawierac jest nastepujacy: stale numeryczne (calkowite) i podstawowe operacje arytmetyczne stale logiczne i operacje logiczne listy (pary?) i operacje do ich konstrukcji i destrukcji wyrazenie warunkowe if zmienne, funkcje anonimowe i aplikacje jednego wyrazenia do drugiego wyrazenie let -- definicje lokalne wyrazenie letrec -- rekursywne definicje lokalne, najlepiej umozliwiajace rekursje wzajemna definicje funkcji, w tym rekursywnych, najlepiej wspierajace rekursje wzajemna operator call/cc operator error (abort) wyrazenie modyfikujace wartosc zmiennej (:= w MLu lub set! w Schemie) Interpreter powinien korzystac ze srodowiska i sterty (heap) do implementacji zwiazania zmiennych z wartosciami przy zachowaniu mozliwosci imperatywnej zmiany ich wartosci oraz z kontynuacji do zaimplementowania operatorow kontroli. Mozliwe rozszerzenia: Wzbogacenie jezyka o operatory shift i reset dla kontynuacji ograniczonych. Tu trzeba sie zastanowic nad semantyka operatorow call/cc i abort, jesli chce sie je utrzymac w jezyku. Wzbogacenie maszyny abstrakcyjnej o prosty Garbage Collector. Wzbogacenie jezyka o wyjatki, przy czym powinno byc to latwiejsze na poziomie maszyny abstrakcyjnej. Tu trzeba sie zastanowic nad wspolpraca mechanizmu obslugi wyjatkow z operatorami kontroli. Parser dla jezyka Mini-Scheme. Skladnia konkretna nie musi przypominac tej z Lispa :). Prosty system typow, czyli przejscie w kierunku MiniML-a. Po zaimplementowaniu rekonstrukcji typow monomorficznych, mozna sprobowac wprowadzic let-polimorfizm do jezyka. Ksiazka Felleisena i Flatta powinna byc pomocna w rozwiazaniu powyzszego zadania i w zaimplementowaniu wiekszosci z proponowanych rozszerzen na poziomie maszyny abstrakcyjnej. Prosze jednak nie nasladowac jej bez namyslu, bo nie wszystkie proponowane tam rozwiazania sa tak eleganckie jak moglyby byc, a poza tym interesujacym pytaniem jest czy odpowiadajace im rozwiazania mozna wprowadzic na poziomie interpretera, tak by funkcyjna odpowiedniosc miedzy nim a maszyna abstrakcyjnej byla zachowana.