Skip to content
New issue

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

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

Already on GitHub? Sign in to your account

proposal: Go 2: express pointer/struct/slice/map/array types as possibly-const interface types #28608

Open
ianlancetaylor opened this issue Nov 6, 2018 · 24 comments

Comments

Projects
None yet
10 participants
@ianlancetaylor
Copy link
Contributor

commented Nov 6, 2018

I propose that it be possible to express pointer, struct, slice, map, and array types as interface types. This issue is an informal description of the idea to see what people think.

Expressing one of these types as an interface type will be written as though the non-interface type were embedded in the interface type, as in type TI interface { T }, or in expanded form as type TS interface { struct { f1 int; f2 string } }. An interface of this form may be used exactly as the embedded type, except that all operations on the type are implemented as method calls on the embedded type. For example, one may write

type S struct {
    f1 int
    f2 string
}

type TS interface {
    S
}

func F(ts TS) int {
    ts.f1++
    return ts.f1 + len(ts.f2)
}

The references ts.f1 and ts.f2 are implemented as method calls on the interface value ts. The methods are implemented as the obvious operations on the underlying type.

The only types that can be converted to TS are structs with the same field names and field types as S (the structs may have other fields as well).

Embedding multiple struct types in an interface type can only be implemented by a struct with all the listed fields. Embedding a struct and a map type, or other combinations, can not be implemented by any type, and is invalid.

For an embedded pointer type, an indirection on the pointer returns an interface value embedding the pointer target type. For example:

type S struct {
    F int
}

type IP interface { *S }
type IS interface { S }

func F(ip IP) {
    s := *ip // s has type IS
    *ip = s // INVALID: s is type IS, but assignment requires type S
    *ip = S{0} // OK
}

Values of one of these interface type may use a type assertion or type switch in the usual way to recover the original value.

