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

[Matthew Johnson]

> 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`.  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.  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.

> 
>> 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).

> 
>> 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`.

Requiring `reducer` to be pure is not enough if we allow `State` to have salient mutable reference semantics attributes.  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”.

> 
>> 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.

> 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.  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.

> 
>> 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.

> 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 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. 

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.

You could argue it is unnecessarily limiting to constrain `State` to be a pure value.  I don’t think that’s a fair critique.  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.

-Matthew

> 
> -- 
> -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/20160522/814b94f3/attachment.html>