вторник, 19 марта 2013 г.

Функциональная чистота и ссылочная прозрачность


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

Что касается "функциональной чистоты", то с нею более-менее понятно: результат зависит только от входных параметров, и функция не производит внешних побочных эффектов в том смысле, что не изменяет состояние окружающего мира. Для статически типизированных языков это обычно означает, что все, что функция делает и производит, описано в ее сигнатуре. Тут я изучал самые разные источники, включая учебники по Common Lisp, Haskell, F# и Scala. Трактовка везде примерно такая, почему-то за исключением одного русскоязычного учебника (не буду называть).

Для определенности возьмем такую вариацию этих терминов из еще невышедшей книги "Functional Programming in Scala":

"An expression e is referentially transparent if for all programs p, all occurrences of e in p can be replaced by the result of evaluating e, without affecting the observable behavior of p. A function f is pure if the expression f(x) is referentially transparent for all referentially transparent x."

Здесь содержатся одно из возможных определений для ссылочной прозрачности и вывод о том, что если выражение f(x) ccылочно-прозрачно для всех ссылочно-прозрачных x, то функция f является чистой. Определение чистоты в книге дается обычное в другом месте. Меня смущает то, что хотя используется слово "if" в последнем предложении, трактуется оно почему-то как "if and only if".

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

Второе. У меня складывается ощущение, что ссылочная прозрачность жестко привязана к конкретному языку программирования, тогда как свойство функции быть чистой является в большой степени над-языковым. Припоминая ассемблер PDP-11, сдается мне, что даже на уровне ассемблера можно оперировать чистотой, если ввести определенные допущения для стека (или стеков). Это так? Если да, то тогда оба понятия действительно не могут быть эквивалентными уже по этому.

В общем, прошу вразумить и поставить на путь истинный.

1 комментарий:

  1. Я прочитал "A function f is pure if the expression f(x) is referentially transparent for all referentially transparent x." как определение чистой функции. То есть, "если выражение f(x) прозрачно для всех прозрачных х, то функцию f _называют_ чистой"

    Если Вам всё ещё интересен этот вопрос, предлагаю начать обсуждение с http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.7800

    ОтветитьУдалить