Войти
Ссылочная прозрачность и ссылочная прозрачность являются свойствами частей компьютерных программ. Выражение называется ссылочно прозрачным, если его можно заменить соответствующим значением (и наоборот) без изменения поведения программы. Для этого требуется, чтобы выражение было чистым, то есть значение выражения должно быть одинаковым для тех же входных данных, и его оценка не должна иметь побочных эффектов . Выражение, которое не является ссылочно прозрачным, называется ссылочно непрозрачным.
В математике все приложения функций референциально прозрачны по определению того, что составляет математическая функция. Однако это не всегда так в программировании, где термины процедура и метод используются, чтобы избежать вводящей в заблуждение коннотации. В функциональном программировании рассматриваются только ссылочно прозрачные функции. Некоторые языки программирования предоставляют средства, гарантирующие ссылочную прозрачность. Некоторые языки функционального программирования обеспечивают ссылочную прозрачность для всех функций.
Важность ссылочной прозрачности заключается в том, что она позволяет программисту и компилятору рассуждать о поведении программы как перезаписываемой системе. Это может помочь в доказательстве правильности, упрощении алгоритма, помощи в изменении кода без его нарушения или оптимизации кода с помощью мемоизации, исключение общего подвыражения, ленивое вычисление или распараллеливание.
Эта концепция, похоже, возникла у Альфреда Норта Уайтхеда и Principia Mathematica Бертрана Рассела (1910–13). Он был принят в аналитической философии Уиллардом Ван Орманом Куайном. В §30 статьи Word and Object (1960) Куайн дает следующее определение:
Способ включения φ является ссылочно прозрачным, если всякий раз, когда вхождение единичного термина t является чисто ссылочным в термине или предложении ψ (t), он является чисто референциальным и в содержащем его члене или предложении φ (ψ (t)).
Термин появился в его современном использовании в информатике, при обсуждении переменных в языках программирования, в оригинальном наборе лекций Кристофера Стрейчи. Основные понятия языков программирования (1967). В примечаниях к лекциям в библиографии есть ссылки на Слово и объект Куайна.
Если все функции, участвующие в выражении, являются чистыми функциями, то выражение является ссылочно прозрачным.
Рассмотрим функцию, которая возвращает ввод из некоторого источника. В псевдокоде вызов этой функции может иметь вид GetInput (Source), где Sourceможет идентифицировать конкретный дисковый файл, keyboard и т. Д. Даже с идентичными значениями Источник, последовательные возвращаемые значения будут другими. Следовательно, функция GetInput ()не является ни детерминированной, ни ссылочно прозрачной.
Более тонкий пример - функция, которая имеет свободную переменную, т.е. зависит от некоторого ввода, который не передается явно в качестве параметра. Затем это разрешается в соответствии с правилами привязки имен к нелокальной переменной, такой как глобальная переменная, переменная в текущей среде выполнения (для динамическая привязка ) или переменная в закрытии (для статической привязки). Поскольку эту переменную можно изменить без изменения значений, переданных в качестве параметра, результаты последующих вызовов функции могут отличаться, даже если параметры идентичны. Однако в чистом функциональном программировании, деструктивное присваивание не допускается, и, таким образом, если свободная переменная статически привязана к значению, функция по-прежнему является ссылочно прозрачной, поскольку ни одна из ни локальная переменная, ни ее значение не могут измениться из-за статической привязки и неизменности соответственно.
Арифметические операции референциально прозрачны: например, 5 * 5можно заменить на 25. Фактически, все функции в математическом смысле прозрачны по ссылкам: sin (x)прозрачен, поскольку он всегда будет давать одинаковый результат для каждого конкретного x.
. Переназначения непрозрачны. Например, выражение C x = x + 1изменяет значение, присвоенное переменной x. Предполагая, что xизначально имеет значение 10, две последовательные оценки выражения дают соответственно 11и 12. Очевидно, что замена x = x + 1на 11или 12дает программу с другим значением, и поэтому выражение не является ссылочно прозрачным. Однако вызов такой функции, как int plusone (int x) {return x + 1; }является прозрачным, поскольку он не будет неявно изменять входной x и, следовательно, не имеет таких побочных эффектов ..
today ()непрозрачно, как если бы вы оценили его и заменили его значением (скажем, «1 января 2001 г.»), вы не получите того же результата, что и, если запустите его завтра. Это потому, что это зависит от состояния (дата).
В языках без побочных эффектов, таких как Haskell, мы можем заменить равными равными: т.е. если x == y, то f (x) == f (y). Это свойство также известно как неотличимые идентичные. Такие свойства не обязательно должны соблюдаться для языков с побочными эффектами. Даже в этом случае важно ограничить такие утверждения так называемым оценочным равенством, то есть равенством терминов, проверенных системой, не включая определяемую пользователем эквивалентность для типов. Например, если B f (A x)и тип Aпереопределил понятие равенства, например если все члены равны, то можно иметь x == yи все же найти f (x)! = f (y). Это связано с тем, что такие системы, как Haskell, не проверяют, что функции, определенные в типах с определяемыми пользователем отношениями эквивалентности, четко определены в отношении этой эквивалентности. Таким образом, ссылочная прозрачность ограничивается типами без отношений эквивалентности. Расширение ссылочной прозрачности до определяемых пользователем отношений эквивалентности может быть выполнено, например, с типом идентичности Мартина-Лофа, но требует системы с зависимым типом, такой как в Agda, Coq или Идрис.
Если замена выражения на его значение действительна только в определенный момент выполнения программы, то выражение не является ссылочно прозрачным. Определение и порядок этих точек последовательности являются теоретической основой императивного программирования и частью семантики императивного языка программирования.
Однако, поскольку ссылочно прозрачное выражение может быть вычислено в любое время, нет необходимости определять точки последовательности и вообще нет никакой гарантии порядка оценки. Программирование, выполняемое без этих соображений, называется чисто функциональным программированием.
Одно из преимуществ написания кода в ссылочно прозрачном стиле состоит в том, что при наличии интеллектуального компилятора статический анализ кода проще и лучше код -улучшающие преобразования возможны автоматически. Например, при программировании на C будет снижение производительности за включение вызова дорогостоящей функции внутри цикла, даже если вызов функции может быть перемещен за пределы цикла без изменения результатов программы. Программист был бы вынужден выполнять ручное перемещение кода вызова, возможно, за счет читабельности исходного кода. Однако, если компилятор может определить, что вызов функции является ссылочно прозрачным, он может выполнить это преобразование автоматически.
Основным недостатком языков, обеспечивающих ссылочную прозрачность, является то, что они делают выражение операций, которое естественным образом соответствует императивному стилю программирования последовательности шагов, более неудобным и менее кратким. Такие языки часто включают механизмы, облегчающие эти задачи, сохраняя при этом чисто функциональные качества языка, такие как грамматики с определенными предложениями и монады.
В качестве примера, давайте воспользуемся двумя функциями, одна из которых является ссылочно прозрачной, а другая - ссылочной непрозрачной:
int g = 0; int rt (int x) {вернуть x + 1; } int ro (int x) {g ++; вернуть x + g; }Функция rtссылочно прозрачна, что означает, что если x == y, то rt (x) == rt (y). Например, rt (6) = 7. Однако мы не можем сказать ничего подобного для ro, потому что он использует глобальную переменную, которую он изменяет.
Ссылочная непрозрачность roзатрудняет рассуждение о программах. Например, допустим, мы хотим рассуждать о следующем утверждении:
int i = ro (x) + ro (y) * (ro (x) - ro (x));
Может возникнуть соблазн упростить это утверждение до:
int i = ro (x) + ro (y) * 0; int я = ро (х) + 0; int я = ро (х);
Однако это не сработает для ro, поскольку каждое вхождение ro (x)оценивается как другое значение. Помните, что возвращаемое значение roосновано на глобальном значении, которое не передается и которое изменяется при каждом вызове ro. Это означает, что математические тождества, такие как x - x = 0, больше не выполняются.
Такие математические тождества будут выполняться для ссылочно прозрачных функций, таких как rt.
. Однако можно использовать более сложный анализ, чтобы упростить оператор до:
int tmp = g; int я = х + tmp + 1 + (y + tmp + 2) * (x + tmp + 3 - (x + tmp + 4)); г = г + 4; int tmp = g; int i = x + tmp + 1 + (y + tmp + 2) * (x + tmp + 3 - x - tmp - 4)); г = г + 4; int tmp = g; int я = х + tmp + 1 + (y + tmp + 2) * (-1); г = г + 4; int tmp = g; int i = x + tmp + 1 - y - tmp - 2; г = г + 4; int я = х - у - 1; г = г + 4;
Это требует большего количества шагов и степени понимания кода, невозможного для оптимизации компилятора.
Таким образом, ссылочная прозрачность позволяет нам рассуждать о нашем коде, что приведет к созданию более надежных программ, возможности обнаружения ошибок, которые мы не могли надеяться найти путем тестирования, и возможности увидеть возможности для оптимизация.
