Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: extend the "append" built-in to work with maps #17350

Closed
bcmills opened this issue Oct 5, 2016 · 27 comments
Closed

proposal: extend the "append" built-in to work with maps #17350

bcmills opened this issue Oct 5, 2016 · 27 comments

Comments

@bcmills
Copy link
Contributor

bcmills commented Oct 5, 2016

There is currently an unpleasant asymmetry between nil maps and nil slices. It's very easy to safely append to a slice regardless of whether the source is nil:

s = append(s, e)

but tedious to safely extend a nil map in a similar way:

if m == nil {
    m = make(map[foo]bar)
}
m[k] = v

Map insertions are common in application code, and the amount of boilerplate involved makes multi-level maps in particular quite awkward to work with. A simple bit of syntactic sugar would make the code much more readable, and provide a pattern (along the lines of the append pattern for slices) that is much more robust to nils:

m = append(m, map[foo]bar{k: v}...)

The specific proposal involves two (backward-compatible) changes to the spec.

Passing arguments to ... parameters

If the final argument is assignable to a map type map[K]V and struct{K; V} is assignable to T, the map may be passed as the value for a ...T parameter if the argument is followed by .... The value passed is a new slice of type []T with a new underlying array whose successive elements are structs containing the keys and corresponding values of the map in unspecified order.

Appending to and copying slices and maps

The variadic function append appends zero or more values x to s of type S, which must be a slice or map type, and returns the resulting slice or map, also of type S. For slices, the values x are passed to a parameter of type ...T where T is the element type of S and the respective parameter passing rules apply. For maps, the values x are passed to a parameter of type ...struct{K; V} where K is the key type of S and V is the element type. As a special case, append also accepts a first argument assignable to type []byte with a second argument of string type followed by .... This form appends the bytes of the string.

append(s S, x ...T) S  // T is the element type of S
append(s S, x ...struct{K; V}) S // K and V are the key and element types of S

If s is a slice and the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large underlying array that fits both the existing elements and the additional values. Otherwise, append re-uses the underlying array.

If s is a map and the value of the map is nil, append allocates a new map value containing the argument keys and element values. Otherwise, append inserts the keys and values into the existing map in order, replacing any existing element value for the key.


The proposed syntax would go nicely with proposal #12854:

m = append(m, {k1, v1}, {k2, v2})

or

m = append(m, {k1: v1, k2: v2, k3: v3}...)
@neild
Copy link
Contributor

neild commented Oct 5, 2016

I think that last example wants to be:

m = append(m, {k1: v1}, {k2: v2}, {k3: v3}, ...)

@cespare
Copy link
Contributor

cespare commented Oct 5, 2016

@neild I don't think so; it's demonstrating the ...-expansion of the first proposed spec change.

@bcmills
Copy link
Contributor Author

bcmills commented Oct 5, 2016

@neild I chose the examples in part based on the ease of extending the spec to describe them. I'd be happy to consider alternatives if they're not much more difficult to specify.

@neild
Copy link
Contributor

neild commented Oct 5, 2016

Ah, never mind; I had the proposed spec change backward.

@dsnet
Copy link
Member

dsnet commented Oct 5, 2016

I'm in favor of something that simplifies inserting into a map, but it does seem odd to me that append is really acting more like a 'merge' in the case of maps.

@jimmyfrasche
Copy link
Member

What value would this have outside of using append on maps?

The only things I can think of looking at the proposed semantics would be:

Rewriting a map[K]V to a []struct{K; V}, or vice versa, as an append one-liner.

Making it easier to use a function that takes a ...struct{K; V} with K hashable.

It can kind of be annoying to update a map that may be nil, but I don't find any of these cases particularly compelling.

I'm willing to accept that I'm missing something.

Otherwise, a merge built in would seem more sensible, but, unlike append, it's easy to write for a fixed pair of key, value types: https://play.golang.org/p/t3HotPePo9

@bcmills
Copy link
Contributor Author

bcmills commented Oct 5, 2016

