Home > Uncategorized > Automatic Model Generation, part 5: Iteration

Automatic Model Generation, part 5: Iteration

Previous parts of this guide have shown how to represent and print CSP models, and how to redefine the CHP monad and the primitives for choice, IO and communication in order to generate CSP models from CHP programs. This part deals with the final difficult item: iteration.

Most processes in CHP run in an infinite loop, terminated only by poison. Many are written using the helper function forever, which is defined: forever p = p >> forever p. Consider what happens when we try to generate the model for such a process, e.g. forever (syncBarrier b). We first encounter the syncBarrier and we store in the model that the process would engage in event "b". Then in the forever function we loop round and reach the syncBarrier again, and add on to the model that the process would next engage in "b" again. And so on and so on. An infinite loop in our program would cause an infinite loop in our model generation, rendering it useless. We cannot observationally determine that the program is looping forever; think how our approach could possibly distinguish the above from replicateM_ 1000000 (syncBarrier b) >> syncBarrier c.

Forever in an Instant

To solve this particular problem, we supply a foreverP function in the CHP library and its redefinition. In the original CHP library, foreverP acts as forever. In the forthcoming chp-spec library, it is defined differently: it runs the code once to record the model, then makes a note in the model that this code should have run forever. It also stops further modelling; any code after a call to forever will be ignored in the normal library, and so it should be here, too:

foreverP :: CHP a -> CHP b
foreverP p = stopSpecT . liftM (Repeat . snd) . finSpecT

stopSpecT :: Monad m => m SpecItem -> CHPSpecT m a
stopSpecT m = CHPSpecT $ const $ liftM (\sp -> (error "stopSpecT", (sp :))) m

The stopSpecT makes sure that no further specification is performed after this point. The crucial part is the const which ignores the continuation function -- this is something that is easily done with our continuation-passing monad (and is like a short-circuiting error monad).

The above takes care of forever, which is used when the program carries no state around. But other processes have direct recursion and cannot use this function.

Process Annotations

To solve the recursion problem, we introduce a process annotation. The process annotation surrounds a process and captures the value of its arguments. The assumption is made (or rather, a condition is placed on the user) that the process will have the same behaviour (excluding any external input from channels and liftIO functions) when given the same arguments. In a pure language like Haskell, this is reasonable and will commonly be the case. The annotation should be added at the beginning of any process that recurses -- when the recursion is performed, the process is modelled iff it has never been run before with these arguments; if it has been run before, its behaviour has already been modelled and recorded, so it is returned directly. Here is the annotation in action, on the security guard from the dining philosophers:

security :: [(Chanin (), Chanin ())] -> CHP ()
security chans = security' chans 0
 where
  security' :: [(Chanin (), Chanin ())] -> Int -> CHP ()
  security' = process "security" $ \chans satDown ->
    let (ups, downs) = unzip chans
        maxSatDown = length chans - 1 in
    (alt $
      [readChannel c >> return (satDown - 1) | c <- ups, satDown > 0] ++
      [readChannel c >> return (satDown + 1) | c <- downs, satDown < maxSatDown]
    ) >>= security' chans

It takes as its first parameter the name of the process -- it is user-supplied, but should be unique in the program. The second parameter is the process itself. Here, the process has two arguments -- but it could be any number. The process annotation is designed using type-classes so that it can be used with processes that take any number of arguments.

We need to store the arguments that each process took when it was modelled. So we need to store the models in a data structure like Map String (Map Args Model). But Args needs to be a set of differently-typed arguments for each process -- we can't statically assign a type to it. If we only supported self-recursion we could probably solve this with phantom type parameters in the monad and so forth, but sometimes, even in Haskell, it is appropriate to use dynamic typing. The Data.Dynamic module supports safe dynamic typing (in that casts from the Dynamic type have a run-time check).

In fact, we don't actually need to store the arguments themselves. What we need to store with a previous model is a function like a -> Bool that says whether the latest parameter is the same as was used for generating the previous model:

type CheckArg = Dynamic -> Bool

checkArgs :: [Dynamic] -> [CheckArg] -> Bool
checkArgs ds fs
  | length ds /= length fs = False
  | otherwise = and $ zipWith ($) fs ds

We create a Process type-class to implement our process annotation:

process :: Process p => String -> p -> p
process s = process' True s []

class Process p where
  process' :: Bool -> String -> [(Dynamic, CheckArg)] -> p -> p

instance (Eq a, Typeable a, Process b) => Process (a -> b) where
 process' topLevel name args f x
  = process' topLevel name (args ++ [(toDyn x,(== Just x) . fromDynamic)]) (f x)

