Programowanie funkcyjne/Moduły

Wprowadzenie

Każdy duży program powinien być podzielony na mniejsze, łatwiejsze do ogarnięcia składowe, nazywane modułami. Jednocześnie, zależności między tymi składowymi powinny być ograniczone do niezbędnego minimum. Stosując taką strukturalizację łatwiej ogarnąć interesującą nas część systemu, gdyż zwykle jest to jeden lub tylko kilka modułów. Łatwiej też pielęgnować taki program.

Moduł można określić jako fragment systemu polegający na wykonaniu wyodrębnionego zadania programistycznego. Każdy moduł ma ściśle określony interfejs --- zestaw obiektów programistycznych, które realizuje. Jedne moduły mogą korzystać z obiektów zaimplementowanych przez inne. Zwykle sformułowaniu zadania programistycznego towarzyszy (mniej lub bardziej formalna) specyfikacja własności, które powinny posiadać obiekty programistyczne implementowane przez dany moduł.

Moduł ma charakter czarnej skrzynki (ang. black-box approach). Na zewnątrz modułu widoczne są wyłącznie te obiekty programistyczne, które tworzą interfejs. Natomiast sposób ich implementacji, jak i ew. obiekty pomocnicze są ukryte wewnątrz modułu. Specyfikacja modułu nie powinna odwoływać się do sposobu implementacji modułu, a jedynie do takich właściwości modułu, które może zaobserwować użytkownik modułu. Co więcej, użytkownik nie tylko nie ma możliwości, ale i nie powinien (w swym programie) wnikać w sposób implementacji modułu (ang. information hiding).

Takie zasady konstrukcji modułów pozwalają (po podzieleniu systemu na moduły) na niezależne ich opracowywanie. Podobnie, moduły można też niezależnie kompilować. Na poziomie języka programowania, wszystkie informacje konieczne do skompilowania modułu są zawarte w interfejsach wykorzystywanych przez niego modułów.

W Ocamlu możemy osobno definiować interfejsy i implementacje modułów. Interfejsy modułów nazywamy sygnaturami natomiast ich implementacje strukturami. Dodatkowo istnieje pojęcie modułów sparametryzowanych, tzw. funktorów. Są to moduły, które mają określony interfejs, a także korzystają z modułów o określonych interfejsach, ale bez sprecyzowanej implementacji. Dopiero po podaniu implementacji tych brakujących modułów, uzyskujemy moduł wynikowy. Funktory można traktować jak konstrukcje przekształcające moduły w moduły. W wykładzie tym zajmiemy się stukturami i sygnaturami, a funktory omówimy w kolejnym wykładzie.

Proste struktury

Definiując strukturę zbieramy razem definicje pojęć, które ta struktura ma udostępniać, otaczamy je słowami struct ... end i nadajemy modułowi nazwę.

<definicja> ::= module <Identyfikator> = <struktura> 
<struktura> ::= struct { <definicja> }* end      
     

Tak zdefiniowana struktura udostępnia wszystkie pojęcia zdefiniowane wewnątrz --- tzn. ma największy z możliwych interfejsów. Do pojęć zdefiniowanych wewnątrz struktury możemy dostać się stosując tradycyjne kwalifikowanie nazw postaci:

<identyfikator> ::= <Identyfikator> . <identyfikator>

Możemy też "otworzyć" strukturę, tzn. wyłuskać z niej wszystkie udostępniane przez nią pojęcia tak, aby były dostępne bez kwalifikowania nazwą modułu.

<jednostka kompilacji> ::= open <Identyfikator>
     

Przykład [Proste moduły]

module Modulik = 
  struct
    type typik = int list
    let lista : typik = [2; 3; 7]
    let prod (l : typik) = List.fold_left ( * ) 1 l
  end;;
 
Modulik.prod Modulik.lista;;
open Modulik;;
prod lista;;
  
module Pusty = 
  struct
  end;;
 
module Modulik : sig type typik = int list val lista : typik val prod : typik -> int end

Podobnie jak jest to możliwe w niektórych językach programowania (np. Modula 2), moduły mogą zawierać moduły lokalne.

Przykład [Moduły lokalne]

module M = 
  struct
    module A = 
      struct
        let a = 27
      end
    module B = 
      struct
        let b = 15
      end
  end;;
 
M.A.a + M.B.b;;

