Proposal: read-only slices

[Brad Fitzpatrick]

Design doc for adding read-only slices to Go:

https://docs.google.com/a/golang.org/document/d/1UKu_do3FRvfeN5Bb1RxLohV-zBOJWTzX0E8ZU1bkqX0/edit#heading=h.2wzvdd6vdi83

Comments welcome.

[Brad Fitzpatrick]

I knew the community would help me pick a color.

I picked the smallest (least offensive?) option: a period isn't too many pixels. 

I don't really care, though.

On Mon, May 13, 2013 at 5:16 PM, <voidl...@gmail.com> wrote:

At first read, I really like everything but the syntax's use of the period/dot and I am eager for something like this to exist in Go.

In my opinion the period is too inconspicuous-
Given: t := make([]T, 10)
Here are a few ideas:

var vt[]#T = t
var vt[]$T = t
var vt[]:T = t
var vt[]~T = t
 

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

[minux]

So this is the (part of?) revised contribution process that you mentioned in another post?

"The Go Language Change Proposal"

Will readonly slices support slicing? (i think it should, but it's not mentioned anywhere in

the docs)

i'm wondering if string could be treated as a [].byte?

that is, at universal block, we have a declaration:

type string [].byte

how does the readonly slices interact with the reflect system?

will it introduce a new Kind or just a readonly flag for the slice kind (so as to pave the way

for future extensions like readonly map)?

[Brad Fitzpatrick]

On Mon, May 13, 2013 at 5:36 PM, minux <minu...@gmail.com> wrote:

On Tue, May 14, 2013 at 8:01 AM, Brad Fitzpatrick <brad...@golang.org> wrote:

Design doc for adding read-only slices to Go:

https://docs.google.com/a/golang.org/document/d/1UKu_do3FRvfeN5Bb1RxLohV-zBOJWTzX0E8ZU1bkqX0/edit#heading=h.2wzvdd6vdi83

Comments welcome.

So this is the (part of?) revised contribution process that you mentioned in another post?

"The Go Language Change Proposal"

No, unrelated.

 

Will readonly slices support slicing? (i think it should, but it's not mentioned anywhere in

the docs)

Yes. Updated doc.

 

i'm wondering if string could be treated as a [].byte?

that is, at universal block, we have a declaration:

type string [].byte

No.

A string has an additional guarantee: that nobody, ever, will mutate those bytes.  The doc explicitly says that [].byte just means you can't.  But somebody else might right now, or some time later.

Nobody wants to get rid of "string".

 

how does the readonly slices interact with the reflect system?

will it introduce a new Kind or just a readonly flag for the slice kind (so as to pave the way

for future extensions like readonly map)?

I'm open to suggestions.  You can imagine reflect.Value.Cap panicing if it's a read-only slice, for instance.  I don't know whether keeping the same Kind would cause problems, if the representation changes.

Alternatively, we could say that the representation of a read-only slice is the same as a slice, and cap() still works, but the cap(v) == len(v) always.

[mortdeus]

I think `[[]]T` is best. Its easy to type in editors, especially with editors that auto close braces. Adding it to the language grammar will be trivial. It also works well with the variable length and multidimensional array syntax.

http://play.golang.org/p/ioYulis11h    

On Monday, May 13, 2013 7:01:57 PM UTC-5, Brad Fitzpatrick wrote:

[Ian Lance Taylor]

On Mon, May 13, 2013 at 5:42 PM, Brad Fitzpatrick <brad...@golang.org> wrote:
>>
>> how does the readonly slices interact with the reflect system?
>> will it introduce a new Kind or just a readonly flag for the slice kind
>> (so as to pave the way
>> for future extensions like readonly map)?
>
>
> I'm open to suggestions. You can imagine reflect.Value.Cap panicing if it's
> a read-only slice, for instance. I don't know whether keeping the same Kind
> would cause problems, if the representation changes.
>
> Alternatively, we could say that the representation of a read-only slice is
> the same as a slice, and cap() still works, but the cap(v) == len(v) always.

