FP (programming language)
Encyclopedia
FP is a programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....

 created by John Backus
John Backus
John Warner Backus was an American computer scientist. He directed the team that invented the first widely used high-level programming language and was the inventor of the Backus-Naur form , the almost universally used notation to define formal language syntax.He also did research in...

 to support the function-level programming
Function-level programming
In computer science, function-level programming refers to one of the two contrasting programming paradigms identified by John Backus in his work on programs as mathematical objects, the other being value-level programming....

 paradigm. This allows eliminating named variables.

Overview

The values that FP programs map into one another comprise a set
Set (computer science)
In computer science, a set is an abstract data structure that can store certain values, without any particular order, and no repeated values. It is a computer implementation of the mathematical concept of a finite set...

 which is closed
Closure (mathematics)
In mathematics, a set is said to be closed under some operation if performance of that operation on members of the set always produces a unique member of the same set. For example, the real numbers are closed under subtraction, but the natural numbers are not: 3 and 8 are both natural numbers, but...

 under sequence formation:

if x1,...,xn are values, then the sequencex1,...,xn〉 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:

x1,...,,...,xn〉 =

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 . Functions are strict
Strict function
A strict function in the denotational semantics of programming languages is a function f where f\left = \perp. The entity \perp, called bottom, denotes an expression which does not return a normal value, either because it loops endlessly or because it aborts due to an error such as division by...

:
f: =

Another example of a primitive function is the selector function family, denoted by 1,2,... where:
1:〈x1,...,xn〉 = x1
i:〈x1,...,xn〉 = xi if 0 < i ≤ n
= ⊥ otherwise

Functionals

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 [f1,...fn] where [f1,...fn]:x = 〈f1:x,...,fn:x

condition (hf;g) where (hf;g):x = f:x if h:x = T
= g:x if h:x = F
= otherwise

apply-to-all αf where αf:〈x1,...,xn〉 = 〈f:x1,...,f:xn

insert-right /f where /f:〈x〉 = x
and /f:〈x1,x2,...,xn〉 = f:〈x1,/f:〈x2,...,xn〉〉
and /f:〈 〉 = unit f

insert-left \f where \f:〈x〉 = x
and \f:〈x1,x2,...,xn〉 = f:〈\f:〈x1,...,xn-1〉,xn
and \f:〈 〉 = unit f

Equational functions

In addition to being constructed from primitives by functionals, a function may be defined recursively by an equation, the simplest kind being:
fEf
where
E
'f is an expression
Expression (programming)
An expression in a programming language is a combination of explicit values, constants, variables, operators, and functions that are interpreted according to the particular rules of precedence and of association for a particular programming language, which computes and then produces another value...

 built from primitives, other defined functions, and the function symbol f itself, using functionals.

See also

  • FL, Backus' FP successor
  • Function-level programming
    Function-level programming
    In computer science, function-level programming refers to one of the two contrasting programming paradigms identified by John Backus in his work on programs as mathematical objects, the other being value-level programming....

  • J
    J (programming language)
    The J programming language, developed in the early 1990s by Kenneth E. Iverson and Roger Hui, is a synthesis of APL and the FP and FL function-level languages created by John Backus....

  • John Backus
    John Backus
    John Warner Backus was an American computer scientist. He directed the team that invented the first widely used high-level programming language and was the inventor of the Backus-Naur form , the almost universally used notation to define formal language syntax.He also did research in...

  • FP84
    FP84
    FP84 is an extension of John Backus' FP programming language to include infinite sequences, programmer-defined combining forms , and lazy evaluation....

  • FFP, Formal Functional Programming
  • FPr
    FPr (programming language)
    FPr is a programming language that is an implementation of an FP-System. FP was invented by John Backus and described in his Turing Award lecture...

    , Function-level Programming right-associative
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK