proposal: spec: add read-only slices and maps as function arguments

henryas commented 7 years ago

Background

I recently stumbled upon a bug and after hours of searching, I managed to find the culprit, which is a function that accidentally modifies the slice argument passed to it. The problem is that as I took several subsets of the original slice and gave them new identities, I forgot that they were still pointing to the original slice. I don't think this is an uncommon issue, and hence the proposal below.

Proposal

I would like to suggest the idea of defining a read-only slice and map in the function arguments. For example, we can define a function as follows:

//function definition func MyFunction(const mySlice []byte, const myMap map[string][]byte) []byte

//usage mySlice := []byte {0x00, 0x01} //normal slice definition. There is no weird const whatsoever. myMap := make(map[string][]byte) //normal map definition.

//you are still using slice and map as you normally would. Slice and map are still modifiable, //but MyFunction cannot alter the original variables. MyFunction(mySlice, myMap)

//you can still make changes here myMap["Me"] = 0x01

or in the interface definition:

type MyInterface { MyFunction(const mySlice []byte) []byte }

Why slices and maps?

With structs, interfaces and built-in types, it is easy to tell whether you want them to be modifiable or not. With slices and maps, it is not so easy to tell. Maps are probably less prone to accidental changes, but slices are tricky, especially when they get passed around many functions.

Implementation Options

Read-only slices and maps are shallow-copied upon being passed to the function. Hence, any accidental change is local to the function. I understand that this will not prevent interior mutability, but exterior mutability is good enough. I think this implementation option is probably less intrusive and there are fewer breaking changes to existing codes (if any) - possibly none.

Alternatively, we may have a more elaborate system where the compiler will not compile if a function tries to modify a read-only slice/map. However, this leads to a very complex solution. What if a new sub-slice is taken from an existing read-only slice, should it be immutable too? Now, what if that sub-slice is passed into another function, should the compiler check whether the other function preserves the integrity of the sub-slice?

I personally tend to lean with the first option.

Syntax

In order not to add any new keyword, I am thinking of reusing const, and it is also more intuitive to those familiar with C-family programming languages. However, I am open to suggestions.

Let me know what you think.

Thanks

mvdan commented 7 years ago

This has been discussed before, and such big changes to the language won't be made in 1.x. I believe there were proposals to also make string be a constant []byte.

dgryski commented 7 years ago

@rsc's previous evaluation of read-only slices: https://docs.google.com/document/d/1-NzIYu0qnnsshMBpMPmuO21qd8unlimHgKjRD9qwp2A/edit

henryas commented 7 years ago

Russ Cox's evaluation applies to the second part of my possible implementation options. While I welcome full-blown read-only types, I do agree that it is a complex issue that must be thoroughly analyzed.

However, what I originally required is nothing revolutionary. See the first implementation option. It can be done in Go 1.x now, but it requires boilerplate for each type. See illustration. It would be nice to have a keyword to do automatic shallow-copying for slice and map for all types without the boilerplates. The objective is to protect the original variables against accidental changes. After slicing and re-slicing and several functions later, it was crazy to track all those mutated slices to find who did what that caused the bug.

dnfield commented 7 years ago

I think this is a great idea, but I don't like the idea of shallow copying. There's nothing stopping you from creating your own types over a slice that do this, and that way at least it's very transparent to you and consumers that they're actually getting copies of data.

I'd love to see go support read only types that are enforced at compile time. Slices in particular - simply have a compile error if someone tries to invoke code that would involve assigning to a slice that's const or read only. I understand it'd be a bit more involved than that, but it'd be very helpful.

henryas commented 7 years ago

Go's slices are way too powerful and flexible that people rarely have to deal with arrays directly any more. In my opinion, a slice should be a read-only view into an array. So if people want to change the content of an array, they would need to deal with the array and not its slice.

If we are going into that direction, then there is no need for new keywords to indicate immutability.

davecheney commented 7 years ago

Appending is a very common operation, how do you propose that append would with your read only slice proposal?

On 17 Jun 2017, at 21:58, henryas notifications@github.com wrote:

Go's slices are way too powerful and flexible that people rarely have to deal with arrays directly any more. In my opinion, a slice should be a read-only view into an array. So if people want to change the content of an array, they would need to deal with the array and not its slice.

If we are going into that direction, then there is no need for new keywords to indicate immutability.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or mute the thread.

dnfield commented 7 years ago

I do not agree that slices should become exclusively read only. Being able to modify slices is an attractive feature, and changing that would be a very radical breaking change.

Appending to a read only slice should throw a compiler error, like any other operation that involves assignment

henryas commented 7 years ago

