FP (сокращение от функционального программирования ) [2] - это язык программирования, созданный Джоном Бэкусом для поддержки парадигмы программирования на уровне функций [2] . Он позволяет создавать программы из набора обычно полезных примитивов и избегать именованных переменных (стиль, также называемый неявным программированием или «без точек»). На него сильно повлиял APL, разработанный Кеннетом Айверсоном в начале 1960-х годов. [3]
Парадигма | Функциональный уровень |
---|---|
Разработано | Джон Бэкус |
Впервые появился | 1977 г. |
Диалекты | |
FP84 | |
Под влиянием | |
APL [1] | |
Под влиянием | |
FL , Haskell |
Язык FP был представлен в статье Бэкуса о премии Тьюринга 1977 года «Можно ли освободить программирование от стиля фон Неймана?» С подзаголовком «Функциональный стиль и его алгебра программ». Статья вызвала интерес к исследованиям функционального программирования [4], что в конечном итоге привело к созданию современных функциональных языков (которые в значительной степени основаны на парадигме лямбда-исчисления ), а не парадигме функционального уровня, на которую надеялся Бэкус. В своей статье о премии Тьюринга Бэкус описал, чем отличается стиль FP:
Система FP основана на использовании фиксированного набора комбинированных форм, называемых функциональными формами. Они, плюс простые определения, являются единственным средством создания новых функций из существующих; в них не используются переменные или правила подстановки, и они становятся операциями связанной алгебры программ. Все функции системы FP относятся к одному типу: они отображают объекты на объекты и всегда принимают один аргумент. [2]
Сама ФП никогда не находила большого применения вне академических кругов. [5] В 1980-х годах Бэкус создал следующий язык, FL , который был внутренним проектом IBM Research.
Обзор
Эти значения , что программы FP карты друг в друга содержать набор , который закрывается при формировании последовательности :
если x 1 , ..., x n - значения , то последовательность〈x 1 , ..., x n〉 также является значением
Эти значения могут быть построены из любого набора атомов: логических, целых, вещественных, символов и т. Д .:
логическое : { T , F } целое : {0,1,2, ..., ∞} символ : {'a', 'b', 'c', ...} символ : { x , y , .. .}
⊥ - неопределенное значение или дно . Последовательности сохраняющие дно :
〈X 1 , ..., ⊥ , ..., x n〉 = ⊥
Программы FP - это функции f , каждая из которых отображает одно значение x в другое:
f : x представляет значение , полученное в результате применения функции f к значению x
Функции либо примитивны (т. Е. Предоставляются в среде FP), либо построены из примитивов с помощью операций формирования программ (также называемых функционалами ).
Примером примитивной функции является константа , которая преобразует значение x в постоянную функцию x̄ . Функции строгие :
е : ⊥ = ⊥
Другим примером примитивной функции является семейство селекторных функций, обозначенное цифрами 1 , 2 , ..., где:
i : 〈 x 1 , ..., x n〉 = x i, если 1 ≤ i ≤ n = ⊥ иначе
Функционалы
В отличие от примитивных функций, функционалы работают с другими функциями. Например, некоторые функции имеют единичное значение, такое как 0 для сложения и 1 для умножения . Функциональная единица выдает такое значение при применении к функции f, которая имеет одно:
единица + = 0 единица × = 1 единица foo = ⊥
Вот основные функции FP:
композиция f ∘ g, где f ∘ g : x = f :( g : x )
конструкция [ f 1 , ..., f n ], где [ f 1 , ..., f n ]: x = 〈f 1 : x , ..., f n : x〉
условие ( h ⇒ f ; g ) где ( h ⇒ f ; g ): x = f : x, если h : x = T = g : x, если h : x = F = ⊥, в противном случае
применимо ко всем α f, где α f : 〈x 1 , ..., x n〉 = 〈f : x 1 , ..., f : x n〉
insert-right / f, где / f : 〈x〉 = x и / f : 〈x 1 , x 2 , ..., x n〉 = f : 〈x 1 , / f : 〈x 2 , ..., x n〉〉 и / f : 〈〉 = unit f
insert-left \ f, где \ f : 〈x〉 = x и \ f : 〈x 1 , x 2 , ..., x n〉 = f : 〈\ f : 〈x 1 , ..., x n- 1〉, x n〉 и \ f : 〈〉 = unit f
Уравнительные функции
Помимо построения из примитивов функционалами, функция может быть определена рекурсивно с помощью уравнения, самый простой вид:
f ≡ E f
где E f - выражение, построенное из примитивов, других определенных функций и самого символа функции f с использованием функционалов.
FP84
FP84 - это расширение FP, включающее бесконечные последовательности , определяемые программистом формы комбинирования (аналогичные тем, которые сам Бэкус добавил в FL , его преемник FP) и ленивое вычисление . В отличие от FFP, другой собственной вариации Бэкуса на FP, FP84 проводит четкое различие между объектами и функциями: т. Е. Последние больше не представлены последовательностями первых. Расширения FP84 в достигаются путем удаления ограничения FP , что строительство последовательности применяются только к не являющимся -⊥ объектов: в FP84 всю вселенной выражений ( в том числе тех , смысл которых ⊥) является замкнутым относительно строительства последовательности.
Семантика FP84 воплощена в базовой алгебре программ, в наборе равенств на уровне функций, которые можно использовать для управления программами и рассуждений о них.
Рекомендации
- ^ Концепция, эволюция и применение функционального программирования Языки архивации 2016-03-11 в Вайбак Machine Paul Hudák, 1989
- ^ a b c Backus, J. (1978). «Можно ли освободить программирование от стиля фон Неймана ?: Функциональный стиль и его алгебра программ» . Коммуникации ACM . 21 (8): 613. DOI : 10,1145 / 359576,359579 .
- ^ "Ассоциация вычислительной техники Премия AM Тьюринга" (PDF) .
- ^ Ян, Жан (2017). «Интервью с Саймоном Пейтон-Джонсом» . Люди языков программирования .
- ^ Гаага, Джеймс (28 декабря 2007 г.). «Археология функционального программирования» . Программирование в двадцать первом веке .
- Жертвуя простотой ради удобства: где провести черту? , Джон Х. Уильямс и Эдвард Л. Виммерс, Исследовательский центр IBM в Алмадене, Материалы пятнадцатого ежегодного симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования, Сан-Диего, Калифорния, январь 1988 г.
Внешние ссылки
- Интерактивный FP (требуется Java), страница справки
- FP trivia (немецкий)