Was ist die funktionale Programmierantwort auf typbasierte Invarianten?

9

Mir ist bewusst, dass das Konzept der Invarianten über mehrere Programmierparadigmen hinweg existiert. Beispielsweise sind Schleifeninvarianten für die OO-, funktionale und prozedurale Programmierung relevant.

Eine sehr nützliche Art in OOP ist jedoch eine Invariante der Daten eines bestimmten Typs. Dies nenne ich im Titel "typbasierte Invarianten". Zum Beispiel Fractionkönnte ein Typ ein numeratorund haben denominator, mit der Invariante, dass sein gcd immer 1 ist (dh der Bruch ist in einer reduzierten Form). Ich kann dies nur garantieren, indem ich eine Art Kapselung des Typs habe und seine Daten nicht frei einstellen kann. Im Gegenzug muss ich nie prüfen, ob es reduziert ist, damit ich Algorithmen wie Gleichheitsprüfungen vereinfachen kann.

Wenn ich dagegen einfach einen FractionTyp deklariere, ohne diese Garantie durch Kapselung bereitzustellen, kann ich keine Funktionen für diesen Typ sicher schreiben, die davon ausgehen, dass der Bruch reduziert wird, da in Zukunft jemand anderes mitkommen und einen Weg hinzufügen könnte einen nicht reduzierten Bruchteil zu bekommen.

Im Allgemeinen kann das Fehlen dieser Art von Invariante zu Folgendem führen:

  • Komplexere Algorithmen als Vorbedingungen müssen an mehreren Stellen überprüft / sichergestellt werden
  • DRY-Verstöße, da diese wiederholten Voraussetzungen dasselbe zugrunde liegende Wissen darstellen (dass die Invariante wahr sein sollte)
  • Voraussetzungen müssen durch Laufzeitfehler und nicht durch Garantien zur Kompilierungszeit erzwungen werden

Meine Frage ist also, wie die funktionale Programmierantwort auf diese Art von Invariante lautet. Gibt es eine funktional-idiomatische Möglichkeit, mehr oder weniger dasselbe zu erreichen? Oder gibt es einen Aspekt der funktionalen Programmierung, der die Vorteile weniger relevant macht?

