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

[Dave Abrahams]

on Sun Dec 25 2016, Xiaodi Wu <swift-evolution at swift.org> wrote:

> On Sun, Dec 25, 2016 at 9:40 PM, Adam Nemecek
> <adamnemecek at gmail.com> wrote:
>
>> > 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()`.
>>
>> Right, it's an empirical argument.
>>
>> > 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()`.
>>
>> Let's not talk about those then. This would not apply to every single type
>> in existence, as I've stated previously.
>>
>
> Whoops, I missed a few items here. In your first post, you stated that you
> wanted your proposed protocol to apply to "basically at least every type
> that currently has a constructor without any arguments." Is that not the
> case?
>
>> It gives you something different every time. How can this be squared with
>> your stated motivation regarding concepts of zero and concepts of equality?
>>
>> Due to the fact that it's a resource, not a value. As I've stated above,
>> not all of this applies to types that are more resource-like.
>>
>
> In Swift, protocols do not merely guarantee particular spellings, but
> particular semantics as well. 

I should add: that's a core principle of generic programming as put
forth by Stepanov.

> If "not all of this applies" to "resource-like" types, what semantic
> guarantees are you proposing for `DefaultConstructible`, and to what
> types would they completely apply?
>
>> 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.
>>
>> This is an appeal to tradition.
>>
>> > 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.
>>
>> I was talking about their analogous swift implementations.
>>
>> > 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?
>>
>> If it's implemented as either nested collections or numbers.
>>
>>
>>
>> On Sun, Dec 25, 2016 at 6:00 PM, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
>>
>>> 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
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>
>>>>>
>>>>
>>>
>>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>

-- 
-Dave