Informatyka MIMUW

[D.L.Parnas, On the Criteria To Be Used in Decomposing Systems into Modules, CACM 12 (15), 1972]
Rozważmy następujący problem. Należy napisać program, który:

• wczyta plik tekstowy,
• dany plik składa się z wierszy, a każdy wiersz ze słów oddzielonych białymi znakami,
• rozważamy rotacje cykliczne wierszy, powstałe przez przestawienie pewnej liczby słów z początku wiersza na koniec,
• program ma wypisać wszystkie możliwe rotacje cykliczne wierszy z wejścia, bez powtórzeń,
  w porządku leksykograficznym, oddzielając słowa w wierszach pojedynczymi odstępami.

Podaj jak byś podzielił program na moduły.
Wymyśl zestaw realistycznych modyfikacji, jakie należy wprowadzić (a jeszcze lepiej poproś o to kolegę) i sprawdź, jak sprawuje się wymyślony przez Ciebie podział na moduły.

Zdefiniuj sygnatury/struktury odpowiadające podanym poniżej pojęciom.
Staraj się wykorzystać zdefiniowane wcześniej pojęcia.

1. Sygnatura półgrupy (typ elementów i operacja łączna).
2. Sygnatura monoidu (półgrupa z elementem neutralnym).
   Struktura monoidu:
   • liczby całkowite z dodawaniem,
   • funkcje (na liczbach całkowitych) z operacją składania,
   • listy (liczb całkowitych) z operacją sklejania,
   • macierzy \(2 \times 2\) z operacją mnożenia.
3. Sygnatura grupy (monoid z elementami odwrotnymi).
4. Sygnatura pierścienia (dodawanie, mnożenie, jedynka, zero, elementy przeciwne).
5. Struktura pierścienia liczb całkowitych.
6. Sygnatura ciała (pierścień z elementami odwrotnymi).
7. Struktura ciała liczb rzeczywistych.
8. Sygnatura porządku częściowego z operacjami sup i inf.
9. Struktura implementująca porządek częściowy par liczb całkowitych z operacjami sup i inf.
   Przyjmujemy, że \((x_1, y_1) \le (x_2, y_2)\) gdy \(x_1 \le x_2\) oraz \(y_1 \le y_2\).
10. Zdefiniuj moduł implementujący przechadzkę -- "kursor" do przechadzania się po drzewach i oglądania go:

     
          sig 
            type α tree = 
              Node of α tree * α  *  α tree |
              Null
            type α walk
            make     : α tree  → α walk
            goleft   : α walk → α walk
            goright  : α walk → α walk
            goup     : α walk → α walk
            lookup   : α walk → α tree
            exception OutsideTree
          end
     

    Wywołanie make d powinno konstruować przechadzkę, w której znajdujemy się w korzeniu drzewa d.
    Wywołanie goleft p powinno konstruować przechadzkę powstałą przez przejście do lewego poddrzewa.
    Analogicznie powinny działać procedury goright i goup.
    Procedura lookup powinna zwrócić poddrzewo zaczepione w wierzchołku drzewa, w którym aktualnie jesteśmy.

    Podczas przechadzki po drzewie możemy przebywać jedynie w wierzchołkach Node _.
    Jeśli nastąpi próba wejścia do Null'a lub wyjścia ,,ponad'' korzeń, należy podnieść wyjątek OutsideTree.