Skip to content

compositional processes for dependent sessions

January 29, 2015

Back in this post, I formulated a notion of session type where the structure of later parts of the session were dependent on the traffic from, not the participants in, the earlier parts. I’m going to tweak the definition a little, just to chunk record-like pieces together, and to be explicit that traffic is a record.

  Record : Set                                        [(R : Record)]r : Set
  ::= ! (X : Signal)                                  [ ! X    ]r = [ X ]s
    | sg (S : Session) (T : [ S ]r -> Session)        [ sg S T ]r = (s : [ S ]r) * [ T s ]r

  Session : Set                                       [(S : Session)]t : Record
  ::= ! (R : Record)                                  [ ! R    ]t = R
    | sg (S : Session) (T : [ [ S ]t ]r -> Session)   [ sg S T ]t = sg [ S ]t \ s -> [ T s ]t
    | op (S : Session)                                [ op S   ]t = [ S ]t

The type Session is defined mutually with the interpretation [-]t which tells you of what the traffic for a session must consist. You can see that it’s a big dependent record type, with nothing higher-order in it, and that fits with our expectation that what goes over wires are finite sequences of bits.

Now we know what the types are, what are the processes which communicate? I gave them a weakest precondition semantics, where G and H, below are postconditions on the session traffic.

Play (! R)    G = (r : [ R ]r) * G r  -- choose a happy record
Play (sg S T) G = Play S \ s -> Play (T s) \ t -> G (s , t)
Play (op S)   G = Oppo S G

Oppo (! R)    H = (r : [ R ]r) -> H r  -- put up with whatever record
Oppo (sg S T) H = Oppo S \ s -> Oppo (T s) \ t -> H (s , t)
Oppo (op S)   H = Play S H

The trouble is that each of Player and Opponent are described by a right-nested sequence of Π- and Σ-types, quantifying over signals. The nesting structure of the session type gets flattened, and you pretty much have to work in continuation-passing style. I did just about manage to program a small example with it, but I wasn’t all that happy with how it worked out.

So I had a nice chat with Simon Gay and the ABCD gang at Glasgow University, and then I had another think. What I want is a more straightforward notion of participant.

Role ::= play | oppo
swap (r : Role) : Role
swap play = oppo
swap oppo = play

Party (r : Role)(S : Session) : Set

but when we try to define that, we hit this problem

Party r (sg S T) = (s : Party r S) * Party r (T (? : [ S ]t))

That is, we have one of the parties to S, but to see how to continue, we need the whole of the traffic generated when that party interacts.

So let’s get it. Let’s define

Party (r : Role)(S : Session) : Set
Reply (r : Role)(S : Session)(p : Party r S) : Record
traff (r : Role)(S : Session)(p : Party r S)(y : [ Reply r S p ]r) : [ [ S ]t ]r

which may remind some of you of an indexed container, but I digress. The plan is that parties are higher-order, reflecting the way behaviour is a function of input. But the replies are first-order. A reply is exactly the fragment of the traffic which is not chosen by the party, so we can construct the whole of the session traffic given one party and the reply to it.

So here goes. Base case:

Party play (! R) = [ R ]r         Party oppo (! R) = One
Reply play (! R) x = ! one        Reply oppo (! R) _ = R
traff play (! R) x _ = x          traff oppo (! X) _ x = x

And now we’re good for

Party r (sg S T) = (s : Party r S) * (s' : [ Reply r S s ]r) -> Party r (T (traff r S s s'))
Reply r (sg S T) (s , k) = sg (Reply r S s) \ s' -> Reply r (T (traff r S s s')) (k s)
traff r (sg S T) (s , k) (s' , t') =
  let ss' = traff r S s s' in ss' , traff r (T ss') (k s') t'

Changing direction is no big deal.

Party r (op T) = Party (swap r) T
Reply r (op T) t = Reply (swap r) T t
traff r (op T) t t' = traff (swap r) T t t'

But now we have a peculiar pickle. If we have both parties, we should be able to figure out both replies, and then we’ll have *two* versions of the traffic, and they’d better agree. We need a traffic equaliser.

talk (S : Session)(p : Party play S)(o : Party oppo S)
  : (p' : [ Reply play S p ]r) * (o' : [ Reply oppo S o ]r) *
    traff play S p p' == traff oppo S o o'
talk (! X) x _ = _ , x , refl
talk (sg S T) (ps , pk) (os , ok) =
  let ps' , os' , qs = talk S ps os
      pt' , ot' , qt = talk (T (traff play S ps ps')) (pk ps') (ok os')
  in  (ps' , pt') , (os' , ot') , (qs , qt)
talk (op T) p o = let o' , p' , q = talk T o p in p' , o' , sym q

I’ve lied, of course. That doesn’t quite typecheck.

  ok os' : Party oppo (T (traff oppo S os os'))

We need to use qs to fix it up. We can do that by carefully abstracting both versions of the traffic.

talk (S : Session)(p : Party play S)(o : Party oppo S)
  : (p' : [ Reply play S p ]r) * (o' : [ Reply oppo S o ]r) *
    traff play S p p' == traff oppo S o o'
talk (! X) x _ = _ , x , refl
talk (sg S T) (ps , pk) (os , ok) =
  let ps' , os' , qs = talk S ps os
      talk' (pss : [ S ]t)(oss : [ S ]t)(qs : pss == oss)
            (pt : Party play (T pss))(ot : Party oppo (T oss))
          : (pt' : [ Reply play (T pss) pt ]r) * (ot' : [ Replay oppo (T oss) ot ]r) *
            traff play (T pss) pt pt' == traff oppo (T oss) ot ot'
      talk' ss ss refl pt ot = talk (T ss) pt ot
      pt' , ot' , qt = talk' (traff play S ps ps') (traff oppo S os os') qs (pk ps') (ok os')
  in  (ps' , pt') , (os' , ot') , (qs , qt)
talk (op T) p o = let o' , p' , q = talk T o p in p' , o' , sym q

(The need to build that particular helper function has me wondering if we could come up with a better notation for programs which build tuples a bit at a time.)

So we end up with a notion of parties to sessions which chop up more compositionally in accordance with the structure of the sessions themselves. It’s still a two-party session story with quite a sequential flavour.

No comments yet

Leave a Reply

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

You are commenting using your 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

%d bloggers like this: