Каков ответ функционального программирования на основанные на типе инварианты?

9

Я знаю, что концепция инвариантов существует в нескольких парадигмах программирования. Например, инварианты цикла актуальны в ОО, функциональном и процедурном программировании.

Однако, один очень полезный вид, найденный в ООП, является инвариантом данных определенного типа. Это то, что я называю «инвариантами на основе типов» в заголовке. Например, Fractionтип может иметь numeratorи denominatorс инвариантом, что их gcd всегда равен 1 (т.е. дробь находится в сокращенной форме). Я могу гарантировать это только наличием некоторой инкапсуляции типа, не позволяющей свободно устанавливать его данные. В свою очередь, мне никогда не нужно проверять, уменьшено ли оно, поэтому я могу упростить алгоритмы, такие как проверки на равенство.

С другой стороны, если я просто объявлю Fractionтип без предоставления этой гарантии посредством инкапсуляции, я не смогу безопасно написать какие-либо функции для этого типа, которые предполагают, что дробь уменьшена, потому что в будущем кто-то еще может прийти и добавить способ получить неуменьшенную фракцию.

Как правило, отсутствие этого вида инварианта может привести к:

  • Более сложные алгоритмы как предварительные условия должны быть проверены / обеспечены в нескольких местах
  • СУХОЕ нарушение, поскольку эти повторяющиеся предварительные условия представляют одно и то же базовое знание (что инвариант должен быть верным)
  • Необходимость принудительного выполнения предварительных условий из-за сбоев во время выполнения, а не гарантий во время компиляции

Так что мой вопрос в том, что ответ функционального программирования на этот вид инварианта. Существует ли функционально-идиоматический способ достижения более или менее одного и того же? Или есть какой-то аспект функционального программирования, который делает преимущества менее значимыми?

