Reference types

[Martin Geisler]

Hi everybody,

I've recently started looking at Go. I have a Python/Java/C background
and I really like how the language feels very lightweight, while also
being statically typed.

When I read the documentation I was confused by the talk about slices,
maps, and channels being "reference types":

http://golang.org/doc/go_spec.html#Making_slices_maps_and_channels

It sounds like there are three kinds of types:

* Values: ints, structs, ...

* Pointers: pointer to a value

* References: slices, maps, and channels

I would have expected a slice to be a small struct with a pointer to the
underlying array, the length, and the capacity. That's a "value" and if
I pass it to a function, I would expect that the three words of memory
are copied onto the stack -- I would not expect to see a "reference"
(what is a reference anyway, if not a pointer?) on the stack.

So I was happy to see that this is also how it works:

http://research.swtch.com/godata

My question is why the language spec talks about reference types then?
Is it because the struct happens to be immutable, so that all the copies
that are made when functions are called all look identical and so one
can *think* of them as being references to the same struct?

--
Martin Geisler

aragost Trifork
Professional Mercurial support
http://www.aragost.com/mercurial/

[Martin Geisler]

[chris dollin]

On 8 March 2012 12:21, Martin Geisler <m...@lazybytes.net> wrote:

> It sounds like there are three kinds of types:
>
> * Values: ints, structs, ...
>
> * Pointers: pointer to a value
>
> * References: slices, maps, and channels

Reference types have implicit pointers and aliasing.

A slice is a reference type because two different slice values
may refer to the same underlying array elements, so assigning
to an element of one can update an element of another. This
doesn't happen with structs (it can of course happen with
/pointers/ to structs, that being one of the points of pointer types
in the first place.)

Chris

--
Chris "allusive" Dollin

[Jan Mercl]

On Thursday, March 8, 2012 1:21:02 PM UTC+1, Martin Geisler wrote:

When I read the documentation I was confused by the talk about slices,
maps, and channels being "reference types":

  http://golang.org/doc/go_spec.html#Making_slices_maps_and_channels

It sounds like there are three kinds of types:

* Values: ints, structs, ...

* Pointers: pointer to a value

* References: slices, maps, and channels

Roughly correct, see bellow.

 

I would have expected a slice to be a small struct with a pointer to the
underlying array, the length, and the capacity.

Exactly that's the current implementation (an implementation detail, though).

 

That's a "value" and if
I pass it to a function, I would expect that the three words of memory
are copied onto the stack

Correct.

 

-- I would not expect to see a "reference"
(what is a reference anyway, if not a pointer?) on the stack.

So I was happy to see that this is also how it works:

  http://research.swtch.com/godata

My question is why the language spec talks about reference types then?

Probably because of the reference semantics of the slice's backing array. I prefer to not confuse myself  so I never call slice a reference type. All I need to remember is that slice is a struct (value type) with a reference to that array - the reference semantics are wrt the array, *not* the slice start and len, that can be changed if every copy of the slice's *value*. Note that the pointer to the backing array is also part of the value, so after:

sliceA := someSliceFunc()

sliceB := sliceB

// do something with sliceA, like append(), ...

Everything works fine, but sliceA and sliceB now may or may not share the same backing array.

 

Is it because the struct happens to be immutable, so that all the copies
that are made when functions are called all look identical and so one
can *think* of them as being references to the same struct?

No.

[Martin Geisler]

chris dollin <ehog....@googlemail.com> writes:

> On 8 March 2012 12:21, Martin Geisler <m...@lazybytes.net> wrote:
>
>> It sounds like there are three kinds of types:
>>
>> * Values: ints, structs, ...
>>
>> * Pointers: pointer to a value
>>
>> * References: slices, maps, and channels
>
> Reference types have implicit pointers and aliasing.

Right -- it's clear that the underlying array 'a' is updated if I do:

var a [10]int
s := a[:]
s[0] = 100

But for me that's just "magic" associated with the slice type. It
doesn't make the slice any more of a reference type than a normal
pointer is a reference type.

> A slice is a reference type because two different slice values may
> refer to the same underlying array elements, so assigning to an
> element of one can update an element of another. This doesn't happen
> with structs (it can of course happen with /pointers/ to structs, that
> being one of the points of pointer types in the first place.)