One way to view this question is: are we introducing a new type, or
are we introducing a special case of an interface type? In one sense
you are proposing a polymorphic interface type that supports the
operations
Len() int
At(int) T
Slice(int, int) [].T
If we view this as an interface type, then reflect should return the
original type. If not, then it could be a new Kind, or it could be
Slice with a new field.

Either way we need to think about converting a value out of the type
and back to []byte and/or string? Is that ever possible? Does it
always involve a copy? If we adopt the interface approach, should we
support x.([]byte) and x.(string)?

Ian

[mortdeus]

Also the syntax works if we wanted to create a read only slice from a r/w slice. ro := rw[[1:4]] 

[Brad Fitzpatrick]

On Mon, May 13, 2013 at 5:59 PM, Ian Lance Taylor <ia...@golang.org> wrote:

On Mon, May 13, 2013 at 5:42 PM, Brad Fitzpatrick <brad...@golang.org> wrote:
>>
>> how does the readonly slices interact with the reflect system?
>> will it introduce a new Kind or just a readonly flag for the slice kind
>> (so as to pave the way
>> for future extensions like readonly map)?
>
>
> I'm open to suggestions.  You can imagine reflect.Value.Cap panicing if it's
> a read-only slice, for instance.  I don't know whether keeping the same Kind
> would cause problems, if the representation changes.
>
> Alternatively, we could say that the representation of a read-only slice is
> the same as a slice, and cap() still works, but the cap(v) == len(v) always.

One way to view this question is: are we introducing a new type, or
are we introducing a special case of an interface type?

I wouldn't make it an interface.

a) that'd have a larger representation, right?

b) I don't want my callees to get access to the underlying []byte with a x.([]byte).

 

 In one sense
you are proposing a polymorphic interface type that supports the
operations
    Len() int
    At(int) T
    Slice(int, int) [].T
If we view this as an interface type, then reflect should return the
original type.  If not, then it could be a new Kind, or it could be
Slice with a new field.

In what sense do you view our current send-only channels?  Aside: I'd love a method operator world, but we're not there.

 

Either way we need to think about converting a value out of the type
and back to []byte and/or string?  Is that ever possible?  Does it
always involve a copy?  If we adopt the interface approach, should we
support x.([]byte) and x.(string)?

I would be fine with s, ok := view.(string), but that means we need to know it was originally a string, which suggests a more interface-y representation, or representation tricks.

I never want to see a cheap view.([]byte).

I'd be totally happy with string([].byte) always making a copy, just like string([]byte)

[Brad Fitzpatrick]

Let's please ignore syntax for now.

It's very subjective, and subjectively, I think [[]] is disgusting.

[Brad Fitzpatrick]

On Mon, May 13, 2013 at 5:59 PM, Ian Lance Taylor <ia...@golang.org> wrote:

Either way we need to think about converting a value out of the type
and back to []byte and/or string?  Is that ever possible?  Does it
always involve a copy? 

You could also imagine that it always makes a copy by default, just like today:

     b := []byte("stuff")

     var s string = string(b)   // calls runtime.slicebytetostring

