www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - pop & popFront combined

reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
Is there a reason why popFront doesn't automatically return what 
front does?

If so I'm still missing a combined variant of pop and popFront in 
std.range.
Why isn't such a common operation in Phobos already?
Sep 20 2014
next sibling parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Saturday, 20 September 2014 at 18:59:03 UTC, Nordlöw wrote:

 Is there a reason why popFront doesn't automatically return 
 what front does?

 If so I'm still missing a combined variant of pop and popFront 
 in std.range.
 Why isn't such a common operation in Phobos already?


Sometimes after popping, the previous `front` is no longer valid, 
such as in the case of a buffer being reused. We should be 
careful about promoting using a previously read `front` after 
`popFront` until we figure out what we want to do about these 
"transient ranges".

If you want move semantics, use `moveFront`.
Sep 20 2014
next sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 20 September 2014 at 19:23:46 UTC, Jakob Ovrum wrote:

 Sometimes after popping, the previous `front` is no longer 
 valid, such as in the case of a buffer being reused. We should 
 be careful about promoting using a previously read `front` 
 after `popFront` until we figure out what we want to do about 
 these "transient ranges".

 If you want move semantics, use `moveFront`.


Excellent! Thanks!
Sep 20 2014
prev sibling next sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 20 September 2014 at 19:23:46 UTC, Jakob Ovrum wrote:

 If you want move semantics, use `moveFront`.


But x.moveFront doesn't modify x.

What I want is to transform my uses of std.range from

if (!x.empty)
{
     x.front.doStuff;
     x.popFront;
}

into

if (!x.empty)
     if (auto front = x.stealFront)
     {
         front.doStuff;
     }

This is more functional/atomic, that is it reduces the risk of 
accidentally forgetting to call popFront at the end.

Destroy!
Nov 01 2014
next sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 1 November 2014 at 11:43:28 UTC, Nordlöw wrote:

 if (!x.empty)
     if (auto front = x.stealFront)
     {
         front.doStuff;
     }

 This is more functional/atomic, that is it reduces the risk of 
 accidentally forgetting to call popFront at the end.


Forgot my explicit question:

So why isn't something like x.stealFront already in Phobos?
Nov 01 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 1 November 2014 at 11:45:25 UTC, Nordlöw wrote:

 So why isn't something like x.stealFront already in Phobos?


First try here:

https://github.com/nordlow/justd/blob/master/range_ex.d#L14

Please comment!
Nov 01 2014
next sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 1 November 2014 at 13:22:34 UTC, Nordlöw wrote:

 https://github.com/nordlow/justd/blob/master/range_ex.d#L14

 Please comment!


What's the recommended way of making stealFront and stealBack 
inout here? Can I somehow use auto ref together with inout?
Nov 01 2014
next sibling parent reply "anonymous" <anonymous example.com> writes:
On Saturday, 1 November 2014 at 13:25:03 UTC, Nordlöw wrote:

 On Saturday, 1 November 2014 at 13:22:34 UTC, Nordlöw wrote:

 https://github.com/nordlow/justd/blob/master/range_ex.d#L14

 Please comment!


 What's the recommended way of making stealFront and stealBack 
 inout here? Can I somehow use auto ref together with inout?


I don't see what you'd need inout for here. stealFront/stealBack 
are not methods.
Nov 01 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 1 November 2014 at 13:36:05 UTC, anonymous wrote:

 I don't see what you'd need inout for here. 
 stealFront/stealBack are not methods.


inout can be used on free functions aswell. See for example

https://github.com/nordlow/justd/blob/master/algorithm_ex.d#L674
Nov 01 2014
parent "anonymous" <anonymous example.com> writes:
On Saturday, 1 November 2014 at 14:01:42 UTC, Nordlöw wrote:

 On Saturday, 1 November 2014 at 13:36:05 UTC, anonymous wrote:

 I don't see what you'd need inout for here. 
 stealFront/stealBack are not methods.


 inout can be used on free functions aswell. See for example

 https://github.com/nordlow/justd/blob/master/algorithm_ex.d#L674


Sure, but it doesn't buy you anything in these cases, does it? 
You can just drop inout from overlapInOrder. It's fully 
templated. T can be const/immutable and you get a const/immutable 
result. Works fine.
Nov 01 2014
prev sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Saturday, 1 November 2014 at 13:25:03 UTC, Nordlöw wrote:

 On Saturday, 1 November 2014 at 13:22:34 UTC, Nordlöw wrote:

 https://github.com/nordlow/justd/blob/master/range_ex.d#L14

 Please comment!


 What's the recommended way of making stealFront and stealBack 
 inout here? Can I somehow use auto ref together with inout?


If you want to avoid the temporary variable, you could write:

     scope(success) r.popFront;
     return r.moveFront;
Nov 01 2014
next sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 1 November 2014 at 13:38:22 UTC, Marc Schütz wrote:

 If you want to avoid the temporary variable, you could write:

     scope(success) r.popFront;
     return r.moveFront;


Does this solution cost performance?
Nov 01 2014
next sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 1 November 2014 at 13:54:31 UTC, Nordlöw wrote:

 On Saturday, 1 November 2014 at 13:38:22 UTC, Marc Schütz wrote:

 If you want to avoid the temporary variable, you could write:

    scope(success) r.popFront;
    return r.moveFront;


 Does this solution cost performance?


I guess we have to look at the assembler output to be sure. Is 
there a convenient way to do this in LDC?
Nov 01 2014
parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Saturday, 1 November 2014 at 14:19:56 UTC, Nordlöw wrote:

 On Saturday, 1 November 2014 at 13:54:31 UTC, Nordlöw wrote:

 On Saturday, 1 November 2014 at 13:38:22 UTC, Marc Schütz 
 wrote:

 If you want to avoid the temporary variable, you could write:

   scope(success) r.popFront;
   return r.moveFront;


 Does this solution cost performance?


 I guess we have to look at the assembler output to be sure. Is 
 there a convenient way to do this in LDC?


ldc2 -O3 -output-s -c test.d

Generates test.s.
Nov 02 2014
prev sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Saturday, 1 November 2014 at 13:54:31 UTC, Nordlöw wrote:

 On Saturday, 1 November 2014 at 13:38:22 UTC, Marc Schütz wrote:

 If you want to avoid the temporary variable, you could write:

    scope(success) r.popFront;
    return r.moveFront;


 Does this solution cost performance?


I think DMD doesn't generate good code for it; IIRC it lowers 
scope(success) to a strange construct with an invisible variable 
and a try/catch. Don't know the reasons for this, maybe it has 
changed by now. Theoretically it would just need to move the 
contents of the scope(success) after the evaluation of the 
returned expression, which is cheap.
Nov 02 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Sunday, 2 November 2014 at 11:46:19 UTC, Marc Schütz wrote:

 I think DMD doesn't generate good code for it; IIRC it lowers 
 scope(success) to a strange construct with an invisible 
 variable and a try/catch. Don't know the reasons for this, 
 maybe it has changed by now. Theoretically it would just need 
 to move the contents of the scope(success) after the evaluation 
 of the returned expression, which is cheap.


Are there cases in LDC where

     auto e = r.moveFront;
     r.popFront;
     return e;

generates code less efficient than

     scope(success) r.popFront;
     return r.moveFront;

because of the extra assignment?
Nov 02 2014
parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Sunday, 2 November 2014 at 12:29:14 UTC, Nordlöw wrote:

 On Sunday, 2 November 2014 at 11:46:19 UTC, Marc Schütz wrote:

 I think DMD doesn't generate good code for it; IIRC it lowers 
 scope(success) to a strange construct with an invisible 
 variable and a try/catch. Don't know the reasons for this, 
 maybe it has changed by now. Theoretically it would just need 
 to move the contents of the scope(success) after the 
 evaluation of the returned expression, which is cheap.


 Are there cases in LDC where

     auto e = r.moveFront;
     r.popFront;
     return e;

 generates code less efficient than

     scope(success) r.popFront;
     return r.moveFront;

 because of the extra assignment?


