Implement numeric types

[jonmeow]

#700 renamed to i32, but left out the rest of the numeric types noted in #543. That is iN, uN, and fN for N in (8, 16, 32, 64). We should implement these.

It may be good to treat #766 as blocking this, so that any implementation is closer to what we expect long-term.

edit: noting a few specific comments on implementation approach:

• Need a Byte type: https://github.com/carbon-language/carbon-lang/issues/767#issuecomment-1330981072
• Rough implementation overview: https://github.com/carbon-language/carbon-lang/issues/767#issuecomment-1373907521
• start with mapping i32 to a prelude type (could even be Int32, non-generic): https://github.com/carbon-language/carbon-lang/issues/767#issuecomment-1374519570

[github-actions[bot]]

We triage inactive PRs and issues in order to make it easier to find active work. If this issue should remain active or becomes active again, please comment or remove the inactive label. The long term label can also be added for issues which are expected to take time. This issue is labeled inactive because the last activity was over 90 days ago.

[matthew-russo]

I was looking at picking this up but saw that it may be blocked on #766 which is further blocked on #742. Just wanted to do a pulse check on the status of this issue in relation to dependency on others. It seems like basic prelude functionality is in place (https://github.com/carbon-language/carbon-lang/blob/trunk/explorer/syntax/prelude.cpp#L11-L24) without a full implementation of imports

[jonmeow]

I added a note on #766. The current prelude functionality is enough to implement things. We do need library support though to make sure it doesn't become a giant file, but I don't think that's an immediate concern.

[matthew-russo]

I see #1998 was cut for a formal proposal on numeric types so I'm going to leave this until things have been finalized through a proposal.

[jonmeow]

FWIW, that issue is really about the names, and the leads already made a decision. There's a separate unresolved (and untracked I think) question about the shape of the underlying types, but I think the i32 -> Int(32) mapping plan is pretty likely, it's really only the nuances that need to be designed. A draft implementation in explorer can help with that; it's unlikely the details would diverge so much as to completely rewrite an implementation.

[github-actions[bot]]

We triage inactive PRs and issues in order to make it easier to find active work. If this issue should remain active or becomes active again, please comment or remove the inactive label. The long term label can also be added for issues which are expected to take time. This issue is labeled inactive because the last activity was over 90 days ago.

[jonmeow]

Note, in recent discussion about this, I think we were thinking what's missing for this to happen is some kind of raw storage type, e.g. Byte to have arrays of Byte. Then Int(32) would have an array of Bytes internally for storage. It would likely still need builtins for operations, but the comparisons and such could be implemented as intended with generic interfaces that call the builtins instead of straight C++ code as i32 is today. The intent is that that model would then be extended for i8 -> Int(8), i16 -> Int(16), and so on.

[priyans-google]

I can take a stab at this. Rough outline:

Parser:

• Generalize IntTypeLiteral to NumericTypeLiteral<BaseType>(size). Propagate both the basetype and size.

Interpreter:

• Add new Value kinds NumericalType and NumericalValue to generalize from IntType and IntValue
• Distinguish between different numeric types in the type checker.
• Change interpreter.cpp to properly handle each operator.

There are a ton of details which I need to understand.

[jonmeow]

A good starting point might be expanding IntTypeLiteral to handle multiple sizes, then thinking more about the other types once you've seen the code flow a little more.

I can take a stab at this. Rough outline:

Parser:

• Generalize IntTypeLiteral to NumericTypeLiteral<BaseType>(size). Propagate both the basetype and size.

Assuming BaseType is something like Int, Float, or UnsignedInt, then that may be fine. Noting that <BaseType> implies a template to me, you might find that you end up always specializing the template separately for the different types. Also, ExpressionKind enumerates things so you might find that challenging to make work with a template.

Instead adding FloatTypeLiteral and UnsignedIntTypeLiteral might be simpler (not guaranteed though; I'm not looking deeply).

Interpreter:

• Add new Value kinds NumericalType and NumericalValue to generalize from IntType and IntValue
• Distinguish between different numeric types in the type checker.
• Change interpreter.cpp to properly handle each operator.

In particular, I think the interpreter.cpp approach may be different.

My Byte comments contain a bit more. In order to have a sized numeric type, we need to store the value somewhere, and that's probably going to be an array of bytes. i.e., var storage: [Byte, size / 8];. The byte type doesn't exist yet.

Intrinsic functions (similar to __intrinsic_int_eq, for example) would need to be added that:

1. Take in the size of the integer and the byte array
2. Convert it to the appropriate type for C++ arithmetic
3. Perform the arithmetic
4. Convert the result back to the array

These intrinsic functions might end up on the more complex end, since they're converting from Carbon arrays to C++ integer types, and need to deal with the various size issues. LLVM's APInt, APSInt, and APFloat types might help here, though others are going to be more familiar with them than myself.

Then if you look at the prelude where __intrinsic_int_eq and similar are called, use that style for the new intrinsics.

There are a ton of details which I need to understand.

[jonmeow]

As I mull this, this might also make the interpreter slightly circular? I'm not sure how size / 8 works if we convert size to be a prelude-defined type, I think it becomes a recursive definition.

[jonmeow]

(maybe need to be really careful not to have literal / literal not use the same code path -- it probably does today)

[priyans-google]

Instead adding FloatTypeLiteral and UnsignedIntTypeLiteral might be simpler (not guaranteed though; I'm not looking deeply).

Makes sense, I'll start with adding size to IntTypeLiteral and (as you said, templates don't help much here anyway).

My first goal would be to get something like this running:

var x: i96 = 25947584758457487584574857;
var y: i64 = 483274347348374837;
var z: i96 = x + y;

This covers a bunch of cases we want to explore:

• non-intrinsic sizes other than 8/16/32/64.
• operations on heterogeneous sized operands
• automatic conversions
• overflow

[jonmeow]

Just an idea, but you might instead start by changing i32 to use an Int type in the prelude that's backed by a Byte array. That requires adding Byte, but avoids the generics and math for a variable size array.

[github-actions[bot]]

We triage inactive PRs and issues in order to make it easier to find active work. If this issue should remain active or becomes active again, please comment or remove the inactive label. The long term label can also be added for issues which are expected to take time.

This issue is labeled inactive because the last activity was over 90 days ago.

[chandlerc]

Closing explorer-specific issues as not-planned for now due to our decision to prioritize working on the toolchain over other implementation work in the near term: https://github.com/carbon-language/carbon-lang/blob/trunk/proposals/p3532.md