But instead, slicebytetostring only conditionally makes a copy, depending on whether &b[0] is from a string (GC information or whether it's in a memory region dedicated to storing string contents)

[Brad Fitzpatrick]

On Mon, May 13, 2013 at 6:17 PM, <voidl...@gmail.com> wrote:

For what its worth, I think I like var vt[]:T = t best.
It is (subjectively) aesthetically clean and in Go has connotations related to slicing [x : y].

On Monday, May 13, 2013 7:16:33 PM UTC-5, voidl...@gmail.com wrote:

At first read, I really like everything but the syntax's use of the period/dot and I am eager for something like this to exist in Go.

In my opinion the period is too inconspicuous-
Given: t := make([]T, 10)
Here are a few ideas:

var vt[]#T = t
var vt[]$T = t
var vt[]:T = t
var vt[]~T = t
 

On Monday, May 13, 2013 7:01:57 PM UTC-5, Brad Fitzpatrick wrote:

[Brad Fitzpatrick]

Sorry, I know that's condescending, but I'd like to keep this focused for now.

Syntax is a huge distraction, and I'm sure it will be a big enough topic later.

Let's figure out how this would work first.

[mortdeus]

If we introduce Immutability for slices we might as well introduce a universal immutability mechanism for all types.     

On Monday, May 13, 2013 7:01:57 PM UTC-5, Brad Fitzpatrick wrote:

[Gustavo Niemeyer]

Thanks Brad, that looks interesting. A few comments:

- The comparison with channels seems distracting
- Behavior when mutating the slice? Undefined, or defined with memory barriers?
- Should the printf family of functions change their formatting argument?
- Does it support + in a similar way to string?
- append?
- ~[]byte seems more clear, and reads properly ("view of slice of T",
not "slice of view of T").

Will send further comments if I can think of other questions.


gustavo @ http://niemeyer.net

[Brad Fitzpatrick]

On Mon, May 13, 2013 at 6:38 PM, Gustavo Niemeyer <gus...@niemeyer.net> wrote:

On Mon, May 13, 2013 at 9:01 PM, Brad Fitzpatrick <brad...@golang.org> wrote:
> Design doc for adding read-only slices to Go:
>
> https://docs.google.com/a/golang.org/document/d/1UKu_do3FRvfeN5Bb1RxLohV-zBOJWTzX0E8ZU1bkqX0/edit#heading=h.2wzvdd6vdi83
>
> Comments welcome.

Thanks Brad, that looks interesting. A few comments:

- The comparison with channels seems distracting

It exists to say that there's precendent.  We already have restricted types.

 

- Behavior when mutating the slice? Undefined, or defined with memory barriers?

Undefined. Like I said in the doc, we already permit data races with []byte. This is no different.

 

- Should the printf family of functions change their formatting argument?

We're not changing the standard library in Go 1.x.

 

- Does it support + in a similar way to string?

No. Will clarify. It's more of a slice than a string.

 

- append?

It's not mutable, so no.

[Andrew Gerrand]

On 13 May 2013 18:36, mortdeus <mort...@gocos2d.org> wrote:

If we introduce Immutability for slices we might as well introduce a universal immutability mechanism for all types.     

It may be worth considering immutability for maps, although I haven't personally felt the need for them.

I don't like the idea of consty pointers, though.

[Andrew Gerrand]

On 13 May 2013 18:38, Gustavo Niemeyer <gus...@niemeyer.net> wrote:

- The comparison with channels seems distracting

I don't think it's a distraction. It provides an important comparison with regard to conversions (eg, you can assign a bidirectional chan to a unidirectional one).

[mortdeus]

Another thing to consider is if we have an immutable slice for types with methods. Whats the rules for methods for pointers? What if one of the slice elements modifies itself by referencing itself via a globally scoped pointer. Do we create a snapshot copies of the slice, and if so how can we update immutable slice to reflect changes made to the original mutable slice?

These are the kinds of things that need to be thought about.

[Andrew Gerrand]

On 13 May 2013 18:46, mortdeus <mort...@gocos2d.org> wrote:

Another thing to consider is if we have an immutable slice for types with methods. Whats the rules for methods for pointers? What if one of the slice elements modifies itself by referencing itself via a globally scoped pointer. Do we create a snapshot copies of the slice, and if so how can we update immutable slice to reflect changes made to the original mutable slice?

These are the kinds of things that need to be thought about.

It's not an issue because type T[] and T.[] are different types. They don't share any methods. All the usual conversion rules apply.

Andrew

[Brad Fitzpatrick]

On Mon, May 13, 2013 at 6:46 PM, mortdeus <mort...@gocos2d.org> wrote:

Another thing to consider is if we have an immutable slice for types with methods. Whats the rules for methods for pointers?

Then the receiver is a pointer to a read-only slice, and it's still not allowed to mutate its receiver.

 

What if one of the slice elements modifies itself by referencing itself via a globally scoped pointer.

We still let you have a data race, as described in the doc.

 

Do we create a snapshot copies of the slice,

 

No.

[Gustavo Niemeyer]

On Mon, May 13, 2013 at 10:41 PM, Brad Fitzpatrick <brad...@golang.org> wrote:
> On Mon, May 13, 2013 at 6:38 PM, Gustavo Niemeyer <gus...@niemeyer.net>

>> - Behavior when mutating the slice? Undefined, or defined with memory
>> barriers?
>
> Undefined. Like I said in the doc, we already permit data races with []byte.
> This is no different.

The behavior of []byte is defined with explicit synchronization. If
you say undefined, then this is different.

>> - append?
>
> It's not mutable, so no.

I suppose it should still be mentioned, at least to define the
cross-compatibility with []byte appending.


gustavo @ http://niemeyer.net

[Brad Fitzpatrick]

On Mon, May 13, 2013 at 6:55 PM, Gustavo Niemeyer <gus...@niemeyer.net> wrote:

On Mon, May 13, 2013 at 10:41 PM, Brad Fitzpatrick <brad...@golang.org> wrote:
> On Mon, May 13, 2013 at 6:38 PM, Gustavo Niemeyer <gus...@niemeyer.net>

>> - Behavior when mutating the slice? Undefined, or defined with memory
>> barriers?
>
> Undefined. Like I said in the doc, we already permit data races with []byte.
> This is no different.

The behavior of []byte is defined with explicit synchronization. If
you say undefined, then this is different.

It's no different than a []byte:

-- we're not inserting atomics for you when you set/get a slice

-- we let you have buggy code with data races

-- we let you use synchronization correctly if you do want concurrent read/write

 

>> - append?
>
> It's not mutable, so no.

I suppose it should still be mentioned, at least to define the
cross-compatibility with []byte appending.

Will do.

 

[David Symonds]

I think append should work. If a read-only slice is the first argument
it'll always reallocate, and it works as normal if it's the second
argument (expanded with ...).

[Ian Lance Taylor]

On Mon, May 13, 2013 at 6:04 PM, Brad Fitzpatrick <brad...@golang.org> wrote:
>>
>> One way to view this question is: are we introducing a new type, or
>> are we introducing a special case of an interface type?
>
>
> I wouldn't make it an interface.
>
> a) that'd have a larger representation, right?

