Expanded support for numeric types in stdlib?


(Austin Zheng) #1

Hi all,

There are quite a few programming languages that provide support for
numeric types apart from the customary floating-point and fixed-width
integer types. Prominent examples of additional numeric types include
rational numbers, arbitrary-width integer types, and fixed-point numbers.
Many of these numeric types are applicable to a wide variety of problem
domains.

Swift seems like it would be a good fit for stdlib implementation of some
of these numeric types. Structs and value semantics, literal
initialization, and operator overloading would allow such types to be
treated as first-class citizens. Is the community amenable to such a
proposal, which would entail the data structures themselves, arithmetic
operations, and interoperation between different numeric types to form a
numerical tower of sorts?

Best regards,
Austin


(Chris Lattner) #2

Hi all,

There are quite a few programming languages that provide support for numeric types apart from the customary floating-point and fixed-width integer types. Prominent examples of additional numeric types include rational numbers, arbitrary-width integer types, and fixed-point numbers. Many of these numeric types are applicable to a wide variety of problem domains.

Hi Austin, great to hear from you:

It would be great to consider this. We’ve specifically recently discussed BigInt support, for example.

One of the things that we’d like to see for Swift 3 is a revised set of numerics protocols, to make it possible to write generic numeric algorithms. One concern I have with this is that abstracting over (e.g.) IEEE and rational numbers may overly complicate the protocols necessary to get simple things done.

That said, I’m not an expert on this area, so I’m cc’ing some people who are :-)

-Chris

···

On Dec 3, 2015, at 1:14 PM, Austin Zheng <austinzheng@gmail.com> wrote:

Swift seems like it would be a good fit for stdlib implementation of some of these numeric types. Structs and value semantics, literal initialization, and operator overloading would allow such types to be treated as first-class citizens. Is the community amenable to such a proposal, which would entail the data structures themselves, arithmetic operations, and interoperation between different numeric types to form a numerical tower of sorts?

Best regards,
Austin
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dmitri Gribenko) #3

Hi Austin,

We are interested in improving our numerics support, and we are
definitely interested in hearing your ideas in this space. You don't
have to write a full proposal though. Just an extended email to
swift-evolution would be a good start.

You can find the current prototype for library support for integers
here: https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb

Dmitri

···

On Thu, Dec 3, 2015 at 1:14 PM, Austin Zheng <austinzheng@gmail.com> wrote:

Hi all,

There are quite a few programming languages that provide support for numeric types apart from the customary floating-point and fixed-width integer types. Prominent examples of additional numeric types include rational numbers, arbitrary-width integer types, and fixed-point numbers. Many of these numeric types are applicable to a wide variety of problem domains.

Swift seems like it would be a good fit for stdlib implementation of some of these numeric types. Structs and value semantics, literal initialization, and operator overloading would allow such types to be treated as first-class citizens. Is the community amenable to such a proposal, which would entail the data structures themselves, arithmetic operations, and interoperation between different numeric types to form a numerical tower of sorts?

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Austin Zheng) #4

Thanks, Chris and Dmitri! I will do some research and write something up
over the weekend.

Austin

···

On Thu, Dec 3, 2015 at 2:24 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:

On Thu, Dec 3, 2015 at 1:14 PM, Austin Zheng <austinzheng@gmail.com> > wrote:
>
> Hi all,
>
> There are quite a few programming languages that provide support for
numeric types apart from the customary floating-point and fixed-width
integer types. Prominent examples of additional numeric types include
rational numbers, arbitrary-width integer types, and fixed-point numbers.
Many of these numeric types are applicable to a wide variety of problem
domains.

>
> Swift seems like it would be a good fit for stdlib implementation of
some of these numeric types. Structs and value semantics, literal
initialization, and operator overloading would allow such types to be
treated as first-class citizens. Is the community amenable to such a
proposal, which would entail the data structures themselves, arithmetic
operations, and interoperation between different numeric types to form a
numerical tower of sorts?

Hi Austin,

We are interested in improving our numerics support, and we are
definitely interested in hearing your ideas in this space. You don't
have to write a full proposal though. Just an extended email to
swift-evolution would be a good start.

You can find the current prototype for library support for integers
here:
https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Austin Zheng) #5

Dear swift-evolution,

I less want to make concrete proposals than start a conversation about
expanded numerical support in Swift. In that spirit, here are some thoughts:

Arbitrary-precision integers (bigints) are a logical first step. Bigints
then enable practical support for rationals. (With bigints, rational
operations need not fail because of integer overflow.) Adding at least
these two numerical types would bring Swift far closer wrt numerical
support wrt languages like Clojure or Ruby.

