Что такое "полное функциональное программирование"?

Wikipedia говорит следующее:

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

и

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

Существует также Lambda The Ultimate Post о документе Общее функциональное программирование.

Я не сталкивался с этим до последней недели в списке рассылки.

Есть ли еще какие-либо ресурсы, ссылки или какие-либо примеры реализации, которые вы знаете?

Ответы

Ответ 1

Если я правильно понял это, Total Functional Programming означает только: Программирование с помощью Total Functions. Если я правильно помню свои математические курсы, функция Total Function является функцией, которая определена во всем домене. Частичная функция - это "дыры" в ее определении.

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

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

Я предполагаю, что это значительно упрощает обработку ошибок: их нет.

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

Ответ 3

Хотя это старый вопрос, я думаю, что ни один из ответов пока не упоминает настоящую мотивацию для полного функционального программирования, а именно:

Если программы являются доказательствами, а доказательства - программами, то программы, которые имеют "дыры", не имеют никакого смысла в качестве доказательств и вводят логическую несогласованность.

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

Также следует отметить, что большинство помощников по доказательству работают, основываясь на этом принципе, Coq, например.