Ben Aaronson
quelle
Viele funktionale Sprachen können dies trivial tun ... Scala, F # und die anderen Sprachen, die gut mit OOP spielen, aber auch Haskell ... Grundsätzlich unterstützt jede Sprache, in der Sie Typen und deren Verhalten definieren können, dies.
AK_
@AK_ Ich bin mir bewusst, dass F # dies kann (obwohl IIRC ein kleines Springen erfordert) und vermutete, dass Scala dies als eine weitere paradigmenübergreifende Sprache könnte. Interessant, dass Haskell das kann - einen Link? Was ich wirklich suche, ist die funktional-idiomatische Antwort und nicht bestimmte Sprachen, die eine Funktion bieten. Aber natürlich können die Dinge ziemlich verschwommen und subjektiv werden, wenn Sie anfangen, über das Idiomatische zu sprechen, weshalb ich es nicht in Frage gestellt habe.
Ben Aaronson
In Fällen, in denen die Vorbedingung zur Kompilierungszeit nicht überprüft werden kann, ist es idiomatisch, den Konstruktor einzuchecken. Betrachten Sie eine PrimeNumberKlasse. Es wäre zu teuer, für jede Operation mehrere redundante Überprüfungen der Primalität durchzuführen, aber es ist keine Art von Test, der zur Kompilierungszeit durchgeführt werden kann. (Viele Operationen, die Sie mit Primzahlen ausführen möchten, z. B. Multiplikation, bilden keinen Abschluss , dh die Ergebnisse sind wahrscheinlich keine garantierte Primzahl. (Als Kommentar
posten,
Eine scheinbar nicht verwandte Frage, aber ... Sind Behauptungen oder Unit-Tests wichtiger?
Rwong
@rwong Ja, einige schöne Beispiele dort. Ich bin mir allerdings nicht 100% klar, an welchem ​​Endpunkt Sie fahren.
Ben Aaronson

Antworten:

2

Einige funktionale Sprachen wie OCaml verfügen über integrierte Mechanismen zur Implementierung abstrakter Datentypen, wodurch einige Invarianten erzwungen werden . Sprachen, die nicht über solche Mechanismen verfügen, sind darauf angewiesen, dass der Benutzer „nicht unter den Teppich schaut“, um die Invarianten durchzusetzen.

Abstrakte Datentypen in OCaml

In OCaml werden Module zum Strukturieren eines Programms verwendet. Ein Modul hat eine Implementierung und eine Signatur , wobei letzteres eine Art Zusammenfassung der im Modul definierten Werte und Typen ist, während das erstere die tatsächlichen Definitionen bereitstellt. Dies kann lose mit dem Diptychon verglichen werden, das .c/.hC-Programmierern bekannt ist.

Als Beispiel können wir das FractionModul folgendermaßen implementieren :

# 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

Diese Definition kann jetzt folgendermaßen verwendet werden:

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

Jeder kann Werte des Typanteils direkt unter Umgehung des eingebauten Sicherheitsnetzes erzeugen Fraction.make:

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

Um dies zu verhindern, ist es möglich, die konkrete Definition des Typs Fraction.twie folgt auszublenden :

# 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

Die einzige Möglichkeit, eine zu erstellen, AbstractFraction.tbesteht darin, die AbstractFraction.makeFunktion zu verwenden.

Abstrakte Datentypen im Schema

Die Schemasprache verfügt nicht über denselben Mechanismus für abstrakte Datentypen wie OCaml. Es beruht darauf, dass der Benutzer „nicht unter den Teppich schaut“, um eine Kapselung zu erreichen.

In Schema ist es üblich, Prädikate wie das fraction?Erkennen von Werten zu definieren , die die Möglichkeit bieten, die Eingabe zu validieren. Nach meiner Erfahrung besteht die vorherrschende Verwendung darin, den Benutzer seine Eingabe validieren zu lassen, wenn er einen Wert fälscht, anstatt die Eingabe in jedem Bibliotheksaufruf zu validieren.

Es gibt jedoch verschiedene Strategien, um die Abstraktion zurückgegebener Werte zu erzwingen, z. B. die Rückgabe eines Abschlusses, der den Wert liefert, wenn er angewendet wird, oder die Rückgabe eines Verweises auf einen Wert in einem von der Bibliothek verwalteten Pool - aber ich habe in der Praxis keine davon gesehen.

Michael Le Barbier Grünewald
quelle
+1 Erwähnenswert ist auch, dass nicht alle OO-Sprachen die Kapselung erzwingen.
Michael Shaw
5

Die Kapselung ist keine Funktion, die mit OOP geliefert wurde. Jede Sprache, die eine ordnungsgemäße Modularisierung unterstützt, hat sie.

Hier ist ungefähr, wie Sie es in Haskell machen:

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

Um ein Rational zu erstellen, verwenden Sie jetzt die Verhältnisfunktion, die die Invariante erzwingt. Da Daten unveränderlich sind, können Sie die Invariante später nicht mehr verletzen.

Dies kostet Sie jedoch etwas: Es ist dem Benutzer nicht mehr möglich, dieselbe Dekonstruktionsdeklaration wie Nenner und Zähler zu verwenden.

Sebastian Redl
quelle
4

Gehen Sie genauso vor: Erstellen Sie einen Konstruktor , der die Einschränkung erzwingt, und stimmen Sie zu, diesen Konstruktor zu verwenden, wenn Sie einen neuen Wert erstellen.

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

Aber Karl, in OOP muss man nicht zustimmen , den Konstruktor zu verwenden. Ja wirklich?

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

Tatsächlich sind die Möglichkeiten für diese Art von Missbrauch in FP geringer. Sie müssen den Konstruktor wegen der Unveränderlichkeit zuletzt setzen. Ich wünschte, die Leute würden aufhören, die Kapselung als einen Schutz vor inkompetenten Kollegen zu betrachten oder die Notwendigkeit der Kommunikation von Einschränkungen zu vermeiden. Das macht es nicht. Es begrenzt nur die Orte, die Sie überprüfen müssen. Gute FP-Programmierer verwenden auch die Kapselung. Es kommt nur in Form der Kommunikation einiger bevorzugter Funktionen, um bestimmte Arten von Modifikationen vorzunehmen.

Karl Bielefeldt
quelle
Nun, es ist möglich (und idiomatisch), beispielsweise Code in C # zu schreiben, was nicht zulässt, was Sie dort getan haben. Und ich denke, es gibt einen ziemlich klaren Unterschied zwischen einer einzelnen Klasse, die für die Durchsetzung einer Invariante verantwortlich ist, und jeder Funktion, die von irgendjemandem geschrieben wurde, überall dort, wo ein bestimmter Typ verwendet wird, der dieselbe Invariante erzwingen muss.
Ben Aaronson
@BenAaronson Beachten Sie einen Unterschied zwischen "Erzwingen" und " Weitergeben " einer Invariante.
Rwong
1
+1. Diese Technik ist in FP noch leistungsfähiger, da sich unveränderliche Werte nicht ändern. So können Sie mit Typen "ein für alle Mal" Dinge über sie beweisen. Dies ist bei veränderlichen Objekten nicht möglich, da das, was jetzt für sie gilt, später möglicherweise nicht mehr zutrifft. Das Beste, was Sie tun können, ist, den Status des Objekts defensiv zu überprüfen.
Doval
@Doval Ich sehe es nicht. Abgesehen davon, dass die meisten (?) Haupt-OO-Sprachen eine Möglichkeit haben, Variablen unveränderlich zu machen. In OO habe ich: Eine Instanz erstellen, dann mutiert meine Funktion die Werte dieser Instanz auf eine Weise, die möglicherweise der Invariante entspricht oder nicht. In FP habe ich: Eine Instanz erstellen, dann erstellt meine Funktion eine zweite Instanz mit unterschiedlichen Werten auf eine Weise, die möglicherweise der Invariante entspricht oder nicht. Ich sehe nicht, wie Unveränderlichkeit dazu beigetragen hat, dass ich mich sicherer fühle, dass meine Invariante für alle Fälle des Typs konform ist
Ben Aaronson,
2
@BenAaronson Unveränderlichkeit hilft Ihnen nicht zu beweisen, dass Sie Ihren Typ korrekt implementiert haben (dh alle Operationen behalten eine bestimmte Invariante bei). Ich sage, dass Sie damit Fakten über Werte verbreiten können. Sie codieren eine Bedingung (z. B. diese Zahl ist gerade) in einem Typ (indem Sie sie im Konstruktor überprüfen), und der erzeugte Wert ist ein Beweis dafür, dass der ursprüngliche Wert die Bedingung erfüllt. Mit veränderlichen Objekten überprüfen Sie den aktuellen Status und halten das Ergebnis in einem Booleschen Wert. Dieser Boolesche Wert ist nur gültig, solange das Objekt nicht mutiert ist, sodass die Bedingung falsch ist.
Doval