Zadanie 1 (20p) Zaimplementuj język funkcyjny
z typami (izo-)rekurencyjnymi, zawierający ponadto:
- wyrażenia arytmetyczne i logiczne,
- rachunek lambda,
- krotki,
- warianty,
- rekursję.
Uwagi:
- Wystarczy napisać system sprawdzania
poprawności typu oraz interpreter, a także
przygotować testy wyrażeń wykorzystujących typy
rekurencyjne (takich jak reprezentacja beztypowego
rachunku lambda).
- Zakładamy semantykę operacyjną z przekazywaniem
argumentów przez wartość.
|
Zadanie 2 (dla chętnych, 20p) Rozszerz
rozwiązanie Zadania 1 o możliwość definiowania
(monomorficznych) rekurencyjnych typów danych znanych
z takich języków jak Haskell czy ML.
Uwagi:
- Każdy taki typ danych może być potraktowany
jako cukier syntaktyczny dla pewnego rekurencyjnie
zdefiniowanego wariantu.
- Wyrażenia fold[T] i unfold[T]
ustalające izomorfizm typu rekurencyjnego T
i jego rozwinięcia powinny być ukryte
(tj. niejawnie dopisane) w konstruktorach
wariantów oraz w wyrażeniu dopasowania wzorca.
|
Zadanie 3 (20p) Zaimplementuj algorytm
rekonstrukcji typu, wyznaczający najbardziej ogólny
typ wyrażenia przy danym kontekście typowania, dla
języka funkcyjnego zawierającego:
- wyrażenia arytmetyczne i logiczne,
- rachunek lambda (bez anotacji typowych),
- pary,
- sumy (bez anotacji typowych),
- rekursję (bez anotacji typowych).
Zauważ, że zamiast generowania wszystkich więzów
najpierw, a następnie rozwiązywania ich, można budować
najbardziej ogólny typ termu inkrementacyjnie,
wyznaczając najbardziej ogólne typy jego podtermów i
rozwiązując powstające na bieżąco więzy.
|
|