How about this? You can still work with slices as usual. You can slice, re-slice, append, make it point to different values, etc. However, regardless what you do to the slice, it won't change the backing arrays and slices. You can think of a slice like a pointer. You can make it point to different values at any time, but in this case you can't change the value you are pointing at.

leiser1960 commented 7 years ago

What is the goal? Better documentation, or race free code? Your proposal goes for the first, I assume. You give the the guarantee that your function will have no way to alter the underlaying array. But you do not get the guarantee that your function is race free in respect of changes to this array, because other goroutines may modify the underlaying array concurrently. Adding immutability to golang should go for both goals, i.e. full value semantics as we have it for strings. This changes assignment as well as comparison semantics. But would help significantly reasoning about non sequential program behaviour. Adding a simple form of immutibility to the type system of go is big challenge, both for language design and implementation. But please go for it!

dnfield commented 7 years ago

I agree that immutability would be great, but I think that's a little different from read-only.

For instance, you could make copy-on-write slices that are immutable - any reference to them points to a structure that doesn't change. That could certainly be powerful and useful, but a bit different from what I understand this proposal to be, which is a bit narrower in scope: simply to have compile time checking that a slice can't be written to if passed as readonly or created as readonly.

On Sat, Jun 17, 2017 at 1:25 PM, leiser1960 notifications@github.com wrote:

What is the goal? Better documentation, or race free code? Your proposal goes for the first, I assume. You give the the guarantee that your function will have no way to alter the underlaying array. But you do not get the guarantee that your function is race free in respect of changes to this array, because other goroutines may modify the underlaying array concurrently. Adding immutability to golang should go for both goals, i.e. full value semantics as we have it for strings. This changes assignment as well as comparison semantics. But would help significantly reasoning about non sequential program behaviour. Adding a simple form of immutibility to the type system of go is big challenge, both for language design and implementation. But please go for it!

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/golang/go/issues/20443#issuecomment-309228554, or mute the thread https://github.com/notifications/unsubscribe-auth/AIOKxX3FGb5iAbgyXz0uLPvBJWLDlPZkks5sFAwagaJpZM4NhrYK .

leiser1960 commented 7 years ago

Const and immutability are different. Obvious to me. The idea to allow an implementation to even modify the const parameter having but still maintaining the "const" guarantee to the caller is very interesting.

I simply asked for more. Why? The spirit of go is about simplicity and consistency, not about ease of implementation and piece meal. So const should work for slices maps all types (perhaps except channels, const channels seem useless to me).

But I support the proposal for more control over mutability, because this is the number one problem when you have concurrency in your program. And the more support you get from the language, compiler, race checker... the better it gets for the programmer.

COW slice implementations are well know, go strings are immutable, I know about COW versions of balanced trees, not shure about hash maps. But your proposal should also be extensible to maps as well.

Am 17. Juni 2017 19:32:43 MESZ schrieb Dan Field notifications@github.com:

I agree that immutability would be great, but I think that's a little different from read-only.

For instance, you could make copy-on-write slices that are immutable - any reference to them points to a structure that doesn't change. That could certainly be powerful and useful, but a bit different from what I understand this proposal to be, which is a bit narrower in scope: simply to have compile time checking that a slice can't be written to if passed as readonly or created as readonly.

On Sat, Jun 17, 2017 at 1:25 PM, leiser1960 notifications@github.com wrote:

What is the goal? Better documentation, or race free code? Your proposal goes for the first, I assume. You give the the guarantee that your function will have no way to alter the underlaying array. But you do not get the guarantee that your function is race free in respect of changes to this array, because other goroutines may modify the underlaying array concurrently. Adding immutability to golang should go for both goals, i.e. full value semantics as we have it for strings. This changes assignment as well as comparison semantics. But would help significantly reasoning about non sequential program behaviour. Adding a simple form of immutibility to the type system of go is big challenge, both for language design and implementation. But please go for it!

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/golang/go/issues/20443#issuecomment-309228554, or mute the thread

https://github.com/notifications/unsubscribe-auth/AIOKxX3FGb5iAbgyXz0uLPvBJWLDlPZkks5sFAwagaJpZM4NhrYK .

-- You are receiving this because you commented. Reply to this email directly or view it on GitHub: https://github.com/golang/go/issues/20443#issuecomment-309228901

-- Diese Nachricht wurde von meinem Android-Mobiltelefon mit K-9 Mail gesendet.

davecheney commented 7 years ago

Would this be valid under your proposal, and what would be the final value of x?

x := int{1,2,3} y := x[:2] z := append(y, 5)

On Sat, 17 Jun 2017, 23:46 henryas notifications@github.com wrote:

