Чисто функциональное программирование
В информатике — чисто функциональное программирование обычно обозначает парадигму программирования стиль построения структуры и элементов компьютерных программ, — который рассматривает все вычисления как оценку математических функций .
Состояние программы и изменяемые объекты обычно моделируются с помощью темпоральной логики как явные переменные, которые представляют состояние программы на каждом этапе ее выполнения: состояние переменной передается в качестве входного параметра функции преобразования состояния, которая возвращает обновленное состояние как часть его возвращаемого значения. Этот стиль обрабатывает изменения состояния без потери ссылочной прозрачности программных выражений.
Чисто функциональное программирование заключается в обеспечении того, чтобы функции внутри функциональной парадигмы зависели только от своих аргументов, независимо от любого глобального или локального состояния. Чисто функциональная подпрограмма имеет видимость только изменений состояния, представленных переменными состояния, включенными в ее область действия.
Разница между чистым и нечистым функциональным программированием [ править ]
Точная разница между чистым и нечистым функциональным программированием является предметом споров. Предложенное Сабри определение чистоты заключается в том, что все распространенные стратегии оценки (вызов по имени, вызов по значению и вызов по необходимости) дают один и тот же результат, игнорируя стратегии, которые ошибочны или расходятся. [1]
Программу обычно называют функциональной, если она использует некоторые концепции функционального программирования , такие как функции первого класса и функции высшего порядка . [2] Однако функция первого класса не обязательно должна быть чисто функциональной, поскольку она может использовать методы императивной парадигмы , такие как массивы или методы ввода-вывода , использующие изменяемые ячейки, которые обновляют свое состояние в качестве побочных эффектов. Фактически, самые ранние языки программирования, которые считались функциональными, — IPL и Lisp . [3] [4] оба являются «нечистыми» функциональными языками по определению Сабри.
Свойства чисто функционального программирования [ править ]
Строгая и нестрогая оценка [ править ]
Каждая стратегия оценки , заканчивающаяся чисто функциональной программой, возвращает один и тот же результат. В частности, это гарантирует, что программисту не придется учитывать, в каком порядке оцениваются программы, поскольку нетерпеливая оценка вернет тот же результат, что и ленивая оценка . Однако все же возможно, что нетерпеливая оценка может не завершиться, пока останавливается ленивая оценка той же программы. Преимущество этого состоит в том, что ленивые вычисления можно реализовать гораздо проще; поскольку все выражения будут возвращать один и тот же результат в любой момент (независимо от состояния программы), их вычисление может быть отложено настолько, насколько это необходимо.
Параллельные вычисления [ править ]
В чисто функциональном языке единственные зависимости между вычислениями — это зависимости данных, а вычисления являются детерминированными. Следовательно, для параллельного программирования программисту нужно только указать части, которые должны вычисляться параллельно, а среда выполнения может обрабатывать все остальные детали, такие как распределение задач по процессорам, управление синхронизацией и связью, а также параллельную сборку мусора. Этот стиль программирования позволяет избежать распространенных проблем, таких как состояния гонки и взаимоблокировки, но имеет меньший контроль, чем императивный язык. [5]
Чтобы обеспечить ускорение, необходимо тщательно выбирать степень детализации задач, чтобы она не была ни слишком большой, ни слишком маленькой. Теоретически можно использовать профилирование во время выполнения и анализ во время компиляции, чтобы определить, ускорит ли введение параллелизма программу и, таким образом, автоматически распараллелит чисто функциональные программы. На практике это не принесло особого успеха, и полностью автоматическое распараллеливание — несбыточная мечта. [5]
Структуры данных [ править ]
Чисто функциональные структуры данных являются постоянными . Для функционального программирования требуется настойчивость; без него одно и то же вычисление могло бы возвращать разные результаты. Функциональное программирование может использовать постоянные нечисто функциональные структуры данных , в то время как эти структуры данных не могут использоваться в чисто функциональных программах.
Чисто функциональные структуры данных часто представляются иначе, чем их императивные аналоги. [6] Например, массив с постоянным доступом и обновлением является базовым компонентом большинства императивных языков, а многие императивные структуры данных, такие как хеш-таблица и двоичная куча , основаны на массивах. Массивы можно заменить картой или списком произвольного доступа , что допускает чисто функциональную реализацию, но время доступа и обновления является логарифмическим . Следовательно, чисто функциональные структуры данных могут использоваться в нефункциональных языках, но они могут быть не самым эффективным доступным инструментом, особенно если не требуется постоянство.
В общем, преобразование императивной программы в чисто функциональную также требует обеспечения того, чтобы ранее изменяемые структуры теперь явно возвращались из функций, которые их обновляют, - программная структура, называемая стилем передачи данных .
Чисто функциональный язык [ править ]
Чисто функциональный язык — это язык, который допускает только чисто функциональное программирование. Однако чисто функциональные программы могут быть написаны на языках, которые не являются чисто функциональными.
Ссылки [ править ]
- ^ Сабри, Амр (январь 1993 г.). «Что такое чисто функциональный язык?». Журнал функционального программирования . 8 (1): 1–22. CiteSeerX 10.1.1.27.7800 . дои : 10.1017/S0956796897002943 . S2CID 30595712 .
- ^ Атенсио, Луис (18 июня 2016 г.). Функциональное программирование на Javascript . Публикации Мэннинга. ISBN 978-1617292828 .
- ^ Мемуары Герберта А. Саймона (1991), Модели моей жизни, стр. 189-190. ISBN 0-465-04640-1 утверждает, что он, Эл Ньюэлл и Клифф Шоу «обычно считаются родителями [поля] искусственного интеллекта» за написание Logic Theorist , программы, которая доказывала теоремы из Principia Mathematica. автоматически. Чтобы добиться этого, им пришлось изобрести язык и парадигму, которые, если смотреть ретроспективно, включают в себя функциональное программирование.
- ^ Маккарти, Джон (июнь 1978 г.). «История Лиспа» . В конференции ACM SIGPLAN по истории языков программирования : 217–223. дои : 10.1145/800025.808387 .
- ^ Перейти обратно: а б Марлоу, Саймон (18 июня 2013 г.). Параллельное и параллельное программирование на Haskell: методы многоядерного и многопоточного программирования . О'Рейли Медиа. стр. 5–6. ISBN 978-1449335946 .
- ^ Чисто функциональные структуры данных Криса Окасаки , Cambridge University Press , 1998, ISBN 0-521-66350-4