Louis Dionne poses the problem of

*move independence*in the context of C++, that is, under which conditions a sequence of operationsf(std::move(x)); g(std::move(x));

is sound in the sense that the first does not interfere with the second. We give here a functional definition for this property that can be applied to the case Louis discusses.

Let

*X*be some type and functions*f*:*X*→*T*×*X*and*g*:*X*→*Q*×*X*. The impurity of a non-functional construct in an imperative language such as C++ is captured in this functional setting by the fact that these functions return, besides the output value itself, a new, possibly changed, value of*X*. We denote by*f*and_{T}*f*the projection of_{X}*f*onto*T*and*X*, respectively, and similarly for*g*. We say that*f does not affect g*if*g*

*(*

_{Q}*x*) =

*g*

*(*

_{Q}*f*(

_{X}*x*)) ∀

*x*∈

*X*.

If we define the equivalence relationship ~

*in*_{g}*X*as*x*~

_{g}*y*iff

*g*

*(*

_{Q}*x*) =

*g*

*(*

_{Q}*y*),

then

*f*does not affect*g*iff*f*(

_{X}*x*) ~

_{g}*x*∀

*x*∈

*X*

or

*f*([

_{X}*x*]

*) ⊆ [*

_{g}*x*]

*∀*

_{g}*x*∈

*X*,

where [

*x*]*is the equivalence class of*_{g}*x*under ~*.*_{g}
We say that

*f*and*g*are*mutation-independent*if*f*does not affect*g*and*g*does not affect*f*, that is,*f*([

_{X}*x*]

*) ⊆ [*

_{g}*x*]

*and*

_{g}*g*([

_{X}*x*]

_{f}

*) ⊆ [*

_{}*x*]

_{f}

*∀*

_{}*x*∈

*X,*

The following considers the case of

*f*and*g*acting on separate components of a tuple: suppose that*X*=*X*_{1}×*X*_{2}and*f*and*g*depend on and mutate*X*_{1}and*X*_{2}alone, respectively, or put more formally:*f*(

_{T}*x*

_{1},

*x*

_{2}) =

*f*(

_{T}*x*

_{1},

*x'*

_{2}),

*f*

_{X2}(

*x*

_{1},

*x*

_{2}) =

*x*

_{2},

*g*

*(*

_{Q}*x*

_{1},

*x*

_{2}) =

*g*

*(*

_{Q}*x'*

_{1},

*x*

_{2}),

*g*

_{X1}(

*x*

_{1},

*x*

_{2}) =

*x*_{1}

for all

*x*_{1},*x'*_{1}∈*X*_{1},*x*_{2},*x'*_{2}∈*X*_{2}. Then*f*and*g*are mutation-independent (proof trivial). Getting back to C++, given a tuple x, two operations of the form:f(std::get<i>(std::move(x))); g(std::get<j>(std::move(x)));

are mutation-independent if i!=j; this can be extended to the case where f and g read from (but not write to) any component of x except the j-th and i-th, respectively.

## No comments :

## Post a Comment