Many languages make a distinction between fixed precision integers and
bigints (i.e. Haskell's Int vs Integer). I propose the definition of two
related types: ArbitraryPrecisionInteger and Integer.

ArbitraryPrecisionInteger is a struct wrapping a pointer to a byte buffer,
much like how Swift's Array, Set, and Dictionary collection types work
(c.f.
https://www.mikeash.com/pyblog/friday-qa-2015-04-17-lets-build-swiftarray.html).
It wraps an arbitrarily large integer within a container adhering to value
semantics. Perhaps this can be exposed as part of the stdlib, or a
'private' implementation detail.

Integer is intended to be used by application developers, and most of the
arithmetic/comparison functionality exposed by the stdlib deals with
arguments and return values of type Integer. Integers are enums:

enum Integer {
case Small(Int)
case Big(ArbitraryPrecisionInteger)
}

Like ArbitraryPrecisionInteger, Integer represents an arbitrary-precision
integer. It wraps either a fixed-size (64-bit) signed integer, or a bigint.
Integer's invariant is that integers within the range of an Int are always
stored as an Int. This is enforced by the mathematical operations defined
on arguments of type Integer. This allows for a slow path (consisting of
operations that are conducted on ArbitraryPrecisionIntegers), and a fast
path (consisting of checked operations on Ints, with automatic promotion to
ArbitraryPrecisionInteger as necessary). Fast path operations, in the best
case, need not allocate heap memory or invoke retain/release operations.

Integers can be unconditionally constructed (promoted) from Ints, and can
be conditionally demoted to Ints ( () -> Int? ). (All Ints are Integers,
but not all Integers are Ints.)

A useful compiler support feature might be a "BigIntegerLiteralConvertible"
protocol, which allows literal integers out of the range of Ints to be
assigned to Integer values. Swift can already tell if an integer literal is
out of range (e.g. "let x : Int8 = 123456"), so there is some precedent.
This would be a more elegant solution than requiring bigints to be
initialized via strings (as some other arbitrary precision arithmetic
libraries do).

Rational numbers are represented by the Rational struct which encapsulates
two Integers, the numerator and denominator. Rationals can be conditionally
constructed explicitly from two Integers (as long as the denominator isn't
0), or from a single Integer (all Integers are Rationals, but the opposite
is not true). A good invariant for Rationals might be having them always
represented in the most simplified form - for example, Rational(2, 6)
should be represented internally as 1/3 when constructed.

Future topics to explore include complex numbers, arbitrary-precision
floating-point numbers, and fixed-precision and/or decimal number types.

Given that I'm little more than a dabbler in these topics (most of my
expertise came from trying to reverse-assemble Clojure's numerical
support), feedback from someone with experience and/or expertise wrt
numerical/scientific computing, bignum libraries, numerical towers, etc.
would be hugely appreciated.

Best regards,
Austin

···

On Thu, Dec 3, 2015 at 6:52 PM, Austin Zheng <austinzheng@gmail.com> wrote:

Thanks, Chris and Dmitri! I will do some research and write something up
over the weekend.

Austin

On Thu, Dec 3, 2015 at 2:24 PM, Dmitri Gribenko <gribozavr@gmail.com> > wrote:

On Thu, Dec 3, 2015 at 1:14 PM, Austin Zheng <austinzheng@gmail.com> >> wrote:
>
> Hi all,
>
> There are quite a few programming languages that provide support for
numeric types apart from the customary floating-point and fixed-width
integer types. Prominent examples of additional numeric types include
rational numbers, arbitrary-width integer types, and fixed-point numbers.
Many of these numeric types are applicable to a wide variety of problem
domains.

>
> Swift seems like it would be a good fit for stdlib implementation of
some of these numeric types. Structs and value semantics, literal
initialization, and operator overloading would allow such types to be
treated as first-class citizens. Is the community amenable to such a
proposal, which would entail the data structures themselves, arithmetic
operations, and interoperation between different numeric types to form a
numerical tower of sorts?

Hi Austin,

We are interested in improving our numerics support, and we are
definitely interested in hearing your ideas in this space. You don't
have to write a full proposal though. Just an extended email to
swift-evolution would be a good start.

You can find the current prototype for library support for integers
here:
https://github.com/apple/swift/blob/master/test/Prototypes/Integers.swift.gyb

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Dmitri Gribenko) #6

Integer is intended to be used by application developers, and most of the
arithmetic/comparison functionality exposed by the stdlib deals with
arguments and return values of type Integer.

So one would use Integer, which is capable of representing arbitrary
precision integers, most of the time? We have considered this in the
past. The concern is that the branches that this introduces
everywhere and the code bloat wouldn't allow Swift to achieve C-like
performance.

We are considering adding an arbitrary precision integer type, though.

A useful compiler support feature might be a "BigIntegerLiteralConvertible"
protocol, which allows literal integers out of the range of Ints to be
assigned to Integer values. Swift can already tell if an integer literal is
out of range (e.g. "let x : Int8 = 123456"), so there is some precedent.

Swift's integer literal convertible protocol supports integers up to
2048 bits. This is sufficient for all practical purposes, I think.

Rational numbers are represented by the Rational struct which encapsulates
two Integers, the numerator and denominator. Rationals can be conditionally
constructed explicitly from two Integers (as long as the denominator isn't
0), or from a single Integer (all Integers are Rationals, but the opposite
is not true).

