Jaka jest funkcjonalna odpowiedź programowa na niezmienniki oparte na typie?

9

Wiem, że koncepcja niezmienników istnieje w wielu paradygmatach programowania. Na przykład niezmienniki pętli są istotne w OO, programowaniu funkcjonalnym i proceduralnym.

Jednak jednym bardzo przydatnym rodzajem znalezionym w OOP jest niezmiennik danych określonego typu. To właśnie nazywam w tytule „niezmiennikami opartymi na typie”. Na przykład Fractiontyp może mieć numeratora denominator, przy niezmienniku, że ich gcd wynosi zawsze 1 (tzn. Ułamek jest w postaci zredukowanej). Mogę to zagwarantować tylko poprzez pewnego rodzaju enkapsulację tego typu, nie pozwalając na swobodne ustawianie danych. W zamian nigdy nie muszę sprawdzać, czy jest zmniejszone, więc mogę uprościć algorytmy, takie jak kontrole równości.

Z drugiej strony, jeśli po prostu zadeklaruję Fractiontyp bez zapewnienia tej gwarancji poprzez enkapsulację, nie mogę bezpiecznie napisać żadnych funkcji tego typu, które zakładają, że ułamek jest zmniejszony, ponieważ w przyszłości ktoś inny mógłby przyjść i dodać sposób zdobycia niezredukowanej frakcji.

Zasadniczo brak tego rodzaju niezmiennika może prowadzić do:

  • Bardziej złożone algorytmy, ponieważ warunki wstępne muszą być sprawdzane / zapewniane w wielu miejscach
  • Naruszenia OSUSZANIA, ponieważ te powtarzające się warunki wstępne reprezentują tę samą wiedzę podstawową (że niezmiennik powinien być prawdziwy)
  • Konieczność egzekwowania warunków wstępnych przez awarie środowiska wykonawczego zamiast gwarancji czasu kompilacji

Moje pytanie brzmi więc, jaka jest funkcjonalna odpowiedź programowa na tego rodzaju niezmiennik. Czy istnieje funkcjonalnie-idiomatyczny sposób osiągnięcia mniej więcej tego samego? Czy jest jakiś aspekt programowania funkcjonalnego, który sprawia, że ​​korzyści są mniej istotne?

