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

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

Ограничения

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

1. Ограниченная форма рекурсии , которая работает только с «сокращенными» формами своих аргументов, такими как рекурсия Вальтера , субструктурная рекурсия или «сильная нормализация», что доказано абстрактной интерпретацией кода. ^[3]
2. Каждая функция должна быть полной (а не частичной ) функцией. То есть у него должно быть определение всего, что находится в его области.
   • Существует несколько возможных способов расширить часто используемые частичные функции, такие как деление, до итоговых: выбор произвольного результата для входных данных, для которых функция обычно не определена (например, для деления); добавление еще одного аргумента для указания результата для этих входных данных; или исключить их с помощью функций системы типов, таких как уточненные типы . ^[2] ${\displaystyle \forall x\in \mathbb {N} .x\div 0=0}$

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

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

импортировать Data.List ( раздел )  qsort [] = [] qsort [ a ] ​​= [ a ] ​​qsort ( a : as ) = let ( меньше , больше ) = раздел ( < a ) как в qsort lesser ++ [ a ] ​​++ qsort больше                       

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

импортировать Data.List ( раздел )  qsort x = qsortSub x x — минимальный регистр qsortSub [] as = as — показывает завершение — стандартные случаи qsort qsortSub ( l : ls ) [] = [] — нерекурсивный, поэтому принимается qsortSub ( l : ls ) [ a ] = [ a ] — нерекурсивно, поэтому принято qsortSub ( l : ls ) ( a : as ) = ​​let ( lesser , Greater ) = раздел ( < a ) as — рекурсивно, но рекурсивно по ls, которая является подструктурой -- его первый ввод. в qsortSub ls lesser ++ [ a ] ​​++ qsortSub ls больше                                          

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

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

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

И Epigram , и Charity можно считать полностью функциональными языками программирования, хотя они и не работают так, как указывает Тернер в своей статье. То же самое можно сделать и с программированием непосредственно в простой системе F , в теории типов Мартина-Лёфа или в исчислении конструкций .

Смотрите также

• Анализ завершения

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

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