[swift-evolution] [Proposal draft] Enhanced floating-point protocols

Thu Apr 21 16:05:22 CDT 2016

I totally agree with you. 

But I think that the suggested Summable with zero fits the bill of your citation quite nicely as it actually is a very generic concept which is widely useful. 

FWIW I had chosen the name Summable instead of Monoid for two reasons: (1) there has been reluctance by some people on this list to add algebraic types to the standard library and (2) Summable is one concrete instance of Monoid for numbers (with respect to addition) just as my other suggestion Multiplicative is another instance of Monoid for numbers (with respect to multiplication).

If we want to add Monoid (and other algebraic types) to the standard library (I would welcome that), you are certainly right that we should design this well. The above actually suggests that summable and multiplicative instances for numbers might just be that: (singleton?) instances of Monoid with an associated type of Number (instead of protocols) so that they can be passed around more easily. 
On the other hand we could borrow some ideas from Eiffel to solve the (semantic) diamond problem via renaming and choosing defaults. Like the early work about generics you found, Eiffel's solution sadly is ignored in most language designs (and interfaces thought of as a solution of the diamond problem... they are not). Not too long ago I wrote a lenghty mail on this list about that in the Mixin thread IIRC.

> I'm not sure I'm adding anything by saying this, but one problem with
> creating protocols that satisfy the absolute minimum requirements for a
> particular algorithm is that you end up without any meaningful
> abstractions.

I think Dave Sweeris' example is not about creating Addable a.k.a Summable just because it satisfies the algorithm but rather it happens that Monoid *is* such a useful abstraction that it naturally pops up in many algorithms.

-Thorsten 

> Am 21.04.2016 um 20:36 schrieb Dave Abrahams via swift-evolution <swift-evolution at swift.org>:
> 
> 
> on Wed Apr 20 2016, davesweeris-AT-mac.com wrote:
> 
>>> On Apr 20, 2016, at 1:15 PM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
>>> 
>>> 
>>>> on Tue Apr 19 2016, Thorsten Seitz <swift-evolution at swift.org> wrote:
>>>> 
>>>> I'd like to have something like Summable with 'add', 'adding' and 'zero' being a
>>>> separate protocol as well as somthing like Multiplicative with 'multiply',
>>>> 'multiplied' and 'one' being a separate protocol, because these are universally
>>>> interesting for other cases, e.g. Summable would be useful for defining path
>>>> lengths in a graph library.
>>>> 
>>>> Would you mind adding that to the proposal?
>>> 
>>> I suspect you may be headed into the realm of
>>> protocols-as-bags-of-syntax.
>> 
>> You say that like it’s a bad thing… 
> 
> Indeed!
> 
>> Am I missing the point? (NOT a rhetorical question)
> 
> I don't know, but I'll try to help answer...
> 
>> Speaking only for myself, I want stuff broken up into many simpler
>> protocols (which `Arithmetic` and such conform to) because there are
>> many algorithms which only require small parts of the larger
>> protocol. What if I wanted to add a function that sums all the
>> elements in a collection?
>> 
>> extension CollectionType where Generator.Element: Arithmetic {
>>    func sum() -> Generator.Element {
>>        var s = Generator.Element()
>>        for e in self {
>>            s.add(e)
>>        }
>>        return s
>>    }
>> }
>> 
>> Yeah, it works, but if I want to get the sum of a collection of some custom type, I
>> have to implement *all* of `Arithmetic`, as opposed to just the two
>> parts of it (`init()` and `.add(:)`) that the algorithm actually
>> uses. It’d be both simpler for the users and *more to the point of the
>> function*, if it could be written like this:
>> 
>> extension CollectionType where Generator.Element: Addable { // "Addable" instead of "Arithmetic"
>>    ... // No change here
>> }
> 
> This method is undocumented.  What does it *do*, given an arbitrary
> element type conforming to Addable?  The answer needs to be a
> description of the semantics that doesn't require me to effectively
> execute the source of the function in my head.  How can I test that the
> method does the right thing?  To answer these questions, you have to
> attach some semantics to Addable so that it's more than a mere bag of
> syntax.  For example, for the above to produce the usual semantics of
> summing, the Element's init() method needs to produce the additive
> identity element.
> 
> Choosing the granularity of protocols is something of an art.  Lots has
> been written about generic programming's “requirement minimization
> principle,” in which the more requirements you add, the less reusable
> algorithms become.  Almost nothing has been written about the other side
> of the coin, but...
> 
> After much googling I came up with a reference to one of Alexander
> Stepanov and James Dehnert's early papers on generic programming (it
> sometimes amazes me how many of the key insights can only be found in
> that early work):
> 
> http://www.stepanovpapers.com/DeSt98.pdf
> 
>  We call the set of axioms satisfied by a data type and a set of
>  operations on it a concept. Examples of concepts might be an integer
>  data type with an addition operation satisfying the usual axioms; or a
>  list of data objects with a first element, an iterator for traversing
>  the list, and a test for identifying the end of the list. **The critical
>  insight which produced generic programming is that highly reusable
>  components must be programmed assuming a minimal collection of such
>  concepts, and that the concepts used must match as wide a variety of
>  concrete program structures as possible**. Thus, successful production
>  of a generic component is not simply a matter of identifying the
>  minimal requirements of an arbitrary type or algorithm – it requires
>  identifying the common requirements of a broad collection of similar
>  components. The final requirement is that we accomplish this without
>  sacrificing performance relative to programming with concrete
>  structures. A good generic library becomes a repository of highly
>  efficient data structures and algorithms, based on a small number of
>  broadly useful concepts, such that a library user can combine them and
>  his own components in a wide variety of ways.
> 
> (emphasis mine).
> 
> I'm not sure I'm adding anything by saying this, but one problem with
> creating protocols that satisfy the absolute minimum requirements for a
> particular algorithm is that you end up without any meaningful
> abstractions.
> 
> “*The* critical insight,” wow.  And it's so easily overlooked.
> 
> HTH,
> 
> -- 
> Dave
> _______________________________________________
> 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/20160421/d81da4e8/attachment.html>