RFC: Split delete!(h::Dict,key) into pop!(), delete!() (#3405)

[kmsquire]

As discussed in #3405, here are some exploratory changes to split delete!(h::Dict, key) into two functions.

• pop!(h::Dict, key) returns the value removed from h, or throws an error if the key missing
• pop!(h::Dict, key, default) returns the value removed from h, or default if the key is missing
• delete!(h::Dict, key) discards the value and returns the modified dictionary; no error thrown on missing value.

Also implemented for Set(), IntSet(). Haven't touched ObjectIdDict or WeakKeyDict.

Edit: Added info about errors, default value on pop!()
Edit: Also updated ObjectIdDict, WeakKeyDict

[StefanKarpinski]

Nice, it seems like a good change and definitely pushes the conversation forward. Now it feels a little like push! should take an optional key, but that doesn't actually make sense for half of the collections. Perhaps we should break the general relationship between push! and pop! except for actual stacks. For example, for sets, push! could replace add! as a function to add an arbitrary item to the set, while pop! could be used to remove an arbitrary item from the set.

[kmsquire]

I think I've finished all of the needed pop! updates. I'd like to say all tests pass, but they're failing for other reasons (going to submit issues tonight or tomorrow).

At this point, I have some thoughts, and could use some feedback.

1. Even though I proposed pop! (based on Python's usage), I'm not sold on push! as the opposite here.
2. With this change, delete! returns the collection. While I like the change, it's pretty disruptive if someone is depending on the previous behavior. I added a deprecation for the three-argument version of delete!, and warnings for the 2-argument version. The warnings are quite annoying, so I think they should be removed in favor of loud warnings on the mailing list if/when this is merged
3. Right now, delete! does not throw an error if the key is not in the collection--it just returns the unchanged collection. This might cause issues with previous code using the two-argument version of delete! and depending on an error being thrown if the key is not in the collection. I made one in-tree change from delete!(a,b) to pop!(a,b) because it was unclear whether or not that behavior was needed. It may be better to throw an error (though I prefer the current behavior--if someone needs an error thrown, they can use pop!).

Other ideas:

1. rename delete! to remove!, to ease the transition
2. use getrm! or getdel! instead of pop! (or some other name that does not imply the requirement of a push!--this is about splitting up delete! into two semantically different concepts, not implementing push! and pop! for all collections.)
3. Or, just deal with pop! without push!. (Or implement push! separately!) FWIW, python has pop() but uses add() to add elements; there's no push() function.

Edit: push() was added (see below)

[JeffBezanson]

Shall we try to get this merged for 0.2?

[StefanKarpinski]

I feel that this generalizes the meaning of pop! in a way that leaves things in an inconsistent state. Should we just say that push! adds an element while pop! removes an element, and in the case of stack-like collections, there is a guarantee that x == pop!(push!(c,x)) and that c is left in the same state before and after? In that case Set add! can become a method of push! and pop! can just give you an arbitrary set element, removing it from the set. I personally think that's a pretty reasonable API but you seemed to have stronger feelings about pushing and popping satisfying specific invariants.

[kmsquire]

@StefanKarpinski, that sounds fine. I'll add the corresponding push! methods.

[kmsquire]

After staring at this a little, I'm wondering if there is need for a method to return both the modified collection and the removed element... For immutable collections, I think this would be required. Thoughts?

[StefanKarpinski]

Those versions wouldn't have the ! so are out of the scope of these particular functions.

[kmsquire]

True, that!

One more thought:

• pop!(), as implemented here, returns the element, and modifies the collection
• delete!() as implemented here, returns the modified collection
• push!() currently returns the modified collection

This generally seems like reasonable behavior for push!(), but is the asymmetry with pop!() reasonable?

[StefanKarpinski]

I think the asymmetry of pop! and push! is traditional and sensible. This is the same sort of "balanced asymmetry" that read and write have.

[kmsquire]

Okay, makes sense.

In that case Set add! can become a method of push!

Can you clarify this statement? Is it that you want add! defined in terms of push!? push! to replace add!? Something else?

At this point, the decision is somewhat arbitrary, just wondering if you had something specific in mind.

[kmsquire]

Reading your earlier suggestion again, I'll deprecate add!.

[kmsquire]

Okay, I added push! for Sets and Dicts, deprecated add!, and removed jl_eqtable_del in response to @JeffBezanson's comment.

Tests pass (on my machine, at least).

The warnings are a bit annoying. The problem is that delete! didn't go away here, but its semantics changed, and the warnings highlight this. For Julia code, that shouldn't be an issue, but for user code, the warnings would be useful. It would be nice would be to turn on deprecations for user code only, but I'm not sure how feasible that is.

I can squash and/or turn off the warnings, although I think the change of meaning of delete! should be announced on the mailing list before this is merged. It would also be worthwhile to grep packages for potential conflicts.

[kmsquire]

This is also one of those changes where it would be nice if a package could depend on a particular non-release version of julia (cf #3465).

[toivoh]

Current add! semantics allow to add an already existing element to a set. Are we comfortable with letting push! do that, especially when it will always add a new element to a vector? I'm not sure what we are gaining by bringing add! and push! together.

[ViralBShah]

Worth keeping in mind that @lindahua is currently using add! on vectors for vector addition in NumericExtensions and we may bring that into Base.

[kmsquire]

Bump.

Given @JeffBezanson's recent comments, it seems like some version of this pull request will likely go into 0.2. Rebasing is slightly painful, so I'd rather not go through it too many more times. If someone can give a heads up when they want to review/try this more, I'll rebase again.

[JeffBezanson]

Let's merge this. @StefanKarpinski ?

[kmsquire]

In the morning, I'll

• fix the deprecation issue Jeff pointed out
• remove the delete warning (its really annoying)
• rebase

One other question: should delete!() throw an error if the key is not present? It currently just returns the unmodified dictionary.

[JeffBezanson]

I thought part of the purpose of delete! was to be silent if the key is not present.

[kmsquire]

@JeffBezanson, you're absolutely right. I had somehow forgotten that that was one of the main points of this change.

[StefanKarpinski]

Give me a bit to look over this.

[kmsquire]

I just rebased to the latest julia, and made a few minor changes. I didn't squash the last commit yet so you can see what these are. Tests pass for me (we'll see what Travis says).

As I pointed out before, because this changes the behavior of delete!, it would be good to announce it on the mailing list when it goes in. In the mean time, I'm installing all available packages and looking for uses of delete!.

[kmsquire]

Re:Travis, clang passed, gcc failed. Passed with gcc on my machine.

cc: @staticfloat

[StefanKarpinski]

These deprecations are not quite right: the rhs needs to be push!(s,x).

[kmsquire]

Whoops, right, thanks.

[staticfloat]

Behold; the Travis gods have deemed a re-run of the gcc job to be acceptable. If you have permissions to JuliaLang/julia.git, you can click on the little gear in the top right of a Travis job and click "re-run job" to do what I just did.

[kmsquire]

@staticfloat, I saw the gear, but "re-run job" was grayed out.

[staticfloat]

You must not have permissions then. :/ I'm not sure how github permissions
map to Travis permissions even. Oh well. Hopefully we'll eventually track
down these bugs and won't need to do this anymore!
-E

On Thu, Aug 8, 2013 at 12:54 PM, Kevin Squire [email protected]:

@staticfloat https://github.com/staticfloat, I saw the gear, but
"re-run job" was grayed out.

—
Reply to this email directly or view it on GitHubhttps://github.com//pull/3439#issuecomment-22350691
.

[JeffBezanson]

bump

[kmsquire]

I'm not quite finished installing all packages (Pkg2 is still slow, and until a moment ago, I wasn't smart enough to catch errors for uninstallable package, so I kept on restarting it).

A quick grep shows that the number of packages using delete! in a way that will break is small, but one of them is BinDeps (cc: @loladiro). I'll post a complete list in a little while.

[kmsquire]

The packages below all use delete!. The maintainers of these packages should read through this pull request and be aware of the changes they may need to make.

Packages using the return value of delete!
BinDeps (cc: @loladiro)
HDFS (cc: @tanmaykm)
HTTP (cc: @dirk)

Packages which may want to make the same change:
Images (cc: @timholy)
DataFrames (cc: @johnmyleswhite, @HarlanH)
JudyDicts (cc: @tanmaykm)
PyCall (cc: @stevengj)
SimJulia (cc: @BenLauwens)

All packages using delete! (most uses okay)
BinDeps (@loladiro)
Blocks (@tanmaykm)
ChainedVectors (@tanmaykm)
DataFrames (@JuliaStats)
Debug (@toivoh)
DictUtils (@slycoder)
FunctionalCollections (@zachallaun)
GLPK (@carlobaldassi)
Gtk (@JuliaLang)
HDFS (@tanmaykm)
HTTP (@dirk)
HttpServer (@HackerSchool)
IJulia (@JuliaLang)
Images (@timholy)
JudyDicts (@tanmaykm)
Mustache (@jverzani)
NetCDF (@meggart)
PyCall (@stevengj)
PySide (@jverzani)
RandomMatrices (@jiahao)
SimJulia (@BenLauwens)
TextAnalysis (@johnmyleswhite)
YAML (@dcjones)

---

Uses of delete! which

1. ignore the return value and
2. do not care if an error is not thrown
   do not need to change anything

Before this patch (#3439) is applied, uses of delete! which use the return value, such as

x = delete!(dict, value[, default])

or want a KeyError() thrown may want to change these uses to something like the following so that their code does not break when this patch is applied:

x = get(dict, value, default)
if x == default
   throw KeyError("$value not found in dictionary")
end
delete!(dict, value)

After this patch is applied, this can simply be changed to

x = pop!(dict, value[, default])

[kmsquire]

These should have been copied in the last note...

CC: @toivoh!, @slycoder!, @zachallaun!, @carlobaldassi!, @HackerSchool!, @jverzani!, @meggart!, @jiahao!, @dcjones

[stevengj]

Should that be get and not get! in your suggested workaround?

[kmsquire]

It should, thanks. Fixed in the issue.

[stevengj]

Wouldn't it be cleaner to do:

if method_exists(pop!, (Dict, Any, Any)) # from Julia #3439
    mypop!(d::Dict, x, y) = pop!(d, x, y)
    mypop!(d::Dict, x) = pop!(d, x)
else
    mypop!(d::Dict, x, y) = delete!(d, x, y)
    mypop!(d::Dict, x) = delete!(d, x)
end

and then just use mypop! until it is safe to just change to pop!?

For my part, I'm happy just waiting for this patch to land and then updating PyCall within the next day or so. Until Julia 0.2 is released, backwards compatibility is not worth messy code for me.

[kmsquire]

That would also be fine. And since you're in charge of your package, doing nothing and letting things break for a little while is fine as well.

I tend to want to coddleaccommodate users who are using a julia 0.2 pre-release for real work, without updating the main code base, but who occasionally update modules, and find that they break for reasons like this. I don't think it puts julia in a good light.

But I keep getting pushback on this, and I admit that 1) it's rather annoying and 2) is mostly just creating extra work for maintainers at this early stage of julia's evolution. So now that most relevant parties have been notified, I guess we should just merge this and pick up the pieces and be done with it. (After @StefanKarpinski gives his blessing.)

(There also aren't as many uses as I first feared.)

[kmsquire]

@StefanKarpinski, do you plan to review this any more? I'd like to make a general announcement on the mailing list, and pull the trigger a day or two later.

[StefanKarpinski]

Yes, sorry for the slowness.

[kmsquire]

No worries, I'll wait.

[StefanKarpinski]

Ok, just went over this with @JeffBezanson and I think we should follow through on this. It leads, however, to further logical changes, such as replacing shift!(c) with pop!(c,1) and unshift!(c,x) with push!(c,1), but those can be made after this is merged. This is a bit of a complex merge, @kmsquire, so go ahead whenever you want.

[StefanKarpinski]

Ah, hell. I'm just merging.

[kmsquire]

@StefanKarpinski, thanks for merging. I was hoping to submit a pull request for at least BinDeps, which will break because of this change, but I guess that can happen now. (cc: @loladiro)

[stevengj]

PS. Why is it pop!(d, k) to remove d[k], but splice!(a, i) to remove a[i]?

[JeffBezanson]

I think pop!(a, i) on arrays could also be defined; its functionality is a subset of splice!. The possible objection is that on arrays popping a non-final element shifts other values, while in sets and dicts only the removed value is affected.