Moduły lokalne nie występują w wielu językach, gdyż zwykle można się obyć bez nich. Gdy poznamy funktory, to zobaczymy, że moduły lokalne sa szczególnie przydatne, gdy wewnątrz modułu chcemy skorzystać z funktora. Wówczas zarówno argument funktora, jak i jego wynik mogą być modułami lokalnymi.

Sygnatury

Sygnatura, to interfejs modułu --- określa, które elementy struktury mają być dostępne na zewnątrz. Wszystko czego nie widać w sygnaturze jest ukryte przed zewnętrznym użytkownikiem. Domyślnie, jeśli sygnatura modułu nie jest podana, to zawiera ona wszystko co zostało zdefiniowane w module. Sygnatura może zawierać deklaracje:

• wartości, z podaniem typu wartości,
• typu wraz z jego definicją,
• typu abstrakcyjnego (z podaniem nazwy, ale bez podania definicji),
• sygnatury lokalnej (czyli sygnatury modułu lokalnego),
• wyjątków.

<definicja>   ::= module type <Identyfikator> = <sygnatura> 
<sygnatura>   ::= sig { <deklaracja> }* end | ...
<deklaracja>  ::= type { <parametr typowy> }* <identyfikator> [ = <typ> ] |
                  val <identyfikator> : <typ> |
                  module type <Identyfikator> =
                  <sygnatura> | 
                  exception <wariant> | ...
     

Deklaracje, które możemy umieścić w sygnaturze wyglądają analogicznie do definicji zawartych w module, z wyjątkiem deklaracji stałych i procedur. W ich przypadku deklaracja zaczyna się słowem kluczowym val i podany jest jedynie typ wartości.

Uwaga

Zarówno nazwy modułów, jak i sygnatur muszą zaczynać się wielką literą. W dalszej części wykładów będziemy stosować dodatkową konwencję:

nazwy modułów będziemy pisać zgodnie z konwencją węgierską, a nazwy sygnatur będziemy pisać wyłącznie wielkimi literami.

Przykład [Bardzo prosta sygnatura]

module type S = 
  sig
    type abstrakcyjny
    type konkretny = int * float
    val x : abstrakcyjny * konkretny
    module type Pusty = sig end
    exception Wyjatek of abstrakcyjny
  end;;

Przykład [Sygnatura kolejek FIFO]

module type FIFO = 
  sig
    exception EmptyQueue
    type 'a queue
    val empty : 'a queue
    val insert : 'a queue -> 'a -> 'a queue
    val front : 'a queue -> 'a
    val remove : 'a queue -> 'a queue
  end;;

Sygnatury można rozszerzać. Definiując jedną sygnaturę można "wciągnąć" do niej zawartość innej sygnatury. Robimy to za pomocą konstrukcji include. Sygnatura taka zawiera wszystko to, co zawiera "wciągnięta" sygnatura, jak i wszystkie inne deklaracje podane explicite.

<deklaracja> ::= include <Identyfikator>

Przykład [Rozszerzanie sygnatur]

module type QUEUE = 
  sig
    include FIFO 
    val back : 'a queue -> 'a
    val insert_front : 'a queue -> 'a -> 'a queue
    val remove_back : 'a queue -> 'a queue
  end;;
module type QUEUE =
  sig
    exception EmptyQueue
    type 'a queue
    val empty : 'a queue
    val insert : 'a queue -> 'a -> 'a queue
    val front : 'a queue -> 'a
    val remove : 'a queue -> 'a queue
    val back : 'a queue -> 'a
    val insert_front : 'a queue -> 'a -> 'a queue
    val remove_back : 'a queue -> 'a queue
  end

Sygnatury można również ukonkretniać. Ukonkretnienie sygnatury polega na zastąpieniu występującego w niej typu abstrakcyjnego typem konkretnym.

<sygnatura> ::= <sygnatura> with type { <parametr typowy> }* <identyfikator> = <typ> 

Przykład [Ukonkretnianie sygnatur]

module type LIST =  FIFO with type 'a queue = 'a list;;
module type LIST =
  sig
    exception EmptyQueue
    type 'a queue = 'a list
    val empty : 'a queue
    val insert : 'a queue -> 'a -> 'a queue
    val front : 'a queue -> 'a
    val remove : 'a queue -> 'a queue
  end

module type S = sig type a type b end with type a = int with type b = float;;
module type S = sig type a = int type b = float end

