Может ли чистая функция иметь свободные переменные?

Например, ссылочно-прозрачная функция без свободных переменных:

g op x y = x `op` y

А теперь теперь функция со свободным (с точки зрения f) переменные op а также x:

x = 1
op = (+)
f y = x `op` y

f также ссылочно прозрачно. Но это чистая функция?

Если это не чистая функция, как называется функция, которая является прозрачной по ссылкам, но использует 1 или более переменных, ограниченных в пределах объема?

Мотивация на этот вопрос:

Мне не понятно из статьи в Википедии:

Значение результата не обязательно зависит от всех (или любых) значений аргумента. Однако это не должно зависеть ни от чего, кроме значений аргумента.

(акцент мой)

ни от поисков Google, может ли чистая функция зависеть от свободных (в смысле ограничения в рамках объема, а не ограничения в пределах объема функции) переменных.

Также в этой книге говорится:

Если функции без свободных переменных являются чистыми, являются ли замыкания нечистыми?

Функция function (y) { return x } Интересно. Он содержит свободную переменную х. Свободная переменная - это переменная, которая не связана внутри функции. До сих пор мы видели только один способ "связать" переменную, а именно, передав аргумент с тем же именем. Так как функция function (y) { return x } не имеет аргумента с именем x, переменная x не связана в этой функции, что делает ее "свободной".

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

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

Итак, каково определение "чистой функции"?

Источник

3 ответа

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

Но давайте углубимся и посмотрим, станет ли это более понятным.

Ссылочная прозрачность

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

New York is an American city.

из которых мы сделали дыру

_ is an American city.

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

Чтобы было ясно, два фрагмента с одинаковыми ссылками, которые мы можем выбрать, будут "Нью-Йорк" и "Большое яблоко". Вставляя эти фрагменты мы пишем

New York is an American city.
The Big Apple is an American city.

предлагая, что

_ is an American city.

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

"The Big Apple" is an apple-themed epithet referring to New York.

и рассмотреть контекст

"_" is an apple-themed epithet referring to New York.

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

"The Big Apple" is an apple-themed epithet referring to New York.
"New York" is an apple-themed epithet referring to New York.

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

Синтаксис v Семантика

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

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

let x = 3 in _

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

\x -> x + 3         --    similar to the context "_ + 3"

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

(\x -> x + 3) 5 
==> 
5 + 3
==> 
8

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

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

x + 3

на самом деле синтаксическая ошибка, так как x просто неизвестен, не связан, и мы не можем рассматривать его семантику как программу на Haskell. Во-вторых, само понятие переменной, которая может быть let(и рассмотрим разницу между "переменным", так как он относится к "слоту", такому как IORef) является полностью синтаксической конструкцией - невозможно даже говорить о них из семантики программы на Haskell.

Итак, давайте уточним вопрос так:

Может ли выражение, содержащее свободные переменные, быть (синтаксически) ссылочно-прозрачным?

и ответ, неинтересно, нет. Ссылочная прозрачность является свойством "контекстов", а не выражений. Итак, давайте вместо этого рассмотрим понятие свободных переменных в контекстах.

Свободные переменные контексты

Как контекст может иметь значимую свободную переменную? Это может быть рядом с дырой

E1 ... x ... _ ... E2

и до тех пор, пока мы не можем вставить что-то в эту синтаксическую дыру, которая "протягивается" и влияет x синтаксически, тогда мы в порядке. Так, например, если мы заполним эту дыру чем-то вроде

E1 ... x ... let x = 3 in E ... E2

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

do x <- foo
   let x = 3
   _
   return x

Теперь мы видим, что дыра, которую мы предоставили, в некотором смысле доминирует над более поздней фразой "return x"На самом деле, если мы вставим фрагмент как"let x = 4"тогда это действительно меняет смысл целого. В этом смысле синтаксис здесь не является ссылочно прозрачным.

Другое интересное взаимодействие между ссылочной прозрачностью и свободными переменными - это понятие присваивающего контекста, такого как

let x = 3 in _

где, с внешней точки зрения, обе фразыx" а также "y"являются ссылкой на то же самое, некоторые именованные переменные, но

let x = 3 in x   ==/==  let x = 3 in y

Прогресс от тернии вокруг равенства и контекста

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

foo >>= \x -> (let x = 3 in ____(return x)_____)

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

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

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

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

чистота

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

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

trivial :: a -> ()
trivial x = x `seq` ()

где у нас есть trivial функция для любого выбора a, Мы отметим конкретный выбор, используя подчеркивание

trivial_Int :: Int -> ()
trivial_Int x = x `seq` ()

Теперь мы можем определить (очень строго) чистую функцию как функцию f :: a -> b такой, что

trivial_b . f = trivial_a

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

Опять же, нет понятия чистоты без значений на Haskell и понятия на значениях Haskell, когда ваши выражения содержат свободные переменные (так как это синтаксическая ошибка).

Так каков ответ?

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

Наконец, чистота - это нечто даже более строгое, чем ссылочная прозрачность, связанная даже с характеристиками сокращения ваших (ссылочно прозрачных) лямбда-терминов.

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

Источник

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

Когда мы смотрим на

increment n = 1+n

это очевидно. Возможно, это не было упомянуто, потому что это так очевидно.

Теперь хитрость в Haskell заключается в том, что не только значения и функции верхнего уровня являются константами, но внутри замыкания также закрываются переменные (!):

add x = (\y -> x+y)

Вот x обозначает значение, которое мы применили add чтобы - мы называем это переменной не потому, что она может измениться в правой части add, но потому что он может отличаться каждый раз, когда мы применяем add, И все же, с точки зрения лямбды, x постоянная

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

Источник

Короткий ответ - ДА, f - чистый

В хаскеле map определяется с foldr, Согласитесь ли вы, что map работает? Если это так, имеет ли значение, что он имеет глобальную функцию foldr это не было предоставлено map в качестве аргумента?

В mapfoldr является свободной переменной. В этом нет сомнений. Не имеет значения, что это функция или что-то, что оценивает значение. Это то же самое.

Свободные переменные, такие как функции foldl а также +, необходимы для существования функциональных языков. Без этого у вас не было бы абстракции, и языки были бы хуже, чем Фортран.

Источник
Другие вопросы по тегам