How about this? You can still work with slices as usual. You can slice, re-slice, append, make it point to different values, etc. However, regardless what you do to the slice, it won't change the backing arrays and slices. You can think of a slice like a pointer. You can make it point to different values at any time, but in this case you can't change the value you are pointing at.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/golang/go/issues/20443#issuecomment-309216103, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAcA77_08XDdk2VLKuG2paKdcYfer45ks5sE9iqgaJpZM4NhrYK .

henryas commented 7 years ago

@dave: the final value of x should remain unchanged, which is {1,2,3}

Anyhow, please do not take this proposal strictly as is. The idea is there, but implementation-wise I am not so certain, which is why I welcome everybody's inputs on this matter. Some form of control over a variable's mutability will certainly be beneficial to Go.

davecheney commented 7 years ago

On Sun, Jun 18, 2017 at 11:32 AM, henryas notifications@github.com wrote:

@dave https://github.com/dave: the final value of x should remain unchanged, which is {1,2,3}

But how can that be, if you permit reslicing and appending?

Anyhow, please do not take this proposal strictly as is. The idea is there, but implementation-wise I am not so certain, which is why I welcome everybody's inputs on this matter. Some form of control over a variable's mutability will certainly be beneficial to Go.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/golang/go/issues/20443#issuecomment-309250785, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAcA44C_XRmFuCIS371aGCzlSb1v6SKks5sFH5IgaJpZM4NhrYK .

henryas commented 7 years ago

@dave: y is a new slice that points to X's first two values. X remains as it is. Y is just a "pointer" to x. Z is a new slice that points to Y's values and 5, but it doesn't change x and y. Even if you were to do z[0] = 7, z at index 0 just points to a new value of 7, but it doesn't change x and y.

But I welcome any other idea. It was just something that came to me as I was driving home from work yesterday.

davecheney commented 7 years ago

So your proposal is every reslicing operation makes a copy of the slice's contents?

On Sun, 18 Jun 2017, 11:55 henryas notifications@github.com wrote:

@dave https://github.com/dave: y is a new slice that points to X's first two values. X remains as it is. Y is just a "pointer" to x. Z is a new slice that points to Y's values and 5, but it doesn't change x and y. Even if you were to do z[0] = 7, z at index 0 just points to a new value of 7, but it doesn't change x and y.

But I welcome any other idea. It was just something that came to me as I was driving home from work yesterday.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/golang/go/issues/20443#issuecomment-309251491, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAcA783fFqZILJnMDreGY5o_2I40j6Gks5sFIOagaJpZM4NhrYK .

henryas commented 7 years ago

Nope. Not a copy. If someone are to change x, the change will cascade down to y and z as long as they are still pointing to any value of x.

Think of a slice like pointers to some values. When the values change, the slice will change too. However, when the slice is changed, it just points to the new values. The old values remain unaffected.

davecheney commented 7 years ago

In my example, currently x ,y and z all point to the same backing array. In your proposal I don't see how to retain the semantics of y and z being unable to modify the contexts of the x without reslicing and or appending making a copy of the slice's backing array. However if that was the case then changes to x would not be reflected in y or z.

I don't see how your proposal will be workable without removing ay least one of append or reslicing.

On Sun, 18 Jun 2017, 12:22 henryas notifications@github.com wrote:

Nope. Not a copy. If someone are to change x, the change will cascade down to y and z as long as they are still pointing to any value of x.

Think of a slice like pointers to some values. When the values change, the slice will change too. However, when the slice is changed, it just points to the new values. The old values remain unaffected.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/golang/go/issues/20443#issuecomment-309252356, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAcA5nc2oG5p44eR-6mCNZPOFZZZZJ5ks5sFInOgaJpZM4NhrYK .

henryas commented 7 years ago

Think about the table of contents (TOC) of a book. The TOC is the slice, the content of the book are the actual values. If you need to find something, you look up the TOC, find the page it refers to, and find the page and read the information.

When the content of a page changes, naturally people who looks up via TOC will see the change. Hence, changes in x will cascade down to y and z.

However, when you change the entries in the TOC, eg. changing the page number a TOC entry points to, people use the TOC will see the new page, but the content of the book remains unchanged. Hence, changes in z does not cascade up to x and y.

davecheney commented 7 years ago

Sure, but how to you propose to implement this at a language level.

On Sun, Jun 18, 2017 at 12:42 PM, henryas notifications@github.com wrote:

Think about the table of contents (TOC) of a book. The TOC is the slice, the content of the book are the actual values. If you need to find something, you look up the TOC, find the page it refers to, and find the page and read the information.

When the content of a page changes, naturally people who looks up via TOC will see the change. Hence, changes in x will cascade down to y and z.

However, when you change the entries in the TOC, eg. changing the page number a TOC entry points to, people use the TOC will see the new page, but the content of the book remains unchanged. Hence, changes in z does not cascade up to x and y.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/golang/go/issues/20443#issuecomment-309253014, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAcA-5OwNNPG3GAZ-Wkr_NYbEsHtsEEks5sFI6KgaJpZM4NhrYK .