I'm not sure. If the element type has a postblit, there might be 
some obscure corner case where the language specification 
requires a copy if you declare a named variable. In general I 
would expect no (language level) copy to take place. The result 
of `moveFront` can just be moved into the yet uninitialized `e`, 
which later can be moved up to the caller. These are simple 
bitblits, not copies.
Nov 02 2014
prev sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 1 November 2014 at 13:38:22 UTC, Marc Schütz wrote:

 If you want to avoid the temporary variable, you could write:

     scope(success) r.popFront;
     return r.moveFront;


Nice solution anyhow! Thanks!
Nov 01 2014
prev sibling next sibling parent reply "anonymous" <anonymous example.com> writes:
On Saturday, 1 November 2014 at 13:22:34 UTC, Nordlöw wrote:

 On Saturday, 1 November 2014 at 11:45:25 UTC, Nordlöw wrote:

 So why isn't something like x.stealFront already in Phobos?


 First try here:

 https://github.com/nordlow/justd/blob/master/range_ex.d#L14

 Please comment!


That is:


 auto ref stealFront(R)(ref R r)
 {
 import std.range: moveFront, popFront;
 auto e = r.moveFront;
 r.popFront;
 return e;
 }


`auto ref` is nonsense here. You can't return a reference to `e`
as
it's a local variable.
Nov 01 2014
next sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Saturday, 1 November 2014 at 13:30:16 UTC, anonymous wrote:

 On Saturday, 1 November 2014 at 13:22:34 UTC, Nordlöw wrote:

 On Saturday, 1 November 2014 at 11:45:25 UTC, Nordlöw wrote:

 So why isn't something like x.stealFront already in Phobos?


 First try here:

 https://github.com/nordlow/justd/blob/master/range_ex.d#L14

 Please comment!


 That is:


 auto ref stealFront(R)(ref R r)
 {
 import std.range: moveFront, popFront;
 auto e = r.moveFront;
 r.popFront;
 return e;
 }


 `auto ref` is nonsense here. You can't return a reference to `e`
 as
 it's a local variable.


It's probably intended to mean `auto` + `ref`, not `auto ref`. 
`ref` alone is already sufficient to get type deduction.
Nov 01 2014
parent "anonymous" <anonymous example.com> writes:
On Saturday, 1 November 2014 at 13:36:05 UTC, Marc Schütz wrote:

 On Saturday, 1 November 2014 at 13:30:16 UTC, anonymous wrote:


[...]

 auto ref stealFront(R)(ref R r)
 {
 import std.range: moveFront, popFront;
 auto e = r.moveFront;
 r.popFront;
 return e;
 }






[...]

 It's probably intended to mean `auto` + `ref`, not `auto ref`. 
 `ref` alone is already sufficient to get type deduction.


But ref is wrong. The function returns a local. Just auto would
be fine.
Nov 01 2014
prev sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 1 November 2014 at 13:30:16 UTC, anonymous wrote:

 `auto ref` is nonsense here. You can't return a reference to `e`
 as
 it's a local variable.


My mistake. Thanks.
Nov 01 2014
prev sibling parent =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Saturday, 1 November 2014 at 13:22:34 UTC, Nordlöw wrote:

 https://github.com/nordlow/justd/blob/master/range_ex.d#L14


Moved here:

https://github.com/nordlow/phobos-next/blob/master/src/range_ex.d#L66
May 11 2016
prev sibling parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Saturday, 1 November 2014 at 11:43:28 UTC, Nordlöw wrote:

 On Saturday, 20 September 2014 at 19:23:46 UTC, Jakob Ovrum 
 wrote:

 If you want move semantics, use `moveFront`.


 But x.moveFront doesn't modify x.


It does modify `x` as it leaves `front` in a destroyed and 
default-initialized state, as required by move semantics.


 What I want is to transform my uses of std.range from

 if (!x.empty)
 {
     x.front.doStuff;
     x.popFront;
 }

 into

 if (!x.empty)
     if (auto front = x.stealFront)
     {
         front.doStuff;
     }

 This is more functional/atomic, that is it reduces the risk of 
 accidentally forgetting to call popFront at the end.

 Destroy!


