In computer science, function-level programming is 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.

"function-level" redirects here. For the term in mental health assessments, see Global Assessment of Functioning.

Not to be confused with Functional 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:¹

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 (cf. point-free programming), since program variables, which are essential in value-level definitions, are not needed in function-level programs.

Introduction

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.

Contrast to functional programming

When Backus studied and publicized his function-level style of programming, his message was mostly misunderstood² as supporting the traditional functional programming 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.

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 (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

Main category: Function-level languages

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

References

1Backus, John (1978). "Can programming be liberated from the von Neumann style?: A functional style and its algebra of programs" (PDF). Communications of the ACM. 21 (8): 613–641. doi:10.1145/359576.359579.
2Hudak, Paul (1989). "Conception, evolution, and application of functional programming languages". ACM Computing Surveys. 21 (3): 359–411. doi:10.1145/72551.72554. S2CID 207637854.

External links

Function Level Programs As Mathematical Objects from John Backus
From Function Level Semantics to Program Transformation and Optimization SpringerLink see point 1.2 and 1.3
Closed applicative languages, FP and FL, in John W. Backus (Publications) or the original Programming Language Semantics and Closed Applicative Languages
Instance variables, a way out of the variable abstinence

Rabbit hole

Where Function-level programming leads. Every connection below has a source: a link in this article, a shared Wikipedia category, or CirrusSearch text similarity. Articles already on your trail are left out.

Go deeper: linked from this article

Listed under See also
Functional programming
Programming paradigm based on applying and composing functions
In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions.
33 min readGo deeper
Linked from the introduction
Programming language
Language for controlling a computer
A programming language is a formal language designed to express computations, typically supporting the specification of software both for humans and for computers.
24 min readGo deeper
Linked from the introduction
Programming paradigm
High-level computer programming conceptualization
A programming paradigm is a relatively high-level way to conceptualize and structure the implementation of a computer program.
9 min readGo deeper
Listed under See also
Imperative programming
Type of programming paradigm in computer science
In computer science, imperative programming is a software programming paradigm that provides specific instructions for how computations should take place.
12 min readGo deeper
Listed under See also
Declarative programming
Programming paradigm based on modeling the logic of a computation
In computer science, declarative programming is a programming paradigm that expresses the logic of a computation without fully describing its control flow.
6 min readGo deeper
Listed under See also
Tacit programming
Programming paradigm
Tacit programming, also called point-free style, is a programming paradigm in which function definitions do not identify the arguments (or "points") on which they operate.
4 min readGo deeper
Linked from the introduction
Variable (high-level programming language)
Named container for a particular type of data
In some high-level programming languages, a variable is an abstract storage or indirection location paired with an associated symbolic name, which contains some known or unknown quantity of data or…
8 min readGo deeper
Linked from the introduction
FP (programming language)
Programming language
FP (for functional programming) is a programming language created by John Backus to support the function-level programming paradigm.
3 min readGo deeper

Adjacent: shared categories and similar text

Linked in “Contrast to functional programming”
Lambda calculus
Mathematical-logic system
In mathematical logic, the lambda calculus (also written as λ-calculus) is a formal system for expressing computation based on function abstraction and application using variable binding and substitution.
28 min readGo deeper
Linked in “Contrast to functional programming”
Cartesian closed category
Type of category in category theory
In category theory, a category is Cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors.
7 min readGo deeper
Linked in “Contrast to functional programming”
Module (mathematics)
Generalization of vector spaces from fields to rings
In mathematics, a module is a generalization of the notion of vector space in which the field of scalars is replaced by a (not necessarily commutative) ring.
8 min readGo deeper
Linked in “Contrast to functional programming”
Higher-order function
Function that takes one or more functions as an input or that outputs a function
In mathematics and computer science, a higher-order function (HOF) is a function that does at least one of the following: takes one or more functions as arguments (i.e. a procedural parameter, which…
9 min readGo deeper
Linked in “Introduction”
Strict function
In computer science and computer programming, a function f is said to be strict if, when applied to a non-terminating expression, it also fails to terminate.
1 min readGo deeper
Linked in “Contrast to functional programming”
Halting problem
Problem in computer science
In computability theory, the halting problem is the decision problem of, given an arbitrary computer program and an input, determining whether said program will eventually finish running and halt, or will continue to run forever.
20 min readGo deeper

Introduction

Contrast to functional programming

Example languages

See also

References

External links

Terminology

Recent changes

Rabbit hole

Go deeper: linked from this article

Adjacent: shared categories and similar text

Introduction

Contrast to functional programming

Example languages

See also

References

External links

Terminology

Key concepts

Go deeper: linked from this article

Adjacent: shared categories and similar text