# 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.

In his 1977 Turing award [http://www.stanford.edu/class/cs242/readings/backus.pdf 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 to be the first programming language to specifically support the function-level programming style.

A "function-level" program is variable-free, since program variables, 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 functions 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 programming style languages (such as Lisp) 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 Lisp (and other 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 (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.

Example languages

The canonical function-level programming language is FP. Others include FL and J.

provides an exhaustive list.

ee also

* Value-level programming (contrast)
* Functional programming (compare)
* Pipeline programming
* Tacit programming
* Concatenative programming language

References

* [http://www.stanford.edu/class/cs242/readings/backus.pdf Can Programming Be Liberated from the von Neumann Style?] Backus' Turing award lecture.

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Value-level programming — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurrent computin …   Wikipedia

• Low-level programming language — In computer science, a low level programming language is a language that provides little or no abstraction from a computer s microprocessor. The word low refers to the small or nonexistent amount of abstraction between the language and machine… …   Wikipedia

• Programming paradigm — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concu …   Wikipedia

• Programming language — lists Alphabetical Categorical Chronological Generational 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… …   Wikipedia

• Programming in the large and programming in the small — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurrent computin …   Wikipedia

• Concatenative programming language — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurr …   Wikipedia

• Functional 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 with the… …   Wikipedia

• J (programming language) — Not to be confused with the J++ or J# programming languages. Infobox programming language name = J paradigm = array, functional, function level, tacit year = 1990 designer = Ken Iverson Roger Hui developer = JSoftware latest release version =… …   Wikipedia

• FP (programming language) — Infobox programming language name = FP logo = paradigm = function level year = 1977 designer = John Backus developer = latest release version = latest release date = typing = implementations = dialects = influenced by = APL influenced = FL, JFP… …   Wikipedia

• Higher-order function — In mathematics and computer science, higher order functions or functionals are functions which do at least one of the following: *take one or more functions as an input *output a function.In mathematics these are also known as operators or… …   Wikipedia