Tuesday, 23 April 2013

More on CSP

CSP is an interesting language because it lets one model potentially complex states through fairly simple means. As we saw in the last entry, you simply have to list how events follow each other. By building sequences of events you're actually drawing a state transition diagram. In such a diagram the transition is the event. For example, here's a diagram of the Blog process we defined earlier:


Each bubble represents a process. Blog1 = Writeup -> Post -> Blog and so on. In this case we just have one chain of events. It is also possible to have multiple chains of events. So we can define Blog as follows:

  Blog = idea -> writeup -> post -> Blog
                 []
                 talk -> writeup -> post -> Blog

In this case there is a concept of choice. Once I have an idea I can either talk about the idea or I can immediately write it up. The notation [] says that the choice is external, meaning that it is not up to this process to decide which path to go down on. CSP does not care, it is there to represent all paths. So, a decision can be made to talk if I have a friend around. If not, then I go straight to writing up my idea. I can also make it an internal decision with the |~| symbol.

Let's define a talkative friend:

  Friend = enterhouse -> talk -> exithouse -> Friend

Notice that after exiting the house he's still my friend. Friend and blogging interact through talking which we, of course, represent in the following process:

  Interaction = Friend {| talk |} Blog

Again, this is a very powerful concept of process composition. This interaction essentially says that the Friend cannot talk until Blog is able to talk. Because our processes are recursive, is it possible that posts will be made without talk ever happening. A quite world - how nice. Interaction process can be represented through a block diagram like this:


It seems so simple but actually there is a lot being abstracted behind the scenes should this be implemented. Those are two processes that have to wait until both are ready to perform the talk event. So, there has to be synchronization going on. To me, the mind warping experience happened when I imagined that this is implemented in hardware and talk is actually a write connecting to components. It should also be noted that talk remains an external event - perhaps a spider need to jump out for the conversation to begin.

For those who have spend many years programming the tendency is to think of talk as an event produced by Friend and an event produced by Blog. So, it seems that the two processes are sending things to each other and what happens if the talks occur at the same time for each process. I struggled with that idea for a while, until I realized that I was thinking about it all wrong. Seems so obvious now. In this concurrent system of representation we do not consider events happening at the same time, rather the processes put themselves into a state where they are ready to accept events. This means that there is always some sequence of events that the system must be able to handle. CSP is the language that allows the user to consider every possible sequence of events to check the constructed model.

No comments:

Post a Comment