5 ms·

> In Structure and Interpretation of Computer Programs, Abelson and Sussman describe an arithmetic system in which the arithmetic types form an explicit lattice

> In Structure and Interpretation of Computer Programs, Abelson and Sussman describe an arithmetic system in which the arithmetic types form an explicit lattice. Every type comes with a “promotion” function to promote it to a type higher up in the lattice. When values of different types are added, each value is promoted, perhaps repeatedly, until the two values are the same type, which is the lattice join of the two original types. I've never used anything like this and don't know how well it works in practice, but it seems like a plausible approach, one which works the way we usually think about numbers, and understands that it can add a float to a Gaussian integer by construing both of them as complex numbers. Julia uses this in pretty much all of its math functions and probably elsewhere as well, and it works unbelievably well. The type promotion system makes math Just Work, even (and especially) in the face of different-sized numbers. The result is that 99.9% of the time you simply don't have to think about the types of your numbers. Here are some examples from the docs: julia> promote_type(Int64, Float64) Float64 julia> promote_type(Int32, Int64) Int64 julia> promote_type(Float32, BigInt) BigFloat julia> promote_type(Int16, Float16) Float16 julia> promote_type(Int64, Float16) Float16 julia> promote_type(Int8, UInt16) UInt16 And not only are types promoted, but in well-typed Julia code, the deduction of promotion types happens at compile time instead of runtime, so there is almost no performance cost to this either.

HalcyonCowboy 5y ago
Wouldn’t that last example be incorrect mathematically? For example, if the Int8 was -10 and the UInt16 was 10, what would that casting do? Would a better promotion be Int32 for both? Just curious, Julia is a language I’ve been very interested in using for a long time, just haven’t had the opportunity to sit down and learn yet.
- adgjlsfhk1 5y ago
  Yeah, it's a little iffy. Finding a sensible set of promotion rules is hard. I don't know the reason (this was decided before I was involved), but if I had to guess, it would be because unsigned types are much less common, so if the user has them, they probably want to keep them for a reason.
- bobbylarrybobby 5y ago
  Ah shit, well I guess you found the 0.1%
  - adwn 5y ago
    You think negative numbers in a signed type are a 1-in-a-1000 case, really? Silently casting signed integers to unsigned is a terrible idea, and a recipe for bugs. And completely unnecessary to boot, because you could promote Int8 to Int16, and (Int16, UInt16) to (Int32, Int32).
    - astrange 5y ago
      Related, an integer bug that can't be fixed in C is that "unsigned short" promotes to "int" instead of "unsigned int", so this doesn't produce the result you want. unsigned x = (unsigned short)65535 * (unsigned short)65535; (It overflows even though it's less than UINT_MAX, and worse it's UB.)
  - kolbusa 5y ago
    This is completely off topic here, but the first promotion of Int64 -> Float64 is also iffy as not every Int64 is exactly representable. The Int64 -> Float16 promotion also looks weird to me because Float16 range is so small
- thaumasiotes 5y ago
  > Wouldn’t that last example be incorrect mathematically? For example, if the Int8 was -10 and the UInt16 was 10, what would that casting do? Well.... Signed integer arithmetic and unsigned integer arithmetic do not differ. At all. The difference between an Int16 and a UInt16 is not in the 16 defined bits. It's in the infinite number of implicit bits representing place values above 2^15. Those bits are always 0 for the UInt16, but they're identical with the high bit of the Int16. So it's not clear what it would mean for the result type to be "incorrect mathematically". Mathematically, an Int16 and a UInt16 are the same thing. However, the path by which you promote the values does matter. I don't know what Julia does. But: -10 (Int8) + 10 (UInt16) -10 (Int16) + 10 (UInt16) 65526 (UInt16) + 10 (UInt16) 0 (UInt16) is a different result from -10 (Int8) + 10 (UInt16) 246 (UInt8) + 10 (UInt16) 246 (UInt16) + 10 (UInt16) 256 (UInt16) One of those should be the result Julia gives. I tend to hope it's the first one. That would correspond to a promotion strategy of "always expand the type to its full width before converting between signed and unsigned". Expansion (and shift, I guess) is the only operation for which the difference between signed and unsigned is relevant. > Would a better promotion be Int32 for both? Probably not; that would imply that when you add two UInt16s together, you expect to get a UInt32 (or UInt17...) back.
  - HalcyonCowboy 5y ago
    It took me a couple of readings to make sure I understood what you were saying, thanks for the reply. I think my misunderstanding was from not knowing Julia and thinking about promotion of values as having a permanent effect on the variables used, which isn’t what’s happening. As well, it requires the user to understand what they’re doing when they’re using an operator that uses automatic promotion, and to think about what they want to happen. For example, if Int8 = -10 and UInt16 = 5, and I’m expecting an answer of -5, then I’ll need to be more explicit to get the number I’m looking for. If I’m expecting 65530, then the implicit promotion works fine. Of course, this is no different from any other programming language that allows addition of differing types. Great point on the path dependence.
    - thaumasiotes 5y ago