This facility in itself is not particularly interesting (it does permit writing an interface type that implements "all structs with a field of name F and type T). To make it more interesting, we add the ability to embed only the getters of the various types, by using const.

type TS interface { const S }

Now the interface type provides only the methods that read fields of S, not the methods that change (or take the address of) fields. This then provides a way to pass a struct (or slice, etc.) to a function without giving the function the ability to change any elements.

Of course, the function can still use a type assertion or type switch to uncover the original value and modify fields that way. Or the function can use the reflect package similarly. So this is not a foolproof mechanism.

Nor should it be. For example, it can be useful to write type ConstByteSlice interface { const []byte } and to use that byte slice without changing it, while still preserving the ability to write f.Write(cbs.([]byte)), relying on the promise of the Write method without any explicit enforcement.

This ability to move back and forth permits adding "const-qualification" on a middle-out basis, without requiring it to be done entirely bottom-up. It also permits adding a mutation at the bottom of a stack of functions using a const interface, without requiring the whole stack to be adjusted, similar to C++ const_cast.

This is not immutability. If the value in the interface is a pointer or slice or map, the pointed-to elements may be changed by other aliases even if they are not changed by the const interface type.

This is, essentially, the ability to say "this function does not modify this aggregate value by accident (though it may modify it on purpose)." This is similar to the C/C++ const qualifier, but expressed as an interface type rather than as a type qualifier.

This is not generics or operator overloading.

One can imagine a number of other ways to adjust the methods attached to such an interface. For example, perhaps there would be a way to drop or replace methods selectively, or add advice to methods. We would have to work out the exact method names (required in any case for type reflection) and provide a way for people to write methods with the same names. That would come much closer to operator overloading, so it may or may not be a good idea.

@ianlancetaylor ianlancetaylor added this to the Go2 milestone Nov 6, 2018

@gopherbot gopherbot added the Proposal label Nov 6, 2018

@martisch

This comment has been minimized.

Copy link
Member

commented Nov 6, 2018

"Now the interface type provides only the methods that read fields of S, not the methods that change (or take the address of) fields."

I think this should only apply (could be clarified) to the "visible" effects on values. e.g. a map should still be able to do some internal restructuring e.g. move a value internally from old to new bucketarray on map access if thats an implementation detail for performance.

As for methods attached to the interface it could be evaluated if some operations that are currently only available through pattern matching as compiler optimizations could be exposed explicitly e.g. f.map.clear() or f.slice.clear().

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor Author

commented Nov 6, 2018

@martisch Agreed. Thanks.

@deanveloper

This comment has been minimized.

Copy link

commented Nov 6, 2018

The struct embedding feels a lot like it's supposed to be generics. I realize that this isn't meant to be a generics proposal, but the only thing it's missing is embedding all builtin types to interfaces, in which case the proposal would make more sense to me than to only embed specific types.

type ConstByteSlice interface { []byte }

I'm assuming this is supposed to be an interface { const []byte }, right?

This ability to move back and forth permits adding "const-qualification" on a middle-out basis, without requiring it to be done entirely bottom-up.

I really like this approach to const types. I think some big concerns to this approach would be that all const types would be wrapped in interface, and it requires quite a bit of boilerplate code in order to make a const type. It would be extremely useful for something like the bytes package, though.

Also, since both maps and slices are allowed to be embedded, would an interface { const map[int]string } be the same as interface { const []string } since they would both have the method call [int] string? If I understand this correctly, map values aren't addressable, but it looks like neither is an interface { const []string }.

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor Author

commented Nov 6, 2018

type ConstByteSlice interface { []byte }

I'm assuming this is supposed to be an interface { const []byte }, right?

Right, fixed, thanks.

Also, since both maps and slices are allowed to be embedded, would an interface { const map[int]string } be the same as interface { const []string } since they would both have the method call [int] string?

They would differ at least in that interface { const []string } would support &is[i] but the map interface would not.

Even if we permitted embedding all builtin types, which we could, this would not be generics because there would be no way to express relationships between types. For example, in Accumulate([]T, func(T, T) T) T there would be no way to describe the relationship between the []T and the plain T.

@deanveloper

This comment has been minimized.

Copy link

commented Nov 6, 2018

They would differ at least in that interface { const []string } would support &is[i] but the map interface would not.

I added this in an edit but it didn't look like I got it in, but it didn't look like the values of interface { const []string } were addressable which was why I was asking. I don't think it's a big deal or anything, mainly just affirming I understand the proposal

Even if we permitted embedding all builtin types, which we could, this would not be generics because there would be no way to express relationships between types. For example, in Accumulate([]T, func(T, T) T) T there would be no way to describe the relationship between the []T and the plain T.

I completely forgot about parametric types, which is like 90% of the reason to want generics haha, my bad.

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor Author

commented Nov 6, 2018

Interesting point, you're right, there may not be a difference between interface { map[int]string } and interface { const []string }.

@deanveloper

This comment has been minimized.

Copy link

commented Nov 6, 2018

Continuing to think about it, this may cause problems. Both are len-able, but the lengths mean different things so you may run into the following issue -

func CustomPrint(s interface { const []byte }) {
	fmt.Println("Printing out our %T\n", s)

	fmt.Print("[")
	for i := 0; i < len(s); i++ {
		fmt.Printf("%d", s[i])
		if i < len(s) - 1 {
			fmt.Print(", ")
		}
	}
	fmt.Print("]")
}

func main() {
	CustomPrint([]byte { 5, 10, 15, 20 })
	// Output:
	// Printing out our []byte
	// [5,10,15,20]
	
	CustomPrint(map[int]byte {
		6:	5,
		7:	10,
		8: 	15,
		10:	20,
	})
	// Output:
	// Printing out our map[int]byte
	// <runtime panic>
}

Perhaps this may just be a "do stupid things, get stupid results", but I'm not sure if passing a map[int]byte into an interface { const []byte } is stupid or not

@martisch

This comment has been minimized.

Copy link
Member

commented Nov 6, 2018

Interesting point, you're right, there may not be a difference between interface { map[int]string } and interface { const []string }.

depending on the methods exposed I think there would be differences as "interface" maps likely have:

  • lookup(key int) (val, ok)
  • delete(key int)
  • no cap
@deanveloper

This comment has been minimized.

Copy link

commented Nov 6, 2018

no cap

I think this is actually they key difference that fixes #28608 (comment). If interface { map[int]string } is not assignable to interface { const []string }, (since []string can be cap'd but map[int]string can't) then the issue I raised is mitigated.

@martisch

This comment has been minimized.

Copy link
Member

commented Nov 6, 2018

no cap

I think this is actually they key difference that fixes #28608 (comment). If interface { map[int]string } is not assignable to interface { const []string }, (since []string can be cap'd but map[int]string can't) then the issue I raised is mitigated.

Guess this will make my not submitted draft proposal how cap can be defined and implement for maps get another blocker 😄

@alanfo

This comment has been minimized.

Copy link

commented Nov 8, 2018

Although I applaud @ianlancetaylor for trying to think 'out of the box' with this proposal, there are two aspects of it which worry me:-

  1. Embedding structs, slices etc. in interfaces will inevitably appear to be muddying the distinction between abstract and concrete types and between methods and fields. The underlying reality may be different but I think it will still look that way to many people.

  2. I'm not sure whether the main aim of the proposal - to provide an indirect way of enabling 'const' function parameters of aggregate types - is a worthwhile one in the first place. If there is no guarantee that the aggregate type won't be mutated by the function, it could be argued that people might just as well rely on the documentation to check this rather than complicate the language itself with such concerns.

@deanveloper

This comment has been minimized.

Copy link

commented Nov 8, 2018

Related - #23796

Here's a summary of the critiques from that proposal -

  • It hides the fact that interfaces are abstract structures
  • It seems like the main purpose is to be syntactic sugar for getters and setters, perhaps we should instead address that issue directly
  • Interfaces should describe behavior, not state
  • There seems to be few real-world examples where this is applicable

My personal critiques, though, don't have too much to do with what's above.

It seems like the problem that the first half of this proposal solves seems it could be alternatively solved by the contracts draft, assuming that (or something similar) gets accepted.

I'm personally okay with interfaces describing state, that's not my issue. I personally see interfaces more as pattern-matchers than behavior-describers. I personally think that contracts and interfaces should be unified (proposal), they are non-orthogonal structures. The first half of this proposal would just make it so contracts and interfaces would be even less orthogonal to each other.

I really like the idea of how const-types would work under this proposal, though. If, on the other hand, we had generics without contracts, I'd actually really like this proposal. I really just don't want to have multiple solutions to the same problem, as it increases the learning-curve for the language.

@networkimprov

This comment has been minimized.

Copy link

commented Nov 8, 2018

@ianlancetaylor I suggested limited-scope immutability here: romshark/Go-1-2-Proposal---Immutability#23. That repo contains the design doc for the const qualifier proposed by @romshark in #27975.

I believe actual immutability should be the priority, if it can be achieved in a way that doesn't break existing programs, or complicate the language. Simple const qualification allows mistakenly-not-const data to be modified accidentally, causing subtle bugs.

@carlmjohnson

This comment has been minimized.

Copy link
Contributor

commented Nov 13, 2018

ISTM that the problem of const-poisoning is created by treating const-ness as a general purpose type qualifier, when really it should only be a qualifier on function parameters. It doesn't make sense to say, e.g. func f(a const []byte) const []byte because once the slice is returned, it's no business of the function whether the slice is mutated or not. I'd like to see that as just a standalone proposal.

As for getters and setters, perhaps there could be some keyword like

type T struct {
    A string // no Get/Set methods
    export b string // T gets automagical GetB() string and SetB(string) methods 
}

That makes it easy to start with a simple getter/setter and then replace it with a more complicated one when you need it.

@oec

This comment has been minimized.

Copy link

commented Nov 30, 2018

This is, essentially, the ability to say "this function does not modify this aggregate value by accident (though it may modify it on purpose)." This is similar to the C/C++ const qualifier, but expressed as an interface type rather than as a type qualifier.

If I understand correctly, the proposal seems to introduce significant changes in the type-system just to convey a simple idea that should be expressed in the signature of a function.

Couldn't we "just" borrow the rules for https://golang.org/ref/spec#Exported_identifiers to apply to functions in a similar way: parameter names in the signature starting with capital letters are to be considered non-const? F.e. func fn(a map[T]S) could not alter a, but func fn(A map[T]S) could alter A.

Even though this would break basically all existing programs, it would be trivial to fix with go fix and the solution doesn't add a keyword, but extends an existing convention. (edit: correction: constwouldn't be an introduction of a new keyword)

