[swift-evolution] [Pitch] Add the DefaultConstructible protocol to the standard library

[Xiaodi Wu]

On Sun, Dec 25, 2016 at 7:30 PM, Adam Nemecek <adamnemecek at gmail.com> wrote:

> >  Is it well settled, either in Swift or in C++/Rust/etc., that the value
> returned by a default initializer/constructor is regarded as an identity
> element or zero?
>
> Int() == 0, String() == "" so to some extent by convention, a lot of types
> have a default value as is.
>

Yes, those particular types have initializers that take no arguments. That
does not address my question. You merely restated your initial observation
that many types in Swift have implemented `init()`.

I didn't think the value returned by `init()` was regarded as any sort of
zero--or even any sort of "default." In fact, some types in Foundation have
a static property called `default` distinct from `init()`. In Rust, the
Default trait requires a function called `default()`, which is documented
as being useful when you want "some kind of default value, and don't
particularly care what it is."

I was asking whether there's some understanding, of which I've been
unaware, that the result of `init()` (or the equivalent in other languages)
is expected to be some sort of zero or an identity element. I'm not aware
of any evidence to that effect. Are you?

> Is the thread that I get by writing `let t = Thread()` some kind of zero
> in any reasonable sense of the word?
>
> DefaultConstructibility makes less sense for types that represent some
> sort of resource but make sense for things that are values. But even in
> this case, Thread() gives you a default value for example if you are
> working with a resizable collection of threads.
>

It gives you something different every time. How can this be squared with
your stated motivation regarding concepts of zero and concepts of equality?

A better question is why does thread currently implement a default
> constructor?
>

It's an initializer that takes no arguments, because none are needed for a
new thread. How else would you write it?

> Do you mean to argue that for an integer the additive identity should be
> considered "more prominent and useful" than the multiplicative identity?
> I'm not aware of any mathematical justification for such a conclusion.
>
> I do. The justification is that if I call the default constructor of Int
> currently, I get the value of 0.
>

This is backwards. Why do you believe that the value you obtain from
`init()` is intended to be an identity element at all, let alone the most
important one? (It's also circular reasoning. Since `init()` only ever
gives you one value at a time, by your reasoning it demonstrates that every
type must have one "more prominent and useful" identity, which is begging
the question.)

Which means that the binary operation must be addition.
>

Based on the value of `Int.init()`, you conclude that addition of integers
is a "more prominent and useful" operation than multiplication? Again, this
is backwards. Rather, we know that each numerical type belongs to multiple
ring algebras; there is no basis for reckoning any as "more useful." Since
`init()` can only ever give us one value at a time, we know that `init()`
cannot give a value that is a meaningful default with respect to any
particular operation.

If I call String() I get "" which is the identity of the + String operation.
>

Or, it's what you get because that's the most trivial possible string.
Quite simply, I do not think the designer of most types that implement
`init()` have paused to wonder whether the value that you get is the
identity element associated with the most useful and prominent operation
that can be performed on that type. I certainly never have.

> Going to your original example, I should add: other languages provide a
> version of `reduce` that doesn't require an initial result (for instance,
> JavaScript). In JavaScript, `[1, 2, 3].reduce((a, b) => a + b)` uses the
> element at array index 0 as the initial result, and the accumulator
> function is invoked starting with the element at array index 1. This is
> precisely equivalent to having `reduce` use the additive identity as the
> default initial result when + is the accumulator function and the
> multiplicative identity when * is the accumulator function (with the
> accumulator function being invoked starting with the element at array index
> 0). It does not require a DefaultConstructible protocol. What more
> ergonomic solution could be implemented using a monoidic wrapper type?
>
> These two will have different signatures. The reduce you describe returns
> an optional,
>

The statement I wrote was in JavaScript, so I'm not sure what you mean by
returning an optional. `[].reduce((a, b) => a + b)` results in an error in
JavaScript. In Swift, such a function may also be implemented with a
precondition that the array is not empty and would not return an optional.

the other one would returns the default value.
>

In what scenario would you prefer to propagate a default after reducing a
potential empty collection _without supplying an explicit default_ for that
operation? This would certainly violate the Swift convention of not
defaulting to zero and, I suspect, most users of Swift would not regard
that as ergonomic at all.


