OEP

178

Title

Variant Call Protocols

Summary

Gives a procedure interface to a request-reply transaction (and more)

Owner

Peter Welch < p.h.welch@kent.ac.uk >

Owner

Eric Bonnici < eb708@kent.ac.uk >

Status

Proposed

Date-Proposed

2010-08-03 (amended 2010-08-16)

Keywords

variant call channel protocol

Call protocols are a language binding for the LEND-RETURN pattern:

Resources that can be lent are anything passable as a parameter (data, channels, timers, ports, ...). For data types, prefixing with VAL indicates whether the data may be changed. Returning a resource is often a null-operation (e.g. if nothing is changed or the accepting process is able to operate directly on the caller's data).

Syntactically, a call is similar to a procedure (or method) invocation and an accept is similar to a procedure (or method) declaration. [However, unlike method calls in Object Orientation, the calling and accepting processes must synchronise. This gives power to the accepting process to refuse a call ... which is not a power given to objects, which must always take its calls ... even when not in a state that it can service them.]

Ada task entry (1983) has the same extended rendezvous semantics between calling and accepting process as the protocol proposed here. However, Ada has no separate notion of a named channel and the caller has to invoke the entry via the accepting task name.

occam3 (1992) introduced CALL channels (i.e. channels defined with a call protocol). That definition did not allow variants - i.e. for any call channel, only one interface (parameter list) was declared. Sadly, occam3 was never implemented.

JCSP has included variant call channels since (around) 2001. They provide the same mechanism as proposed here, though with the usual Java syntactic overhead.

This proposal is for variant call protocols (with which channels may be declared). The syntax extends the existing variant PROTOCOL mechanism and needs no new keywords. Here is an example with variants that are exclusively calls:

PROTOCOL AGENT
  CASE
    on.holiday (VAL BOOK trash, more.trash, SHARED CHAN HOLIDAY.REPORT report!)
    working ([][]REAL64 invert.this, SHARED CHAN WORK.REPORT report!)
    lunch (SHARED CHAN FOOD from.canteen?, SHARED CHAN LUNCH.REPORT report!)
:

A protocol may be a mix of existing tagged sequential protocols and tagged calls. The difference is easy to parse: the former has a ";" following the tag and the latter has a "(". Tags with no data or call remain allowed. Tags must be different within a particular protocol.

A channel carrying these calls is declared in the usual way - for example:

SHARED ! CHAN AGENT c:

To make a call, a process must have the writing end (in this case, SHARED) of the channel:

PAR
  WHILE TRUE            -- holiday resort process
    SEQ
      ...
      CLAIM c ! on.holiday (basic.oo, advanced.oo, report!)
      ...
  WHILE TRUE            -- workplace process
    SEQ
      ...  generate X
      CLAIM c ! working (X, report!)
      ...  use X
  WHILE TRUE            -- canteen process
    SEQ
      ...
      CLAIM c ! lunch (from.canteen?, report!)
      ...

where, of course, the types of the arguments passed must conform to those declared for the relevant call.

To accept a call, a process must have the receiving end:

PROC agent (CHAN AGENT c?, ...)
  ...  local declarations and initialisations
  INITIAL BOOL alive IS TRUE:
  WHILE alive
    SEQ
      INITIAL BOOL working IS TRUE:
      WHILE working
        c ?? CASE
          working ([][]REAL64 invert.this, SHARED CHAN WORK.REPORT report!)
            ...
          lunch (SHARED CHAN FOOD from.canteen?, SHARED CHAN LUNCH.REPORT report!)
            ...
      INITIAL BOOL holidaying IS TRUE:
      WHILE holidaying
        c ?? CASE
          on.holiday (VAL BOOK trash, more.trash, SHARED CHAN HOLIDAY.REPORT report!)
            ...
:

Call protocol semantics are an extended rendezvous - hence, the use of the extended input ("??") symbol. If any variant of a CASE input is a call accept, that input must be an extended one.

The accept body (i.e. the indented process following each call declaration) may use the call parameters, as well as anything visible globally (e.g. the agent parameters and its locals). The call ends when the indented process ends, whereupon the calling and accepting process go their separate ways.

If there was nothing to return (e.g. some changed data or a mobile channel end), an accept of a call would be the same as an extended input of the parameters in a standard tagged sequential protocol.

Note that the agent in the above example is programmed to accept only certain variants of the call protocol at certain places in its code. As for channels with existing CASE protocols, if an unexpected variant is called, the semantics is STOP. This example system is, of course, unsafe ... since it will deadlock if an on.holiday call arrives while it is working (and that is quite likely). Still, it serves as an example!

Call channels may be used as ALT guards, with a syntax similar to extended input guards - for example:

ALT
  BYTE ch:
  keyboard ?? ch
    ...  extended-input response
    ...  post-guard response
  c ?? CASE
    working ([][]REAL64 invert.this, SHARED CHAN WORK.REPORT report!)
      ...  working rendezvous code
      ...  post-guard response
    on.holiday (VAL BOOK trash, more.trash, SHARED CHAN HOLIDAY.REPORT report!)
      ...  holiday rendezvous code
      ...  post-guard response
  tim ? AFTER timeout
    ...  timeout response

A call protocol guard is the complete call, including the accept body (labelled rendezvous code above). This is similar to an extended input guard, which includes the extended response code. If a post-guard response process is SKIP, it may be omitted.

Example: bounded buffer

This is a standard example. Note that the procedure-like call interface on the channels enables symmetric coding (whereas, in classical occam, the read channel needs supplementing with a read-request channel ... so that the coding of the reads has extra structure over that for writes).

PROTOCOL WRITE
  CASE
    write (VAL THING x)
:

PROTOCOL READ
  CASE
    read (THING x)
:

PROC buffer (VAL INT n, CHAN WRITE in?, CHAN READ out?)
  INITIAL []ITEM b IS MOBILE [n]THING:
  INITIAL INT count IS 0:
  INITIAL INT lo IS 0:
  INITIAL INT hi IS 0:
  WHILE TRUE
    ALT
      (count < n) & in ?? write (VAL THING x)
        b[lo] := x
        count, lo := count + 1, (lo + 1)\n
      (count > 0) & out ?? read (THING x)
        x := b[hi]
        count, hi := count - 1, (hi + 1)\n
:

The call protocols above happen not to be variant - so, the (existing) single-line shorthand for single-option CASE inputs has been used.

Note that the rendezvous codes above are as brief as possible (single lines), with the housekeeping code (maintaining count, lo and hi) kept outside, as post-guard responses.

For these protocols, a writer process would run:

c ! write (x)

and a reader process would run:

d ! read (x)

where c and d are their names for their channels to the buffer.

Speculation: non-variant call protocols

We wonder whether a compatible shorthand for non-variant call protocols could or should be crafted?

A small annoyance in the buffer example above is that the programmer has to work with two names: one for the name of the channel and one for the name of the call (in/write and out/read). Both names are always used together.

A non-variant call protocol could just define a parameter list and the call itself made and accepted via the channel name ... for instance:

PROTOCOL WRITE IS (VAL THING x):

PROTOCOL READ IS (THING x):

PROC buffer (VAL INT n, CHAN WRITE in?, CHAN READ out?)
  INITIAL []ITEM b IS MOBILE [n]THING:
  INITIAL INT count IS 0:
  INITIAL INT lo IS 0:
  INITIAL INT hi IS 0:
  WHILE TRUE
    ALT
      (count < n) & in ?? (VAL THING x)
        b[lo] := x
        count, lo := count + 1, (lo + 1)\n
      (count > 0) & out ?? (THING x)
        x := b[hi]
        count, hi := count - 1, (hi + 1)\n
:

A writer process could run:

c ! (x)

A reader process could run:

d ! (x)

We could further drop the "IS" in the protocol declaration, the "??" in an accept and the "!" in a call. This gets fairly close to the previous occam3 proposal!

Implementation

Rule: input from a channel with call variants is by extended input (??).

Rationale: a call implies an extended rendezvous. We do not propose to allow some variants (e.g. calls) to be extended and others (e.g. a tagged sequence) not to be extended. Existing CASE protocols have the same rule: either all listed variants are part of an extended input or all are not. [Note: without this rule, the syntax for CASE inputs as ALT guards would not be pretty!]

So, getting the tag for a channel with call variants will always be an extended input from the channel. So, the calling process will not be re-scheduled immediately after the call arguments are transferred.

If the tag is for a call, transfer the arguments from caller to acceptor in the most efficient way.

If the calling and accepting processes are in the same memory space, this should be the same way as PROC parameters are set up - i.e. large arguments are always passed by reference and small ones by value (or copy-in-copy-out, if non-VAL data).

If the processes are in different memory spaces, all arguments must be copied over and back (for updated non-VAL data).

Claim: Parallel useage and anti-aliasing rules ensure no semantic difference between these parameter passing mechanisms.

The accepting process executes its body. Updated data is copied back (unless passed by reference).

The calling process is then re-scheduled.

Acknowledgements

Adam Sampson: for pointing out problems if extended input were not mandated for the accept syntax ... and for suggesting the term call protocol, rather than call channel.

Fred Barnes: for raising the issue of how call parameters may be passed safely and efficiently - hopefully, now resolved ...

<<< more text coming >>>

OEP/178 (last edited 2011-06-18 12:53:14 by phw)