FP (programming language)

Last updated
FP
Paradigm Function-level
Designed by John Backus
First appeared1977
Dialects
FP84
Influenced by
APL [1]
Influenced
FL, Haskell, Joy

FP (short for functional programming) [2] is a programming language created by John Backus to support the function-level programming [2] paradigm. It allows building programs from a set of generally useful primitives and avoiding named variables (a style also called tacit programming or "point free"). It was heavily influenced by APL developed by Kenneth E. Iverson in the early 1960s. [3]

Contents

The FP language was introduced in Backus's 1977 Turing Award paper, "Can Programming Be Liberated from the von Neumann Style?", subtitled "a functional style and its algebra of programs." The paper sparked interest in functional programming research, [4] eventually leading to modern functional languages, which are largely founded on the lambda calculus paradigm, and not the function-level paradigm Backus had hoped. In his Turing award paper, Backus described how the FP style is different:

An FP system is based on the use of a fixed set of combining forms called functional forms. These, plus simple definitions, are the only means of building new functions from existing ones; they use no variables or substitutions rules, and they become the operations of an associated algebra of programs. All the functions of an FP system are of one type: they map objects onto objects and always take a single argument. [2]

FP itself never found much use outside of academia. [5] In the 1980s Backus created a successor language, FL as an internal project at IBM Research.

Overview

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

if x1,...,xn are values, then the sequence 〈x1,...,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 functionsf that each map a single valuex into another:

f:x represents the value that results from applying the functionf      to the valuex

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:

i:〈x1,...,xn〉  =  xi  if  1 ≤ 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:

compositionf∘g        where    f∘g:x = f:(g:x)
construction [f1,...,fn] where   [f1,...,fn]:x =  〈f1:x,...,fn: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:〈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:

f ≡ Ef

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

FP84

FP84 is an extension of FP to include infinite sequences, programmer-defined combining forms (analogous to those that Backus himself added to FL, his successor to FP), and lazy evaluation. Unlike FFP, another one of Backus' own variations on FP, FP84 makes a clear distinction between objects and functions: i.e., the latter are no longer represented by sequences of the former. FP84's extensions are accomplished by removing the FP restriction that sequence construction be applied only to non-⊥ objects: in FP84 the entire universe of expressions (including those whose meaning is ⊥) is closed under sequence construction.

FP84's semantics are embodied in an underlying algebra of programs, a set of function-level equalities that may be used to manipulate and reason about programs.

Related Research Articles

<span class="mw-page-title-main">Diophantine equation</span> Polynomial equation whose integer solutions are sought

In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, for which only integer solutions are of interest. A linear Diophantine equation equates to a constant the sum of two or more monomials, each of degree one. An exponential Diophantine equation is one in which unknowns can appear in exponents.

<span class="mw-page-title-main">Gradient</span> Multivariate derivative (mathematics)

In vector calculus, the gradient of a scalar-valued differentiable function of several variables is the vector field whose value at a point gives the direction and the rate of fastest increase. The gradient transforms like a vector under change of basis of the space of variables of . If the gradient of a function is non-zero at a point , the direction of the gradient is the direction in which the function increases most quickly from , and the magnitude of the gradient is the rate of increase in that direction, the greatest absolute directional derivative. Further, a point where the gradient is the zero vector is known as a stationary point. The gradient thus plays a fundamental role in optimization theory, where it is used to minimize a function by gradient descent. In coordinate-free terms, the gradient of a function may be defined by:

In computability theory, a primitive recursive function is, roughly speaking, a function that can be computed by a computer program whose loops are all "for" loops. Primitive recursive functions form a strict subset of those general recursive functions that are also total functions.

In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as in a formal one. If the function is total, it is also called a total recursive function. In computability theory, it is shown that the μ-recursive functions are precisely the functions that can be computed by Turing machines. The μ-recursive functions are closely related to primitive recursive functions, and their inductive definition (below) builds upon that of the primitive recursive functions. However, not every total recursive function is a primitive recursive function—the most famous example is the Ackermann function.

<span class="mw-page-title-main">John Backus</span> American computer scientist

John Warner Backus was an American computer scientist. He led the team that invented and implemented FORTRAN, the first widely used high-level programming language, and was the inventor of the Backus–Naur form (BNF), a widely used notation to define syntaxes of formal languages. He later did research into the function-level programming paradigm, presenting his findings in his influential 1977 Turing Award lecture "Can Programming Be Liberated from the von Neumann Style?"

In mathematics, a function from a set X to a set Y assigns to each element of X exactly one element of Y. The set X is called the domain of the function and the set Y is called the codomain of the function.

