Полное функциональное программирование - Total functional programming

Полное функциональное программирование (также известный как сильное функциональное программирование,[1] противопоставляться обычному, или слабый функциональное программирование ) это программирование парадигма, которая ограничивает диапазон программ теми, которые доказуемо прекращение.[2]

Ограничения

Прекращение действия гарантируется следующими ограничениями:

  1. Ограниченная форма рекурсия, который оперирует только "сокращенными" формами его аргументов, такими как Рекурсия Вальтера, субструктурная рекурсия, или "сильно нормализующий", как доказано абстрактная интерпретация кода.[3]
  2. Каждая функция должна быть итоговой (в отличие от частичный ) функция. То есть у него должно быть определение для всего, что находится в его области.
    • Существует несколько возможных способов расширить часто используемые частичные функции, такие как деление, до полного: выбор произвольного результата для входных данных, на которых функция обычно не определена (например, для деления); добавление еще одного аргумента, чтобы указать результат для этих входов; или исключая их с помощью функций системы типов, таких как типы уточнения.[2]

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

Например, быстрая сортировка не является тривиальным показателем субструктурной рекурсии, но он повторяется только до максимальной глубины длины вектора (временная сложность наихудшего случая О (п2)). Реализация быстрой сортировки в списках (которая будет отклонена субструктурной рекурсивной проверкой) использует Haskell:

импорт Data.List (раздел)qsort []       = []qsort [а]      = [а]qsort (а:в качестве)   = позволять (меньший, больше) = раздел (<а) в качестве                 в qsort меньший ++ [а] ++ qsort больше

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

импорт Data.List (раздел)qsort Икс = qsortSub Икс Икс- минимальный случайqsortSub []     в качестве     = в качестве - показывает прекращение- стандартные кейсы qsortqsortSub (л:ls) []     = [] - нерекурсивный, поэтому принятоqsortSub (л:ls) [а]    = [а] - нерекурсивный, поэтому принятоqsortSub (л:ls) (а:в качестве) = позволять (меньший, больше) = раздел (<а) в качестве                            - рекурсивный, но повторяется на ls, который является подструктурой                            - его первый вход.                         в qsortSub ls меньший ++ [а] ++ qsortSub ls больше

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

Еще одним результатом тотального функционального программирования является то, что оба строгая оценка и ленивая оценка приводить к одинаковому поведению в принципе; однако тот или иной вариант может быть предпочтительным (или даже необходимым) по причинам производительности.[4]

В общем функциональном программировании проводится различие между данные и кодата - первый финишный, а последнее потенциально бесконечно. Такие потенциально бесконечные структуры данных используются для таких приложений, как Ввод / вывод. Использование codata влечет за собой использование таких операций, как Corecursion. Однако можно сделать Ввод / вывод в общем функциональном языке программирования (с зависимые типы ) также без кодовых.[5]

Обе Эпиграмма и Благотворительность можно считать полностью функциональными языками программирования, даже если они не работают Тернер уточняет в своей статье. Так можно программировать прямо на простом Система F, в Теория типа Мартина-Лёфа или Расчет конструкций.

Рекомендации

  1. ^ Этот срок обусловлен: Тернер, Д.А. (Декабрь 1995 г.). Элементарное строгое функциональное программирование. Первый международный симпозиум по языкам функционального программирования в образовании. Springer LNCS. 1022. С. 1–13..
  2. ^ а б Тернер, Д.А. (2004-07-28), «Полное функциональное программирование», Журнал универсальных компьютерных наук, 10 (7): 751–768, Дои:10.3217 / jucs-010-07-0751
  3. ^ Тернер, Д.А. (2000-04-28), «Обеспечение завершения в ESFP», Журнал универсальных компьютерных наук, 6 (4): 474–488, Дои:10.3217 / jucs-006-04-0474
  4. ^ Различия между ленивым и нетерпеливым оцениванием обсуждаются в: Гранстрем, Дж. Г. (2011). Трактат по интуиционистской теории типов. Логика, эпистемология и единство науки. 7. ISBN  978-94-007-1735-0. См., В частности, стр. 86–91.
  5. ^ Гранстрем, Дж. Г. (май 2012 г.), «Новая парадигма для разработки на основе компонентов», Журнал программного обеспечения, 7 (5): 1136–1148, Дои:10.4304 / jsw.7.5.1136-1148[мертвая ссылка ] Архивная копия