On purity grades of value types [was: ValueType protocol]

I didn’t explain it well, but my idea was that definition of the equivalence is left to the type author. Effectively implementation of the == is the type-specific definition. And the way how authors of the type implement it affects if type is a value type or a reference type.

You don’t need to know if type is a value type for that. All you need is an implementation of Hashable conformance consistent with mutability analysis in Swift. If at some point of the execution of the Swift program x == y and x.hashValue == z there must be no operational on x which changes that, but is not a mutation from the type-checker perspective. This property must hold regardless of value/reference semantics. Types for which this property does not hold are buggy.

Which leads to a question: do you even care about value/reference semantics? Sounds like property you are interested in is “correct implementation of Hashable conformance”.

It is a set of types of variables used in an expression. We can prove that one of the types is not a value type, but actually it looks like we cannot even know which one. If all expressions using variables of single type T behave as if T is a value type, and all expressions using variables of single type U behave as if U is a value type, but there exists an expression using mix of variables of both types, that violates this, which type is to blame - T or U?

Yep, totally agree.

In practice, the distinction between value types and reference types is based on semantics, not the implementation. In practice, all data works with references: to CPU registers, for instance. Like GOTO, reference semantics are a reflection of how computers actually operate.

Current best practice is that things Swift calls value types implicitly use value semantics, things Swift calls reference types implicitly use reference semantics, and every deviation from that is carefully documented.

Container types like Array are self-documenting, more or less: Array<AnyObject> obviously (or rather, implicitly) uses value semantics while containing elements that do not. Same with Optional<AnyObject>. Note that the actual implementation is irrelevant: both Array and Optional use references internally to implement CoW.

As others have mentioned, a form of “purity grade” is actually in Swift 5.5 as Sendable. It makes weaker guarantees, of course; it promises thread safety, not value semantics. Even so, it can’t actually be compile-time checked, beyond basics like requiring final on classes. In fact, most protocol conformance cannot be checked for validity beyond having the right interface. In the end, you simply need to adopt norms as much as possible, document deviations from that norm, and trust others to do the same.

There's been enough confusion around value semantics that I don't mind breaking these ideas down further in the interest of clarity. A caveat, though: if you are looking for something deep in that breakdown you may be disappointed. At some point we will use plain human language to describe everything (even math), and I've used these words with their plain English meaning.

(Switching from a to v for clarity; my mistake for using a in the first place)

Code that observes the value of a variable v has semantics that depend on the value of v, and code that alters the value of v would affect the semantics of some hypothetical code-to-be-executed that observes (reads) only the value of v.

I can think of more elaborate ways to write these definitions that use fork() and specify program outputs for identical inputs and prohibit non-determinism such as random number generators, but although these approaches may seem to be founded on understood mechanisms, ultimately they fall back on simple English words such as “identical” that you'd be just as entitled to ask me to define.

Exactly! That's a feature, not a bug. Why do we want these different definitions? Will it help us to write or understand code? If so, how?

When you have a bunch of ideas competing for your attention it is tempting to compromise by validating all of them. I consider doing the work to discover the one essential concept and fearlessly label it as such to be a form of “not compromising.”

Technically, my definition is designed to get at the minimal necessary property for local reasoning (the hard part of the problem) and thus it deals with equality and hashing only as a convention, in the “Documenting Value” section. If a and b in your example have a well-behaved value semantic type by those conventions, of course the code would not assert. The properties you're testing with those asserts are covered by Equatable, Hashable, and Comparable protocols (you haven't said whether your type conforms to these) and are traditionally united in a refined protocol/concept called Regular. They are definitely important, but are not strictly necessary in order to solve the local reasoning problem, which is what everyone has struggled with for years.

the above grade system at least gives answers to questions like those (assert1 and assert3 will never trigger in absolute/clean/fair purity grade code but might trigger in dirty grade code, assert2 and assert 4 will never trigger in absolute purity grade code but might trigger in other grades)

The question is, do we want to encourage people to require, implement, document, and reason about shades of Regular-ity or should we just give them one simple tool, Regular? A crucial part of the generic programming process involves clustering the possible fine-grained distinctions among requirements into “Concepts”. The only reason to have two concepts instead of one is when the distinction enables useful expressivity that would otherwise be impossible or inefficient (we distinguish bidirectional collections from random access collections because, e.g., Set and Array are both useful and have inherently distinct properties). I claim that a type satisfying any of your “grades” can be made to satisfy Regular without any loss of expressivity or efficiency.

It would of course be fair to argue that you want to “cluster” the local reasoning property into Regular as well, and that a separate ValueSemantic property is unimportant. I'd certainly consider that idea.

I find that a bit shocking. Unless things have gone badly wrong while I wasn't looking, for most types, that relation depends only and entirely on the values of the types involved.

This is the problem with using “equivalence” and failing to define “value.” We should decide whether the value of a floating point zero includes its sign. If we want to claim it is Regular, we'd have to say no, that the sign of a floating point zero is a non-salient attribute.

Notably, my intuition is that Double is obviously a "value type". The fact that it has a loosey-goosey == definition does not preclude it from being one.

I'm guessing you're focused on the local reasoning part, which I'm calling “value semantics,” and not on Regular-ity, which seems to be @tera's concern.

i'm not saying that's a bug... it's a missing opportunity!

i hope you can agree with me that language like swift minus ability to override EQ/hash/lessThan would be "safer" than swift - if you can't customise those basic ops you can't make them bogus, mistakenly or maliciously. so a == b will always be b == a, a < b will always be !(b >= a), hashValue, ==, < will always deliver the same results for the sames values because built in functions can't be wrong, they can't hang, spend unreasonable amount of time, touch globals, block for unbound amount of time on mutex, and so on and so forth..

and i would definitely agree with you that this version of language would be quite restrictive to be useful, as ability to customise those basic ops opens many interesting opportunities!

the purity grading system i'm talking about combines these levels into one language - you now have a choice whether you want absolute safety at the price of inflexibility (absolute) on one end of the spectrum, or you want maximum flexibility at the price of safety (dirty) on the other end of the spectrum, or you have some reasonably safe and flexible "middle ground" (clean/fair). you can have different purity grades for different parts of the app following some simple (and enforced!) rules: when at purity level you'll only be able calling through the same or cleaner purity level.

Not in the sense that we use the term around here, i.e. to indicate memory, type, or thread-safety.

and i would definitely agree with you that this version of language would be quite restrictive to be useful, as ability to customise those basic ops opens many interesting opportunities!

But I didn't make that claim, so there's nothing to (dis)agree with.

the purity grading system i'm talking about combines these levels into one language - you now have a choice whether you want absolute safety at the price of inflexibility ( absolute ) on one end of the spectrum, or you want maximum flexibility at the price of safety ( dirty ) on the other end of the spectrum, or you have some reasonably safe and flexible "middle ground" ( clean/fair ). you can have different purity grades for different parts of the app following some simple (and enforced!) rules: when at purity level you'll only be able calling through the same or cleaner purity level.

Yes, and I'm saying that having many such choices is not necessarily empowering for programmers. Unless you already have a examples of many real-world types that fit into each of these categories but couldn't be made “absolute,” and can demonstrate how you would use the categories to describe algorithms or to reason about code that is currently hard to understand, I don't see any point in breaking the world up this way.

2 Likes

I'm also curious about what this buys the average swift programmer.

I wouldn't want to have to annotate every one of my functions with one of these purity levels. It also seems like the only backwards compatible option for a default would be dirty.

Let's say that I've now re-written my app and annotated the entirety of my architecture to support something that is absolute. What happens when I need some 3rd party library that either has no annotations (must be assumed to be dirty) or has a level below my level, do I need to rewrite my whole app in response?

The level of changes and invasiveness of the change don't seem like they match the benefits of what you get from it. As a trade-off for the effort involved here, what exactly is a developer getting in return?

1 Like

not necessarily every function: there could be a reasonable system with function inheriting purity level of class/struct it is defined in unless it wants to use a different level.

very similar situation you have today when calling third party code from a real time audio I/O proc ² : if that third party code can take a lock or call malloc (among many other dangerous things!) - you just can't call it directly, you either put it onto a different non realtime thread/queue and communicate with it by merely reading/writing to memory or you bin it altogether and use a different safer code when you prefer direct callouts from your I/O proc. in more traditional use case you'd probably call that "dirtier" code on a dispatch queue. or, if that's not a big concern to you, you make the relevant part of your code that deals with that third party code dirtier than it was before.

if purity grading system is introduced - it will first be adopted by libraries authors. apps that don't care can leave purity unspecified.

value safety (the opposite of value fragility). a dictionary or a set with their invariants broken because of duplicated keys - are broken values, and we can break them providing a custom code for EQ/hash to the things we put into these containers. ditto for a mere struct or enum. that custom code can happen in a third party library you are using or your own code. that code can be there either mistakenly or maliciously. you can't break "Int" or "Double" value types, Dictionary, Set or your custom struct/enum (*) are value types, and they shall be as unbreakable as primitive value types. imho.

(*) those that adhere to david's definition of value semantic.

a much more rudimentary example that illustrates the problem without involving collection types (here xxx is some struct/enum):

let a = xxx
let h1 = a.hashValue
let h2 = a.hashValue
assert(h1 == h2) // can happen at dirty purity level due to non pure "hash" or non pure "EQ" implementation.

to not have this situation you do these things: stick to discipline, introduce coding standards in your team, carefully audit third party code you are using to see what's it's doing, perform this audit on every update of that third party code and live dangerously as every now and then shit happens, even without third party code involvement. or you introduce a purity system to your world and let compiler do the relevant checks for you.

