kent logo

CO538 Anonymous Questions and Answers Keyword Index

This page provides a keyword index to questions and answers. Clicking on a keyword will take you to a page containing all questions and answers for that keyword, grouped by year.

To submit a question, use the anonymous questions page. You may find the keyword index and/or top-level index useful for locating past questions and answers.

Keyword reference for alt


Question 53 (2012):

Submission reference: IN2357

I'm reading the "Choice" slides, slide 99, but I'm struggling to understand:

"By only allowing input guards, only one process is ever involved in any choice (i.e. if one process is ALTing, no process communicating with it can be ALTing)."

Can you explain this in a bit more detail?

Answer 53:

There's not much more to say ... but let's talk it through ...

The network in "Choice" slide 99 shows two processes communicating with each other by ALTing over the same two channels (a and b). Each ALT contains an input guard and an output guard. One decision has to be made – namely, which communication (over a or over b) will take place? Both processes must make this decision and they must make the same decision, which is what makes this expensive to implement.

But output guards are not allowed (currently) in occam-pi. Therefore, if one process is making a choice (ALTing) and that choice involves a channel, that involvement must be an offer to input from that channel. The process at the other end of that channel is only able, of course, to output to that channel – which it cannot be doing as part of an ALT, so it cannot be making a choice! Therefore, it cannot be involved in the choice being made by the first process.

Similarly, processes at the other end of all channels involved in the ALT of the first process cannot be involved in that choice.

The only other possible guards in the ALT of the first process are timeouts and SKIPs, none of which involve other proesses.

Therefore, if one process is making a choice, no other process is making a choice that impacts on the first choice – i.e. only one process is ever involved in deciding any individual choice. This makes ALTs inexpensive to implement, which is why output guards are (currently) not allowed!

Keywords: alt , choice


Question 73 (2011):

Submission reference: IN2142

Supposing you have a process "plex" that ALT's over two incoming INT channels:

  PROC plex (CHAN INT in.0?, in.1?)
        INT x, y:
	  in.0 ? x
	  in.1 ? y

... with "plex" called using two "numbers" processes:

  PROC main (CHAN BYTE in?, out!, err!)
    CHAN INT a, b:
      numbers (a!)
      numbers (b!)
      plex (a?, b?)

Since only one guard is executed, why does the program not block? Will both x and y be set (and only a single body executed)? Could I write the following?

        INT x, y:
          in.0 ? x
              out.int (x, 0, out!)
              out.int (y, 0, out!)
          in.1 ? y

Answer 73:

In every loop of your plex process, only one ALT guard is executed – i.e. a communication from either one of its input channels is taken. Your main process does not deadlock since its two numbers processes will always offer to send messages and plex will always take a message from one of them. Were you forgetting about the WHILE-loop in your plex?

The last fragment of code in your question is wrong because the y variable in the second call to out.int is undefined. This fragment executes as follows: it waits for a message on either of its input channels; if it takes a message from in.1, it does nothing else; if it takes a message from in.0, it catches it in variable x and outputs ASCII bytes for its decimal representation down the out channel (which must carry BYTEs, otherwise the fragment of code would not compile) and then tries to do the same for the integer value in variable y ... but that value has not been set anywhere ... which makes no sense and is not allowed.

Keywords: alt

Question 9 (2011):

Submission reference: IN2039

Regarding the integrate process, I was confused on how the network was initiated. Is the following explanation correct?

Thinking sequentially, from the network diagram, it appears to begin with a number read in by the plus component. plus requires two inputs, so my thought was that the network would deadlock since only a single number could possibly be read in.

However, since all components are ran in parallel, the network is in-fact initiated by the *prefix* component. prefix outputs a 0, which is read in by plus (as well as the input number), passed to delta, with prefix copying the stream from delta from then on.

Answer 9:

Thank you for this question. Apologies for this lengthy reply ...

Thinking sequentially about a parallel network is not a good idea. The network does not begin with, nor is it initiated by, any of its parallel components. All its components start independently and in whatever order they happen to get going.

The platform on which the components run does not matter. They could be physically separate pieces of silicon real-estate, part of a larger chip, in which case the order in which they power up is indeterminate (though separated by nanoseconds). They could be on different computers in the cloud (in separate parts of the planet), in which case the order in which they start is also indeterminate (and may be hours apart). They could be software scheduled on a single core (as is the case with the Transterpreter) – in which case the order they are scheduled is still indeterminate! On some magic platform of the future, they might even start up simultaneously (though the Special Theory of Relativity pours scorn on the idea of simultaneity).

The point is that PAR components start in any order and that order does not matter! So, stop worrying about which component physically starts first.

In the case of the integrate process, its components' first actions are to communicate either between each other or with devices external to integrate. Indeed, apart from the addition in the plus component, there is nothing else that they do!

Other components (of other PARs) may get on with lots of computation (e.g. calculate pi to a billion decimal places, invert some very large matrices) before any communication. If those components are placed on separate computational engines (e.g. separate cores on a microprocessor or separate computers in the cloud), then their computations can proceed in parallel (i.e. at the same time). Clearly, the order in which they actually start is not relevant.

