Побочные эффекты, нарушающие ссылочную прозрачность

11

Функциональное программирование в Scala объясняет влияние побочного эффекта на нарушение прозрачности ссылок:

побочный эффект, который подразумевает некоторое нарушение ссылочной прозрачности.

Я прочитал часть SICP , в которой обсуждается использование «модели замещения» для оценки программы.

Поскольку я примерно понимаю модель замещения с ссылочной прозрачностью (RT), вы можете разложить функцию на ее простейшие части. Если выражение RT, вы можете декомпозировать выражение и всегда получать один и тот же результат.

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

Пример:

val x = foo(50) + bar(10)

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

Я чувствую себя комфортно с этим объяснением, но я не совсем понимаю.

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

Кевин Мередит
источник

Ответы:

20

Давайте начнем с определения ссылочной прозрачности :

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

Это означает, что (например) вы можете заменить 2 + 5 на 7 в любой части программы, и программа все равно должна работать. Этот процесс называется заменой. Подстановка действительна тогда и только тогда, когда 2 + 5 можно заменить на 7, не затрагивая любую другую часть программы .

Допустим, у меня есть класс Bazс именами Fooи функциями Bar. Для простоты мы просто скажем это Fooи Barоба вернем значение, которое передано. Итак Foo(2) + Bar(5) == 7, как и следовало ожидать. Ссылочная прозрачность гарантирует, что вы можете заменить выражение Foo(2) + Bar(5)на 7любое место в вашей программе, и программа все равно будет функционировать идентично.

Но что если Fooвернуть возвращенное значение, но Barвернуть переданное значение плюс последнее предоставленное значение Foo? Это достаточно легко сделать, если вы храните значение Fooв локальной переменной внутри Bazкласса. Хорошо, если начальное значение этой локальной переменной равно 0, выражение Foo(2) + Bar(5)вернет ожидаемое значение при 7первом его вызове, но вернет 9второй раз, когда вы его вызываете.

Это нарушает ссылочную прозрачность двумя способами. Во-первых, нельзя рассчитывать на то, что Bar будет возвращать одно и то же выражение при каждом вызове. Во-вторых, возник побочный эффект, а именно, что вызов Foo влияет на возвращаемое значение Bar. Поскольку вы больше не можете гарантировать, что Foo(2) + Bar(5)будет равно 7, вы больше не можете заменить.

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

Роберт Харви
источник
5
Таким образом, взлом RTотключает вас от использования substitution model.. Большая проблема с невозможностью использования substitution model- это сила использования его для рассуждения о программе?
Кевин Мередит
Это точно верно.
Роберт Харви
1
+1 чудесно понятный и понятный ответ. Спасибо.
Рашит
2
Также, если эти функции прозрачны или «чисты», порядок, в котором они фактически выполняются, не важен, нам не важно, выполняются ли сначала foo () или bar (), и в некоторых случаях они могут никогда не оценить, если они не нужны.
Захари К
1
Еще одним преимуществом RT является то, что дорогие ссылочно-прозрачные выражения могут быть кэшированы (поскольку их оценка один или два раза должна давать точно такой же результат).
dcastro
3

Представьте, что вы пытаетесь построить стену, и вам дали ассортимент коробок разных размеров и форм. Вам необходимо заполнить определенное L-образное отверстие в стене; Вы должны искать L-образную коробку или можете заменить две прямые коробки соответствующего размера?

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

В императивном мире опасно строить свою стену, не осматривая содержимое каждой коробки и сравнивая их с содержимым каждой другой коробки:

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

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

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

На императивном языке вы никогда не знаете, какие сюрпризы могут скрываться внутри.

itsbruce
источник
«На чистом функциональном языке все, что вам нужно, это подпись функции, чтобы знать, что она делает». - Это обычно не так. Да, исходя из предположения о параметрическом полиморфизме, мы можем заключить, что функция типа (a, b) -> aможет быть только fstфункцией, а функция типа a -> aможет быть только identityфункцией, но вы не можете ничего сказать, например, о функции типа (a, a) -> a.
Jörg W Mittag
2

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

Да, интуиция совершенно права. Вот несколько указателей, чтобы получить более точную информацию:

Как вы сказали, любое выражение RT должно иметь single«результат». То есть, учитывая factorial(5)выражение в программе, оно всегда должно давать один и тот же «результат». Таким образом, если определенное число factorial(5)находится в программе и оно дает 120, оно всегда должно давать 120 независимо от того, какой «порядок шагов» он расширяет / вычисляет - независимо от времени .

Пример: factorialфункция.

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

Есть несколько соображений с этим объяснением.

Прежде всего, имейте в виду, что разные модели оценки (см. Аппликативный и нормальный порядок) могут давать разные «результаты» для одного и того же выражения RT.

def first(y, z):
  return y

def second(x):
  return second(x)

first(2, second(3)) # result depends on eval. model

В приведенном выше коде, firstи secondявляются референциально прозрачными, и тем не менее, выражение в конце дает разные «результаты» , если оценены при нормальном порядке и аппликативном порядке ( в соответствии с последним, выражение не останавливается).

.... что приводит к использованию "результата" в кавычках. Поскольку для остановки выражения не требуется, оно может не давать значения. Таким образом, использование «результата» довольно размыто. Можно сказать, что выражение RT всегда дает то же самое computationsпри модели оценки.

В-третьих, может потребоваться, чтобы два приложения foo(50)появлялись в программе в разных местах как разные выражения - каждое из них давало свои собственные результаты, которые могли бы отличаться друг от друга. Например, если язык допускает динамическую область видимости, оба выражения, хотя и лексически идентичные, различны. В Perl:

sub foo {
    my $x = shift;
    return $x + $y; # y is dynamic scope var
}

sub a {
    local $y = 10;
    return &foo(50); # expanded to 60
}

sub b {
    local $y = 20;
    return &foo(50); # expanded to 70
}

Динамический охват вводит в заблуждение, потому что он позволяет легко думать, что xэто единственный вход для foo, когда в действительности это так xи есть y. Один из способов увидеть разницу состоит в том, чтобы преобразовать программу в эквивалентную без динамической области видимости - то есть, передавая явно параметры, поэтому вместо определения foo(x)мы определяем foo(x, y)и передаем yявно в вызывающих программах.

Дело в том, что мы всегда находимся в functionмышлении: учитывая определенный вклад в выражение, нам дают соответствующий «результат». Если мы даем один и тот же вклад, мы всегда должны ожидать один и тот же «результат».

А как насчет следующего кода?

def foo():
   global y
   y = y + 1
   return y

y = 10
foo() # yields 11
foo() # yields 12

fooПроцедура ломает RT , потому что есть переопределения. То есть, мы определили yв одной точке, а затем переопределили то же самое y . В приведенном выше примере perl, ys - это разные привязки, хотя они имеют одно и то же буквенное имя «y». Здесь yс на самом деле то же самое. Вот почему мы говорим, что (пере) присваивание является мета- операцией: вы фактически меняете определение своей программы.

Грубо говоря, люди обычно изображают разницу следующим образом: в установке без побочных эффектов у вас есть отображение input -> output. В «императивной» обстановке у вас есть input -> ouputконтекст, stateкоторый может меняться со временем.

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

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

Тиаго Сильва
источник
1
Приятно, что вы упомянули памятку. Это можно использовать в качестве примера внутреннего состояния, которое не видно снаружи: функция, использующая мемоизацию, по-прежнему прозрачна по ссылкам, даже если внутренне она использует состояние и мутацию.
Джорджио