protocol-oriented integers (take 2)

Evolution Discussion
81

While I applaud the ingenuity behind this solution, it seems an odd thing to do, and I wonder if it's something that might become obsolete in the future?

I mean, since the purpose of this is just to select the correct method declaration, then the more "correct" way to do this would be using labelled Void arguments, but of course these aren't as neat right now:

  protocol FixedWithInteger {
    func adding(_ other:Self, withOverflow:Void) -> (partialValue:Self, overflow:ArithmeticOverflow)
  }

  x.add(y, withOverflow:())

This uses the method's label to avoid the need to declare enums purely for selection. The problem is of course that the syntax isn't that great because of the extraneous :(). It would be better if we could just do x.add(y, withOverflow:), but that might be ambiguous because using labels without values is how we select labelled functions (e.g- let f = adding(:withOverflow:) would select the method).

I'm just wondering if there's a change to labelled void arguments that we could make that would allow that style to be used instead? It just feels to me like using a labelled Void is the "proper" way to achieve what is needed, and that using enums just because it isn't possible right now is something that could become obsolete in future.

- Haravikk

···

On 31 Jan 2017, at 20:53, Max Moiseev via swift-evolution <swift-evolution@swift.org> wrote:

Hi Brent,

Thanks a lot for your suggestions! After having discussed them with Dave, we came up with the following design that I personally like a lot.

enum Overflowing { case .withOverflow }
enum FullWidth { case .fullWidth }

protocol FixedWidthInteger {
func adding(_ other: Self, _: Overflowing) -> (partialValue: Self, overflow: ArithmeticOverflow)
func subtracting(_ other: Self, _: Overflowing) -> (partialValue: Self, overflow: ArithmeticOverflow)
func multiplied(by other: Self, _: Overflowing) -> (partialValue: Self, overflow: ArithmeticOverflow)
func divided(by other: Self, _: Overflowing) -> (partialValue: Self, overflow: ArithmeticOverflow)

func multiplied(by other: Self, _: FullWidth) -> DoubleWidth<Self>
func dividing(_ other: DoubleWidth<Self>, _: FullWidth) -> (quotient: Self, remainder: Self)
}

Call sites would look like:

x.multiplied(by: y, .withOverflow) and x.multiplied(by: y, .fullWidth)

a little different for the division:

x.divided(by: y, .withOverflow) and y.dividing(x, .fullWidth)

Note the inverse-ness of `dividing`, but the lack of the argument label makes it quite natural.

82

What about taking a mathematical approach to numbers?

protocol Group : Equatable {
    static var zero: Self { get }
    static func + (Self, Self) -> Self
    static func += (inout Self, Self)
    static func - (Self, Self) -> Self
    static func -= (inout Self, Self)
    static prefix func - (Self) -> Self
}

protocol Ring : Group {
    static var one: Self { get }
    static func * (Self, Self) -> Self
    static func *= (inout Self, Self)
    func tryDivide(by: Self) -> Self?
    func tryInvert() -> Self?
}

protocol Field : Ring {
    static func / (Self, Self) -> Self
    static func /= (inout Self, Self)
    var inverted: Self { get }
}

protocol VectorSpace : Group {
    associatedtype Scalar : Field
    static func * (Self, Scalar) -> Self
    static func *= (inout Self, Scalar) -> Self
    static func / (Self, Scalar) -> Self
    static func /= (inout Self, Scalar) -> Self
    static func * (Scalar, Self) -> Self
}

The first test for the inclusion of any protocol in the standard library
is: “what generic algorithm that uses this protocol as a constraint
would be appropriate for inclusion in the standard library?”

I don't think we have a use for any of the above directly in the
standard library. All the generic algorithms I know of that would be
appropriate to those protocols are part of some specialized domain that
should have its own library built on top of the Swift standard lib.

···

on Sun Jan 15 2017, Anton Zhilin <swift-evolution@swift.org> wrote:

Detalization of mathematical terminology will be determined by what kind of
types we have in the standard library. Integer types are rings (except for
overflow), floating-point types are fields (except for precision), point
types are linear spaces, so I thought the abstractions above are the bare
minimum.

Unfortunately, Swift doesn’t have rename operations for protocol
requirements, so we can’t express groups that use operations other than +
and -. What we can do is to include an adapter to wrap current instance in
an additive group interface:

struct MultiplicativeGroupAdapter<T: Field> : Group {
    // ...
}

extension Field {
    var multiplicativeGroup: MultiplicativeGroupAdapter<Self>
}

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

--
-Dave

83

There _may_ be value in recognizing the distinction between rings and
fields, perhaps? Just as the FP protocols make room for people to implement
their own decimal FP types, and just as you're trying to make Arithmetic
accommodate complex numbers, the distinction would allow someone to write
algorithms generic over rationals and reals (i.e. fields). Being able to
represent exact fractions isn't so terribly niche, and I think the design
wouldn't be terribly complicated by its accommodation:

// rename Arithmetic to Ring
// it's acceptable to omit `.one` from Ring, though some may call that a
Pseudoring
// consider omitting division from Ring and pushing it down to
BinaryInteger and Field

protocol BinaryInteger : Ring { ... }

protocol Field : Ring {
  static var one { get }
  static func / (Self, Self) -> Self
  static func /= (inout Self, Self)
  var inverted: Self { get } // default impl: .one / self
}

protocol FloatingPoint : Field { ... }
// rational number types and complex number types
// would also conform to Field

What about taking a mathematical approach to numbers?

protocol Group : Equatable {

    static var zero: Self { get }

    static func + (Self, Self) -> Self

    static func += (inout Self, Self)

    static func - (Self, Self) -> Self

    static func -= (inout Self, Self)

    static prefix func - (Self) -> Self

}

protocol Ring : Group {

    static var one: Self { get }

    static func * (Self, Self) -> Self

    static func *= (inout Self, Self)

    func tryDivide(by: Self) -> Self?

    func tryInvert() -> Self?

}

protocol Field : Ring {

    static func / (Self, Self) -> Self

    static func /= (inout Self, Self)

    var inverted: Self { get }

}