@romshark

This comment has been minimized.

Copy link

commented Nov 30, 2018

@oec what do you do with mixed-mutability types then?

I've discussed this issue in #27975 a lot. You do not want to make immutability a property of symbols (such as a variable or an argument) because this will introduce transitive immutability, which means that you can't have, say, an immutable slice of mutable objects: immut [] mut T. Mixed-mutability may be relatively rare, but it's one of the cases when we really need the help of the compiler, but we'll throw away the concept of immutability in cases like this entirely because it doesn't allow us to achieve what we'd like to, which makes it rather useless!

@oec

This comment has been minimized.

Copy link

commented Nov 30, 2018

@romshark I agree with you on the problems you point out regarding immutability. My suggestion is not an attempt to implement immutability of types.

Instead, my question is if the main goal of the current proposal - IIUC: ability to say "this function does not modify this aggregate value by accident..." - couldn't be achieved by extension of an existing convention, rather than by introduction of a keyword and changes to the type-system.
(edit: correction: constwouldn't be an introduction of a new keyword)

But I suppose that if immutability is going to be introduced thoroughly in the type system like you suggest in #27975, this proposal can be closed anyways.

@romshark

This comment has been minimized.

Copy link

commented Nov 30, 2018

@oec I see the point, but I think it's better left out entirely if it can't be solved properly.

I think we all agree that we don't want semi-useful language features because they'd only pollute the language with tons of exceptions and make it unnecessarily complicated.

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor Author

commented Nov 30, 2018

It's not clear to me that it's all that useful in practice to have an immutable slice of mutable objects. Sure, it's a meaningful concept, and once in a while it comes up, but I suspect that programming would not be made significantly more difficult if there were no way to describe such a thing. Transitive immutability seems more common and easier to understand.

@romshark

This comment has been minimized.

Copy link

commented Nov 30, 2018

@ianlancetaylor Rephrasing the popular quote: 95% of the time transitive immutability is enough - yet we should not pass up our opportunities in that critical 5%.

I'm proposing immutability qualification propagation to achieve this goal:

/* transitive immutability */

// immutable matrix of immutable pointers to immutable T's
func f(a immut [][]*T) {}

/* mixed mutability */

// immutable matrix of immutable pointers to mutable T's
func f(a immut [][]* mut T) {}

// mutable matrix of immutable pointers to immutable T's
func f(a [][] immut *T) {}

This way we can cover 100% just fine, because the qualifier propagates until it's canceled out so the first one looks & feels transitive while the later are more specific but still allow us to use the safety features when facing that critical 5% of cases.

@deanveloper

This comment has been minimized.

Copy link

commented Nov 30, 2018

I personally think that forcing immutability in the type system is a bad idea. You run into a problem with something like bytes.Split, which has the function signature func Split(s, sep []byte) [][]byte.

At first you might be naive and say "well, it doesn't modify the bytes, so we can make it read-only!" So you do that, the signature is now func Split(s, sep immut []byte) [][]byte. Now the issue becomes, s is an immut []byte, which means we should be returning an immut [][]byte. BUT, if we pass a normal []byte into Split, we would want to have a [][]byte returned, not an immut [][]byte.

Example:

func Split(s, sep immut []byte) immut [][]byte { ... }

func main() {
    var someBytes = []byte{1, 2, 6, 3}
    someBytes = Split(someBytes, []byte{2})[0] // compile error, cannot assign immut []byte to []byte
}

(Note, this proposal suffers from the same issue, except it allows conversion from immutability to mutability, so it's not quite as bad)

@jimmyfrasche

This comment has been minimized.

Copy link
Member

commented Nov 30, 2018

@deanveloper with the contracts pre-proposal you could write

func Split(T C)(s T, sep immut []byte) T

where C is a contract that accepts either []byte or immut []byte.

@deanveloper

This comment has been minimized.

Copy link

commented Nov 30, 2018

@jimmyfrasche That's a good point, I was thinking about current Go. Parametric-typed functions would fix this issue.

@romshark

This comment has been minimized.

Copy link

commented Nov 30, 2018

@deanveloper we already discussed const poisoning before. One possible solution was previously proposed by Jonathan Amsterdam in #22876, let's call it "immutability genericity":

func Split(s, sep mut? []byte) (r mut? [][]byte) { ... }

The ? specifies undetermined, generic qualifiers.

  • both s and sep can thus be any of:
    • []byte
    • immut []byte
    • [] immut byte
    • immut [] mut byte

...because mut? []byte essentially stands for: mut? [] mut? byte

  • the returned r will become any of
    • [][]byte
    • immut [][]byte
    • [] immut []byte
    • [][] immut byte
    • immut [][] mut byte
    • and any other possible combination...

...depending on the type it's written to:

var r immut [][]byte
var s []byte
r = Split(s, []byte(","))

In case the receiver type for r is not specified the default qualifier is used:

func Split(...) (r mut? [][]byte) {...}
func main() {
  r := Split(...) // r is of type [][]byte
}

or:

func Split(...) (r immut? [][]byte) {...}
func main() {
  r := Split(...) // r is of type immut [][]byte
}

We cannot however mutate an undetermined type because it'd need to be a determined mutable one instead:

func Split(s, sep mut? []byte) (r mut? [][]byte) {
  s[0] = 2  // Compile-time error, illegal mutation
  sep = nil // Compile-time error, illegal mutation
}

I haven't yet thought it through entirely so it's not yet documented anywhere but here, but this is the most likely one for the upcoming second revision of my proposal.

Some form of generics is another way, but that's still unclear so I tend to not rely on it too much

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.