Ćwiczenia 7: Moduły

[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.