[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Mobile variables
oops forgot to add the reference - http://www.luca.demon.co.uk/
Paddy Nixon wrote:
>
> I can't write a long reply to this now as I have 15 Georgians here for
> the week. I have lately been reading up on work in the mobility
> community and they attack the concept of mobile variables quiet
> aggressively - and although it isn't in a shared memory context the same
> concepts apply.
>
> Now - the thing is - they haven't captured the solution to mobile
> variable (and state) quiet as succinctly and cleverly as you have
> Adrian. There is definetly something in this. I will endeavour to dig
> out some references towards the end fo the week on similiar ideas in
> order that we can compare you approach.
>
> In the meantime, the only reference I have to hand is some theory work
> being done by Luca Cardelli and Andrew Gordon. They are developing a
> calculus (called Ambient Calculus) to address explicitly the problems of
> mobility (code, state, variablers, objects etc...). His problem is -
> they don't have a suitable language to implement the abstractions. Now
> JCSP et al might offer an interesting implementation route...?
>
> Sorry about the ramble - but the ideas are too nice to ignore. I'll
> collect myself for a more coherent response later in the week.
>
> cheers
>
> Paddy
>
> Adrian Lawrence wrote:
> >
> > Mobile Variables
> > ================
> >
> > This is so obvious that it must have been suggested before?
> >
> > A common objection to message passing in shared memory is that it involves
> > redundant copying. A large buffer in shared memory passed across a channel
> > will be copied. To avoid that, we might turn off usage checking, allow
> > concurrent access, and impose CREW by passing an access token across a
> > channel. Or we might pass an ARRAY pointer. Such techniques are well known
> > in the occam community.
> >
> > But a simple language extension puts this on a sound footing and makes code
> > transparent and elegant. Introduce channels that transport *variables*.
> >
> > Doing this in a very general way can present problems with static memory
> > allocation, aliasing, usage checking and transportation of variables out
> > of their scope.
> >
> > But the slightly restricted version below seems to overcome those problems.
> >
> > If a variable x is sent on a channel c, it is as if it is taken out of
> > scope. So after c ! VAR x , x is no longer accessible.
> >
> > After the matching c ? VAR x, it is as if x has come into scope.
> > "As if" is used above in case "scope" is taken to be static and textual.
> > So this "dynamic scoping" is really a dynamic usage rule.
> > Notice that we require the input to use the same name x: we must avoid
> > aliasing. And it conforms to static textual scoping: x remains in scope
> > in the existing sense.
> >
> > Consider:
> >
> > --{{{ example
> > MOBILE INT x: -- "MOBILE" is redundant but avoids the compiler needing
> > -- to search forward. "SHARED" is an alternative.
> > CHAN OF VAR x c: -- must reference existing variable(s) in scope
> > -- (This alone is enough to imply that x is MOBILE)
> >
> > CLAIM x -- like a PAR, but claims exclusive access for first process
> > SEQ
> > x := 42
> > c ! VAR x -- export access rights, in effect exporting the variable
> > SEQ
> > c ? VAR x -- receive exclusive access right to x
> > ... -- presumably use x for something here
> >
> > -- x is implicitly released here at the end of the scope of the CLAIM.
> > -- Thus x is now subject to normal usage rules unless another CLAIM is
> > -- made.
> > --}}}
> >
> > The idea is that the movable variable (x above) is declared in outer scope.
> > This restricts the construct to a shared memory, although the motivation
> > was to permit static memory allocation.
> >
> > The declaration
> > MOBILE INT x:
> > is designed to allow the compiler to determine that the variable x will be
> > used in a VAR channel (or at least CLAIMed) without having to look ahead.
> > Since the idea has similarities to a SHARED channel, perhaps this should be
> > SHARED INT x: ?
> > But SHARED seems to have exactly the wrong connotations here.
> > This special declaration is intended to facilitate one possible
> > implementation strategy where the compiler reserves storage for the variable
> > together with a flag. Perhaps "MOBILE/SHARED" is unnecessary?
> >
> > The declaration
> > CHAN OF VAR x c: -- does this need brackets: CHAN OF (VAR x) c : ?
> > which specifies the variable(s) explicitly rather than
> > CHAN OF VAR INT c:
> > provides a simple way to avoid variables being exported out of their scope.
> > However this needs care when abbreviations are involved including formal
> > parameters of procedures.
> >
> > The CLAIM syntax is really a special sort of PAR (with a PRI CLAIM
> > matching a PRI PAR). It allows the compiler to determine which sort
> > of usage check to apply.
> >
> > In the scope of
> > CLAIM v1,v2,v3
> > the variables v1,v2 and v3 must be held exclusively by a single branch.
> > If any of v1,v2 and v3 were not already CLAIMed, then they are
> > owned by the first component until any are moved by a VAR communication.
> > At the end of the CLAIM, any of the variables still held are released to
> > the enclosing environment. So a CLAIM has two functions:-
> > a) to determine the usage rules; and
> > b) to make the initial allocation of ownership.
> >
> > The compiler applies two usage rules:
> > 1) the usual CREW for components of any embedded (PRI) PARs augmented
> > to exclude any VAR communications;
> > 2) the new dynamic exclusive rule which will usually be implemented by
> > code generation which applies to the components of a CLAIM.
> >
> > When applying rule 1) to an embedded PAR, the compiler regards a CLAIM v
> > as equivalent to a local declaration
> > (type) v:
> > This permits the compiler to use the existing static usage checks at compile
> > time. Run time code determines whether v is held: if it is not, any
> > reference is an error and behaves as STOP.
> >
> > Although a optimising compiler might be able to dispense with a
> > CLAIM v1,v2,v3
> > altogether when applying rule 2 to simple cases, rule 2 will usually be
> > implemented at run time by the code generated with minimal overhead. Thus
> > most compilers can simply omit any static usage checks on CLAIMed
> > variables not appearing in an embedded PAR.
> >
> > Outside the CLAIM, rule 1 applies as usual.
> > So a variable can be accessed under both sharing schemes: otherwise
> > there might still be some residual redundant copying in certain
> > applications.
> >
> > VAR communications might be implemented by passing
> > a pointer to the MOBILE variable, or a token of the access rights.
> >
> > The VARs in c ! VAR x and c ? VAR x are strictly redundant: the
> > channel type determines that the objects must be variables. But the
> > explicit VARs make it easier to read and understand the code.
> >
> > PAR
> > c1 ! VAR x
> > c2 ! VAR x
> > is banned for obvious reasons. But so is
> > PAR
> > c ! VAR x
> > y := 5
> > because the communicating branch does not have exclusive access to x.
> > This should be
> > CLAIM x
> > c ! VAR x -- an error if the CLAIM was not successful
> > y := 5
> > which shows why embedded CLAIMs on the same variable are permitted.
> > VAR communications are only permitted where there is exclusive access
> > obtained by a local CLAIM: local here means that the closest enclosing
> > parallel constructor is a (PRI) CLAIM of the relevant variable.
> > Likewise
> > CLAIM x
> > c ? VAR x -- this one is an error if the CLAIM succeeded
> > y := 5
> > is valid. If the CLAIM on x succeeds, then c ? VAR x is an error and
> > behaves as STOP. But the CLAIM on x is expected to fail: its purpose here
> > is to inform the compiler to generate mutually exclusive code in any
> > reference to x.
> >
> > In general the compiler cannot track the dynamic movement of a variable
> > by static analysis: attempting to output a variable that is not held at
> > run time is an error, and compiles as STOP.
> > If a program needs to test for access rights, it can use code like:
> > IF
> > x = x -- the compiler compiles access test
> > c ! VAR x -- which it needs anyway here, so it might conflate?
> > TRUE
> > ... whatever
> > Or is that too obscure? The alternative seems to be yet another key word,
> > OWN x, maybe? :-( But it would give the compiler a much better opportunity
> > to optimize code like that above.
> >
> > At the end of a CLAIM block, if the variable is "held" it is passed up
> > to the next enclosing CLAIM if any. Otherwise, the shared variable reverts
> > to its normal usage matching the textual scope.
> >
> > Both CLAIMs and CHANs can use lists of variables, including arrays.
> > Examples:
> >
> > CHAN OF VAR x1,x2,x3,x4 c : -- allows c to move only these
> > CLAIM p,q,r,s,t -- CLAIMs 5 variables
> >
> > Inputs on VAR channels involving several variables use variant protocol
> > syntax. Notice that there is no need for an implementation to employ
> > tags. If access rights are passed by token, these are equivalent to tags.
> > If variable address/pointers are passed, these also are their own
> > identifiers. The second example at the end of this note illustrates
> > the CASE syntax.
> >
> > --{{{ Semantics
> >
> > An informal account can be given in terms of passing the address/pointer
> > to the shared variable.
> > Outside a claim the pointer/address of the variable is kept in outer scope.
> > A CLAIM moves that pointer into the "local scope"/workspace of the first
> > branch. It may be moved on an appropriate VAR channel: the sender may
> > not retain a copy. At the end of the CLAIM, the pointer is moved back to
> > outer scope. Such a scheme might use a Not_a_Pointer value for empty
> > slots. Such a run time strategy means that the compiler need do no usage
> > checking within CLAIMs.
> >
> > Another implementation could involve access tokens, especially if
> > addresses were expensive to move.
> > A MOBILE variable might have a boolean stored with it: if TRUE,
> > the variable is "present": subject to the usual rules: CREW usage checking
> > in PARs.
> > However, a CLAIM results in the associated value being FALSE which
> > means that some process has exclusive access to the variable.
> > The boolean becomes TRUE again only when the variable is RELEASEd.
> >
> > --}}}
> >
> > The example below illustrates several points, including the
> > possible need to include extra type specifications in CHAN OF VAR formal
> > parameters.
> > Care needs to be taken to avoid unintentional aliasing of MOBILE
> > variable names: recall that the meaning of formal parameters is defined
> > by abbreviation.
> >
> > --{{{ Another example
> > [2][rows][cols]INT image:
> >
> > --{{{ produce
> > PROC produce(CHAN OF VAR [2][rows][cols]INT image[0],
> > [2][rows][cols]INT image[1] in,out)
> > INT ping,pong:
> > SEQ
> > ping := 1
> > WHILE TRUE
> > SEQ
> > pong := ping
> > ping := ping >< 1
> > CLAIM image[ping]
> > SEQ
> > ... fill image[ping] from camera
> > out ! VAR image[ping]
> > CLAIM image[pong]
> > in ? CASE VAR image[pong]
> > :
> > --}}}
> > --{{{ consume
> > PROC consume(CHAN OF VAR [2][rows][cols]INT image[0],
> > [2][rows][cols]INT image[1] in,out:)
> > INT ping,pong:
> > SEQ
> > ping := 1
> > WHILE TRUE
> > SEQ
> > pong := ping
> > ping := ping >< 1
> > CLAIM image[pong}
> > out ! VAR image[pong]
> > CLAIM image[ping]
> > SEQ
> > in ? CASE VAR image[ping]
> > ... process
> > :
> > --}}}
> >
> > CHAN OF VAR image[0],image[1] up,down:
> >
> > CLAIM image[0] -- we expect this to eliminate an indirection
> > produce(up,down)
> > CLAIM image[1]
> > consume(up,down)
> > SKIP
> >
> > -- If there were more than 2 buffers, or if we wished to make things more
> > -- symmetrical, we could have a process that CLAIMed all the buffers, and
> > -- then distributed the variables down VAR channels to the components...
> > -- Or produce(..) could CLAIM both, and send one on initially. Roll your
> > -- own.
> > --}}}
> >
> > --{{{ Questions
> >
> > 1) What have I overlooked? What pathologies can arise?
> >
> > 2) Should c ! VAR x and c ? VAR x be written as c ! x and c ? x.
> > Do we need to flag the nature of the communication to make the code
> > easier to understand?
> >
> > 3) Is the typing right?
> >
> > 4) Using explicit variable names in the VAR CHAN protocol solves some
> > problems, but makes it very easy to introduce aliasing in the
> > formal parameters of PROCedures. Is there a better way?
> >
> > 5) Is implementation feasible and simple?
> >
> > 6) Has something like this or better already been suggested?
> > --}}}
> >
> > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> >
> > These are thoughts to get discussion going. I have changed my mind several
> > times today alone about some aspects, so I might want to retract or modify.
> > And I have probably overlooked something or other.
> >
> > But has anything of this sort been done before? Is there anything similar
> > in other languages? Is this interesting/useful/promising?
> >
> > Adrian
> > --
> > A E Lawrence, MA., DPhil. adrian.lawrence@xxxxxxxxxxxxxx
> > MicroProcessor Unit, 13, Banbury Road, Oxford. OX2 6NN. UK.
> > Voice: (+44)-1865-273274, Fax: (+44)-1865-273275