@jimmyfrasche

What value would this have outside of using append on maps?

Very little. Making append work with maps is pretty much the point.

Making it easier to use a function that takes a ...struct{K; V} with K hashable.

Technically yes, but I would hope not to see much (if any) code of that form. (Most structs should have named fields rather than anonymous ones.)

Otherwise, a merge built in would seem more sensible, but, unlike append, it's easy to write for a fixed pair of key, value types: https://play.golang.org/p/t3HotPePo9

That's much less efficient than the proposed semantics, especially given that the compiler could optimize literals with "append" to avoid intermediate allocations.

A hand-rolled equivalent would be closer to: https://play.golang.org/p/PAkqDYq7V5


The "easy to write" helper-function you propose is not much more difficult for the existing append for slices, modulo reallocating slices being a bit clunkier than reallocating maps: https://play.golang.org/p/ca5oQ2xMVs

And yet, we have append for slices: it makes the code simpler, less error-prone, and more efficient.

@griesemer
Copy link
Contributor

I'm sympathetic to the problem (there's many lazily initialized maps in go/types for instance, and it would be nice to not have to check first, before setting a value).

That said, I don't like to combine this with append. For one, it's not an "append", it's an "insert". Secondly, I'm not convinced it's just a bit of syntactic sugar:

m = append(m, map[foo]bar{k: v}...)

requires a bit more work than just syntax tree rewriting (which would be needed if it were just syntactic sugar). The 2nd argument to append is a map value that needs to be evaluated - I doubt we want to recognize that entire pattern. What if we used a map name? Do the maps have to be identical in type? (doesn't make sense, it's only about keys and values). I think there's more happening here than meets the eye, certainly more than what one would expect from syntactic sugar.

Furthermore, there's quite a bit of extra spec language needed to make this happen, it seems. I don't think that extra complexity carries its weight.

As is stands, I am not in favor of this proposal.

@ianlancetaylor
Copy link
Member

func Insert(m interface{}, args ...interface{}) interface{} {
    if len(args) % 2 != 0 {
        panic("must have pairs of keys and values")
    }
    mv := reflect.ValueOf(m)
    if mv.IsNil() {
        mv = reflect.MakeMap(mv.Type())
    }
    for i := 0; i < len(args); i += 2 {
        mv.SetMapIndex(reflect.ValueOf(args[i]), reflect.ValueOf(args[i+1]))
    }
    return mv.Interface()
}

@bradfitz
Copy link
Contributor

bradfitz commented Oct 6, 2016

@ianlancetaylor, when I saw args ... I assumed you were going to let me auto-vivify a map of map of maps and let me pass in Insert(topMap, key, key, key, value). :-)

@dsnet dsnet added this to the Proposal milestone Oct 6, 2016
@dsnet dsnet added the Proposal label Oct 6, 2016
@bcmills
Copy link
Contributor Author

bcmills commented Oct 6, 2016

@ianlancetaylor I had thought about something like that. It's better than nothing, but still makes maps second-class compared to slices and append: the reflective version of Insert that you wrote is much less type-safe than append (and requires a type-assertion), and an equivalent type-safe builtin would have an effective "type" that can't be described using the Go type system (alternating varargs).

I suppose the compiler could optimize calls to it, but to do that in the near future with a fairly simple compiler like gc it seems like we would need a well-known Insert implementation that it could special-case.

Perhaps a builtin merge function along the lines of the function @jimmyfrasche provided would provide a better balance of spec complexity, efficiency, and type-safety.

The change to the spec would be smaller than my initial proposal; something along the lines of:


Merging maps

The built-in variadic function merge combines the keys and elements of zero or more maps x to m of type M, which must be a map type, and returns the resulting map, also of type M. The values x are passed to a parameter of type ...M and the respective parameter passing rules apply.

merge(m M, x ...M) M

If m is nil, merge allocates a new map to merge into. Otherwise, merge re-uses the passed-in map m. For each x in order, merge append inserts the keys and values of x into m, replacing any existing element value for the key.

