ФП (язык программирования)

FP (сокращение от функционального программирования ) ^[2] — язык программирования, созданный Джоном Бэкусом для поддержки парадигмы программирования на уровне функций ^[2] . Он позволяет создавать программы из набора общеупотребительных примитивов и избегать именованных переменных (стиль, также называемый неявным программированием или «бесточечным программированием»). На него сильное влияние оказал APL, разработанный Кеннетом Э. Айверсоном в начале 1960-х годов. ^[3]

Язык FP был представлен в статье Бэкуса, удостоенной премии Тьюринга в 1977 году , «Можно ли освободить программирование от стиля фон Неймана?», с подзаголовком «функциональный стиль и его алгебра программ». Статья вызвала интерес к исследованиям в области функционального программирования ^[4] , что в конечном итоге привело к появлению современных функциональных языков, которые в значительной степени основаны на парадигме лямбда-исчисления , а не на парадигме уровня функций, на которую надеялся Бэкус. В своей статье, удостоенной премии Тьюринга, Бэкус описал, чем отличается стиль FP:

Система FP основана на использовании фиксированного набора комбинационных форм, называемых функциональными формами. Они, а также простые определения, являются единственными средствами построения новых функций из существующих; они не используют переменных или правил подстановки и становятся операциями связанной алгебры программ. Все функции системы FP относятся к одному типу: они отображают объекты на объекты и всегда принимают один аргумент. ^[2]

Сам по себе FP никогда не находил широкого применения за пределами академической среды. ^[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

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

Примером примитивной функции является константа , которая преобразует значение x в константную функцию x̄ . Функции являются строгими :

ж : ⊥ = ⊥

Другим примером примитивной функции является семейство селекторных функций, обозначаемое как 1 , 2 ,..., где:

i :〈 x 1 ,..., x n〉 =  x i если 1 ≤ i ≤ n = ⊥ в противном случае

В отличие от примитивных функций, функционалы оперируют другими функциями. Например, некоторые функции имеют единичное значение, например 0 для сложения и 1 для умножения . Функциональная единица производит такое значение при применении к функции f , которая имеет единицу:

единица + = 0 единица × = 1 единица foo = ⊥

Вот основные функции ФП:

композиция  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〉

вставить-справа / 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 с использованием функционалов.

FP84 — это расширение FP, включающее бесконечные последовательности , определяемые программистом комбинирующие формы (аналогичные тем, которые сам Бэкус добавил в FL , его преемника FP), и ленивые вычисления . В отличие от FFP, еще одной собственной вариации Бэкуса на тему FP, FP84 проводит четкое различие между объектами и функциями: т. е. последние больше не представлены последовательностями первых. Расширения FP84 достигаются путем снятия ограничения FP, согласно которому построение последовательности должно применяться только к не -⊥ объектам: в FP84 вся вселенная выражений (включая те, значением которых является ⊥) закрыта относительно построения последовательности.

Семантика FP84 воплощена в базовой алгебре программ — наборе равенств на уровне функций , которые можно использовать для манипулирования программами и рассуждений о них.

• Жертвование простоты ради удобства: где провести черту?, Джон Х. Уильямс и Эдвард Л. Виммерс, Исследовательский центр IBM Almaden, Труды пятнадцатого ежегодного симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования, Сан-Диего, Калифорния, январь 1988 г.

• FP-интерпретатор, написанный на Delphi/Lazarus
• Дирк Герритс: лекция по случаю вручения премии Тьюринга (1977-1978) и далее в книге Джона В. Бэкуса (Публикации)
• FP84 против FL: Жертвоприношение простоты ради удобства: где провести черту? JH William и EL Wimmers, 1988 (страницы 169–179)