[swift-evolution] Should we rename "class" when referring to protocol conformance?

[Dave Abrahams]

on Sun May 22 2016, Matthew Johnson <swift-evolution at swift.org> wrote:

>> On May 22, 2016, at 12:04 PM, Dave Abrahams via swift-evolution
>> <swift-evolution at swift.org> wrote:
>> 
>> 
>> on Mon May 16 2016, Matthew Johnson <swift-evolution at swift.org> wrote:
>> 
>>>> On May 15, 2016, at 2:01 PM, Dave Abrahams
>>>> <dabrahams at apple.com> wrote:
>>>> 
>>>> 
>>>> on Fri May 13 2016, Matthew Johnson <matthew-AT-anandabits.com
>>>> <http://matthew-at-anandabits.com/>> wrote:
>>>> 
>>> 
>>>>> Sent from my iPad
>>>>> 
>>>>>> On May 13, 2016, at 9:12 AM, Dave Abrahams <dabrahams at apple.com> wrote:
>>>>>> 
>>>>>> 
>>>>>>> on Mon May 09 2016, Matthew Johnson <matthew-AT-anandabits.com> wrote:
>>>>>>> 
>>>>>>> My claim is that substituting the constraint of “it has value
>>>>>>> semantics,” while presumably looser than the PureValue constraint, would
>>>>>>> not compromise the correctness of your view controller, so not only is
>>>>>>> the meaning of PureValue hard to define, but it doesn't buy you
>>>>>>> anything.  If you want to refute that, just show me the code.
>>>>>>> 
>>>>>>> This is not an algorithmic use but is still perfectly valid IMO.
>>>>>>> 
>>>>>>> If the properties of PureValue matter to your view controller, there's
>>>>>>> an algorithm somewhere that depends on those properties for its
>>>>>>> correctness.
>>>>>>> 
>>>>>>> In many cases it may just be view configuration that depends on those
>>>>>>> properties.  I suppose you can call view configuration code an
>>>>>>> algorithm but I think that would fall outside of common usage.
>>>>>> It's an algorithm, or if the configuration is declarative, there's
>>>>>> an algorithm that manipulates it.  That said, I still don't have a
>>>>>> concrete example of how view configuration can depend on these
>>>>>> properties.
>>>>> The algorithm might just be "copy x bit of data to y view
>>>>> property, etc".  That is so trivial that it feels like a stretch to
>>>>> call it an algorithm.
>>>> 
>>>> Algorithms can be trivial.
>>> 
>>> Fair enough.  Although in most contexts people don’t use the word when
>>> discussing the trivial.
>> 
>> Yes, quite a shame, that.
>> 
>>>>> That "algorithm" doesn't depend on this property because it
>>>>> executes at a single point in time.  However, a view controller
>>>>> might depend on that property in order to render properly across
>>>>> time (for example, configuring cells as they scroll on and off
>>>>> screen).
>>>> The example is too abstract for me to understand.
>>>> 
>>>> Let me put this differently: I recognize that your concept of
>>>> “PureValue” may be a *sufficient* condition for some generic
>>>> algorithm/component to work, but it is never a *necessary*
>>>> condition, because genericity (or use of a superclass or protocol
>>>> type) erases details of the actual types involved from the point of
>>>> view of the algorithm/component.  It doesn't matter if your type
>>>> contains a class reference if it has value semantic properties.  My
>>>> claim is that PureValue is an overly-restrictive constraint that
>>>> makes many things less useful than they should be.
>>> 
>>> In many cases this is true - you don’t need more than value semantics
>>> as you define it.  However it is not at all true that PureValue is
>>> never necessary for the correctness of code.  I’m going to provide an
>>> example to the contrary below.
>>> 
>>>> 
>>>>> This property allows us to separate values from non-local mutation
>>>>> and make such separation a requirement.  Rather than observing
>>>>> mutations of objects with KVO, etc we might prefer to observe
>>>>> something that provides a new aggregate value instead, while
>>>>> requiring the entire aggregate value itself to be (observably)
>>>>> immutable at all times (because we stored it with a let property
>>>>> locally).  This can make it easier to reason about correct behavior
>>>>> of your code.  But it doesn't work unless all visible parts of the
>>>>> aggregate are immutable.
>>>>> 
>>>>> If you're not familiar with Elm, Redux, etc it might be worth
>>>>> taking a look.
>>>> That's a pretty broad link.  At which parts do you think I should
>>>> look?
>>> 
>>> The piece that matters here is state management.  The core concept is
>>> to tightly control how mutations happen.  It is modeled in terms of
>>> state type T, an initial value t, an action type A (instances of which
>>> are mutation commands, as in the command pattern), and a reducer
>>> function (T, A) -> T which produces a new state.
>>> 
>>> Here’s a toy implementation that is somewhat simplistic but captures
>>> the essence of the concept:
>>> 
>>> class Store<State, Action> {
>>>    typealias Reducer = (State, Action) -> State
>>> 
>>>    var stateHistory: [State]
>>>    let reducer: Reducer
>>> 
>>>    init(initialState: State, reducer: Reducer) {
>>>        stateHistory = [initialState]
>>>        self.reducer = reducer
>>>    }
>>> 
>>>    func applyAction(action: Action) {
>>>        let newState = reducer(stateHistory.last!, action)
>>>        stateHistory.append(newState)
>>>    }
>>> 
>>>    var currentState: State {
>>>        return stateHistory.last!
>>>    }
>>> 
>>>    var canUndo: Bool {
>>>        return stateHistory.count > 1
>>>    }
>>> 
>>>    func undo() {
>>>        if canUndo {
>>>            stateHistory.popLast()
>>>        }
>>>    }
>>> }
>>> 
>>> This design relies on State being a PureValue.  The whole idea is that
>>> the only way any path of observation rooted at currentState can change
>>> is when the reducer returns a new state when it is called by
>>> `applyAction`.  That guarantee 
>> 
>> I'm sorry, I can't understand what guarantee you're describing here.
>> Can you describe it in terms of preconditions, postconditions, and
>> invariants?
>
> I don’t think so.  You could state precondition, postconditions, and
> invariants that would all rely on `==`.  However, if reference
> semantic types implement `==` as `===` these would not be strong
> enough to provide the intended guarantee.
>
> The guarantee depends on preventing *other code* from mutating values
> in `stateHistory`.  

Ignoring the fact that you made `Store` a class, which makes that kind
of prevention impossible...

> If State is Array<TypeWithMutableReferenceSemantics> and some other
> code has a reference to the objects in the array the *other* code
> might mutate those objects.  This would violate the semantic guarantee
> that is intended.  

This depends on your view that the contents of the shared mutable
instance is a salient attribute of the `Array`, *and* on an undeclared
intention.

> But any preconditions, postconditions, and invariants stated using
> `==` would still be preserved because those shared mutable references
> still compare equal.
>
>> 
>> Just looking at the code, it seems to me that the only actual
>> requirement for sane results here is that the result (and effects) of
>> the `reducer` function depends only on the values of its arguments.
>> This is a highly precedented kind of requirement.  For example, you
>> don't expect sort() to produce meaningful results if the comparison
>> function's result changes based on something other than the values of
>> the elements being compared.
>
> Yes, the reducer must be pure.  But that is not enough for `Store` to
> behave as intended.

Since you haven't documented anything about Store, it's hard to know
what your intended behavior is.

>>> cannot be provided by value semantics alone under your definition of
>>> value semantics.  Further, each state in the history is intended to be
>>> a static snapshot of the “currentState” state at a specific point in
>>> time.  All states should be logically independent from each other and
>>> from anything anywhere else in the program.  This cannot be guaranteed
>>> under your definition of value semantics.
>> 
>> That is exactly my definition of value semantics (modulo aggregation; a
>> value that is composed of other values obviously is dependent on the
>> values it's composed of).  But distinct instances of types with value
>> semantics have values that are logically independent.
>
> The modulo aggregation thing is exactly what this whole thread hinges
> on.  What I am saying is that sometimes it is important that the
> aggregate as a whole have value semantics.  In other words, if any of
> it’s salient attributes are references the objects they point to must
> have value semantics (which requires immutability).

Of course, that's what value semantics means.  I don't think we differ
on this point.

>>> If we allow State to be Array<MyMutableReferenceType> which has value
>>> semantics under your definition it is clear that we should have no
>>> expectation that the desired properties are preserved.  
>>> The Store class is fundamentally broken if it can be used with State
>>> types that are not pure values.
>> 
>> It depends on the semantic requirements placed on `reducer`.  If you
>> insist that `reducer` should be able to do anything at all, then clearly
>> you need to constrain `State` in ways that make this component less
>> useful than it might otherwise be.  But even then, you can't allow
>> `reducer` to *whatever* it wants because it could circle back and modify
>> the `Store` instance.
>
> `reducer` is intended to be pure.  I didn’t specify that because Swift
> doesn’t have syntax for it.  I was just giving valid Swift code and
> discussing the latent requirements of `State`.

You didn't discuss *any* semantic requirements, so it's hard to say
anything for sure about your example.

> Requiring `reducer` to be pure is not enough if we allow `State` to
> have salient mutable reference semantics attributes.  

? Of course it can't; salient attributes of any value type must be
values.

> The references contained in `initialState` and visible via
> `currentState` could be captured and mutated by any code working with
> the store.
>
>>> I’m not sure why it didn’t occur to me sooner, but this strategy for
>>> managing app state is very similar in nature to what Sean Parent
>>> discusses in his value semantics talk
>>> (https://www.youtube.com/watch?v=_BpMYeUFXv8
>>> <https://www.youtube.com/watch?v=_BpMYeUFXv8> and related
>>> https://www.youtube.com/watch?v=bIhUE5uUFOA
>>> <https://www.youtube.com/watch?v=bIhUE5uUFOA>).
>>> 
>>> Sean discusses using value semantics to model applications state (he
>>> calls it document).  His examples don’t use reified actions and
>>> reducer functions so it is a bit different but it relies on the same
>>> pure value semantics.  The demo he gives in the talk is a toy example
>>> modeled on the design Photoshop uses to implement its history feature.
>>> This design relies on each document in the history being an aggregate
>>> which is a PureValue.  This is not an academic discussion, but on with
>>> real world practical utility.
>> 
>> I'm very familiar with this talk; it was a major inspiration for my
>> presentation at WWDC last year.  I'll freely admit I get most of my good
>> ideas from Sean ;-)
>
> Great!  I would be pretty surprised if Sean thinks the distinction I
> am trying to make is unimportant.  His talk indicates that he is very
> concerned about shared mutable state.  All I am looking for is a
> constraint that lets me say “the aggregate rooted at type Foo does not
> contain shared mutable state”.

...which all hinges on the word “contain,” which goes back to “what are
the boundaries of the value?”  Something that you can reach, but that is
not within the boundaries of a value, is not part of the value's state.

I agree that types from which you cannot even reach shared mutable state
are useful and provide stronger protections than other types.  What I
don't see is that there's any generic component whose correctness
depends on this unreachability, because once a generic component
constrains the concrete model type to have value semantics, the
component isn't really allowed to touch reachable but non-salient
attributes, anyway.

Why do I think so?  I guess I believe that protocol requirements should
always be salient.

>>> Sean says “value semantics is similar to functional programming,
>>> except objects still have addresses and in-situ operations… You're
>>> trying to maintain the ability to locally reason about your code but
>>> you're not denying the fact that the machine has memory and you can do
>>> in-situ operations on it”.  
>>> 
>>> Towards the end he quotes from a discussion he had with John Backus
>>> (inventor of FP).  John said: “it always annoyed me that FP and the no
>>> side effect way of programming had become a religion.  With FP I was
>>> trying to come up with a mathematically rigorous way to program and I
>>> understood the complexities of having side effects.  I always knew we
>>> had to deal with side effects, I just wanted a structured way to do
>>> it.”  John agreed that Sean’s approach to value semantics provides
>>> such a structure.  Allowing shared mutable references throws away that
>>> structured approach.  (As an aside, this is the most exciting thing
>>> about value semantics IMO - it provides a structured approach to side
>>> effects, allowing local reasoning about code).
>>> 
>>> Sean gives an example of how references break the ability to reason
>>> locally where he has two shared_ptrs that point to the same object:
>>> 
>>> "If you look at it in terms of just the individual types you kind of
>>> do have value semantics.  When I copy a shared pointer it copies the
>>> pointer with value semantic operations...  The problem is the
>>> references.  When I'm looking at a shared_ptr I'm looking at it as if
>>> I have the object.  
>> 
>> This is the key phrase; it is about the implied programming model for
>> shared_ptr, which is a cultural phenomenon, not an absolute truth.  
>
> I’m not quite sure I follow you here.  Sean has a slide in the
> presentation which shows two shared_ptrs to the same object.  He draws
> a boundary around the whole thing and calls that (both shared_ptrs
> *and* the object) the value.  
> His point is that you cannot consider the shared_ptr on its own, or
> even one of the shared_ptrs and the object that is referenced.  They
> are intricately inter-related.

I know what his point is :-).  This is the same point made around slide 27 of
http://devstreaming.apple.com/videos/wwdc/2015/408509vyudbqvts/408/408_protocoloriented_programming_in_swift.pdf?dl=1

