Signed Integers By Default
23 points by runxiyu
23 points by runxiyu
I am generally of the opinion that languages shouldn't do automatic type promotion and should default to signed integers. Multiplication should always have a result type that is double the width of the operands and should have explicit non-widening versions.
The thing I would like to see more of is Ada-style (Pascal-style?) explicit ranges. Unsigned integers are a special case of this that happens to be easy to represent. But if I know that I'm storing integers in the range [0,100], then I should be able to say that, not just say 'well, it fits in an 8-bit integer and I don't want negative values so I'll pick u8 as the type'. And I want to define wrapping or saturating behaviour, or operations that return larger ranges or require me to put the thing back in line. And the compiler should pick the narrowest machine type that can store the range I want.
Can you explain why you wouldn't want automatic widening in the following case?
let x: u8 = ...
let y: u64 = ...
x + y
I think x should be widened to u64 here without having to cast it.
Because consistency is really important for people being able to keep rules in their head and if I widen there then I have corner cases. If x is i8, I either don't widen (unless I want to introduce a complex set of integer promotion rules that lead to bugs), so now I have some heterogeneous types that support implicit widening but others that don't. Maybe it's okay to implicitly widen but not change sign, but generally my experience is that this is code where I really want the reviewer to think about the behaviour. Why am I adding a u8 to a u64 here? Why is x a u8, if it's being used in arithmetic with a u64?
In this small contrived example, it's obviously simpler than writing zero_extend<u64>(x) + y, but when I come to review it I can see that this is correct and I can ask 'why does x need extending? Is storing it as a u8 actually saving anything useful?', whereas with the code as you've written it there's some unstated design assumption that may or may not be sensible that isn't exposed.
If I had my way, the promotion rules would be signed can be widened into a larger signed, and an unsigned can be widened into a larger unsigned, but you should not be able to automagically widen an unsigned into a wider signed, nor a signed into a wider unsigned. That should require explicit coding.
Shortening is an issue (going from u64 to u32 or i62 to i32) and should also probably require explit code.
The thing I would like to see more of is Ada-style (Pascal-style?) explicit ranges.
Yeah, tho a modern programming language should do it better.
The problem with ranges of that era is they were fixed by the variable declaration. It was easy for intermediate results to bust out of the declared range, and it was inconvenient to relax the constraints within a procedure even if the final result was known a priori to be in range, or if the programmer wanted their own range error handling.
Nowadays it would be better to infer the ranges of intermediate values through arithmetic ops with some abstract interpretation, and allow normal range checks in if statements (etc) to narrow the types. Something like what ATS or refinement or liquid types do, tho I suspect there is a way to provide those kinds of features in a manner that’s more palatable to programmers who aren’t formal methods geeks. TypeScript’s flow-aware type narrowing is a step in the right direction.
What it should look like to the programmer is that arithmetic works in the same mathematically correct manner as bignums, but because the compiler knows the bounded range of all values, it can compile efficiently using fixed width numbers. And comparisons between numeric values should always return mathematically correct results for any pair of types: it isn’t even that hard to correctly compare (say) an f64 and an i64; if the programmer discovers that a correct comparison is too slow they can either use an explicit conversion to throw away some bits, or add a range check earlier to ensure (say) the i64 is within the 53 bit floating point integer range.
And range types eliminate the need for any special case bodges for integer literals: the type of a literal is simply the range covering exactly that value, and there’s no need to work out a more specific type later depending on its context.
Also worth noting sign extension as probably the strongest case against both automatic widening and promotion from unsigned to signed and vice versa.
It's extremely easy to introduce subtle bugs if you don't pay attention to the fact that e.g. 0x70 widens to 0x7770 as a signed byte, but 0x0070 as an unsigned one.
Um ... wouldn't 0x70 widen as 0x0070 regardless? 0x70 doesn't have the sign bit set. It's 0x80 that would sign extend into 0xFF80. From the number you used, I think you mixed octal with hexadecimal. It would be 070 that extends into 07770. I hate that C uses a leading '0' to mean octal.
C29 will let you use an 0o prefix to indicate octal. https://en.wikipedia.org/wiki/C29_(C_standard_revision)#Constants
That is very correct, I was getting my wires crossed when thinking up an example.
The fact that your example is wrong rather reinforces you point that this is confusing.
Does that mean the compiler should be smart enough to know the bounds of the value and error out on paths that are undefined/out of bounds?
Explicit ranges are exactly what I'd prefer too. However, I'm not sure what the correct run-time behavior on out-of-range should be, panic?
var i: int[0, 100]
i = 100
i++
I'd suggest it should produce the same compile-time error as:
var: i: int[0, 100]
i = 101
because this the same (potential) out-of-range assignment problem if you do abstract interpretation and track how the ranges flow through the code.
I think hwj is more interested in cases that aren't amenable to compile-time analysis, For example:
var i: int[0, 100]
i = 90
i += opaque_function_that_returns_an_int()
That problem does not exist under static bignum rules: All you need is correct type inference: The resulting type of each mathematical operation is exactly wide enough to represent all output values.
For addition:
int[A, B] + int[C, D] → int[A+C, B+D]
So that's an invalid program that shall not compile. Slap on the fingers! We get forced to either redeclare i to accept the widening…
var i: int[0, 100] = 90
var i = i + opaque_function_that_returns_an_int()
… or do a narrowing conversion. Note that we don't need a special narrowing conversion: Again, the result of each mathematical operation is exactly wide enough to represent all output values:
var i: int[0, 100] = 90
i = (i + opaque_function_that_returns_an_int()) % 101
That's what we have to do if we are summing unbounded input. Admittedly, the overflow detection is essentially manual:
var sum: usize = 0
var overflow: bool = false
while (…) {
var widesum = sum + opaque_function_that_returns_an_int()
sum = widesum % range(usize)
overflow |= widesum > sum
}
Except that should be solvable with a macro and a Result type. This way, all unavoidable overflow is explicit and must be handled. And we avoid the avoidable. We get a language that is safe yet panicfree.
Hrm, that's true. Does make me wonder how typing would work at some points, though. For instance, how would you type a non-wrapping/non-saturating sum()?
Reminds me of interval arithmetic, if anything, though I'm not familiar enough with the field to say to what extent the benefits/drawbacks transfer, if they do at all.
That's where I want to see explicit type-level choices for this. The valid options are:
i is 0.i is 100.i++ isn't defined but i + 1 evaluates to a union type of either int[0, 100] or OverflowError (which may also encapsulate the overflow in a type that is guaranteed to support be able to hold the result, such as a BigInt) and each addition must check this condition (or explicitly discard it).The last one is useful in some niche cases, but the choice of which to use should be part of the type.
How about having no default at all? In the easy case, when we specify the type, the notion of default does not make sense:
let x : i32 = 42
let y : u32 = 24
Okay, I lied: what is the type of 42 and 24 here? In most languages they’d be something like i32 or u32, or maybe the widest type possible, but still something by default, and then converted to the declared type. One simple way to avoid that is to mandate annotations:
let x : i32 = 42i
let y : u32 = 24u
And while we’re at it, we could avoid default sizes too:
let x : i32 = 42i32
let y : u32 = 24u32
Holly crap this is fucking ugly. But there’s another way: Haskell’s type classes. The idea’s simple: let numeric literals just be numbers (or floating point numbers if there’s a dot or an exponent), and infer what their actual type should be depending on context. For instance:
let x : i32 = 42 // 42 is inferred to be i32
let y : u32 = 24 // 24 is inferred to be u32
let z := 44 // z is a number
let t := x + z // t is inferred to be i32 (because of x)
let u := x + y // Type error, convert either x or y
I have implemented this for a scripting language aimed at controlling a test environment for programmable logic controllers. The users were not programmers by trade, and we were supposed to handle all the C numeric types. This inference was my solution: keep the strict typing discipline with no implicit conversion, without forcing the poor users to state the obvious all the time.
And, no default at all.
I think it worked out great, and the customer was reportedly happy about my scripting language, but I reckon I don’t actually know: this was a ship and forget project; for all I know there’s a whole team of Q/A folks out there wishing me eternal torment.
The idea’s simple: let numeric literals just be numbers (or floating point numbers if there’s a dot or an exponent), and infer what their actual type should be depending on context.
Go, Zig and WGSL do this as well (without using Haskell type classes).
42 has type AbstractInt, which only exists at compile time.In Go, “Numeric constants represent exact values of arbitrary precision and do not overflow.”
That does not seem to be correct: https://go.dev/play/p/gVagt7NGY-D
They seem to be using 512 bits. That's a lot of bits, but it's not arbitrary precision.
I'm quoting from the official language specification. https://go.dev/ref/spec#Constants
Later on in the spec, it says
Implementation restriction: Although numeric constants have arbitrary precision in the language, a compiler may implement them using an internal representation with limited precision. That said, every implementation must:
- Represent integer constants with at least 256 bits.
Well the official language spec seems to be rather misleading then. IMO we shouldn't uncritically cite specs if they make claims that don't hold up to scrutiny.
Though they do not overflow, that part is correct.
what is the type of 42 and 24 here? In most languages they’d be something like i32 or u32, or maybe the widest type possible, but still something by default, and then converted to the declared type.
Raw numeric literals don't need to have a type in this context and you don't need to do any promotions/demotions. The compiler can leave them as untyped AST nodes until they get compiled, and only compile them with a specific known type. It looks something like this:
# Good:
def compile_declaration(decl):
type = parse_type(decl.type)
value = compile_to_type(decl.val, type)
if value is None:
error(f"Can't compile {decl.val} to type {type}")
...
# Worse:
def compile_declaration(decl):
value = compile(decl.val)
needed_type = parse_type(decl.type)
actual_type = get_type(decl.val)
if can_convert(actual_type, needed_type):
error(f"Can't convert {actual_type} to {needed_type}")
value = convert(value, from=actual_type, to=needed_type)
...
You don't ever need to get the type of the integer literal in this example, you just need to have logic that knows how to handle an integer literal AST when compiling to a specific integer type. The only time when you would need to get the type of an integer literal is if your language supports type inference (e.g. foo := 123) or if you wanted to give a compiler error that explicitly tells you the type of a value when it has the wrong type (saying Expected a String, but got an Int as opposed to Expected a string, but got 123).
You can also apply the same principle to arithmetic operations, so for example, x : i32 = 1 + 2 will call compile_to_type(AST("1 + 2"), i32), which will call compile_to_type(AST("1"), i32) and compile_to_type(AST("2"), i32), threading the needed type through the compilation.
The only time when you would need to get the type of an integer literal is if your language supports type inference (e.g. foo := 123)
Yes, this is something I desire, in part to keep things orthogonal and unsurprising: rules that apply everywhere without exception. You would have noticed I showed this very example in my comment. I could disallow it for practical reasons, but it would feel incomplete.
or if you wanted to give a compiler error that explicitly tells you the type of a value when it has the wrong type
Good error messages are paramount, I would want that even if I didn’t want the other.
You can also apply the same principle to arithmetic operations
I actually did.
Why stop at signedness? Integers should be bignums by default, for much the same reason.
For that matter why stop at integers? Math should be rational by default. This one is very slightly harder to justify because sometimes one really does want IEEE 754 floating point numbers for a calculation, but note the word ‘default.’
I know that we’re all used to machine ints and floats now, so they do not seem surprising, but I suspect that for a layman it would be less surprising for computers not to have problems with negative, large or rational numbers.
Users also express surprise at out-of-memory errors, and bignums can allocate all over the place.
These are engineering tradeoffs. There's no perfect & affordable solution here.
I really like the Smalltalk / Lisp choice that integers are things that are stored inline in the pointer but automatically promote to BigInt on overflow. On a 64-bit machine, that typically gives you a 61-bit signed integer as the default type, which is big enough for most things, but which gracefully fails over to a slower path that doesn't lose information on overflow.
That's not appropriate for systems programming, where you need to be able to do arithmetic that definitely won't allocate memory, but for application programming it's almost always the right choice.
It is elegant.
For application programming my integers often end up in Postgres which has sized types too, and some correspondence between valid application state and serializable/persistable state can be good.
Also - does this trick work properly with CHERI/CHERIoT?
I suppose you can do similar tricks with float NaN values for a generic 64-bit numeric type…
I think signed by default is sensible.
In Odin I disallowed even [value information preserving implicit integer conversions], for many reasons, but a big one is that type information is lost even if the value is preserved.
What does type information being lost mean? I assume Odin is statically typed. So expressions have types that are known at compile time and cannot change. I think maybe the author means that it is difficult for the user to determine the type of an expression involving implicit integer conversions. Or maybe they mean that the types of subexpressions are "lost" in that they do not become the type of the expression.
The former can be solved by having simple rules for implicit integer conversions. The latter is a normal part of programming (any function call could have this property!).
One thing I did not see in this post was a justification of why signed/unsigned overflow and underflow do not trap. There was a jab at Rust changing its behavior between release and debug, but not a justification of why one behavior was better than the other. In general, I think wrapping should be an opt-in behavior for people who know what they're doing. If you agree with that, then the question is how should someone opt in, and what should happen if someone doesn't opt in. I think again, Rust has the right idea of a named "wrapping_add" function, e.g. Once these functions are in the language, we can call overflow/underflow when not using one of these functions an error. And then the only question is how to handle the error. I think trapping is the right idea in this case. I think it would be better to rely on the wider software system's ability to handle a trap, than the system's ability to handle essentially a random number plugged into some function or variable.
Odin has distinct types. This means i64 and int are distinct even if they might be the same size on the target platform, and do not implicit convert to one another But Odin allows the user to define distinct types too, e.g. My_Int :: distinct i32 where My_Int != i32.
The remark of "type information" being "lost" here is to make it clear that what people are implying is when they want to allow for implicit conversions, the types themselves are treated as not carrying any important information beyond the range of values they can hold. Allowing implicit conversions of that nature, does mean you lose information about the type (e.g. int being semantically different to i64, for example). The compiler may know all of the types, because it is a statically type and compiled language, but a language is for the programmer, and not solely the computer. It's a subtle point which usually has to be experience to understand it, especially in Odin.
n.b. `distinct types work extremely well in Odin because literals are "untyped" (technically a form of existential types), meaning they don't have a concrete type until they instantiated in use, preventing a slew of problems which would require implicit conversions others with "concretely typed" types.
Regarding overflow, Odin defines ALL integer arithmetic to be wrapping, 2's complement, arithmetic. And the behaviour is the same regardless of the optimization level (unlike some other contemporary languages). If you want to check for overflow manually, there are intrinsics for that.
Odin's wrapping behaviour (which is not opt-out-able) is a decision I made very early on and do not regret it one bit. But Odin makes this behaviour well defined, and extremely consistent throughout the languages too. Even in subtle places such as bit shifts. Odin's bit shifts are defined in such a way such that x << 2 is equivalent to doing (x << 1) << 1, meaning a shift acts akin to x * 2^n with wrapping behaviour. This removes the platform-specific behaviour of many languages, and allows for a lot of useful things because of the consistency.
There is one aspect of Odin which allows for user-definable behaviour: integer division by zero. Odin by default defines x/0 to be trapping, because that is what most people expect. However you can easily define it in multiple different ways:
trap: x/0 trapszero: x/0 == 0
all-bits: x/0 == ~T(0)
self: x/0 == x
Personally I am a fan of zero behaviour, which a lot of proofing languages do too. But the others exist too because certain platforms will do that naturally—e.g. all-bits is the behaviour on RISC-V processors. But we do still default to trap because people expect, even if I don't think it is necessarily the most pragmatic behaviour when dealing with computers.
Odin's wrapping behaviour (which is not opt-out-able) is a decision I made very early on and do not regret it one bit.
FWIW, in Rust we are also not regretting our choice to say that wrapping is a bug. Some people regret us not catching that bug by default in release builds, but having the checks on in debug builds means most of those bugs to get caught during testing (and of course bounds checks and general memory safety means that if the rare wrapping bug slips through, it's almost always not catastrophic).
Wrapping is so rarely what one actually wants that having to write x.wrapping_add(y) in those rare cases is entirely acceptable, and a useful explicit signal.
So, I find this a bit surprising that always-wrapping works so well for you. Do you have a theory why wrapping bugs are not a common problem in Odin, given that bug detection / analysis tools have no way to distinguish buggy accidental wrapping from intended wrapping?
Odin's bit shifts are defined in such a way such that x << 2 is equivalent to doing (x << 1) << 1, meaning a shift acts akin to x * 2^n with wrapping behaviour
Yeah that makes most sense numerically. In Rust unfortunately the default wrapping shifts don't do this, one has to call unbounded_shl to get this.
I agree. It does seem weird on first blush, but an array index is really an offset, not an absolute value. You have to look deeper into how it is used, not just what its valid values are.
An index being an offset is entirely subjective (assuming with "offset" you mean something in the range 0 .. N), and I suspect a relic from C and its descendants treating it that way. As a counter example, various languages such as Ruby allow for negative indexes to allow reverse indexing, e.g. [10, 20, 30][-2] in Ruby produces 20. While niche in their use, it can be quite nice at times as it removes the need for manually doing something like x[x.size - index].
Python does this too; best part is [-1] for last element specifically.
> test = [10, 20, 30]
> test[-1]
30
OCaml only has signed integers as built-in types (there are some libraries that add unsigned integers and operations on them, but they're rarely used).
This makes reviewing FFI code tricky, because you need to know the range of the C type at runtime to know whether you can store an unsigned C integer as a signed OCaml value.
Although having more than one signed type can also lead to bugs. Had code that worked fine on 32-bit and broke on 64-bit, because the C int type was used to store an OCaml int (whereas it should've been long and Long_val).
So for compatibility with C retaining unsigned types in the language might be useful, although as said elsewhere that is just a special case for specifying the range, and it'd be better if you could be more explicit about the range instead.
Java also only has signed integer, besides FFI concerns I remember it also makes modular arithmetic (and fields which use that e.g. cryptography) more complicated (modulo on negative numbers are inconsistent between languages, if shifts are arithmetic they’ll sign extend, etc…)
Not mine, just the first search result: https://gist.github.com/joezeng/d5d562ff34b390f20c22405b6bc9e99e
We should really minimize the amount of surprises. For me, Python is doing great here. The integers pretty much behave exactly as I expect, in the mathematical sense. Fractions, not so much. Does anybody know if there is something better than ieee754?
Does anybody know if there is something better than ieee754?
We could maybe have arbitrary precision rationals? But those are likely to be real slow, maybe even memory hungry: the terms of a fraction can grow arbitrarily large even if the value of the division does not.
The numeric results however should be perfectly unsurprising.