Чистота против ссылочной прозрачности
Термины, кажется, определены по- разному, но я всегда думал о том, что одно подразумевает другое; Я не могу вспомнить ни одного случая, когда выражение является ссылочно прозрачным, но не чистым, или наоборот.
Википедия поддерживает отдельные статьи для этих понятий и говорит:
Если все функции, участвующие в выражении, являются чистыми функциями, то выражение является ссылочно прозрачным. Кроме того, некоторые нечистые функции могут быть включены в выражение, если их значения отбрасываются и их побочные эффекты незначительны.
Из чистых выражений:
Чистые функции необходимы для построения чистых выражений. [...] Чистые выражения часто называют ссылочно-прозрачными.
Я нахожу эти утверждения запутанными. Если побочные эффекты от так называемой "нечистой функции" достаточно незначительны, чтобы позволить их не выполнять (т. Е. Заменить вызов такой функции ее значением) без существенного изменения программы, то это так же, как если бы оно было чисто в первое место, не так ли?
Есть ли более простой способ понять разницу между чистым выражением и ссылочно-прозрачным, если оно есть? Если есть разница, пример выражения, которое ясно демонстрирует это, будет принят.
7 ответов
Если я соберу в одном месте каких-то трех теоретиков моего знакомого, то по крайней мере двое из них не согласятся со значением термина "ссылочная прозрачность". И когда я был молодым студентом, мой наставник дал мне документ, объясняющий, что, даже если вы рассматриваете только профессиональную литературу, фраза "ссылочно-прозрачный" используется для обозначения как минимум трех разных вещей. (К сожалению, эта бумага находится где-то в коробке перепечаток, которые еще предстоит отсканировать. Я искал ее в Google Scholar, но безуспешно.)
Я не могу сообщить вам, но я могу посоветовать вам сдаться: поскольку даже крошечные кадры теоретиков с острым языком не могут договориться о том, что это значит, термин "референтно прозрачный" бесполезен. Так что не используйте это.
PS В любой теме, связанной с семантикой языков программирования, Википедия ненадежна. Я бросил пытаться исправить это; процесс в Википедии, похоже, учитывает изменения и популярное голосование за стабильность и точность.
Все чистые функции обязательно ссылочно прозрачны. Поскольку по определению они не могут получить доступ ни к чему, кроме того, что им передано, их результат должен быть полностью определен их аргументами.
Тем не менее, возможно иметь ссылочно прозрачные функции, которые не являются чистыми. Я могу написать функцию, которая дается int iзатем генерирует случайное число r, вычитает r от себя и помещает его в sзатем возвращается i - s, Очевидно, что эта функция нечиста, потому что она генерирует случайные числа. Тем не менее, это ссылочный прозрачный. В этом случае пример глупый и надуманный. Однако, например, в Haskell, id функция имеет тип a - > a тогда как мой stupidId функция будет иметь тип a -> IO a показывая, что он использует побочные эффекты. Когда программист может с помощью внешнего доказательства гарантировать, что его функция фактически прозрачна, то он может использовать unsafePerformIO раздеть IO отойти от типа.
Я несколько не уверен в ответе, который я даю здесь, но наверняка кто-то укажет нам направление.:-)
"Чистота" обычно считается означающей "отсутствие побочных эффектов". Выражение называется чистым, если в его оценке отсутствуют побочные эффекты. Каков побочный эффект тогда? В чисто функциональном языке побочный эффект - это все, что не идет по простому бета-правилу (правило, которое оценивает применение функции, аналогично замене фактического параметра для всех свободных вхождений формального параметра).
Например, в функциональном языке с линейными (или уникальными, это различие не должно беспокоить в данный момент) типами допускается некоторая (контролируемая) мутация.
Поэтому я думаю, что мы выяснили, что такое "чистота" и "побочные эффекты".
Прозрачность ссылок (в соответствии с цитированной вами статьей в Википедии) означает, что переменная может быть заменена выражением, которое она обозначает (сокращенно, расшифровывается), без изменения смысла имеющейся программы (кстати, это также сложный вопрос, и Я не буду пытаться сделать это здесь). Таким образом, "чистота" и "ссылочная прозрачность" - это действительно разные вещи: "чистота" - это свойство некоторого выражения, что примерно означает "не вызывает побочных эффектов при выполнении", тогда как "ссылочная прозрачность" - это свойство, относящееся к переменной и выражению, которое это означает и означает, что "переменная может быть заменена тем, что она обозначает".
Надеюсь, это поможет.
Чистые функции — это те, которые возвращают одно и то же значение при каждом вызове и не имеют побочных эффектов.
Ссылочная прозрачность означает, что вы можете заменить связанную переменную ее значением и получить тот же результат.
И чисто, и ссылочно прозрачно:
def f1(x):
t1 = 3 * x
t2 = 6
return t1 + t2
Почему это чисто?
Потому что это функция только ввода и не имеет побочных эффектов.
Почему это ссылочно прозрачно?
Вы можете заменить и на их соответствующие правые стороны в
returnзаявление следующим образом
def f2(x):
return 3 * x + 6
а также
f2всегда будет возвращать тот же результат, что и в каждом случае.
Чисто, но не ссылочно прозрачно:
Давайте изменим следующим образом:
def f3(x):
t1 = 3 * x
t2 = 6
x = 10
return t1 + t2
Давайте попробуем тот же трюк еще раз, заменив
t1а также
t2с их правыми сторонами, и посмотрите, является ли это эквивалентным определением .
def f4(x):
x = 10
return 3 * x + 6
Мы можем легко заметить, что и не эквивалентны при замене переменных их правыми частями/значениями.
f3(1)вернется
9а также
f4(1)вернется
36.
Ссылочно прозрачный, но не чистый :
Простое изменение
f1чтобы получить нелокальное значение , следующим образом:
def f5:
global x
t1 = 3 * x
t2 = 6
return t1 + t2
Выполнение того же упражнения на замену, что и раньше, показывает, что
f5по-прежнему ссылочно прозрачен. Однако он не является чистым, поскольку не является функцией только переданных ему аргументов.
Внимательно наблюдая, причина, по которой мы теряем ссылочную прозрачность при переходе от
f3к
f4в том, что
xизменен. В общем случае, делая переменную
final(или те, кто знаком со Scala, используя
valс вместо
vars), а использование неизменяемых объектов может помочь сохранить ссылочную прозрачность функции. Это делает их более похожими на переменные в алгебраическом или математическом смысле и, таким образом, лучше поддается формальной проверке.
Начнем с вопроса: чист ли этот фрагмент Haskell?
next :: IORef Int -> IO Int
next r = do i <- readIORef v
writeIORef (i + 1)
return i
расточный ответ: мы не знаем , - монадический тип и его ассортимент примитивов, FFI звонков, соавт которые считаются абстрактными .
Альтернативный ответ: да - это просто совокупность неактивных действий. Эти действия могут произойти только [ законно ], если они вызваны из, но к тому времени, когда это произойдет, (и впоследствии) будут семантически вне Haskell.
Так что насчет этого фрагмента Haskell:
next :: STRef Int -> IO Int
next r = do i <- readSTRef v
writeSTRef (i + 1)
return i
Допускается ли альтернативный ответ?
- модифицированный ответ: [...] - это просто композиция неактивных
IOmain :: IO ()но к тому времени, когда это произойдет,main(и впоследствии)[?!] будет семантически вне Haskell.
...что, если
next является частью
ST действие, вызванное
runST :: (forall s . ST s a) -> a ...?
t = runST $ runX
runX = do ...
i <- next v
...
Этот альтернативный ответ здесь не сработает - никогда семантически не «выходит наружу». Если оценивается, то
next :: STRef Int -> ST Int - и все эффекты, на которые он опирается - будут происходить «внутри Haskell».
Если «чистота» означает «отсутствие эффектов» («побочные эффекты» или иначе!), Тогда это нечистота.
Но мы все еще можем использовать рассуждения по уравнениям:
t + 2*t^2
а также:
let x = t in x + 2*x^2
были бы эквивалентными выражениями - ссылочная прозрачность сохраняется.
Итак, чистота и ссылочная прозрачность разные:
чистота: свойство выражения не использует эффекты;
ссылочная прозрачность: свойство, что выражение всегда имеет одно и то же значение в одной и той же среде.
Несмотря на все это, не ждите, что сайт Haskell будет обновлен в ближайшее время - механизм оценки Haskell на самом деле нестрогий, но термин « ленивый » сохраняется ...
... вы не уверены? Хорошо, рассмотрим простой примитив, например, для добавления значений:
primPlusInt :: Int -> Int -> Int
Давайте поразмышляем, как будут оцениваться:
- если еще не оценен, тогда оцените и перезапишите его результат;
- если еще не оценен, тогда оцените и перезапишите его результат;
- Извлеките примитивное значение (типа
Int#в GHC) изx; - Извлеките примитивное значение из
y; - Заменить неиспользуемую область памяти (или регистр ЦП) примитивным результатом сложения двух примитивных значений из шагов 3 и 4;
- Перезаписать приложение
primPlusInt x yс финальным (Int) результат, используя примитивный результат из шага 5.
... по крайней мере четыре назначения перезаписи - их будет больше, если будут выполнены оценки на шагах 1 и 2, не говоря уже о возможности сборки мусора, планирования потоков и т. д.
runX, все эти эффекты происходят «внутри Haskell». Это неизбежное следствие запуска программы - функциональной или иной - поверх механизма, который изначально основан на изменяемом состоянии.
Но - прямо как
t ранее -
primPlusInt[ при правильной реализации ] также является ссылочно прозрачным.
Эти слайды из одного выступления ACCU2015 содержат большое резюме по теме прозрачности ссылок.
С одного из слайдов:
Язык является ссылочно прозрачным, если (a) каждое подвыражение может быть заменено любым другим, равным ему по значению, и (b) все вхождения выражения в данном контексте дают одно и то же значение.
Например, у вас может быть функция, которая записывает свои вычисления в стандартный вывод программы (так что она не будет чистой функцией), но вы можете заменить вызовы этой функции аналогичной функцией, которая не регистрирует ее вычисления., Следовательно, эта функция имеет свойство ссылочной прозрачности. Но... приведенное выше определение касается языков, а не выражений, как подчеркивают слайды.
[...] это так же, как если бы оно было чистым, не так ли?
Из определений у нас нет, нет.
Есть ли более простой способ понять разницу между чистым выражением и ссылочно-прозрачным, если оно есть?
Попробуйте слайды, которые я упомянул выше.
Я процитирую то, что Джон Митчелл написал в своей книге " Концепция языка программирования". Я не помню это построчно, но он определяет, что чистый функциональный язык должен пройти декларативный языковой тест, который:
"В рамках определенного замедления x1,...,xn все вхождения выражения e, содержащего только переменные x1,...,xn, имеют одинаковое значение".
Короче говоря, все остальные упоминали, что не имеют побочных эффектов или не имеют побочных эффектов ("Отсутствие побочных эффектов").
В лингвистике имя или именная фраза считаются референтно прозрачными, если их можно заменить другой именной фразой с тем же референтом, не меняя смысла предложения, которое оно содержит.
Что в 1-м случае имеет место, но во 2-м случае становится слишком странным.
Случай 1: "Я видел, как Уолтер садился в свою новую машину".
И если у Уолтера есть Centro, то мы можем заменить это в данном предложении следующим образом:
"Я видел, как Уолтер вошел в свой центр"
Вопреки первому:
Случай № 2: Его звали Уильям Руфус из-за его прочитанной бороды.
Руфус означает "немного красный", и речь шла об Уильяме IV из Англии.
"Его звали Уильям IV из-за его прочитанной бороды". выглядит слишком неловко
Традиционный способ сказать, что язык является ссылочно прозрачным, если мы можем заменить одно выражение другим равным значением в любом месте программы, не меняя смысла программы.
Таким образом, ссылочная прозрачность является свойством чисто функционального языка. И если ваша программа свободна от побочных эффектов, то это свойство сохранится.
Так что откажитесь от этого - это отличный совет, но в этом контексте он также может хорошо выглядеть.