Бен Ааронсон
источник
многие функциональные языки могут делать это тривиально ... Scala, F # и другие языки, которые хорошо работают с ООП, но также и с Haskell ... в основном любой язык, который позволяет вам определять типы, и их поведение поддерживает это.
AK_
@AK_ Я знаю, что F # может сделать это (хотя IIRC требует небольшого количества прыжков с обруча) и предположил, что Scala мог бы использовать его как другой кросс-парадигмальный язык. Интересно, что Haskell может это сделать - есть ссылка? Что я действительно ищу, так это функционально-идиоматический ответ, а не конкретные языки, которые предлагают такую ​​возможность. Но, конечно, все может стать довольно размытым и субъективным, если вы начнете говорить о том, что идиоматично, поэтому я оставил это вне вопроса.
Бен Ааронсон
Для случаев, когда предварительное условие не может быть проверено во время компиляции, идиоматично проверять в конструкторе. Рассмотрим PrimeNumberкласс. Было бы слишком дорого выполнять несколько избыточных проверок на простоту для каждой операции, но это не тот тип теста, который можно выполнить во время компиляции. (Многие операции, которые вы хотели бы выполнить с простыми числами, скажем, умножение, не образуют замыкание , т.е. результаты, вероятно, не гарантируются простыми числами . (Публикация в виде комментариев, поскольку я сам не знаю функционального программирования.)
rwong
Кажущийся не связанным с этим вопрос, но ... Важнее ли утверждения или юнит-тесты?
Rwong
@ rwong Да, есть несколько хороших примеров. Я на самом деле не на 100% понимаю, к чему ты клонишь.
Бен Ааронсон

Ответы:

2

Некоторые функциональные языки, такие как OCaml, имеют встроенные механизмы для реализации абстрактных типов данных, что обеспечивает применение некоторых инвариантов . Языки, которые не имеют таких механизмов, полагаются на пользователя, «не заглядывающего под ковер» для обеспечения соблюдения инвариантов.

Абстрактные типы данных в OCaml

В OCaml модули используются для структурирования программы. Модуль имеет реализацию и сигнатуру , последний является своего рода сводкой значений и типов, определенных в модуле, тогда как первый предоставляет фактические определения. Это можно сравнить с диптихом, .c/.hзнакомым программистам на Си.

В качестве примера, мы можем реализовать Fractionмодуль следующим образом:

# 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

Это определение теперь можно использовать так:

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

Любой может получить значения типовой доли напрямую, минуя встроенную систему безопасности Fraction.make:

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

Чтобы предотвратить это, можно скрыть конкретное определение типа 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

Единственный способ создать это AbstractFraction.t- использовать AbstractFraction.makeфункцию.

Абстрактные типы данных в схеме

Язык Scheme не имеет такого же механизма абстрактных типов данных, как OCaml. Он полагается на пользователя, «не заглядывающего под ковер» для достижения инкапсуляции.

В Схеме обычно определяют предикаты, такие как fraction?распознавание значений, дающих возможность проверить входные данные. По моему опыту, доминирующее использование - позволить пользователю проверять свой ввод, если он подделывает значение, а не проверять ввод в каждом вызове библиотеки.

Однако существует несколько стратегий для принудительного абстрагирования возвращаемых значений, например, возвращая замыкание, которое возвращает значение при применении, или возвращая ссылку на значение в пуле, управляемом библиотекой, - но я никогда не видел ни одного из них на практике.

Михаэль Ле Барбье Грюневальд
источник
+1 Стоит также отметить, что не все ОО-языки обеспечивают инкапсуляцию.
Майкл Шоу
5

Инкапсуляция не является функцией, которая пришла с ООП. Любой язык, который поддерживает правильную модуляризацию, имеет это.

Вот примерно как вы это делаете на Хаскеле:

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

Теперь, чтобы создать Rational, вы используете функцию отношений, которая применяет инвариант. Поскольку данные неизменны, вы не сможете позже нарушить инвариант.

Однако это вам чего-то стоит: пользователь больше не может использовать ту же деконструирующую декларацию, что и знаменатель и числитель.

Себастьян Редл
источник
4

Вы делаете это так же: создаете конструктор, который обеспечивает ограничение, и соглашаетесь использовать этот конструктор всякий раз, когда вы создаете новое значение.

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

Но, Карл, в ООП вам не нужно соглашаться на использование конструктора. Да неужели?

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

На самом деле, возможности для такого рода злоупотреблений в FP меньше. Вы должны поставить конструктор последним из-за неизменности. Я бы хотел, чтобы люди перестали думать о инкапсуляции как о некой защите от некомпетентных коллег или об устранении необходимости сообщать об ограничениях. Это не делает этого. Это просто ограничивает места, которые вы должны проверить. Хорошие программисты FP также используют инкапсуляцию. Это просто происходит в форме сообщения нескольких предпочтительных функций для внесения определенных изменений.

Карл Билефельдт
источник
Ну, можно (и идиоматично), например, написать код на C #, что не позволяет делать то, что вы там сделали. И я думаю, что есть довольно четкое различие между одним классом, отвечающим за принудительное выполнение инварианта, и каждой функцией, написанной кем-либо, где бы ни использовался определенный тип для принудительного применения того же инварианта.
Бен Ааронсон
@BenAaronson Обратите внимание на разницу между «применением» и «распространением» инварианта.
Руонг
1
+1. Этот метод еще более мощный в FP, потому что неизменяемые значения не меняются; таким образом, вы можете доказать вещи о них "раз и навсегда", используя типы. Это невозможно с изменяемыми объектами, потому что то, что верно для них сейчас, может не быть правдой позже; лучшее, что вы можете сделать в обороне - перепроверить состояние объекта.
Довал
@Doval Я не вижу этого. Если оставить в стороне, что большинство (?) Основных ОО-языков имеют способ сделать переменные неизменяемыми. В OO у меня есть: Создать экземпляр, затем моя функция изменяет значения этого экземпляра таким образом, который может соответствовать или не соответствовать инварианту. В FP у меня есть: Создать экземпляр, затем моя функция создает второй экземпляр с различными значениями таким образом, который может соответствовать или не соответствовать инварианту. Я не понимаю, как неизменность помогла мне почувствовать уверенность в том, что мой инвариант соответствует всем экземплярам типа
Бен Ааронсон,
2
@BenAaronson Неизменность не поможет вам доказать, что вы правильно реализовали свой тип (т. Е. Все операции сохраняют некоторый заданный инвариант). Я хочу сказать, что он позволяет вам распространять факты о значениях. Вы кодируете некоторое условие (например, это число является четным) в типе (проверяя его в конструкторе), и полученное значение является доказательством того, что исходное значение удовлетворяет условию. С изменяемыми объектами вы проверяете текущее состояние и сохраняете результат в логическом значении. Это логическое значение хорошо только до тех пор, пока объект не мутирует, так что условие ложно.
Довал