11 ms·
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
by captainmuon 4y ago
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).
- dahfizz 4y agoWhat do you do when operating on the largest int type available?
- tromp 4y agoDon't have a largest int type?!
- captainmuon 4y agoMaybe spit out a warning and use bignums? You are then supposed to explicitly narrow the type, or explicitly opt into using bignums.
- layer8 4y agoWhat 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.
- captainmuon 4y agoYou 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 or 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").
- layer8 4y agoYes. 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.
- ithinkso 4y agoIsn'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
- wongarsu 4y ago> 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.
- jefftk 4y agoWhat type do I get if I'm multiply four int32s?
- captainmuon 4y agoIt 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.
- dragontamer 4y agoHow many bits is x/y? Assuming x and y are 32-bit integers
- messe 4y ago33-bits? INT_MIN / -1 = INT_MAX + 1.
- layer8 4y agoYou eventually need bigints for that, and thus trade off performance against the no-overflow guarantee.
- chewbacha 4y agoSo, 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.
- rep_lodsb 4y agoThe 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.
- webstrand 4y agoThis 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.
- Aaargh20318 4y agoBut 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.
- 4y ago
- ipsi 4y agoIn 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.
- rep_lodsb 4y agoIn 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.
- Someone 4y agoSwift (https://docs.swift.org/swift-book/LanguageGuide/AdvancedOperators.html# 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.
- captainmuon 4y agoIt 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.
- usefulcat 4y agoThe boost safe_numerics library (c++) has support for this (up to a point), in addition to detecting overflow at compile or run time.
- gumby 4y ago> 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?
- fulafel 4y agoPike, 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
- eesmith 4y agoTcl. In tclsh: % expr 1 + 9223372036854775807 9223372036854775808 % expr 9223372036854775808 + 1 9223372036854775809
- tudorpavel 4y agoRuby's Integer type works like BigInteger under the hood.
- arh68 4y agoErlang's got them, I'm pretty sure.
- OkayPhysicist 4y agoYep, 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.
- ErikCorry 4y agoDart 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.
- ardel95 4y agoThe 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.
- zimpenfish 4y agoIs 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 https://go.dev/play/p/SgdWzzqDygn
- ardel95 4y agoEh, that’s what I get for writing code on a cell phone. Fixed.
- glxxyz 4y agoIt can be rewritten without the test: return a - (a - b) / 2;
- Chinjut 4y agoWouldn't this still overflow when one of the values is positive, the other is negative, and their difference is sufficiently large?
- halpmeh 4y agoThe 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.
- Sesse__ 4y ago> 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 https://github.com/google/wuffs).
- HappySweeney 4y agoIIRC Dart 1 did this, and it was abandoned due to binary size issues.
- TheRealPomax 4y agoif 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.
- withinboredom 4y agoThe amount of cryptography that relies on overflows is amazing and annoying when trying to implement it in a language/framework that doesn’t overflow.
- andrewla 4y agoIt 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.
- PaulHoule 4y agoMany 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.
- travisgriggs 4y agoAmongst 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.
- mkl 4y agoPython 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).
- kazinator 4y agoYou 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.
- DerekL 4y ago> 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.
- benibela 4y agoPascal does something like that. But it only goes up to 64-bit, then you get overflow again
- throw827474737 4y agoand 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.