dnfield commented 7 years ago

It seems to me that we have at least a few proposals here:

Most basically, support for some kind of read-only/const declaration of slices (and perhaps maps), to trigger a compiler error if you try to do anything to that slice that would modify it. Thus all assignments/appends would fail, as would any attempt to create a writable (non-const) sub-slice from it. This should be a non-breaking change, as effectively a read-only slice would be a new type that is not currently used.
Immutable types. While this could be done without exposing the plumbing for it to users, it's hard to say how that would really help (particularly if you want to be able to send users a read-only slice to read from without creating a copy of the memory). So, for example, point 1 might enable something like: func (const []byte) AppendBytes(const []byte bytes) const []byte
Completely changing the nature of slices in a non-compatible way. I'm struggling to see the value of this - users are used to reasoning about mutable slices (even if it's complicated to do so and error prone). There's lots and lots of code out there that uses mutable slices. I strongly oppose the idea that slices should automatically allocate new memory (or, more new memory than the minimum needed for the pointer/len/capacity) - the whole point of slices is that they avoid these allocations.

For what it's worth, I see this as parallel to some of the work going on in .NET Core 2.0 around Span<T> and ReadOnlySpan<T>, with slice as is being parallel to Span<T>. I also see this as a very valuable tool for use in concurrency scenarios where it's critical to avoid unnecessary allocations and data copying for read only usage. I'm less concerned with mistakes someone might make from passing slices when they really should be using arrays (which seems to be a bigger concern for @henryas )

leiser1960 commented 7 years ago

The proposal here is not about immutable types, it is about your point 1 or 2 @davecheney question was, if y is a const slice (which is my interpretation) i.e. x := int{1,2,3} var y const []int = x[:2] z := append(y, 5) What is z pointing to? Will the last line compile?

You may prohibit the last line completely, or allow it. In the second case z must point to a new array, and be of type []int. append applied to a const slice behaves as if len==cap. This would be a consistent extension, a const slice simply has no cap at all.

My concerns are about the question: x := int{1,2,3} var y const []int = x[:2] z := x[:2] x[0] = 9. // or z[0] = 9 which is the same b := y[0] == z[0] Is b true or false? This proposal says true. Immutability would require it to be false. Reasoning about the program with immutability is much simpler because immutable values are race free. Implementing it efficiently may be a bit harder.

The question: Does z and y point to x? Is not a relevant question for immutable types. It must not be detectable! (It may as long as no one changes x as in my example.) But it is of big importance for the const proposal and race detection.

creker commented 7 years ago

I think simple const keyword like in C could be naturally (and probably within Go 1.x) extended to a shallow immutable solution. Instead of throwing compile errors, on any change to the const slice compiler could emit a shallow copy operation. Changing an element in a const slice - make a copy and make the change to that copy. Appending - make a copy and append to that. Crossing any boundary between const and non-const should make a copy. Of course, these copy operations must be thread-safe. Otherwise it's useless.

The big problem with that is hidden copy operations and change of semantics. You're no longer sure exactly how your assignment/append will work without looking up the type of the slice. We kind of have the same problem with methods with value/pointer receivers but it's less obvious here.

davecheney commented 7 years ago

I'm strongly opposed to this hidden copying. There is already enough of that in the language as it is, eg.

