![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to manCh2.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 manCh2.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: .\" @(#)manCh2.rno 6.1 (Berkeley) 4/29/86
6: .\"
7: .NS 1 "System Description"
8: .sp
9: .NS 2 "Objects"
10: .sp
11: .pp
12: The set of objects \(*W consists of
13: the atoms and sequences $fs$ (where the $x sub i memberOf OMEGA$).
14: (Lisp users should note the similarity to the list structure syntax,
15: just replace the parenthesis
16: by angle brackets and commas by blanks. There are no 'quoted' objects,
17: \*(IE 'abc).
18: The atoms uniquely determine the set of valid objects and consist of the
19: numbers (of the type found in \s-2FRANZ LISP\s+2 [Fod80]), quoted ascii strings
20: ("abcd"), and unquoted alphanumeric strings (abc3).
21: There are three predefined atoms, $T$ and $F$, that correspond
22: to the logical values 'true' and 'false', and the undefined atom $bold "?"$,
23: \fIbottom\fP.
24: \fIBottom\fP denotes the value returned as the result of an
25: undefined operation, \*(EG division by zero.
26: The empty sequence, $<>$ is also an atom. The following are examples
27: of valid FP objects:
28: .sp 2
29: .(b C
30: .TS
31: center;
32: l l l.
33: $?$ $1.47$ $3888888888888$
34: $ab$ "$CD$" $<1,<2,3>>$
35: $<>$ $T$ $<a,<>>$
36: .TE
37: .)b
38: .sp 2
39: There is one restriction on object construction: no object may contain
40: the undefined atom, such an object is itself undefined, \*(EG
41: $<1,?>~==~?$. This property is the
42: so-called \*(lqbottom preserving property\*(rq [Ba78].
43: .sp
44: .NS 2 "Application"
45: .sp
46: .pp
47: This is the single FP operation and is designated by the colon (":").
48: For a function $sigma$ and an object $x$, $sigma : x$ is an application
49: and its meaning is the object that results from applying $sigma$ to
50: $x$ (\*(IE evaluating $sigma (x)$).
51: We say that $sigma$ is the \fIoperator\fP and that $x$ is
52: the \fIoperand\fP.
53: The following are examples of applications:
54: .sp 2
55: .TS
56: center;
57: l c l l c l.
58: $bold + : <7,8>$ $==$ $15$ $bold tl :<1,2,3>$ $==$ $<2,3>$
59: \fB1\fP $: <a,b,c,d>$ $==$ $a$ \fB2\fP $: <a,b,c,d>$ $==$ $b$
60: .TE
61: .sp 2
62: .nr ii 0.35i
63: .NS 2 "Functions"
64: .sp
65: .pp
66: All functions (\fIF\fP) map objects into objects, moreover, they are
67: \fIstrict\fP:
68: .sp 6p
69: .EQ I (2.1)
70: sigma^:^? equiv ?,~~ forAll ^sigma^ memberOf F
71: .EN
72: .sp 6p
73: To formally characterize the primitive functions,
74: we use a modification of McCarthy's conditional expressions [Mc60]:
75: .sp 6p
76: .EQ I (2.2)
77: p sub 1~->~ e sub 1~; ... ;~p sub n~->~ e sub n~;~e sub {n + 1}
78: .EN
79: .sp 6p
80: This statement is interpreted as follows:
81: return function $e sub 1$ if the predicate '$p sub 1$' is
82: true $,...,~e sub n$ if '$p sub n$' is true.
83: If none of the predicates are satisfied then default to $e sub {n + 1}$.
84: It is assumed that $x ,~x sub i ,~y ,~y sub i ,~z sub i memberOf OMEGA$.
85: .sp
86: .NS 3 "Structural"
87: .sp
88: .b "Selector Functions"
89: .(b M F
90: .sp
91: For a nonzero integer $mu$,
92: .sp
93: .nf
94: .ip "$bold mu~ : ~x~ ==$"
95: .sp 4p
96: \&$x = fs ~ andsign ~0~<~mu~<=~k ~->~ x sub mu ;$
97: .sp 4p
98: \&$x = fs ~ andsign ~-k <= mu < 0 ~ -> ~ x sub {k + mu + 1}; ~ ?$
99: .fi
100: .)b
101: .sp
102: .(b
103: .nf
104: .ip "$bold pick~ : ~<n,x>~ ==$"
105: .sp 4p
106: \&$x = fs ~ andsign ~0~<~n~<=~k ~->~ x sub n ;$
107: .sp 4p
108: \&$x = fs ~ andsign ~-k <= n < 0 ~ -> ~ x sub {k + n + 1}; ~ ?$
109: .fi
110: .)b
111: .sp 2
112: .pp
113: The user should note that the function
114: symbols \fB1\fP,\fB2\fP,\fB3\fP$,...$ are
115: to be distinguished from the atoms $1,2,3,...$.
116: .(b M F
117: .sp
118: .ip "$bold last ~ : ~x~ ==$"
119: .sp 4p
120: \&$x = <> ~ -> ~ <> ~ ;$
121: .sp 4p
122: \&$x = fs ~ andsign ~ k >= 1 ~ -> ~ x sub k ;~?$
123: .)b
124: .(b M F
125: .sp
126: .ip "$bold first ~ : ~x~ ==$"
127: .sp 4p
128: \&$x = <> ~ -> ~ <> ~ ;$
129: .sp 4p
130: \&$x = fs ~ andsign ~ k >= 1 ~ -> ~ x sub 1 ;~?$
131: .)b
132: .sp
133: .(b M F
134: .b "Tail Functions"
135: .sp
136: .ip "$bold tl ~:~x ~==$"
137: .sp 4p
138: \&$x = <x sub 1 > ~ -> ~ <> ~ ;$
139: .sp 4p
140: \&$x = fs ~ andsign ~ k >= ~ 2 ~ -> ~<x sub 2 ~,..., ~x sub k > ~ ;~ ?$
141: .)b
142: .sp 6p
143: .(b M F
144: .ip "$bold tlr ~ : ~ x~==$"
145: .sp 4p
146: \&$x = <x sub 1 > ~ -> ~ <> ~ ;$
147: .sp 4p
148: \&$x = fs ~ andsign ~ k >= ~ 2 ~ -> ~ <x sub 1 ~ ,..., ~x sub {k - 1} > ~ ; ~ ?$
149: .)b
150: .sp
151: .pp
152: Note: There is also a function
153: \fBfront\fP that is equivalent to \fBtlr\fP.
154: .sp
155: .(b M F
156: .b "Distribute from left and right"
157: .sp
158: .ip "$bold distl ~:~x~==$"
159: .sp 4p
160: \&$x = <y,<>>~->~<>;$
161: .sp 4p
162: \&$x = <y, qz >~->~<<y,z sub 1 >,...,<y,z sub k >>;~?$
163: .)b
164: .sp 6p
165: .(b M F
166: .ip "$bold distr ~:~x~==$"
167: .sp 4p
168: \&$x = <<>,y>~->~<>;$
169: .sp 4p
170: \&$x = < qy , z >~->~<<y sub 1 , z >,...,<y sub k , z >>;~?$
171: .)b
172: .sp 6p
173: .(b M F
174: .b "Identity"
175: .sp 6p
176: $bold id ~:~x~==~x$
177: .)b
178: .sp 6p
179: $bold out ~:~x~==~x$
180: .pp
181: \fBOut\fP is similar to \fPid\fP.
182: Like \fBid\fP it returns its argument as the result,
183: unlike \fPid\fP
184: it prints its
185: result on \fIstdout\fP \(mi
186: It is the only function with a side effect.
187: \fPOut\fP is intended to be used for debugging only.
188: .sp
189: .(b M F
190: .b "Append left and right"
191: .sp
192: .nf
193: .ip "$bold apndl ~:~x~==$"
194: .sp 4p
195: \&$x = <y,<>>~->~<y>;$
196: .sp 4p
197: \&$x = <y, qz >~->~<y, z sub 1 ,~ z sub 2 ,...,~ z sub k >;~?$
198: .)b
199: .sp 6p
200: .(b M F
201: .ip "$bold apndr ~:~x~==$"
202: .sp 4p
203: \&$x = <<>,z>~->~<z>;$
204: .sp 4p
205: \&$x = < qy , z >~->~< y sub 1 ,~ y sub 2 ,...,~ y sub k ,~z >;~?$
206: .fi
207: .)b
208: .sp
209: .(b M F
210: .b "Transpose"
211: .sp
212: .nf
213: .ip "$bold trans~:~x~==$"
214: .sp 4p
215: \&$x = <<>,...,<>>~->~<>;$
216: .sp 4p
217: \&$x = fs ~->~<y sub 1 ,..., y sub m >;~?$
218: .sp 8p
219: \&where $x sub i ~=~<x sub i1 ,..., x sub im >~andsign
220: ~ y sub j ~=~<x sub 1j ,..., x sub kj >,$
221: .sp 4p
222: \&$1<=i<=k ~,~ 1<=j<=m.$
223: .)b
224: .sp
225: .fi
226: .(b M F
227: .ip "$bold reverse~:~x~==~$"
228: .sp 4p
229: \&$x =<>~ ->;$
230: .sp 4p
231: \&$x = fs ~->~ <x sub k ,..., x sub 1 >;~?$
232: .)b
233: .sp
234: .(b M F
235: .b "Rotate Left and Right"
236: .sp
237: .nf
238: .ip "$bold rotl~:~x~==$"
239: .sp 4p
240: \&$x = <>~ -> ~ <>;~x = <x sub 1 >~->~<x sub 1 >;$
241: .sp 4p
242: \&$x = fs ~ andsign ~k >= 2~ -> ~ <x sub 2 ,..., x sub k , x sub 1 >;~?$
243: .)b
244: .sp
245: .(b M F
246: .ip "$bold rotr~:x~==$"
247: .sp 4p
248: \&$x = <>~ -> ~ <>;~x = <x sub 1 >~->~<x sub 1 >;$
249: .sp 4p
250: \&$x = fs ~ andsign ~k >= 2~ -> ~
251: <x sub k ,~ x sub 1 ,..., x sub {k - 2},~ x sub {k - 1} >;~?$
252: .)b
253: .fi
254: .sp 2
255: .(b M F
256: .nf
257: .ip "$bold concat~:~x~==$"
258: .sp 4p
259: \&$x = <<x sub 11 ,..., x sub 1k >,<x sub 21 ,..., x sub 2n >
260: ,...,<x sub m1 ,..., x sub mp >> ~ andsign ~ k, ~m, ~n, ~p ~>~ 0 ~->$
261: \&$<x sub 11 ,..., x sub 1k , x sub 21 ,..., x sub 2n ,..., x sub m1 ,..., x sub mp >; ?$
262: .)b
263: .sp
264: .(b M F
265: .pp
266: Concatenate removes all occurrences of the null sequence:
267: .sp
268: .EQ I (2.3)
269: bold concat ~ :~ <<1,3>,<>,<2,4>,<>,<5>> ~==~ <1,3,2,4,5>
270: .EN
271: .)b
272: .sp
273: .(b M F
274: .ip "$bold pair~:~x~==$"
275: .sp 4p
276: \&$x = fs ~ andsign ~ k >0 ~ andsign ~ k~is~even~->~ <<x sub 1 , x sub 2 >
277: ,..., <x sub k-1 , x sub k >>;$
278: .sp 4p
279: \&$x = fs ~ andsign ~ k >0 ~ andsign ~ k~is~odd~->~ <<x sub 1 , x sub 2 >
280: ,..., <x sub k >>;~?$
281: .)b
282: .sp
283: .(b M F
284: .ip "$bold split~:~x~==$"
285: .sp 4p
286: \&$x = <x sub 1 > ~->~<<x sub 1 > , <>>;$
287: .sp 4p
288: \&$x = fs ~ andsign ~ k > 1 ~ ->
289: ~<<x sub 1 ,..., x sub {left ceiling k/2 right ceiling} >,
290: <x sub {left ceiling k/2 right ceiling + 1} ,..., x sub k >>; ?$
291: .)b
292: .sp
293: .(b M F
294: .ip "\fBiota\fP$~:x~==$"
295: .sp 4p
296: \&$x = 0 ~->~ <>;$
297: .sp 4p
298: \&$x memberOf bold {N sup +} ~ ->~<1,2,...,x>;~?$
299: .)b
300: .sp
301: .NS 3 "Predicate (Test) Functions"
302: .sp
303: $bold atom~:~x~==~x~ memberOf atoms~-> ~ T ; ~ x$\(!=$? -> ~ F ;~ ?$
304: .sp
305: $bold eq ~:~x~==~x~=<y,z> ~ andsign ~ y=z ~ -> ~ T ;~x= <y,z> ~ andsign ~y$ \(!= $z ~->~ F ;~?$
306: .sp
307: .pp
308: Also less than ($bold <$), greater than ($bold >$),
309: greater than or equal (\fB>=\fP),
310: less than or equal (\fB<=\fP), not equal (\fB~=\fP);
311: \&'$bold =$' is a synonym for \fBeq\fP.
312: .sp
313: $bold null ~ : x~==~x = <> ~ -> ~ T ;~x$\(!=$?~ -> ~ F ;~?$
314: .sp 6p
315: $bold length ~ :~ x~==~x~= ~ fs ~ -> ~ k; ~ x = <> ~ -> ~0; ~ ?$
316: .sp
317: .NS 3 "Arithmetic/Logical"
318: .sp
319: $bold +~:~ x ~ ==~ x = <y,z> ~ andsign ~y,z ~ are ~ numbers ~ ->~ y+z; ~ ?$
320: $bold -~:~ x ~ ==~ x = <y,z> ~ andsign ~y,z ~ are ~ numbers ~ -> ~y-z; ~ ?$
321: $bold *~:~ x ~ ==~ x = <y,z> ~ andsign ~y,z ~ are ~ numbers ~ -> ~y$\(mu$z; ~ ?$
322: \fB/\fP$~:~ x ~ ==~ x = <y,z> ~ andsign ~y,z ~ are ~ numbers ~ andsign
323: ~z$\(!= $0 ~ ->~y$\(di$z ;~?$
324: .sp
325: .b "And, or, not, xor"
326: .sp
327: $nd~:~<x,y>~==~x = T ~->~ y;~x= F ~->~ F ;~?$
328: .sp 8p
329: $rr~:~<x,y>~==~x = F ~->~ y;~x= T ~->~ T ;~?$
330: .sp 8p
331: .(b M F
332: .nf
333: .ip "$bold xor~:~<x,y>~==$"
334: .sp 4p
335: \&$x = T ~ andsign ~ y = T ~->~ F ;~ x = F ~ andsign ~ y = F ~->~ F ;$
336: .sp 4p
337: \&$x = T ~ andsign ~ y = F ~->~ T ;~ x = F ~ andsign ~ y = T ~->~ T ;~?$
338: .fi
339: .)b
340: .sp 6p
341: $bold not~:~x~==~x= T ~->~F;~x= F~->~T ;~?$
342: .NS 3 "Library Routines"
343: .sp
344: $bold "sin"~:~x~==~x roman {~is~a~number} ~->~sin(x);~?$
345: .sp 8p
346: $bold "asin"~:~x~==~x roman {~is~a~number}
347: ~andsign~|x|~<=~1 ~->~sin sup {-1} (x);~?$
348: .sp 8p
349: $bold "cos"~:~x~==~x roman {~is~a~number} ~->~cos(x);~?$
350: .sp 8p
351: $bold "acos"~:~x~==~x roman {~is~a~number}
352: ~andsign~|x|~<=~1 ~->~cos sup {-1} (x);~?$
353: .sp 8p
354: $bold "exp"~:~x~==~x roman {~is~a~number} ~->~ e sup x;~?$
355: .sp 8p
356: $bold "log"~:~x~==~x roman {~is~a~positive~number} ~->~ ln(x);~?$
357: .sp 8p
358: $bold "mod"~:~<x,y>~==~ x nd y roman {~are~numbers} ~->~ x ~-~ y times
359: left floor x over y right floor ~;~?$
360: .sx 2
361: .sp
362: .NS 2 "Functional Forms"
363: .pp
364: Functional forms define new \fIfunctions\fP
365: by operating on
366: function and object \fIparameters\fP of the form.
367: The resultant expressions
368: can be compared and contrasted to the \fIvalue\fP-oriented
369: expressions of traditional programming languages.
370: The distinction lies in the domain of
371: the operators; functional forms manipulate functions, while traditional
372: operators manipulate values.
373: .pp
374: One functional form is \fIcomposition\fP. For two functions $phi$ and
375: $psi$ the form $phi ~ @ ~psi$ denotes their composition $phi ~$\*(cm$~ psi$:
376: .sp 4p
377: .EQ I (2.4)
378: ( phi ~@~ psi )~:~x~==~phi :( psi :x),~~ forAll ~~x memberOf OMEGA
379: .EN
380: .sp
381: The \fIconstant\fP function takes an object parameter:
382: .sp
383: .EQ I (2.5)
384: %x:y~==~y=?~->~?;~x,~~~ forAll ~~x,y~ memberOf OMEGA
385: .EN
386: .sp
387: The function $%?$ always returns ?.
388: .pp
389: In the following description of the functional forms, we assume that
390: $xi , ~xi sub i ,~sigma , ~sigma sub i ,~tau ,$ and $tau sub i$
391: are functions and that
392: $x,~x sub i ,~ y$ are objects.
393: .sp 2
394: .b "Composition"
395: .sp
396: $( sigma ~@~ tau ):x~==~sigma : ( tau : x)$
397: .sp 2
398: .b "Construction"
399: .sp
400: $[ sigma sub 1 ,..., sigma sub n ]:x~==~< sigma sub 1 : x,..., sigma sub n : x>$
401: .sp
402: Note that construction is also bottom-preserving, \*(EG
403: .sp 6p
404: .EQ I (2.6)
405: [ bold +, bold /]^:^<3,0>~=~<3,?>~=~?
406: .EN
407: .sp 2
408: .(b M F
409: .b "Condition"
410: .sp
411: .ip "$( xi~"->" ~sigma ;~tau ):x~==~$"
412: .sp 4p
413: \&$( xi : x) = T~->~sigma : x;$
414: .sp 4p
415: \&$~ ( xi : x)= F~ ->~tau :x;~?$
416: .)b
417: .sp 8p
418: .pp
419: The reader should be aware of the distinction between
420: \fIfunctional expressions\fP, in the variant of McCarthy's conditional
421: expression,
422: and the \fIfunctional form\fP introduced here.
423: In the former case the result is a \fIvalue\fP, while in the latter case
424: the result is a \fIfunction\fP. Unlike Backus' FP, the conditional form
425: \fImust\fP be enclosed in parenthesis, \*(EG
426: .sp 6p
427: .EQ I (2.7)
428: roman {"(isNegative -> - @ [%0,id] ; id")}
429: .EN
430: .sp
431: .(b M F
432: .b "Constant"
433: .sp
434: $%x:y~==~y=?~->~?;~x,~~~~~~ forAll ~x memberOf OMEGA$
435: .sp
436: .)b
437: This function returns its object parameter as its result.
438: .sp
439: .(b M F
440: .b "Right Insert"
441: .sp 6p
442: .nf
443: .ip "$! bold sigma~:x~==$"
444: .sp 4p
445: \&$x = <>~->~e sub f : x;$
446: .sp 4p
447: \&$x=<x sub 1 >~->~x sub 1 ;$
448: .sp 4p
449: \&$x= fs ~ andsign ~k>2~->~ sigma :<x sub 1 ,~! sigma :<x sub 2 ,...,~x sub k >>;~?$
450: .sp 10p
451: \&\*(EG $!+:<4,5,6> =15$.
452: .)b
453: .pp
454: If $sigma$ has a right identity element $e sub f$,
455: then $! sigma :<>~=~ e sub f$, \*(EG
456: .sp 6p
457: .EQ I (2.8)
458: !+^:^<> =0 ~roman "and" ~!*^:^<> =1
459: .EN
460: .sp
461: Currently,
462: identity functions are defined for $+ \ (0),\ - \ (0), \ * \ (1),
463: \ / \ (1)$,
464: also for \fBand\fP (T), \fBor\fP (F), \fBxor\fP (F). All other unit functions
465: default to bottom (?).
466: .sp
467: .(b M F
468: .b "Tree Insert"
469: .sp 6p
470: .ip " \fB|\fP $sigma~:~x~==$"
471: .sp 4p
472: \&$x = <>~->~e sub f : x;$
473: .sp 4p
474: \&$x=<x sub 1 >~->~x sub 1 ;$
475: .sp 4p
476: .nf
477: \&$x= fs ~ andsign ~k>1~->$
478: .sp 4p
479: \&$bold sigma ~:~< $\fB|\fP$~ sigma~:~
480: <x sub 1 ,..., x sub {left ceiling k/2 right ceiling} >~,~
481: "\fB|\fP" ~ sigma ~:~<x sub {left ceiling k/2 right ceiling + 1}
482: ,..., x sub k >>; ?$
483: .sp 10p
484: \&\*(EG
485: .EQ I (2.9)
486: "\fB|\fP" +:<4,5,6,7> ~==~ +:<+:<4,5> , +:<6,7>> ~==~ 15
487: .EN
488: .sp
489: .fi
490: .)b
491: .sp
492: .pp
493: Tree insert uses the same identity functions as right
494: insert.
495: .sp
496: .b "Apply to All"
497: .sp
498: .ip "\fB&\fP$^sigma :~x~==$"
499: .sp 4p
500: \&$x=<>~-><>;$
501: .sp 4p
502: \&$x= fs~->~< sigma : x sub 1 ,...,~sigma : x sub k >;~?$
503: .sp
504: .(b M F
505: .b "While"
506: .sp
507: .ip "(\fBwhile\fP$ ~xi~sigma ):x~==$"
508: \&$xi : x= T~->~($\fBwhile\fP$ ~xi~sigma ):( sigma : x);$
509: .sp 4p
510: \&$xi : x= F~->~x;~?$
511: .)b
512: .sp
513: .NS 2 "User Defined Functions"
514: .pp
515: An FP definition is entered as follows:
516: .sp 6p
517: .EQ I (2.10)
518: "{fn-name fn-form},"
519: .EN
520: .sp
521: where \fIfn-name\fP is an ascii string consisting of letters, numbers and the
522: underline symbol, and \fIfn-form\fP is any valid functional form, including
523: a single primitive or defined function.
524: For example the function
525: .sp
526: .EQ I (2.11)
527: "{factorial !* @ iota}"
528: .EN
529: .sp
530: .pp
531: is the non-recursive definition of
532: the factorial function. Since FP systems are applicative it is permissible
533: to substitute the actual definition of a function for any reference to it
534: in a functional form: if $f ~==~ 1 @ 2$ then $f~:~x~==~1@2~:~x,~~~
535: forAll ~x memberOf OMEGA$.
536: .pp
537: References to undefined functions bottom out:
538: .sp
539: .EQ I (2.12)
540: f:x~==~? forAll x memberOf OMEGA ,~f^ notmemberof F
541: .EN
542: .sx 1
543: .bp
544:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.