FP (programming language)

<h2 id="overview">Overview</h2>
The values that FP programs map into one another comprise a <a href="/facts/Set_(abstract_data_type)/ovoXUmF9">set</a> which is <a href="/facts/Closure_(mathematics)/Ct6r2fJz">closed</a> under sequence formation:

if x1,...,xn are values, then the sequence 〈x1,...,xn〉 is also a value

These values can be built from any set of atoms: booleans, integers, reals, characters, etc.:

boolean  : {T, F}
integer  : {0,1,2,...,∞}
character : {'a','b','c',...}
symbol  : {x,y,...}

⊥ is the undefined value, or bottom. Sequences are bottom-preserving:

〈x1,...,⊥,...,xn〉 = ⊥

FP programs are functions f that each map a single value x into another:

f:x represents the value that results from applying the function f 
 to the value x

Functions are either primitive (i.e., provided with the FP environment) or are built from the primitives by program-forming operations (also called functionals).
An example of primitive function is constant, which transforms a value x into the constant-valued function x̄. Functions are <a href="/facts/Strict_function/Fc6PYymI">strict</a>:

f:⊥ = ⊥

Another example of a primitive function is the selector function family, denoted by 1,2,... where:

i:〈x1,...,xn〉 = xi if 1 ≤ i ≤ n
 = ⊥ otherwise

<h2 id="functionals">Functionals</h2>
In contrast to primitive functions, functionals operate on other functions. For example, some functions have a unit value, such as 0 for addition and 1 for multiplication. The functional unit produces such a value when applied to a function f that has one:

unit + = 0
unit × = 1
unit foo = ⊥

These are the core functionals of FP:

composition f∘g where f∘g:x = f:(g:x)

construction [f1,...,fn] where   [f1,...,fn]:x =  〈f1:x,...,fn:x〉

condition (h ⇒ f;g)    where   (h ⇒ f;g):x   =  f:x   if   h:x  =  T
                                             =  g:x   if   h:x  =  F
                                             =  ⊥    otherwise

apply-to-all αf where αf:〈x1,...,xn〉 = 〈f:x1,...,f:xn〉

insert-right  /f       where   /f:〈x〉             =  x
                       and     /f:〈x1,x2,...,xn〉  =  f:〈x1,/f:〈x2,...,xn〉〉
                       and     /f:〈 〉             =  unit f

insert-left  \f       where   \f:〈x〉             =  x
                      and     \f:〈x1,x2,...,xn〉  =  f:〈\f:〈x1,...,xn-1〉,xn〉
                      and     \f:〈 〉             =  unit f

<h2 id="equational-functions">Equational functions</h2>
In addition to being constructed from primitives by functionals, a function may be defined recursively by an equation, the simplest kind being:

f ≡ Ef

where Ef is an <a href="/facts/Expression_(computer_science)/eRlhoBeN">expression</a> built from primitives, other defined functions, and the function symbol f itself, using functionals.

<h2 id="fp84">FP84</h2>
FP84 is an extension of FP to include <a href="/facts/Infinite_sequence/gV2S4uqp">infinite sequences</a>, programmer-defined <a href="/facts/Combining_form/9zVyEVVL">combining forms</a> (analogous to those that Backus himself added to <a href="/facts/FL_programming_language/EahaIaDo">FL</a>, his successor to FP), and <a href="/facts/Lazy_evaluation/mD3DxDkc">lazy evaluation</a>. Unlike FFP, another one of Backus' own variations on FP, FP84 makes a clear distinction between objects and functions: i.e., the latter are no longer represented by sequences of the former. FP84's extensions are accomplished by removing the FP restriction that sequence construction be applied only to non-⊥ objects: in FP84 the entire universe of expressions (including those whose meaning is ⊥) is <a href="/facts/Closed_under/Ct6r2fJz">closed under</a> sequence construction.
FP84's semantics are embodied in an underlying algebra of programs, a set of <a href="/facts/Function-level_programming/0uCybhfG">function-level</a> equalities that may be used to manipulate and reason about programs.

<ul><li>Sacrificing simplicity for convenience: Where do you draw the line?, John H. Williams and Edward L. Wimmers, IBM Almaden Research Center, Proceedings of the Fifteenth Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, San Diego, CA, January 1988.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://pointfree-interpreter.github.io/">FP-Interpreter</a> written in Delphi/Lazarus</li>
<li><a href="http://dirkgerrits.com/publications/john-backus.pdf#section.9">Dirk Gerrits: Turing Award lecture (1977-1978) ff</a>, in John W. Backus (Publications)</li>
<li>FP84 vs FL: <a href="https://dl.acm.org/doi/pdf/10.1145/73560.73575">Sacrificing simplicity for convenience: Where do you draw the line?</a> J.H. William and E.L. Wimmers, 1988 (Pages 169–179)</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Backus, J. (1978). "Can programming be liberated from the von Neumann style?: A functional style and its algebra of programs". Communications of the ACM. 21 (8): 613. doi:10.1145/359576.359579. <a href="https://doi.org/10.1145%2F359576.359579" target="_blank">https://doi.org/10.1145%2F359576.359579</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Backus, J. (1978). "Can programming be liberated from the von Neumann style?: A functional style and its algebra of programs". Communications of the ACM. 21 (8): 613. doi:10.1145/359576.359579. <a href="https://doi.org/10.1145%2F359576.359579" target="_blank">https://doi.org/10.1145%2F359576.359579</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">"Association for Computing Machinery A. M. Turing Award" (PDF).[permanent dead link] <a href="http://signallake.com/innovation/JBackus032007.pdf" target="_blank">http://signallake.com/innovation/JBackus032007.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Yang, Jean (2017). "Interview with Simon Peyton-Jones". People of Programming Languages. <a href="https://www.cs.cmu.edu/~popl-interviews/peytonjones.html" target="_blank">https://www.cs.cmu.edu/~popl-interviews/peytonjones.html</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Backus, J. (1978). "Can programming be liberated from the von Neumann style?: A functional style and its algebra of programs". Communications of the ACM. 21 (8): 613. doi:10.1145/359576.359579. <a href="https://doi.org/10.1145%2F359576.359579" target="_blank">https://doi.org/10.1145%2F359576.359579</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Hague, James (December 28, 2007). "Functional Programming Archaeology". Programming in the Twenty-First Century. <a href="http://prog21.dadgum.com/14.html" target="_blank">http://prog21.dadgum.com/14.html</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
</ol>

FP (programming language) open-in-new

FP (programming language)