Right, because they would also record the original type.

>> In one sense
>> you are proposing a polymorphic interface type that supports the
>> operations
>> Len() int
>> At(int) T
>> Slice(int, int) [].T
>> If we view this as an interface type, then reflect should return the
>> original type. If not, then it could be a new Kind, or it could be
>> Slice with a new field.
>
>
> In what sense do you view our current send-only channels?

Channels feel a bit different to me: they remain channels, but
converting to a send-only or receive-only channel eliminates certain
operations. Converting []byte to [].byte changes the nature of the
value, since it no longer has a capacity. Converting string to
[].byte changes the meaning of the string significantly--e.g., range
and slice operations act differently.

As far as reflection goes, a chanType has a channel direction field
that indicates the directions that the channel supports (SendDir,
RecvDir, BothDir). We could add a field to sliceType.

Ian

[Dan Kortschak]

On Mon, 2013-05-13 at 20:27 -0700, Ian Lance Taylor wrote:
> Converting []byte to [].byte changes the nature of the
> value, since it no longer has a capacity.

Why in principle should a [].byte not have a capacity? The elements of
the view are not writable, but why should a holder of the [].byte not be
able to expand the length to the capacity? They can make no change to
the underlying data, all they can do is see it. The capacity means
something slightly different here, but it still seems to have a meaning.

Dan

[mortdeus]

cap([].byte) == len([].byte)

[Gustavo Niemeyer]

Pretty consistently, in the vast majority of cases where a slice is
extended one mutates its content. While someone can break that rule,
it sounds like a view not being extensible is a sane and practical
promise.


gustavo @ http://niemeyer.net

[Ian Lance Taylor]

On Mon, May 13, 2013 at 6:46 PM, mortdeus <mort...@gocos2d.org> wrote:

> Another thing to consider is if we have an immutable slice for types with
> methods. Whats the rules for methods for pointers? What if one of the slice
> elements modifies itself by referencing itself via a globally scoped
> pointer. Do we create a snapshot copies of the slice, and if so how can we
> update immutable slice to reflect changes made to the original mutable
> slice?

We don't make a snapshot copy. I don't see how that could be possible.

In Brad's proposal, a value of type [].T is not immutable. It simply
does not support any modification operations. As the doc says, this
is similar to a send-only channel. The existence of a value V of chan
<- int doesn't mean that there is no way to receive values from the
channel; it only means that you can't receive a value from V.

