FP (programming language): Difference between revisions

Revision as of 21:16, 27 October 2006

Latest revision as of 09:26, 11 August 2025

(122 intermediate revisions by 67 users not shown)

Line 1:

{{Short description|Programming language}}

'''FP''' (short for '''F'''unction '''P'''rogramming) is a [[programming language]] created by [[John Backus]] to support the [[function-level programming]] paradigm. This allows for the elimination of named variables.

* [[J programming language|J]]{{Infobox programming language

|name = FP

|logo =

*|paradigm = [[Function-level programming|Function-level]]

|year = 1977

*|designer = [[John Backus]]

|developer =

|latest release version =

|latest release date =

|typing =

|implementations =

|dialects = FP84

|influenced_by = [[APL (programming language)|APL]]<ref name="Hudak 1989">[https://dl.acm.org/doi/10.1145/72551.72554 The Conception, Evolution, and Application of Functional Programming Languages] {{Webarchive|url=https://web.archive.org/web/20160311204021/http://haskell.cs.yale.edu/wp-content/uploads/2011/01/cs.pdf |date=2016-03-11 }} Paul Hudak, 1989</ref>

|influenced = [[FL (programming language)|FL]], [[Haskell (programming language)|Haskell]], [[Joy (programming language)|Joy]]

}}

'''FP''' (short for ''functional programming'')<ref name="Backus 1977"/> is a [[programming language]] created by [[John Backus]] to support the [[function-level programming]]<ref name="Backus 1977"/> paradigm. It allows building programs from a set of generally useful primitives and avoiding named variables (a style also called [[tacit programming]] or "point free"). It was heavily influenced by [[APL (programming language)|APL]] developed by [[Kenneth E. Iverson]] in the early 1960s.<ref name=acm/>

The FP language was introduced in Backus's 1977 [[Turing Award]] paper, "Can Programming Be Liberated from the von Neumann Style?", subtitled "a functional style and its algebra of programs." The paper sparked interest in [[functional programming]] research,<ref>{{cite web|last1=Yang|first1=Jean|title=Interview with Simon Peyton-Jones|url=https://www.cs.cmu.edu/~popl-interviews/peytonjones.html|website=People of Programming Languages|date=2017}}</ref> eventually leading to modern functional languages, which are largely founded on the [[lambda calculus]] paradigm, and not the function-level paradigm Backus had hoped. In his Turing award paper, Backus described how the FP style is different:

{{blockquote|An FP system is based on the use of a fixed set of combining forms called functional forms. These, plus simple definitions, are the only means of building new functions from existing ones; they use no variables or substitutions rules, and they become the operations of an associated algebra of programs. All the functions of an FP system are of one type: they map objects onto objects and always take a single argument.<ref name="Backus 1977"/>}}

FP itself never found much use outside of academia.<ref name="p21">{{cite web|last1=Hague|first1=James|title=Functional Programming Archaeology|url=http://prog21.dadgum.com/14.html|website=Programming in the Twenty-First Century|date=December 28, 2007}}</ref> In the 1980s Backus created a successor language, [[FL (programming language)|FL]] as an internal project at [[IBM Research]].

== Overview ==

The '''values''' that FP programs map into one another comprise a [[set (abstract data type)|set]] which is [[closure (mathematics)|closed]] under '''sequence formation''':

if '''x'''₁,...,'''x'''_n are '''values''', then the '''sequence''' 〈'''x'''₁,...,'''x'''_n〉 is also a '''value'''

Line 22 ⟶ 45:

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 oneprimitive such operationfunction is '''constant''', which transforms a value '''x''' into the constant-valued function '''x̄'''. Functions are [[strict function|strict]]:

'''f''':'''⊥''' = '''⊥'''

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

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:

'''''i''''':〈'''x'''₁,...,'''x'''_n〉 = '''x'''_i if 01 <≤ '''''i''''' ≤ n

= ⊥ otherwise

==Functionals==

SomeIn 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 &times;×''' = 1

'''unit foo''' = ⊥

==Functionals==

These are the core functionals of FP:

'''constantcomposition''' '''x̄f'''∘'''g''' where '''x̄f'''∘'''g''':'''yx''' = '''f''':('''g''':'''x''')

'''compositionconstruction''' ['''f'''°₁,...,'''gf''' _n] where ['''f'''°₁,...,'''gf'''_n]:'''x''' = 〈'''f'''₁:('''gx''',...,'''f'''_n:'''x''')〉

'''construction''' ['''f'''₁,...'''f'''_n] where ['''f'''₁,...'''f'''_n]:'''x''' = 〈'''f'''₁:'''x''',...,'''f'''_n:'''x'''〉

'''condition''' ('''h''' ⇒ '''f''';'''g''') where ('''h''' ⇒ '''f''';'''g'''):'''x''' = '''f''':'''x''' if '''h''':'''x''' = '''T'''

Line 57 ⟶ 85:

In addition to being constructed from primitives by functionals, a function may be defined recursively by an equation, the simplest kind being:

'''f''' ≡ ''E'''''f'''

where ''E''''''f''' is an [[expression (programmingcomputer science)|expression]] built from primitives, other defined functions, and the function symbol '''f''' itself, using functionals.

==FP84==

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

'''FP84''' is an extension of FP to include [[infinite sequence]]s, programmer-defined [[combining form]]s (analogous to those that Backus himself added to [[FL programming language|FL]], his successor to FP), and [[lazy evaluation]]. 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 [[closed under]] sequence construction.

'''1''':〈'''x'''₁,...,'''x'''_n〉 = '''x'''₁

'''''i''''':〈'''x'''₁,...,'''x'''_n〉 = '''x'''_i if 0 < '''''i''''' ≤ n

= ⊥ otherwise

FP84's semantics are embodied in an underlying algebra of programs, a set of [[function-level programming|function-level]] equalities that may be used to manipulate and reason about programs.

==See also==

* [[FL programming language]] (Backus' successor to FP)

* [[Function-level programming]]

* [[Programs as mathematical objects]]

* [[J programming language|J]] programming language

* [[John Backus]]

==References==

[[Category:Function-level languages]]

{{Reflist|refs=

<ref name="Backus 1977">{{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| year = 1978| last1 = Backus | first1 = J. | doi-access = free}}</ref>

<ref name=acm>{{cite web |title=Association for Computing Machinery A. M. Turing Award |url=http://signallake.com/innovation/JBackus032007.pdf }}{{Dead link|date=March 2024 |bot=InternetArchiveBot |fix-attempted=yes }}</ref>

}}

*''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.

==External links==

[[es:Lenguaje de programación FP]]

* [https://pointfree-interpreter.github.io/ FP-Interpreter] written in Delphi/Lazarus

[[fr:Functional Programming]]

* [http://dirkgerrits.com/publications/john-backus.pdf#section.9 Dirk Gerrits: Turing Award lecture (1977-1978) ff], in John W. Backus (Publications)

* FP84 vs FL: [https://dl.acm.org/doi/pdf/10.1145/73560.73575 Sacrificing simplicity for convenience: Where do you draw the line?] J.H. William and E.L. Wimmers, 1988 (Pages 169–179)

[[Category:Academic programming languages]]

[[Category:Function-level languages]]

[[Category:Programming languages created in 1977]]