Hacker News Reader

Comment by captainmuon | Hacker News Reader

If I ever create a programming language, one thing I'd like to try is to promote integer operations to larger types, so there is never overflow. For example, if a and b are int16, then a+b is int17, and (a+b)/2 is int16 again.

In practice you'd store them in the next larger integer, so 32 bits for a 17 bit int. If you really want to cut off bits or overflow, you use a cast or modulo.

It seems really weird that the "correct" way to do this calculation is to resort to bit manipulation (which should be an implementation detail IMO).

View on HN

So, this is basically what dynamic languages do because they _can_ go back an allocate more memory transparently to the developer. However, static languages cannot change the size of the values dynamically at runtime without additional memory allocations. In fact, this would likely mean that all numbers must be heap allocated, which will likely be a performance penalty when working in high-performance systems. In these cases, using an algorithm that produces correct results without error with constant memory usage is preferred.

The result of any expression would still be assigned to a variable or function parameter that has a defined type, so it would be limited to that size. However, intermediate values could automatically use larger registers, the CPU's carry flag, or some other mechanism to expand the range.

It would be desirable that every expression either produces the mathematically correct result, or a runtime exception.

In many cases it would be easy for the compiler to limit intermediate results to some number of bits (since it knows the maximum allowed range for the final result), but it may be a problem to guarantee this.

This should be possible for static languages? Since the width of the operands are known ahead of time, a wider integer can be unconditionally reserved on the stack for the result of the operation.

I'm curious which dynamic language reallocates to store larger integers? All of the dynamic languages that I'm familiar with simply store numbers as doubles, with variable width integers being handled by opt-in types.

But if you do this in a static language you’d quickly run out of space anyway.

Say you start with two Int16’s. Any addition would result in an Int17. Adding a pair of those together would result in an Int18, and so forth.

You’d blow past Int64 in no time.

I'm pretty sure their intent was to demote the value back to an int16 after completing the midpoint operation.

> You’d blow past Int64 in no time.

Not really. You only need to preserve according to the msb of each number. If you are adding 0(Int18)+1(Int18), you don't need 1(Int36) anymore than you need 1(Int18) or even 1(Int1).

But you don't know the MSB at compile time in the general case.

> If you are adding 0(Int18)+1(Int18), you don't need 1(Int36)

No, you’d need an Int19. We were talking about statically typed languages, so you need to decide the type at compile-time. If you add two UInt16’s they could both contain up to 0xFFFF, you need 17 bits to store that answer. Basically, with every addition you need 1 more bit than the largest of the two (types, not values) you are adding together to prevent a potential overflow. It’s even worse for multiplication.

Couldn't you have a constraining operation in there to assert that you have enough bits? You are right that we don't know if `a + b` would need more bits than either a or b. However, we could have an assert that allows us to ensure the static constraints are satisfied. And the type system could be used as a place to know where we haven't checked the constraint.

(Note that I'm not too clear how valuable this would be. Just asking why that isn't a valid path.)

> No, you’d need an Int19.

No, that's completely false. You don't need an Int19 but an Int1.

How do you figure that you can store the result of adding 2 Int18s in an Int1 ? Remember, we’re talking about static types and you don’t know the values at compile time.

Python, common lisp, and perl for starters.

I didn't know python could do that, that's pretty cool.

I gotta disagree on perl, though, even though it can represent numbers outside of the range of a double, it can't manipulate them without converting them into doubles.

“use bignum;” and you can.

Also scheme and prolog

The problem you can then run into is that a mathematical operation can OOM

I've not seen this in practice.

You need some numeric accident involving a higher power operator like exponentiation.

In TXR Lisp I made exponentiation n-ary: you can do (expt x y z ...).

The associativity is right to left: it means

rather than the less useful cumulative exponentiation of the same base:

  yz...
 x

which can easily be obtained as (expt x (* y z ..)).

So, anyway, if you apply expt to small list of small operands, you can cons up a big number in rather a hurry.

If it is important to prevent a problem like this, a limit can be imposed on bignums (say, large enough for common cryptography to still work).

> Since the width of the operands are known ahead of time

Not so for loops and accumulator constructs.

I think it would be reasonable to also have overflowing and checked versions of the operators, for cases where the compiler can't guarantee the size (e.g. mutable variables in loops).

> Since the width of the operands are known ahead of time, a wider integer can be unconditionally reserved on the stack for the result of the operation.