This proposal is analogous to a const char * pointer in C/C++. The
array to which such a pointer points may change, but it may not be
changed through that pointer.


This is perhaps something of a drawback to this proposal. It provides
a read-only view of a slice, but it in no way ensures that the slice
does not change. This has some utility as documentation: a function
or method that takes a parameter of type [].T is certain to not modify
the elements of that slice (barring the use of unsafe). And of course
we get the ability to pass a string value to a parameter of type
[].byte. But this is not the same as immutability. It is only the
inability to change the elements of a slice through a particular view
of that slice.

The proposal suffers from the strstr problem of C. The C function
strstr may be written as either "char *strstr(const char *, const char
*);" (the standard way) or as "char *strstr(char *, const char *);" or
as "const char *strchr(const char *, const char *);". The first
requires an unsafe operation in the implementation of strstr: a
conversion from const char * to char *; it also provides an
underhanded way to convert from "const char *" to "char *". The
second means that strstr may not be used to search inside a string
literal. The third means that the caller of strstr may need to
perform the unsafe operation. The equivalent problem in Go shows up
in bytes.Split. We can use [].byte as the first parameter, but then
we have to return [][].byte which may not be what the caller needs.
Or we can use []byte as the first parameter, but then we can't pass in
a string literal or a [].byte, although the function does not need to
modify the slice it is passed.

I suspect that these kinds of issues may be inevitable when trying to
provide a read-only version of a type in a language like Go, or C,
that does not support function overloading and does not support any
sort of polymorphism (e.g., func Split(T {[]byte, [].byte}, [].byte) T
which is intended to mean that the first parameter is either []byte or
[].byte and the result parameter has the same type as the first
parameter).


Note that there is another approach, which is to not make read-only
variants of types, but to instead have read-only values. The way this
works is to say that a value of type []T may happen to be immutable,
meaning that the values in the slice may not be modified. We permit
the free assignment of string to []byte, but the resulting value is
immutable. Any attempt to modify it fails, at compile time if
possible but otherwise at runtime. We implement this by, say,
negating the length field. Any attempt to access a value in the slice
uses the absolute value of the length field in the bounds check. Any
attempt to change a value in the slice uses the length field
unchanged, thus failing the bounds check. This approach loses the
documentation aspect of Write([].byte). The advantage is that the
type system does not become more complex. The disadvantage is that
more errors are detected only at runtime.

Ian

[Daniel Theophanes]

I'm sure performance could be improved with this.

It feels just different enough to feel confusing. I find the idea of a read-only map interesting. I think you've pulled a small thread on a much larger concept. Or tried to overly generalize a much smaller one (convert []byte <-> string w/o copy).

I don't like introducing such a specialized type.

Another option to creating a new read-only type is to create a region that can lock the mutability of a slice or un-lock the mutability of a string.

bb := make([]byte, 10)

lock(bb)

defer unlock(bb)

s := string(bb[:3]) // No copy.

bb[2] = 'a' // Compile error or panic.

However, I'm sure you've thought through all these options already.

-Daniel

[Ian Lance Taylor]

That's true, it could work that way. I think one of Brad's goals is
the copy-free conversion of string to [].byte, and of course a string
does not have a capacity. But I suppose we could implement that by
setting the capacity of the [].byte to the length of the string.
Still, it's hard to see any particular use for a capacity for [].byte.

Ian

[Dan Kortschak]

On Mon, 2013-05-13 at 21:28 -0700, Ian Lance Taylor wrote:
> Still, it's hard to see any particular use for a capacity for [].byte.

Yes, I was struggling to find one. None appeared that were convincing.

Dan

[Lucio De Re]

I was going to wait for the .1 version of the proposal before reading
it and the discussion so far has been quite instructive. Still, what
follows may be a little off the mark.

Firstly, I agree with Ian's view that having immutable underlying data
is more constructive than having a mechanism to pick an immutable view
of potentially mutable underlying data. The copy free conversion of a
string to a slice seems small gain for a new language construct and
the reverse operation, the copy free conversion of a [].byte to a
string does not make much sense as it would allow the creation of
mutable strings, From an embedded-system perspective, immutability
ought to be a property of memory elements, not their representation;
we may want to follow that path instead.

