Stream: beginners

Topic: Generic Unsigned Integer

Chris Duncan (Oct 09 2022 at 03:57):

Is there a generic type for unsigned integers, as in, a type that the only restriction on the number is that it is unsigned and does not limit the size or the underlying representation of the number? I would like to write functions that work on any unsigned integer to only choose its size at the edge of the app.

Luke Boswell (Oct 09 2022 at 03:59):

Is that what an Int * is?

jan kili (Oct 09 2022 at 03:59):

Currently no: https://github.com/roc-lang/roc/blob/main/crates/compiler/builtins/roc/Num.roc#L421

jan kili (Oct 09 2022 at 04:00):

As you can see in the definitions for I128, U8, etc. the size & signedness are currently entangled

jan kili (Oct 09 2022 at 04:00):

However, I imagine that could change

Luke Boswell (Oct 09 2022 at 04:01):

Could you do something like [U16, U32, U64, ...]?

jan kili (Oct 09 2022 at 04:02):

@Luke Boswell you could use tags to indicate what type of data you're intending to be passing around, but it wouldn't enforce it

jan kili (Oct 09 2022 at 04:03):

since the numerical system currently only supports enforcing either integerness or 64-bit-unsigned-integer-ness, but nothing in-between

jan kili (Oct 09 2022 at 04:04):

@Chris Duncan in other words, you can definitely write those functions today, but you can't prevent yourself from using them on signed integers

jan kili (Oct 09 2022 at 04:06):

well, actually, nevermind, @Luke Boswell makes a good point - you could restrict them to operate on the exact complete set of currently-defined unsigned integer types

Ayaz Hafiz (Oct 09 2022 at 04:08):

Yeah, re what Luke suggested, you could do something like

UnsignedInt : [U8 U8, U16 U16, ...]

addUnsigned : UnsignedInt, UnsignedInt -> UnsignedInt

but this can be kind of annoying , since you'll need to enumerate all cases in a when expression

jan kili (Oct 09 2022 at 04:11):

UnsignedFriend : [Smol U8, Small U16, Medium U32, Big U64, Beeg U128]
addUnsigned : UnsignedFriend, UnsignedFriend -> UnsignedFriend
addUnsigned = \a, b ->
    when a is
        Smol aa ->
            when b is
                Smol bb ->
                    Smol (aa + bb)
                Small bb ->
                    Small ((Num.toU16 aa) + bb)
                Medium bb ->
                    oh no
                ...
        Small aa ->
            oh no
        ...

jan kili (Oct 09 2022 at 04:13):

Currently this would require 25 when cases, which means 40+ lines of repetitive code

jan kili (Oct 09 2022 at 04:16):

The practical solutions to this are:
a) in your project, discourage (but don't prevent) use with signed integers by naming it something like fooUnsigned
b) in the Roc builtins, disentangle signedness from size for integer types for everyone, which doesn't seem crazy

jan kili (Oct 09 2022 at 04:18):

However, if short-term safety is your goal, then enjoy a Beeg function :laughing:

Ayaz Hafiz (Oct 09 2022 at 04:19):

Yeah, I guess we could add this to Num.roc so that Integer range is defined as Integer range := [Signed range, Unsigned range]. And then you get Unsigned range : Integer (Unsigned range) and likewise for Signed

At runtime there would be no extra cost here, just possibly a minor cost to typechecking

jan kili (Oct 09 2022 at 04:28):

@Ayaz Hafiz Would the definition instead be something like Integer signedness range := { signedness, range } so that we can define integer types like I128 : Num (Integer Signed 128)? I'm unfamiliar with opaque types, but I don't know how we'd define I128 with the Integer definition you gave above.

jan kili (Oct 09 2022 at 04:29):

Hmm, maybe I128 : Num (Integer (Signed 128)), but something feels wrong about (Signed 128) mapping to range...

Ayaz Hafiz (Oct 09 2022 at 04:32):

either way works, those two definitions are actually identical in terms of what they can express :sweat_smile:

Ayaz Hafiz (Oct 09 2022 at 04:32):

there are probably other ways too

jan kili (Oct 09 2022 at 04:33):

Oh, cool... but how do we not need signedness as a type variable?

Ayaz Hafiz (Oct 09 2022 at 04:34):

well presumably it would only take on two forms, Signed or Unsigned. That’s why i explicitly enumerated them

Ayaz Hafiz (Oct 09 2022 at 04:35):

“range” could be thought of as “bitWidth” here

jan kili (Oct 09 2022 at 04:40):

Sorry if I'm being thick here, but wouldn't

