|
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
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?
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!
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?)
WHILE TRUE
SEQ
INT x, y:
ALT
in.0 ? x
SKIP
in.1 ? y
SKIP
:
... with "plex" called using two "numbers" processes:
PROC main (CHAN BYTE in?, out!, err!)
CHAN INT a, b:
PAR
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:
ALT
in.0 ? x
SEQ
out.int (x, 0, out!)
out.int (y, 0, out!)
in.1 ? y
SKIP
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
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.
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
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
ALT
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?
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)
INITIAL BOOL loop IS TRUE:
SEQ
WHILE loop
ALT
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
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.
Yes – use a SKIP guard at the end of a PRI ALT. See slide 30 of the "choice" slides.
Keywords: alt
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
SKIP
But I get a incorrect indentation error.
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":
PRI ALT
ALT i = 0 FOR 10
in[i] ? y
... do stuff here
SKIP
... 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
|
This work is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License. |
