AI22-0164-1

!standard X.Y(PP)                                    26-05-25  AI22-0164-1/01

!standard A.B(PP)

!class Amendment 26-05-25

!status work item 26-05-25

!status received 26-05-25

!assigned author Tucker Taft

!submitter Tucker Taft

!priority Medium

!difficulty Medium

!subject Move and Swap operations

!summary

Provide support for Move and Swap operations that take advantage of the implicit level of indirection which will often be used for optional and expandable objects, as proposed in AIs AI22-0152-1 and AI22-0148-1. Also allow the programmer to specify, using a Storage aspect, that the storage for an object should be allocated from the same storage area associated with a preexisting object, with the intent of later swapping or moving the new object into some part of the preexisting object.

!issue

Presuming that one or both of the "optional objects" AI and the "expandable objects" AI are approved, it would be very useful to have operations that recognize that such objects are often represented with a level of indirection, and at least in some cases, the manipulation of implicit pointers can avoid an expensive recursive copy operation.

!recommendation

We recommend that we add support for two operations that take advantage of the implicit level of indirection when possible.  The two operations are Move and Swap.  Move presumes that the source is an optional object, and it moves the content of the RHS into the LHS, leaving a null behind in the RHS.  Constraint_Error will be raised if the target does not allow null, but the prior value of the source is null.  Swap, on the other hand, works whether both or neither of the objects are optional.  It exchanges the content of the two objects. Both Move and Swap would take advantage of the level of indirection if possible, by using (implicit) pointer manipulation rather than physical copying so long as the LHS and the RHS can use the same storage area.^[a][b]

In addition to these two new attributes, we propose a Storage aspect which can be specified when declaring a standalone object, to indicate that it should be allocated from the same storage area as some preexisting object, with the intent of later swapping or moving some part of the new object into some part of the preexisting object.

At a syntax level, we propose that Move can be used as a parameterless attribute function of an optional variable object, when used as the source of an assignment operation, to indicate the creation of a logical copy of the value of the object denoted by the prefix, and then the object's value being set to null.  Here are four contexts where the Move attribute could be used, as each is, effectively, the source of an assignment:

Invoking the Move attribute is meant to be equivalent to invoking a function Move with one in-out parameter, with a body of approximately:

function Move (A : in out null or T) return null or T

is
   Result : constant null or T := A;
begin
   A := null;
   return Result;
end Move;

As implied by the above, using the equivalence that B'Move == Move(B) == B.Move, by the time B'Move is complete, B is null, and the value of the attribute reference is the prior value of B.

The Swap attribute would be a procedure that takes one variable parameter, with the effect of swapping the contents of the prefix and the parameter:^{[l][m][n][o][p][q][r]}

Y.Left'Swap (Y.Right); -- This is a more direct way to swap subtrees.

If we declare the Storage aspect of Y to refer to X, then the assignment of Y.Right'Move into X.Left above would be expected to use pointer manipulation rather than copying:^[s][t][u][v]

!wording

TBD

!discussion

TBD

!example

See the !recommendation above.

!ACATS test

Indicate what sort of ACATS tests would be appropriate to verify correct implementation of this AI.

!appendix

See ARG GitHub issue #149 for some discussion of these operations.

[b]Your comment explains why we propose the Storage aspect below.

[c]I feel uncomfortable to have an attribute that both returns a value and modifies its prefix. I was about to suggest a procedure similar to swap, but then your example wouldn't work...

[d]In my experience using the Move operation in ParaSail, it is often used to initialize another object.  So a procedure doesn't really work.  In ParaSail, the Move operation uses a distinct syntax (<==), but that seems overly disruptive in the context of Ada.  The fact is we now have functions with IN OUT parameters, which could be called using prefix notation, such as X.Move, so it is not so different to have an attribute like X'Move that updates its prefix.

[e]I'm not sure that two wrongs make a right here! Usually, the prefix of a subprogram is modified in a minor way (such as updating the generator for a random number function, or modifying an element of a container), not completely obliterating it. Just because it is legal to write a function that obliterates its prefix doesn't mean anyone should actually write such code, and I certainly don't want to suggest that people do by including that in the language-defined operations.

[f]I'd be happier with new operators here (if we do this at all, which I am unconvinced about -- most of the time, copying is fine and the extra cost is not significant, and Move is always less safe than Copy). These operations don't map well to attributes, which I think you've proven by these examples!

