Полное функциональное программирование
-
Определение тотального функционального программирования
- Тотальное функциональное программирование ограничивает программы доказуемо завершаемыми.
-
Ограничения тотального функционального программирования
- Ограниченная форма рекурсии, включая рекурсию Вальтера и субструктурную рекурсию.
- Использование различных методов для обработки неопределенных входных данных, таких как выбор произвольного результата или исключение их.
- Не является полным по Тьюрингу, но поддерживает широкий спектр алгоритмов.
-
Примеры алгоритмов и их преобразование
- Алгоритмы с асимптотическими границами могут быть преобразованы в доказуемо завершающие функции.
- Быстрая сортировка является примером алгоритма, который может быть реализован с ограничениями по глубине рекурсии.
-
Различия в оценке и использование codata
- Строгая и ленивая оценка приводят к одинаковому поведению, но могут быть предпочтительны по производительности.
- Различие между данными и кодированными данными, где первые конечны, а вторые потенциально бесконечны.
-
Примеры функциональных языков программирования
- Epigram и Charity могут считаться полноценными функциональными языками, несмотря на различия в реализации.
- Программирование возможно в простых системах F, системах типов Мартина-Лефа и математическом анализе конструкций.
Полный текст статьи: