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

[Dave Abrahams]

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