The process' function takes a Bool (ignore that for now), the process name, a list of arguments so far (each pair is the argument itself, and its function to check against a future value), and then wraps a process "p". The instance shown above is the one that captures all a process's parameters. Each parameter is appended to the list. toDyn turns a value into a Dynamic, and fromDynamic returns a Maybe value (Nothing if the type-cast is unsuccessful, Just if was successful). Comparing the result of fromDynamic to Just x checks both the type and the value at once. To support dynamic typing, parameters must have a Typeable instance (which GHC can derive for most types -- and is supplied for all CHP library types) and an Eq instance to check for equality. The most notable types that cannot be used for a parameter are functions. This is a limitation of the approach -- and indeed, CSP itself does not support any notion of functions being passed around. Any processes that take functions as parameters would have to be made first-order (Neil Mitchell's Firstify comes to mind).

The base-case instance for Process is the one that actually uses the parameter list:

data CHPState = CHPState { ... , 
 chpProcessMap :: Map.Map String (Map.Map Integer ([CheckArg], (Spec,Dynamic))),
 chpFreeNames :: [(Dynamic, CheckArg)],
 chpNextProcess :: !Integer }

instance (Typeable a, Eq a) => Process (CHP a) where
  process' topLevel name immArgs p = addSpecT1 $ do
    st <- get
    let possibles = Map.toList <$> (Map.lookup name $ chpProcessMap st)
        args = if topLevel then immArgs
                 else chpFreeNames st ++ immArgs
    case possibles >>= L.find (checkArgs (map fst args) . fst . snd) of
      Just (n, (_, (_, r)))
        -> return (flip fromDyn (error "process-lookup") r, Call n)
      Nothing -> 
        do let n = chpNextProcess st
           put $ st { chpProcessMap = insertMapMap name n
                        (map snd args, (error "process", toDyn ()))
                          $ chpProcessMap st
                    , chpFreeNames = args
                    , chpNextProcess = succ n
                    }
           (r, f) <- finSpecT p
           modify $ \st' -> st' { chpProcessMap = insertMapMap name n
                                    (map snd args, (f, toDyn r))
                                      $ chpProcessMap st'
                                  -- Restore original free names:
                                , chpFreeNames = chpFreeNames st }
           return (r, Call n)

The case statement checks if any previously-modelled processes match. If one does (the Just case), its model and return value are returned. If Nothing is found, the process is modelled. It is crucial that the state is first updated with an entry for the process -- that way, when the process recurses, it can find itself in the collection of recorded processes (if the recursion uses the same argument values). The dummy entry has the right parameters but an invalid model (that will never be accessed before it is later updated) and an incorrect return type; processes that recurse and then examine the value of the recursive call are not supported here. However, almost every recursive CHP process is tail-recursive, which can be modelled just fine (if they weren't tail recursive, they would probably feature a space-leak). After the process has been modelled, its entry is updated with the real return value and real specification.

The model returned by the process annotation is always simply a Call item. Therefore, any process that recurses will simply have a Call item added to the end, stopping the model from extending forever -- provided that at some point the same parameters are used to the process. A parameter with continually-changing parameters that never repeat -- for example, one that outputs ascending integers -- cannot be modelled here. This is yet another limitation of the approach.

Example

As an example, we'll use the security guard shown earlier in this post, and how that is modelled with three philosophers (i.e. three sets of channels). Our approach produces a model for each different set of arguments to the process -- the models for different arguments can potentially be completely different. Some effort could be put into collapsing them back down during post-processing, but here are the three models:

security_10=
  (((security.up.phil0?x_14 -> security_9)
    []
    (security.up.phil1?x_15 -> security_9)
    []
    (security.up.phil2?x_16 -> security_9)
    []
    (security.down.phil0?x_17 -> security_11)
    []
    (security.down.phil1?x_21 -> security_11)
    []
    (security.down.phil2?x_22 -> security_11)))
security_11=
  (((security.up.phil0?x_18 -> security_10)
    []
    (security.up.phil1?x_19 -> security_10)
    []
    (security.up.phil2?x_20 -> security_10)))
security_9=
  (((security.down.phil0?x_13 -> security_10)
    []
    (security.down.phil1?x_23 -> security_10)
    []
    (security.down.phil2?x_24 -> security_10)))

The top process, security_10, is the state where one philosopher is currently seated and thus all up and down events are offered. If an up event occurs, the next process is security_9, the state where no philosophers are seated, and thus only down events are offered. If a down event occurs in security_10, the next process is security_11, where two philosophers are seated and only up events are offered: this prevents a third philosopher sitting down (which could potentially lead to the classic deadlock in the dining philosophers).

That concludes all the in-depth technical parts of this guide. There'll be one more post explaining the top-level specify method, which should also include the announcement of the release of the chp-spec library based on this guide.

About these ads
Categories: Uncategorized Tags: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: