Блог

У меня есть этот код

 data Slist a = Empty | Scons (Sexp a) (Slist a) 
data Sexp a = AnAtom a | AnSlist (Slist a)
data Fruit = Peach | Apple | Pear | Lemon | Fig deriving (Show,Eq)

sxOccurs oatm sxp =
  let slOC Empty = 0
      slOC (Scons se sls) = (seOC se)   (slOC sls)
      seOC (AnAtom atm) = if (atm == oatm) then 1 else 0
      seOC (AnSlist sla) = slOC sla
  in seOC sxp
 

Как вы можете видеть, у sxOccurs меня внутри есть две вспомогательные функции let , которые являются «взаимно самореферентными», как их называет мой Маленький MLer: slOC и seOC . Поэтому в SML вы должны использовать ключевое and слово, чтобы сообщить им друг о друге и «перекрестно ссылаться» друг на друга. Кстати, sxOccurs подсчитывает количество конкретных AnAtom объектов в s-списке, в моем примере атомы являются Fruit переменными.

Мой вопрос в том, является ли это примером ссылочной прозрачности? Аналогично, в Дэви он приводит такой пример

 let s0 = emptyStack
    s1 = push 12.2 s0
    s2 = push 7.1 s1
    s3 = push 6.7 s2
    s4 = divStack s3
    s5 = push 4.3 s4
    s6 = subtStack s5
    s7 = multStack s6
    s8 = push 2.2 s7
    s9 = addStack s8
in popStack s9
 

отмечая, что стек в Imperative-land постоянно изменяет стек, в то время как Haskell создает новую si переменную для каждой операции стека. Затем он говорит, что каждую из этих строк можно было бы перетасовать в другом порядке, и результат остался бы неизменным. AFAICT это та же основная идея, что и у меня sxOccurs , когда неважно, в каком порядке я представляю подфункции. Итак, опять же, является ли это более глубоким значением ссылочной прозрачности? Если нет, то что это я здесь показываю?

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

Например, вы пишете:

 slOC Empty = 0
slOC (Scons se sls) = (seOC se)   (slOC sls)
seOC (AnAtom atm) = if (atm == oatm) then 1 else 0
seOC (AnSlist sla) = slOC sla
 

Вот пара преобразований, которые вы могли бы сделать, благодаря ссылочной прозрачности:

 -- replace slOC by its definition
seOC (AnSlist sla) = (v -> case v of Empty -> 0; SCons se sls -> seOC se   slOC sls) sla
-- replace slOC by its definition *again*, starting from the previous line
seOC (AnSlist sla) = (v -> case v of
    Empty -> 0
    SCons se sls -> seOC se   (v -> case v of
        Empty -> 0
        SCons se sls -> seOC se   slOC sls
        ) sls
    ) sla
-- replace slOC by its definition in another equation
slOC (Scons se sls) = seOC se   (v -> case v of Empty -> 0; SCons se sls -> seOC se   slOC sls) sls
-- or, you could replace seOC by its definition instead
slOC (SCons se sls) = (v -> case v of
    AnAtom atm -> if atm == oatm then 1 else 0
    AnSlist sla -> sLOC sla
    ) se   slOC sls
-- or you could do both, of course
 

Ну, конечно, верно? К настоящему времени вы, возможно, думаете: «Но, Дэниел, как это свойство могло когда-либо потерпеть неудачу?». Я кратко перейду к другому языку, чтобы проиллюстрировать: C.

 int *x = malloc(sizeof(*x));
x[0] = 42;
printf("%dn", x[0]);
 

В случае, если вы плохо читаете C , это создает новую переменную с именем x , выделяет для нее некоторое пространство, записывает 42 в это пространство, а затем выводит значение, хранящееся в этом пространстве. (Мы, вероятно, должны ожидать, что он будет напечатан 42 !) Но я определил x = malloc(sizeof(*x)) в первой строке; могу ли я заменить x это определение в другом месте?

Нет! Это совсем другая программа:

 int *x = malloc(sizeof(*x));
malloc(sizeof(*x))[0] = 42;
printf("%dn", x[0]);
 

Это все еще синтаксически корректная программа, но теперь x[0] она не была инициализирована в тот момент, когда мы достигаем строки, которая ее печатает, потому что мы выделили второй, независимый кусок пространства и инициализировали вместо этого другое пространство.

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

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

 global_var = 0

def my_function():
    return global_var

my_function() # 0
global_var = 100
my_function() # 100
 

Мы позвонили my_function с теми же входными данными, но он таинственным образом выдал другой результат. Теперь, конечно, в этом примере очевидно, почему это так, но идея ссылочной прозрачности заключается в том, что в реальном коде это не будет настолько очевидным. Если язык, на котором вы работаете, не имейте ссылочную прозрачность, и действительно, если язык поощряет мутацию стиля действия на расстоянии, то вы неизбежно получите функции, которые обращаются к изменяемому состоянию, о котором вы не знаете. Хорошо написанная функция будет включать обширную документацию об этих угловых случаях, но если вы когда-либо работали с какой-либо базой кода среднего или большего размера, вы знаете, что «хорошо документированная функция» — это редкое зрелище.

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

 myFunction :: IORef Int -> IO Int
myFunction = readIORef
 

Но теперь одна только подпись типа с первого взгляда говорит нам: «здесь происходит что-то подозрительное; покупатель остерегается», и даже тогда мы можем получить доступ только к одной глобальной переменной IORef , к которой она дает нам доступ.

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