array.pop_back() does not return its element

[BryantLam]

# Chapel 1.16
proc pop_back()
  Remove the last element from the array, reducing the size of the domain by one.

array.pop_back() does not return its element. It should. (Why doesn't it?)

Also, list.pop_front() does return an element.

[bradcray]

@daviditen : Can you weigh in on this one? Is it just oversight?

[daviditen]

The array-as-vector functionality was modeled heavily after C++ std::vector, and std::vector's pop_back() doesn't return the popped element for exception safety reasons.

I haven't dug too deeply into the problem, but at a glance I think that if our copy-initializers are able to throw an error we're in the same boat as C++, but if not it can safely return the popped value.

[BryantLam]

Exception safety is a good reason to not have it. -- list.pop_front shouldn't return an element in that case.

[mppf]

The array-as-vector functionality was modeled heavily after C++ std::vector, and std::vector's pop_back() doesn't return the popped element for exception safety reasons.

I haven't dug too deeply into the problem, but at a glance I think that if our copy-initializers are able to throw an error we're in the same boat as C++, but if not it can safely return the popped value.

I disagree about this being a good enough answer here. Certainly it's the historical reason.

But Chapel and C++ have different memory management strategies - in particular while both support ideas like RAII and value types with copy constructors/initializers, the C++ model is more restrictive, significantly.

In particular, in C++ there are two starting-point assumptions that are not true for Chapel:

1. The language supports value types with self-referential pointers
2. Types must opt-in to "move" construction

In Chapel, we simply do not expect a record that contains a c_ptr to itself to remain a reasonable object. Since Chapel doesn't actually have pointers the way C++ does, and since it doesn't support ref fields, you'd actually have to use a c_ptr to even create this pattern. But the language does not support it.

As a result, for a call like this:

   var x = something.pop();

there is not any copy-initialization occurring in that line of code. The value is always "moved". (There are exceptions for things like array slices, and that is where I'd characterize the question as not entirely settled). This design is described in CHIP 13.

So, based on CHIP 13 rules, there isn't a copy initialization for typical use of a pop function. Is there copy-initialization within the pop function?

The answer is that there could be, but pop could also be implemented in a way that does not need copy-initialization. For example:

proc something.pop() {
  var ret:elementType;
  ret <=> elements[end]; // swap, assuming this does not use `=` overloads
  return ret;
}

might be one way to write it, but it depends on what we decide is the fate of the swap operator & whether or not it's reasonable for it to default to a low-level "bit copy" type swap. In any case if swap doesn't do what I'm trying to convey here, it could be implemented with more low level constructs.

The idea in the above code example is to perform two actions:

1. "move" the value from the end of the array/container into a local variable
2. "move" a default-initialized value into the value at the end of the array/container.

Note though, a different way of representing growable arrays/vectors wouldn't even need default initialization, if it tracked the bounds of which element slots were initialized vs. just allocated.

So, I'm saying that the argument "We can't write a pop function without having it possibly call a copy initialization that could throw" is just not accurate.

But, what if pop did call a copy-initializer, and what if the copy initializer did throw? We can agree that pop could be written in a way that copy-initializes.

First of all, right now, a copy-initializer can't throw. (see #6145, but @psahabu has a more specific design proposal for throwing initializers). So this can't be a problem right now.

Second of all, even if the copy-initializer did throw, the author of the pop function would be made aware of this (because they'd have to mark their functions throws to propagate). At that point, I think it's reasonable to expect that the author of the pop function handle the errors correctly.

It seems from the Stack Overflow post linked above that idea that pop_back in C++ doesn't return the element for the reason of exceptions seems to come from this document: Exception Handling: A False Sense of Security. While I think that document is a reasonable historical artifact about C++ exceptions, I disagree with its main argument (that in C++ exceptions are "too hard" to get right). Furthermore, the Chapel error handling design is significantly different and offers "strict mode" in which you have to clearly show the possible control flow from exceptions. Meaning that I'd expect the author of pop to think about this issue and handle it correctly. Or at least be able to understand and fix bugs in the area as they come up.

Summing up, I disagree that the C++ story is a compelling reason that pop_back in Chapel should not return a value. (Besides which these C++ inspired methods have the wrong naming convention - see #6698).

[bradcray]

I'm encouraged by Michael's comments above in that it certainly seems more intuitive / convenient to have the pop routines return values...

I'm also wondering whether, if there were some case Michael didn't anticipate, we could use reflection to switch between returning and non-returning versions of pop based on the type stored within the vector. (I'm not suggesting that we pursue this or worry about it in the short-term, but that if something goes wrong down the line, we have a fallback other than "arrays of ints can't pop ints back to the user").

[psahabu]

The current design for throwing initializers is now in #8692.

[daviditen]

Michael's argument sounds convincing to me. I think the pop routines can return the removed element as long as we pay careful attention to the rules in CHIP 13.

[BryantLam]

While I'm not an expert on exception safety, @mppf's rationale makes sense to me.