Added to Favorites

Related Searches

Definitions

Nearby Words

FP (short for Function Programming) is a programming language created by John Backus to support the function-level programming paradigm. This allows for the elimination of named variables.

The values that FP programs map into one another comprise a set which is closed under sequence formation:

if x_{1},...,x_{n}are values, then the sequence 〈x_{1},...,x_{n}〉 is also a value

These values can be built from any set of atoms: booleans, integers, reals, characters, etc.: boolean : {T, F} integer : {0,1,2,...,∞} character : {'a','b','c',...} symbol : {x,y,...}

⊥ is the undefined value, or bottom. Sequences are bottom-preserving:

〈x_{1},...,⊥,...,x_{n}〉 = ⊥

FP programs are functions f that each map a single value x into another:

f:x represents the value that results from applying the function f

to the value x

Functions are either primitive (i.e., provided with the FP environment) or are built from the primitives by program-forming operations (also called functionals).

An example of primitive function is constant, which transforms a value x into the constant-valued function x̄. Functions are strict:

f:⊥ = ⊥

Another example of a primitive function is the selector function family, denoted by 1,2,... where:

1:〈x_{1},...,x_{n}〉 = x_{1}

i:〈x_{1},...,x_{n}〉 = x_{i}if 0 < i ≤ n

= ⊥ otherwise

In contrast to primitive functions, functionals operate on other functions. For example, some functions have a unit value, such as 0 for addition and 1 for multiplication. The functional unit produces such a value when applied to a function f that has one:

`unit + = 0`

`unit × = 1`

`unit foo = ⊥`

These are the core functionals of FP:

composition f°g where f°g:x = f:(g:x)

construction [f_{1},...f_{n}] where [f_{1},...f_{n}]:x = 〈f_{1}:x,...,f_{n}:x〉

condition (h ⇒ f;g) where (h ⇒ f;g):x = f:x if h:x = T

= g:x if h:x = F

` = ⊥ otherwise`

apply-to-all αf where αf:〈x_{1},...,x_{n}〉 = 〈f:x_{1},...,f:x_{n}〉

insert-right /f where /f:〈x〉 = x

and /f:〈x_{1},x_{2},...,x_{n}〉 = f:〈x_{1},/f:〈x_{2},...,x_{n}〉〉

and /f:〈 〉 = unit f

insert-left f where f:〈x〉 = x

and f:〈x_{1},x_{2},...,x_{n}〉 = f:〈f:〈x_{1},...,x_{n-1}〉,x_{n}〉

and f:〈 〉 = unit f

In addition to being constructed from primitives by functionals, a function may be defined recursively by an equation, the simplest kind being:

f ≡ Efwhere Ef is an expression built from primitives, other defined functions, and the function symbol f' itself, using functionals.

- FL programming language (Backus' successor to FP)
- Function-level programming
- Programs as mathematical objects
- J programming language
- John Backus

- Can Programming Be Liberated from the von Neumann Style? Backus' Turing award lecture.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Thursday October 11, 2007 at 12:47:31 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Thursday October 11, 2007 at 12:47:31 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.