Yep, this is pretty standard. How do you propose to model "Integers
are Rationals" in Swift?

A good invariant for Rationals might be having them always
represented in the most simplified form - for example, Rational(2, 6) should
be represented internally as 1/3 when constructed.

This has performance tradeoffs. What do other libraries and languages do?

Future topics to explore include complex numbers, arbitrary-precision
floating-point numbers, and fixed-precision and/or decimal number types.

What about protocols, operations and algorithms?

Dmitri

···

On Thu, Dec 3, 2015 at 9:22 PM, Austin Zheng <austinzheng@gmail.com> wrote:

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Lily Ballard) #7

I know Haskell always reduces Rationals to their reduced form. This does have performance implications, but not doing so has surprising consequences for operations you perform on them. For example, it’s reasonable to expect that Rational(2,6) == Rational(1,3), but implementing that without reduced Rationals pretty much requires reducing them on the fly. The alternative, of saying they’re not equal, would probably surprise most people.

-Kevin Ballard

···

On Dec 3, 2015, at 9:48 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:

A good invariant for Rationals might be having them always
represented in the most simplified form - for example, Rational(2, 6) should
be represented internally as 1/3 when constructed.

This has performance tradeoffs. What do other libraries and languages do?


(Austin Zheng) #8

Clojure also performs automatic reduction of rational numbers. However, the
source code seems to indicate that reduction is built into the definitions
of the methods that perform arithmetic on rational numbers, and the "Ratio"
class that implements rational number support does not do any reduction
itself.

(c.f.
https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Numbers.java,
ll. 350-364, 704-727, et al)

From a semantic standpoint, I would be very surprised if e.g. 2/6 and 1/3

were not considered equal, or for that matter if they weren't completely
interchangeable.

- Austin

···

On Thu, Dec 3, 2015 at 11:21 PM, Kevin Ballard <kevin@sb.org> wrote:

On Dec 3, 2015, at 9:48 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:
>
>> A good invariant for Rationals might be having them always
>> represented in the most simplified form - for example, Rational(2, 6)
should
>> be represented internally as 1/3 when constructed.
>
> This has performance tradeoffs. What do other libraries and languages
do?

I know Haskell always reduces Rationals to their reduced form. This does
have performance implications, but not doing so has surprising consequences
for operations you perform on them. For example, it’s reasonable to expect
that Rational(2,6) == Rational(1,3), but implementing that without reduced
Rationals pretty much requires reducing them on the fly. The alternative,
of saying they’re not equal, would probably surprise most people.

-Kevin Ballard


(Vinicius Vendramini) #9

If Swift’s Ints may go up to 2048 bits, I’d agree that they probably cover most cases. That’s not to say a big int would be useless, just that I think it should be separate, meant to be used by those who actually need it rather than interfering with normal Int logic, which is likely to be used more often.

···

On Dec 4, 2015, at 2:45 AM, Austin Zheng <austinzheng@gmail.com> wrote:

Clojure also performs automatic reduction of rational numbers. However, the source code seems to indicate that reduction is built into the definitions of the methods that perform arithmetic on rational numbers, and the "Ratio" class that implements rational number support does not do any reduction itself.

(c.f. https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Numbers.java, ll. 350-364, 704-727, et al)

From a semantic standpoint, I would be very surprised if e.g. 2/6 and 1/3 were not considered equal, or for that matter if they weren't completely interchangeable.

- Austin

On Thu, Dec 3, 2015 at 11:21 PM, Kevin Ballard <kevin@sb.org <mailto:kevin@sb.org>> wrote:
On Dec 3, 2015, at 9:48 PM, Dmitri Gribenko <gribozavr@gmail.com <mailto:gribozavr@gmail.com>> wrote:
>
>> A good invariant for Rationals might be having them always
>> represented in the most simplified form - for example, Rational(2, 6) should
>> be represented internally as 1/3 when constructed.
>
> This has performance tradeoffs. What do other libraries and languages do?

I know Haskell always reduces Rationals to their reduced form. This does have performance implications, but not doing so has surprising consequences for operations you perform on them. For example, it’s reasonable to expect that Rational(2,6) == Rational(1,3), but implementing that without reduced Rationals pretty much requires reducing them on the fly. The alternative, of saying they’re not equal, would probably surprise most people.

-Kevin Ballard

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dmitri Gribenko) #10

Swift's 'Int's are pointer-sized. Swift's integer literals can be up
to 2048 bits, which allows one to write types (e.g., BigInt) that can
be initialized from large literals.

Dmitri

···

On Fri, Dec 4, 2015 at 6:13 AM, Vinicius Vendramini <vinivendra@gmail.com> wrote:

If Swift’s Ints may go up to 2048 bits, I’d agree that they probably cover most cases. That’s not to say a big int would be useless, just that I think it should be separate, meant to be used by those who actually need it rather than interfering with normal Int logic, which is likely to be used more often.

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/