I think that means that my Slice struct below is also a "reference
type". I guess one could call it that, but from the language spec I got
the impression that a reference type was something special. Since it's
just a value that points to another value, it felt unnecessary to me to
introduce a new concept.

type Slice struct {
array *[10]int
offset int
length int
}

func (s *Slice) Index(i int) int {
return s.array[s.offset + i]
}

func (s *Slice) Assign(i, value int) {
s.array[s.offset + i] = value

[Martin Geisler]

On Thursday, 8 March 2012 17:12:53 UTC+1, Jan Mercl wrote:

On Thursday, March 8, 2012 1:21:02 PM UTC+1, Martin Geisler wrote:

So I was happy to see that this is also how it works:

  http://research.swtch.com/godata

My question is why the language spec talks about reference types then?

Probably because of the reference semantics of the slice's backing array. I prefer to not confuse myself  so I never call slice a reference type. All I need to remember is that slice is a struct (value type) with a reference to that array - the reference semantics are wrt the array, *not* the slice start and len, that can be changed if every copy of the slice's *value*.

That makes a lot of sense. I'm glad to hear that I'm not the only one who think of slices as values that contain references to arrays.

Now that I think about it, I guess the description "reference type" makes more sense for a map. Here, the underlying storage isn't exposed to the user at all — but you still see the updated values after passing the map by value to a function that updates the map. 

That could be achieved by passing the map by reference, but it could also be achieved if a map was just a small struct pointing to some external storage. I guess that is how a map is implemented internally?

All in all I guess I feel that one could have conveyed the same semantics in the spec by saying that slices, maps, and channels are light-weight values — values so small that one doesn't have to pass around pointers to them.

Thanks for the inputs.

[chris dollin]

On 8 March 2012 17:19, Martin Geisler <m...@lazybytes.net> wrote:

> All in all I guess I feel that one could have conveyed the same semantics in
> the spec by saying that slices, maps, and channels are light-weight values —
> values so small that one doesn't have to pass around pointers to them.

Like integers and (some) structs?

The point of calling slices and maps and channels "reference types" is
to say that there are pointers /inside/ them even though one doesn't
use extra syntax (like *) to get at the pointed-to things. You get aliasing
like you do with [the targets of] pointers and don't with structs.

[John Asmuth]

Are slices considered by most to be reference types? As far as I am aware, maps and chans are pointers to more complex structures. Slices, on the other hand, are the combination of a length, a capacity and a pointer.

When you copy a slice and update the length or capacity (by calling append, for instance), the original slice is unchanged.

With maps and chans, there is nothing you can do (besides using the = operator) that will have an effect on the copy but not have an effect on the original.

[Steven Blenkinsop]

On 2012-03-08, at 1:37 PM, John Asmuth <jas...@gmail.com> wrote:

Are slices considered by most to be reference types? As far as I am aware, maps and chans are pointers to more complex structures. Slices, on the other hand, are the combination of a length, a capacity and a pointer.

When you copy a slice and update the length or capacity (by calling append, for instance), the original slice is unchanged.

You can't actually update the length or capacity of a slice. You can only construct a new slice referring to the same underlying array, and then replace the old slice with the new slice.

With maps and chans, there is nothing you can do (besides using the = operator) that will have an effect on the copy but not have an effect on the original.

This statement is equally true of slices. Any statement that affects the actual slice involves reassigning it.

I think people over think the concept of a reference. It just means something that serves the purpose of referring you to something. It's not magical. A pointer is a simple reference that tells you where to look. A slice tells you where to start looking and how far. Maps and channels also just tell you where to look, but the data they reference and the operations they support on it are more complex. The point is that all the actually data is stored indirectly and all you're holding is information on how to access it. As a result, in many cases you don't need to add another layer of indirection, unless you want a double indirection for some reason.

[John Asmuth]

On Thu, Mar 8, 2012 at 2:15 PM, Steven Blenkinsop <stev...@gmail.com> wrote:

You can't actually update the length or capacity of a slice. You can only construct a new slice referring to the same underlying array, and then replace the old slice with the new slice.

via unsafe, which I admit is a bit of a nitpick.

 

I think people over think the concept of a reference. It just means something that serves the purpose of referring you to something. It's not magical.

Except it carries with it connotations from "pass-by-reference" (from CS in general) and "reference type" (from C++), which Go cannot do and does not have. I really wish we had another word for these things other than "reference type".

[Steven Blenkinsop]

On 2012-03-08, at 2:19 PM, John Asmuth <jas...@gmail.com> wrote:

On Thu, Mar 8, 2012 at 2:15 PM, Steven Blenkinsop <stev...@gmail.com> wrote:

I think people over think the concept of a reference. It just means something that serves the purpose of referring you to something. It's not magical.

Except it carries with it connotations from "pass-by-reference" (from CS in general)

I think this is a mistake. People confusing references with pass-by-reference is like people mistaking ships for shipping.

and "reference type" (from C++), which Go cannot do and does not have. I really wish we had another word for these things other than "reference type".

That's the problem with hijacking general terms for specific things: you run out of general words. It wouldn't be a problem if people were flexible enough to adapt their understanding of words for new contexts, but that is often, unfortunately, not the case.

However, I'd like to point out that a C++ reference type is a reference type where all operations (other than initialization) reach through, whereas Go reference types support specific operations with limited reach-through. I'd prefer the term "alias" for the C++ variety though, since it's of the more specific variety of references that can be used in place of what they reference. There might be an even more specific term that I'm not thinking of right now.

[minux]

I think it's because it references the underlying data.

Even if the slice itself is passed by value, you can still change its underlying array.

 

[Martin Geisler]

Steven Blenkinsop <stev...@gmail.com> writes:

> On 2012-03-08, at 1:37 PM, John Asmuth <jas...@gmail.com> wrote:
>
> I think people over think the concept of a reference.

That I'll be happy to admit :-) But I find it an interesting topic, I
would like to really understand the primitives since I'm learning the
language.

> It just means something that serves the purpose of referring you to
> something. It's not magical. A pointer is a simple reference that
> tells you where to look. A slice tells you where to start looking and
> how far. Maps and channels also just tell you where to look, but the
> data they reference and the operations they support on it are more
> complex. The point is that all the actually data is stored indirectly

> and all you're holding is information on how to access it. [...]

What about a string? If I do

s := "my little string"
t := s

have I then copied the string? Or is both s and t pointing to the same
piece of memory. I would hope so since strings are immutable. Does that
make a string a reference type too?

--
Martin Geisler

Mercurial links: http://mercurial.ch/

[roger peppe]

a string is implemented just like []byte except it doesn't include the capacity
value and you can't change what it points to.

it's a reference type but you can't observe that.

[Martin Geisler]

chris dollin <ehog....@googlemail.com> writes:

> On 8 March 2012 17:19, Martin Geisler <m...@lazybytes.net> wrote:
>
>> All in all I guess I feel that one could have conveyed the same
>> semantics in the spec by saying that slices, maps, and channels are
>> light-weight values ― values so small that one doesn't have to pass
>> around pointers to them.
>
> Like integers and (some) structs?

Yes, exactly.

> The point of calling slices and maps and channels "reference types" is
> to say that there are pointers /inside/ them even though one doesn't
> use extra syntax (like *) to get at the pointed-to things. You get
> aliasing like you do with [the targets of] pointers and don't with
> structs.

Right, got it. Another thing that made me pause when I read "reference
type" is that C++ has them too. So I wondered if they're the same as C++
references -- and it turns out they're not.

I now think of slices, maps, and channels as small structs with no
exported fields and special syntax associated with them ([] and <-).
That sound like an easy and correct way to think of them.

Thanks for the help.

[andrey mirtchovski]

"People confusing references with pass-by-reference is like people
mistaking ships for shipping."

we need a fortunes file for go.

[Martin Geisler]

roger peppe <rogp...@gmail.com> writes:

Right, not by poking at it from inside the language.

I've searched some more and I can see that I'm not the only one who
dislikes how maps and slices are called "reference types". An early blog
post has this critique:

So: you can't write parametric types - but they can. And that creates
a very weird asymmetry to the language. Everything in Go is passed by
value - except for the built-in slice and map types, which are passed
by reference. Everything is allocated by "new" - except for the
built-in slice and map types, which are allocated by "make". It's by
far the biggest blemish in Go, and it's absolutely infuriating.

http://scienceblogs.com/goodmath/2009/11/googles_new_language_go.php

This later corrected in a comment:

Mark, you misunderstand the reference type/make thing, as do most
people. It's the Go folks' fault for describing it so badly.

Think of a slice as

type Slice struct { ptr *T; begin, end int }

And think of "make([]int, 20)" as a call to a function
"slice.Make(20)" that returns a Slice. With regard to memory, the
so-called "reference types" can be described in the language, and
there is no call-by-reference, only call-by-value. What the designers
have given themselves with these types is genericity and some
syntactic sugar (and pointer arithmetic in the case of slices), but
nothing special from a memory or calling-convention viewpoint.

http://scienceblogs.com/goodmath/2009/11/googles_new_language_go.php#comment-2114341

I'm posting it here for future reference to people that find this thread
in the archive.

I think it would have made sense to have

s := NewSlice(int, 20, 30) // make([]int, 20, 30)
m := NewMap(int, bool, 20) // make(map[int] bool, 20)
c := NewChannel(int, 20) // make(chan int, 20)

Yes, those builtin functions would be "magic" since they take a type as
parameter. But that's not more magical than how make takes a type.

Such functions could also have been made more regular so that they
always take exactly two/three arguments. Being new to the language, I
find it strage that make can take a varying number of arguments (and
this number of arguments even depend on the type given as the first
argument!). But maybe I should think of make as being variadic?

[Guillaume Lescure]

I thought it was variatic too but apparently, it's not :  http://weekly.golang.org/pkg/builtin/#make 
Just some sugar :)

