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

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

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

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

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

История

Эта концепция (хотя и не термин) возникла, по-видимому, у Альфреда Норта Уайтхеда и в «Принципах математики» Бертрана Рассела (1910-13). Она была принята в аналитической философии Уиллардом Ван Орманом Куайном. В книге «Слово и объект» (1960) Куайн дает это определение:

Режим сдерживания φ является ссылочно прозрачным, если всякий раз, когда вхождение сингулярного терма t является чисто ссылочным по термину или предложению ψ (t), оно также чисто ссылочно в содержащем слове или предложении φ (ψ (t)).

Этот термин появился в его современном использовании, при обсуждении переменных в языках программирования, в оригинальном наборе лекций Кристофера Стрэчи «Основные понятия в языках программирования» (1967). В библиографии упоминаются «Слово и объект» Куайна.

Примеры и контрпримеры

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

Рассмотрим функцию, возвращающую данные из какого-либо источника. В псевдокоде вызов этой функции может быть GetInput (Source), где Source может указывать конкретный файл диска, клавиатуру и т. д. Даже при одинаковых значениях Source, последовательные возвращаемые значения будут разными. Таким образом, функция GetInput () не является детерминированной или ссылочно прозрачной.

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

Арифметические операции ссылочно прозрачны: например, 5 * 5 можно заменить на 25. Фактически все функции в математическом смысле являются ссылочно прозрачными: sin (x) является прозрачным, так как он всегда будет давать одинаковый результат для каждого конкретного x.

Присвоения же не прозрачны. Например, выражение на языке Си x = x + 1 изменяет значение, присвоенное переменной x. Предполагая, что x изначально имеет значение 10, два последовательных вычисления выражения дают соответственно 11 и 12. Очевидно, что замена x = x + 1 на 11 или 12 приведёт к тому, что выражение будет иметь различные значения для одного выражения. Поэтому такое выражение не является ссылочно прозрачным. Однако вызов функции, такой как int plusone (int x) {return x + 1;}, является прозрачным, поскольку он не будет неявно изменять входное значение x и, следовательно, не имеет таких побочных эффектов.

Функция today() не является ссылочно прозрачной. Если вычислить эту функцию и заменить её значением (например, «1 января 2001 года»), то завтра, запустив today(), не получить тот же самый результат. Это связано с тем, что выдаваемое функцией значение зависит от состояния (даты).

В языках без побочных эффектов, таких как Haskell, мы можем заменить равенство на равенство, потому что f(x) = f(x) для любого значения x. Но это не относится к языкам с побочными эффектами.

Контраст с императивным программированием

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

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

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

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

Ещё пример

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

int globalValue = 0;
 int rq(int x)
 {
   globalValue++;
   return x + globalValue;
 }
 int rt(int x)
 {
   return x + 1;
 }

Функция rt является ссылочно прозрачной, что означает, что rt(x) = rt(y), если x = y. Например, rt(6) = 6 + 1 = 7, rt(4) = 4 + 1 = 5 и т. д. Однако мы не можем сказать ничего подобного для rq, потому что она использует глобальную переменную, которую модифицирует.

Ссылочная непрозрачность rq затрудняет рассуждение о программах. Например, предположим, что мы хотим объяснить следующее утверждение:

integer p = rq(x) + rq(y) * (rq(x) — rq(x));

Может возникнуть соблазн упростить это утверждение:

integer p = rq(x) + rq(y) * (0);
integer p = rq(x) + 0;
integer p = rq(x);

Однако это не будет работать для rq(), потому что каждое вхождение rq(x) оценивается по другому значению. Помните, что значение, возвращаемое rq, берётся из глобальной переменной, которая не передается и которая изменяется при каждом вызове rq. Это означает, что математические тождества, такие как x - x = 0 {\ displaystyle x-x = 0} x-x = 0, больше не выполняются.

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

Однако для упрощения утверждения можно использовать более сложный анализ:

integer a = globalValue; integer p = x + a + 1 + (y + a + 2) * (x + a + 3 - (x + a + 4)); globalValue = globalValue + 4;
integer a = globalValue; integer p = x + a + 1 + (y + a + 2) * (x + a + 3 - x - a - 4)); globalValue = globalValue + 4;
integer a = globalValue; integer p = x + a + 1 + (y + a + 2) * -1; globalValue = globalValue + 4;
integer a = globalValue; integer p = x + a + 1 - y - a - 2; globalValue = globalValue + 4;
integer p = x - y - 1; globalValue = globalValue + 4;

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

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