Function-level programming
Encyclopedia
In computer science, function-level programming refers to one of the two contrasting programming paradigm
s identified by John Backus
in his work on programs as mathematical objects, the other being value-level programming
.
In his 1977 Turing award
lecture, Backus set forth what he considered to be the need to switch to a different philosophy in programming language design:
He designed FP
to be the first programming language
to specifically support the function-level programming style.
A function-level program is variable-free (cf. point-free programming), since program variable
s, which are essential in value-level definitions, are not needed in function-level ones.
In the function-level style of programming, a program is built directly from programs that are given at the outset, by combining them with program-forming operations or functionals. Thus, in contrast with the value-level approach that applies the given programs to values to form a succession of values culminating in the desired result value, the function-level approach applies program-forming operations to the given programs to form a succession of programs culminating in the desired result program.
As a result, the function-level approach to programming invites study of the space of programs under program-forming operations, looking to derive useful algebraic properties of these program-forming operations. The function-level approach offers the possibility of making the set of programs a mathematical space by emphasizing the algebraic properties of the program-forming operations over the space of programs.
Another potential advantage of the function-level view is the ability to use only strict function
s and thereby have bottom-up semantics, which are the simplest kind of all. Yet another is the existence of function level definitions that are not the lifted (that is, lifted from a lower value-level to a higher function-level) image of any existing value-level one: these (often terse) function-level definitions represent a more powerful style of programming not available at the value-level and, arguably, are often easier to understand and reason about.
style languages instead of his own FP
and its successor FL
.
Backus calls functional programming applicative programming;
his function-level programming is a particular, constrained
type of applicative programming.
A key distinction from functional languages is that Backus' language has the following hierarchy of types:
...and the only way to generate new functions is to use one of the functional forms, which are fixed: you cannot build your own functional form (at least not within FP; you can within FFP (Formal FP)).
This restriction means that functions in FP are a module
(generated by the built-in functions) over the algebra of functional forms, and are thus algebraically tractable. For instance, the general question of equality of two functions is equivalent to the halting problem
, and is undecidable, but equality of two functions in FP is just equality in the algebra, and thus (Backus imagines) easier.
Even today, many users of lambda style
languages often misinterpret Backus' function-level approach as a restrictive variant of the lambda style, which is a de facto value-level style. In fact, Backus would not have disagreed with the 'restrictive' accusation: he argued that it was precisely due to such restrictions that a well-formed mathematical space could arise, in a manner analogous to the way structured programming
limits programming to a restricted version of all the control-flow possibilities available in plain, unrestricted unstructured programs.
The value-free style of FP is closely related to the equational logic of a cartesian-closed category.
. Others include FL, FPr
and J
.
Programming paradigm
A programming paradigm is a fundamental style of computer programming. Paradigms differ in the concepts and abstractions used to represent the elements of a program and the steps that compose a computation A programming paradigm is a fundamental style of computer programming. (Compare with a...
s identified 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...
in his work on programs as mathematical objects, the other being value-level programming
Value-level programming
Value-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 function-level programming...
.
In his 1977 Turing award
Turing Award
The Turing Award, in full The ACM A.M. Turing Award, is an annual award given by the Association for Computing Machinery to "an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting and major technical importance to the...
lecture, Backus set forth what he considered to be the need to switch to a different philosophy in programming language design:
Programming languages appear to be in trouble. Each successive language incorporates, with a little cleaning up, all the features of its predecessors plus a few more. [...] Each new language claims new and fashionable features... but the plain fact is that few languages make programming sufficiently cheaper or more reliable to justify the cost of producing and learning to use them.
He designed FP
FP (programming language)
FP is a programming language created by John Backus to support the function-level programming paradigm...
to be the first 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....
to specifically support the function-level programming style.
A function-level program is variable-free (cf. point-free programming), since program variable
Variable (programming)
In computer programming, a variable is a symbolic name given to some known or unknown quantity or information, for the purpose of allowing the name to be used independently of the information it represents...
s, which are essential in value-level definitions, are not needed in function-level ones.
In the function-level style of programming, a program is built directly from programs that are given at the outset, by combining them with program-forming operations or functionals. Thus, in contrast with the value-level approach that applies the given programs to values to form a succession of values culminating in the desired result value, the function-level approach applies program-forming operations to the given programs to form a succession of programs culminating in the desired result program.
As a result, the function-level approach to programming invites study of the space of programs under program-forming operations, looking to derive useful algebraic properties of these program-forming operations. The function-level approach offers the possibility of making the set of programs a mathematical space by emphasizing the algebraic properties of the program-forming operations over the space of programs.
Another potential advantage of the function-level view is the ability to use only strict function
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...
s and thereby have bottom-up semantics, which are the simplest kind of all. Yet another is the existence of function level definitions that are not the lifted (that is, lifted from a lower value-level to a higher function-level) image of any existing value-level one: these (often terse) function-level definitions represent a more powerful style of programming not available at the value-level and, arguably, are often easier to understand and reason about.
Contrast to functional programming
When Backus studied and publicized his function-level style of programming, almost thirty years ago, his message was mostly misunderstood, giving boost to the traditional functional programmingFunctional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
style languages instead of his own FP
FP (programming language)
FP is a programming language created by John Backus to support the function-level programming paradigm...
and its successor FL
FL programming language
FL is a programming language created at the IBM Almaden Research Center by John Backus, John Williams, and Edward Wimmers in 1989....
.
Backus calls functional programming applicative programming;
his function-level programming is a particular, constrained
type of applicative programming.
A key distinction from functional languages is that Backus' language has the following hierarchy of types:
- atoms
- functions, which take atoms to atoms
- Higher-order functions (which he calls "functional forms"), which take one or two functions to functions
...and the only way to generate new functions is to use one of the functional forms, which are fixed: you cannot build your own functional form (at least not within FP; you can within FFP (Formal FP)).
This restriction means that functions in FP are a module
Module (mathematics)
In abstract algebra, the concept of a module over a ring is a generalization of the notion of vector space, wherein the corresponding scalars are allowed to lie in an arbitrary ring...
(generated by the built-in functions) over the algebra of functional forms, and are thus algebraically tractable. For instance, the general question of equality of two functions is equivalent to the halting problem
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
, and is undecidable, but equality of two functions in FP is just equality in the algebra, and thus (Backus imagines) easier.
Even today, many users of lambda style
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
languages often misinterpret Backus' function-level approach as a restrictive variant of the lambda style, which is a de facto value-level style. In fact, Backus would not have disagreed with the 'restrictive' accusation: he argued that it was precisely due to such restrictions that a well-formed mathematical space could arise, in a manner analogous to the way structured programming
Structured programming
Structured programming is a programming paradigm aimed on improving the clarity, quality, and development time of a computer program by making extensive use of subroutines, block structures and for and while loops - in contrast to using simple tests and jumps such as the goto statement which could...
limits programming to a restricted version of all the control-flow possibilities available in plain, unrestricted unstructured programs.
The value-free style of FP is closely related to the equational logic of a cartesian-closed category.
Example languages
The canonical function-level programming language is FPFP (programming language)
FP is a programming language created by John Backus to support the function-level programming paradigm...
. Others include FL, 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...
and 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....
.
See also
- Value-level programmingValue-level programmingValue-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 function-level programming...
(contrast) - Functional programmingFunctional programmingIn computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
(compare) - Programming paradigmProgramming paradigmA programming paradigm is a fundamental style of computer programming. Paradigms differ in the concepts and abstractions used to represent the elements of a program and the steps that compose a computation A programming paradigm is a fundamental style of computer programming. (Compare with a...
s - Pipeline programmingPipeline programmingWhen a programming language is originally designed without any syntax to nest function calls, pipeline programming is a simple syntax change to add it. The programmer connects notional program modules into a flow structure, by analogy to a physical pipeline carrying reaction products through a...
- Tacit programmingTacit programmingTacit programming is a programming paradigm in which a function definition does not include information regarding its arguments, using combinators and function composition instead of variables...
- Concatenative programming languageConcatenative programming languageA concatenative programming language is a point-free programming language in which all expressions denote functions and the juxtaposition of expressions denotes function composition...