protocol VectorSpace : Group {

    associatedtype Scalar : Field

    static func * (Self, Scalar) -> Self

    static func *= (inout Self, Scalar) -> Self

    static func / (Self, Scalar) -> Self

    static func /= (inout Self, Scalar) -> Self

    static func * (Scalar, Self) -> Self

}

The first test for the inclusion of any protocol in the standard library

is: “what generic algorithm that uses this protocol as a constraint

would be appropriate for inclusion in the standard library?”

I don't think we have a use for any of the above directly in the

standard library. All the generic algorithms I know of that would be

appropriate to those protocols are part of some specialized domain that

should have its own library built on top of the Swift standard lib.

Detalization of mathematical terminology will be determined by what kind

of

···

On Sun, Jan 15, 2017 at 09:14 Dave Abrahams via swift-evolution < swift-evolution@swift.org> wrote:
on Sun Jan 15 2017, Anton Zhilin <swift-evolution@swift.org> wrote:

types we have in the standard library. Integer types are rings (except for

overflow), floating-point types are fields (except for precision), point

types are linear spaces, so I thought the abstractions above are the bare

minimum.

Unfortunately, Swift doesn’t have rename operations for protocol

requirements, so we can’t express groups that use operations other than +

and -. What we can do is to include an adapter to wrap current instance in

an additive group interface:

struct MultiplicativeGroupAdapter<T: Field> : Group {

    // ...

}

extension Field {

    var multiplicativeGroup: MultiplicativeGroupAdapter<Self>

}

​

_______________________________________________

swift-evolution mailing list

swift-evolution@swift.org

https://lists.swift.org/mailman/listinfo/swift-evolution

--

-Dave

_______________________________________________

swift-evolution mailing list

swift-evolution@swift.org

https://lists.swift.org/mailman/listinfo/swift-evolution

84

"Mathematically correct" integers behave just like Int in that there is not
a multiplicative inverse. What we're trying to do here is to determine how
much of what we know about mathematics is usefully modeled in the standard
library. The answer is not zero, because there is more than just counting
that people do with integers.

···

On Sun, Jan 15, 2017 at 17:54 David Sweeris <davesweeris@mac.com> wrote:

On Jan 15, 2017, at 17:19, Jacob Bandes-Storch via swift-evolution < > swift-evolution@swift.org> wrote:

On Sun, Jan 15, 2017 at 2:42 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Sun, Jan 15, 2017 at 3:29 PM, Jacob Bandes-Storch via swift-evolution < > swift-evolution@swift.org> wrote:

[ proposal link:
Protocol-oriented integers (take 2) · GitHub ]

On Sat, Jan 14, 2017 at 4:55 PM, Dave Abrahams via swift-evolution < > swift-evolution@swift.org> wrote:

Responding to both Jacob and Xiaodi here; thanks very much for your
feedback!

on Sat Jan 14 2017, Xiaodi Wu <swift-evolution@swift.org> wrote:
> I think, in the end, it's the _name_ that could use improvement here. As
> the doc comments say, `Arithmetic` is supposed to provide a "suitable
basis
> for arithmetic on scalars"--perhaps `ScalarArithmetic` might be more
> appropriate? It would make it clear that `CGVector` is not meant to be a
> conforming type.

We want Arithmetic to be able to handle complex numbers. Whether Scalar
would be appropriate in that case sort of depends on what the implied
field is, right?

I think "scalar" is an appropriate term for any field. The scalar-ness
usually comes into play when it's used in a vector space, but using the
term alone doesn't bother me.

It's true that CGPoint and CGVector have no obvious sensible
interpretation of "42", and that's unfortunate. The problem with
protocols for algebraic structures is that there's an incredibly
complicated lattice (see figures 3.1, 3.2 in
ftp://jcmc.indiana.edu/pub/techreports/TR638.pdf) and we don't want to
shove all of those protocols into the standard library (especially not
prematurely) but each requirement you add to a more-coarsely aggregated
protocol like Arithmetic will make it ineligible for representing some
important type.

Yep, it is quite complicated, and I understand not wanting to address all
that right now; calling it ScalarArithmetic seems appropriate to clarify
the limitations. FieldArithmetic might also be appropriate, but is less
clear (+ see below about quaternions).

Daves Sweeris and Abrahams wrote:

> > I was under the impression that complex numbers are scalar numbers...
although maybe not since once you get past, I think quaternions, you start
losing division and eventually multiplication, IIRC. (I hate it when two of
my recollections try to conflict with each other.)
>
> Well, you can view them as 2d vectors, so I'm not sure. We need more of
a numerics expert than I am to weigh in here.

But complex numbers have multiplication and division operations defined
(they form a field), unlike regular vectors in R². Meaning you can have a
vector space over the field of complex numbers.

You still have multiplication and division past quaternions, but the
quaternions are *not commutative*. This isn't really a problem in Swift,
since the compiler never allows you to write an expression where the order
of arguments to an operator is ambiguous. This means they are *not a
field*, just a division ring <https://en.wikipedia.org/wiki/Division_ring&gt; (a
field is a commutative division ring). (I believe you can't technically
have a vector space over a non-commutative ring; the generalization would
be a module <https://en.wikipedia.org/wiki/Module_(mathematics)&gt;\.
That's probably an argument for the name ScalarArithmetic over
FieldArithmetic.)

Hmm, the issue is that the integers are not a field. So, if we're going to
have it all modeled by one protocol, maybe neither is the best term.

Eurgh. That's true. Appropriate mathematical terms go out the window when
"division" doesn't actually produce a multiplicative inverse.

BasicArithmetic?

I was thinking something similar... Could we just rename Int/UInt to
Counter/UnsignedCounter, and leave all these "mathematically correct"
protocols and types to mathematically correct numeric libraries?

- Dave Sweeris

85

I mean that `OptionSet.RawValue` currently has to conform to
`BitwiseOperations`,

Actually it doesn't. You just have to implement these yourself in that
case:

extension OptionSet where Self.RawValue : BitwiseOperations {

Oh, I didn't realize it was implemented that way (and was going to stay that way). Thanks for the correction.

but would now need to conform to `BinaryInteger` (or a sub-protocol).

Does that limit you in some useful way?

Well, a type like `Data` could be usefully conformed to `BitwiseOperations`, which would permit its use as a variable-sized bit buffer, but conforming it to `BinaryInteger` would make no sense and might cause mis-conformances. (For instance, `BinaryInteger.Type.+` and the `+` operator that works on `RangeReplaceableCollection`s like `Data` are incompatible). You would instead have to use a big-int type, but it's apparently common for those to be implemented in ways that make bitwise operations slow.

However, unless I'm mistaken, I believe a `BitwiseOperations` protocol could be extracted from `BinaryInteger` later (right? Resilience permits you to add a new super-protocol and move some of the sub-protocol's requirements up into it?), so we can pick that up later.

···

On Jan 30, 2017, at 11:25 AM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

--
Brent Royal-Gordon
Architechies

86

Hi Brent,

Thanks a lot for your suggestions! After having discussed them with Dave,
we came up with the following design that I personally like a lot.

enum Overflowing { case .withOverflow }

I really dislike “Overflowing”; it seems to imply that there *will* be
overflow. How about

  enum ReportingOverflow { case .reportingOverflow }

enum FullWidth { case .fullWidth }

protocol FixedWidthInteger {
  func adding(_ other: Self, _: Overflowing) -> (partialValue: Self,
overflow: ArithmeticOverflow)
  func subtracting(_ other: Self, _: Overflowing) -> (partialValue: Self,
overflow: ArithmeticOverflow)
  func multiplied(by other: Self, _: Overflowing) -> (partialValue: Self,
overflow: ArithmeticOverflow)
  func divided(by other: Self, _: Overflowing) -> (partialValue: Self,
overflow: ArithmeticOverflow)

  func multiplied(by other: Self, _: FullWidth) -> DoubleWidth<Self>
  func dividing(_ other: DoubleWidth<Self>, _: FullWidth) -> (quotient:
Self, remainder: Self)
}

Call sites would look like:

x.multiplied(by: y, .withOverflow) and x.multiplied(by: y, .fullWidth)

a little different for the division:

x.divided(by: y, .withOverflow) and y.dividing(x, .fullWidth)

Note the inverse-ness of `dividing`, but the lack of the argument label
makes it quite natural.

This is an improvement in many ways, I think. However `.fullWidth` vs.
`DoubleWidth` seems less than ideal.

IMO .fullWidth is an improvement over .DoubleWidth, at least for
multiplication. The latter just repeats type information, where the
former tells you something about *how* the operation is to be performed.

I get that you can't reuse `DoubleWidth` for the single-case enum, but
still.

Now that * and &* no longer used the `multiplied(by:)` spelling, is there a
reason not to take advantage of overloading on the return value for these
very specialized methods?

protocol FixedWidthInteger {
  typealias OverflowFlagging = (partialValue: Self, overflow:
ArithmeticOverflow)
  func multiplied(by other: Self) -> OverflowFlagging
  func multiplied(by other: Self) -> DoubleWidth<Self>
}

You'd then write `x.multiplied(by: y) as OverflowFlagging` and
`x.multiplied(by: y) as DoubleWidth`

It's too subtle, IMO, and any place that type context is available to
disambiguate the result, it

             x.multiplied(by: y)

will look like it should be rewritten as

             x * y

With respect to `dividing` vs `divided`, IMO it'd be a tricky name,
especially for non-English speakers. The "ed/ing" rule has these suffixes
used pretty interchangeably to indicate a non-mutating operation, depending
on the vagaries of the English language, but we've never had an "ed" and an
"ing" used for completely different things on the same type, as far as I'm
aware. Why not move the `dividing` version to DoubleWidth, where it can be
a proper `divided(by:)`?

Max and I discussed this; I'll let him answer.

···

on Tue Jan 31 2017, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:

On Tue, Jan 31, 2017 at 2:53 PM, Max Moiseev <moiseev@apple.com> wrote:

--
-Dave

87

Why didn't I think of that? :-)

···

on Tue Jan 31 2017, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:

Why not move the `dividing` version to DoubleWidth, where it can be
a proper `divided(by:)`?

--
-Dave

88

There _may_ be value in recognizing the distinction between rings and
fields, perhaps? Just as the FP protocols make room for people to implement
their own decimal FP types, and just as you're trying to make Arithmetic
accommodate complex numbers, the distinction would allow someone to write
algorithms generic over rationals and reals (i.e. fields). Being able to
represent exact fractions isn't so terribly niche, and I think the design
wouldn't be terribly complicated by its accommodation:

// rename Arithmetic to Ring
// it's acceptable to omit `.one` from Ring, though some may call that a
Pseudoring
// consider omitting division from Ring and pushing it down to
BinaryInteger and Field

protocol BinaryInteger : Ring { ... }

protocol Field : Ring {
  static var one { get }
  static func / (Self, Self) -> Self
  static func /= (inout Self, Self)
  var inverted: Self { get } // default impl: .one / self
}

protocol FloatingPoint : Field { ... }
// rational number types and complex number types
// would also conform to Field

What generic algorithms would this enable? Would they be appropriate
for the standard library (as opposed to some more specialized numerics
library)?

···

on Sun Jan 15 2017, Xiaodi Wu <swift-evolution@swift.org> wrote:

On Sun, Jan 15, 2017 at 09:14 Dave Abrahams via swift-evolution < > swift-evolution@swift.org> wrote:

on Sun Jan 15 2017, Anton Zhilin <swift-evolution@swift.org> wrote:

What about taking a mathematical approach to numbers?

protocol Group : Equatable {

    static var zero: Self { get }

    static func + (Self, Self) -> Self

    static func += (inout Self, Self)

    static func - (Self, Self) -> Self

    static func -= (inout Self, Self)

    static prefix func - (Self) -> Self

}

protocol Ring : Group {

    static var one: Self { get }

    static func * (Self, Self) -> Self

    static func *= (inout Self, Self)

    func tryDivide(by: Self) -> Self?