Back with integrate, because they communicate with each other, we do need to consider the patterns (i.e. sequences) of communication that are possible. In general (and in this case), there can be several.

The last paragraph in your question pretty much says it right.

The above bullets, however, do not describe all the possible initial patterns of communication!

For example, in the fourth bullet above, the second input value could be taken (it it is being offered by some external device) by plus (actually, by one if its freshly spawned sub-processes). So, that second external input could happen inteleaved anywhere between the two outputs from delta described in this bullet.

Do not be alarmed by all these different possible sequences in which the communications may happen. Apart from getting a feel for the rules of synchronised communication (fundemental to the occam-pi/CSP concurrency model), we don't need to think at this low-level about what is actually happening! A crucial property of the occam-pi/CSP concurrency algebra is that the function performed by a network is deterministic (i.e. independent of the order in which events actually happen). For integrate, its outputs are the running sums of its inputs, regardless of the order of its internal actions.

At least, that's the story so far ...

In lecture 6, we will introduce Choice mechanisms that are provided so that we can design processes whose functions are determined by the order in which events happen. However, the nice thing about occam-pi is that we only get non-determinism by explicitly programming it. For almost all other concurrency models, non-determinacy is the default mode of operation (which means that the understanding we had about serial coding no longer applies) and we have to become skillful in eliminating it ... and that turns out to be very hard ...

With occam-pi/CSP concurrency, our intuition about serial programming remains trustworthy. For example, a variable only changes its value if the code working on it changes its value. There's no guarantee of that with, for example, threads-and-locks concurrency – i.e. what you see is not what you get.

[Aside: in most Object Oriented languages (including Java), the position is even worse ... that guarantee does not even apply to purely serial programming ... but that's another story ...]

Keywords: q2 , non-determinism , choice , alt


Question 55 (2010):

Submission reference: IN1951

I am using kroc on Mac and I have a problem that I do not understand. I have a code that does not work if I use the Transterpreter but works if I use the command line to compile and launch the executable. For example:

  PROC  my.proc(..., BLOB blob)
    WHILE loop
	  BLOB b:
	  camera ? blob

I am using the BLOB I get in my PROC parameter. If I do not have the "BLOB b:" before the line "camera ? blob", the code does not work. Is this a bug?

Answer 55:

Your code fragment has illegal indentation and a missing response process to the camera input guard of the ALT. Correcting this (and filling in gaps to get something compilable) gets:

  PROC my.proc (CHAN CAMERA camera?, BLOB blob)
      WHILE loop
	  BLOB b:                -- spurious declaration (the questioned line)
	  camera ? blob
            loop := NOT loop     -- silly code
      camera ? blob              -- more silly code

Using kroc on my Mac, the above compiles whether the spurious declaration is present or not. Same with the Transterpreter on the Mac. I've not tried with the Transterpreter on Windows – it should also be the same though. All systems use the same compiler. Send me (p.h.welch@kent.ac.uk) your code if it still won't compile!

Keywords: alt

Question 26 (2010):

Submission reference: IN1921

Is there any way of elsing on the guards of an ALT statement – i.e. if a guard blocks it, do something else. I only ask because I want to see if the security blocks a philosopher when it tries to sit down.

Answer 26:

Yes – use a SKIP guard at the end of a PRI ALT. See slide 30 of the "choice" slides.

Keywords: alt

Question 23 (2010):

Submission reference: IN1918

In a replicated ALT is there a way to place a SKIP guard at the end? I have tried placing it at various points such as:

  ALT i = 0 FOR 10
    in[i] ? y
      ...  do stuff here

But I get a incorrect indentation error.

Answer 23:

A replicated ALT must have one (and only one!) guarded process indented below it – see slide 110 of "choice". So, your replicated ALT finishes with the "... do stuff here" line – and the indentation level returns to that of the ALT. Your SKIP is not at that level, so it's an indentation error (as the compiler correctly reports).

If you really want a SKIP guard to follow a replicated ALT, we must use a nested ALT (slides 123-133 of "choice"). The particular form you need is similar to the use of a replicated IF in slides 92-93 of "replicators":

    ALT i = 0 FOR 10
      in[i] ? y
        ...  do stuff here
      ...  do this if no in[i] channels are ready

Note that, as for all un-conditioned SKIP guards, the governing ALT must be PRIioritised – otherwise, the compiler would be correct to throw away the entire ALT and leave just the code reaction to the SKIP (because it's always ready and, therefore, may always be chosen!).

However, are you sure you want that SKIP guard? That would be a poll (see slide 30 in "choice") of all the channels in the 'in' array ... and polling is, usually, a more complex and inefficient way of doing the right thing ... in occam-pi anyway! See Question 32 (2004) and this part of Fred's occam tutorial.

Keywords: replicator , alt , polling

Valid CSS!

Valid XHTML 1.0!

This work is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License.
Last modified Mon May 20 13:50:24 2013
This document is maintained by Fred Barnes, to whom any comments and corrections should be addressed.