[g]SPARK forbids expressions with side effects. That argues against a 'Move attribute that always nulls its prefix -- opinions from SPARK experts would be welcome. Of course this argument assumes that SPARK will eventually allow optional objects and components, but it would be disappointing if an Ada extension intended to automate memory management could not be included in SPARK.

[h]SPARK has move semantics for its access types, so in fact they have almost exactly this kind of situation.  SPARK also allows side-effects in expressions now, so long as the function has an appropriate declaration (I believe they consider it a "volatile" function).

[i]I fear there will be problems if several 'Move are allowed in the same expression. For one problem: what if X'Move appears twice or more times in the same expression, with the same prefix X? If 'Move nulls its prefix immediately, one of the 'Move will return null, but which one it is may depend on unspecified evaluation order. If 'Move does not null its prefix immediately (as you seem to suggest), there may be two or more references to the same object.

[j]We will probably have to rely on the rules against having the same object as an OUT parameter multiple times in the same expression (6.4.1(6.18/3)).  These rules may need to be tightened a bit as well.

[k]I have clarified that 'Move nulls out the prefix before returning a value.

[l]Swap is symmetric, it should look like it. It makes more sense as a traditional function call (an operator? "<=>"? ":=:"?)

[m]In ParaSail, the swap operation uses syntax that matches one of your suggestions, namely "<=>".

[n]And move is "<==", which can also be used in aggregates and named notation instead of "=>" to indicate that the object providing the value is set to null after being copied/moved.

[o]I was actually thinking more of ":=:" for Swap, and ":-" for Move (the later comes from Simula, if I remember my history of programming languages class 46 years later). I thought that "<=>" looked too much like a  (very weird) relational operator. I'd rather keep these things out of the middle of expressions, much like we don't allow := in expressions. (I realize there a cute examples where they work inside of an expression, but those things don't happen very often in practice unless you are actively looking for them.)

[q]I don't quite understand your last statement here. We have build-in-place for aggregates and function calls, but that is quite different than Move. Move requires the object is allocated from the same pool as the result, which would imply changing the master that applies to function results and aggregates in some cases. Sounds scary.

[r]The intent here is that when building an aggregate as the RHS of an assignment, the compiler would try to build it in the appropriate storage area, so something like a "Move" could be used to do the assignment without a physical copy.  Similarly, when assigning the result of a function call with a large result, the compiler would do what it could to avoid a physical copy, by passing in an address (for known-size objects) or a storage area (for unknown-size objects) where the result should be built.  The point is that there should be no reason for the programmer to explicitly invoke a "Move" operation when the RHS is an aggregate or a (non-aliased result) function call, since a compiler would already avoid extra copies when possible.

[s]This would imply that the (some of the) memory of Y is not recovered until the scope of X is left. Are we OK with an aspect which guarantees a (temporary) storage leak? If X is a global object, the memory will never be recovered during the life of the program. Also, X would have to live longer than Y (I guess as an aspect that has to be the case).

[t]Y is still finalized and the storage it occupies is expected to be reclaimed when it goes out of scope, if it is not null. The expectation, however, is that a local variable declared this way is expected to be null by the time it goes out of scope.  If it is *not* null, then this implies putting the storage occupied by Y onto the free list associated with the storage area associated with X.  This is the same thing that would happen if some optional component of X were set to null.  So another way to think about this is that if Y is not null when it goes out of scope, it is set to null, with that having the usual effects.

[u]??? "Free list". This memory is allocated from storage pools, just like any other. Yes, the storage pool internally has a list of allocated nodes, but there is no way to move nodes from one pool to another (there are no such operations in storage pools). At least in my proposed implementation, one uses the same code to handle assignments to all objects with optional componants, which includes allocated objects, so one can only assume the basic pool operations.

[v]I think we are in agreement here.  I was just emphasizing that if Y is allocated out of the area associated with X, then reclaiming Y would put its storage on a free list for that storage area.  And the simplest way to describe what happens when Y goes out of scope is that it is assigned null.

[w]This doesn't make much sense. If the point of this to to avoid copying, it doesn't make sense for it to be optional. It doesn't work very well for bounded objects, either. I still prefer Move and Swap to be illegal/raise Program_Error if they have to make a copy.

[x]Performance is almost never guaranteed by any sort of normative rule.  We could require documentation, I suppose, and compilers could certainly provide warnings.  I would hope that compilers would notice that the last use of a local variable is a "move" (or swap) and automatically allocate it in the most efficient storage area.  It seems overkill to require the programmer to always specify this.  Also, for smallish objects, there is no need to worry about the storage location, but you still might like the "move" semantics.