> Fundamentally the default constructibles are useful in numerical
> computations e..g. dealing with tensors.
>

Can you give an example of an algorithm dealing with tensors where you
would use a `DefaultConstructible` generic over all types that have
`init()`, as opposed to working with the existing `Integer`,
`FloatingPoint`, and other numerical protocols? (I should also add, FWIW, I
have never seen a generic algorithm written for integers or FP types that
has preferred the use of `T()` over `0`.)


On Sun, Dec 25, 2016 at 3:30 PM, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
>
>> On Sun, Dec 25, 2016 at 5:27 PM, Adam Nemecek <adamnemecek at gmail.com>
>> wrote:
>>
>>> > *Which* APIs become more ergonomic?
>>>
>>> I'll get back to this question in a second if I may. This would be a
>>> longer discussion and I first want to make sure that before we get into the
>>> details that there is a possibility of this being introduced (I'm asking if
>>> violating the no zero defaults is more important than slightly more
>>> ergonomic APIs). But to give a broad answer I think that the concept of a
>>> zero is closely related to the concept of equality (and all the things that
>>> build up on equality such as comparability and negation).
>>>
>>> > 1) How does this square with Swift’s general philosophy to not
>>> default initialize values to “zero”?
>>>
>>> I actually wasn't aware of this philosophy. Despite this philosophy,
>>> look at how many types actually currently implement a default constructor.
>>>
>>
>> (Not a rhetorical question:) Is it well settled, either in Swift or in
>> C++/Rust/etc., that the value returned by a default initializer/constructor
>> is regarded as an identity element or zero? Is the thread that I get by
>> writing `let t = Thread()` some kind of zero in any reasonable sense of the
>> word?
>>
>>
>>> Also can I ask what's the motivation behind this philosophy?
>>> I think that in Swift, default constructibility makes complete sense for
>>> (most?) structs, maybe less so for classes.
>>>
>>> > 2) To your original example, it isn’t immediately clear to me that
>>> reduce should choose a default identity.  Some types (e.g. integers and FP)
>>> belong to multiple different ring algebras, and therefore have different
>>> identity values that correspond to the relevant binary operations.
>>>
>>> This is a good point that I've considered as well but felt that for the
>>> most part, there is one particular identity and associated operation that
>>> is more prominent and useful than others. Furthermore, modeling different
>>> algebras isn't mutually exclusive with writing generic algorithms that rely
>>> on this protocol, you can always introduce some monoidic wrapper type that
>>> defines the more appropriate default value and operation.
>>>
>>
>> Do you mean to argue that for an integer the additive identity should be
>> considered "more prominent and useful" than the multiplicative identity?
>> I'm not aware of any mathematical justification for such a conclusion.
>>
>> Going to your original example, I should add: other languages provide a
>> version of `reduce` that doesn't require an initial result (for instance,
>> JavaScript). In JavaScript, `[1, 2, 3].reduce((a, b) => a + b)` uses the
>> element at array index 0 as the initial result, and the accumulator
>> function is invoked starting with the element at array index 1. This is
>> precisely equivalent to having `reduce` use the additive identity as the
>> default initial result when + is the accumulator function and the
>> multiplicative identity when * is the accumulator function (with the
>> accumulator function being invoked starting with the element at array index
>> 0). It does not require a DefaultConstructible protocol. What more
>> ergonomic solution could be implemented using a monoidic wrapper type?
>>
>>
>> On Sun, Dec 25, 2016 at 1:24 PM, Chris Lattner <clattner at apple.com>
>>> wrote:
>>>
>>>> On Dec 25, 2016, at 12:54 PM, Adam Nemecek via swift-evolution <
>>>> swift-evolution at swift.org> wrote:
>>>>
>>>> Does enabling a lot of small improvements that make APIs more ergonomic
>>>> count as practical?
>>>>
>>>>
>>>> Yes, that would count as practical, but Xiaodi’s question is just as
>>>> important.  *Which* APIs become more ergonomic?
>>>>
>>>> Here are a couple of more questions:
>>>>
>>>> 1) How does this square with Swift’s general philosophy to not default
>>>> initialize values to “zero”?
>>>>
>>>> 2) To your original example, it isn’t immediately clear to me that
>>>> reduce should choose a default identity.  Some types (e.g. integers and FP)
>>>> belong to multiple different ring algebras, and therefore have different
>>>> identity values that correspond to the relevant binary operations.
>>>>
>>>> -Chris
>>>>
>>>>
>>>> On Sun, Dec 25, 2016 at 12:19 PM, Xiaodi Wu <xiaodi.wu at gmail.com>
>>>> wrote:
>>>>
>>>>> On Sun, Dec 25, 2016 at 3:07 PM, Adam Nemecek <adamnemecek at gmail.com>
>>>>> wrote:
>>>>>
>>>>>> There's a book that provides quite a bit of info on this
>>>>>>
>>>>>> https://smile.amazon.com/Elements-Programming-Alexander-Step
>>>>>> anov/dp/032163537X?sa-no-redirect=1
>>>>>>
>>>>>> They say that DefaultConstructible is one of the essential protocols
>>>>>> on which most algorithms rely in one way or another. One of the authors is
>>>>>> the designer of the C++ STL and basically the father of modern generics.
>>>>>>
>>>>>> This protocol is important for any algebraic structure that deals
>>>>>> with the concept of appending or addition (as "zero" is one of the
>>>>>> requirements of monoid). There isn't a good short answer to your question.
>>>>>> It's a building block of algorithms. Think about why a
>>>>>> RangeReplaceableCollection can provide you with a default constructor but a
>>>>>> Collection can't.
>>>>>>
>>>>>
>>>>> It's well and fine that most algorithms rely on the concept in one way
>>>>> or another. Yet the Swift standard library already implements many generic
>>>>> algorithms but has no DefaultConstructible, presumably because there are
>>>>> other protocols that guarantee `init()` and the algorithms being
>>>>> implemented don't need to be (practically speaking) generic over all
>>>>> DefaultConstructible types. My question is: what practical use cases are
>>>>> there for an explicit DefaultConstructible that are impractical today?
>>>>>
>>>>>
>>>>> On Sun, Dec 25, 2016 at 11:37 AM, Xiaodi Wu <xiaodi.wu at gmail.com>
>>>>>> wrote:
>>>>>>
>>>>>>> Can you give some other examples of generic algorithms that would
>>>>>>> make use of this DefaultConstructible? I'm having trouble coming up with
>>>>>>> any other than reduce.
>>>>>>> On Sun, Dec 25, 2016 at 14:23 Adam Nemecek via swift-evolution <
>>>>>>> swift-evolution at swift.org> wrote:
>>>>>>>
>>>>>>>> This protocol is present in C++ http://en.cppreference.com
>>>>>>>> /w/cpp/concept/DefaultConstructible as well as in Rust
>>>>>>>> https://doc.rust-lang.org/std/default/
>>>>>>>>
>>>>>>>> It's the identity element/unit of a monoid or a zero.
>>>>>>>>
>>>>>>>> The Swift implementation is very simple (I'm open to different
>>>>>>>> names)
>>>>>>>>
>>>>>>>> protocol DefaultConstructible {
>>>>>>>>     init()
>>>>>>>> }
>>>>>>>>
>>>>>>>> A lot of the standard types could then be made to conform to this
>>>>>>>> protocol. These include all the numeric types, collection types (array,
>>>>>>>> set, dict), string, basically at least every type that currently has a
>>>>>>>> constructor without any arguments.
>>>>>>>>
>>>>>>>> The RangeReplaceableCollection protocol would inherit from this
>>>>>>>> protocol as well.
>>>>>>>>
>>>>>>>> This protocol would simplify a lot of generic algorithms where you
>>>>>>>> need the concept of a zero (which shows up a lot)
>>>>>>>>
>>>>>>>> Once introduced, Sequence could define an alternative
>>>>>>>> implementation of reduce where the initial result doesn't need to be
>>>>>>>> provided as it can be default constructed.
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> _______________________________________________
>>>>>>>> swift-evolution mailing list
>>>>>>>> swift-evolution at swift.org
>>>>>>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>>>>>>>
>>>>>>>
>>>>>>
>>>>>
>>>> _______________________________________________
>>>> swift-evolution mailing list
>>>> swift-evolution at swift.org
>>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>>>
>>>>
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20161225/a675458f/attachment.html>