What is the width of `i` in:

    foo(int count) {
      int i = 0;
      for (int j = 0; j < count; j++) {
        i = i + i;
      }
    }

You probably want i=1 since i=0 is an answer you can predict:

i = 0 implies that i = 0 + 0 = 0; so the loop doesn’t evolve, and the whole thing can be optimized to just i = 0.

For i=1, the loop simplifies to 2^count and a count-length type, which is the point I think you wanted.

Heh, oops, yes. :)

Static languages can have types which have an unboxed value part (of fixed size) that manages a boxed heap part.

  class bignum {
  private:
    digit_t *limbs;
  public:
    bignum(int val);
    ~bignum();
    bignum operator +(const bignum &rhs);
    ...
  };

Haskell is both compiled and has arbitrarily large integers. Granted, Haskell isn't used for high performance systems, but it can be used to generate programs for high performance systems.

> However, static languages cannot change the size of the values dynamically at runtime without additional memory allocations.

That is false; a static language could have bignum integers. E.g. you can easily have a bignum class in C++, which is static.

You can't have a variable-length bignum as an unboxed value type.

"Language with unboxed value types" and "statically typed language" are separate, somewhat related concepts.

They're right that this would require additional allocations though, no?

As you indicate though there's no need for this to be something the user of the type needs to think about.

You might not want that unconditional promotion in a systems programming language.

The problem in C that you can avoid is not taking into account the destination type of a calculation.

If you have in16 + int16, being assigned, returned or passed to a int32 type, then the calculation can be done in int32.

If the result is going back to an int16 type, then there is no need to go to int32.

In C expressions, the types are almost purely synthesized attributes: what that term means is that the information flows up the abstract syntax tree from the children to the parents. in a = b + c, the type of (b + c) is determined without regard for the parent = node. This is very simple and has the benefit of being not only easy to understand but in some ways referentially transparent: when we move (b + c) elsewhere, it retains its meaning (except for the part of what happens to the resulting value in the new context). More sophisticated rules can reduce errors though.

> If you have in16 + int16, being assigned, returned or passed to a int32 type, then the calculation can be done in int32.

By the way, if int has 16 bits (which is rare nowadays), then the calculation will happen in 16 bits. If int has more than 16 bits, then both operands will be promoted to that size before the operation.

The correct way most people would write this for positive integers is:

if (a < b)

  return a + (b - a) / 2;

else

  return b + (a - b) / 2;

This method is just more efficient (for places where it matters) as it avoids divisions and branches. But for a vast, vast majority of use-case that tiny efficiency gain doesn’t really matter.

Is that the right way around? If `a<b` then `a-b` will be negative, surely, and adding that to `a` will be moving down from `a`, not from `a` to `b`?

cf https://go.dev/play/p/SgdWzzqDygn

Eh, that’s what I get for writing code on a cell phone. Fixed.

It can be rewritten without the test:

    return a - (a - b) / 2;

Tweet said unsigned ints, so don’t think this would work. Even with signed I think this can overflow.

> Tweet said unsigned ints

Which tweet?

Wouldn't this still overflow when one of the values is positive, the other is negative, and their difference is sufficiently large?

The tweet said unsigned ints

Tweet? But yes, sorry, I missed that your post said positive ints. The article was about signed ints, though.

Oh, you are right. For some reason I thought I saw unsigned in there.

C promotion rules can can convert unsigned to signed and vice versa so it still matters.

you can also do

min(a,b) + (max(a,b) - min(a,b))>>1

It seems like if you did this you would need special syntax for accumulators and loops; there you cannot (necessarily) use static analysis to determine the proper types.

Amongst the many other dynamic languages that did this, Smalltalk was also one of them. Smalltalk took it a bit farther though. Python/Erlang will turn integer division (unbounded or optimized) into a floating point result.

Smalltalk had first class fraction objects as part of it's transcendental number system. There's a great story about Dan Ingalls changing one line of code to make all of the original Smalltalk BitBlt transparently work with fractions. I always miss having fractions as part of the transcendental math experience in "very high level languages".

The downside of these approaches, is that you can optimize some paths so that things stay relatively quick, but other paths will really slow down all of a sudden.

For example, in Smalltalk,

    16r7FFFFFFF timesRepeat: [ self fastOp ]

would allow you to do a microbenchmark on a fast operation. But if you moved to

    16r7FFFFFFF + 1 timesRepeat: [ self fastOp ]

