FP

Appeared in:
1977
Influenced:
Paradigm:
Typing discipline:
File extensions:
.fp
Versions and implementations (Collapse all | Expand all):
Programming language

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 function-level 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 function-level programming paradigm, but it has only a few implementations which differ quite a lot, and none of them is used in real-life 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 function-level 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 floating-point) 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 <x1, ..., xn>, where xi 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 non-strict 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 undefined-preserving, i.e., if function argument or one of elements in sequence is undefined, the return of the function or the sequence itself is undefined as well.

As any function-level 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 constant-value function is used.

2. functions can be primitive or user-defined. FP functions always take one atom as argument, which is written as f:x. The list of primitive functions includes:

  • identity: id:x evaluates to x.
  • constant-value: %x:y evaluates to x for any value of y (some authors consider % to be a functional form, but it doesn’t have a function-type argument).
  • math +,-,*,/: +:<x y> evaluates to x+y, if x and y are scalar values.
  • selector: i:<x1 ... xn> evaluates to xi, 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.
  • user-defined 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 user-defined. Unlike functions, forms can have multiple arguments. The list of standard forms includes:

  • construction: [f1, ..., fn]:x evaluates to <f1:x ... fn:x>.
  • composition: f @ g:x evaluates to f:(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, otherwise falseChoice:x is returned. All three arguments of conditional are functions.
  • apply-to-all: @f:<x1 ... xn> evaluates to <f:x1 ... f:xn>.
  • right insert: !f:<x1 x2 ... xn> evaluates to f:<x1 !f:<x2 ... xn>> and is applied recursively;
    !f:<x> evaluates to x (left insert is defined in a similar way).

Elements of syntax:

Inline comments %

Links:

Examples:

Factorial:

Example for versions Interactive FP

This 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 argument x is equal to zero, and seq, applied to (x-1), with x 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 argument x is equal to zero, and factorial, applied to (x-1), multiplied by x 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 FP

This 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 constant-value 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 Paws

This 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 built-in. 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 Paws

This 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))