[Martin Geisler]

Guillaume Lescure <guil.l...@gmail.com> writes:

> Le vendredi 9 mars 2012 06:18:09 UTC-5, Martin Geisler a écrit :
>
>> Such functions could also have been made more regular so that they
>> always take exactly two/three arguments. Being new to the language, I
>> find it strage that make can take a varying number of arguments (and
>> this number of arguments even depend on the type given as the first
>> argument!). But maybe I should think of make as being variadic?
>

> I thought it was variatic too but apparently, it's not:
> http://weekly.golang.org/pkg/builtin/#make Just some sugar :)

Yeah, I know that make is not a variatic function -- I get

foo.go:10: too many arguments to make([]int)

from

make([]int, 1, 2, 3)

I'm just pointing out that this behavior is inconsistent with the rest
of Go -- since, as far I know, I cannot define a function where the
compiler will check that I call it with up to three arguments.

It's inconsistencies like that which makes it hard for me to reason
about what make really "is". In Python, even built-in functions act like
pretty much like user-defined functions and I find that very elegant.

As far as I can see from searching the archive nobody suggested the
functions NewSlice, NewMap, and NewChannel before. But has the concept
of specific initializer functions for these types been rejected before?

[John Fries]

Sorry to revive this old thread, but I wanted to ask if this same reasoning applies to maps.

func addtomap(m2 map[int]bool) {

for i := 0; i < 10000000; i++ {

m[i] = true

}

fmt.Println("len(m2)", len(m))

}

func main() {

m1 := make(map[int]bool)

addtomap(m1)

fmt.Println("len(m1):", len(m))

}

By analogy with the reasoning for sequences in this thread, I thought that at some point during the call to addtomap, the underlying capacity of m2 would have to be increased, at which point m2 would point somewhere different than where m1 points. However, this does not seem to be the case. len(m1) was always equal to len(m2). Is this something that can be relied on or should I be passing pointers when I want to insert records into the original map?

[Kyle Lemons]

slices are a view into an underlying array; maps are references to a data structure.  As it grows and changes, all references to the map continue to reference the entirety of the map.  Just don't try to access it concurrently.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[John Fries]

specifically, don't try to write to it concurrently, or read from it while writing to it. concurrent reads are fine, right?

[Kyle Lemons]

Ah, yes, sorry :).  Reads are fine if they are only concurrent with other reads.