CTM:Exercise 4-8

Posted by Urban Hafner Mon, 07 Nov 2005 14:31:03 GMT

The problem

Dataflow behaviour in a concurrent setting. Consider the function {Filter In F}, which returns the elements of In for which the boolean function F returns true. Here is a possible definition of Filter:

fun {Filter In F}
   case In
   of X|In2 then
      if {F X} then X|{Filter In2 F}
      else {Filter In2 F} end
   else
      nil
   end
end

Executing the following:

{Show {Filter [5 1 2 4 0] fun {$ X} X>2 end}}

displays

[5 4]

(We use the procedure Show, which displays the instantaneous value of its argument in Mozart’s emulator window. Unlike Browse, this output is not updated if the argument is subsequently bound.) So Filter works as expected in the case of a sequential execution when all the input values are available. Let us now explore the dataflow behaviour of Filter.

a) What happens when we execute the following?: 

declare A
{Show {Filter [5 1 A 4 0] fun {$ X} X>2 end}}
One of the list elements is a variable A that is not yet bound to a value. Remember that the case and if statements will suspend the thread in which they execute, until they can decide which alternative path to take.

b) What happens when we execute the following?: 

declare Out A
thread Out={Filter [5 1 A 4 0] fun {$ X} X>2 end} end
{Show Out}
Remember calling Show displays its argument as it exists at the instant of the call. Several possible results can be displayed. Which and why? Is the Filter function deterministic? Why or why not?

c) What happens when we execute the following?: 

declare Out A
thread Out={Filter [5 1 A 4 0] fun {$ X} X>2 end} end
{Delay 1000}
{Show Out}
Remember that the call {Delay N} suspends its thread for at least N ms. During this time, other ready threads can be executed.

d) What happens when we execute the following?: 

declare Out A
thread Out={Filter [5 1 A 4 0] fun {$ X} X>2 end} end
thread A=6 end
{Delay 1000}
{Show Out}
What is displayed and why?

My solution

a) Nothing is displayed because Filter is suspended waiting on A to become bound.

b) What gets displayed on my box is Out<optimized>. But when I use the Browser I see 5|_. Another possible value would _ if Show is executed before Filter. But even though there can be different values shown doesn’t mean that Filter itself is not deterministic. What’s not deterministic is the way threads are executed and Show is probably not part of the declarative model.

c) This displays 5|_<optimized>. So it seems that the calls to Show in b) that I got were all before the call to Filter.

d) This of course displays [5 6 4]. Filter can finish because A gets bound, and we are waiting long enough before calling Show.

Tags , , , , , ,

RSS feed for this post

Comments are disabled