On Tuesday, 23 August 2016 at 20:40:06 UTC, Andrei Alexandrescu wrote:
> Currently checkedint (https://github.com/dlang/phobos/pull/4613) stands at 2432 lines and implements a variety of checking behaviors. At this point I just figured I can very easily add custom bounds, e.g. an int limited to 0 through 100 etc. It would take just a few lines because a lot of support is there (bounds hooks, custom min/max) anyway.
>
> However, I fear it might complicate definition and just be a bit much. Here's the design I'm thinking of. Current:
>
> struct Checkedint(T, Hook = Abort);
>
> Under consideration:
>
> struct Checkedint(T, Hook = Abort, T min = T.min, T max = T.max);
>
> It's easy to take the limits into account, but then there are a few messes to mind:
>
> * When assigning a Checked to another, should the limits be matched statically or checked dynamically?
>
> * When composing, do the limits compose meaningfully?
>
> * How to negotiate when both the user of Checked and the Hook need to customize the limits? (e.g. if you look at WithNaN it needs to reserve a special value, thus limiting the representable range).
>
> I think all of these questions have answers, but I wanted to gauge the interest in bounded checked integrals. Would the need for them justify additional complications in the definition?
>
>
> Andrei

It's just an abortion.

There is a C++ bounded::integer library by David Stone that looks much better than what you have here.  For a language that's claiming to be a better C++ and with better CT features, I would expect something more elegant and useful.  Besides, this only works with integers.  You've been bashing Go for lack of generics, so how about we see something that works with other types too, no?

Perl 6:

subset MyInt of Int where (4 < * < 123);

or for string,

subset MyStr of Str where (0 < *.chars < 100);

Just beautiful, and what you would expect from a language that's trying to be better than the past.

Update: I've taken a shot at adding bounds, see https://github.com/dlang/phobos/pull/4613/commits/bbdcea723e3dd98a979ae3f06a6786645647a778. Here are a few notes:

* The Hook API works nicely with built-in or custom hooks, so no change there was necessary.

* The constructor got quite a bit more complicated because it needs to evaluate statically the bounds, which in turn evaluate the constructor statically. My solution was to define minRep and maxRep as the built-in representations of the min and max, and use those inside the constructor.

* There's trouble about choosing between a conservative and a statically precise approach to bounds computation. The simplest example is computing -x where x has type Checked!int. The precise result type is Checked!(int, int.min + 1, int.max). (If x == int.min, attempting to evaluate -x aborts the program.) The precise type is technically correct, but I assume in practice it'll just create a lot of annoyance due to the fact that x and -x have "slightly" different types.

* It gets worse with binary operators. Implementing the precise limits is a mini-project of its own (akin to the VRP algorithms). Going conservative (as the current work does) is annoying in a different way - any binary operator loses the custom limits information that the user in all likelihood had carefully planted.

My decision following this experiment is to drop support for custom limits in Checked. The complexity/power balance is untenable.

However, the hooks should be reusable with a different artifact called e.g.:

struct Bounded(T, T min, T max, Hook);

That should do precise static bounds computation in all VRP glory and interact well with Checked so the two can be composed.


Andrei

Am Tue, 23 Aug 2016 16:40:06 -0400
schrieb Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org>:

> Currently checkedint (https://github.com/dlang/phobos/pull/4613) stands at 2432 lines and implements a variety of checking behaviors. At this point I just figured I can very easily add custom bounds, e.g. an int limited to 0 through 100 etc. It would take just a few lines because a lot of support is there (bounds hooks, custom min/max) anyway.

In Pascal/Delphi I used them often for day of the week,
percentages and anything else that is naturally bounded. I
guess as so often with "library features" it would depend on
some pull and push factors. "What module was it? What do I
have to set for 'Hook' again, so I can set 'min' and
'max'?" vs. "It's the proper type to use. It save me time here
by catching bugs."

> However, I fear it might complicate definition and just be a bit much. Here's the design I'm thinking of. Current:
> 
> struct Checkedint(T, Hook = Abort);
> 
> Under consideration:
> 
> struct Checkedint(T, Hook = Abort, T min = T.min, T max = T.max);
>
> It's easy to take the limits into account, but then there are a few messes to mind:
> 
> * When assigning a Checked to another, should the limits be matched statically or checked dynamically?

As for statically checking, "a = b" should work if b's range is included in a's range, just like we can assign a ubyte to a uint. Types with only a partial overlap should probably be dealt with at runtime the same way assignments of normal ints would be checked. As an upgrade to that one could also statically check if the ranges have no overlap at all.

> * When composing, do the limits compose meaningfully?

You mean like when one multiplies two Checkedints ?

> * How to negotiate when both the user of Checked and the Hook need to customize the limits? (e.g. if you look at WithNaN it needs to reserve a special value, thus limiting the representable range).
> 
> I think all of these questions have answers, but I wanted to gauge the interest in bounded checked integrals. Would the need for them justify additional complications in the definition?
> 
> 
> Andrei

I have no answer to that either. The following could make it more accessible, much like the two Exception constructors we have:

alias CheckedInt(T, T min, T max, Hook = Abort) =
      CheckedIntImpl!(T, Hook, min, max);
alias CheckedInt(T, Hook = Abort) =
      CheckedIntImpl!(T, Hook, T.min, T.max);

struct CheckedIntImpl(T, Hook = Abort, T min, T max);

-- 
Marco

On 08/29/2016 11:33 AM, Marco Leise wrote:
> The following could make it
> more accessible, much like the two Exception constructors we
> have:
>
> alias CheckedInt(T, T min, T max, Hook = Abort) =
>       CheckedIntImpl!(T, Hook, min, max);
> alias CheckedInt(T, Hook = Abort) =
>       CheckedIntImpl!(T, Hook, T.min, T.max);
>
> struct CheckedIntImpl(T, Hook = Abort, T min, T max);

Since then I've decided to confine static bounds computation to a separate type. Checked does naturally allow for hooks that impose dynamic bounds enforcement.

One interesting tidbit - I was looking at a bounded integer library for C++ and it looks like it didn't implement the most interesting parts - computing bounds for logical operations: https://bitbucket.org/davidstone/bounded_integer/src/cd25b513c508498e882acb6543db5e08999243fb/include/bounded/detail/arithmetic/bitwise_and.hpp?at=default&fileviewer=file-view-default


Andrei

On Tuesday, 23 August 2016 at 20:40:06 UTC, Andrei Alexandrescu wrote:
> When composing, do the limits compose meaningfully?

They should. Generally speaking, if that doesn't produce reasonable bounds (leaving aside rounding errors) at the end of the computation, it means that the logic of the computation itself is wrong.

Ordinary abstract numbers don't really have "minimum" and "maximum" values; any variable that requires them has some sort of implied unit which determines its bounds. Therefore, the bounds should follow the rules of dimensional analysis (https://en.wikipedia.org/wiki/Dimensional_analysis).

On Mon, 29 Aug 2016 18:20:05 +0000, tsbockman wrote:

> On Tuesday, 23 August 2016 at 20:40:06 UTC, Andrei Alexandrescu wrote:
>> When composing, do the limits compose meaningfully?
> 
> They should. Generally speaking, if that doesn't produce reasonable bounds (leaving aside rounding errors) at the end of the computation, it means that the logic of the computation itself is wrong.

The ranges expand very fast. Addition and subtraction double the range, multiplication squares it, exponentiation is n^^n. Larger bounds are usually not useful bounds.

On Tuesday, 30 August 2016 at 03:37:06 UTC, Chris Wright wrote:
> On Mon, 29 Aug 2016 18:20:05 +0000, tsbockman wrote:
>> They should. Generally speaking, if that doesn't produce reasonable bounds (leaving aside rounding errors) at the end of the computation, it means that the logic of the computation itself is wrong.
>
> The ranges expand very fast. Addition and subtraction double the range, multiplication squares it, exponentiation is n^^n. Larger bounds are usually not useful bounds.

Ranges don't always grow. Some operations will also cause them to shrink, if they're really being tracked correctly: bitwise AND, integer division, and modulus all tend to do so.

If the ranges are intrinsically significant (it's logically impossible for a creature to have -7 eyes) and the calculation is meaningful and correct, things should balance out at the end to produce a useful range for the final result.

On the other hand, arbitrary sanity check ranges (it's merely extremely unlikely for a creature to have 2147483647 eyes) shouldn't be passed on to intermediate values at all; they must be assigned manually based on human intuition, and this is only really worth doing for inputs and outputs. In such cases, the best return value for binary operations would be normal (conceptually) unbounded CheckedInt.

Give me mathematically correct bounds, or no bounds at all. Anything else will cause problems.

On 08/29/2016 11:37 PM, Chris Wright wrote:
> On Mon, 29 Aug 2016 18:20:05 +0000, tsbockman wrote:
>
>> On Tuesday, 23 August 2016 at 20:40:06 UTC, Andrei Alexandrescu wrote:
>>> When composing, do the limits compose meaningfully?
>>
>> They should. Generally speaking, if that doesn't produce reasonable
>> bounds (leaving aside rounding errors) at the end of the computation, it
>> means that the logic of the computation itself is wrong.
>
> The ranges expand very fast. Addition and subtraction double the range,
> multiplication squares it, exponentiation is n^^n. Larger bounds are
> usually not useful bounds.

Yah, was thinking of the same. So before long you run into the bounds, at which points it's all up to the checking policy. -- Andrei

On Tue, 30 Aug 2016 13:24:04 +0000, tsbockman wrote:
> On Tuesday, 30 August 2016 at 03:37:06 UTC, Chris Wright wrote:
>> On Mon, 29 Aug 2016 18:20:05 +0000, tsbockman wrote:
>>> They should. Generally speaking, if that doesn't produce reasonable bounds (leaving aside rounding errors) at the end of the computation, it means that the logic of the computation itself is wrong.
>>
>> The ranges expand very fast. Addition and subtraction double the range,
>> multiplication squares it, exponentiation is n^^n.
>> Larger bounds are usually not useful bounds.
> 
> Ranges don't always grow. Some operations will also cause them to shrink, if they're really being tracked correctly:

We can only track types, not values, and that strongly hampers our ability to reduce ranges. We can still do it sometimes, but no operation always reduces ranges (and every operation sometimes extends ranges).

> bitwise AND,

It tends to extend the lower bound. For instance:

Bounded!(int, -100, 5) a = -99, b = -32;
auto c = a & b;

Here, c has type Bounded!(int, -128, 5) and value -128.

Similarly, Bounded!(int, 7, 55) & Bounded!(int, 12, 64) yields Bounded!
(int, 0, 55).

And for an odd one, Bounded!(int, 50, 55) & Bounded!(int, 60, 62) yields Bounded!(int, 48, 54).

So bitwise AND *sometimes* reduces the range (in sometimes hard to predict ways), but it also sometimes extends it.

> integer division,

You can only reduce a range with integer division if the divisor's static range does not include the identity. For example (assuming the range is open on both ends):

Bounded!(int, 0, 100) a = 1, b = 100;
auto c = b / a;

c has type Bounded!(0, 100) and value 100.

On the other hand, it can sometimes reduce the range:

Bounded!(int, 4, 8) a = 4, b = 8;
auto c = b / a;

Here, c has type Bounded!(int, 1, 2) and value 2.

And sometimes it extends the range:

Bounded!(int, -1, 1) a = -1;
Bounded!(int, 0, 128) b = 128;
auto c = a / b;

Here, c has type Bounded!(int, -128, 128) and value -128.

> and modulus all tend to do so.

Modulus can result in a range larger than its operands':

Bounded!(int, 1, 2) a = 1, b = 2;
auto c = b % a;

Here, c has type Bounded!(int, 0, 2) and value 0.

On Tuesday, 30 August 2016 at 14:58:16 UTC, Chris Wright wrote:
> On Tue, 30 Aug 2016 13:24:04 +0000, tsbockman wrote:
>> Ranges don't always grow. Some operations will also cause them to shrink, if they're really being tracked correctly:
>
> We can only track types, not values, and that strongly hampers our ability to reduce ranges. We can still do it sometimes, but no operation always reduces ranges (and every operation sometimes extends ranges).

Then don't try to propagate the ranges at all.

Use regular `CheckedInt` as the return type for all of `BoundInt`'s non-assignment binary operations. Make the user explicitly label which variables should be checked against what ranges, instead of automatically inserting the usually-wrong guess that every intermediate value belongs in the same narrow range as the inputs. Otherwise, `BoundInt` will generate tons of spurious exceptions, particularly for multiplication.

Expressions that are complicated enough that custom range-based sanity checks need to be done inside of it, on rvalues, should probably be broken up into smaller pieces, anyway.