ФП (язык программирования)
| Парадигма | Функциональный уровень |
|---|---|
| Разработано | Джон Бэкус |
| Впервые появился | 1977 |
| Диалекты | |
| ФП84 | |
| Под влиянием | |
| АПЛ [1] | |
| Под влиянием | |
| Флорида , Хаскелл , Джой | |
FP (сокращение от функционального программирования ) [2] — это язык программирования, созданный Джоном Бэкусом для поддержки программирования на уровне функций. [2] парадигма. Он позволяет создавать программы из набора обычно полезных примитивов и избегать именованных переменных (стиль, также называемый неявным программированием или «бесточечным программированием»). На него сильно повлиял APL, разработанный Кеннетом Э. Айверсоном в начале 1960-х годов. [3]
Язык FP был представлен в статье Бэкуса на Премии Тьюринга 1977 года «Можно ли программирование освободиться от стиля фон Неймана?» с подзаголовком «Функциональный стиль и его алгебра программ». Статья вызвала интерес к исследованиям в области функционального программирования. [4] в конечном итоге это привело к созданию современных функциональных языков, которые в значительной степени основаны на парадигме лямбда-исчисления , а не на парадигме функционального уровня, на которую надеялся Бэкус. В своей статье о премии Тьюринга Бэкус описал, чем отличается стиль ФП:
Система ФП основана на использовании фиксированного набора комбинирующих форм, называемых функциональными формами. Это, а также простые определения, являются единственными средствами создания новых функций из существующих; они не используют никаких переменных или правил подстановок и становятся операциями связанной алгебры программ. Все функции системы ФП относятся к одному типу: они отображают объекты на объекты и всегда принимают один аргумент. [2]
Сам по себе FP никогда не находил особого применения за пределами академических кругов. [5] В 1980-х годах Бэкус создал язык-преемник FL в рамках внутреннего проекта IBM Research.
Обзор
[ редактировать ]Значения , которые программы FP отображают друг в друга, составляют набор , замкнутый при формировании последовательности :
if x1,...,xn are values, then the sequence 〈x1,...,xn〉 is also a value
Эти значения могут быть построены из любого набора атомов: логических, целых, действительных, символов и т. д.:
boolean : {T, F}
integer : {0,1,2,...,∞}
character : {'a','b','c',...}
symbol : {x,y,...}
⊥ — неопределенное значение или дно . Последовательности сохраняют нижнюю часть :
〈x1,...,⊥,...,xn〉 = ⊥
Программы FP — это функции f , каждая из которых отображает одно значение x в другое:
f:x represents the value that results from applying the function f
to the value x
Функции либо являются примитивными (т. е. предоставляются средой FP), либо строятся из примитивов с помощью операций формирования программ (также называемых функционалами ).
Примером примитивной функции является константа , которая преобразует значение x в функцию x̄ с постоянным значением . Функции строгие :
f:⊥ = ⊥
Другим примером примитивной функции является семейство функций селектора , обозначаемое 1 , 2 ,... где:
i:〈x1,...,xn〉 = xi if 1 ≤ i ≤ n
= ⊥ otherwise
Функционалы
[ редактировать ]В отличие от примитивных функций, функционалы оперируют другими функциями. Например, некоторые функции имеют единичное значение, например 0 для сложения и 1 для умножения . Функциональный блок выдает такое значение при применении к функции f, которая имеет такое значение:
unit + = 0 unit × = 1 unit foo = ⊥
Вот основные функции FP:
composition f∘g where f∘g:x = f:(g:x)
construction [f1,...,fn] where [f1,...,fn]:x = 〈f1:x,...,fn:x〉
condition (h ⇒ f;g) where (h ⇒ f;g):x = f:x if h:x = T
= g:x if h:x = F
= ⊥ otherwise
apply-to-all αf where αf:〈x1,...,xn〉 = 〈f:x1,...,f:xn〉
insert-right /f where /f:〈x〉 = x
and /f:〈x1,x2,...,xn〉 = f:〈x1,/f:〈x2,...,xn〉〉
and /f:〈 〉 = unit f
insert-left \f where \f:〈x〉 = x
and \f:〈x1,x2,...,xn〉 = f:〈\f:〈x1,...,xn-1〉,xn〉
and \f:〈 〉 = unit f
Эквациональные функции
[ редактировать ]Помимо того, что функция может быть построена из примитивов с помощью функционалов, она может быть определена рекурсивно с помощью уравнения, простейшим из которых является:
f ≡ Ef
где E f — выражение, построенное из примитивов, других определенных функций и самого функционального символа f с использованием функционалов.
ФП84
[ редактировать ]FP84 — это расширение FP, включающее бесконечные последовательности , определяемые программистом формы объединения (аналогичные тем, которые сам Бэкус добавил в FL , его преемника FP) и ленивые вычисления . В отличие от FFP, еще одного из собственных вариантов FP Бэкуса, FP84 проводит четкое различие между объектами и функциями: т.е. последние больше не представляются последовательностями первых. Расширения FP84 достигаются путем удаления ограничения FP, согласно которому построение последовательности применяется только к объектам, отличным от -⊥: в FP84 вся вселенная выражений (включая те, значение которых равно ⊥) закрыта при построении последовательности.
Семантика FP84 воплощена в базовой алгебре программ, наборе равенств функционального уровня , которые можно использовать для манипулирования программами и рассуждений о них.
Ссылки
[ редактировать ]- ^ Концепция, эволюция и применение языков функционального программирования. Архивировано 11 марта 2016 г. в Wayback Machine Пол Худак, 1989 г.
- ^ Перейти обратно: а б с Бэкус, Дж. (1978). «Можно ли программирование освободить от стиля фон Неймана?: Функциональный стиль и его алгебра программ» . Коммуникации АКМ . 21 (8): 613. дои : 10.1145/359576.359579 .
- ^ «Премия А. М. Тьюринга Ассоциации вычислительной техники» (PDF) . [ постоянная мертвая ссылка ]
- ^ Ян, Жан (2017). «Интервью с Саймоном Пейтоном-Джонсом» . Люди языков программирования .
- ^ Хейг, Джеймс (28 декабря 2007 г.). «Археология функционального программирования» . Программирование в XXI веке .
- Жертвовать простотой ради удобства: где провести черту? , Джон Х. Уильямс и Эдвард Л. Виммерс, Исследовательский центр IBM в Альмадене, Материалы пятнадцатого ежегодного симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования, Сан-Диего, Калифорния, январь 1988 г.
Внешние ссылки
[ редактировать ]- FP-интерпретатор, написанный на Delphi/Lazarus
- Дирк Герритс: Лекция на премию Тьюринга (1977–1978) и далее , в книге Джона В. Бэкуса (Публикации)
- FP84 против FL: Жертвовать простотой ради удобства: где провести черту? Дж. Х. Уильям и Э. Л. Виммерс, 1988 г. (страницы 169–179)