3 ms·

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 characterist

by 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.
saghm 5y ago
> 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. For my own personal vanity, is someone who hasn't studied high enough level math enough to have a formal sense of what "finite field" means necessarily non-fluent in practical computation, or is it possible to have sufficient intuition about computational versus "real-world" integers without being able to express it?
- adrian_b 5y ago
  Programmers may not know what a finite field means, but they must know for any operation that they are using whether the operation is invertible or not, i.e. whether from the result you can recover the input value or not. If they are not aware of this property, bugs will certainly be caused by this, sooner or later. In a set of modular numbers where the modulus is not a prime number, e.g. in C/C++ "unsigned char", "unsigned short" "unsigned", "unsigned long" and "unsigned long long", where the modulus is a power of two, multiplication is invertible only if the multiplicator is relatively prime with the modulus. In the C/C++ modular numbers that means that only multiplication with odd numbers is invertible. A consequence of this fact, which should be familiar to most programmers, even if they might not be aware of the cause, is that we have only one kind of shift to the left (i.e. multiplication by 2), but 2 kinds of shift to the right (division by 2). In the set of integers modulo 2^n there are 2 numbers that multiplied by 2, i.e. shifted 1 position to the left, give the same number, and they correspond to the so-called logical shift to the right a.k.a. unsigned shift to the right and to the so-called arithmetical shift to the right a.k.a. signed shift to the right. The names of the 2 shifts to the right are misleading, because both are well-defined meaningful operations for what in C/C++ are named "unsigned" numbers, but which are defined in the standards as modular integers, not unsigned integers (which would give exceptions or saturation on overflow). The fact that in C/C++ you get for ">>" one of the 2 shifts depending on whether the operand is "signed" or "unsigned" is just a convention. However this convention is useful in most cases, because in C/C++ smaller numbers are typically considered as being truncated from larger numbers that correspond to either their zero-extended or their sign-extended equivalent, and not as really being modular numbers as they are defined and as they behave. In languages that impose more constraints on the programmers, e.g. Ada, the programmer need not be so aware about how numbers are represented and which is the meaning and properties of the operations applied to numbers. On the other hand, in C/C++, which besides some implicit safe conversions also have a large number of unsafe unchecked implicit or explicit number conversions, programmers will very likely cause some bugs eventually, unless they understand well the differences between modular numbers, signed integer numbers, unsigned integer numbers (really unsigned numbers, not those named so in C), how these numbers are compared by the hardware, depending on whether they are signed or not, how and when overflow is signaled by the hardware, also depending on whether the numbers are signed or not, which operations are invertible and which not, and so on. Sometimes, especially when programming for embedded computers, the freedom of C/C++ is convenient, but nonetheless a lot of care is needed to not be surprised by undesired implicit conversions and truncations, like in the example that started this thread.

by saurik 5y ago

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.

saghm 5y ago

> 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. For my own personal vanity, is someone who hasn't studied high enough level math enough to have a formal sense of what "finite field" means necessarily non-fluent in practical computation, or is it possible to have sufficient intuition about computational versus "real-world" integers without being able to express it?

adrian_b 5y ago
Programmers may not know what a finite field means, but they must know for any operation that they are using whether the operation is invertible or not, i.e. whether from the result you can recover the input value or not. If they are not aware of this property, bugs will certainly be caused by this, sooner or later. In a set of modular numbers where the modulus is not a prime number, e.g. in C/C++ "unsigned char", "unsigned short" "unsigned", "unsigned long" and "unsigned long long", where the modulus is a power of two, multiplication is invertible only if the multiplicator is relatively prime with the modulus. In the C/C++ modular numbers that means that only multiplication with odd numbers is invertible. A consequence of this fact, which should be familiar to most programmers, even if they might not be aware of the cause, is that we have only one kind of shift to the left (i.e. multiplication by 2), but 2 kinds of shift to the right (division by 2). In the set of integers modulo 2^n there are 2 numbers that multiplied by 2, i.e. shifted 1 position to the left, give the same number, and they correspond to the so-called logical shift to the right a.k.a. unsigned shift to the right and to the so-called arithmetical shift to the right a.k.a. signed shift to the right. The names of the 2 shifts to the right are misleading, because both are well-defined meaningful operations for what in C/C++ are named "unsigned" numbers, but which are defined in the standards as modular integers, not unsigned integers (which would give exceptions or saturation on overflow). The fact that in C/C++ you get for ">>" one of the 2 shifts depending on whether the operand is "signed" or "unsigned" is just a convention. However this convention is useful in most cases, because in C/C++ smaller numbers are typically considered as being truncated from larger numbers that correspond to either their zero-extended or their sign-extended equivalent, and not as really being modular numbers as they are defined and as they behave. In languages that impose more constraints on the programmers, e.g. Ada, the programmer need not be so aware about how numbers are represented and which is the meaning and properties of the operations applied to numbers. On the other hand, in C/C++, which besides some implicit safe conversions also have a large number of unsafe unchecked implicit or explicit number conversions, programmers will very likely cause some bugs eventually, unless they understand well the differences between modular numbers, signed integer numbers, unsigned integer numbers (really unsigned numbers, not those named so in C), how these numbers are compared by the hardware, depending on whether they are signed or not, how and when overflow is signaled by the hardware, also depending on whether the numbers are signed or not, which operations are invertible and which not, and so on. Sometimes, especially when programming for embedded computers, the freedom of C/C++ is convenient, but nonetheless a lot of care is needed to not be surprised by undesired implicit conversions and truncations, like in the example that started this thread.