Łączenie struktur i sygnatur

Podając jawnie sygnaturę dla struktury ograniczamy wgląd do środka sygnatury. Można to zrobić na kilka sposobów: treść sygnatury i struktury można podać explicite, lub odwołać się do zdefiniowanej sygnatury/struktury.

<definicja> ::= module <Identyfikator> [ : <sygnatura> ] = <struktura> 
<struktura> ::= <struktura> : <sygnatura> <struktura> ::= <Identyfikator> 
<sygnatura> ::= <Identyfikator>      

Przykład [Różne sposoby definiowania modułu FIFO]

module Fifo_implementation = 
  struct
    exception EmptyQueue
    type 'a queue = 'a list
    let empty = []
    let insert q x = q @ [x]
    let front q = 
      match q with
        [] -> raise EmptyQueue |
        h::_ -> h
    let remove q = 
      match q with
        [] -> raise EmptyQueue |
        _::t -> t
  end;;
  
module Fifo : FIFO = Fifo_implementation;;
module Fifo = (Fifo_implementation : FIFO);;
  
module Fifo : sig ... end = struct ... end;;
        

Podobnie jak można rozszerzać sygnatury, można też rozszerzać moduły:

Przykład [Liczby wymierne z dwiema barierami abstrakcji]

Zwróćmy uwagę, że operacje arytmetyczne są zaimplementowane bez znajomości implementacji struktury danych ułamków.

module type ULAMKI = 
  sig 
    type t
    val ulamek : int -> int -> t
    val licznik : t -> int
    val mianownik : t -> int
  end;;
  
module type RAT = 
  sig
    include ULAMKI 
    val plus : t -> t -> t
    val minus : t -> t -> t
    val razy : t -> t -> t
    val podziel : t -> t -> t
    val rowne : t -> t -> bool
  end;;
  
module Ulamki : ULAMKI = 
  struct
    type t = int * int
    let ulamek l m = (l, m)
    let licznik (l, _) = l
    let mianownik (_, m) = m
  end;;
  
module Rat : RAT =
    struct
      include Ulamki 
      let plus x y = 
        ulamek 
          (licznik x * mianownik y + licznik y * mianownik x) 
          (mianownik x * mianownik y)
      let minus x y = 
        ulamek 
          (licznik x * mianownik y - licznik y * mianownik x) 
          (mianownik x * mianownik y)
      let razy x y = 
        ulamek
          (licznik x * licznik y)
          (mianownik x * mianownik y)
      let podziel x y = 
        ulamek
          (licznik x * mianownik y)
          (mianownik x * licznik y)
      let rowne x y = 
        (licznik x * mianownik y) = (licznik y * mianownik x)
    end;;

Jak wyodrębniać moduły?

Jakimi zasadami kierować się dzieląc program na moduły? Każdy program można podzielić na moduły: pierwsze 100 linii, drugie 100 linii, itd. Oczywiście nie każdy podział jest właściwy. Podział programu na moduły powinien być taki, aby:

• powiązania między modułami były jak najmniejsze;
• jak najmniej szczegółów budowy jednego modułu miało wpływ na budowę innego modułu,
• jeden moduł powinien koncentrować się na jednej decyzji
• projektowej, jednym "sekrecie";
• nie należy łączyć nie związanych ze sobą sekretów w jednym module.

Powyższe zasady są znane pod nazwą separation of concerns. Rozważając kilka możliwych podziałów na moduły możemy porównać je stosując następujący eksperyment myślowy. Przygotowujemy listę potencjalnych zmian w programie. Lista ta nie może być wydumana, ani nie może to być lista zmian, które łatwo wprowadzić do programu, ale lista realnych zmian, które mogą wynikać z potrzeb użytkownika programu. Dla każdej z tych zmian i każdego z podziałów na moduły badamy ile modułów należy zmodyfikować w celu prowadzenia danej zmiany. Im więcej modułów, tym gorzej.
Przykład: [D.L.Parnas,On the Criteria To Be Used in Decomposing Systems into Modules, CACM 12 (15), 1972] Przykład problemu: tekst, rotacje cykliczne wierszy. Możliwe podziały mogą organizować się albo wokół faz działania programu, albo wokół danych. Ten drugi sposób jest lepszy.

Laboratoria i ćwiczenia

Laboratoria i ćwiczenia do wykładu