ФП (язык программирования)
Парадигма | Функциональный уровень |
---|---|
Разработано | Джон Бэкус |
Впервые появился | 1977 |
Диалекты | |
ФП84 | |
Под влиянием | |
АПЛ [1] | |
Под влиянием | |
Флорида , Хаскелл , Джой |
FP (сокращение от функционального программирования ) [2] — это язык программирования , созданный Джоном Бэкусом для поддержки программирования на уровне функций. [2] парадигма. Он позволяет создавать программы из набора обычно полезных примитивов и избегать именованных переменных (стиль, также называемый неявным программированием или «бесточечным программированием»). На него сильно повлиял APL , разработанный Кеннетом Э. Айверсоном в начале 1960-х годов. [3]
Язык FP был представлен в статье Бэкуса на Премии Тьюринга 1977 года «Можно ли программирование освободиться от стиля фон Неймана?» с подзаголовком «Функциональный стиль и его алгебра программ». Статья вызвала интерес к исследованиям в области функционального программирования. [4] в конечном итоге это привело к созданию современных функциональных языков, которые в значительной степени основаны на парадигме лямбда-исчисления , а не на парадигме функционального уровня, на которую надеялся Бэкус. В своей статье о премии Тьюринга Бэкус описал, чем отличается стиль ФП:
Система ФП основана на использовании фиксированного набора комбинирующих форм, называемых функциональными формами. Это, а также простые определения, являются единственными средствами создания новых функций из существующих; они не используют никаких переменных или правил подстановок и становятся операциями связанной алгебры программ. Все функции системы ФП относятся к одному типу: они отображают объекты на объекты и всегда принимают один аргумент. [2]
Сам по себе FP никогда не находил особого применения за пределами академических кругов. [5] В 1980-х годах Бэкус создал язык-преемник FL в рамках внутреннего проекта IBM Research.
Обзор [ править ]
Значения , которые программы FP отображают друг в друга, составляют набор при , замкнутый формировании последовательности :
если x 1 ,..., x n являются значениями , то последовательность 〈 x 1 ,..., x n 〉 также является значением
Эти значения могут быть построены из любого набора атомов: логических, целых, действительных, символов и т. д.:
логическое значение : { Т , F } целое число : {0,1,2,...,∞} символ : {'a','b','c',...} символ : { х , у ,...}
⊥ — неопределенное значение или дно . Последовательности сохраняют нижнюю часть :
〈 x 1 ,..., ⊥ ,..., x n 〉 = ⊥
Программы FP — это функции f , каждая из которых отображает одно значение x в другое:
f : x представляет значение , полученное в результате применения функции f до значения х
Функции либо являются примитивными (т. е. предоставляются средой FP), либо строятся из примитивов с помощью операций формирования программы (также называемых функционалами ).
Примером примитивной функции является константа , которая преобразует значение x в функцию x̄ с постоянным значением . Функции строгие :
ж : ⊥ = ⊥
Другим примером примитивной функции является семейство функций селектора , обозначаемое 1 , 2 ,... где:
я :〈 x 1 ,..., x n 〉 = x i , если 1 ≤ i ≤ n = ⊥ иначе
Функционалы [ править ]
В отличие от примитивных функций, функционалы оперируют другими функциями. Например, некоторые функции имеют единичное значение, например 0 для сложения и 1 для умножения . Функциональный блок выдает такое значение при применении к функции f , которая имеет такое значение:
единица + = 0 единица × = 1 единица фу = ⊥
Вот основные функции FP:
композиция f ∘ g где f ∘ g : x = f :( g : x )
конструкция [ f 1 ,..., f n ] где [ f 1 ,..., f n ]: x = 〈 f 1 : x ,..., f n : x 〉
условие ( час ⇒ ж ; г ) где ( час ⇒ ж ; г ): Икс знак равно ж : Икс если час : Икс знак равно Т = г : х , если ч : х = F = ⊥ иначе
применим ко всем α f где α f :〈 x 1 ,..., x n 〉 = 〈 f : x 1 ,..., f : x n 〉
вставить вправо / f где / f :〈 x 〉 = x и / f :〈 x 1 , x 2 ,..., x n 〉 = f :〈 x 1 ,/ f :〈 x 2 ,..., x n 〉〉 и / f :〈 〉 = единица f
вставить слева \ f где \ f :〈 x 〉 = x и \ f :〈 x 1 , x 2 ,..., x n 〉 = f :〈\ f :〈 x 1 ,..., x n-1 〉, x n 〉 и \ f :〈 〉 = единица f
Эквациональные функции [ править ]
Помимо того, что функция может быть построена из примитивов с помощью функционалов, она может быть определена рекурсивно с помощью уравнения, простейшим из которых является:
ж ≡ Е ж
где 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)