m0 := map[int]int{0: 0}
m1 := merge(m0, map[int]int{1: 2})                // add new elements     m1 == map[int]int{0: 0, 1: 2}
m2 := merge(m1, map[int]int{0: 3, 4: 5})          // add and replace multiple elements    m2 == []int{0: 3, 1: 2, 4: 5}
m3 := merge(nil, m2)                              // make a copy of m2 as a new map value

@ianlancetaylor
Copy link
Member

I guess I don't understand why you are pushing for merge rather than insert. I would expect that insert would be more commonly used. Are there many cases where people want to merge maps?

Either way, this is another example of a function that could be written easily if we had generics.

@dsnet
Copy link
Member

dsnet commented Oct 6, 2016

@ianlancetaylor, what's your definition of merge and insert?

EDIT: Did you mean something like?

func insert(m map[K]V, k K, v V) map[K]V

@ianlancetaylor
Copy link
Member

merge takes map arguments, insert takes key/value pairs, as in my example above using reflection. So, yes, like your function, but with varargs.

@bcmills
Copy link
Contributor Author

bcmills commented Oct 6, 2016

@ianlancetaylor, I'm pushing for merge because I can define its type similarly to the way append is defined, as a pseudo-generic function that otherwise has an ordinary Go type. (That is, I can write it as merge(m M, x ...M) M.

I agree that insert better matches common usage, but it's further away from ordinary Go types. It requires either matched pairs of alternating keys and values as varargs, or structs to pair them up.

As far as I am aware, not even any of the proposals for #15292 would be able to express the former type.

My initial proposal was an attempt at the latter, but without either #12854 or some extension of ... for map arguments the syntax is pretty heinous.

@bradfitz
Copy link
Contributor

bradfitz commented Oct 6, 2016

If the language is changed to make auto-vivifying maps easier, be sure to handle multiple level maps too. That's where this is most painful for me in practice.

As a bad example because this is gross, but this syntax is currently not possible (type *map[K]V does not support indexing), so it's free to give it new behavior:

     var m map[int][bool]string
     (&m)[1][true] = "foo"

Maybe there's something similar that's less gross.

@bcmills
Copy link
Contributor Author

bcmills commented Oct 6, 2016

@bradfitz Under some variant of this proposal, you could maybe write that as:

var m map[int][bool]string
m = insert(m, {1, insert(m[1], {true, "foo"})})

