--- This system
is (very) experimental ---
The trace shows values exchanged on channels;
"output" is the standard output channel.
Simple Parallel Functional Language L.A. Monash Comp Sci 8/4/93
1: let rec
2: eoi = -999,
3:
4: L =5::6::7::19::15::12::13::0::1::4::
5: 3::2::8::18::17::16::9::10::11::14::nil,
6: LU=0::1::2::3::4::5::6::7::8::9::nil,
7: LD=9::8::7::6::5::4::3::2::1::0::nil, {data sets}
8:
9: listtochan = lambda L. lambda ch.
10: if null L then ch!eoi -> stop
11: else ch!hd L -> listtochan tl L ch,
12:
13:
14: split = lambda inch. lambda out1. lambda out2.
15: let rec {alternate elements from inch go to each output channel}
16: flip = lambda out1. lambda out2.
17: inch?x ->
18: if x=eoi then out1!eoi -> stop || out2!eoi -> stop
19: else out1!x -> flip out2 out1
20: in flip out1 out2,
21:
22:
23: merge = lambda in1. lambda in2. lambda outch.
24: let rec
25: copy = lambda inch.
26: inch?x -> outch!x -> if x=eoi then stop else copy inch,
27:
28: f = lambda x. lambda y. {NB. x<>eoi or y<>eoi}
29: if x=eoi then outch!y -> copy in2
30: else if y=eoi then outch!x -> copy in1
31: else if x<y then outch!x -> in1?z -> f z y
32: else outch!y -> in2?z -> f x z
33:
34: in in1?x -> in2?y -> f x y |
35: in2?y -> in1?x -> f x y,
36:
37:
38: msort = lambda inch. lambda outch.
39: inch?x -> inch?y ->
40: if y=eoi then outch!x -> outch!eoi -> stop
41: else
42: let a=chan, b=chan, c=chan, d=chan
43: in a!x -> b!y -> split inch a b ||
44: msort a c || msort b d ||
45: merge c d outch,
46:
47:
48: c=chan
49:
50: in listtochan L c || msort c output
51:
52: {\fB Parallel Merge Sort. \fP}
53:
54:
--- end of parsing ---
(let rec ((eoi =(-(999 ))),
((L =((5 )::((6 )::((7 )::((19 )::((15 )::((12 )::((13 )::((0 )::((1 )::((4 )::((3 )::((2 )::((8 )::((18 )::((17 )::((16 )::((9 )::((10 )::((11 )::((14 )::(nil )))))))))))))))))))))),
((LU =((0 )::((1 )::((2 )::((3 )::((4 )::((5 )::((6 )::((7 )::((8 )::((9 )::(nil )))))))))))),
((LD =((9 )::((8 )::((7 )::((6 )::((5 )::((4 )::((3 )::((2 )::((1 )::((0 )::(nil )))))))))))),
((listtochan =(lambda (L ).(lambda (ch ).(if (null (L ))then (((ch )!(eoi ))->(stop ))else (((ch )!(hd (L )))->(((listtochan )(tl (L )))(ch ))))))),
((split =(lambda (inch ).(lambda (out1 ).(lambda (out2 ).(let rec ((flip =(lambda (out1 ).(lambda (out2 ).(((inch )?(x ))->(if ((x )=(eoi ))then ((((out1 )!(eoi ))->(stop ))||(((out2 )!(eoi ))->(stop )))else (((out1 )!(x ))->(((flip )(out2 ))(out1 )))))))))
in (((flip )(out1 ))(out2 ))))))),
((merge =(lambda (in1 ).(lambda (in2 ).(lambda (outch ).(let rec ((copy =(lambda (inch ).(((inch )?(x ))->(((outch )!(x ))->(if ((x )=(eoi ))then (stop )else ((copy )(inch ))))))),
((f =(lambda (x ).(lambda (y ).(if ((x )=(eoi ))then (((outch )!(y ))->((copy )(in2 )))else (if ((y )=(eoi ))then (((outch )!(x ))->((copy )(in1 )))else (if ((x )<(y ))then (((outch )!(x ))->(((in1 )?(z ))->(((f )(z ))(y ))))else (((outch )!(y ))->(((in2 )?(z ))->(((f )(x ))(z ))))))))))))
in ((((in1 )?(x ))->(((in2 )?(y ))->(((f )(x ))(y ))))|(((in2 )?(y ))->(((in1 )?(x ))->(((f )(x ))(y )))))))))),
((msort =(lambda (inch ).(lambda (outch ).(((inch )?(x ))->(((inch )?(y ))->(if ((y )=(eoi ))then (((outch )!(x ))->(((outch )!(eoi ))->(stop )))else (let ((a =(chan)),
((b =(chan)),
((c =(chan)),
((d =(chan))))))
in ((((((a )!(x ))->(((b )!(y ))->((((split )(inch ))(a ))(b ))))||(((msort )(a ))(c )))||(((msort )(b ))(d )))||((((merge )(c ))(d ))(outch )))))))))),
((c =(chan)))))))))))
in ((((listtochan )(L ))(c ))||(((msort )(c ))(output ))))
--- running ---
ch3 5 ch3 6 ch4 5 ch5 6 ch3 7 ch4 7 ch3 19 ch8 5 ch9 7 ch5 19 ch3 15 ch4 15 ch3 12 ch8 15 ch16 5 ch17 15 ch12 6 ch13 19 ch5 12 ch3 13 ch4 13 ch3 0 ch9 13 ch20 7 ch21 13 ch12 12 ch5 0 ch3 1 ch4 1 ch3 4 ch8 1 ch16 1 ch28 5 ch29 1 ch24 6 ch25 12 ch13 0 ch5 4 ch3 3 ch4 3 ch3 2 ch9 3 ch20 3 ch36 7 ch37 3 ch12 4 ch5 2 ch3 8 ch4 8 ch3 18 ch8 8 ch17 8 ch40 15 ch41 8 ch24 4 ch44 6 ch45 4 ch32 19 ch33 0 ch13 2 ch5 18 ch3 17 ch4 17 ch3 16 ch9 17 ch21 17 ch48 13 ch49 17 ch12 18 ch5 16 ch3 9 ch4 9 ch3 10 ch8 9 ch16 9 ch28 9 ch52 5 ch53 9 ch25 18 ch56 12 ch57 18 ch32 2 ch13 16 ch5 10 ch3 11 ch4 11 ch3 14 ch9 11 ch20 11 ch36 11 ch64 7 ch65 11 ch12 10 ch5 14 ch3 -999 ch4 -999 ch8 -999 ch16 -999 ch28 -999 ch52 -999 ch53 -999 ch54 5 ch55 9 ch29 -999 ch30 5 ch54 -999 ch31 1 ch17 -999 ch40 -999 ch41 -999 ch42 15 ch43 8 ch18 1 ch31 -999 ch19 8 ch43 -999 ch9 -999 ch20 -999 ch36 -999 ch64 -999 ch65 -999 ch66 7 ch67 11 ch37 -999 ch38 7 ch66 -999 ch39 3 ch21 -999 ch48 -999 ch49 -999 ch50 13 ch51 17 ch22 3 ch39 -999 ch23 13 ch50 -999 ch10 1 ch18 5 ch30 9 ch55 -999 ch11 3 ch22 7 ch38 11 ch67 -999 ch24 10 ch44 10 ch68 6 ch69 10 ch60 19 ch61 2 ch33 16 ch13 14 ch5 -999 ch12 -999 ch24 -999 ch44 -999 ch68 -999 ch69 -999 ch70 6 ch71 10 ch45 -999 ch46 6 ch70 -999 ch47 4 ch25 -999 ch56 -999 ch57 -999 ch58 12 ch59 18 ch26 4 ch47 -999 ch27 12 ch58 -999 ch32 14 ch13 -999 ch60 14 ch32 -999 ch76 19 ch77 14 ch60 -999 ch76 -999 ch77 -999 ch78 19 ch79 14 ch61 -999 ch62 14 ch79 -999 ch63 2 ch72 0 ch73 16 ch33 -999 ch72 -999 ch73 -999 ch74 0 ch75 16 ch34 2 ch63 -999 ch35 0 ch74 -999 ch14 4 ch26 6 ch46 10 ch71 -999 ch15 0 ch35 16 ch75 -999 ch6 1 ch10 5 ch18 9 ch30 -999 ch7 0output 0 ch15 2 ch34 14 ch62 19 ch78 -999 ch7 2 output 1 ch15 14 ch34 19 ch62 -999 ch6 3 output 2 ch11 7 ch22 11 ch38 -999 ch7 4 output 3 ch14 6 ch26 10 ch46 -999 ch6 5 output 4 ch10 8 ch19 15 ch42 -999 ch7 6 output 5 ch14 10 ch26 -999 ch6 7 output 6 ch11 11 ch22 -999 ch7 10 output 7 ch14 12 ch27 18 ch59 -999 ch6 8 output 8 ch10 9 ch18 -999 ch6 9 output 9 ch10 15 ch19 -999 ch6 11 output 10 ch11 13 ch23 17 ch51 -999 ch7 12 output 11 ch14 18 ch27 -999 ch6 13 output 12 ch11 17 ch23 -999 ch7 14 output 13 ch15 16 ch35 -999 ch6 15 output 14 ch10 -999 ch7 16 output 15 ch15 19 ch34 -999 ch6 17 output 16 ch11 -999 ch7 18 output 17 ch14 -999 ch6 -999 output 18 ch7 19 output 19 ch15 -999 ch7 -999 output -999 2 processes left 5067 evals, 1040 env cells used, 20 cells used --- finished ---