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

Matthew Johnson matthew at anandabits.com
Mon May 23 09:10:51 CDT 2016

> On May 22, 2016, at 3:34 PM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
> 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.

Let’s say we intend to preserve snapshots of our state at each point in time in order to preserve history, which is what `Store` is doing for us.  In this case `State` cannot have any mutable shared parts.  This means that each `DrawableObject` must be a pure value - either a value type or an immutable reference type.  Every time the state of a `DrawableObject` is modified (by the `reducer`) a copy must be made.  This means that (assuming `DrawableObject` is an immutable reference type - if it was mutable our history would easily be corrupted).  Identity of the reference != identity of the entity.  At best reference identity can be viewed as the identity of the state of the entity at a specific point in history.  In this design reference identity is not a good way to reference the entity.  Using reference identity is probably not the right way to model selection.  It is probably better to use a stable reference to the entity itself rather than a reference to its state at a specific point in time.

For the sake of argument, let’s say we still want to model selection this way.  Any time a copy of the `DrawableObject` is made as the result of an action we must also remember to make a new selection set that points to the new instance (with the old old instance removed) if the `DrawableObject` is selected.  Getting this inter-dependency right everywhere is going to be a challenge.  Modeling selection in some other fashion is likely going to be a much more robust design.

Requiring `State` to be a pure value can help guide users away from this kind of problem.

Moving to a new topic, you have said this several times: "I don't believe it's appropriate to represent that with a protocol, because I don't believe there exist any generic components whose correctness depends on it."

I believe heart of the issue here is that “correctness” depends on the specification.  For example, I do not believe it is possible to correctly implement a generic CSP channel without a `PureValue` constraint on the message type. 

You can look at the world in such a way that you could “correctly” implement a CSP channel that allows you to pass references to shared mutable state across the channel.  However, violates the specification of what a CSP channel is.  It also largely defeats the purpose of using CSP in the first place.  It might be reasonable to *implement* the CSP channel with constraints that allow for this and it might even be reasonable to expose it via public API as an unsafe channel (or something like that).  But it certainly should not be the default or recommended interface to a CSP channel.

When you write a program where threads only communicate by sending pure values over channels you have a global guarantee that your program does not have data races. This global property depends upon the fact that references to mutable state cannot be shared between threads (excepting transfer of ownership where the reference in the sending thread is guaranteed to be unique and is invalidated by a linear typing mechanism), in other words it depends upon the interface having a pure value constraint.  This emergent global property is an example of what I mean when I say "constraints can be liberating".

Correctness of implementation may not always be the same as correctness of interface.  “Arbitrary” restrictions on the interface can be extremely useful.  They can provide extremely useful, higher level properties and guarantees about larger pieces of your application that would be lost without these constraints, as in the CSP example. So even if they are not strictly necessary to the implementation, they can be necessary for the correct design of an interface that meets a specification designed to allow such properties to emerge.

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

This question actually kept me up last night.

One reason to use PureValue is to allow make your interface safer and / or easier to use correctly.  The CSP example and the Store example are relevant here.

Aside from that, I think it is worth noting that genericity is not a black and white property.  You can take it to the extreme as Stepanov teaches.  This is beautiful and is the right thing to do in widely used libraries.  However, it does come with a cost.  Generic code is more complex to design, reason about, and implement correctly.

Most applications contain a mix of concrete and generic code.  The generic code has varying degrees of genericity.  We choose constraints that provide the genericity we need while providing guarantees that reduce the scope of what must be considered when reasoning about the code.  There are good reasons, both technical and economic, for doing this.  

If a PureValue constraint makes it easier to reason about your code and does not inhibit the genericity you need it may be worthwhile to introduce the constraint.  If it turns out that you later need more genericity you can always revisit the code and consider lifting the constraint.  


> -- 
> -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/20160523/ffedf1da/attachment.html>

More information about the swift-evolution mailing list