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

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

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

Определяемые пользователями функции имеют несколько свойств, определяющих способность ядра Компонент SQL Server Database Engine индексировать результаты функции как с помощью индексов вычисляемых столбцов, вызывающих функцию, так и с помощью индексированных представлений, которые на нее ссылаются. Детерминизм функции — одно из таких свойств. Например, в представлении нельзя создать кластеризованный индекс, если оно ссылается на какие-либо недетерминированные функции. Дополнительные сведения о свойствах функций, включая детерминизм, см. в разделе Определяемые пользователем функции.

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

Детерминизм встроенных функций

На детерминизм встроенных функций повлиять нельзя. Каждая из них детерминирована или недетерминирована в зависимости от реализации в SQL Server. Например, если вы укажете в запросе предложение ORDER BY, детерминизм функции, используемой в этом запросе, не изменится.

Все встроенные строковые функции являются детерминированными, кроме FORMAT. Список этих функций см. в разделе Строковые функции (Transact-SQL).

Следующие встроенные функции, отличные от строковых функций, всегда детерминированы.

Источник

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

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

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

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

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

Вот описание чистой функции из википедии:

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

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

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

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

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

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

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

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

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

Действительно здорово узнать что-то новое, но еще лучше узнать о том, что ваши знания были неверны.

Источник

Чистые функции — JS: Функции

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

Детерминированность

Встроенная в JavaScript функция Math.random() возвращает случайное число от 0 до 1:

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

Например, недетерминированными являются функции, оперирующие системным временем. Так, функция Date.now() каждый раз возвращает новое значение:

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

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

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

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

Понятие «Детерминированность» не ограничивается программированием или математикой. Сквозь него можно рассматривать практически любой процесс. Например, подбрасывание монетки — недетерминированный процесс, его результат случаен.

Побочные эффекты (side effects)

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

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

А вот вычисления (логика), напротив, не содержат побочных эффектов. Например, функция, суммирующая два переданных аргументами числа.

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

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

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

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

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

Инкремент и декремент — единственные базовые арифметические операции в JS, которые обладают побочными эффектами (изменяют само значение в переменной). Именно поэтому с ними сложно работать в составных выражениях. Они могут приводить к таким сложноотлавливаемым ошибкам, что во многих языках вообще отказались от их введения (в Ruby и Python их нет). В JS стандарты кодирования предписывают их не использовать.

Чистые функции

Идеальная функция с точки зрения удобства работы с ней называется чистой (pure). Чистая функция — это детерминированная функция, которая не производит побочных эффектов. Такая функция зависит только от своих входных аргументов и всегда ведёт себя предсказуемо.

Чистые функции обладают рядом ключевых достоинств:

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.

Источник

Эффекты и чистые функции

Тезис Чёрча — Тьюринга означает (несколько упрощая), что любая компьютерная программа может быть представлена машиной Тьюринга или функцией λ-исчисления, то есть математической функцией. Конечно, это относится и к составляющим программу функциям и процедурам языков программирования.

Но что такое математическая функция?

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

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

В мире чистого программирования нарушения этих свойств принято называть эффектами.

1. Эффект частичности

Если процедура частично определена, то есть не определена для каких-либо значений аргумента, она не возвращает значения для него, или, как говорят математики, не завершается. Погодите-ка! Если она не завершается, то что происходит?

В современных языках программирования процедура может «не завершаться» разными способами:

2. Эффекты недетерменированности (неопределённости)

2.1. Эффект нестабильности

Функция не всегда возвращает одинаковые значения для одного значения аргумента.

Пример: генератор случайных чисел.

2.2. Эффект множественности

Функция возвращает сразу много ответов.

Множественная функция может вернуть и пустое множество результатов, то есть эффект частичности можно рассматривать как частный случай эффекта множественности.

3. Побочный эффект

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

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

Примеры вы сами можете легко привести.

(Иногда говорят об идемпотентных побочных эффектах. Это, несомненно, меньшее зло, чем произвольные побочные эффекты.)

Заключение

Мы рассмотрели основные виды эффектов в математике и программировании.

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

Источник

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

Транскрипт урока

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

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

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

Отвлеклись, давайте — к делу. В программировании детерминированная функция, это функция, которая всегда производит тот же результат при одинаковых вводных данных:

Вам наверное интересно, как ещё может вести себя функция. Недетерминированная функция непредсказуема, её результат зависит от чего-то ещё.

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

Ещё более простой пример — генератор случайных чисел. Обычно в любом языке программирования есть какой-нибудь встроенный способ генерации случайных чисел. В JavaScript он такой:

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

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

Детерминированные функции предсказуемы: они менее хрупкие, о них проще рассуждать и представлять их. Использовать их тоже проще, собирая сложные структуры и программы.

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

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

А ваш хороший друг — функция console.log — имеет: она выводит что-то на экран. Эта штука на экране — определённо что-то за рамками функции, это компьютер, мир в котором живёт функция.

Или рассмотрим следующий код:

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

Чем меньше побочных эффектов имеет функция, тем лучше.

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

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

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

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

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

Если вы смотрели видео, но не выполняли упражнения и тесты — то обязательно сделайте это. Курс рассчитан именно на это, а видео сами по себе — это только часть процесса. Есть большая разница между «кажется, понял» и «умею».

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

Я надеюсь, что программирование станет важной и интересной частью вашей жизни.

Выводы

Детерминированная функция всегда возвращает одинаковое значение при определённом вводе (аргументы).

surfaceAreaCalculator это детерминированная функция.

Недетерминированная функция не всегда будет возвращать одинаковое значение при определённом вводе.

Функция, которая возвращает погоду на данный момент для какой-нибудь координаты — недетерминированная: погода всегда меняется, поэтому мы не можем быть уверены, какой ответ выдаст функция.

Другой пример — генератор случайных чисел:

Побочные эффекты: то, как функция меняет внешний мир.

surfaceAreaCalculator не имеет никаких побочных эффектов. Она ничего не меняет за пределами своих границ.

Функция console.log имеет побочный эффект: она что-то выводит на экран.

То, что функции возвращают, не имеет ничего общего с тем, как они влияют на внешний мир.

Чем меньше побочных эффектов имеет функция, тем лучше.

Когда функция детерминированная и не имеет побочных эффектов, мы называем её «чистой» функцией. Чистые функции:

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

Дополнительные материалы

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты.

Источник