Qual é a resposta da programação funcional para invariantes baseados em tipo?

9

Estou ciente de que o conceito de invariantes existe em vários paradigmas de programação. Por exemplo, invariantes de loop são relevantes em OO, programação funcional e processual.

No entanto, um tipo muito útil encontrado no OOP é um invariante dos dados de um tipo específico. É isso que estou chamando de "invariantes baseados em tipo" no título. Por exemplo, um Fractiontipo pode ter um numeratore denominator, com o invariante que a sua gcd é sempre 1 (isto é, a fracção está numa forma reduzida). Só posso garantir isso tendo algum tipo de encapsulamento do tipo, não permitindo que seus dados sejam configurados livremente. Em troca, nunca tenho que verificar se é reduzido, para simplificar algoritmos como verificações de igualdade.

Por outro lado, se eu simplesmente declarar um Fractiontipo sem fornecer essa garantia por meio do encapsulamento, não posso escrever com segurança nenhuma função nesse tipo que assuma que a fração seja reduzida, porque no futuro alguém mais poderia aparecer e adicionar uma maneira de se apossar de uma fração não reduzida.

Geralmente, a falta desse tipo de invariante pode levar a:

  • Algoritmos mais complexos, pois as pré-condições precisam ser verificadas / garantidas em vários locais
  • Violações DRY, pois essas pré-condições repetidas representam o mesmo conhecimento subjacente (que o invariante deve ser verdadeiro)
  • Ter que impor condições prévias através de falhas de tempo de execução, em vez de garantias em tempo de compilação

Então, minha pergunta é qual é a resposta da programação funcional para esse tipo de invariante. Existe uma maneira idiomática funcional de conseguir mais ou menos a mesma coisa? Ou há algum aspecto da programação funcional que torna os benefícios menos relevantes?

Ben Aaronson
fonte
muitas linguagens funcionais podem fazer isso trivialmente ... Scala, F # e outras linguagens que funcionam bem com OOP, mas Haskell também ... basicamente qualquer linguagem que permita definir tipos e seu comportamento suporta isso.
AK_
@AK_ Estou ciente de que o F # pode fazer isso (embora o IIRC exija alguns pequenos pulos de argola) e imaginei que Scala poderia ser uma outra linguagem entre paradigmas. Interessante que Haskell possa fazer isso - conseguiu um link? O que realmente estou procurando é a resposta idiomática funcional , em vez de idiomas específicos que oferecem um recurso. Mas é claro que as coisas podem ficar um pouco confusas e subjetivas quando você começa a falar sobre o que é idiomático, e foi por isso que deixei de fora da questão.
Ben Aaronson
Nos casos em que a pré-condição não pode ser verificada em tempo de compilação, é idiomático fazer check-in no construtor. Considere uma PrimeNumberaula. Seria muito caro executar várias verificações redundantes de primalidade para cada operação, mas não é um tipo de teste que pode ser executado em tempo de compilação. (A série de operações que você gostaria de realizar em números primos, digamos, multiplicação, não formam um fechamento , ou seja, os resultados provavelmente não são garantidos prime (Posting como comentários, uma vez que não conheço programação funcional eu)..
rwong
Uma pergunta aparentemente não relacionada, mas ... As afirmações ou testes de unidade são mais importantes?
rwong 21/05
@ rwong Sim, alguns bons exemplos lá. Na verdade, não estou 100% claro em que ponto final você está dirigindo.
Ben Aaronson

Respostas:

2

Algumas linguagens funcionais, como o OCaml, possuem mecanismos internos para implementar tipos de dados abstratos, portanto, reforçando alguns invariantes . Os idiomas que não possuem esses mecanismos dependem do usuário "não olhar embaixo do tapete" para impor os invariantes.

Tipos de dados abstratos no OCaml

No OCaml, os módulos são usados ​​para estruturar um programa. Um módulo possui uma implementação e uma assinatura , sendo o último um tipo de resumo dos valores e tipos definidos no módulo, enquanto o primeiro fornece as definições reais. Isso pode ser pouco comparado ao díptico .c/.hfamiliar aos programadores em C.

Como exemplo, podemos implementar o Fractionmódulo assim:

# 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 definição agora pode ser usada assim:

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

Qualquer pessoa pode produzir valores da fração de tipo diretamente, ignorando a rede de segurança incorporada em Fraction.make:

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

Para evitar isso, é possível ocultar a definição concreta do tipo Fraction.tassim:

# 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

A única maneira de criar um AbstractFraction.té usar a AbstractFraction.makefunção

Tipos de dados abstratos no esquema

A linguagem do esquema não possui o mesmo mecanismo de tipos abstratos de dados que o OCaml. Ele conta com o usuário "não olhando embaixo do tapete" para alcançar o encapsulamento.

No esquema, é habitual definir predicados, como fraction?reconhecer valores, dando a oportunidade de validar a entrada. Na minha experiência, o uso dominante é permitir que o usuário valide sua entrada, se forjar um valor, em vez de validar a entrada em cada chamada da biblioteca.

No entanto, existem várias estratégias para impor a abstração dos valores retornados, como retornar um fechamento que gera o valor quando aplicado ou retornar uma referência a um valor em um pool gerenciado pela biblioteca - mas nunca vi nenhum deles na prática.

Michael Le Barbier Grünewald
fonte
+1 Também vale a pena mencionar que nem todos os idiomas OO impõem o encapsulamento.
Michael Shaw
5

Encapsulamento não é um recurso que acompanha o OOP. Qualquer linguagem que suporte modularização adequada possui.

Aqui está mais ou menos como você faz isso em 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)

