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: new type: integer range constraint #29649

Closed
viper10652 opened this issue Jan 10, 2019 · 23 comments
Closed

proposal: Go 2: new type: integer range constraint #29649

viper10652 opened this issue Jan 10, 2019 · 23 comments
Labels
FrozenDueToAge LanguageChange Proposal v2 A language change or incompatible library change
Milestone

Comments

@viper10652
Copy link

Context:
When certain data types are known to only have a limited set of values, then it is only possible to test for these dynamically in the current Go version.
It should be possible for incompatible types to be tested statically at runtime.

Proposal:

I can think of two ways to specify a constraint on the possible values of an integer type:

  1. as an enumeration (has been proposed in other proposals, won't repeat here)
  2. as a range

E.g.
type MONTHS range 1 ... 12
type DAYSOFMONTH range 1 ... 31
subtype DAYS_OF_FEBR of DAYSOFMONTH range 1 ... 28
subtype DAYS_OF_LEAP_FEBR of DAYSOFMONTH range 1 ... 29

when I receive a value of type DAYSOFMONTH
then I would like to test if it is valid for a subtype.
E.g.
var birthday DAYSOFMONTH
birthday := 14
if birthday in DAYS_OF_LEAP_FEBR { ... }

This concept exists in the Ada programming language.

There needs to be a conversion capability to convert non-constrained integer types to and from constrained integer types (range or enumeration).
This is useful when decoding and encoding between binary data received over a communication link and logical data.

E.g.
var b1 int
var b2 int
var f DAYSOFMONTH

b1 := 14
f := b1 // potential out-of-range
b2 := f // should be safe

conversion from constrained types to unconstrained should not be a problem
conversion from unconstrained types to constrained can result in an error.
Assignments that can cause an out-of-range condition need to be accompanied with an error assignment. The compiler can enforce the use
E.g.
var err error
f, err := b1 // when out-of-range, f is assigned Nil

@gopherbot gopherbot added this to the Proposal milestone Jan 10, 2019
@CAFxX
Copy link
Contributor

CAFxX commented Jan 10, 2019

While I like the idea, I think you could make a much stronger case by staying completely clear of dates/times in your examples.

@mvdan mvdan added LanguageChange v2 A language change or incompatible library change labels Jan 10, 2019
@mvdan
Copy link
Member

mvdan commented Jan 10, 2019

Also note that the compiler now has a "prove" pass that can keep track of the numeric ranges of integers. For example:

func Foo(s []byte) {
    if len(s) < 10 {
        _ = s[4] // no bounds check
    }
}

So I wonder - would this actually help in that many situations?

There are also languages like wuffs, which specialise in these kinds of static checks. It must statically prove that integer and buffer overflows are impossible, for example. And in the future it will support generating Go code, too.

@jimmyfrasche
Copy link
Member

I brought up similar idea in #19814 (comment) (toward bottom of comment).

@ianlancetaylor ianlancetaylor changed the title proposal: integer range constraint proposal: Go 2: new type: integer range constraint Jan 11, 2019
@networkimprov
Copy link

See also my comment here: #28987 (comment)

Which probably should be a separate value constraints proposal. Note its use of type aliases and values already defined in existing code...

@bcmills
Copy link
Contributor

bcmills commented Jan 11, 2019

This proposal is missing an essential detail: what happens to ranged integers if they overflow the declared range? (When, if ever, are those overflows checked?)

@josharian
Copy link
Contributor

This has been discussed a bit at
#19814 (comment) and surrounding comments. (Note that that is a very long thread, which GitHub has auto-collapsed, and frustratingly when you link into the middle of a collapsed thread, GitHub does not auto-expand it for you. So you'll have to manually expand the comments. Search in the page for uint12. Sorry about that.)

@beoran
Copy link

beoran commented Jan 15, 2019

Ranged numbers are a great feature also found in Pascal and Ada, which help programming more safely. The Go compiler already has a range check for arrays, and this could be used to prove at compile time that a variable's value stays within range.

The month example given is not so compelling, but I know a few life critical systems where range checked numbers would help immensely.

If the compile cannot statically determine that a value stays within range then a result, ok or result ,err should be mandatory for the expression in question so a run time check can be introduced. Or, a panic might be raised as it is today for array indices.

@ianlancetaylor
Copy link
Contributor

I note that the proposal mentions subtype, but there is no such explicit concept or keyword in Go.

What problem is this solving?

What happens when adding two values of the same range type? If the sum is outside the range, does the program panic?

What about multiplication between two values of the same range type? What about multiplication by an untyped constant?

type R range 3 ... 7
func F() {
    // What happens with the final i++ here?  When it goes to 8, do we panic?
    for i = R(3); i <= 7;  i++ {
        // do something
    }
}

@griesemer
Copy link
Contributor

Along the same lines of what @ianlancetaylor already mentioned: Integer range types such as you propose and which were popular in languages such as Ada and Pascal were not picked up in successor languages. There are reasons for that. In fact, successful programming paradigms tend to get copied enthusiastically by newer languages, exactly because they do solve a problem and make programming simpler or better in some important way. One of the key criteria when we designed Go was not to include known language features that didn't pass the test of time.

It turns out that integer range types, while they sound really nice in theory, tend to make programming harder. As somebody who has programmed several years in Pascal, I can attest that problems such as the for-loop question above do occur. There are various solutions around the problem, and one of them is for the compiler to not check the range (which is what the Pascal compiler I was using did); of course that defeats the purpose. Then there are all the questions about (mathematical) closed-ness of the type regarding operations (what happens when I multiply elements of a range integer, etc.). Such operations are at best ad-hoc defined and ranges may not be enforced by the compiler (because it's too expensive). And if the ranges are enforced, people won't use those types because they are too expensive - they just use integers.

Even in existing Go, we find that it's often better in APIs to stick to int rather than uint (even though we know a value cannot be negative) because it makes interaction with existing code much simpler and doesn't require conversions.

I summary, I am not in favor of this idea.

@beoran
Copy link

beoran commented Jan 16, 2019

About successor languages, far as I know Modula-2 Modula-3, and Delphi also have ranged types, Oberon does not include them but has a SET type in Oberon 2 which is quite similar except that the lower bound is always 0. So I disagree that this feature was not widely copied in successor languages.

I agree that range types are pointless if the range is not checked. Which is why, like in ADA, range types should be range checked on every operation, and either panic with a recoverable panic at run time, or give an error at compile time if the compiler can statically check that the value will be out of range. An extra result, ok := form on any operations involving ranged types could also be handy.

The argument that range checked numbers will not be used because it is too expensive is true for Pascal, certaly FreePascal where you have to explicitly turn it on with the {$R+} compiler instruction. But it is not true for Go, where we already have mandatory array index range checking and have a whole mechanism to make the compiler omit the checks if possible, thus limiting the performance impact. This feature would be very similar to array indices. Range checking on array indices is one of the features that makes Go a safer language than C or FreePasal. I feel that ranged numbers would likewise help Go to become an even a safer language.

To solve the for loop problem, I propose that for a type Foo range(A..B) the range keyword could be extended like this: for i:= range Foo, or for i := range range(A..B), and then the loop will iterate from A to B inclusive, where range checks can be omitted because now i is guaranteed to be in range unless operated on in the loop.

As for what the use case of this feature is, this would be for making Go more suitable for implementing software where safety is more important than interoperability. For such programs it is often crucial that certain variables can have only certain values that are within operational range.

@ianlancetaylor
Copy link
Contributor

As for what the use case of this feature is, this would be for making Go more suitable for implementing software where safety is more important than interoperability. For such programs it is often crucial that certain variables can have only certain values that are within operational range.

This is a restriction expressed in the type system. Go intentionally has a weak type system, and there are many restrictions that can be expressed in other languages but cannot be expressed in Go. Go in general encourages programming by writing code rather than programming by writing types. Why does this restriction in particular carry enough benefit that it is worth adding to the language? What does it permit us to do that we cannot already do?

@griesemer
Copy link
Contributor

@beoran You are correct about Modula-2/3, I misremembered that they had subrange types; my apologies. What I meant about successor languages though was not limited to direct successors of a specific language, but any language defined later. It doesn't seem like a feature that has gained wide-spread adoption.

Regarding your argument that such a range feature would make the language more safe: I am not convinced. With regard to array indices, there's no substantial benefit; that one can specify the lower bound to be non-0 is not really a big deal (in fact it makes using such arrays more cumbersome). With regard to integer subranges, yes, a program might panic because a result is out of range (assuming the compiler generates the necessary checks). But if that panic is not suitably handled, the program is not necessarily more safe, it simply won't work (which may be worse or better, depending on the situation). It would be a different story if the compiler could statically detect that results are always within range. It might able to do that in many cases, but it's not possible to do this in all cases.

@beoran
Copy link

beoran commented Jan 17, 2019

@ianlancetaylor True, go language has few type system level restrictions. And, yes, some more manual work, I can define Range and Ranged types in Go as it is now and have range checked values at run time the at the overhead cost of a single pointer per Ranged value. Here is how I did it: https://play.golang.org/p/c7Y0tJreYdB

@griesemer Well, I consider the argument of popularity of a feature to be not very relevant anyway. For example, Go has built in support for couroutines/goroutines which is rarely found in any popular language apart from Erlang. Popularity is less important than the benefit versus cost argument, which I fully support.

When a new Go language feature is requested then often I will oppose the proposal here if I feel the costs outweigh the benefits. However, for this feature, I feel the costs are likely to be low because the go compiler already does a form of range checking. And as for the benefits, what I see as the crucial benefit of this feature over implementing a ranged type in Go manually, is that the compiler should perform range checks at run time as much as is possible. Sure, it is not possible to do this at all times, but it seems to be the "Nirvana Fallacy" to insist that the compiler must always be able to do so.

@ianlancetaylor
Copy link
Contributor

Note that the cost of a feature is not the cost of implementing it, which is generally inconsequential (or, for some requested features, impossible), but the cost of forcing everybody who learns the language to learn about the feature.

@beoran
Copy link

beoran commented Jan 18, 2019

Well, the cost of implementation is also important, I think but I agree that the main cost is the complexity cost. However, I'd say that this feature is not very hard to learn about, and doesn't interfere very much with people who do not use it. The solution can be well understood, meeting point 2 and 3 of the Go language 2 criteria.

However, since, for the time being, it seems only 2 or 3 people are interested in this feature, I will concede that on that point this proposal doesn't meet criteria 1 "address an important issue for many people", so I will let it rest, unless later it turns out more people do become interested in this feature.

@beoran
Copy link

beoran commented Feb 21, 2019

I wrote a document with a proposal that unifies this idea and enumerations under a single concept of range types. See here for those interested: https://gist.github.com/beoran/83526ce0c1ff2971a9119d103822533a

@bradfitz
Copy link
Contributor

What is the zero value of the MONTHS type from:

type MONTHS range 1 ... 12

If I write:

var m MONTHS

What is m?

@ianlancetaylor
Copy link
Contributor

Above @beoran says we can let this proposal rest, so doing so. This seems related to enums, and perhaps can be merged into some enum proposal such as #28987.

@beoran
Copy link

beoran commented Feb 26, 2019

Good question. In my proposal the syntax would be type Months range int { January = 1 + iota, February, March, April, May, June, July, August, September, October, November, December}, so arguably the zero value should be that of the underlying type, int, 0. So the variable assignment is then a panic or A compilation error since the zero value, 0 is out of range for this range type.

Alternatively, perhaps more usefully the zero value could be the first value of an enumerated range, and the lower bound of a bounded range.

@beoran
Copy link

beoran commented Feb 26, 2019

@ianlancetaylor Maybe I should give my proposal that unifies ranges for enums and bounds a separate new thread?

@networkimprov
Copy link

@beoran there is already one proposal like that in the comments of #28987 (comment)

@beoran
Copy link

beoran commented Feb 26, 2019

Yes, but my probosal is more detailed and backwards compatible with Go1.

@ianlancetaylor
Copy link
Contributor

@beoran We are always happy to look at a good proposal.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge LanguageChange Proposal v2 A language change or incompatible library change
Projects
None yet
Development

No branches or pull requests