² - realtime audio code explanation

realtime audio code is a good example that illustrates when grading system is important. to oversimplify - you write code that can't call malloc / can't lock on mutex or semaphore, can't call dispatch async, etc. of course you can't use swift containers. imagine you need to write such code - every step is dangerous, you are on a mine field, and you are on your own as (currently) compiler can't help you. if you did a mistake - it might not be immediately obvious anything is wrong. until your app is already in the field and then it misbehaves on some user systems but not others. with "realtime" grade your life would be much easier as compiler would not allow anything unsafe automatically!

we can have a less derogatory name instead of dirty if that's a concern.

Apologies in advance as things like this in the forums can go a bit over my head, but I found this thread intriguing even though I don't know a ton about some of the lower level stuff like malloc, having come from a nontraditional background to programming.

I guess I'm imagining that this would propagate similarly to throws except that semantically I don't think it makes sense to have the purity version of a do-catch handling. Wouldn't that defeat the whole purpose of having something marked as absolute?

I think part of what I'm wondering here is that either the xxx type is unambiguous and the compiler can synthesize it (this is the approach I usually take when I need to have eq/hashable code in my own code by just marking the relevant members with the relevant protocols) or it would need to be written out manually. Is the idea that manually written code can't be absolute or how can you guarantee that manually written code for a Hashable or Equatable conformance fulfills the requirement?

sorry, i don't understand the question.

correct, "absolute" can't have custom EQ/hash at all. "clean" can't read/write external memory in their EQ/hash, "fair" can read but not write to external memory (clean/fair can be blended together with no much harm), "dirty" can do everything. interesting feature of clean/fair is that a custom "hashValue" (no matter how possibly written!) will always return the same result for a given value. this "mathematically bulletproof" aspect is what makes it so fascinating.

Maybe I can clarify with an example:

func embeddedFunction() {
  // Does something
}

func callingFunction() {
  embeddedFunction()
}

Given the above functions, we have a recourse in the future if embeddedFunction needs to be converted to throwing but the calling one cannot.

func embeddedFunction() throws {
  // Does something
}

func callingFunction() {
  do {
    try embeddedFunction()
  } catch {
    // Do catch let's me bail out if I need to call a throwing thing from
    // a context that won't throw and I can log or otherwise handle the error
  }
}

There's an escape hatch here for interfacing with a throwing thing that lets the developer control the flow of errors throughout the app and recover, log, or otherwise not handle. Given a function that would be marked as absolute, there would be seemingly no way to call a dirtier function. In fact, that's kind of the whole point, right?

dirty func embeddedFunction() {
  // Does something
}

absolute func callingFunction() {
  embeddedFunction() // not callable here and no way to do so
}

If the embedded function needs to change absolute to less pure there's no other option but for that to propagate all the way up the call hierarchy. Is this the trade-off you were referencing between strictness and flexibility?

indeed, absolutePureFunction() will not be able calling a function which is dirtier than absolute. (like kernel space code can't call user space code. or realtime safe code can't call non realtime safe code. like low level code generally shall not call high level code (i still remember that odd looking "reinsert ejected disk or press cmd+. to abort" alert window when the app attempted to read a file on the ejected disk)).

you can add that as a tradeoff that "dirty is unsafe but can call anything". basically i meant that the cleaner you go the more mathematically bulletproof your app is, but at the same time the fewer things you can do. as an example you can have a non customisable always right bitwise a < b on the absolute level but to make it customisable you'll need to go to clean/fair level, and to base it, say, on system locale comparison rules (that can dynamically change) you'll need to go to the dirty level. and the dirtier you go the less mathematically bulletproof the app is (irt value type axioms, app correctness, halting, crashes).

I think my vague uneasiness comes from a few things overall here as someone who usually works with Swift at a higher abstraction level:

  1. Are there any cases where it would be either valuable or appropriate to override the compiler here? This discussion makes me think of when I've done some physics work in the past for school and you have to assume that the object is a sphere with zero friction to get it to work out for the calculations. Is it possible in the real world to make these kinds of guarantees about absolute code, or will it be very rare in practice?

  2. It seems likely that purity levels have the potential to cause a lot of code churn as they display similar propagation patterns to others that we've seen in some of the other effectful systems in Swift (try/throw, async/await). You've said that there could be some sensible defaults, but I'm not sure what that would mean or how that could help mitigate some of the issues here.

  3. How would this play with progressive disclosure? So far all of the examples that you've added here seem to be at lower level of abstraction or more niche code. With other features that are powerful and niche, they tend to have a smaller footprint and "scarier" names whereas this seems to be at a similar level of visibility and prominence as something like access control levels or throws and the like. I suspect that someone writing a Vapor app or working on one of the Apple platforms may not necessarily want to have to consider the same guarantees or matrix of choice presented here. How do you envision something like this working with progressive disclosure?

Terms of Service

Privacy Policy

Cookie Policy