3 ms·

> I don't think you usually want "integers" for most computer work and are better off thinking in terms of finite fields instead of numbers whenever possible I

> I don't think you usually want "integers" for most computer work and are better off thinking in terms of finite fields instead of numbers whenever possible I think it is the other way around, and that's why high level languages (under some definition of HLL) tend to have arbitrary precision integers. Python, Ruby, Lisp, and now Javascript (bigint) all have them. Finite fields are almost never used except in some special applications like cryptography or error correcting codes. Multiplication in the field with 2**32 elements doesn't look anything like integer multiplication. Normal computer arithmetic is not finite field arithmetic. We really should be using trap-on-overflow in C most of the time. Making that difficult on RISC-V seems to me like a poor design decision.

saurik 5y ago
Yeah... I absolutely appreciate my belief is controversial "at best" ;P, but I stand by it, and even (personally) consider this one of the defining characteristics of someone who truly "understands" and thinks fluently and natively in the mental model of practical computation vs. someone who would prefer to translate from their real-world experience into the inherently-finite world of machines. That said, I certainly agree that if you are working with an actual unbounded numerical value you should be using a data structure that at least attempts to simulate an unbounded numerical value; but, what people always insist on instead is to continue using their fixed integer types which they want to magically have compatible semantics with unbounded integers... a fiction they insist the compilers and even CPUs join them in crafting, with things like the "trap-on-overflow" feature you are advocating for :/. The result of this is that, rather than accepting types like "uint64" are finite fields that should have perfectly regular overflow, and inverse semantics that under no circumstances, should be "messed with" by the environment, and that they should be using "BigInt" for any actual numbers that occasionally come up, people keep ruining the finite field types by trying and, in the end, failing to add a bunch of weird optimizations and overflow trap semantics to their operation... mitigations that only cause further errors later: these types should have the most brutal possible interpretation of finite field math, and anyone who wants an actual number--maybe to represent a physical or monetary quantity should be forced to not consider them an option. Meanwhile, languages should do anything and everything possible to not pessimize the syntax of types like BigInt by providing a short name for a good implementation of the type along with operator overloading that prevents anyone from ever considering the usage of a type like C's "int" to represent a number merely because it is easier or looks better or feels natural: you fix this issue, and "trap on overflow"--a ridiculous semantic that makes software look like it works until you push it a bit, and in a way that fails to be fungible with (and accepting the same solutions as) running out of memory--becomes a feature that has no legitimate usage.
- throwaway81523 5y ago
  uint64 is not a finite field type. For example, the number 2 has no multiplicative inverse mod 2**64. Ok I guess I understand what you meant, it's just that the mathematical concept of a finite field means something completely different than that. The integers mod 2**64 are a ring even though not a field, if that helps. But I'll stop quibbling over terminology. We do in fact normally use integer datatypes to represent integers rather than elements of a cyclic group. For example, we expect n+1 to always be greater than n unless we are doing something not-so-common. In (say) Python, the int type is bigint, sometimes informally called "infinite precision" though their size is actually bounded by the size of the computer's memory. If your integers get too big, your program runs out of memory and weird things can happen, such as crashing, the OOM killer clobbering the process, or whatever. Basically undefined behaviour. In C it is the same thing, an int64 is infinite precision except bounded by the size of the machine word instead of by the memory size. If your program experiences uint64 overflow it's likely to be a genuine error condition unless the program is doing bit twiddling rather than arithmetic. In the case where it is an error condition, of course I'd want to trap it. Haskell makes the distinction between the Int type (an integer expected to fit in the size of a machine word) and the Word type (a bit pattern that supports some arithmetic operations). That is really what C should have done from the beginning. I've been wanting to check how Rust handles it.
  - tialaramex 5y ago
    Rust offers: * i8::MIN.checked_abs() is None * i8::MIN.overflowing_abs() is (i8::MIN,true) * i8::MIN.saturating_abs() is i8::MAX * i8::MIN.wrapping_abs() is i8::MIN [edited to add] * i8::MIN.unsigned_abs() is the 8-bit unsigned value 128 and finally * i8::MIN.abs() will panic in debug builds or give i8::MIN in non-debug builds. You should obviously not choose this last option if you in fact will call this function on i8::MIN (or any similar minimum values) which is why it panics if that happens. You should have instead chosen which behaviour you wanted (checked, overflowing, saturating or wrapping) up front.
  - saurik 5y ago
    > The integers mod 2*64 are a ring even though not a field, if that helps. Oh, ugh: I actually usually say "modular ring", but I'm not even sure that's a technical term, so for this comment I tried to get all fancy (as I thought I remembered that all rings are fields but not all fields are rings) and failed :(. > We do in fact normally use integer datatypes to represent integers rather than elements of a cyclic group. I assume our core disagreement comes because I believe that fundamentally everything representable on a Von Neumann computer is cyclic due to how memory works. I continue to 100% appreciate that this is an incredibly controversial opinion and that very few people are going to agree with me on this. > If your program experiences uint64 overflow it's likely to be a genuine error condition unless the program is doing bit twiddling rather than arithmetic. In the case where it is an error condition, of course I'd want to trap it. However, here I want to claim you are just wrong: you simply shouldn't be using that type for this... you should be using a big integer type; and the core solution here should NOT be to make overflow of this type trap, but to figure out why you are using this type in the first place and fix the language until you stop. > In (say) Python, the int type is bigint, sometimes informally called "infinite precision" though their size is actually bounded by the size of the computer's memory. If your integers get too big, your program runs out of memory and weird things can happen, such as crashing, the OOM killer clobbering the process, or whatever. This is fundamentally different, though: this isn't your program being wrong, but the system executing your program being wrong. Your program should strive to be correct, and insisting that "no one is ever going to need more than X-bits worth of Y" as an assertion in your program--as opposed to it merely being a limitation of the machine running your program--is a mistake.

saurik 5y ago

Yeah... I absolutely appreciate my belief is controversial "at best" ;P, but I stand by it, and even (personally) consider this one of the defining characteristics of someone who truly "understands" and thinks fluently and natively in the mental model of practical computation vs. someone who would prefer to translate from their real-world experience into the inherently-finite world of machines. That said, I certainly agree that if you are working with an actual unbounded numerical value you should be using a data structure that at least attempts to simulate an unbounded numerical value; but, what people always insist on instead is to continue using their fixed integer types which they want to magically have compatible semantics with unbounded integers... a fiction they insist the compilers and even CPUs join them in crafting, with things like the "trap-on-overflow" feature you are advocating for :/. The result of this is that, rather than accepting types like "uint64" are finite fields that should have perfectly regular overflow, and inverse semantics that under no circumstances, should be "messed with" by the environment, and that they should be using "BigInt" for any actual numbers that occasionally come up, people keep ruining the finite field types by trying and, in the end, failing to add a bunch of weird optimizations and overflow trap semantics to their operation... mitigations that only cause further errors later: these types should have the most brutal possible interpretation of finite field math, and anyone who wants an actual number--maybe to represent a physical or monetary quantity should be forced to not consider them an option. Meanwhile, languages should do anything and everything possible to not pessimize the syntax of types like BigInt by providing a short name for a good implementation of the type along with operator overloading that prevents anyone from ever considering the usage of a type like C's "int" to represent a number merely because it is easier or looks better or feels natural: you fix this issue, and "trap on overflow"--a ridiculous semantic that makes software look like it works until you push it a bit, and in a way that fails to be fungible with (and accepting the same solutions as) running out of memory--becomes a feature that has no legitimate usage.

throwaway81523 5y ago
uint64 is not a finite field type. For example, the number 2 has no multiplicative inverse mod 2**64. Ok I guess I understand what you meant, it's just that the mathematical concept of a finite field means something completely different than that. The integers mod 2**64 are a ring even though not a field, if that helps. But I'll stop quibbling over terminology. We do in fact normally use integer datatypes to represent integers rather than elements of a cyclic group. For example, we expect n+1 to always be greater than n unless we are doing something not-so-common. In (say) Python, the int type is bigint, sometimes informally called "infinite precision" though their size is actually bounded by the size of the computer's memory. If your integers get too big, your program runs out of memory and weird things can happen, such as crashing, the OOM killer clobbering the process, or whatever. Basically undefined behaviour. In C it is the same thing, an int64 is infinite precision except bounded by the size of the machine word instead of by the memory size. If your program experiences uint64 overflow it's likely to be a genuine error condition unless the program is doing bit twiddling rather than arithmetic. In the case where it is an error condition, of course I'd want to trap it. Haskell makes the distinction between the Int type (an integer expected to fit in the size of a machine word) and the Word type (a bit pattern that supports some arithmetic operations). That is really what C should have done from the beginning. I've been wanting to check how Rust handles it.
- tialaramex 5y ago
  Rust offers: * i8::MIN.checked_abs() is None * i8::MIN.overflowing_abs() is (i8::MIN,true) * i8::MIN.saturating_abs() is i8::MAX * i8::MIN.wrapping_abs() is i8::MIN [edited to add] * i8::MIN.unsigned_abs() is the 8-bit unsigned value 128 and finally * i8::MIN.abs() will panic in debug builds or give i8::MIN in non-debug builds. You should obviously not choose this last option if you in fact will call this function on i8::MIN (or any similar minimum values) which is why it panics if that happens. You should have instead chosen which behaviour you wanted (checked, overflowing, saturating or wrapping) up front.
- saurik 5y ago
  > The integers mod 2*64 are a ring even though not a field, if that helps. Oh, ugh: I actually usually say "modular ring", but I'm not even sure that's a technical term, so for this comment I tried to get all fancy (as I thought I remembered that all rings are fields but not all fields are rings) and failed :(. > We do in fact normally use integer datatypes to represent integers rather than elements of a cyclic group. I assume our core disagreement comes because I believe that fundamentally everything representable on a Von Neumann computer is cyclic due to how memory works. I continue to 100% appreciate that this is an incredibly controversial opinion and that very few people are going to agree with me on this. > If your program experiences uint64 overflow it's likely to be a genuine error condition unless the program is doing bit twiddling rather than arithmetic. In the case where it is an error condition, of course I'd want to trap it. However, here I want to claim you are just wrong: you simply shouldn't be using that type for this... you should be using a big integer type; and the core solution here should NOT be to make overflow of this type trap, but to figure out why you are using this type in the first place and fix the language until you stop. > In (say) Python, the int type is bigint, sometimes informally called "infinite precision" though their size is actually bounded by the size of the computer's memory. If your integers get too big, your program runs out of memory and weird things can happen, such as crashing, the OOM killer clobbering the process, or whatever. This is fundamentally different, though: this isn't your program being wrong, but the system executing your program being wrong. Your program should strive to be correct, and insisting that "no one is ever going to need more than X-bits worth of Y" as an assertion in your program--as opposed to it merely being a limitation of the machine running your program--is a mistake.