FP
 Appeared in:
 1977
 Influenced:
 Paradigm:
 Typing discipline:
 File extensions:
 .fp
 Versions and implementations (Collapse all  Expand all):
FP (“Functional Programming”) is an algebraic programming language.
FP was invented by John Backus and presented in 1977 in a paper called “Can Programming Be Liberated from the von Neumann style? A Functional Style and its Algebra of Programs”. The language description given in this paper is the de facto standard of the language.
FP was designed as a model of language to support functionlevel programming style. It was intended to be more of a math model than of an actual language, and so it was. It is a canonical example of a language implementing functionlevel programming paradigm, but it has only a few implementations which differ quite a lot, and none of them is used in reallife development. However, the concept of FP had strong influence on development of other functional languages.
Most implementations use essentially different language syntax. The following description uses language notation taken from Interactive FP implementation.
As any functionlevel programming language, FP consists of three groups of entities:
1. atoms. FP uses the following types of atoms:
 scalar values. FP is designed to process numerical (both integer and floatingpoint) and logical (denoted as T and F) data. Some implementations, like Furry Paws, extend the language to allow processing strings as sequences of character codes.

sequences. A sequence is defined as
<x_{1}, ..., x_{n}>
, where x_{i} are another atoms. Note that atoms of different types can be intermixed in one sequence, so<1 <2 5.0> T>
is a valid sequence. 
undefined value. This is the
undefined
used in definition of strict and nonstrict paradigms: an atom which has no specific value, either because it has not been evaluated yet or because its evaluation has ended in an error. FP is strict language: all its functions and sequences are undefinedpreserving, i.e., if function argument or one of elements in sequence isundefined
, the return of the function or the sequence itself isundefined
as well.
As any functionlevel language, FP allows the use of atoms only as input and output values of the program. If program logic requires using a constant, a corresponding constantvalue function is used.
2. functions can be primitive or userdefined. FP functions always take one atom as argument, which is written as f:x
. The list of primitive functions includes:

identity:
id:x
evaluates tox
. 
constantvalue:
%x:y
evaluates tox
for any value ofy
(some authors consider % to be a functional form, but it doesn’t have a functiontype argument). 
math +,,*,/:
+:<x y>
evaluates tox+y
, if x and y are scalar values. 
selector:
i:<x_{1} ... x_{n}>
evaluates tox_{i}
, if i is between 1 and n, inclusive. 
comparison =,>,<:
=:<x y>
evaluates to T, if x=y, and to F otherwise.  a variety of vector and matrix functions, like concatenate, append, rotate, transpose etc.

userdefined functions have the following syntax:
{ functionName ( function code ) }
. After a function is defined, it can be called in a same way as primitive functions are.
FP is typesafe: the function is evaluated only if its arguments are of correct types.
3. functional forms can not be userdefined. Unlike functions, forms can have multiple arguments. The list of standard forms includes:

construction:
[f_{1}, ..., f_{n}]:x
evaluates to<f_{1}:x ... f_{n}:x>
. 
composition:
f @ g:x
evaluates tof:(g:x)
. 
conditional choice is written as
( condition > trueChoice ; falseChoice )
and applies to a value x using the following rules: first,condition:x
is evaluated; if it results in T value,trueChoice:x
is evaluated and returned, otherwisefalseChoice:x
is returned. All three arguments of conditional are functions. 
applytoall:
@f:<x_{1} ... x_{n}>
evaluates to<f:x_{1} ... f:x_{n}>
. 
right insert:
!f:<x_{1} x_{2} ... x_{n}>
evaluates tof:<x_{1} !f:<x_{2} ... x_{n}>>
and is applied recursively;
!f:<x>
evaluates tox
(left insert is defined in a similar way).
Elements of syntax:
Inline comments  % 

Examples:
Factorial:
Example for versions Interactive FPThis example defines four functions — two of necessity, and two for readability. All of them accept scalar values for input; seq
returns a sequence of scalars, and the other three return individual scalars.

zero
checks whether its argument is equal to zero; 
dec
decrements its argument; 
seq
returns<0>
if its argumentx
is equal to zero, andseq
, applied to(x1)
, withx
appended to right otherwise (if we unwind this recursive definition, we’ll get simply the sequence of values<0 1 ... x>
). 
factorial
returns 1 if its argumentx
is equal to zero, andfactorial
, applied to(x1)
, multiplied byx
otherwise.
The last line of the example applies factorial
to each element of sequence, obtained by applying seq
to 16. Note that all math operations produce floating point values, so the actual output will look like this:
< 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
Fibonacci numbers:
Example for versions Interactive FPThis example works in a same way as the factorial one, but without readability functions added.
{ seq ( = @ [id, %1] > %<1> ; concat @ [ seq @  @ [id, %1] , [id] ] ) }
{ fibonacci ( < @ [id, %3] > %1 ; + @ [ fibonacci @  @ [id, %1], fibonacci @  @ [id, %2] ] ) }
&fibonacci @ seq:16
Hello, World!:
Example for versions Furry Paws~x
is constantvalue function (denoted with %
in Interactive FP).
emit
is a function which writes its argument to stdout.
main
is a function which is the first to be invoked when the program is executed.
main = emit.(return ~"Hello, World!\n")
Factorial:
Example for versions Furry PawsThis example works in exactly the same way as the one in Interactive FP, except for that it doesn’t define zero
function, since it’s builtin. Note that here all operations are done within integer data type, and 13! overflows it, so the program can be called only to print factorials up to 12!. show
is another way to output data.
dec = sub.[id, ~1]
seq = zero > [id] ; cat.[seq.dec, [id]]
factorial = zero > ~1 ; mul.[id, factorial.dec]
main = show.(return @factorial.(seq.~12))
Fibonacci numbers:
Example for versions Furry PawsThis example works exactly like the one for Interactive FP.
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))
Comments
]]>blog comments powered by Disqus
]]>