Programowanie funkcyjne/Moduły

From Studia Informatyczne

Spis treści

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 ewentualne 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, 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. W następnym punkcie zobaczymy jak można określać sygnaturę modułu. Najpierw jednak zobaczmy jak wyglądają same sygnatury.

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 sygnaturę struktury określamy tym samym jej interfejs. Tylko te elementy struktury, które należą do sygnatury, będą widoczne na zewnątrz struktury. Wszystkie pozostałe elementy struktury będą lokalne dla niej. Oczywiście wszystkie elementy, które są zadeklarowane w sygnaturze, muszą być zdefiniowane w strukturze.

Składniowo, sygnaturę struktury można określić na kilka sposobów: treść sygnatury i struktury można podać explicite lub użyć nazwy wcześniej zdefiniowanej sygnatury/struktury, sygnaturę można też podać przy nazwie modułu lub przy tworzącej go strukturze.

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


Przykład [Różne sposoby określania sygnatur]

Określając sygnaturę modułu możemy to zrobić w dowolny (zgodny ze składnią) sposób. Poniższe przykłady ilustrują różne sposoby definiowania modułu implementującego kolejki FIFO, zgodnego z sygnaturą 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ć struktury. Definiując jedną strukturę, można do niej "wciągnąć" zawartość innej struktury. Robimy to za pomocą konstrukcji include. Struktura taka zawiera wszystko to, co zawiera "wciągnięta" struktura, jak i wszystkie inne definicje podane explicite.

<definicja> ::= include <Identyfikator>


Przykład [Rozszerzanie struktur]

Moduły są formą enkapsulacji, bariery abstrakcji, która oddziela użytkowników modułu od sposobu jego implementacji. Typowy moduł definiuje strukturę danych oraz operacje na niej. Jednak nie wszystkie udostępniane operacje muszą zależeć od sposobu realizacji struktury danych. Wówczas możemy wprowadzić dodatkową barierę abstrakcji oddzielającą realizację struktury danych i implementację operacji zależnych od niej, od implementacji pozostałych operacji. Korzyść z takiej dodatkowej bariery abstrakcji jest taka, że w przypadku modyfikacji struktury danych, tylko część operacji wymaga zmiany.

Taką dodatkową barierę abstrakcji możemy zapisać definiując dwa moduły i używając rozszerzania modułów. Poniższy przykład ilustruje zastosowanie tej techniki w module implementującym ułamki i operacje na nich.

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;;

Zasady tworzenia modułów

Jakimi zasadami kierować się dzieląc program na moduły? Odpowiedź na to pytanie należy do inżynierii oprogramowania, a nie do programowania funkcyjnego. Skoro jednak zajmujemy się modułami, to powiedzmy o tym kilka słów.

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,
  • każdy moduł powinien koncentrować się wokół jednej decyzji projektowej, tzw. "sekretu" modułu, przy czym nie należy łączyć nie związanych ze sobą sekretów w jednym module; zasada ta jest znana pod nazwą separation of concerns,
  • użytkownicy modułów powinni polegać jedynie na tym, co jest określone w interfejsie i specyfikacji modułu, natomiast nie powinni polegać na żadnym konkretnym sposobie implementacji modułu, tzw. black-box approach.
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 wprowadzenia danej zmiany. Im mniej modułów, tym lepiej, gdyż zmiany są bardziej lokalne.

Pamiętajmy, że z punktu widzenia języka programowania sygnatura to zestaw deklaracji, nagłówków, określających interfejs modułu. Jednak interfejs, tak jak go widzą użytkownicy modułu, to nie tylko nagłówki, ale i specyfikacja modułu. Dlatego też często w sygnaturze zapisuje się w komentarzach (nieformalną) specyfikację modułu. Tak też powinniśmy myśleć o sygnaturach. Jeżeli zdarzy nam się zdefiniować dwie sygnatury identyczne z punktu widzenia języka programowania, ale różniące się zawartymi w komentarzach specyfikacjami, to nie ma w tym nic niewłaściwego.

Ćwiczenia

Ćwiczenia