would suddenly cause your benchmark to take 30x+ longer, because you had tripped from immediate tagged integer format to integer-as-an-object representation.

Python integer division (//) will always return an integer. Proper division of two integers with / will return a float, not an exact rational (except when the float can represent it).

In addition to what everyone else has said, that would presumably prevent you from writing statements like "a++" or "a += 1" - instead you'd have to write "a = (a + 1) as u8", which seems like it would get very tedious, even if it is much clearer that it could overflow.

In the proposed language (which isn't C!), that should produce an exception on overflow.

If you wanted it to wrap around, you could use an expression like "a = (a+1) % 256", or maybe something like Ada's modular types.

Swift (https://docs.swift.org/swift-book/LanguageGuide/AdvancedOper...) uses

  a = a &+ 1

or the shorthand

  a &+= 1

IMO, that looks ugly, but that probably is a matter of getting used to it.

Compared to the %256 option, it has the advantage that, if you change the type of a, you won’t have to remember to change the modulus.

They also chose to not make modular integers separate types. That makes mixing ‘normal’ and modular arithmetic on integers easier (with modular types, you’d have to convert between regular and modular integers all the time) (edit: that also is consistent with the fact that the bitwise operators work with regular ints, and ook not require a special “set of 8/16/32/…” type that’s implemented as an integer)

I wouldn’t know how common such mixing is and, hence, whether that is a good choice.

It wouldn't produce an exception, it would not compile. The nice thing is that you can avoid range checking at runtime.

Exactly, Ada's modular types would be a good option in this case, if that is what you want (my feeling is, most likely not unless you are doing some low level stuff). An alternative would be to rewrite the for loop in a functional or range based style.

In algorithmic code, you almost never want overflow. If you have a little function to calculate something, you want the intermediate variables to be big enough to perform the calculation, and in the end you cast it down to the size needed (maybe the compiler can do it, but maybe you know from some mathematical principles that the number is in a certain range and do it manually). In any case, I would want to be warned by the compiler if I am:

1. loosing precision

2. performing a wrong calculation (overflowing)

3. accidentially loosing performance (using bignums when avoidable)

1 and 2 can happen in C if you are not careful. 3 could theoretically happen in Python I guess, but it handles the transition int <-> bignum transparently good enough so it was never an issue for me.

> It wouldn't produce an exception, it would not compile. The nice thing is that you can avoid range checking at runtime.

You're proposing a language where you cannot increment integers? I don't think that would be a very popular language.

You could increment integers so long as you make it clear what you will do in the overflow case. Either use bigints with no overflow, specify that you do in fact want modular behavior, or specify what you want to do when your fixed width int overflows upon increment. That seems eminently sensible, instead of having overflow just sit around as a silent gotcha enabled by default everywhere.

Rust has a collection of wrapping functions to cover this case, e.g.

    a = b.wrapping_add(c);

I find this much clearer than any implicit or sigil-denoted behavior.

The amount of cryptography that relies on overflows is amazing and annoying when trying to implement it in a language/framework that doesn’t overflow.

The boost safe_numerics library (c++) has support for this (up to a point), in addition to detecting overflow at compile or run time.

> If I ever create a programming language, one thing I'd like to try is to promote integer operations to larger types, so there is never overflow.

Are there any languages other than Lisp and Python that have automatic bignum support?

Pike, Haskell.

Clojure makes a gesture toward it, literals are automatically promoted but the normal operators don't do it:

  user=> (+ 1 9223372036854775807) ;; max signed int64
  Execution error (ArithmeticException) at user/eval5 (REPL:1).
  integer overflow
  user=> (+ 1 9223372036854775808) ;; one higher

9223372036854775809N

Tcl. In tclsh:

  % expr 1 + 9223372036854775807
  9223372036854775808
  % expr 9223372036854775808 + 1
  9223372036854775809

Ruby's Integer type works like BigInteger under the hood.

Erlang's got them, I'm pretty sure.

Yep, integers on the BEAM are unbounded, since the language was built with "This program will run forever" as a design concern. Indices capping out and causing crashes was not an acceptable state of affairs.

Dart initially had it, but JS compatibility was more important.

However they don't have JS compatibility either (Dart does not round off large integers like JS does), so I forget what the point was.

Dart also (very early) had infinite precision fractions. So if you divided 355 by 113 you didn't get 3 or 3.1415... you got the fraction 355/133 which was an instance of a first class numeric type.

Unfortunately this means your numbers can grow to need arbitrary amounts of storage in loops.

Commonlisp has rationals as well (355/133) though division doesn't generate them by default.

The issue with this type of promotion is that you usually want to preserve the type. Like if I add two int32s, I probably want an int32 as a result.

A cooler feature would be requiring the compiler to prove the addition wouldn’t overflow.

> A cooler feature would be requiring the compiler to prove the addition wouldn’t overflow.

Wuffs is specialized enough to do exactly that (https://github.com/google/wuffs).

Many dynamic languages (e.g. Python, Clojure) do some variation of promoting numbers to larger types, usually not in small increments (keeping track of how many bits the number is probably adds an unreasonable overhead) but in large increments and ultimately promoting to an arbitrary precision int, a rational, or a BigDecimal. The people I know who are messing around with 5-bit ints and other irregular types are doing it with FPGAs where it unambiguously saves resources as opposed to costing them.

You eventually need bigints for that, and thus trade off performance against the no-overflow guarantee.

What do you do when operating on the largest int type available?

Don't have a largest int type?!

We live in a universe where infinite computer memory is not (yet) possible. Your CPU registers can only be so big.

A smart compiler might recognize cases where a finite number of types suffice, and reject programs where no such bound can be deduced.

Maybe spit out a warning and use bignums? You are then supposed to explicitly narrow the type, or explicitly opt into using bignums.

What do you do when incrementing (or adding to) an integer in a loop? You’d need sophisticated analysis to determine that the overall sum will always fit into a specific type, or otherwise you’d end up with bigints all the time.

You wouldn't modify an integer in place. At least it wouldn't be idiomatic. Quite a few languages, especially functional, have that constraint. You can always do range-based-for:

    for i in [0, 100]:
        // i is known to be in [0, 100]
        // the argument is known to be in [0, 200]
        do_something(i*2)

If you really want unbounded growth, you need a bignum. If you want to be bounded in size but not in time, you have to specify overflow behavior. Something like (ugly pseudocode):

    integer[modulo 256] a = 0;
    while some_condition:
        a += 1

    integer[0, 1000] b = 0;
    while some_condition:
        guard if b < 999:
            // b is now in [0, 999]
            b += 1

The whole point is, forcing you to make your mind up about overflow behavior (and not just using int32 or int all the time and hoping i is going to be "small").

Yes. My point is, you’d need that ranged-based static analysis, and probably (judging from how interval arithmetic usually turns out) you’d need bigints much more frequently than they are currently used.

Isn't uint8 exactly what your 'integer[modulo 256]' is? And for unbounded you do need bignum and dynamic allocation so I'm not sure I see any benefits to explicitely fine-graining the range instead of using machine word at all times and bignums when needed

> Isn't uint8 exactly what your 'integer[modulo 256]' is

In c/c++ it is. Obviously some other languages would disagree.

I think a better example of what GP is thinking about is Rust's approach, where overflowing an u8 panics (in debug builds), but you can do x.wrapping_add(y), x.saturating_add(y), x.checked_add(y) etc., depending on what you want to happen when the operation overflows.

If you're expecting arithmetic to work not modularly, you do need to either verify that there can never be an overflow or use bignums. Otherwise you have a bug.

if you're going that far, why bother with a "next largest" that's more than 1 byte larger? If you're just using it for intermediate values, just uplift that int16 to an int24, or that int64 to an int72, they're only there for as long as the LHS/RHS needs to evaluate: they're not getting stored, no need to use double the memory allocation.

What type do I get if I'm multiply four int32s?

It should fit in 128 bits or in the range of [-2^128,2^128] (tiny bit narrower since max and min int32 are asymmetric). The question is what type do you want? Do you want the full result? Or do you want it to be modulo something? Or are you sure that the numbers are small, but just kept in int32 storage for some other reason?

The compiler could use static analysis to keep the size to a minimum, for example in this case:

    int32 a
    int32 b = 2
    var c = a * b

it would know that c just needs 33 bits.

How many bits is x/y?

Assuming x and y are 32-bit integers

33-bits? INT_MIN / -1 = INT_MAX + 1.

and what is 3int16? nint16? you want to have an own calculation system about sizes in your calculations? Either go straight just unbounded ints like some languages (e.g. Python) already do, or nothing.. and it comes with a cost.

Pascal does something like that.

But it only goes up to 64-bit, then you get overflow again

IIRC Dart 1 did this, and it was abandoned due to binary size issues.

Reply on news.ycombinator.com