var ints [2^24]int for i := range ints { // there's a copy here }

On Mon, Jun 19, 2017 at 9:09 AM, Antonenko Artem notifications@github.com wrote:

I think simple const keyword like in C could be naturally (and probably within Go 1.x) extended to a kind of immutable solution. Instead of throwing compile errors, on any change to the const slice compiler could emit a shallow copy operation. Changing an element in a const slice - make a copy and make the change to that copy. Appending - make a copy and append to that. Of course, these copy operations must be thread-safe. Otherwise it's useless.

The big problem with that is hidden copy operations and change of semantics. You're no longer sure exactly how your assignment/append will work without looking up the type of the slice. We kind of have the same problem with methods with value/pointer receivers but it's less obvious here.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/golang/go/issues/20443#issuecomment-309309026, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAcAyYgjLhCdEfWLc5cz7wmQdkhmAw0ks5sFa4fgaJpZM4NhrYK .

cespare commented 7 years ago

Read-only slice types seem like a more or less reasonable proposal -- which is why Russ's evaluation of such a proposal (linked to by @dgryski earlier) was very in-depth and involved a real implementation of the feature. By contrast, I think that immutable types which do full copies of themselves transparently are a fairly unserious feature in a language where performance is even a vague concern.

Immutable types in other languages allow you to "modify" them (i.e. get a new object that's a modification of the old object while leaving the old object untouched) without doing full copies all over the place. For example, in Clojure, the persistent types such as vectors and maps are backed by tree structures which allow multiple objects to share common structure. When you append something to a vector or associate a new key/value into a map, the cost of that operation and the amount of extra space used is ~constant, not linear in the size of the vector/map.

That said, I doubt that any form of immutable/persistent data structures like these fit well in the Go language (though I look forward to Russ's evaluation of immutability in the future).

dnfield commented 7 years ago

It seems significantly different to approach this as a simple static analysis/compile time check rather than a full blown runtime type. If I read Russ's analysis correctly, it seems that he's approaching it more from a runtime point of view than a compile time point of view. I think it's also more interesting from an interface/contract perspective than from a code consolidation perspective. In other words, readonly would simply mean that the recipient cannot modify the data (if they want to, they must first create their own local mutable copy). This is really only enforceable at compile time - someone reflecting on the type should be able to overcome it, no matter what kind of runtime limitations you try to impose.

I also don't see readonly as meaning "can't change" - if the source changes, the source changes. Consumers of a readonly []byte shouldn't assume that the data in the backing array is immutable, simply that they're not allowed to change it

creker commented 7 years ago

doing full copies all over the place.

That's a common misconception with immutability and you will find it debunked in many posts. In theory, yes. When you actually use it in real application the copying is not such a big problem. You end up passing the same immutable collection because it's thread-safe by definition saving in memory and performance because you don't need synchronization. Very likely you will end up with architecture which doesn't require much copying in the first place. Of course, it still depends on the specific case. In some cases you might end up with even less garbage. In others with more. So something like Clojure persistence vectors would be beneficial. But that's an implementation detail which could be introduced later as a runtime optimization. No need to do everything at once.

But, still, hidden copy operations are a big problem and most likely will lead to bugs when you try to modify an immutable slice thinking it was mutable.

leiser1960 commented 7 years ago

@dnfield wrote

I also don't see readonly as meaning "can't change" - if the source changes, the source changes. So readonly or const does nothing to prevent races. Even if may code cannot change the data it may be part of the data race. But it still helps with reasoning, because you know its readonly in this function.

creker commented 7 years ago

But that kinda makes it useless and degrades it into C/C++ consts. The code that accepts const slice still has to reason about changes that may occur outside which, in my opinion, defeats any purpose of this construct.

henryas commented 7 years ago

I think we need to figure out whether we want "read-only" or "const" or both. To me, "read-only" implies we can read it but someone else may change it while we are reading it. On the other hand, "const" means the variable is fixed and it's not going to change.

To ensure a const guarantee, a const slice must comes from a const array. That's the only safe way you can have a const slice. After all, a slice is just a reflection of the underlying array. So instead of trying to const the slice, we should const the array.

Regarding "read-only" and thread safety, Go (at least Go 1.x) is not a concurrent-safe language in the first place. It is up to the programmers to ensure data race does not happen. To be concurrent-safe, immutability alone is not enough. You need to implement a similar mechanism to Rust's ownership and borrowing system. If we are going to that direction, we may as well go without GC since we are already halfway there, but that's another topic. So I don't think we should shoot down the "read-only" suggestion based on possible data-races.

dnfield commented 7 years ago

@creker , how on earth would we avoid that?

It's not possible to guarantee that a source array won't be modified at runtime - even if you build in all the compile checks in the world, some form of reflection or unsafe or the underlying subsystem (or cgo) will be able to overcome it.

All that's really possible is to guarantee that a given function won't (or can't) attempt to modify data it's given access to. You're telling that function "if you want to modify this data, you need to make a copy of it, and understand you're working only on the mutable copy." The function's telling you "I promise I won't modify this data (without resorting to some kind of awful reflection/unsafe trick), so you don't have to worry about any synchronization if you call me, and I can't mess up other readers." Yes, that's probably a lot like C/C++ consts, but it's functionality that is lacking in Go and would be useful.

As it stands right now, if I pass a slice to a function, I have no way of telling that function (or any other function it calls) not to try to modify that slice. Other members of the project have no easy way to reason about whether they should be allowed to modify the underlying data, and when or if they might need to copy the data. It's all pretty dangerous and certainly an easy way to introduce difficult to track bugs. It's a problem that can certainly be solved by the language and the compiler, even if it leaves other problems around that are challenging.

bcmills commented 7 years ago

@dnfield

even if you build in all the compile checks in the world, some form of reflection or unsafe or the underlying subsystem (or cgo) will be able to overcome it.

unsafe allows you to violate the semantics of the language, but if you do that in your program that's your own bug to deal with. In particular, the language and runtime do not need to work around programs that use unsafe to do things that are explicitly forbidden.

That said, the historical usage of the word const to mean "read-only" in C and C++ suggests that we should not use that same word to mean "immutable".

bcmills commented 7 years ago

@henryas

Regarding "read-only" and thread safety, Go (at least Go 1.x) is not a concurrent-safe language in the first place. It is up to the programmers to ensure data race does not happen.

Some of us regard that as a defect which should be remedied. If we're going to pay the cost of adding a feature to the language, we should ensure it provides commensurate benefits.

The mutation bugs I tend to see in real-world Go programs are not bugs that would be detected or fixed by const as proposed here. For example, I've seen many io.Writer implementations that do not modify the passed-in buffer but do erroneously access it after control has returned to the caller:

func (w *Writer) Write(p []byte) (n int, err error) {
  w.sending.Add(1)
  go w.send(p)  // BUG: May access p after Write returns.
  return len(p), nil
}

func (w *Writer) Close() (err error) {
  w.sending.Wait()
  return w.firstError()
}

To detect that class of error, we would need to combine the "read only" const property with some other property ("local"?), or else enforce deeper immutability. I don't think const alone pulls its weight.

creker commented 7 years ago

@dnfield, there's always a way to overcome something. If you're violating certain semantics, then you're on your own.

I already proposed a solution to avoid that. Yes, it's shallow immutability but still. You have a guarantee that no one can change your immutable slice because any change operation on it produces a new slice with a new backing array. Without going into unsafe/reflection zone there's no way to modify someone's data. You could go the other way and forbid changes to immutable slice at compile time and required programmer to first make a mutable copy. Either way it's race-free by design, which is what immutability is all about.

@henryas, immutability can guarantee race-free code even without Rust ownership model. Look at functional languages.

henryas commented 7 years ago

@creker. Actually, immutability is only one aspect in functional languages in dealing with data race, and it alone isn't adequate. Haskell has MVar which works like mutex. It also has message which is like Go's channel. It also has other tools, such as STM. The takeaway is that the language itself does not promise race-free codes. It still depends on the programmers to ensure race free codes. Rust is probably the only one that makes a bold claim of being a data-race free language. So you need more than immutability to make a race-free language.

creker commented 7 years ago

@henryas

the language itself does not promise race-free codes. It still depends on the programmers to ensure race free codes

And I'm not debating that and never have I said that immutability would make Go a race-free language, which is a pretty big claim. All I'm saying is immutability does give you the ability to write race-free code (no mutable shared state, no data races) without using much of the synchronization primitives you would use with mutable state. Data dependencies become much easier to reason about which alone gives you a huge benefit when writing concurrent code. Go has some nice features that also allow you to write race-free code much easier and immutable collections could be another such feature. Your proposal is pretty much what I'm suggesting with shallow immutability.

leiser1960 commented 7 years ago

@davecheney:

I'm strongly opposed to this hidden copying.

That is a strong point. When you go from a mutable value to an immutable one a hidden (deep) copy may be necessary. It may be elided if there are no further modifications to the modifiable value. So if you share by communication and do so by sharing immutable values, the compiler should be able to elide the copy.

If not the programm is still safer but slower.

I believe the borrowing of rust may be an interesting model for go as well. But That would be a completely different proposal.

@henryas: rusts borrowing model solves your writer problem. It is a bug to let a borrowed value escape.

As far is I remember my compiler construction lessons long ago escape analysis, alias analysis and borrowing are very similar mechanisms in the implementation all based on data flow analysis.

henryas commented 7 years ago

How about turning the built-in arrays, slices, and maps into 'objects' with methods attached to them? That way we can use interface to create their read-only types and the compiler can enforce their intended usage as defined by the interface. In fact, the user can define their own version of restricted maps, slices, and arrays.

With this approach, there is no need for any new keyword. We can further slim down Go's specs by removing the array, slices, and maps related syntax. The behavior of the array, slices and maps will now be defined by their methods.

myitcv commented 7 years ago

I don't have any specific comments on this proposal; rather just wanted to point out an experiment with immutable data structures that I've put together: https://github.com/myitcv/immutable

The principal focus of this experiment has been the interface to the code-generated immutable data structures; there are clearly countless optimisations etc that could be made to the underlying implementation.

Given we don't have any language-level support for immutable data structures, in our approach we're limited to implementing immutability via types and their methods. This gives the overall interface a rather bloated feel, but despite this, as others have commented above, in certain situations it becomes significantly easier to reason about things knowing you are working with immutable data structures (nothing new in that statement obviously).

Like @cespare, I'm interested to hear the result of @rsc's evaluation of immutability.

ianlancetaylor commented 7 years ago

@myitcv I skimmed your wiki page, and it's not obvious to me that you are describing what I would call immutable data structures. I may well have missed something but it looks more like C-style const references--that is, references to a data structure such that you can not change the data structure through that reference, but the data structure can be changed in other ways through other non-const references.

If I'm right about that, then I think that is a reasonable thing to discuss, but I don't think we should use the name "immutable" for it. To me "immutable" connotes a data structure that can not change after it has been initialized.

My apologies if I misunderstand.

myitcv commented 7 years ago

@ianlancetaylor - I might well be using the term incorrectly, so any apology is just as likely required from my side!

The wiki doesn't do a great job of providing a motivating example, so I'll try and provide one here (and then refine the wiki). And if we conclude my use of the term "immutable" is incorrect, then I'll fix that too, but bear with its use for what follows.

immutableGen is a go generate generator that creates immutable struct, map and slice type declarations from template type declarations.

For example, consider the declaration of an immutable struct type Person:

// person.go
package example

import "fmt"

//go:generate immutableGen

// via go generate, this template is code generated into the immutable Person
// struct within the same package
type _Imm_Person struct {
    Name string
    Age  int
}

// Hence we can then define methods on *Person (methods can only be defined on
// a pointer receiver)
func (p *Person) String() string {
    return fmt.Sprintf("Person{ Name: %q, Age: %v}", p.Name(), p.Age())
}

The type Person is declared in the generated code

A quick test of the resulting types:

package example_test

import (
    "fmt"
    "testing"

    "myitcv.io/immutable/example"
)

func TestThis(t *testing.T) {
    // the zero value of Person is immutable
    p1 := new(example.Person)

    fmt.Printf("p1: %v\n", p1)
    fmt.Println()

    // hence setting the name on the Person pointed to by p1 leaves that Person
    // unchanged and instead returns a new Person with the name set (notice the
    // code generated "setter" for Name)
    p2 := p1.SetName("Paul")

    fmt.Printf("p1: %v\n", p1)
    fmt.Printf("p2: %v\n", p2)
    fmt.Println()

    p3 := p1.WithMutable(func(p *example.Person) {
        // WithMutable is used whre multiple mutations are required... but again
        // the mutations are applied to a copy (the p passed to this function is
        // mutable copy of p1, which when WithMutable returns is marked
        // immutable)
        p.SetName("Monty Python")
        p.SetAge(42)
    })

    fmt.Printf("p1: %v\n", p1)
    fmt.Printf("p2: %v\n", p2)
    fmt.Printf("p3: %v\n", p3)
}

gives the output:

p1: Person{ Name: "", Age: 0}

p1: Person{ Name: "", Age: 0}
p2: Person{ Name: "Paul", Age: 0}

p1: Person{ Name: "", Age: 0}
p2: Person{ Name: "Paul", Age: 0}
p3: Person{ Name: "Monty Python", Age: 42}

Once initialized, a *Person value cannot be modified; any attempt to do so returns a copy that has been modified (let me repeat the aforementioned caveat of a very inefficient implementation at this stage). Same goes for immutable slices and maps generated via immutableGen.

Correct usage of methods on these generated immutable types is enforced by immutableVet)

The interface to such immutable data structures is, as you can see, quite bloated. But again, this is just an experiment based on the existing Go language.

So I think that fits with the definition of immutable data structures?

ianlancetaylor commented 7 years ago

I see, so you have a set of methods that return a copy that can be modified. OK, I agree that this does seem like an immutable type. (I think I would just provide a single method that returns a copy.) Thanks for the explanation.

myitcv commented 7 years ago

I see, so you have a set of methods that return a copy that can be modified

Almost; the methods return a modified copy, but the returned value is itself immutable. So any attempt to "modify" the returned value (via a "setter") results in another copy.

Hence (p2 as before):

p4 := p2.SetAge(42)

fmt.Printf("p1: %v\n", p1)
fmt.Printf("p2: %v\n", p2)
fmt.Printf("p4: %v\n", p4)

gives:

p1: Person{ Name: "", Age: 0}
p2: Person{ Name: "Paul", Age: 0}
p4: Person{ Name: "Paul", Age: 42}

(WithMutable and AsMutable/AsImmutable allow for working with a mutable receiver where multiple changes are required)

henryas commented 7 years ago

If you turn Person into objects, what you are trying to do is already achievable without needing code generation. See https://play.golang.org/p/TUaq76pB98

I do think that by wrapping them into objects, we can take advantage of Go's interface to solve this problem. The same goes with array, slices, and maps. However, the problem with the built-in array, slices, and maps is that they have no behavior (no methods) and thus one cannot directly apply interface to them. You need to create new objects by wrapping those built-in collections. On one hand, you can say it is a good practice to wrap a collection because you are giving them a domain identity. On the other hand, it involves additional boilerplate code. Without generics, you end up creating many different collection objects for each different type.

I believe we should look into using Go's interface instead of looking for new magic keywords.

myitcv commented 7 years ago

@henryas thanks, I think I get what @ianlancetaylor was referring to now by the "single method that returns a copy". So we're using the same definition for immutability, it's just different interfaces/approaches.

Of course there is nothing that requires code generation; we introduced it because it was easy and it saved writing tonnes of boilerplate as you say. Taking your example, code generation would allow you to "explode":

type personImpl struct {
    name string
    age  int
}

into the full implementation you have in your linked example.

Writing code to write less code as someone once said 👍

Azareal commented 7 years ago

Something which would be useful in addition to const maps and slices are const keys for maps. In other words, you declare all the keys the map can have and it'll be enforced by the compiler. While it overlaps with structs, it has the benefits of a map. E.g. Calling the field stored in a string without using reflection.

And for full const maps, I don't think any of the keys or contents should be editable.

var blahblah map[const string]string Constant keys.

var blahblah map[string]string Normal map.

const blahblah map[string]string Full constant map.

Perhaps, something like this. This would help eliminate bugs (e.g. calling the wrong key), and to give the compiler more chances to speed things up. For things which can be detected at compile time, it would error and halt compilation, otherwise it would panic.

hooluupog commented 6 years ago

Just give my two cents, I'd love to be able to send immutable / read-only data(a very large slice,map,struct,etc) back and forth to goroutines through channel.There are three use cases,

Read-only access the data by different goroutines without needing to do a full copy. It's safe and performant to share immutable data.
Read-write access the data by different goroutines. Then copy-on-write is inevitable.
Send data[1] to only one receiver(Only receiver has the right to modify the data once sent out). The sent data is not copied, just the ownership of the data is transferred to the receiver.So Something like Transferable Objects [2] would be helpful. [1]the sent data can be parts of origin data. For example,The sender created a large list and sent subLists(different list segments) to many receivers simultaneously.Each receiver just got the ownership of its own sublist. [2]https://developers.google.com/web/updates/2011/12/Transferable-Objects-Lightning-Fast

henryas commented 6 years ago

I may have a change of opinion about this proposal since I first wrote it. I would now be very cautious about introducing mutability/immutability (or something similar) into Go. Being able to tell the compiler exactly what you want so that it can work smarter and help you catch errors is always ideal. Mutability/immutability embodies one of those ideals. However, implementation-wise, it introduces a whole lot of other problems.

In order to be able to specify a type as a mutable/immutable, you also need to be able to mark their methods as such. In Go, you may do this by adding an extra keyword to the receivers. You may also need to be able to mark the method signature in an interface as mutable/immutable. Once you have mutability qualifiers all over the place, you have to give extra thought when designing your code because if you are not careful, you may hinder your code future usability due to the unnecessary constraints you place in your codes. Even after some careful consideration, you may still find yourself in an awkward situation due to the mutability constraints. In Rust, they have a number of special pointers to bail you out when everything else fails. One such smart pointer is the Cell/RefCell, which is a way to allow mutability in an immutable object. When I first learned about it, I thought I would never going to need it. It turns out that there are quite a number of occasions when I had to use it. One such example is when I needed to create a mock object. The methods being mocked specify that the receiver must be immutable (because the actual object mustn't change anything), and yet the mock object needs to update itself in order to keep track of the way the mock object is used. Hence, the need for the smart pointers.

I am now of the opinion that Go's current approach, although it is far from perfect, is simpler and less mentally taxing. I would wait until something better comes along.

leiser1960 commented 6 years ago

@henryas:

I would now be very cautious about introducing mutability/immutability (or something similar) into Go.

Being cautious is always a good idea. But sending a mutable value over a channel is risky. Adding immutability is tricky, but locating race conditions is difficult. Your proposal is a step in the right direction.

dnfield commented 6 years ago

I think immutability in Go is still a great thing to pursue. I still think we have a few different good ideas in here that would be of varying utility and difficulty to implement.

The use case that drew me to this has to do with unsafe/syscall usage. I would like to be able to memory map a file in Go and pass around slices with confidence that receivers cannot modify them (without going unsafe themselves). This is more or less having an interface that utilizes something like C const, and is really just a compile time constraint. The benefit is that it could allow services to process large amounts of read-only data more efficiently. And this is less about preventing race conditions rather than protecting memory/data integrity - if I'm working with a read-only slice, I know I don't have to worry about data read/write race conditions, and I also know that none of my consumers can mess with that.

I can also see a great case for having runtime immutability, which would almost certainly involve some of the copying mechanisms that have been discussed above. That certainly seems like a bigger issue and something that would require some new features. It's different than the use case I mention above though.

golang / go