Ben Aaronson
źródło
wiele funkcjonalnych języków potrafi to zrobić w trywialny sposób ... Scala, F # i inne języki, które ładnie grają w OOP, ale Haskell też ... w zasadzie każdy język, który pozwala definiować typy i ich zachowanie, obsługuje to.
AK_
@AK_ Wiem, że F # może to zrobić (chociaż IIRC wymaga niewielkich skoków do obręczy) i domyśliłem się, że Scala może być innym językiem krzyżowym. Ciekawe, że Haskell może to zrobić - masz link? Naprawdę szukam odpowiedzi funkcjonalno-idiomatycznej , a nie konkretnych języków, które oferują tę funkcję. Ale oczywiście rzeczy mogą stać się dość rozmyte i subiektywne, kiedy zaczniesz mówić o tym, co jest idiomatyczne, i dlatego pominąłem to.
Ben Aaronson
W przypadkach, w których nie można sprawdzić warunku wstępnego w czasie kompilacji, idiomatyczne jest sprawdzenie w konstruktorze. Rozważ PrimeNumberklasę. Wykonanie wielu redundantnych kontroli pierwszeństwa dla każdej operacji byłoby zbyt drogie, ale nie jest to rodzaj testu, który można wykonać w czasie kompilacji. (Wiele operacji, które chciałbyś wykonać na liczbach pierwszych, powiedzmy, mnożenie, nie tworzy zamknięcia , tzn. Wyniki prawdopodobnie nie są gwarantowane jako liczby pierwsze. (Publikowanie jako komentarz, ponieważ sam nie znam programowania funkcjonalnego.)
rwong
Pozornie niezwiązane pytanie, ale ... Czy twierdzenia lub testy jednostkowe są ważniejsze?
rwong
@rwong Tak, kilka fajnych przykładów. W rzeczywistości nie jestem w 100% pewien, do jakiego ostatecznego punktu dążysz.
Ben Aaronson

Odpowiedzi:

2

Niektóre języki funkcjonalne, takie jak OCaml, mają wbudowane mechanizmy implementujące abstrakcyjne typy danych, które wymuszają niektóre niezmienniki . Języki, które nie mają takich mechanizmów, polegają na tym, że użytkownik „nie zagląda pod dywan” w celu wymuszenia niezmienników.

Abstrakcyjne typy danych w OCaml

W OCaml moduły są używane do struktury programu. Moduł ma implementację i podpis , przy czym ten ostatni jest rodzajem podsumowania wartości i typów zdefiniowanych w module, podczas gdy ten pierwszy zawiera rzeczywiste definicje. Można to luźno porównać do dyptyku .c/.hznanego programistom C.

Jako przykład możemy zaimplementować Fractionmoduł w następujący sposób:

# module Fraction = struct
  type t = Fraction of int * int
  let rec gcd a b =
    match a mod b with
    | 0 -> b
    | r -> gcd b r

  let make a b =
   if b = 0 then
     invalid_arg "Fraction.make"
   else let d = gcd (abs a) (abs b) in
     Fraction(a/d, b/d)

  let to_string (Fraction(a,b)) =
    Printf.sprintf "Fraction(%d,%d)" a b

  let add (Fraction(a1,b1)) (Fraction(a2,b2)) =
    make (a1*b2 + a2*b1) (b1*b2)

  let mult (Fraction(a1,b1)) (Fraction(a2,b2)) =
    make (a1*a2) (b1*b2)
end;;

module Fraction :
  sig
    type t = Fraction of int * int
    val gcd : int -> int -> int
    val make : int -> int -> t
    val to_string : t -> string
    val add : t -> t -> t
    val mult : t -> t -> t
  end

Tej definicji można teraz używać w następujący sposób:

# Fraction.add (Fraction.make 8 6) (Fraction.make 14 21);;
- : Fraction.t = Fraction.Fraction (2, 1)

Każdy może wytworzyć wartości frakcji typu bezpośrednio, omijając wbudowaną siatkę bezpieczeństwa Fraction.make:

# Fraction.Fraction(0,0);;
- : Fraction.t = Fraction.Fraction (0, 0)

Aby temu zapobiec, możliwe jest ukrycie konkretnej definicji typu Fraction.t:

# module AbstractFraction : sig
  type t
  val make : int -> int -> t
  val to_string : t -> string
  val add : t -> t -> t
  val mult : t -> t -> t
end = Fraction;;

module AbstractFraction :
sig
  type t
  val make : int -> int -> t
  val to_string : t -> string
  val add : t -> t -> t
  val mult : t -> t -> t
end

Jedynym sposobem na utworzenie AbstractFraction.tjest użycie AbstractFraction.makefunkcji.

Abstrakcyjne typy danych w schemacie

Język schematu nie ma tego samego mechanizmu abstrakcyjnych typów danych, co OCaml. Polega ona na tym, że użytkownik „nie patrzy pod dywan”, aby uzyskać hermetyzację.

W schemacie zwyczajowo definiuje się predykaty, takie jak fraction?rozpoznawanie wartości, dające możliwość weryfikacji danych wejściowych. Z mojego doświadczenia wynika, że ​​dominującym zastosowaniem jest umożliwienie użytkownikowi sprawdzania poprawności danych wejściowych, jeśli wykuwa wartość, zamiast sprawdzania poprawności danych wejściowych w każdym wywołaniu biblioteki.

Istnieje jednak kilka strategii wymuszających abstrakcję zwracanych wartości, takich jak zwracanie zamknięcia, które daje wartość po zastosowaniu lub zwracanie odwołania do wartości w puli zarządzanej przez bibliotekę - ale nigdy nie widziałem żadnej z nich w praktyce.

Michael Le Barbier Grünewald
źródło
+1 Warto również wspomnieć, że nie wszystkie języki OO wymuszają enkapsulację.
Michael Shaw
5

Hermetyzacja nie jest funkcją dostarczaną z OOP. Ma go każdy język, który obsługuje odpowiednią modularyzację.

Oto w przybliżeniu, jak to robisz w Haskell:

-- Rational.hs
module Rational (
    -- This is the export list. Functions not in this list aren't visible to importers.
    Rational, -- Exports the data type, but not its constructor.
    ratio,
    numerator,
    denominator
    ) where

data Rational = Rational Int Int

-- This is the function we provide for users to create rationals
ratio :: Int -> Int -> Rational
ratio num den = let (num', den') = reduce num den
                 in Rational num' den'

-- These are the member accessors
numerator :: Rational -> Int
numerator (Rational num _) = num

denominator :: Rational -> Int
denominator (Rational _ den) = den

reduce :: Int -> Int -> (Int, Int)
reduce a b = let g = gcd a b
             in (a `div` g, b `div` g)

Teraz, aby utworzyć produkt Rational, użyj funkcji ratio, która wymusza niezmiennik. Ponieważ dane są niezmienne, nie można później naruszyć niezmiennika.

To cię jednak kosztuje: użytkownik nie może już używać tej samej deklaracji dekonstrukcyjnej, co w mianowniku i liczniku.

Sebastian Redl
źródło
4

Robisz to w ten sam sposób: stwórz konstruktor, który wymusza ograniczenie, i zgódź się na użycie tego konstruktora za każdym razem, gdy utworzysz nową wartość.

multiply lhs rhs = ReducedFraction (lhs.num * rhs.num) (lhs.denom * rhs.denom)

Ale Karl, w OOP nie musisz zgadzać się na użycie konstruktora. Naprawdę?

class Fraction:
  ...
  Fraction multiply(Fraction lhs, Fraction rhs):
    Fraction result = lhs.clone()
    result.num *= rhs.num
    result.denom *= rhs.denom
    return result

W rzeczywistości możliwości tego rodzaju nadużyć są mniejsze w FP. Ci mają umieścić konstruktor ostatni, ze względu na niezmienność. Chciałbym, żeby ludzie przestali myśleć o enkapsulacji jako o jakiejś ochronie przed niekompetentnymi kolegami lub jako o unikaniu konieczności komunikowania się z ograniczeniami. To nie robi tego. To ogranicza miejsca, które musisz sprawdzić. Dobrzy programiści FP również używają enkapsulacji. Po prostu występuje w postaci przekazywania kilku preferowanych funkcji w celu dokonania pewnych modyfikacji.

Karl Bielefeldt
źródło
Cóż, możliwe jest (i idiomatyczne) pisanie kodu na przykład w C #, co nie pozwala na to, co tam zrobiłeś. I myślę, że istnieje całkiem wyraźna różnica między pojedynczą klasą odpowiedzialną za wymuszanie niezmiennika a każdą funkcją napisaną przez kogokolwiek, gdziekolwiek, gdzie pewien typ wymaga wymuszenia tego samego niezmiennika.
Ben Aaronson
@BenAaronson Zwróć uwagę na różnicę między „wymuszaniem” a „propagowaniem” niezmiennika.
rwong
1
+1. Ta technika jest jeszcze potężniejsza w FP, ponieważ niezmienne wartości się nie zmieniają; w ten sposób możesz udowodnić o nich „raz na zawsze” za pomocą typów. Nie jest to możliwe w przypadku obiektów zmiennych, ponieważ to, co jest dla nich teraz prawdziwe, może nie być prawdą później; najlepiej jak potrafisz obronnie, ponownie sprawdź stan obiektu.
Doval
@Doval Nie widzę tego. Odkładając na bok, że większość (?) Głównych języków OO ma sposób uczynienia zmiennych niezmiennymi. W OO mam: Utwórz instancję, a następnie moja funkcja mutuje wartości tej instancji w sposób, który może, ale nie musi, być zgodny z niezmiennikiem. W FP mam: Utwórz instancję, a następnie moja funkcja tworzy drugą instancję z różnymi wartościami w sposób, który może, ale nie musi, być zgodny z niezmiennikiem. Nie rozumiem, w jaki sposób niezmienność sprawiła, że ​​poczułem się bardziej pewny, że mój niezmiennik jest dostosowany do wszystkich przypadków tego typu
Ben Aaronson
2
@BenAaronson Niezmienność nie pomoże ci udowodnić, że poprawnie zaimplementowałeś swój typ (tzn. Wszystkie operacje zachowują niektóre niezmienniki). Mówię, że pozwala to rozpowszechniać fakty na temat wartości. Kodujesz jakiś warunek (np. Ta liczba jest parzysta) w typie (sprawdzając go w konstruktorze), a wygenerowana wartość jest dowodem, że oryginalna wartość spełnia warunek. W przypadku obiektów zmiennych można sprawdzić bieżący stan i zachować wynik w postaci logicznej. Ta wartość logiczna jest dobra tylko tak długo, jak długo obiekt nie jest zmutowany, więc warunek jest fałszywy.
Doval