FP (programming language): Difference between revisions

Revision as of 03:13, 28 December 2005

Revision as of 17:59, 26 July 2006

Line 5:

The '''values''' that FP programs map into one another comprise a [[set]] which is [[closed]] under '''sequence formation''':

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

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

Line 21:

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

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

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''' = ⊥⊥

==Functionals==

These are the core functionals of FP:

'''constant''' '''x̄x̄''' where '''x̄x̄''':'''y''' = '''x'''

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

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

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

'''''i''''':&lang;〈'''x'''₁,...,'''x'''_n&rang;〉 = '''x'''_i if 0 < '''''i''''' &le;≤ n

= &#8869;⊥ otherwise

==See also==