Is that unreadable, or just readable enough? (I'm not sure myself.)

@bcmills
Copy link
Contributor Author

bcmills commented Oct 6, 2016

Or, we could generalize the "N-element struct" version in fun and interesting ways for multi-level maps:

m = insert(m, {1, true, "foo"})

@bradfitz
Copy link
Contributor

bradfitz commented Oct 6, 2016

At that point I'd write if statements. :-)

@cznic
Copy link
Contributor

cznic commented Oct 6, 2016

type m map[foo]bar

func (p *m) set(k foo, v bar) {
        if *p == nil {
                *p = m{k: v}
                return
        }

        (*p)[k] = v
}

@extemporalgenome
Copy link
Contributor

@bcmills I'm not convinced that struct { K; V } is a meaningful idiom in Go -- for example, I've only seen it used in intermediate processing. For that to be truly powerful in Go, the language would have needed to incorporate it into many aspects of the language design, such as treating maps as a semantically-equivalent optimization of []struct{ K; V }.

As they stand currently, maps are more expensive than other builtin data-structures in Go, and arguably people are using maps-of-maps-of-maps (k^3 maps, where k is the depth) when they should be using k maps. For example, instead of:

m := make(map[A]map[B]map[C]D)
// do initialization checking at each level -- lots of if's.

You can use:

var (
   mA   = make(map[A][]B)
   mAB  = make(map[struct{A; B}][]C)
   mABC = make(map[struct{ A; B; C }]D)
)
// initialization is done (no if's), potentially 100k's fewer maps for the GC to scan

If you don't need to iterate or find values based on "partial keys", the second solution would only require a single mABC map. The patterns people tend to use with maps are often very suboptimal already: my stance on this proposal is that it would aid the abuse of a technique that should be avoided in most cases.

Additionally, an unstated implication of this proposal is that it would prevent type inference in more cases with append. For example, the language team may decide to explore relaxing explicit typing of appends-to-nil, such as:

x := append(nil, struct { K; V }{"a", 5})

Given the current Go language, with such a relaxation, x's type would be unambiguously inferable as []struct{ K; V }. With this proposal, it would be unclear as to whether the nil refers to a nil map[K]V or a nil slice. Making nil appends more convenient is not entirely compelling, but given the comparative centrality of slices in Go, I've seen many more "append chains" involving a []string(nil) as the first append argument than I have seen deeply nested maps.

@neild
Copy link
Contributor

neild commented Oct 6, 2016

As a not-very-serious idea, how about an autovivification operator?

x# evaluates to x, creating x if it is nil.

var m map[int]int
x := m# // m = make(map[int]int); x := m

var m map[int]int
m#[0] = 1 // m = make(map[int]int); m[0] = 1

m := make(map[int]int)
m#[0] = 1 // m is non-nil, so just m[0] = 1

var p *int
*p# = 42 // p = new(int); *p = 42

var m map[int]*struct{F int}
m#[0]#.F = 1

var x interface{}
x.(map[int]int)#[0] = 1 // compile error: "cannot assign to x.(map[int]int)"

@bcmills
Copy link
Contributor Author

bcmills commented Oct 6, 2016

@cznic Yes, that's the same kind of boilerplate that was addressed in proposal #16721 (which was accepted).

@bcmills
Copy link
Contributor Author

bcmills commented Oct 6, 2016

@extemporalgenome

For that to be truly powerful in Go, the language would have needed to incorporate it into many aspects of the language design […]

I'm not proposing for it to be "truly powerful". I'm merely proposing for it to reduce the boilerplate required when using nil maps.

arguably people are using maps-of-maps-of-maps (k^3 maps, where k is the depth) when they should be using k maps

Agreed. A more realistic version of @bradfitz's example using multi-level maps would probably involve one or more of:

  • an intermediate struct at each level, e.g.:
type County struct {
  SeatName string
  Cities map[string]*City
}
type Nation struct {
  Languages []string
  Counties map[string]*County
}
type Continent map[string]*Nation

(But in that case, the syntactic sugar for multi-level maps isn't helpful.)

  • or, using the sub-maps as individual values (for example, passing the elements of a map[foo]map[bar]baz to a func(map[bar]baz)). In that case the syntactic sugar is helpful, but only marginally. It's clear enough to write the levels separately:
m1 := insert(m[1], {true, "foo"})
m = insert(m, {1, m1})

Additionally, an unstated implication of this proposal is that it would prevent type inference in more cases with append.
[…]
Given the current Go language, with such a relaxation, x's type would be unambiguously inferable as []struct{ K; V }.

No. You already need the concrete type of the slice being appended to: the elements passed to append need only be assignable to the type of the slice elements, not the exact type. In the example you give, a declaration

type Foo struct { K; V }

would make it ambiguous whether the type of x should be []Foo or []struct{K; V}.

If you're appending individual elements to a nil slice you probably ought to be using a slice literal anyway. (The useful case for append(nil, …) is for copying an existing slice of unknown length.)

@cznic
Copy link
Contributor

cznic commented Oct 6, 2016

@bcmills

Yes, that's the same kind of boilerplate that was addressed in proposal #16721 (which was accepted).

#16721 is not a language change proposal.

@zigo101
Copy link

zigo101 commented Oct 6, 2016

I feel extending the "append" built-in to work with channel is more reasonable. ;D

@griesemer
Copy link
Contributor

I doesn't look like there is support for this. Closing.

@griesemer griesemer reopened this Oct 31, 2016
@golang golang locked and limited conversation to collaborators Oct 31, 2017
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests