¿Cuál es la respuesta de programación funcional a los invariantes basados ​​en tipos?

9

Soy consciente de que el concepto de invariantes existe en múltiples paradigmas de programación. Por ejemplo, los invariantes de bucle son relevantes en la programación OO, funcional y de procedimiento.

Sin embargo, un tipo muy útil que se encuentra en OOP es una invariante de los datos de un tipo particular. Esto es lo que llamo "invariantes basados ​​en tipos" en el título. Por ejemplo, un Fractiontipo podría tener un numeratory denominator, con la invariante de que su mcd siempre es 1 (es decir, la fracción está en una forma reducida). Solo puedo garantizar esto al tener algún tipo de encapsulación del tipo, sin dejar que sus datos se configuren libremente. A cambio, nunca tengo que verificar si se reduce, por lo que puedo simplificar algoritmos como las verificaciones de igualdad.

Por otro lado, si simplemente declaro un Fractiontipo sin proporcionar esta garantía a través de la encapsulación, no puedo escribir con seguridad ninguna función en este tipo que suponga que la fracción se reduce, porque en el futuro alguien más podría venir y agregar una forma de conseguir una fracción no reducida.

En general, la falta de este tipo de invariante podría conducir a:

  • Los algoritmos más complejos como condiciones previas deben verificarse / garantizarse en múltiples lugares
  • Violaciones SECAS ya que estas precondiciones repetidas representan el mismo conocimiento subyacente (que la invariante debe ser verdadera)
  • Tener que imponer condiciones previas a través de fallas de tiempo de ejecución en lugar de garantías en tiempo de compilación

Entonces mi pregunta es cuál es la respuesta de programación funcional a este tipo de invariante. ¿Existe una forma funcional-idiomática de lograr más o menos lo mismo? ¿O hay algún aspecto de la programación funcional que hace que los beneficios sean menos relevantes?

Ben Aaronson
fuente
muchos lenguajes funcionales pueden hacer esto de manera trivial ... Scala, F # y los otros lenguajes que funcionan bien con OOP, pero también Haskell ... básicamente cualquier lenguaje que le permita definir tipos y su comportamiento lo respalda.
AK_
@AK_ Soy consciente de que F # puede hacer esto (aunque IIRC requiere algunos saltos menores) y supuse que Scala podría ser otro lenguaje de paradigma cruzado. Interesante que Haskell pueda hacerlo, ¿tiene un enlace? Lo que realmente estoy buscando es la respuesta funcional-idiomática , en lugar de los lenguajes específicos que ofrecen una función. Pero, por supuesto, las cosas pueden volverse algo confusas y subjetivas una vez que empiezas a hablar sobre lo que es idiomático, por eso lo dejé fuera de discusión.
Ben Aaronson
Para los casos en que la condición previa no se puede verificar en tiempo de compilación, es idiomático verificar en el constructor. Considera una PrimeNumberclase. Sería demasiado costoso realizar múltiples verificaciones redundantes de primalidad para cada operación, pero no es un tipo de prueba que pueda realizarse en tiempo de compilación. (Una gran cantidad de operaciones que desea realizar en números primos, por ejemplo multiplicación, no forman un cierre , es decir, los resultados probablemente no son garantizados primo (envíos como los comentarios ya que no conozco a mí mismo la programación funcional)..
rwong
Una pregunta aparentemente no relacionada, pero ... ¿Son más importantes las afirmaciones o las pruebas unitarias?
rwong
@rwong Sí, algunos buenos ejemplos allí. Sin embargo, en realidad no estoy 100% claro en qué punto final estás conduciendo.
Ben Aaronson

Respuestas:

2

Algunos lenguajes funcionales como OCaml tienen mecanismos incorporados para implementar tipos de datos abstractos, por lo tanto, imponen algunas invariantes . Los idiomas que no cuentan con tales mecanismos dependen de que el usuario "no mire debajo de la alfombra" para imponer a los invariantes.

Tipos de datos abstractos en OCaml

En OCaml, los módulos se utilizan para estructurar un programa. Un módulo tiene una implementación y una firma , siendo este último un tipo de resumen de valores y tipos definidos en el módulo, mientras que el primero proporciona las definiciones reales. Esto se puede comparar libremente con el díptico .c/.hfamiliar para los programadores de C.

Como ejemplo, podemos implementar el Fractionmódulo de esta manera:

# 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

Esta definición ahora se puede usar así:

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

Cualquiera puede producir valores de la fracción tipo directamente, sin pasar por la red de seguridad incorporada Fraction.make:

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

Para evitar esto, es posible ocultar la definición concreta del tipo Fraction.tasí:

# 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

La única forma de crear un AbstractFraction.tes usar la AbstractFraction.makefunción.

Tipos de datos abstractos en esquema

El lenguaje Scheme no tiene el mismo mecanismo de tipos de datos abstractos que OCaml. Se basa en el usuario "no mirar debajo de la alfombra" para lograr la encapsulación.

En Scheme, es costumbre definir predicados como fraction?reconocer valores que dan la oportunidad de validar la entrada. En mi experiencia, el uso dominante es permitir que el usuario valide su entrada, si falsifica un valor, en lugar de validar la entrada en cada llamada a la biblioteca.

Sin embargo, existen varias estrategias para imponer la abstracción de los valores devueltos, como devolver un cierre que produce el valor cuando se aplica o devolver una referencia a un valor en un grupo administrado por la biblioteca, pero nunca vi ninguno de ellos en la práctica.

Michael Le Barbier Grünewald
fuente
+1 También vale la pena mencionar que no todos los lenguajes OO imponen la encapsulación.
Michael Shaw
5

La encapsulación no es una característica que vino con OOP. Cualquier lenguaje que admita una modularización adecuada lo tiene.

A continuación, te mostramos cómo hacerlo en 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)

Ahora, para crear un Rational, utiliza la función de relación, que aplica la invariante. Debido a que los datos son inmutables, no puede violar más tarde la invariante.

Sin embargo, esto le cuesta algo: ya no es posible que el usuario use la misma declaración de deconstrucción que el uso de denominador y numerador.

Sebastian Redl
fuente
4

Lo haces de la misma manera: crea un constructor que aplique la restricción y acepta usar ese constructor cada vez que crees un nuevo valor.

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

Pero Karl, en OOP no tienes que aceptar usar el constructor. ¿Oh enserio?

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

De hecho, las oportunidades para este tipo de abuso son menores en FP. Usted tiene que poner el constructor pasado, debido a la inmutabilidad. Desearía que la gente dejara de pensar en la encapsulación como una especie de protección contra colegas incompetentes, o como obviando la necesidad de comunicar restricciones. No hace eso. Simplemente limita los lugares que tiene que consultar. Los buenos programadores de FP también usan encapsulación. Simplemente viene en forma de comunicar algunas funciones preferidas para hacer ciertos tipos de modificaciones.

Karl Bielefeldt
fuente
Bueno, es posible (e idiomático) escribir código en C #, por ejemplo, lo que no permite lo que has hecho allí. Y creo que hay una diferencia bastante clara entre una sola clase responsable de hacer cumplir una invariante y cada función escrita por cualquier persona, en cualquier lugar que use un cierto tipo que tenga que hacer cumplir la misma invariante.
Ben Aaronson
@BenAaronson Observe una diferencia entre "imponer" y "propagar" un invariante.
rwong
1
+1. Esta técnica es aún más poderosa en FP porque los valores inmutables no cambian; así puedes probar cosas sobre ellos "de una vez por todas" usando tipos. Esto no es posible con objetos mutables porque lo que es verdad para ellos ahora puede no serlo más tarde; lo mejor que puedes hacer a la defensiva vuelve a comprobar el estado del objeto.
Doval
@Doval, no lo estoy viendo. Dejando de lado que la mayoría (?) De los principales idiomas OO tienen una forma de hacer que las variables sean inmutables. En OO tengo: Crear una instancia, luego mi función muta los valores de esa instancia de una manera que puede o no ajustarse a la invariante. En FP tengo: Crear una instancia, luego mi función crea una segunda instancia con diferentes valores de una manera que puede o no ajustarse a la invariante. No veo cómo la inmutabilidad me ha ayudado a sentirme más segura de que mi invariante se ajusta a todas las instancias del tipo
Ben Aaronson
2
@BenAaronson La inmutabilidad no lo ayudará a demostrar que ha implementado su tipo correctamente (es decir, todas las operaciones conservan algunos invariantes dados). Lo que estoy diciendo es que le permite propagar datos sobre valores. Codifica alguna condición (por ejemplo, este número es par) en un tipo (verificándolo en el constructor) y el valor producido es una prueba de que el valor original cumplió la condición. Con los objetos mutables, verifica el estado actual y mantiene el resultado en un valor booleano. Ese booleano solo es bueno mientras el objeto no esté mutado, por lo que la condición es falsa.
Doval