FP (programming language): Difference between revisions

Revision as of 13:49, 14 August 2004

Latest revision as of 09:26, 11 August 2025

(154 intermediate revisions by 78 users not shown)

Line 1:

{{Short description|Programming language}}

'''FP''' (short for '''F'''unctional '''P''' programming) is a [[programming language]] created by [[John Backus]] to support the [[Function-level programming]] paradigm.

{{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''' &lt;'''x'''₁,...,'''x'''_n> is also a ''value''

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

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

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'':

〈'''x'''₁,...,'''⊥''',...,'''x'''_n〉 = '''⊥'''

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 [[strict function|strict]]:

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

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

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

= ⊥ otherwise

==Functionals==

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''' ['''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'''

= '''g''':'''x''' if '''h''':'''x''' = '''F'''

= '''⊥''' otherwise

'''apply-to-all''' ''α'''''f''' where ''α'''''f''':〈'''x'''₁,...,'''x'''_n〉 = 〈'''f''':'''x'''₁,...,'''f''':'''x'''_n〉

'''insert-right''' /'''f''' where /'''f''':〈'''x'''〉 = '''x'''

and /'''f''':〈'''x'''₁,'''x'''₂,...,'''x'''_n〉 = '''f''':〈'''x'''₁,/'''f''':〈'''x'''₂,...,'''x'''_n〉〉

and /'''f''':〈 〉 = '''unit f'''

'''insert-left''' \'''f''' where \'''f''':〈'''x'''〉 = '''x'''

and \'''f''':〈'''x'''₁,'''x'''₂,...,'''x'''_n〉 = '''f''':〈\'''f''':〈'''x'''₁,...,'''x'''_n-1〉,'''x'''_n〉

and \'''f''':〈 〉 = '''unit f'''

==Equational functions==

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 (computer science)|expression]] built from primitives, other defined functions, and the function symbol '''f''' itself, using functionals.

==FP84==

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

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.

==References==

{{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==

Functions are either primitive (i.e., provided with the FP environment) or are built from the primitives by '''program-forming operations''' (also called '''functionals'''). One such operation is '''constant''', which transforms a value '''x''' into the constant-valued function '''x&#x304;''' where:

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

'''constant''' '''x&#x304;''' where '''x&#x304;''':'''y''' = '''x'''

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

for all values '''y''' (except the '''undefined''' value, which all functions, being [[strict function|strict]], map into itself). Next there are the three principal functionals of FP:

* 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)

'''composition''' '''f'''&#x&#176;'''g''' where '''f'''&#x&#176;'''g''':'''x''' = '''f''':('''g''':'''x''')

[[Category:Academic programming languages]]

'''construction''' ['''f'''₁,...'''f'''_n] where ['''f'''₁,...'''f'''_n]:'''x''' = '''<''' '''f'''₁:'''x''',...,'''f'''_n:'''x''' '''>'''

[[Category:Function-level languages]]

[[Category:Programming languages created in 1977]]