View source for Function-level programming

{{Short description|Computer programming paradigm}}
{{redirect|function-level|the term in mental health assessments|Global Assessment of Functioning}}
{{confused|functional programming}}
{{original research|date=April 2018}}

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:<ref>{{cite journal|doi=10.1145/359576.359579|title=Can programming be liberated from the von Neumann style?: A functional style and its algebra of programs|journal=Communications of the ACM|volume=21|issue=8|pages=613–641|year=1978|last1=Backus|first1=John|url=https://www.cs.ucf.edu/~dcm/Teaching/COT4810-Fall%202012/Literature/Backus.pdf|doi-access=free}}</ref>
<blockquote>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.</blockquote>

He designed [[FP (programming language)|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|''point-free'' programming]]), since [[Variable (programming)|program variable]]s, 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 [[Programs as mathematical objects|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.

==Contrast to functional programming==
When Backus studied and publicized his function-level style of programming, his message was mostly misunderstood<ref>{{cite journal|doi=10.1145/72551.72554|title=Conception, evolution, and application of functional programming languages|journal=ACM Computing Surveys|volume=21|issue=3|pages=359–411|year=1989|last1=Hudak|first1=Paul|s2cid=207637854}}</ref> as supporting the traditional [[functional programming]] style languages instead of his own [[FP (programming language)|FP]] and its successor [[FL programming language|FL]].

Backus calls functional programming [[applicative programming]];{{clarify|date=November 2016}} 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 function]]s (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 (mathematics)|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 calculus|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 programming|unstructured programs]].

The value-free style of FP is closely related to the equational logic of a [[cartesian-closed category]].

==Example languages==
{{maincat|Function-level languages}}
The canonical function-level programming language is [[FP (programming language)|FP]]. Others include [[FL (programming language)|FL]], and [[J (programming language)|J]].

==See also==
* [[Concatenative programming language]]
* [[Functional programming]], [[declarative programming]] (compare)
* [[Tacit programming]]
* [[Value-level programming]], [[imperative programming]] (contrast)

==References==
{{Reflist}}

==External links==
* [https://dl.acm.org/doi/pdf/10.1145/800223.806757 Function Level Programs As Mathematical Objects] from John Backus
* From Function Level Semantics to Program Transformation and Optimization [https://link.springer.com/content/pdf/10.1007/3-540-15198-2_5.pdf?pdf=inline%20link SpringerLink] see point 1.2 and 1.3
* [http://dirkgerrits.com/publications/john-backus.pdf#section.8 Closed applicative languages, FP and FL], in John W. Backus (Publications) or the original [https://dl.acm.org/doi/pdf/10.1145/512927.512934 Programming Language Semantics and Closed Applicative Languages]
* Instance variables, a [https://esolangs.org/wiki/FP_trivia way out] of the variable abstinence

{{Programming paradigms navbox}}

{{DEFAULTSORT:Function-Level Programming}}
[[Category:Programming paradigms]]
[[Category:Programming language theory]]