His point is that if your mental model is that you have a value that
includes the state of the object being pointed to, your mental model is
broken.  In fact, shared_ptr in C++ tries to discourage that broken
mental model by defining `==` in the same way I'm proposing to define it
for references, but that doesn't stop many people from thinking of it
wrongly.

>> Yes, when people get a reference to a class instance in Swift, they
>> normally don't even think about what's stored in the instance as
>> being distinct from the value of the reference, and indeed the
>> language syntax is more hostile to making that distinction than the
>> syntax of C++.  Defining the value of a reference to be the address
>> it points at (unless the instance is immutable) allows everything to
>> fall back into place, logically speaking.
>> 
>> Whether programmers can learn to understand the world this way is
>> certainly debatable, but it's pretty clear to me that leaving “the value
>> of a reference” undefined is untenable, and defining it in any way that
>> doesn't result in a reference having value semantics would make
>> describing algorithm semantics almost impossible.  So what's the
>> alternative?
>
> I agree that this is the right approach when you are writing
> algorithms like `rotate`, etc.  The reference is the value you’re
> concerned with.
>
> I also think it is important to be able to make a distinction between
> an aggregate that is logically independent from any other data
> structures in your program and an aggregate which contains shared
> references to mutable state that is also referenced elsewhere in your
> program.  