    func tryInvert() -> Self?

}

protocol Field : Ring {

    static func / (Self, Self) -> Self

    static func /= (inout Self, Self)

    var inverted: Self { get }

}

protocol VectorSpace : Group {

    associatedtype Scalar : Field

    static func * (Self, Scalar) -> Self

    static func *= (inout Self, Scalar) -> Self

    static func / (Self, Scalar) -> Self

    static func /= (inout Self, Scalar) -> Self

    static func * (Scalar, Self) -> Self

}

The first test for the inclusion of any protocol in the standard library

is: “what generic algorithm that uses this protocol as a constraint

would be appropriate for inclusion in the standard library?”

I don't think we have a use for any of the above directly in the

standard library. All the generic algorithms I know of that would be

appropriate to those protocols are part of some specialized domain that

should have its own library built on top of the Swift standard lib.

Detalization of mathematical terminology will be determined by what kind

of

types we have in the standard library. Integer types are rings (except for

overflow), floating-point types are fields (except for precision), point

types are linear spaces, so I thought the abstractions above are the bare

minimum.

Unfortunately, Swift doesn’t have rename operations for protocol

requirements, so we can’t express groups that use operations other than +

and -. What we can do is to include an adapter to wrap current instance in

an additive group interface:

struct MultiplicativeGroupAdapter<T: Field> : Group {

    // ...

}

extension Field {

    var multiplicativeGroup: MultiplicativeGroupAdapter<Self>

}

​

_______________________________________________

swift-evolution mailing list

swift-evolution@swift.org

https://lists.swift.org/mailman/listinfo/swift-evolution

--

-Dave

_______________________________________________

swift-evolution mailing list

swift-evolution@swift.org

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

--
-Dave

89

> There _may_ be value in recognizing the distinction between rings and
> fields, perhaps? Just as the FP protocols make room for people to
implement
> their own decimal FP types, and just as you're trying to make Arithmetic
> accommodate complex numbers, the distinction would allow someone to write
> algorithms generic over rationals and reals (i.e. fields). Being able to
> represent exact fractions isn't so terribly niche, and I think the design
> wouldn't be terribly complicated by its accommodation:
>
> ```
> // rename Arithmetic to Ring
> // it's acceptable to omit `.one` from Ring, though some may call that a
> Pseudoring
> // consider omitting division from Ring and pushing it down to
> BinaryInteger and Field
>
> protocol BinaryInteger : Ring { ... }
>
> protocol Field : Ring {
> static var one { get }
> static func / (Self, Self) -> Self
> static func /= (inout Self, Self)
> var inverted: Self { get } // default impl: .one / self
> }
>
> protocol FloatingPoint : Field { ... }
> // rational number types and complex number types
> // would also conform to Field
> ```

What generic algorithms would this enable?

For one, anything to do with dividing into equal parts could be generic
over floating point, rational, and even complex numbers, but you probably
wouldn't want to include integer types in such an algorithm.

Would they be appropriate
for the standard library (as opposed to some more specialized numerics
library)?

The issue is that it's not terribly ergonomic to relegate `Field` to a
specialized library because one cannot retroactively conform
`FloatingPoint` to `Field`.

···

On Sun, Jan 15, 2017 at 3:27 PM, Dave Abrahams via swift-evolution < swift-evolution@swift.org> wrote:

on Sun Jan 15 2017, Xiaodi Wu <swift-evolution@swift.org> wrote:

On Sun, Jan 15, 2017 at 09:14 Dave Abrahams via swift-evolution < > > swift-evolution@swift.org> wrote:
>
> on Sun Jan 15 2017, Anton Zhilin <swift-evolution@swift.org> wrote:
>
>> What about taking a mathematical approach to numbers?
>
>>
>
>> protocol Group : Equatable {
>
>> static var zero: Self { get }
>
>> static func + (Self, Self) -> Self
>
>> static func += (inout Self, Self)
>
>> static func - (Self, Self) -> Self
>
>> static func -= (inout Self, Self)
>
>> static prefix func - (Self) -> Self
>
>> }
>
>>
>
>> protocol Ring : Group {
>
>> static var one: Self { get }
>
>> static func * (Self, Self) -> Self
>
>> static func *= (inout Self, Self)
>
>> func tryDivide(by: Self) -> Self?
>
>> func tryInvert() -> Self?
>
>> }
>
>>
>
>> protocol Field : Ring {
>
>> static func / (Self, Self) -> Self
>
>> static func /= (inout Self, Self)
>
>> var inverted: Self { get }
>
>> }
>
>>
>
>> protocol VectorSpace : Group {
>
>> associatedtype Scalar : Field
>
>> static func * (Self, Scalar) -> Self
>
>> static func *= (inout Self, Scalar) -> Self
>
>> static func / (Self, Scalar) -> Self
>
>> static func /= (inout Self, Scalar) -> Self
>
>> static func * (Scalar, Self) -> Self
>
>> }
>
> The first test for the inclusion of any protocol in the standard library
>
> is: “what generic algorithm that uses this protocol as a constraint
>
> would be appropriate for inclusion in the standard library?”
>
> I don't think we have a use for any of the above directly in the
>
> standard library. All the generic algorithms I know of that would be
>
> appropriate to those protocols are part of some specialized domain that
>
> should have its own library built on top of the Swift standard lib.
>
>> Detalization of mathematical terminology will be determined by what kind
> of
>
>> types we have in the standard library. Integer types are rings (except
for
>
>> overflow), floating-point types are fields (except for precision), point
>
>> types are linear spaces, so I thought the abstractions above are the
bare
>
>> minimum.
>
>>
>
>> Unfortunately, Swift doesn’t have rename operations for protocol
>
>> requirements, so we can’t express groups that use operations other than
+
>
>> and -. What we can do is to include an adapter to wrap current instance
in
>
>> an additive group interface:
>
>>
>
>> struct MultiplicativeGroupAdapter<T: Field> : Group {
>
>> // ...
>
>> }
>
>>
>
>> extension Field {
>
>> var multiplicativeGroup: MultiplicativeGroupAdapter<Self>
>
>> }
>
>>
>
>> ​
>
>> _______________________________________________
>
>> swift-evolution mailing list
>
>> swift-evolution@swift.org
>
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>>
>
> --
>
> -Dave
>
> _______________________________________________
>
> swift-evolution mailing list
>
> swift-evolution@swift.org
>
> https://lists.swift.org/mailman/listinfo/swift-evolution
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>

