Являются ли побочные эффекты всем, что не может быть найдено в чистой функции?

Question

Можно ли с уверенностью сказать, что имеет место следующая дихотомия:

Каждая заданная функция

• либо чистый
• или имеет побочные эффекты

Если это так, побочные эффекты (функции) - это то, что невозможно найти в чистой функции.

Answer 1

Это очень сильно зависит от определений, которые вы выбираете. Справедливо будет сказать, что функция является чистой или нечистой. Чистая функция всегда возвращает один и тот же результат и не изменяет среду. Нечистая функция может возвращать разные результаты при многократном выполнении (что может быть вызвано тем, что что-то делает с окружающей средой).

Являются ли все примеси побочными эффектами? Я бы так не сказал - функция может зависеть от чего-то в той среде, в которой она выполняется. Это может быть чтение какой-либо конфигурации, местоположения GPS или чтение данных из Интернета. Это не совсем "побочные эффекты", потому что это ничего не делает для мира.

Я думаю, что есть два вида примесей:

• Выходная примесь - это когда функция что-то делает с миром. В Haskell это моделируется с помощью монад - нечистой функции a -> b на самом деле функция a -> M b где M захватывает другие вещи, которые он делает с миром.

• Входная примесь - это когда функция требует чего-то из среды. Нечистая функция a -> b можно моделировать как функцию C a -> b где тип C захватывает другие вещи из среды, к которой может получить доступ функция

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

Answer 2

Чтобы функция была чистой, она должна:

1. не подвержены побочным эффектам (т.е. всегда возвращают одно и то же значение для одинаковых аргументов)
2. не вызывает побочных эффектов

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

Answer 3

Я не вижу проблем с определением чистой функции: чистая функция - это функция. Т.е. он имеет домен, кодомен и отображает элементы первого в элементы второго. Это определено на всех входах. Он ничего не делает для среды, потому что "среда" на данный момент не существует: нет машин, которые могут выполнить (для некоторого определения "выполнить") данную функцию. Существует просто полное отображение от чего-то к чему-то.

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

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

Но есть и другие существа: темные обитатели подземного мира. Они похожи на функции, но они осведомлены об окружающей среде и могут взаимодействовать с ней: читать переменные, отправлять сообщения и запускать ракеты. Мы называем этих павших родственников функций "нечистыми" или "эффективными" и избегаем, насколько это возможно, потому что их природа настолько мрачна, что о них невозможно рассуждать.

Таким образом, между этими функциями, которые могут взаимодействовать с внешним миром, и теми, которые этого не делают, явно есть большая разница. Однако определение "снаружи" тоже может варьироваться. State Монада моделируется с использованием только чистых инструментов, но мы думаем о f : Int -> State Int Int как насчет эффективных вычислений. Более того, не прекращение и исключения (error "...") являются эффектами, но Haskellers обычно не считают их так.

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

Answer 4

Способ определения чистоты функции f является ∀x∀y x = y ⇒ f x = f yТ.е. при одном и том же аргументе функция возвращает тот же результат, либо сохраняет равенство.

Это не то, что люди обычно имеют в виду, когда говорят о "чистых функциях"; они обычно означают "чистый", поскольку "не имеет побочных эффектов". Я не понял, как квалифицировать "побочный эффект" (комментарии приветствуются!), Поэтому мне нечего сказать по этому поводу.

Тем не менее, я исследую эту концепцию чистоты, потому что она может предложить некоторое понимание. Я не эксперт здесь; это в основном я просто бродяга. Я, однако, надеюсь, что это вызывает некоторые проницательные (и корректирующие!) Комментарии.

Чтобы понять чистоту, мы должны знать, о каком равенстве мы говорим. Что значит x = y значит, а что значит f x = f y имею в виду?

Одним из вариантов является семантическое равенство Хаскеля. То есть равенство семантики, которое Хаскелл присваивает его терминам. Насколько я знаю, официальной денотационной семантики для Haskell нет, но https://en.wikibooks.org/wiki/Haskell/Denotational_semantics предлагает разумный стандарт, который, я думаю, сообщество более или менее соглашается на специальную. Когда Хаскелл говорит, что его функции чисты, это равенство, к которому он относится.