In category theory, the product of two objects in a category is a notion designed to capture the essence behind constructions in other areas of mathematics such as the Cartesian product of sets, the direct product of groups or rings, and the product of topological spaces. Essentially, the product of a family of objects is the "most general" object which admits a morphism to each of the given objects.

In mathematics, Fatou's lemma establishes an inequality relating the Lebesgue integral of the limit inferior of a sequence of functions to the limit inferior of integrals of these functions. The lemma is named after Pierre Fatou.

<span class="mw-page-title-main">Uniform norm</span> Function in mathematical analysis

In mathematical analysis, the uniform norm assigns to real- or complex-valued bounded functions defined on a set the non-negative number

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.

This page lists some examples of vector spaces. See vector space for the definitions of terms used on this page. See also: dimension, basis.

In mathematics, a multicategory is a generalization of the concept of category that allows morphisms of multiple arity. If morphisms in a category are viewed as analogous to functions, then morphisms in a multicategory are analogous to functions of several variables. Multicategories are also sometimes called operads, or colored operads.

In the mathematical theory of probability, a Doob martingale is a stochastic process that approximates a given random variable and has the martingale property with respect to the given filtration. It may be thought of as the evolving sequence of best approximations to the random variable based on information accumulated up to a certain time.

In mathematics, a constraint is a condition of an optimization problem that the solution must satisfy. There are several types of constraints—primarily equality constraints, inequality constraints, and integer constraints. The set of candidate solutions that satisfy all constraints is called the feasible set.

Function Representation is used in solid modeling, volume modeling and computer graphics. FRep was introduced in "Function representation in geometric modeling: concepts, implementation and applications" as a uniform representation of multidimensional geometric objects (shapes). An object as a point set in multidimensional space is defined by a single continuous real-valued function of point coordinates which is evaluated at the given point by a procedure traversing a tree structure with primitives in the leaves and operations in the nodes of the tree. The points with belong to the object, and the points with are outside of the object. The point set with is called an isosurface.

In abstract algebra, a completion is any of several related functors on rings and modules that result in complete topological rings and modules. Completion is similar to localization, and together they are among the most basic tools in analysing commutative rings. Complete commutative rings have a simpler structure than general ones, and Hensel's lemma applies to them. In algebraic geometry, a completion of a ring of functions R on a space X concentrates on a formal neighborhood of a point of X: heuristically, this is a neighborhood so small that all Taylor series centered at the point are convergent. An algebraic completion is constructed in a manner analogous to completion of a metric space with Cauchy sequences, and agrees with it in the case when R has a metric given by a non-Archimedean absolute value.

In mathematical logic, predicate functor logic (PFL) is one of several ways to express first-order logic by purely algebraic means, i.e., without quantified variables. PFL employs a small number of algebraic devices called predicate functors that operate on terms to yield terms. PFL is mostly the invention of the logician and philosopher Willard Quine.

In mathematics, a set of n functions f1, f2, ..., fn is unisolvent on a domain Ω if the vectors

In mathematics, and especially differential topology and singularity theory, the Eisenbud–Levine–Khimshiashvili signature formula gives a way of computing the Poincaré–Hopf index of a real, analytic vector field at an algebraically isolated singularity. It is named after David Eisenbud, Harold I. Levine, and George Khimshiashvili. Intuitively, the index of a vector field near a zero is the number of times the vector field wraps around the sphere. Because analytic vector fields have a rich algebraic structure, the techniques of commutative algebra can be brought to bear to compute their index. The signature formula expresses the index of an analytic vector field in terms of the signature of a certain quadratic form.

LOOP is a simple register language that precisely captures the primitive recursive functions. The language is derived from the counter-machine model. Like the counter machines the LOOP language comprises a set of one or more unbounded registers, each of which can hold a single non-negative integer. A few arithmetic instructions operate on the registers. The only control flow instruction is 'LOOP x DO...END'. It causes the instructions within its scope to be repeated x times.

References

  1. ↑ The Conception, Evolution, and Application of Functional Programming Languages Archived 2016-03-11 at the Wayback Machine Paul Hudak, 1989
  2. 1 2 3 Backus, J. (1978). "Can programming be liberated from the von Neumann style?: A functional style and its algebra of programs". Communications of the ACM. 21 (8): 613. doi: 10.1145/359576.359579 .
  3. ↑ "Association for Computing Machinery A. M. Turing Award" (PDF).[ permanent dead link ]
  4. ↑ Yang, Jean (2017). "Interview with Simon Peyton-Jones". People of Programming Languages.
  5. ↑ Hague, James (December 28, 2007). "Functional Programming Archaeology". Programming in the Twenty-First Century.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.