--
-Dave

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

90

> There _may_ be value in recognizing the distinction between rings and
> fields, perhaps? Just as the FP protocols make room for people to
implement
> their own decimal FP types, and just as you're trying to make Arithmetic
> accommodate complex numbers, the distinction would allow someone to write
> algorithms generic over rationals and reals (i.e. fields). Being able to
> represent exact fractions isn't so terribly niche, and I think the design
> wouldn't be terribly complicated by its accommodation:
>
> ```
> // rename Arithmetic to Ring
> // it's acceptable to omit `.one` from Ring, though some may call that a
> Pseudoring
> // consider omitting division from Ring and pushing it down to
> BinaryInteger and Field
>
> protocol BinaryInteger : Ring { ... }
>
> protocol Field : Ring {
> static var one { get }
> static func / (Self, Self) -> Self
> static func /= (inout Self, Self)
> var inverted: Self { get } // default impl: .one / self
> }
>
> protocol FloatingPoint : Field { ... }
> // rational number types and complex number types
> // would also conform to Field
> ```

What generic algorithms would this enable?

For one, anything to do with dividing into equal parts

For example...?

could be generic over floating point, rational, and even complex
numbers, but you probably wouldn't want to include integer types in
such an algorithm.

Would they be appropriate
for the standard library (as opposed to some more specialized numerics
library)?

The issue is that it's not terribly ergonomic to relegate `Field` to a
specialized library because one cannot retroactively conform
`FloatingPoint` to `Field`.

I don't think this is an important enough concern to justify adding
protocols to the standard library. The number of types one has to
individually make conform to Field is probably going to remain small.

Show-me-the-mone^Walgorithms-ly y'rs,

···

on Sun Jan 15 2017, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:

On Sun, Jan 15, 2017 at 3:27 PM, Dave Abrahams via swift-evolution < > swift-evolution@swift.org> wrote:

on Sun Jan 15 2017, Xiaodi Wu <swift-evolution@swift.org> wrote:

--
-Dave

91

"Mathematically correct" integers behave just like Int in that there is
not a multiplicative inverse. What we're trying to do here is to determine
how much of what we know about mathematics is usefully modeled in the
standard library. The answer is not zero, because there is more than just
counting that people do with integers.

It's an interesting problem... When I was in school, "integer" division
"returned" a "quotient and remainder", a "fraction" (which, occasionally,
could be simplified to just an integer), or a "real". We never talked about
division in the context of "(Int, Int) -> Int", though. OTOH, I never took
any math classes past Differential Equations or Linear Algebra, either...
I'm *aware* of areas of math where you formally restrict yourself to the
kind of "(Int, Int) -> Int" operations we're doing here, but I don't
really know much about it. Is division even well-defined in that context?

- Dave Sweeris

I'm no mathematician, and I'm not sure how to tackle the question of
"well-defined." Hopefully someone who is more knowledgable can chime in
here.

But I'll have a go at replying to your point as it relates to the practical
issue here. Two Int values can be "divided" to produce another Int, and
that gives a predictable and well-understood result. It's an operation
that's always going to be there--first, because it'd be insane to remove it
since much working code relies on it, and second, because we're only
re-designing integer protocols and not the concrete types. However, it _is_
true that such an operation has very different semantics from division as
you learned it in math.

This is why I'm advocating for perhaps another look at the top of this
integer protocol hierarchy. At the moment, `Arithmetic` offers reasonable
semantic guarantees for a lot of things, but `/` has different semantics
for integer types and floating point types

Well, that really depends on how closely you look. From one
point-of-view, floating point division and integer division *both*
produce approximate results.

and is really closer to just syntax. Other mathematical types--which
certainly the stdlib doesn't have to offer, but the stdlib protocol
hierarchy shouldn't preclude their conformance to relevant protocols
if it's possible--such as fractions and complex numbers, share with
floating point types the semantics of `/` that qualify these types as
fields. Dave A's question as to practical uses can probably best be
answered in this way: to the extent that any generic algorithm relies
on `/` having semantics and can be applied to fractions and real
numbers, it would be useful to distinguish such an operation from
integer "division."

That's not a bad answer. Ruminating on this...

···

on Sun Jan 15 2017, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:

On Sun, Jan 15, 2017 at 6:42 PM, David Sweeris <davesweeris@mac.com> wrote:

On Jan 15, 2017, at 18:02, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

--
-Dave

92

It's an interesting problem... When I was in school, "integer" division "returned" a "quotient and remainder", a "fraction" (which, occasionally, could be simplified to just an integer), or a "real". We never talked about division in the context of "(Int, Int) -> Int", though. OTOH, I never took any math classes past Differential Equations or Linear Algebra, either... I'm aware of areas of math where you formally restrict yourself to the kind of "(Int, Int) -> Int" operations we're doing here, but I don't really know much about it. Is division even well-defined in that context?

- Dave Sweeris

···

Sent from my iPhone

On Jan 15, 2017, at 18:02, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

"Mathematically correct" integers behave just like Int in that there is not a multiplicative inverse. What we're trying to do here is to determine how much of what we know about mathematics is usefully modeled in the standard library. The answer is not zero, because there is more than just counting that people do with integers.

93