adgjlsfhk1 5y ago
the main thing Julia loses from this approach is function types. since each function is a user extendable blob of methods, there basically ceases to be a meaningful notion of the type of a function. imo, this is a worthwhile trade-off, but it can sometimes be annoying (and it's why Julia is hard to compile ahead of time. this pattern makes figuring out which methods you need to compile Turing complete)

HalcyonCowboy 5y ago

Wouldn’t that last example be incorrect mathematically? For example, if the Int8 was -10 and the UInt16 was 10, what would that casting do? Would a better promotion be Int32 for both? Just curious, Julia is a language I’ve been very interested in using for a long time, just haven’t had the opportunity to sit down and learn yet.

adgjlsfhk1 5y ago
Yeah, it's a little iffy. Finding a sensible set of promotion rules is hard. I don't know the reason (this was decided before I was involved), but if I had to guess, it would be because unsigned types are much less common, so if the user has them, they probably want to keep them for a reason.
bobbylarrybobby 5y ago
Ah shit, well I guess you found the 0.1%
- adwn 5y ago
  You think negative numbers in a signed type are a 1-in-a-1000 case, really? Silently casting signed integers to unsigned is a terrible idea, and a recipe for bugs. And completely unnecessary to boot, because you could promote Int8 to Int16, and (Int16, UInt16) to (Int32, Int32).
  - astrange 5y ago
    Related, an integer bug that can't be fixed in C is that "unsigned short" promotes to "int" instead of "unsigned int", so this doesn't produce the result you want. unsigned x = (unsigned short)65535 * (unsigned short)65535; (It overflows even though it's less than UINT_MAX, and worse it's UB.)
- kolbusa 5y ago
  This is completely off topic here, but the first promotion of Int64 -> Float64 is also iffy as not every Int64 is exactly representable. The Int64 -> Float16 promotion also looks weird to me because Float16 range is so small
thaumasiotes 5y ago
> Wouldn’t that last example be incorrect mathematically? For example, if the Int8 was -10 and the UInt16 was 10, what would that casting do? Well.... Signed integer arithmetic and unsigned integer arithmetic do not differ. At all. The difference between an Int16 and a UInt16 is not in the 16 defined bits. It's in the infinite number of implicit bits representing place values above 2^15. Those bits are always 0 for the UInt16, but they're identical with the high bit of the Int16. So it's not clear what it would mean for the result type to be "incorrect mathematically". Mathematically, an Int16 and a UInt16 are the same thing. However, the path by which you promote the values does matter. I don't know what Julia does. But: -10 (Int8) + 10 (UInt16) -10 (Int16) + 10 (UInt16) 65526 (UInt16) + 10 (UInt16) 0 (UInt16) is a different result from -10 (Int8) + 10 (UInt16) 246 (UInt8) + 10 (UInt16) 246 (UInt16) + 10 (UInt16) 256 (UInt16) One of those should be the result Julia gives. I tend to hope it's the first one. That would correspond to a promotion strategy of "always expand the type to its full width before converting between signed and unsigned". Expansion (and shift, I guess) is the only operation for which the difference between signed and unsigned is relevant. > Would a better promotion be Int32 for both? Probably not; that would imply that when you add two UInt16s together, you expect to get a UInt32 (or UInt17...) back.
- HalcyonCowboy 5y ago
  It took me a couple of readings to make sure I understood what you were saying, thanks for the reply. I think my misunderstanding was from not knowing Julia and thinking about promotion of values as having a permanent effect on the variables used, which isn’t what’s happening. As well, it requires the user to understand what they’re doing when they’re using an operator that uses automatic promotion, and to think about what they want to happen. For example, if Int8 = -10 and UInt16 = 5, and I’m expecting an answer of -5, then I’ll need to be more explicit to get the number I’m looking for. If I’m expecting 65530, then the implicit promotion works fine. Of course, this is no different from any other programming language that allows addition of differing types. Great point on the path dependence.
  - thaumasiotes 5y ago

adgjlsfhk1 5y ago

the main thing Julia loses from this approach is function types. since each function is a user extendable blob of methods, there basically ceases to be a meaningful notion of the type of a function. imo, this is a worthwhile trade-off, but it can sometimes be annoying (and it's why Julia is hard to compile ahead of time. this pattern makes figuring out which methods you need to compile Turing complete)