Integer range := [Signed range, Unsigned range]
I128 : Num (Integer (Signed 128))

mean that I128 is "represented"(?) as Num (Signed (Signed 128))? And how would it know that first Signed part?

jan kili (Oct 09 2022 at 04:42):

as opposed to

Integer signedness range := { signedness, range }
I128 : Num (Integer Signed 128)

meaning that I128 is represented as Num { signedness: Signed, range: 128 }?

jan kili (Oct 09 2022 at 04:55):

Maybe the generalization of my question is:

How can you ever use a tag union as an underlying representation of an opaque type when the tags represent an externally-pickable behavior, since you can't pick the tag via type variables?

(pardon my lack of vocabulary around opaque types, I'm sure "pick" and "represent" aren't ideal words here)

jan kili (Oct 09 2022 at 05:06):

(and I'm not asking just to be pedantic - I went to implement this change and got stuck)

Ayaz Hafiz (Oct 09 2022 at 05:07):

I wasn't thinking of a signedness type variable, instead to enumerate signedness explicitly - sorry, I know I glossed over that in your description

Ayaz Hafiz (Oct 09 2022 at 05:07):

Concretely

Ayaz Hafiz (Oct 09 2022 at 05:09):

<oops>

Ayaz Hafiz (Oct 09 2022 at 05:10):

oh oops

Ayaz Hafiz (Oct 09 2022 at 05:10):

one sec

Ayaz Hafiz (Oct 09 2022 at 05:13):

sorry, you're right, I got too caught up in the value level. my bad, that was really a huge oversight on my part. you would have to have a type variable for the sign

jan kili (Oct 09 2022 at 05:14):

Phew, I feel like I just connected a bunch of static-typing neurons in my brain :big_smile:

Ayaz Hafiz (Oct 09 2022 at 05:16):

No yeah you're totally right. Sorry again

jan kili (Oct 09 2022 at 05:18):

All good! It was a helpful exploration for me :) hopefully others, too

jan kili (Oct 09 2022 at 05:18):

I'm diving back into implementation now, and enjoying the nuance of Nat :stuck_out_tongue:

jan kili (Oct 09 2022 at 05:43):

My implementation so far, what do y'all think? :smiley:

Num range := range

Integer signedness bits := { signedness, bits }
Fraction pointSystem bits := { pointSystem, bits }

Int signedness bits : Num (Integer signedness bits)
Frac pointSystem bits : Num (Fraction pointSystem bits)

I8 : Int Signed Static8Bits
I16 : Int Signed Static16Bits
I32 : Int Signed Static32Bits
I64 : Int Signed Static64Bits
I128 : Int Signed Static128Bits

U8 : Int Unsigned Static8Bits
U16 : Int Unsigned Static16Bits
U32 : Int Unsigned Static32Bits
U64 : Int Unsigned Static64Bits
U128 : Int Unsigned Static128Bits

Nat : Int Unsigned Dynamic32Or64BitsPerSystem

Signed := []
Unsigned := []

Static8Bits := []
Static16Bits := []
Static32Bits := []
Static64Bits := []
Static128Bits := []
Dynamic32Or64BitsPerSystem := []

F32 : Frac FloatingPoint Static32Bits
F64 : Frac FloatingPoint Static64Bits
Dec : Frac FixedPoint Static128Bits

FixedPoint := []
FloatingPoint := []

jan kili (Oct 09 2022 at 05:48):

I wish I saw a way to enable both generic integers and generic 32-bit numbers... because it's so close now... but that doesn't seem syntactically possible to cut generically across both of those dimensions. Oh well, handling both 32-bit integers and 32-bit fractions probably doesn't have many use cases... right?

Richard Feldman (Oct 09 2022 at 05:48):

I'm curious what the motivating use case is! I thought about having this as a distinction back in 2018 but concluded it wouldn't be worth the added type complexity and (probably very minor) compile time increase :big_smile:

Richard Feldman (Oct 09 2022 at 05:49):

I don't think you can add it onto the existing system, but it's definitely possible (at nontrivial cost) to make Num support this while still supporting all the use cases it currently does

jan kili (Oct 09 2022 at 05:50):

("it" & "this" meaning 32-bit generics?)

jan kili (Oct 09 2022 at 05:51):

Yes, I'm also interested in the use cases for signedness/bit-depth generics! What's new since 2018?

jan kili (Oct 09 2022 at 05:52):

@Chris Duncan what's your motivation for this? (mine is just "because it seems right")

Richard Feldman (Oct 09 2022 at 05:53):

my threshold for making Num more complex is way higher than "seems right" :laughing:

