[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Mobile variables
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