]]> ]]>
Править | Обсудить | История

FP

Дата создания:
1977
Повлиял на:
Парадигма:
Типизация:
Принятые расширения файлов:
.fp
Реализации и версии (свернуть все | развернуть все):
Язык программирования

FP (“Functional Programming”) — алгебраический язык программирования.

FP был изобретен Джоном Бэкусом (John Backus) и опубликован в 1977 году в статье под названием “Can Programming Be Liberated from the von Neumann style? A Functional Style and its Algebra of Programs” (“Возможно ли освободить программирование от стиля фон Неймана? Алгебра программ в функциональном стиле”) . Описание языка, данное в статье, является фактическим стандартом, и дальнейшей стандартизации FP не подвергался.

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

(Следующее описание использует синтаксис языка приведенной по ссылке реализации.)

Как и любой язык программирования, реализующий парадигму программирования на уровне функций, FP состоит из трех групп сущностей:

1. атомы. FP использует следующие типы атомов:

  • скалярные значения. FP работает с числовыми (целыми и с плавающей точкой) и логическими (константами, обозначенными T и F) данными. Некоторые реализации, например, Furry Paws, расширяют язык, включая в него возможности обработки строк как последовательностей кодов символов.
  • последовательности. Последовательность определяется как <x1, ..., xn>, где xi — другие атомы. Следует отметить, что в одной последовательности могут объединяться атомы разных типов; так, <1 <2 5.0> T> — законная последовательность.
  • значение “неопределенность”. То же значение, которое используется в определении строгой и нестрогой парадигм: атом, не имеющий определенного значения, либо еще не вычисленный, либо вычисленный с ошибкой. FP — строгий язык: если аргумент функции или элемент последовательности не определен, то результат вычисления функции или сама последовательность также не определены.

Как и любой язык, действующий на уровне функций, FP позволяет использовать атомы только в качестве входных и выходных значений программы. Если логика программы содержит константу, используется соответствующая функция-константа.

2. функции могут быть элементарными или определенными программистом. В языке FP функции всегда принимают в качестве аргумента ровно один атом, что записывается как f:x. Элементарные функции FP включают следующие:

  • тождество: id:x возвращает x.
  • константа: %x:y возвращает x для любого значения y (некоторые авторы рассматривают % как функциональную форму, но эта операция не принимает функцию в качестве аргумента).
  • математические +,-,*,/: +:<x y> возвращает x+y, если x и y — скалярные значения.
  • выборочная функция (селектор): i:<x1 ... xn> возвращает xi, если 1 <= i <= n.
  • сравнения =,>,<:=:<x y> возвращает T, если x=y, и F в противном случае.
  • ряд векторных и матричных функций: конкатенация, присоединение в начало/конец, циклическая перестановка, транспонирование и т.д.
  • определение функции программистом имеет следующий синтаксис: { functionName ( function code ) }. После определения функция вызывается так же, как элементарные функции.

FP — безопасный с точки зрения типов язык: функция вычисляется только в том случае, если ее аргумент правильного типа.

3. функциональные формы не могут определяться программистом, т.е. используются только формы, встроенные в язык. В отличие от функций, функциональные формы могут принимать несколько аргументов. Список стандартных форм FP включает в себя следующие:

  • составление: [f1, ..., fn]:x эквивалентно <f1:x ... fn:x>.
  • композиция: f @ g:x эквивалентно f:(g:x).
  • условный выбор записывается как ( condition -> trueChoice ; falseChoice ) и применяется к атому x по следующему правилу: сначала вычисляется функция condition:x; если ее результат — T, возвращается trueChoice:x, иначе — falseChoice:x. Все три аргумента условного выбора — функции.
  • применить-ко-всем: @f:<x1 ... xn> эквивалентно <f:x1 ... f:xn>.
  • правая вставка: !f:<x1 x2 ... xn> эквивалентно f:<x1 !f:<x2 ... xn>> (и применяется рекурсивно); !f:<x> эквивалентно x (левая вставка вычисляется аналогично).

Ссылки:

Примеры:

Факториал:

Пример для версий Interactive FP

Этот пример определяет четыре функции — две по необходимости, и две для читабельности. Все они принимают на вход скалярные значения; seq возвращает последовательность скаляров, остальные три — скаляры.

  • zero проверяет, равен ли ее аргумент нулю;
  • dec уменьшает аргумент на единицу;
  • seq возвращает <0>, если ее аргумент x равен нулю, и результат применения seq к (x-1) с присоединенным справа x иначе (если мы развернем это рекурсивное определение, мы получим просто последовательность <0 1 … x>) .
  • factorial возвращает 1, если ее аргумент x равен нулю, и результат применения factorial к (x-1), умноженный на x, иначе.

Последняя строка примера применяет factorial к каждому элементу последовательности, полученной применением seq к входному параметру — 16. Следует отметить, что все матеметические операции возвращают числа с плавающей запятой, поэтому результат выполнения программы будет иметь следующий вид: < 1 1.0 2.0 6.0 24.0 120.0 720.0 5040.0 40320.0 362880.0 3628800.0 3.99168E7 4.790016E8 6.2270208E9 8.7178289E10 1.30767428E12 2.09227885E13 > 

{ zero ( = @ [id, %0] ) }
{ dec ( - @ [id, %1] ) }
{ seq ( zero -> %<0> ; apndr @ [ seq @ dec , id ] ) }
{ factorial ( zero -> %1 ; * @ [id, factorial @ dec ] ) }
&factorial @ seq:16

Числа Фибоначчи:

Пример для версий Interactive FP

Этот пример работает так же, как пример факториала, но без добавления функций для читабельности. 

{ seq ( = @ [id, %1] -> %<1> ; concat @ [ seq @ - @ [id, %1] , [id] ] ) }
{ fibonacci ( < @ [id, %3] -> %1 ; + @ [ fibonacci @ - @ [id, %1], fibonacci @ - @ [id, %2] ] ) }
&fibonacci @ seq:16

Hello, World!:

Пример для версий Furry Paws

~x — функция-константа (обозначенная как % в Interactive FP). emit — стандартная функция, выводящая свой аргумент в стандартный поток вывода. main — функция, наличие которой в программах на Furry Paws обязательно, т.к. при выполнении программы она вызывается первой. 

main = emit.(return ~"Hello, World!\n")

Факториал:

Пример для версий Furry Paws

Этот пример работает точно так же, как пример для Interactive FP, за исключением отсутствия определения функции zero, являющейся встроенной. Следует отметить, что здесь все операции выполняются в пределах стандартного целочисленного типа, и 13! вызывает ошибку переполнения, поэтому программа может быть вызвана только для факториалов до 12!. show — альтернативный способ вывода информации. 

dec = sub.[id, ~1]
seq = zero -> [id] ; cat.[seq.dec, [id]]
factorial = zero -> ~1 ; mul.[id, factorial.dec]

main = show.(return @factorial.(seq.~12))

Числа Фибоначчи:

Пример для версий Furry Paws 
one = eq.[id, ~1]
dec = sub.[id, ~1]
seq = one -> [~1] ; cat.[seq.dec, [id]]
fibonacci = lt.[id, ~3] -> ~1 ; add.[fibonacci.sub.[id, ~1], fibonacci.sub.[id, ~2]]

main = show.(return @fibonacci.(seq.~16))

Комментарии

]]>

blog comments powered by Disqus

]]>

Работа программистам