Editing Function-level programming (section)

==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]].