![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to manCh5.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 manCh5.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: .\" @(#)manCh5.rno 6.1 (Berkeley) 4/29/86
6: .\"
7: .NS 1 "Programming Examples"
8: .pp
9: We will start off by developing a larger FP program, \fImergeSort\fP.
10: We measure \fImergeSort\fP using the trace package, and then we
11: comment on the measurements.
12: Following \fImergeSort\fP
13: we show an actual session at the terminal.
14: .NS 2 "MergeSort"
15: .pp
16: The source code for
17: \fImergeSort\fP is:
18: .(b
19: .sp 4p
20: .hl
21: .sp 4p
22: .(c
23: # Use a divide and conquer strategy
24: .sp 3p
25: {mergeSort $^"\fB|\fP"^$ merge}
26: .sp 6p
27: {merge atEnd @ mergeHelp @ [[], fixLists]}
28: .sp 6p
29: # Must convert atomic arguments into sequences
30: # Atomic arguments occur at the leaves of the execution tree
31: .sp 3p
32: {fixLists &(atom -> [id] ; id)}
33: .sp 6p
34: # Merge until one or both input lists are empty
35: .sp 3p
36: {mergeHelp (while \kxand @ &(not@null) @ 2
37: \h'\nxu'(firstIsSmaller -> \kytakeFirst ;
38: \h'\nyu'takeSecond))}
39: .sp 6p
40: # Find the list with the smaller first element
41: .sp 3p
42: {firstIsSmaller < @ [1@1@2, 1@2@2]}
43: .sp 6p
44: # Take the first element of the first list
45: .sp 3p
46: {takeFirst [apndr@[1,1@1@2], [tl@1@2, 2@2]]}
47: .sp 6p
48: # Take the first element of the second list
49: .sp 3p
50: {takeSecond [apndr@[1,1@2@2], [1@2, tl@2@2]]}
51: .sp 6p
52: # If one list isn't null, then append it to the
53: # end of the merged list
54: .sp 3p
55: {atEnd (firstIsNull -> \kzconcat@[1,2@2] ;
56: \h'\nzu'concat@[1,1@2])}
57: .sp 6p
58: {firstIsNull null@1@2}
59: .)c
60: .sp 4p
61: .hl
62: .sp 4p
63: .)b
64: .pp
65: The merge sort algorithm uses a divide and conquer strategy;
66: it splits the input in half, recursively sorts each half,
67: and then merges the sorted lists.
68: Of course, all these sub-sorts can execute
69: in parallel, and the
70: tree-insert ($"\fB|\fP" $) functional form expresses this
71: concurrency. \fIMerge\fP removes successively larger elements
72: from the heads of the
73: two lists (either \fItakeFirst\fP or \fItakeSecond\fP)
74: and appends these elements to the end of the merged sequence.
75: \fIMerge\fP terminates when
76: one sequence is empty, and then
77: \fIatEnd\fP appends
78: any remaining non-empty sequence
79: to the end of the merged one.
80: .CH "Dynamic Statistics"
81: .pp
82: On the next page we
83: give the trace of the function \fImerge\fP, which information
84: we can use to determine the structure of
85: \fImerge\fP's execution tree.
86: Since the tree is well-balanced,
87: many of the \fImerge\fP's
88: could be executed in parallel.
89: Using this trace we
90: can also calculate
91: the average length of the
92: arguments passed to \fImerge\fP, or a distribution of argument lengths.
93: This information is useful for
94: determining communication costs.
95: .(b
96: .nf
97: .sp 4p
98: .nf
99: .hl
100: .sp 4p
101: .(c
102: )trace on merge
103:
104: mergeSort\ :\ <0\ 3\ -2\ 1\ 11\ 8\ -22\ -33>
105: |\ 3\ >Enter>\ merge\ [<0\ 3>]
106: |\ 3\ <EXIT<\ \ merge\ \ <0\ 3>
107: |\ 3\ >Enter>\ merge\ [<-2\ 1>]
108: |\ 3\ <EXIT<\ \ merge\ \ <-2\ 1>
109: |2\ >Enter>\ merge\ [<<0\ 3>\ <-2\ 1>>]
110: |2\ <EXIT<\ \ merge\ \ <-2\ 0\ 1\ 3>
111: |\ 3\ >Enter>\ merge\ [<11\ 8>]
112: |\ 3\ <EXIT<\ \ merge\ \ <8\ 11>
113: |\ 3\ >Enter>\ merge\ [<-22\ -33>]
114: |\ 3\ <EXIT<\ \ merge\ \ <-33\ -22>
115: |2\ >Enter>\ merge\ [<<8\ 11>\ <-33\ -22>>]
116: |2\ <EXIT<\ \ merge\ \ <-33\ -22\ 8\ 11>
117: 1\ >Enter>\ merge\ [<<-2\ 0\ 1\ 3>\ <-33\ -22\ 8\ 11>>]
118: 1\ <EXIT<\ \ merge\ \ <-33\ -22\ -2\ 0\ 1\ 3\ 8\ 11>
119:
120: <-33\ -22\ -2\ 0\ 1\ 3\ 8\ 11>
121: .)c
122: .sp 4p
123: .hl
124: .fi
125: .)b
126: .bp
127: .NS 2 "FP Session"
128: .pp
129: User input is
130: \fBemboldened\fP, terminal output in Roman script.
131: .sp 0.5i
132: .nf
133: \fBfp\fP
134:
135: FP, v. 4.1 11/31/82
136: \fB )load ex_man\fP
137: {all_le}
138: {sort}
139: {abs_val}
140: {find}
141: {ip}
142: {mm}
143: {eq0}
144: {fact}
145: {sub1}
146: {alt_fnd}
147: {alt_fact}
148: \fB )fns\fP
149:
150: .TS
151: l l l l l l l.
152: abs_val all_le alt_fact alt_fnd eq0 fact find
153: ip mm sort sub1 \& \& \&
154: .TE
155:
156: \fB abs_val : 3\fP
157:
158: 3
159:
160: \fB abs_val : -3\fP
161:
162: 3
163:
164: \fB abs_val : 0\fP
165:
166: 0
167:
168: \fB abs_val : <-5 0 66>\fP
169:
170: ?
171:
172: \fB &abs_val : <-5 0 66>\fP
173:
174: <5 0 66>
175:
176: \fB )pfn abs_val\fP
177:
178: {abs_val ((> @ [id,%0]) -> id ; (- @ [%0,id]))}
179:
180: \fB [id,%0] : -3\fP
181:
182: <-3 0>
183:
184: \fB [%0,id] : -3\fP
185:
186: <0 -3>
187:
188: \fB - @ [%0,id] : -3\fP
189:
190: 3
191:
192: \fB all_le : <1 3 5 7>\fP
193:
194: T
195:
196: \fB all_le : <1 0 5 7>\fP
197:
198: F
199:
200: \fB )pfn all_le\fP
201:
202: {all_le ! and @ &<= @ distl @ [1,tl]}
203:
204: \fB distl @ [1,tl] : <1 2 3 4>\fP
205:
206: <<1 2> <1 3> <1 4>>
207:
208: \fB &<= @ distl @ [1,tl] : <1 2 3 4>\fP
209:
210: <T T T>
211:
212: \fB ! and : <F T T>\fP
213:
214: F
215:
216: \fB ! and : <T T T>\fP
217:
218: T
219:
220: \fB sort : <3 1 2 4>\fP
221:
222: <1 2 3 4>
223:
224: \fB sort : <1>\fP
225:
226: <1>
227:
228: \fB sort : <>\fP
229:
230: ?
231:
232: \fB sort : 4\fP
233:
234: ?
235:
236: \fB )pfn sort\fP
237:
238: {sort (null @ tl -> [1] ; (all_le -> apndl @ [1,sort@tl]; sort@rotl))}
239:
240: \fB fact : 3\fP
241:
242: 6
243:
244: \fB )pfn fact sub1 eq0\fP
245:
246: {fact (eq0 -> %1 ; *@[id , fact@sub1])}
247:
248: {sub1 -@[id,%1]}
249:
250: {eq0 = @ [id,%0]}
251:
252: \fB &fact : <1 2 3 4 5>\fP
253:
254: <1 2 6 24 120>
255:
256: \fB eq0 : 3\fP
257:
258: F
259:
260: \fB eq0 : <>\fP
261:
262: F
263:
264: \fB eq0 : 0\fP
265:
266: T
267:
268: \fB sub1 : 3\fP
269:
270: 2
271:
272: \fB %1 : 3\fP
273:
274: 1
275:
276: \fB alt_fact : 3\fP
277:
278: 6
279:
280: \fB )pfn alt_fact\fP
281:
282: {alt_fact !* @ iota}
283:
284: \fB iota : 3\fP
285:
286: <1 2 3>
287:
288: \fB !* @ iota : 3\fP
289:
290: 6
291:
292: \fB !+ : <1 2 3>\fP
293:
294: 6
295:
296: \fB find : <3 <3 4 5>>\fP
297:
298: T
299:
300: \fB find : <<> <3 4 <>>>\fP
301:
302: T
303:
304: \fB find : <3 <4 5>>\fP
305:
306: F
307:
308: \fB )pfn find\fP
309:
310: {find (null@2 -> %F ; (=@[1,1@2] -> %T ; find@[1,tl@2]))}
311:
312: \fB [1,tl@2] : <3 <3 4 5>>\fP
313:
314: <3 <4 5>>
315:
316: \fB [1,1@2] : <3 <3 4 5>>\fP
317:
318: <3 3>
319:
320: \fB alt_fnd : <3 <3 4 5>>\fP
321:
322: T
323:
324: \fB )pfn alt_fnd\fP
325:
326: {alt_fnd ! or @ &eq @ distl }
327:
328: \fB distl : <3 <3 4 5>>\fP
329:
330: <<3 3> <3 4> <3 5>>
331:
332: \fB &eq @ distl : <3 <3 4 5>>\fP
333:
334: <T F F>
335:
336: \fB !or : <T F T>\fP
337:
338: T
339:
340: \fB !or : <F F F>\fP
341:
342: F
343:
344: \fB )delete alt_fnd\fP
345:
346: \fB )fns\fP
347:
348: .TS
349: l l l l l l l.
350: abs_val all_le alt_fact eq0 fact find ip
351: mm sort sub1 \& \& \& \&
352: .TE
353:
354: \fB alt_fnd : <3 <3 4 5>>\fP
355:
356: alt_fnd not defined
357:
358: ?
359: \fB {g g}\fP
360:
361: {g}
362: \fB g : 3\fP
363:
364: non-terminating
365:
366: ?
367:
368: [Return to top level]
369:
370: FP, v. 4.0 10/8/82
371: \fB [+,*] : <3 4>\fP
372:
373: <7 12>
374:
375: .(b
376: \fB [+,* : <3 4>\fP
377:
378: syntax error:
379:
380: [+,* \kx: <3 4>
381: \h'\nxu'^
382: .)b
383: \fB ip : <<3 4 5> <5 6 7>>\fP
384:
385: 74
386:
387: \fB )pfn ip\fP
388:
389: {ip !+ @ &* @ trans}
390:
391: \fB trans : <<3 4 5> <5 6 7>>\fP
392:
393: <<3 5> <4 6> <5 7>>
394:
395: \fB &* @ trans : <<3 4 5> <5 6 7>>\fP
396:
397: <15 24 35>
398:
399: \fB mm : <<<1 0> <0 1>> <<3 4> <5 6>>>\fP
400:
401: <<3 4> <5 6>>
402:
403: \fB )pfn mm\fP
404:
405: {mm &&ip @ &distl @ distr @[1,trans@2]}
406:
407: \fB [1,trans@2] : <<<1 0> <0 1>> <<3 4> <5 6>>>\fP
408:
409: <<<1 0> <0 1>> <<3 4> <5 6>>>
410:
411: \fB distr : <<<1 0> <0 1>> <<3 4> <5 6>>>\fP
412:
413: <<<1 0> <<3 4> <5 6>>> <<0 1> <<3 4> <5 6>>>>
414:
415: \fB &distl : <<<1 0> <<3 4> <5 6>>> <<0 1> <<3 4> <5 6>>>>\fP
416:
417: <<<<1 0> <3 4>> <<1 0> <5 6>>> <<<0 1> <3 4>> <<0 1> <5 6>>>>
418:
419: .(b
420: \fB &ip @ &dist & distr @ [1,trans @ 2] : <<<1 0> <0 1>> <<3 4> <5 6>>>\fP
421:
422: syntax error:
423:
424: [+,* \kx: <3 4>
425: \h'\nxu'^
426: &ip @ &distl \kx& distr @ [1,trans @ 2] : <<<1 0> <0 1>> <<3 4> <5 6>>>
427: \h'\nxu'^
428: .)b
429: \fB &ip @ &distl @ distr @ [1,trans@2] : <<<1 0> <0 1>> <<3 4> <5 6>>>\fP
430:
431: ?
432: .sp 2
433: .fi
434: .bp
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.