Чистые и детерминированные функции

Перевод статьи Джастина Этеридж (Justin Etheredge), в которой автор объясняет тонкую разницу между детерминированными и чистыми функциями.

Вчера я читал блог Мэтта Подвизоки (Matt Podwysocki) (этот блог, кстати, потрясающий, идите и подпишитесь), и у него есть пост «Recursing into Recursion – Memoization». Отличный пост, если вы хотите познакомиться с мемоизацией. У меня уже был пост об обобщенной функции мемоизации некоторое время назад, поэтому мы будем говорить не о мемоизации. То, что возбудило во мне интерес, было в конце статьи Мэтта:

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


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


Вот описание чистой функции из википедии:
  1. Функция всегда вычисляет одинаковое результирующее значение для одних и тех же наборов аргументов. Результирующее значение функции не может зависеть от любой скрытой информации или состояния, которое может изменяться по мере выполнения программы, не может зависеть от любых внешних входных данных от устройств ввода/вывода.
  2. Вычисление результата не должно вызывать любые семантически наблюдаемые побочные эффекты, такие как мутацию изменяемых объектов, или вывод в устройства ввода/вывода.

А вот определение детерминированного алгоритма Национальным Институтом стандартов и технологий (США):

Алгоритм, поведение которого можно полностью предсказать по входным данным.

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

Например:

Детерминированная и чистая:

public int Add(int val1, int val2)
{
	return val1 + val2;
}


Детерминированная, но не чистая:

public int Add(int val1, int val2)
{
	Console.WriteLine(val1 + " " + val2);
	return val1 + val2;
}


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

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

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

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

Действительно здорово узнать что-то новое, но еще лучше узнать о том, что ваши знания были неверны.
Поделиться публикацией
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама
Комментарии 16
  • +3
    Чистые функции, хороши тем, что их можно вычислять в любом порядке(или вообще не вычислять, если не надо). Ваши же «детерминированные фунции» требуют строгого и последовательного вычисления, иначе в консоли вместо «Hello, world!» появится «world! Hello,» или вообще «world!».
    • 0
      То есть, любая чистая функция ассоциативна?
      • +12
        Меня, видимо, неправильно поняли. Я говорю, что если у нас есть несколько вызовов чистых функций, то их можно выполнить в любом порядке, т.е., например, при вычислении
        SomeFunction(Clean1(arg1), Clean2(arg2), Clean3(arg3));
        

        Если функции Clean1..3 чистые, ты мы сначала можем вычислить Clean2(arg2), потом Clean3(arg3), а Clean1(arg1) вообще не вычислять, т.к. в SomeFunction это значение не понадобилось. А если Clean1..3 печатают что-то в консоль, то может получиться «world! Hello,».
      • 0
        Скорее, коммутативна.
    • 0
      По мере возможности пвытаюсь делать функции чистыми, однако это не всегда возможно, должны же быть функции, клоторые выводят данные в какой-то поток, или берут их из него. По мпте.матическому определению функия никак не взаимодействует с внешним миром. Все остальные «функции», насколько я знаю, называются процедураами.

      Но я ттак и не понял почему автор ошибался, разьве что не совсем точно дал опре, деление.
      • 0
        Ссори за опечатки, впервые пишу с сесорной клавиатуры.
      • +1
        Я не пишу это в личку, потому что следующее утверждение — вопрос на обсуждение.

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


        В оригинале звучит так: «Детерминированные фунуции также могут не использовать внешнее состояние, т.к. это может влиять на их выполнение. Но большинство определений детерминированных функций просто утверждает, что вы можете определить их результат на основе входных данных».
        • 0
          То есть, по определению, детерминированная функция может сколько угодно использовать состояние, если оно не влияет на возвращаемый результат. В переводе же детерминированная функция фактически приравнивается к чистой.
        • +12
          И это все?
          • +2
            Функция вывода на консоль не будет детерминированной. Взять к примеру случай, когда консоль вдруг становится недоступна (а такое бывает, если например это какое-то терминальное устройство) и мы получаем исключение. В случае «нечистых» функций таких «если», может быть порядочно, чтобы с уверенностью заявить, что функции не являются детерминированными.
            • +3
              В соответствии с подобными рассуждениями ни одна функция не может считаться детерминированной, поскольку всегда есть вероятность того, что закончится память или сыграют роль еще какие-нибудь внешние по отношению к функции факторы. Дело в том, что понятие «чистота» относится к функции как к программной реализации алгоритма, а понятие детерминированности к самому алгоритму.
            • +2
              «Подвизоки»… Подвысоцкий же!
              • 0
                Здесь он сам себя представляет, можете ознакомиться.
              • 0
                А мне вот не совсем понятно, как быть с логированием. С одной стороны -= оно что-то куда-то пишет. А с другой — никак не влияет на логику работы системы. Я, конечно, понимаю что бага в коде логирования может вызвать падение всей системы, но то же самое можно сказать о любом методе, который мы вызываем.
                • 0
                  Подозреваю что функция с журналированием — детерминированная, но не чистая. Чистая функция — это нечто вроде чёрного ящика — вход-выход и ничего более.

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.