Другим выбором является пользовательское равенство (т.е. (==)) выводя Eq учебный класс. Это актуально при использовании денотационного дизайна, то есть мы назначаем нашу собственную семантику терминам. С этим выбором мы можем случайно написать функции, которые нечисты; Haskell не имеет отношения к нашей семантике.

Я буду ссылаться на семантическое равенство Хаскеля как = и пользовательское равенство как ==, Также я предполагаю, что == является отношением равенства - это не имеет места для некоторых случаев == например, для Float,

Когда я использую x == y как предложение, что я на самом деле имею в виду x == y = True ∨ x == y = ⊥, так как x == y :: Bool а также ⊥ :: Bool, Другими словами, когда я говорю x == y это правда, я имею в виду, что если он вычисляет что-то другое, чем ⊥, то он вычисляется в True.

Если x а также y равны в соответствии с семантикой Haskell, то они равны в соответствии с любой другой семантикой, которую мы можем выбрать.

Доказательство: если x = y затем x == y ≡ x == x а также x == x это правда, потому что == чисто (согласно =) и рефлексивный.

Точно так же мы можем доказать ∀f∀x∀y x = y ⇒ f x == f y, Если x = y затем f x = f y (так как f чисто) поэтому f x == f y ≡ f x == f x а также f x == f x это правда, потому что == чисто и рефлексивно.

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

data Pair a = Pair a a

instance (Eq a) => Eq (Pair a) where
  Pair x _ == Pair y _ = x == y

swap :: Pair a -> Pair a
swap (Pair x y) = Pair y x

Теперь у нас есть:

Pair 0 1 == Pair 0 2

Но:

swap (Pair 0 1) /= swap (Pair 0 2)

Замечания: ¬(Pair 0 1 = Pair 0 2) поэтому мы не были уверены, что наше определение (==) было бы хорошо.

Более убедительным примером является рассмотрение Data.Set, Если x, y, z :: Set A тогда вы надеетесь, что это так, например:

x == y ⇒ (Set.union z) x == (Set.union z) y

Особенно когда Set.fromList [1,2,3] а также Set.fromList [3,2,1] обозначают одно и то же множество, но, вероятно, имеют разные (скрытые) представления (не эквивалентные семантике Хаскелла). То есть мы хотим быть уверены, что ∀z Set.union z чист в соответствии с (==) за Set,

Вот тип, с которым я играл:

newtype Spry a = Spry [a]

instance (Eq a) => Eq (Spry a) where
  Spry xs == Spry ys = fmap head (group xs) == fmap head (group ys)

Spry это список, который имеет неравные смежные элементы. Примеры:

Spry [] == Spry []
Spry [1,1] == Spry [1]
Spry [1,2,2,2,1,1,2] == Spry [1,2,1,2]

Учитывая это, что является чистой реализацией (согласно == для Spry) для flatten :: Spry (Spry a) -> Spry a такой, что если x является элементом вложенной spry, это также элемент плоской spry (то есть что-то вроде ∀x∀xs∀i x ∈ xs[i] ⇒ x ∈ flatten xs)? Упражнение для читателя.

Также стоит отметить, что функции, о которых мы говорили, находятся в одном домене, поэтому они имеют тип A → A, Это за исключением случаев, когда мы доказали ∀f∀x∀y x = y ⇒ f x == f y который переходит от семантической области Haskell к нашей собственной. Это может быть какой-то гомоморфизм... может быть, теоретик категории мог бы весить здесь (и, пожалуйста, сделайте!).

Answer 5

Побочные эффекты являются частью определения языка. В выражении

f e

побочные эффекты e все части eПоведение, которое "перемещается" и становится частью поведения выражения приложения, а не передается в f как часть стоимости e,

Для конкретного примера рассмотрим эту программу:

f x = x; x
f (print 3)

где концептуально синтаксис x; x означает "запустить x, затем запустить его снова и вернуть результат".

На языке, где print пишет в stdout как побочный эффект, это пишет

3

потому что вывод является частью семантики выражения приложения.

На языке, где вывод print это не побочный эффект, это пишет

3
3

потому что вывод является частью семантики x переменная внутри определения f,