>
>>
>>
>>
>>
>>
>> "Mathematically correct" integers behave just like Int in that there is
>> not a multiplicative inverse. What we're trying to do here is to determine
>> how much of what we know about mathematics is usefully modeled in the
>> standard library. The answer is not zero, because there is more than just
>> counting that people do with integers.
>>
>>
>> It's an interesting problem... When I was in school, "integer" division
>> "returned" a "quotient and remainder", a "fraction" (which, occasionally,
>> could be simplified to just an integer), or a "real". We never talked about
>> division in the context of "(Int, Int) -> Int", though. OTOH, I never took
>> any math classes past Differential Equations or Linear Algebra, either...
>> I'm *aware* of areas of math where you formally restrict yourself to the
>> kind of "(Int, Int) -> Int" operations we're doing here, but I don't
>> really know much about it. Is division even well-defined in that context?
>>
>> - Dave Sweeris
>>
>
> I'm no mathematician, and I'm not sure how to tackle the question of
> "well-defined." Hopefully someone who is more knowledgable can chime in
> here.
>
> But I'll have a go at replying to your point as it relates to the practical
> issue here. Two Int values can be "divided" to produce another Int, and
> that gives a predictable and well-understood result. It's an operation
> that's always going to be there--first, because it'd be insane to remove it
> since much working code relies on it, and second, because we're only
> re-designing integer protocols and not the concrete types. However, it _is_
> true that such an operation has very different semantics from division as
> you learned it in math.
>
> This is why I'm advocating for perhaps another look at the top of this
> integer protocol hierarchy. At the moment, `Arithmetic` offers reasonable
> semantic guarantees for a lot of things, but `/` has different semantics
> for integer types and floating point types

Well, that really depends on how closely you look. From one
point-of-view, floating point division and integer division *both*
produce approximate results.

Yes, from a certain point of view. I remember we did discuss this at one point on the list; I asked whether FloatingPoint was meant to model only the countable set of representable values or whether it was meant to model the uncountable set of reals. The answer was that here in Swift-land we're trying to model the latter, and the approximate result is an artifact of the imperfect modeling. Integer division, however, is not such an artifact, but fundamentally a different operation.

That's right. Thanks for keeping us honest and reminding us of our guiding stars. :ok_hand:t2:

···

Sent from my moss-covered three-handled family gradunza

On Jan 15, 2017, at 5:29 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Sun, Jan 15, 2017 at 7:24 PM, Dave Abrahams <dabrahams@apple.com> wrote:
on Sun Jan 15 2017, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:
> On Sun, Jan 15, 2017 at 6:42 PM, David Sweeris <davesweeris@mac.com> wrote:
>> On Jan 15, 2017, at 18:02, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

> and is really closer to just syntax. Other mathematical types--which
> certainly the stdlib doesn't have to offer, but the stdlib protocol
> hierarchy shouldn't preclude their conformance to relevant protocols
> if it's possible--such as fractions and complex numbers, share with
> floating point types the semantics of `/` that qualify these types as
> fields. Dave A's question as to practical uses can probably best be
> answered in this way: to the extent that any generic algorithm relies
> on `/` having semantics and can be applied to fractions and real
> numbers, it would be useful to distinguish such an operation from
> integer "division."

That's not a bad answer. Ruminating on this...

--
-Dave

94

I'm no mathematician, and I'm not sure how to tackle the question of
"well-defined." Hopefully someone who is more knowledgable can chime in
here.

But I'll have a go at replying to your point as it relates to the practical
issue here. Two Int values can be "divided" to produce another Int, and
that gives a predictable and well-understood result. It's an operation
that's always going to be there--first, because it'd be insane to remove it
since much working code relies on it, and second, because we're only
re-designing integer protocols and not the concrete types. However, it _is_
true that such an operation has very different semantics from division as
you learned it in math.

This is why I'm advocating for perhaps another look at the top of this
integer protocol hierarchy. At the moment, `Arithmetic` offers reasonable
semantic guarantees for a lot of things, but `/` has different semantics
for integer types and floating point types and is really closer to just
syntax. Other mathematical types--which certainly the stdlib doesn't have
to offer, but the stdlib protocol hierarchy shouldn't preclude their
conformance to relevant protocols if it's possible--such as fractions and
complex numbers, share with floating point types the semantics of `/` that
qualify these types as fields. Dave A's question as to practical uses can
probably best be answered in this way: to the extent that any generic
algorithm relies on `/` having semantics and can be applied to fractions
and real numbers, it would be useful to distinguish such an operation from
integer "division."

···

On Sun, Jan 15, 2017 at 6:42 PM, David Sweeris <davesweeris@mac.com> wrote:

Sent from my iPhone
On Jan 15, 2017, at 18:02, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

"Mathematically correct" integers behave just like Int in that there is
not a multiplicative inverse. What we're trying to do here is to determine
how much of what we know about mathematics is usefully modeled in the
standard library. The answer is not zero, because there is more than just
counting that people do with integers.

It's an interesting problem... When I was in school, "integer" division
"returned" a "quotient and remainder", a "fraction" (which, occasionally,
could be simplified to just an integer), or a "real". We never talked about
division in the context of "(Int, Int) -> Int", though. OTOH, I never took
any math classes past Differential Equations or Linear Algebra, either...
I'm *aware* of areas of math where you formally restrict yourself to the
kind of "(Int, Int) -> Int" operations we're doing here, but I don't
really know much about it. Is division even well-defined in that context?

- Dave Sweeris

95

>
>>
>>
>>
>>
>>
>> "Mathematically correct" integers behave just like Int in that there is
>> not a multiplicative inverse. What we're trying to do here is to
determine
>> how much of what we know about mathematics is usefully modeled in the
>> standard library. The answer is not zero, because there is more than
just
>> counting that people do with integers.
>>
>>
>> It's an interesting problem... When I was in school, "integer" division
>> "returned" a "quotient and remainder", a "fraction" (which,
occasionally,
>> could be simplified to just an integer), or a "real". We never talked
about
>> division in the context of "(Int, Int) -> Int", though. OTOH, I never
took
>> any math classes past Differential Equations or Linear Algebra,
either...
>> I'm *aware* of areas of math where you formally restrict yourself to the
>> kind of "(Int, Int) -> Int" operations we're doing here, but I don't
>> really know much about it. Is division even well-defined in that
context?
>>
>> - Dave Sweeris
>>
>
> I'm no mathematician, and I'm not sure how to tackle the question of
> "well-defined." Hopefully someone who is more knowledgable can chime in
> here.
>
> But I'll have a go at replying to your point as it relates to the
practical
> issue here. Two Int values can be "divided" to produce another Int, and
> that gives a predictable and well-understood result. It's an operation
> that's always going to be there--first, because it'd be insane to remove
it
> since much working code relies on it, and second, because we're only
> re-designing integer protocols and not the concrete types. However, it
_is_
> true that such an operation has very different semantics from division as
> you learned it in math.
>
> This is why I'm advocating for perhaps another look at the top of this
> integer protocol hierarchy. At the moment, `Arithmetic` offers reasonable
> semantic guarantees for a lot of things, but `/` has different semantics
> for integer types and floating point types