Yes!  If by “shared references” you mean *salient, semantically exposed
shared references,* that distinction is called “value semantics.”

> In this case you are concerned with the state that is referenced
> (specifically, whether it the state is mutable and whether you have a
> reference that is guaranteed to always be unique - like unique_ptr or
> an owned reference in Rust - or not).
>
> We need to be able to look at the world both ways.  They are both very
> useful in different contexts.

IMO it is much better to find a single programming model that can be
made to work for all contexts.  We should try mightily to achieve that,
if nothing else, to avoid confusion.  If it can't be done, then so be
it, but my strong inclination is to avoid creating subtle distinctions
like “value” vs. “pure value” if they aren't needed.

>>> So really what I have is two objects that intersect.  So really my
>>> object in the program is this whole connected mess.  At any particular
>>> point in code I have difficulty reasoning about the whole thing.  The
>>> shared structure breaks our ability to reason locally about code."
>>> 
>>> Sean makes an important distinction between looking at individual
>>> types and looking at the aggregate as a whole.  It is very important
>>> to him that the entire aggregate be logically independent as this
>>> facilitates local reasoning.  This is exactly what I have been calling
>>> a pure value.  Pure value never allows any intersection to be observed
>> 
>> Yes, but: you can only measure an intersection of two values if *you
>> stay within the boundaries of those values*.  
>
> If you consider a shared_ptr to define the boundary of its value then
> this is not what Sean said.  In Sean’s talk he calls the object that
> two shared_ptrs reference the “intersection”.  He crosses the
> reference when measuring intersection.

I don't know what you mean here.  A shared_ptr *does* define the
boundary of its value, and it does so implicitly by defining the
semantics of equality.  That very clearly indicates that the pointee is
not part of the shared_ptr's value.  But again, many people don't
program that way.

