Ch5, Ex5

Code that can be used to run the various code snippets in the problem:

declare
proc {Barrier Ps}
   fun {BarrierLoop Ps L}
      case Ps of P|Pr then M in
         thread {P} M=L end
         {BarrierLoop Pr M}
      [] nil then L
      end
   end
   S={BarrierLoop Ps unit}
in
   {Wait S}
end
proc {NewPortClose ?S ?Send ?Close}
   PC={NewCell S}
in
   proc {Send M}
      S in
      {Exchange PC M|S S}
   end
   proc {Close}
      nil=@PC
   end
end
proc {ConcFilter L F ?L2}
   Send Close
in
   {NewPortClose L2 Send Close}
   {Barrier
    {Map L
     fun {$ X}
        proc {$}
           if {F X} then {Send X} end
        end
     end}}
   {Close}
end 

a:)It shows [5 4] but [4 5] is also possible and depends upon the thread execution order put down by the thread scheduler which are created by Barrier. Clearly there is an observable nondeterminism.
BTW here is a snippet that *almost* makes sure that [4 5] is printed

declare Out A
thread {Delay 500} A = 5 end
%ConcFilter doesn't wait for A and carries on with other
%elements, A is processed later when its bound, Regular
%Filter in this case will wait for A to bound and still
%print [5 4]
{ConcFilter [A 1 2 4 0] fun {$ X} X>2 end Out}
{Show Out} 

b:)Same as a.

c:)Nothing is displayed as Barrier blocks because one of the child thread is blocked at A.
Once A is bound to 3, Out can have two values [5 4 3] and [4 5 3]. 3 always comes last because all the threads except that needing A finish there execution.

d:)Well complexity of both is O(n). But execution time depends upon following cases
I. If all the elements in input list are bound then Filter is much faster because ConcFilter does exactly the same things as Filter but with the overhead of creating threads for processing each element.
II.If let say first element of the list is not bound, in this case Filter will not be able to process the other elements also unless first one is bound while ConcFilter can carry on processing other elements even though first is not bound, so if list length is sufficiently large and predicate function is time consuming then ConcFilter will do a better job.