Well, that really depends on how closely you look. From one
point-of-view, floating point division and integer division *both*
produce approximate results.

Yes, from a certain point of view. I remember we did discuss this at one
point on the list; I asked whether FloatingPoint was meant to model only
the countable set of representable values or whether it was meant to model
the uncountable set of reals. The answer was that here in Swift-land we're
trying to model the latter, and the approximate result is an artifact of
the imperfect modeling. Integer division, however, is not such an artifact,
but fundamentally a different operation.

···

On Sun, Jan 15, 2017 at 7:24 PM, Dave Abrahams <dabrahams@apple.com> wrote:

on Sun Jan 15 2017, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:
> On Sun, Jan 15, 2017 at 6:42 PM, David Sweeris <davesweeris@mac.com> > wrote:
>> On Jan 15, 2017, at 18:02, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

> and is really closer to just syntax. Other mathematical types--which
> certainly the stdlib doesn't have to offer, but the stdlib protocol
> hierarchy shouldn't preclude their conformance to relevant protocols
> if it's possible--such as fractions and complex numbers, share with
> floating point types the semantics of `/` that qualify these types as
> fields. Dave A's question as to practical uses can probably best be
> answered in this way: to the extent that any generic algorithm relies
> on `/` having semantics and can be applied to fractions and real
> numbers, it would be useful to distinguish such an operation from
> integer "division."

That's not a bad answer. Ruminating on this...

--
-Dave

96

Yeah, but integer division tends to be so "approximate" that the answer can easily be useless without also calculating x%y. Floating point division will generally give you at least a few correct digits, won't it?

- Dave Sweeris

···

On Jan 15, 2017, at 19:24, Dave Abrahams <dabrahams@apple.com> wrote:

on Sun Jan 15 2017, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:

On Sun, Jan 15, 2017 at 6:42 PM, David Sweeris <davesweeris@mac.com> wrote:

On Jan 15, 2017, at 18:02, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

"Mathematically correct" integers behave just like Int in that there is
not a multiplicative inverse. What we're trying to do here is to determine
how much of what we know about mathematics is usefully modeled in the
standard library. The answer is not zero, because there is more than just
counting that people do with integers.

It's an interesting problem... When I was in school, "integer" division
"returned" a "quotient and remainder", a "fraction" (which, occasionally,
could be simplified to just an integer), or a "real". We never talked about
division in the context of "(Int, Int) -> Int", though. OTOH, I never took
any math classes past Differential Equations or Linear Algebra, either...
I'm *aware* of areas of math where you formally restrict yourself to the
kind of "(Int, Int) -> Int" operations we're doing here, but I don't
really know much about it. Is division even well-defined in that context?

- Dave Sweeris

I'm no mathematician, and I'm not sure how to tackle the question of
"well-defined." Hopefully someone who is more knowledgable can chime in
here.

But I'll have a go at replying to your point as it relates to the practical
issue here. Two Int values can be "divided" to produce another Int, and
that gives a predictable and well-understood result. It's an operation
that's always going to be there--first, because it'd be insane to remove it
since much working code relies on it, and second, because we're only
re-designing integer protocols and not the concrete types. However, it _is_
true that such an operation has very different semantics from division as
you learned it in math.

This is why I'm advocating for perhaps another look at the top of this
integer protocol hierarchy. At the moment, `Arithmetic` offers reasonable
semantic guarantees for a lot of things, but `/` has different semantics
for integer types and floating point types

Well, that really depends on how closely you look. From one
point-of-view, floating point division and integer division *both*
produce approximate results.

97

Responding to the thread in general here, not so much any specific email:

“Arithmetic” at present is not a mathematically-precise concept, and it may be a mistake to make it be one[1]; it’s a mathematically-slightly-fuzzy “number” protocol. FWIW, if I had to pick a mathematical object to pin it to, I would make it a [non-commutative] ring, which give it:

  addition, subtraction, multiplication, IntegerLiteralConvertible, and an inverse: T? property.

Note that this would make division go out the window, but we would *preserve* int literal convertible (because there’s a unique map from Z to any ring — Z is the initial object in the category of rings). I think that it’s quite important to keep that for writing generic code.

Vectors and points are not “numbery” in this sense, so they should not conform to this protocol, which is why it’s OK that multiplication and int literals don’t make sense for them. They’re property a vector space or module built over a scalar type.

I would be OK with moving division out of the Arithmetic protocol, as the division operator is fundamentally different for integers and floating-point, and you want to have separate left- and right- division for quaternions and matrices. I would be pretty strongly opposed to removing integer literals; they rightfully belong here.

I think the name “Arithmetic” is sound. It is deliberately *not* one of the standard mathematical abstractions, reserving those names for folks who want to build a precise lattice of algebraic objects. Vectors don’t belong in this protocol, though.

– Steve

[1] We don’t want to make a semester course in modern algebra a prerequisite to using Swift, as much as I would enjoy building a tower of formalism as a mathematician.

98

Responding to the thread in general here, not so much any specific email:

“Arithmetic” at present is not a mathematically-precise concept, and
it may be a mistake to make it be one[1]; it’s a
mathematically-slightly-fuzzy “number” protocol. FWIW, if I had to
pick a mathematical object to pin it to, I would make it a
[non-commutative] ring, which give it:

  addition, subtraction, multiplication, IntegerLiteralConvertible, and an inverse: T?
      property.