Agora, para criar um Rational, você usa a função ratio, que impõe a invariável. Como os dados são imutáveis, você não pode mais tarde violar o invariável.

No entanto, isso custa algo para você: não é mais possível que o usuário use a mesma declaração de desconstrução que o denominador e o numerador.

Sebastian Redl
fonte
4

Você faz da mesma maneira: crie um construtor que imponha a restrição e concorde em usá-lo sempre que criar um novo valor.

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

Mas Karl, no OOP, você não precisa concordar em usar o construtor. Sério?

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

De fato, as oportunidades para esse tipo de abuso são menores no PF. Você tem que colocar o construtor por último, por causa da imutabilidade. Eu gostaria que as pessoas parassem de pensar no encapsulamento como algum tipo de proteção contra colegas incompetentes, ou como obvia a necessidade de comunicar restrições. Não faz isso. Apenas limita os lugares que você deve verificar. Bons programadores de FP também usam encapsulamento. Ele vem apenas na forma de comunicar algumas funções preferidas para fazer certos tipos de modificações.

Karl Bielefeldt
fonte
Bem, é possível (e idiomático) escrever código em C #, por exemplo, o que não permite o que você fez lá. E acho que há uma clara diferença entre uma única classe ser responsável por impor uma invariante e todas as funções escritas por qualquer pessoa, em qualquer lugar que use um determinado tipo para impor a mesma invariante.
Ben Aaronson
@BenAaronson Observe a diferença entre "impor" e "propagar" uma invariante.
rwong 21/05
11
+1. Essa técnica é ainda mais poderosa no FP, porque valores imutáveis ​​não mudam; assim, você pode provar coisas sobre eles "de uma vez por todas" usando tipos. Isso não é possível com objetos mutáveis, porque o que é verdade para eles agora pode não ser verdade mais tarde; o melhor que você pode fazer é verificar novamente defensivamente o estado do objeto.
Doval
@Doval Não estou vendo. Deixando de lado que a maioria das principais linguagens OO tem uma maneira de tornar variáveis ​​imutáveis. No OO eu tenho: Crie uma instância, então minha função modifica os valores dessa instância de uma maneira que pode ou não estar em conformidade com o invariante. No FP, eu tenho: Criar uma instância, então minha função cria uma segunda instância com valores diferentes de uma maneira que pode ou não estar em conformidade com a invariante. Eu não vejo como a imutabilidade ajudou a tornar-me sentir mais confiante de que minha invariante é conformado a para todas as instâncias do tipo
Ben Aaronson
2
A @BenAaronson Immutability não ajudará você a provar que implementou seu tipo corretamente (ou seja, todas as operações preservam algumas invariantes). O que estou dizendo é que isso permite que você propague fatos sobre valores. Você codifica alguma condição (por exemplo, esse número é par) em um tipo (verificando-o no construtor) e o valor produzido é a prova de que o valor original atendeu à condição. Com objetos mutáveis, você verifica o estado atual e mantém o resultado em um valor booleano. Esse booleano só é bom enquanto o objeto não for alterado para que a condição seja falsa.
Doval