![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to manCh1.rno CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / share / doc / ps2 / 07.fp|
Return to manCh1.rno CVS log | Up to [CSRG BSD Unix] / 43BSDReno / share / doc / ps2 / 07.fp |
1.1 root 1: .\" Copyright (c) 1980 Regents of the University of California.
2: .\" All rights reserved. The Berkeley software License Agreement
3: .\" specifies the terms and conditions for redistribution.
4: .\"
5: .\" @(#)manCh1.rno 6.1 (Berkeley) 4/29/86
6: .\"
7: .sp
8: .NS 1 "Background"
9: .sp
10: .pp
11: \fBFP\fP stands for a \fIFunctional Programming\fP language.
12: Functional programs
13: deal with \fIfunctions\fP instead of \fIvalues\fP.
14: There is no explicit representation of state, there are
15: no assignment statments, and hence,
16: no variables.
17: Owing to the lack of state, FP functions are free from
18: side-effects; so we
19: say the FP is \fIapplicative\fP.
20: .pp
21: All functions take one argument and they are evaluated using
22: the single FP
23: operation, \fIapplication\fP (the colon ':' is the apply operator).
24: For example, we read $~+^:^<3~4>~$ as \*(lqapply
25: the function '+' to its argument <3 4>\*(rq.
26: .pp
27: Functional programs express a functional-level combination of
28: their components
29: instead of describing state changes using value-oriented
30: expressions.
31: For example, we write the function returning the
32: \fIsin\fP of the \fIcos\fP
33: of its input, \*(IE $sin(cos(x))$, as:
34: $sin^@^cos$. This is a \fIfunctional expression\fP, consisting
35: of the single \fIcombining form\fP called \fIcompose\fP ('@'
36: is the compose operator)
37: and its \fIfunctional arguments\fP \fIsin\fP and \fIcos\fP.
38: .pp
39: All combining forms take functions as arguments and return
40: functions as results; functions may either be applied,
41: \*(EG
42: $sin @ cos^:^3$, or used as a functional argument in another functional
43: expression, \*(EG \fItan @ sin @ cos\fP.
44: .pp
45: As we have seen,
46: FP's combining forms allow us to express
47: control abstractions without the use of variables.
48: The \fIapply to all\fP functional form (&)
49: is another case in point. The function '& exp'
50: exponentiates all the elements of its argument:
51: .sp 4p
52: .EQ I (1.1)
53: "&exp : <1.0 2.0>" ~==~ "<2.718 7.389>"
54: .EN
55: .sp 4p
56: In (1.1)
57: there are
58: no induction variables, nor a
59: loop bounds specification.
60: Moreover, the code is useful for any size argument,
61: so long as the sub-elements of its argument conform to the domain of the
62: \fIexp\fP function.
63: .pp
64: We must change our view of the programming process
65: to adapt to the functional
66: style.
67: Instead of writing down a set of steps that manipulate and assign values,
68: we compose functional expressions
69: using
70: the higher-level functional forms.
71: For example, the function that adds a
72: scalar to all elements of a vector will be written in two steps. First,
73: the function that distributes the scalar amongst each element
74: of the vector:
75: .sp 4p
76: .EQ I (1.2)
77: "distl : <3 <4 6>>" ~==~ "<<3 4> <3 6>>"
78: .EN
79: .sp 4p
80: Next, the function that adds the pairs of elements that
81: make up a sequence:
82: .sp 4p
83: .EQ I (1.3)
84: "&+ : <<3 4> <3 6>>" ~==~ "<7 9>"
85: .EN
86: .sp 4p
87: .pp
88: In a value-oriented programming language the computation
89: would be expressed as:
90: .sp 4p
91: .EQ I (1.4)
92: "&+ : distl : <3 <4 6>>,"
93: .EN
94: .sp 4p
95: which means to apply 'distl' to the input and then to apply '+'
96: to every element of the result.
97: In FP we write (1.4) as:
98: .sp 4p
99: .EQ I (1.5)
100: "&+ @ distl : <3 <4 6>>."
101: .EN
102: .sp 4p
103: The functional expression of (1.5) replaces
104: the two step value expression of (1.4).
105: .pp
106: Often,
107: functional expressions are built from the inside out,
108: as in LISP.
109: In the next example we derive a function that scales then
110: shifts a vector, \*(IE for scalars $a,~b^$ and a vector $v vec$,
111: compute $a~+~b v vec$. This FP function will have three
112: arguments, namely $a,~b~$ and $~v vec$. Of course, FP
113: does not use formal parameter names, so
114: they will be designated by the function symbols 1, 2, 3.
115: The first code segment scales $v vec~$ by $b$ (defintions
116: are delimited with curly braces '{}'):
117: .sp 4p
118: .EQ I (1.6)
119: "{scaleVec &\(** @ distl @ [2,3]}"
120: .EN
121: .sp 4p
122: The code segment in (1.5)
123: shifts the vector.
124: The completed function is:
125: .sp 4p
126: .EQ I (1.7)
127: "{changeVec &+ @ distl @ [1 , scaleVec]}"
128: .EN
129: .pp
130: In the derivation of the program we wrote from right to left,
131: first doing the \fIdistl\fP's and then composing with the
132: \fIapply-to-all\fP functional form.
133: Using an imperative language, such as Pascal,
134: we would write the program from
135: the outside in, writing the loop
136: before inserting the arithmetic operators.
137: .pp
138: Although
139: FP encourages a recursive programming style,
140: it provides combining forms to avoid explicit recursion.
141: For example, the
142: right insert combining form (!)
143: can be used to write a function
144: that adds up a list of numbers:
145: .sp 4p
146: .EQ I (1.8)
147: "!+ : <1 2 3>" ~==~ 6
148: .EN
149: .pp
150: The equivalent, recursive function is much longer:
151: .sp 4p
152: .EQ I (1.9)
153: "{addNumbers (null -> %0 ; + @ [1, addNumbers @ tl])}"
154: .EN
155: .pp
156: The generality of the combining forms encourages hierarchical
157: program development. Unlike APL,
158: which restricts
159: the use of combining forms to certain builtin functions,
160: FP allows combining forms to take any functional expression as
161: an argument.
162: .bp
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.