Note that this would make division go out the window, but we would
*preserve* int literal convertible (because there’s a unique map from
Z to any ring — Z is the initial object in the category of rings). I
think that it’s quite important to keep that for writing generic code.

Vectors and points are not “numbery” in this sense, so they should not
conform to this protocol, which is why it’s OK that multiplication and
int literals don’t make sense for them. They’re property a vector
space or module built over a scalar type.

I would be OK with moving division out of the Arithmetic protocol, as
the division operator is fundamentally different for integers and
floating-point, and you want to have separate left- and right-
division for quaternions and matrices. I would be pretty strongly
opposed to removing integer literals; they rightfully belong here.

I think the name “Arithmetic” is sound. It is deliberately *not* one
of the standard mathematical abstractions, reserving those names for
folks who want to build a precise lattice of algebraic
objects. Vectors don’t belong in this protocol, though.

OK, suppose we move division, and state in the documentation that models
of Arithmetic should have the mathematical properties of a
(non-commutative) Ring?

– Steve

[1] We don’t want to make a semester course in modern algebra a
prerequisite to using Swift, as much as I would enjoy building a tower
of formalism as a mathematician.

Indeedy.

···

on Sun Jan 15 2017, Stephen Canon <swift-evolution@swift.org> wrote:

--
-Dave

99

One example: earlier, it was demonstrated that a genetic lerp would not
accommodate vector types. However, it _does_ work fine for any scalar (i.e.
field) type; however, with the currently proposed integer protocols, one
would constrain it to Arithmetic types, yet the algorithm would be bogus
for integers.

···

On Sun, Jan 15, 2017 at 19:21 Dave Abrahams <dabrahams@apple.com> wrote:

on Sun Jan 15 2017, Xiaodi Wu <xiaodi.wu-AT-gmail.com> wrote:

> On Sun, Jan 15, 2017 at 3:27 PM, Dave Abrahams via swift-evolution < > > > swift-evolution@swift.org> wrote:

>

>>

>> on Sun Jan 15 2017, Xiaodi Wu <swift-evolution@swift.org> wrote:

>>

>> > There _may_ be value in recognizing the distinction between rings and

>> > fields, perhaps? Just as the FP protocols make room for people to

>> implement

>> > their own decimal FP types, and just as you're trying to make
Arithmetic

>> > accommodate complex numbers, the distinction would allow someone to
write

>> > algorithms generic over rationals and reals (i.e. fields). Being able
to

>> > represent exact fractions isn't so terribly niche, and I think the
design

>> > wouldn't be terribly complicated by its accommodation:

>> >

>> > ```

>> > // rename Arithmetic to Ring

>> > // it's acceptable to omit `.one` from Ring, though some may call
that a

>> > Pseudoring

>> > // consider omitting division from Ring and pushing it down to

>> > BinaryInteger and Field

>> >

>> > protocol BinaryInteger : Ring { ... }

>> >

>> > protocol Field : Ring {

>> > static var one { get }

>> > static func / (Self, Self) -> Self

>> > static func /= (inout Self, Self)

>> > var inverted: Self { get } // default impl: .one / self

>> > }

>> >

>> > protocol FloatingPoint : Field { ... }

>> > // rational number types and complex number types

>> > // would also conform to Field

>> > ```

>>

>> What generic algorithms would this enable?

>

> For one, anything to do with dividing into equal parts

For example...?

> could be generic over floating point, rational, and even complex

> numbers, but you probably wouldn't want to include integer types in

> such an algorithm.

>

>> Would they be appropriate

>> for the standard library (as opposed to some more specialized numerics

>> library)?

>>

>

> The issue is that it's not terribly ergonomic to relegate `Field` to a

> specialized library because one cannot retroactively conform

> `FloatingPoint` to `Field`.

I don't think this is an important enough concern to justify adding

protocols to the standard library. The number of types one has to

individually make conform to Field is probably going to remain small.

Show-me-the-mone^Walgorithms-ly y'rs,

--

-Dave

100

> Responding to the thread in general here, not so much any specific email:
>
> “Arithmetic” at present is not a mathematically-precise concept, and
> it may be a mistake to make it be one[1]; it’s a
> mathematically-slightly-fuzzy “number” protocol. FWIW, if I had to
> pick a mathematical object to pin it to, I would make it a
> [non-commutative] ring, which give it:
>
> addition, subtraction, multiplication, IntegerLiteralConvertible,
and an inverse: T?
> property.
>
> Note that this would make division go out the window, but we would
> *preserve* int literal convertible (because there’s a unique map from
> Z to any ring — Z is the initial object in the category of rings). I
> think that it’s quite important to keep that for writing generic code.
>
> Vectors and points are not “numbery” in this sense, so they should not
> conform to this protocol, which is why it’s OK that multiplication and
> int literals don’t make sense for them. They’re property a vector
> space or module built over a scalar type.
>
> I would be OK with moving division out of the Arithmetic protocol, as
> the division operator is fundamentally different for integers and
> floating-point, and you want to have separate left- and right-
> division for quaternions and matrices. I would be pretty strongly
> opposed to removing integer literals; they rightfully belong here.
>
> I think the name “Arithmetic” is sound. It is deliberately *not* one
> of the standard mathematical abstractions, reserving those names for
> folks who want to build a precise lattice of algebraic
> objects. Vectors don’t belong in this protocol, though.

OK, suppose we move division, and state in the documentation that models
of Arithmetic should have the mathematical properties of a
(non-commutative) Ring?

Unless I'm mistaken, after removing division, models of SignedArithmetic
would have the mathematical properties of a ring. For every element a in
ring R, there must exist an additive inverse -a in R such that a + (-a) =
0. Models of Arithmetic alone would not necessarily have that property.

···

On Mon, Jan 16, 2017 at 12:44 AM, Dave Abrahams via swift-evolution < swift-evolution@swift.org> wrote:

on Sun Jan 15 2017, Stephen Canon <swift-evolution@swift.org> wrote:

– Steve
>
> [1] We don’t want to make a semester course in modern algebra a
> prerequisite to using Swift, as much as I would enjoy building a tower
> of formalism as a mathematician.

Indeedy.

--
-Dave

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