I wonder if the above means that once we create a view ([].byte) of a
memory region, we effectively lock that region from alteration from
anywhere? If then we extend the len() of that view, we necessarily
extend (or reduce) the read-only boundary, etc. We could then have a
view operator similar, but not necessarily visually similar to slicing
to perform such an operation on any memory area and perhaps we ought
to be looking in that direction? The compiler would not pick this up,
but the language constructs to intercept erroneous accesses to the
locked region at runtime could be added to Go and would be useful to
some developers. It may also be an interesting approach to locking.

As for using channels as an example of prior art, if assigning a
bidirectional channel to a unidirectional one effectively blocks
access to one direction, this is an artificial situation, in an ideal
situation, one would explicitly request to change the properties of
the channel instead. I hope we're not using this misfeature as
encouragemt for future development.

Lastly, in my opinion the possibility of races occurring when
manipulating complex data elements needs to be addressed, if necessary
by adding language constructs to protect critical regions. But using
the existence of such possibilities should not be deemed as permission
to continue the trend, on the contrary, in a situation where race
conditions can be eliminated or at least alleviated (having read-only
data reduces the risk of races in some respects), one ought to
consider any opportunity to eliminate race conditions entirely.

Mine are probably not the best educated comments, I'm sure, I hope
they are helpful.

Lucio.

[Brad Fitzpatrick]

On Mon, May 13, 2013 at 8:27 PM, Ian Lance Taylor <ia...@golang.org> wrote:

>>>>  In one sense

>> you are proposing a polymorphic interface type that supports the
>> operations
>>     Len() int
>>     At(int) T
>>     Slice(int, int) [].T
>> If we view this as an interface type, then reflect should return the
>> original type.  If not, then it could be a new Kind, or it could be
>> Slice with a new field.
>
>
> In what sense do you view our current send-only channels?

Channels feel a bit different to me: they remain channels, but
converting to a send-only or receive-only channel eliminates certain
operations.  Converting []byte to [].byte changes the nature of the
value, since it no longer has a capacity.

Okay, but what if it still had a capacity, in its representation and/or capability (via cap(v)), but just one you couldn't usefully use, since you couldn't append onto it?

Then it's just like channels: the same representation, but the type system is restricting the available operations. That's all I care about.

I don't care about cap() so much (I just see it as unnecessary and useless on [].T, so could go), but I do care about capabilities.  I would love an operator method world where there were interfaces like SliceReader[T] with Len() int and At(int) T, and SliceWriter[T] adding Addr(int) *T.  But in lieu of that, and before generics, I like being able to restrict access with something like [].T.

 

Converting string to
[].byte changes the meaning of the string significantly--e.g., range
and slice operations act differently.

But we can make these copy-free too:

   var v [].byte = ...

   for i, s := range string(v) { ... }

 

   var s string = ...[

   var i, s := range []byte(s) { ... }

That is https://code.google.com/p/go/issues/detail?id=2204

I would naturally expect that a range over a [].byte acts like a range over a []byte instead of a string, so I don't view that as a deficiency.

[Brad Fitzpatrick]

On Mon, May 13, 2013 at 9:16 PM, Daniel Theophanes <kard...@gmail.com> wrote:

I'm sure performance could be improved with this.

It feels just different enough to feel confusing. I find the idea of a read-only map interesting. I think you've pulled a small thread on a much larger concept. Or tried to overly generalize a much smaller one (convert []byte <-> string w/o copy).

I don't like introducing such a specialized type.

Another option to creating a new read-only type is to create a region that can lock the mutability of a slice or un-lock the mutability of a string.

bb := make([]byte, 10)

lock(bb)

defer unlock(bb)

s := string(bb[:3]) // No copy.

bb[2] = 'a' // Compile error or panic.

However, I'm sure you've thought through all these options already.

That is not the path to performance.

That seems extremely complex in both the compiler and runtime.  I think it would end up slower, and more confusing.

I'd rather use mprotect and unsafe if I wanted to play those games.