Copyright (c) 1980 The Regents of the University of California.
All rights reserved.
%sccs.include.redist.roff%
@(#)manCh5.rno 6.2 (Berkeley) 04/17/91
.NS 1 "Programming Examples" .pp We will start off by developing a larger FP program, mergeSort. We measure mergeSort using the trace package, and then we comment on the measurements. Following mergeSort we show an actual session at the terminal. .NS 2 "MergeSort" .pp The source code for mergeSort is: .(b .hl .(c # Use a divide and conquer strategy {mergeSort $^"|"^$ merge} {merge atEnd @ mergeHelp @ [[], fixLists]} # Must convert atomic arguments into sequences # Atomic arguments occur at the leaves of the execution tree {fixLists &(atom -> [id] ; id)} # Merge until one or both input lists are empty {mergeHelp (while \kxand @ &(not@null) @ 2 \h'\nxu'(firstIsSmaller -> \kytakeFirst ; \h'\nyu'takeSecond))} # Find the list with the smaller first element {firstIsSmaller < @ [1@1@2, 1@2@2]} # Take the first element of the first list {takeFirst [apndr@[1,1@1@2], [tl@1@2, 2@2]]} # Take the first element of the second list {takeSecond [apndr@[1,1@2@2], [1@2, tl@2@2]]} # If one list isn't null, then append it to the # end of the merged list {atEnd (firstIsNull -> \kzconcat@[1,2@2] ; \h'\nzu'concat@[1,1@2])} {firstIsNull null@1@2} .)c .hl .)b .pp The merge sort algorithm uses a divide and conquer strategy; it splits the input in half, recursively sorts each half, and then merges the sorted lists. Of course, all these sub-sorts can execute in parallel, and the tree-insert ($"|" $) functional form expresses this concurrency. Merge removes successively larger elements from the heads of the two lists (either takeFirst or takeSecond) and appends these elements to the end of the merged sequence. Merge terminates when one sequence is empty, and then atEnd appends any remaining non-empty sequence to the end of the merged one. .CH "Dynamic Statistics" .pp On the next page we give the trace of the function merge, which information we can use to determine the structure of merge's execution tree. Since the tree is well-balanced, many of the merge's could be executed in parallel. Using this trace we can also calculate the average length of the arguments passed to merge, or a distribution of argument lengths. This information is useful for determining communication costs. .(b
abs_val : 3
3
abs_val : -3
3
abs_val : 0
0
abs_val : <-5 0 66>
?
&abs_val : <-5 0 66>
<5 0 66>
)pfn abs_val
{abs_val ((> @ [id,%0]) -> id ; (- @ [%0,id]))}
[id,%0] : -3
<-3 0>
[%0,id] : -3
<0 -3>
- @ [%0,id] : -3
3
all_le : <1 3 5 7>
T
all_le : <1 0 5 7>
F
)pfn all_le
{all_le ! and @ &<= @ distl @ [1,tl]}
distl @ [1,tl] : <1 2 3 4>
<<1 2> <1 3> <1 4>>
&<= @ distl @ [1,tl] : <1 2 3 4>
<T T T>
! and : <F T T>
F
! and : <T T T>
T
sort : <3 1 2 4>
<1 2 3 4>
sort : <1>
<1>
sort : <>
?
sort : 4
?
)pfn sort
{sort (null @ tl -> [1] ; (all_le -> apndl @ [1,sort@tl]; sort@rotl))}
fact : 3
6
)pfn fact sub1 eq0
{fact (eq0 -> %1 ; *@[id , fact@sub1])}
{sub1 -@[id,%1]}
{eq0 = @ [id,%0]}
&fact : <1 2 3 4 5>
<1 2 6 24 120>
eq0 : 3
F
eq0 : <>
F
eq0 : 0
T
sub1 : 3
2
%1 : 3
1
alt_fact : 3
6
)pfn alt_fact
{alt_fact !* @ iota}
iota : 3
<1 2 3>
!* @ iota : 3
6
!+ : <1 2 3>
6
find : <3 <3 4 5>>
T
find : <<> <3 4 <>>>
T
find : <3 <4 5>>
F
)pfn find
{find (null@2 -> %F ; (=@[1,1@2] -> %T ; find@[1,tl@2]))}
[1,tl@2] : <3 <3 4 5>>
<3 <4 5>>
[1,1@2] : <3 <3 4 5>>
<3 3>
alt_fnd : <3 <3 4 5>>
T
)pfn alt_fnd
{alt_fnd ! or @ &eq @ distl }
distl : <3 <3 4 5>>
<<3 3> <3 4> <3 5>>
&eq @ distl : <3 <3 4 5>>
<T F F>
!or : <T F T>
T
!or : <F F F>
F
)delete alt_fnd
)fns
alt_fnd : <3 <3 4 5>>
alt_fnd not defined
?
{g g}
{g}
g : 3
non-terminating
?
[Return to top level]
FP, v. 4.0 10/8/82
[+,*] : <3 4>
<7 12>
.(b
[+,* : <3 4>
syntax error:
[+,* \kx: <3 4>
\h'\nxu'^
.)b
ip : <<3 4 5> <5 6 7>>
74
)pfn ip
{ip !+ @ &* @ trans}
trans : <<3 4 5> <5 6 7>>
<<3 5> <4 6> <5 7>>
&* @ trans : <<3 4 5> <5 6 7>>
<15 24 35>
mm : <<<1 0> <0 1>> <<3 4> <5 6>>>
<<3 4> <5 6>>
)pfn mm
{mm &&ip @ &distl @ distr @[1,trans@2]}
[1,trans@2] : <<<1 0> <0 1>> <<3 4> <5 6>>>
<<<1 0> <0 1>> <<3 4> <5 6>>>
distr : <<<1 0> <0 1>> <<3 4> <5 6>>>
<<<1 0> <<3 4> <5 6>>> <<0 1> <<3 4> <5 6>>>>
&distl : <<<1 0> <<3 4> <5 6>>> <<0 1> <<3 4> <5 6>>>>
<<<<1 0> <3 4>> <<1 0> <5 6>>> <<<0 1> <3 4>> <<0 1> <5 6>>>>
.(b
&ip @ &dist & distr @ [1,trans @ 2] : <<<1 0> <0 1>> <<3 4> <5 6>>>
syntax error:
[+,* \kx: <3 4>
\h'\nxu'^
&ip @ &distl \kx& distr @ [1,trans @ 2] : <<<1 0> <0 1>> <<3 4> <5 6>>>
\h'\nxu'^
.)b
&ip @ &distl @ distr @ [1,trans@2] : <<<1 0> <0 1>> <<3 4> <5 6>>>
?
.bp
All rights reserved.
%sccs.include.redist.roff%
@(#)manCh5.rno 6.2 (Berkeley) 04/17/91
.NS 1 "Programming Examples" .pp We will start off by developing a larger FP program, mergeSort. We measure mergeSort using the trace package, and then we comment on the measurements. Following mergeSort we show an actual session at the terminal. .NS 2 "MergeSort" .pp The source code for mergeSort is: .(b .hl .(c # Use a divide and conquer strategy {mergeSort $^"|"^$ merge} {merge atEnd @ mergeHelp @ [[], fixLists]} # Must convert atomic arguments into sequences # Atomic arguments occur at the leaves of the execution tree {fixLists &(atom -> [id] ; id)} # Merge until one or both input lists are empty {mergeHelp (while \kxand @ &(not@null) @ 2 \h'\nxu'(firstIsSmaller -> \kytakeFirst ; \h'\nyu'takeSecond))} # Find the list with the smaller first element {firstIsSmaller < @ [1@1@2, 1@2@2]} # Take the first element of the first list {takeFirst [apndr@[1,1@1@2], [tl@1@2, 2@2]]} # Take the first element of the second list {takeSecond [apndr@[1,1@2@2], [1@2, tl@2@2]]} # If one list isn't null, then append it to the # end of the merged list {atEnd (firstIsNull -> \kzconcat@[1,2@2] ; \h'\nzu'concat@[1,1@2])} {firstIsNull null@1@2} .)c .hl .)b .pp The merge sort algorithm uses a divide and conquer strategy; it splits the input in half, recursively sorts each half, and then merges the sorted lists. Of course, all these sub-sorts can execute in parallel, and the tree-insert ($"|" $) functional form expresses this concurrency. Merge removes successively larger elements from the heads of the two lists (either takeFirst or takeSecond) and appends these elements to the end of the merged sequence. Merge terminates when one sequence is empty, and then atEnd appends any remaining non-empty sequence to the end of the merged one. .CH "Dynamic Statistics" .pp On the next page we give the trace of the function merge, which information we can use to determine the structure of merge's execution tree. Since the tree is well-balanced, many of the merge's could be executed in parallel. Using this trace we can also calculate the average length of the arguments passed to merge, or a distribution of argument lengths. This information is useful for determining communication costs. .(b
.hl .(c )trace on merge mergeSort : <0 3 -2 1 11 8 -22 -33> | 3 >Enter> merge [<0 3>] | 3 <EXIT< merge <0 3> | 3 >Enter> merge [<-2 1>] | 3 <EXIT< merge <-2 1> |2 >Enter> merge [<<0 3> <-2 1>>] |2 <EXIT< merge <-2 0 1 3> | 3 >Enter> merge [<11 8>] | 3 <EXIT< merge <8 11> | 3 >Enter> merge [<-22 -33>] | 3 <EXIT< merge <-33 -22> |2 >Enter> merge [<<8 11> <-33 -22>>] |2 <EXIT< merge <-33 -22 8 11> 1 >Enter> merge [<<-2 0 1 3> <-33 -22 8 11>>] 1 <EXIT< merge <-33 -22 -2 0 1 3 8 11> <-33 -22 -2 0 1 3 8 11> .)c .hl.)b .bp .NS 2 "FP Session" .pp User input is emboldened, terminal output in Roman script.fp FP, v. 4.1 11/31/82 )load ex_man {all_le} {sort} {abs_val} {find} {ip} {mm} {eq0} {fact} {sub1} {alt_fnd} {alt_fact} )fns
| abs_val all_le alt_fact alt_fnd eq0 fact find |
| ip mm sort sub1 \& |
| abs_val all_le alt_fact eq0 fact find ip |
| mm sort sub1 \& |