The other half of my post explained why such a `stealFront` is 
problematic.
Nov 01 2014
next sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 1 November 2014 at 16:10:17 UTC, Jakob Ovrum wrote:

 The other half of my post explained why such a `stealFront` is 
 problematic.


Got it. Thanks!
Nov 01 2014
prev sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 1 November 2014 at 16:10:17 UTC, Jakob Ovrum wrote:

 problematic.


What about turning stealFront and stealBack at

https://github.com/nordlow/justd/blob/master/range_ex.d

into mixins?
Nov 01 2014
prev sibling next sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 20 September 2014 at 19:23:46 UTC, Jakob Ovrum wrote:

 Sometimes after popping, the previous `front` is no longer 
 valid, such as in the case of a buffer being reused. We should


This seems like a error-prone design to me.

I guess performance is the motivation right?

Maybe a future data-flow analysis á lá Rust could come to the 
rescue here ;)
Nov 01 2014
prev sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 20 September 2014 at 19:23:46 UTC, Jakob Ovrum wrote:

 Sometimes after popping, the previous `front` is no longer 
 valid, such as in the case of a buffer being reused.


Is there a suitable trait we can use to detect this and in turn 
use to disallow stealFront() and stealBack() in these cases?

  We should

 be careful about promoting using a previously read `front` 
 after `popFront` until we figure out what we want to do about 
 these "transient ranges".
Nov 01 2014
parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 1 November 2014 at 20:48:45 UTC, Nordlöw wrote:

 Is there a suitable trait we can use to detect this and in turn 
 use to disallow stealFront() and stealBack() in these cases?


Made it a separate new question at

http://forum.dlang.org/thread/onibkzepudfisxtrigsi forum.dlang.org#post-onibkzepudfisxtrigsi:40forum.dlang.org
Nov 01 2014
prev sibling next sibling parent reply "AsmMan" <jckj33 gmail.com> writes:
On Saturday, 20 September 2014 at 18:59:03 UTC, Nordlöw wrote:

 Is there a reason why popFront doesn't automatically return 
 what front does?

 If so I'm still missing a combined variant of pop and popFront 
 in std.range.
 Why isn't such a common operation in Phobos already?


So far I know isn't common use return value from popFront() at 
same time it's called. For example, checkout how is:

int[] a = [1,2,3];
foreach(int n; a) {}

is translated:

for(auto r = a; !r.empty; r.popFront())
{
   int n = r.front;
}

to return same as value in front by popFront() save previously 
value is needed:

int popFrontInt(out int[] arr)
{
    int current = arr[0]; // or arr.front
    arr = arr[1 .. $];
    return current;
}

(this isn't exactly like Phobos implementation and is int[]-only, 
btw)

the cost of the 'current' variable may be a bit expansive (one 
extra register use per function call) and useless, since it isn't 
used and a common use is one like the loop.

I think it's well-designed, IMHO...


 On Saturday, 20 September 2014 at 18:59:03 UTC, Nordlöw wrote:
 If you want move semantics, use `moveFront`.


Is this function part of phobos library? if so, where?
Sep 20 2014
parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Saturday, 20 September 2014 at 19:40:02 UTC, AsmMan wrote:

 Is this function part of phobos library? if so, where?


It's in std.range.
Nov 01 2014
prev sibling parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 09/20/2014 11:59 AM, "Nordlöw" wrote:

 Is there a reason why popFront doesn't automatically return what front
 does?

 If so I'm still missing a combined variant of pop and popFront in
 std.range.
 Why isn't such a common operation in Phobos already?


It is also related to exception safety. It took the C++ community to 
realize that a Stack data structure with pop() returning the top object 
cannot be made exception safe. The solution was to separate pop() from 
top().

Here is the original paper demonstrating the impossibility:

 
http://ptgmedia.pearsoncmg.com/imprint_downloads/informit/aw/meyerscddemo/DEMO/MAGAZINE/CA_FRAME.HTM

Here is Herb Sutter's presentation of the solution:

   http://www.gotw.ca/gotw/008.htm

Ali
Sep 20 2014