Zadania na 12.12.2007 Zadanie 1 Napisz naiwna funkcje obliczajaca n-ty wyraz ciagu Fibonacciego w stylu kontynuacyjnym. Nastepnie zdefunkcjonalizuj kontynuacje w swoim rozwiazaniu. Zadanie 2 Napisz funkcje w stylu kontynuacyjnym wyznaczajaca iloczyn etykiet (liczb calkowitych) w drzewie binarnym, ze specjalnym uwzglednieniem przypadku, gdy w drzewie znajduje sie 0. Nastepnie: (1) przeksztalc ja do zwyklego stylu z uzyciem operatora call/cc, (2) zdefunkcjonalizuj kontynuacje w swoim rozwiazaniu. Zadanie 3 Napisz bezposrednio lub wyprowadz przy pomocy refunkcjonalizacji i transformacji ze stylu kontynuacyjnego funkcje, ktora sprawdza czy dana lista jest palindromem, uzywajac n/2 wywolan rekurencyjnych, gdzie n jest nieznana dlugoscia listy. Zadanie 4 Zapisz funkcje backtrack z wykladu w stylu kontynuacyjnym. Pamietaj, ze w tym stylu wszystkie funkcje (poza trywialnymi) przyjmuja kontynuacje jako dodatkowy argument. Na przyklad, wywolaniu backtrack (fn amb => if (amb()) then 1 else 2) bedzie teraz odpowiadalo wywolanie backtrack (fn amb => fn k => amb (fn b => if b then k 1 else k 2)) (fn x => x). Zadanie 5 Rozszerz definicje funkcji backtrack z wykladu o mozliwosc zglaszania porazek w czasie obliczen z nawrotami. Zgloszenie porazki, realizowane przez wywolanie bezparametrowej funkcji fail, powinno spowodowac wycofanie sie z biezacej galezi obliczen do najblizszego rozgalezienia, w ktorym jakas galaz nie byla jeszcze probowana. Na przyklad, wyrazenie backtrack (fn amb => fn fail => if amb() then if amb() then 1 else fail() else if amb() then 3 else 4) powinno miec wartosc [4,3,1]. Wykorzystaj swoja funkcje backtrack do napisania funkcji bitseq, ktora dla danych liczb naturalnych n oraz s, znajdzie wszystkie ciagi zero-jedynkowe, ktorych dlugosc wynosi n, a suma (tj. liczba jedynek) s. Zadanie 6 Wykorzystaj podany na wykladzie mechanizm tworzenia i uzywania wspolprogramow do rozwiazania problemu tej samej korony (same-fringe problem). Dwa drzewa maja taka sama korone, jesli etykiety w ich lisciach czytane od lewej do prawej tworza jednakowe ciagi. Np. Zadanie 7 Uzywajac operatora call/cc oraz kolejki, zaproponuj prosta implementacje (anonimowych) procesow wspolbieznych. Uruchomiony proces moze dobrowolnie oddac sterowanie do systemu. Wowczas zostaje on wstawiony na koniec kolejki procesow, a uruchomiany lub wznowiony zostaje pierwszy proces z kolejki. Przetestuj swoje rozwiazanie na grupie procesow, ktore wspolpracuja, zeby wypisywac na wyjscie jakis konkretny napis.