>> A value type can contain a
>> reference to a shared cache as an incidental part, and this reference
>> can even be observable, as long as it is clearly distinguished as *not*
>> being within the boundaries of the value.  One consequence of that is
>> that the results of equality comparison would never depend on the state
>> of the cache.
>
> Agree.  I’m not sure why you would expose the cache, but it is
> effectively the same as the capacity of an array.  

It's a little different, from a thread-safety perspective.

> It is incidental and implementation related, not part of the salient
> semantics of the type.
>
>> 
>>> (immutable intersections are allowed because they cannot be observed,
>>> which Sean alludes to in passing).  Incidentally, it is pretty clear
>>> from the talk that immutable intersection is heavily used in Photoshop
>>> history in order to keep memory use reasonable.  This falls into the
>>> category of persistent data structures.
>>> 
>>> My impression is that Sean’s definition of "value semantics” excludes
>>> “intersecting objects” (where the intersection is mutable) and is
>>> aligned with John’s “full value semantics” and the notion of “pure
>>> value” we have been discussing.
>> 
>> I think I discussed this with Sean a week ago…
>
> And what was the outcome of that discussion?  I would be very
> interested in hearing what he had to say.

Unfortunately I don't remember; staying up to 3AM tends to blur some
details ;-)

> Let’s consider the Photoshop history example since that ties back to
> something we know has proven to work very well in practice in a large
> scale application.
>
> I’ll approximate based on what I could infer from Sean’s talk.  Among
> other things, the document aggregate contains bitmap values.  These
> are structured as a container of pointers to pixel buffers.  The
> entire document aggregate is a persistent data structure that uses CoW
> to share as much memory as possible between snapshots.  When a drawing
> operation is performed, relevant pixel buffers are copied and mutated
> by the operation and a new document snapshot is added to the history.
>
> It is absolutely essential to this design that the pixel buffer
> pointers are not shared with code that can write to them.  If this was
> allowed many snapshots would likely be affected and the history would
> be corrupted.
>
> The `Store` example above is intended to preserve the same semantics
> as Photoshop does with its history feature.  This depends on `State`
> being a pure value.  If `State` is
> `Array<MutableReferenceSemanticType>` those semantics simply cannot be
> preserved.  It is admittedly a toy example but I think it serves to
> demonstrate the point.

I don't agree.  What you're referring to is a matter of quality of
encapsulation rather than one of correctness.  You can easily see this
by refactoring your program whose `State` is
`Array<MutableReferenceSemanticType>` into one that has a global
`Array<MutableReferenceSemanticType>` somewhere, and whose `State` is
`Array<Int>` where the `Int` is, semantically, an index into the global
array.  This is a semantics-preserving transformation.  Now your `State`
is what you call a “PureValue” and your program is no more correct (or
incorrect) than it was before.

> You could argue it is unnecessarily limiting to constrain `State` to
> be a pure value.  I don’t think that’s a fair critique.  

I do argue exactly that, and though you may disagree with my argument,
I cannot imagine why you'd call it unfair.

> In any practical scenario where you would use `State` you actually
> *want* this constraint and want as much help as possible in ensuring
> that your program adheres to it.

To get sane semantic guarantees, you can constrain what information is
reachable from `State` *and* constrain the semantics of `reduce`, or you
could simply say that `State` is a value and constrain `reduce` to not
use `State`'s non-salient attributes.  If you say that protocols should
only expose salient attributes, you don't even need to add that specific
constraint to `reduce`.

IMO we are arguing at the margins because most value types don't expose
non-salient attributes at all, but your model would arbitrarily prevent
object identities from being used as values in many places where they
would work just fine.  If I represent selections in my drawing
application as `Set<DrawableObject>`, where object identity is used to
determine set membership, I don't want to be prevented from plugging
that into a generic component such as your `Store`.  And I don't see why
I should be.  That, right there, is a “practical scenario where you
would use `State`” and where `PureValue` makes no difference.

Furthermore, it complicates the user model.  How would I know whether to
require value semantics or `PureValue` in my generic component?  

-- 
-Dave