Richard Feldman (Oct 09 2022 at 05:53):

my original motivating use case for signedness was wanting Num.neg to only accept signed numbers

Richard Feldman (Oct 09 2022 at 05:54):

because with unsigned ones you either give it exactly 0 or else it's going to panic

jan kili (Oct 09 2022 at 05:57):

Well, really how much more complex is Num (Integer Signed Static8Bits) than Num (Integer Signed8)? Is it a matter of character count?

jan kili (Oct 09 2022 at 05:58):

Personally it feels more explanatory, which counts for something, even lowering complexity by making it less magical

jan kili (Oct 09 2022 at 05:59):

However, compile times matter.

Ayaz Hafiz (Oct 09 2022 at 05:59):

I'll give a couple examples I've run into:

• one is throughout advent of code 2021 there are times I've wanted to generically operate over unsigned types, like when working on a 2D Cartesian plane only in Q1: https://github.com/ayazhafiz/roc-advent-of-code/blob/main/2021/day4.roc. Ideally you (or the compiler) would minimize the runtime unsigned integer you use but in practice a U64 is fine. I had a similar thing for day 6
• When you bit shift you want to shift by an unsigned integer amount; again, in practice just passing a U8 is fine

jan kili (Oct 09 2022 at 06:02):

(To be fair to the downsides of verbosity, it would be pretty jarring to type List.len [1, 2, 3] into the REPL and see 3 : Num (Integer Unsigned Dynamic32Or64BitsPerSystem) :laughter_tears: ...it's not wrong, though)

Chris Duncan (Oct 09 2022 at 06:03):

@Ayaz Hafiz You beat me to it :laughter_tears: I'm also doing Advent of Code, and I'm encountering the same want of having functions that operate over natural numbers and expressing that restriction in the types.

jan kili (Oct 09 2022 at 06:05):

It's worth mentioning Nat already exists, and it can already service the use cases mentioned so far

jan kili (Oct 09 2022 at 06:05):

(unless you're working with big numbers on a 32-bit system)

jan kili (Oct 09 2022 at 06:08):

Let's continue discussing if this is sufficiently motivated/justified, but here's a visualization of what the builtins changes might entail: https://github.com/roc-lang/roc/pull/4268/files (and it's missing how many other downstream files will need to change)

Richard Feldman (Oct 09 2022 at 06:15):

I remember from my earlier exploration (it's been a few years, so not sure exactly what I had written down, or where) that it's doable with Int still having one type parameter

Richard Feldman (Oct 09 2022 at 06:16):

and then having separate Signed * and Unsigned *

Richard Feldman (Oct 09 2022 at 06:16):

it was something to do with Int's type param being a record I think

Richard Feldman (Oct 09 2022 at 06:18):

so it was something like Signed a : Int { signedness : [Signed], other : a }

Richard Feldman (Oct 09 2022 at 06:19):

where other is whatever other info you want in there (e.g. number of bits)

Chris Duncan (Oct 09 2022 at 06:19):

@JanCVanB, I am using Nat precisely because it's the most generic of the unsigned integers.

jan kili (Oct 09 2022 at 06:21):

@Richard Feldman oh interesting, does reducing the quantity of type parameters inherently reduce complexity to either developers or the compiler?

Richard Feldman (Oct 09 2022 at 06:23):

I think it does for developers - like consider the type of https://www.roc-lang.org/builtins/Num#shiftLeftBy

Int a, U8 -> Int a

vs

Int a b, U8 -> Int a b

Richard Feldman (Oct 09 2022 at 06:24):

it's not the end of the world, but it's definitely more to think about for no real benefit in the common case

Richard Feldman (Oct 09 2022 at 06:24):

the type parameter in the first type communicates "whatever type of integer you pass in, that's the type of integer you'll get back" - just like List a

Richard Feldman (Oct 09 2022 at 06:25):

the second one communicates the same information, but in a way that requires strictly more explanation

jan kili (Oct 09 2022 at 06:25):

:100: I forgot that a majority of exposures to these type signature will be with placeholders like a and *

jan kili (Oct 09 2022 at 06:26):

it also eats up a whole letter in complex signatures

Richard Feldman (Oct 09 2022 at 06:26):

yeah I think it's valuable to have Num, Int, and Frac all have one type parameter, no matter how deep the hierarchy goes beneath them

jan kili (Oct 09 2022 at 06:26):

Totally - and it's trivial to adapt my implementation above to do that.

Ayaz Hafiz (Oct 09 2022 at 13:43):

I don't like this idea but you could do this with abilities rather than extra type parameter

Last updated: Jul 26 2025 at 12:14 UTC