Author: Matthew Johnson
This document explores the issues surrounding adding language support for value semantics and pure functions. It also explores a possible design for doing this that brings compiler-verified referential transparency to Swift. The goal is to initiate a serious discussion of these topics in the Swift evolution community as well as attract collaborators who are willing and able to work on implementation.
These topics have been discussed several times by the Swift evolution community. Threads discussing value semantics can be found here, here and here and an old document discussing the topic is here. Threads discussing pure functions can be found here, here, here, here and here. Note: thread titles don't always reflect the course the discussion eventually takes and in some cases the most relevant discussion is not at the beginning of the thread. Michel Fortin in particular has invested significant energy into pure functions for Swift. One of his posts includes some important semantic questions for us to consider.
Before we explore the motivation and solution in depth, let's begin with a few observations. Some of these observations should be uncontroversial while others are derived from the author's experience and others may disagree. Robust discussion of these observations is welcome.
This is a natural consequence of the decision to support first-class value types and use them heavily in conjunction with copy-on-write in the design of the standard library and Foundation. User-authored value types that are aggregates of value-semantic types provided in the standard and other libraries and do not use shared mutable state in their implementation also have value semantics. Value semantics composes cleanly.
In the author's experience it is safe to say that most value types in Swift have value semantics, especially at the application level. In many cases a foundational value type provided by a library will not have simple value semantics (by way of composition) but in most cases they will still have value semantics (by using copy-on-write).
Value types without value semantics are not rare but they are in some sense the exception that prove the rule. Further, value types that do not have value semantics tend to be much more rarely used than those that do have value semantics (such as the Unsafe… family) in most code, especially application-level code. A quick survey of the standard library and Foundation supports these observations.
This is a natural consequence of having a lot of types with value semantics. Instances of a type that has value semantics must be independent when copied. They cannot share mutable state with each other in an observable way.
It is also rather unusual to see a member of a type with value semantics that produces an observable side effect. Crucially, mutating methods are simply another way to return a value: mutating does not imply that a side effect will be produced, only that the prior value will be replaced. The semantics are identical to calling a non-mutating method that returns a new value and immediately assigning it to the variable on which the method was called.
While it is possible for a type with value semantics to provide an impure member doing so is relatively unusual.
The use of free functions is discouraged in idiomatic Swift. Settting them aside leaves us with members and closures.
The purity of a closure will usually be specified by a type context and checked rather than explicitly stated. The implication is that any annotation burden will usually fall on the code defining the type context, not the closure itself.
While pure members are not uncommon in reference types they are far less common than they are in value types. Further, they are often exclusively (or almost exclusively) used by code that is already impure and often nearby. This is a natural consequence of reference semantics. The value of recognizing these members as pure is much less than for value-semantic types.
For example, a view may have the following properties: let horizontalPadding: CGFloat and var horizontalMargin: CGFloat { return horizontalPadding * 2 }. These pure properties will typically be used in layout operations with many side effects. When a non-trival amount of pure code like this is found in a type with reference semantics there is usually a good opportunity for refactor and introduce a supporting struct that has value semantics.
Some readers may be thinking "but a reference type can have value semantics". This is true as long as we set aside object identity as well as weak and unowned references. In fact, the members of a reference type only storing immutable data will usually be pure. However, as we will see later on, there are good reasons to restrict language-recognized value semantics to value types. There are also attractive opportunities to minimize the cases where a value-semantic reference type makes sense. This approach would result in immutable reference types being relatively unusual.
While these topics are theoretically independent they have a significant relationship that should not be ignored. There is a lot of leverage to be gained by considering these topics together and designing language support that takes advantage of this close relationship.
In his concurrency manifesto, Chris Lattner discusses the disadvantages of shared mutable state. His discussion is restricted to sharing across concurrency contexts. This is appropriate for a document focused on concurrency but we should also consider the problems shared mutable state causes even when concurrency is not present.
Any UI programmer will be familiar with how difficult a graph of mutable objects can be to reason about even when all the code runs within a single concurrency context (in this case, the UI context). This complexity is magnified in the presence of global state (often in the form of singletons accessed directly via a shared property) and broadcast control flow mechanisms such as notifications and signals.
When attempting to understand such a system we must contemplate a complex, dynamic network of relationships between objects, the messages that flow between them, the state each of them maintain, and the behaviors dependent upon that state. These systems quickly become more sophisticated than any of us can fully understand. It is not possible to fully reason about any part of the system without considering the whole. In order to be complete, reasoning must be global. This problem is explored in depth in the paper Out of the Tar Pit.
There is nothing inherently wrong with these systems. In fact, they are necessary. Resources are real and our programs couldn't accomplish any meaningful work if they didn't perform IO. On the other hand, maybe we will better off if we avoid the complexity of shared mutable state and pervasive side effects when we don't really need them. And as it turns out, we don't need them nearly as much as we often think we do.
Pure functions and value semantics give us the ability to reason locally about our code: a function takes zero or more values, returns zero or more values and that's it. The property that underlies this locality of reasoning is known as referential transparency which Wikipedia defines as follows:
An expression is said to be referentially transparent if it can be replaced with its corresponding value without changing the program's behavior.[1] As a result, evaluating a referentially transparent function gives the same value for same arguments. Such functions are called pure functions.
Wikipedia elaborates in the definition of pure function:
In computer programming, a function may be considered a pure function if both of the following statements about the function hold:
- The function always evaluates the same result value given the same argument value(s). The function result value cannot depend on any hidden information or state that may change while program execution proceeds or between different executions of the program, nor can it depend on any external input from I/O devices (usually—see below).
- Evaluation of the result does not cause any semantically observable side effect or output, such as mutation of mutable objects or output to I/O devices (usually—see below).
The result value need not depend on all (or any) of the argument values. However, it must depend on nothing other than the argument values. The function may return multiple result values and these conditions must apply to all returned values for the function to be considered pure. If an argument is passed by reference, any parameter mutation will alter the value of the argument outside the function, which will render the function impure.
The notion of value semantics is not usually associated with functional programming for a simple reason: all values in a pure functional language have value semantics! In languages like Swift where that is not the case the distinction becomes crucial.
The advantages of restricting programs (or at least the parts of them we can) to the referentially transparent realm of pure functions and values have been recognized for a very long time.
It has been almost 40 years since John Backus gave his seminal Turing Award Lecture titled "Can Programming Be Liberated From the von Neumann Style" where he lamented the "lack of useful mathematical properties for reasoning about programs" and observed "there is a desperate need for a powerful methodology to help us think about programs, and no conventional language even begins to meet that need". The lecture proceeded to outline his research into functional programming. The director of the team that invented FORTRAN finished his career convinced that imperative programming was not able to meet the need of programmers to reason about their programs.
Anyone interested in exploring the research into the advantages of functional programming may wish to begin with one of the most widely read papers on the topic: John Hughes' classic manifesto "Why Functional Programming Matters". Over the last few years John has being giving talks based on this paper.
Industry adoption of ideas originating in functional programming has been somewhat slow but has also been happening for a long time and has been accelerating for the last decade or so. This includes functional or functionally-inspired libraries in imperative languages as well as both dynamically and statically typed functional languages (most of which are actually multi-paradigm, also including support for an object system of one kind or another). This section briefly discusses some of the more notable examples.
Erlang was the first functional language to be deployed at scale in a mission-critical application, first at Ericsson and later elsewhere. The Wikipedia article on Erlang quotes Tim Bray's OSCON in July 2008 where he said:
If somebody came to me and wanted to pay me a lot of money to build a large scale message handling system that really had to be up all the time, could never afford to go down for years at a time, I would unhesitatingly choose Erlang to build it in.
Erlang was also an industry pioneer of the actor model which clearly plays a large role in the stability of Erlang servers. That said, the role of its functional approach should not be minimized.
More recently, the dynamic functional language Elixir which runs on the Erlang platform has seem some adoption in the web server domain, particularly among those who formerly used Ruby.
In the .NET community LINQ and Rx are the most widely used, functionally inspired tools (known to the author). Erik Meijer helped to design these features and has been an important evangelist for and educator of aspring functional programmers in the .NET community. The .NET platform also hosts F#, one of the more widely used languages in the ML family.
The JVM platform hosts two very popular functional languages. Scala is a statically typed hybrid functional language that sits somewhere between Swift and Haskell in approach. Clojure is a modern Lisp supported by carefully selected and well designed libraries.
Clojure's persistent data structures are probably are perhaps the most widely used implementation of purely functional data structures. This family of data structures was the subject of Chris Okasaki's PhD dissertation and subsequent book. The most important attribute of data structures in this family space-efficient sharing. This allows them to scale extremely well supporting localized mutation of large collections with minimal copying while sharing no mutable state. This is an extremely important property. It would be wise for the Swift community to eventually adopt a standard implementation, although that is beyond the scope of this document.
The Clojure implementation takes performance very seriously and includes support for controlled local mutation via transients. The name "transient" sounds fancy but they are basically equivalent to copy-on-write, but place an unfortunate syntactic burden on users when mutation is used. Jean Niklas L'orange has a good 5-part blog series discussing the implementation: part 1, part 2, part 3, part 4 and part 5.
Rich Hickey (creator of Clojure) has been one of the most prominent advocates for functional and value-oriented programming in the industry for at least a decade and is an incredible speaker. He has given several talks relevant to this document. Are We There Yet explores the relationships between identity, state and value. In The Value of Values he compares value-oriented programming to imperative and object-oriented programming (often referred to as place-oriented programming in the talk). In The Language of the System he discusses how to leave object-oriented habits behind and design value-oriented systems.
Facebook's engineering teams have released a number of libraries designed with a functional approach. React rapidly became one of the most widely used libraries for building web front ends. Facebook is even bringing first-class support for functional programming to React with the OCaml-inspired language Reason.
Elm is a Haskell-ish language (modulo the fancy type system) that takes a similar approach using an even more functional style.
UI programmers in the Swift community have been inspired by both React and Elm, releasing a number of open source experiments and libraries.
Swift is already a good (not great) language for writing in a functional style. Copy-on-write value semantics gives us independent values that behave like values in functional languages. Swift also plenty of syntactic sugar that makes functional code a pleasure to write and pretty to read.
Many Swift programmers have been taking advantage of this ever since the language was first released and have explored many different ways to leverage this. Chris Eidhof, Florian Kugler, and Wouter Swierstra have published a book Functional Swift teaching Swift programmers how to approach the language from a functional perspective. The annual Functional Swift Conference (with videos available) is a place where Swift programmers can share their experience with and approaches to functional programming.
Andy Matuschak's talk Controlling Complexity in Swift: Making Value Types Friends does a particularly good job of explaining the advantages of value semantics and how we can take advantage of it in Swift. He uses the wonderful analogy of a zoetrope to explain the relationships between object, identity, state, value, time and causality. Later on Andy acknowledges that he is talking about functional programming. He presents the approach of "functional core / imperative shell" previously advocated why Gary Bernhardt in the talk Boundaries. This can roughly be thought of as a functional analogue of the Clean Architecture .
Dave Abrahams introduced all of us to Protocol-Oriented Programming (and Crusty!) at WWDC in 2014. This talk demonstrates how we can use value types and protocols instead of objects and inheritance when implement abstractions in Swift. The techniques covered in this session are crucial for Swift programmers that want to move away from object-oriented designs and toward designs that use value semantics and pure functions.
Swift is its own language and we must learn to think about values and pure functions in the way that is most appropriate for Swift. The idioms, patterns and techniques used in functional languages may or may not be idiomatic in a functional subset of Swift. In many cases there will approaches that are better suited to Swift.
Doug Gregor's 2015 WWDC session Building Better Apps with Value Types in Swift illustrates this very well. Sometimes there is fundamental Big-O performance gap between imperative algorithms that leverage mutation and purely functional algorithms only create new values. In other cases controlled local mutation (as provided by Swift's mutability model) can simply result in more clear (or more familiar) code without significantly harming to our ability to reason about its behavior. Copy-on-write value semantics allows us to have our cake an eat it too: we can use imperative algorithms to realize optimal performance without sacrificing referential transparency. Swift is the first language (known to the author) to adopt this approach fundamental in the design of its basic types.
Whether we write code inspired by other languages or discover new ideas idiomatic in Swift, language support referential transparency in the form of pure functions and value semantics will is one of the most impactful enhancements we could make to support the community that is actively using Swift in a functional style as well as all Swift programmers who rely on value semantics in one way or another.
As the previous sections demonstrate, functional programming is increasingly important to the Swift community as well as the broader industry. All indications are that this trend is only going to continue accelerating in the future. With first-class language support Swift will become one of the best languages available for writing production code in a referentially transparent style.
Without language support we rely on discipline and trust when attempting to program in a functional style. This can take us a long way but we will never have the same degree of certainty when reasoning as we can with language support. Any mistake that compromises purity or value semantics is viral - it compromises any function that calls the accidentally impure function or type constructed in terms of the type that was intended to have value semantics but does not.
To paraphrase Evan Czaplicki (creator of Elm) from a recent talk, even when you're attempting to write pure code in an imperative language as the lines of code increase the probability of having shared mutable state somewhere approaches 1. In a language (or subset of a language) which guarantees referential transparency the probability is 0 no matter how many lines. Purity doesn't tend to scale with correctness unless there language support.
This problem is compounded in team environments where a mix of skill levels are present. Without language support, programmers who are still learning to work in a functional style are likely to unintentionally compromise the purity of a function or the value semantics of a type. A disciplined team may catch many such mistakes in code review but some will inevitably slip through. With language support these mistakes will be caught immediately. Even better, the compiler will provide immediate feedback to programmers learning this style. This rapid feedback will often speed up the learning process.
As will be demonstrated in this document, there are a lot of subtleties involved in defining purity and value semantics in a language as rich as Swift that most Swift programmers will not have thought deeply about. Even when they have they may choose definitions with varying levels of strictness, resulting in a compositional behavior where the least strict semantic wins. Even then, the compiler will offer no help in upholding even the least strict semantic.
Through language support we can adopt common definitions. Swift programmers will not need to know about the subtleties involved unless they happen to do something that violates the semantic contract. At this point they should be motivated to learn why a particular piece of code causes a function to be impure or a type to not have value semantics.
Language support is especially important for generic and higher-order code that needs to rely on the properties provided by pure functions and value semantics. For example, a data storage library may be designed to work with Codable types that have value semantics as well as predicates and sort comparators that are pure functions. Without language support this library is unnecessarily vulnerable to accident and abuse.
As Chris Lattner mentioned in his concurrency manifesto, a guarantee of value semantics allows us to safely send a value from one concurrency context to another. The fundamental reason for this is the purity of its members. In fact, if a type that has value semantics contains an impure member it is not safe to invoke that member on a value received from a different concurrency context.
It is highly desirable that a library be able to rely on the value semantics of generic or existential types and the purity of user-supplied functions in order to safely move them between concurrency contexts. This is a little bit precarious without language support. The best a library can do right now is to document the semantic requirements of user code and offer a "use at your own risk" guarantee. This can result in complex defensive code in libraries that attempt to maintain safety in the presence of unverified user code. We can and should do better.
Well designed language support for value semantics and pure functions will bring semantic clarity to all Swift code. Establishing a clear and common understanding of what these mean in Swift is a obviously prerequisite. Additionally, the semantics of code that does not meet these requirements will be clarified.
A good example of how language support can increase clarity is the following struct that has somewhat unusual semantics:
import ReactiveSwift
struct ObservableInt {
private let (signal, observer) = Signal<Int, NoError>.pipe()
var changeSignal: Signal<Int, NoError> {
return signal
}
var value: Int {
didSet {
observer.send(value: value)
}
}
}This is obviously a toy example but code like this has been seen in shipping apps with many users. In real world code the struct is likely to be much larger and a maintenance programmer might not even notice that it vends a signal.
It is quite likely that this type does not behave as the author intends. When copies are made the pipe is shared. Listeners to the signal will receive unexpected change events containing unexpected values. The problem can be masked by the fact that it works as long as no calling code registers listeners through two different copies that share the same pipe. A problem like this can be latent in a code base for a long time before manifesting as an observable bug.
Maybe some authors really do intend to write a type like this because they know all usage sites and believe it to be appropriate to the circumstances. We shouldn't prevent them from doing this but requiring a second thought seems appropriate given the potential for trouble. Value types that do not have value semantics are a relatively advanced tool. They are much too easy for a programmer to create unintentionally in Swift today.
Well designed language support for value semantics will highlight value types with unusual semantics such as this. It will also help to highlight any impure members of a type that does have value semantics. This brings semantic clarity to both the author and users of the type. It does so especially where it is most necessary: when the usual semantics do not hold and the programmer must pay closer attention to what they are doing.
Functional programming has been rapidly gaining mindshare and adoption in the industry in many domains. Swift is already an excellent language for many functional idioms. However, supporting it properly requires providing language-level verification of referential transparency in the form of pure functions and value semantics. Combining these powerful tools for understanding our code with our existing ability to implement high-performance libraries (using low-level, unsafe tools when necessary) should play an important part in Swift's plan for world domination.
All programming languages intended to accomplish meaningful work require an implementation that runs on the machines we have: it must eventually be defined in terms of processor instructions, memory and register access, IO, etc. Even a pure functional language with lazy evaluation such as Haskell must have an implementation that allocates and collects memory, implements the IO monad, etc. The design question is not whether such an implementation exists, but what relationship it has to programs written in the language.
One choice is to place the boundary between pure code and impure implementation at the compiler and runtime as Haskell does. Another option is to extend the boundary to the implementation of (some) libraries written in the language itself. These libraries can use annotations to tell the compiler when the programmer is taking care to provide a pure or value-semantic implementation despite the inability to statically verify that the implementation upholds the specified semantic.
In either case the correctness of compiler verification rests upon the correctness of the implementation. The latter approach obviously leaves a lot more room for mistakes - the size of the impure implementation is unbounded and open to users. In practice this would be roughly analogous to Swift's approach to memory safety which works very well.
Our approach to purity should adopt this philosophy: any design must include the ability for a programmer to include an annotation asserting that a piece of code upholds the semantic contract required of a pure function or value semantics even when the implementation is such that the compiler is not able to prove it correct. This capability is necessary for the efficient implementation of copy-on-write types that the compiler acknowledges as having value semantics and pure members. The implementation of these types must be possible not only in the standard library but also in 3rd party libraries.
These annotations should be similar to unsafe constructs in the sense that they should stand out at the point of use and be discouraged in application-level code. They assertions they make will serve as postulates upon which the compiler can prove the purity of user-code which does not make use of them. Similar annotations could be used when importing C functions and constants known to have pure implementations.
Any optimizations that take advantage of the properties of purity will need to be considered carefully: ultimately purity will rely upon the correctness of arbitrary code. This should be acceptable as optimization is not the driving motivator for adding language support for pure functions. As in D, the implementation could also include a notion of a "strongly pure" function which only relies (directly or indirectly) on trusted unsafe(pure) annotations such as those provided by the standard library. The optimizer could be more aggressive in optimizing the use of "strongly pure" functions. This distinction would not be visible in the programmer model.
D is the language most similar to Swift that supports pure functions. When thinking about what semantics might be appropriate for Swift it is instructive to consider the prior art.
D does not allow anything like unsafe(pure). Instead, D allows a pure function to write to any (possibly shared) state reachable via its arguments. This approach works well in D because it also has a transitive immutability model that can be used to strengthen the effective purity of a pure function.
The motivating observation behind design decision is that under the relaxed definition of purity a function can be considered strongly or weakly pure based on whether or not it has any arguments through which mutable state can be reached. Weakly pure functions are safe to call from strongly pure functions. This is because they are only allowed to use shared mutable state reachable via arguments while a strongly pure function cannot possibly provide such an arguments. Any mutable state which is reachable must be local to the strongly pure function.
The end result is that the relaxed requirement for purity in combination with transitive immutability results in many more functions being pure than would otherwise be possible, all without the need to trust a programmer annotation. Anyone Interested in learning more about pure functions in D may want to read this detailed discussion of pure functions.
If transitive immutability were ever added to Swift we may be able to relax some of the rules in contained in this document allowing us to reduce the need for the unsafe(pure) modifier. Even then, including this modifier is necessary in Swift. A mutating member of a copy-on-write type would not be able to provide the strongly pure guarantee that should be possible because we know it will not read or write shared mutable state. Further, unsafe(pure) is analogous to the model we use for memory safety and facilitates C interop.
A design that allows arbitrary code to declare itself to be pure must clearly define the semantic contract that pure functions must uphold. This means we must define clearly how we interpret "the same result value given the same argument value(s)" and what constitutes an "observable side effect". The compiler will ensure this contract is preserved by functions that are defined only in terms of other pure functions and do not directly use an unsafe(pure) annotation anywhere in their body. (In this section, "function" is used generally: initializers, properties, subscripts and methods are also included.)
There are several cases to consider.
The only sensible meaning of "the same" for metatypes is identity which is how == is implemented for them.
It is less obvious here, but we must also use identity for class instances. This carries the implication that a pure function may not return new instances of reference types. As we will see below, they are still allowed to create new instances if that is necessary to the implementation.
Object identity must be used even if a class happens to implement Equatable, and even if it is final and all members are pure, and all stored properties are immutable. This gives the class value semantics according to the common definition but there remain easily observable differences between different instances of any class, specifically weak and unowned references. We could make an exception for value-semantic classes and use Equatable instead, but the author believes this is not the right approach. The issue of value-semantic reference types is discussed in more detail the section on value semantics.
Value types that have value semantics should always implement Equatable unless an implementation is not pragmatically possible or efficient. Even when they don't implement Equatable the documentation for the type should define a logical equivalence congruent with behavioral equivalence that is to be used when reasoning about code that works its values. Either way, for the sake of purity we simply use equality to determine whether two values are "the same".
It is not possible to define "the same with respect to purity" in the general case for value types that do not have value semantics. The conservative approach is to simply say pure functions cannot traffic in these values. At first this seems overly restrictive but the subtleties that are possible with such types may make it attractive. For example, consider the following type:
struct StringRef: Equatable {
var string: NSString
static func == (_ lhs: StringRef, _ rhs: StringRef) -> Bool {
return lhs.string == rhs.string
}
}This type simply wraps a reference to an object and provides a forwarding implementation of Equatable. It is possible to have two instances of this type wrapping different instances of NSString while still comparing equal. Because the reference is exposed by the API of this type and object identity is relevant with respect to purity we cannot consider two such instances to be "the same" with respect to purity despite the fact that they compare equal. Note: it is not the mere existence of a reference property or the use of a class's implementation of Equatable that creates this potential - it is the fact that such a reference is accessible outside the implementation of the type.
On the other hand, many value types that do not have value semantics will have a conformance to Equatable consistent with the present rules. UnsafePointer is a good example.
Perhaps all we need to do is admit that the notion of "the same with respect to purity" is stricter than Equatable because it incorporates object identity. Just as two instances with the same hash value are not necessarily equal, two instances that compare equal may not be "the same with respect to purity". The latter also requires any corresponding references from which an aggregate value is composed to be identical, not just equal.
If we decide to adopt the more relaxed policy it will probably need to be a semantic requirement that is not strictly enforced by the compiler (although a best-effort attempt at enforcement could be implemented). In scenario it may be desirable to require an unsafe(pure) annotation indicating that the programmer is responsible for maintaining part of the semantic contract of purity.
There are three ways we might consider function values "the same" when they are used as arguments or results of a pure function:
- Consider functions "the same" only if they refer to identical code and if relevant, an identical context pointer.
- Consider functions "the same" if they refer to identical code and all captures in their contexts are "the same" according to the present rules.
- Use a more relaxed, behavioral notion of "the same" that only considers arguments, results and side effects.
The first possibility is excessively strict: this would prevent a pure function from returning a closure that captures its arguments, even when the captured arguments have value semantics.
The third possibility has some appeal, especially when the argument or result functions are pure. Logically: { (x: Int) in x * 2 } == { (x: Int) in x + x }. These functions always produce the same result given the same argument.
The second possibility appears to be the most pragmatic and is probably the definition we should use when considering whether two function arguments to or results from a pure function are "the same".
Note: a pure function may accept impure functions as arguments and return them as results as long as it does not call them and the context of any impure function results meets the present requirements of being "the same" when arguments are "the same".
Observable side effects include the following:
- performing I/O
- deadlocks, race conditions, and other synchronization issues
- reading or writing shared mutable state in an observable way
- making available shared mutable state
- observable reference count operations
Significant performance degradation in the presence of concurrency due to things like lock contention falls into the category of "other synchronization issues". While we want to preserve flexibility for the implementer we also want the ability to freely call a pure function from any concurrency context without having to worry about concurrency-related performance issues. Exactly what constitutes a significant performance degradation is something the community should consider carefully, including the potential for accumulated degradation when a pure function makes use of many other pure functions that in turn use many other pure functions.
Reading shared mutable state is not technically a side effect but is included anyway while we are listing things a pure function is not allowed to do.
Making available shared mutable state is a somewhat subtle notion that seems necessary in a language with an unsafe(pure) mechanism allowing low-level implementations to be considered pure. A good example of what this means is a function that maintains a thread-safe memoization cache. By using unsafe(pure) the author will be able to read and write shared mutable state but any result returned must have been computable from the input alone. The address of the cache itself and any previous arguments or results (for other argument values) it stores are not computable from the input and may not be returned from a pure function.
The example of a memoization cache is also useful for discussion of observable reference count operations. If such a cache were to hold a strong reference to an argument or previous result it could extend the lifetime of the referent and influence the behavior of code holding weak or unowned references to the referent. The potential to influence conditionals must be considered observable side effects. Weak and unowned references do not have the potential to extend the lifetime of the referent so a memoization cache could store them without producing an observable side effect. Similarly, strong references to instances not visible outside the implementation are not able to influence behavior of the rest of the program and holding them does not constitute an observable reference count operation.
- accessing register flags (using the same or similar rules as D)
- writing to
inoutarguments - reading or writing to shared mutable state in a non-observable way
- unobservable reference count operations
- weak reference count operations
- allocating or deallocating memory
- trapping
- throwing an error
- limited debug I/O
In Swift inout arguments are semantically equivalent to a return value that is immediately assigned to the argument's storage.
The second item makes a crucial distinction between observable and non-observable access to shared mutable state. This was already alluded to above through the example of a memoization cache.
A crucial example that includes both access to shared mutable state and unobservable reference counting is that of balanced reference count operations. Incrementing and decrementing even a strong reference count is not observable as long as the counting is properly synchronized and the count is the same when a function exits as it was when the function was entered.
Trapping is not itself an observable side effect but can be a result of an observable side effect. For example, a trap due to a precondition violation such as a subscript out of range, an integer overflow or divide by zero are not an observable side effects. Traps like this are caused directly by the input and are part of the semantic contract of the function. Unless we want to prevent pure code from subscripting an array we need to allow pure functions to have preconditions.
Traps that are not directly caused by precondition violations must be considered observable side effects. For example, a trap caused by force unwrapping a weak reference stored in a memoization cache would not have happened had the result computed directly. Traps like this are a violation of the semantic contract of purity.
In Swift we can consider throwing an error just another way to return a value. This means that while the act of throwing itself is not a violation of the requirements of purity throwing could still violate the definition of purity in some cases. For example, throwing a reference to a memoization cache violates purity for the same reason returning it does as would propagating an error thrown by a method of the memoization cache.
Finally, in the spirit of pragmatism we will want to support the debugging of pure functions by allowing some limited I/O to happen. D includes a debug statement modifier that pure functions can use to perform any impure operations for the purposes of debugging. Statements that include this modifier are only included in debug builds.
This approach is simple and flexible but feels too permissive as it can cause debug builds to behave arbitrarily different ways than release builds. If a programmer really needs that degree of flexibility the design in this document is already capable of supporting it by combining #if DEBUG with unsafe(pure). The extra verbosity is probably warranted outside of the most common and least dangerous debug needs such as writing to the console. The community should have a robust discussion about what kind of debug exceptions we really need to support with convenient syntax.
A value is has meaning independent of identity. The meaning of the value can be thought of as a Platonic form
Forms are mind independent abstract objects or paradigms (παραδείγματα: patterns in nature) of which particular objects and the properties and relations present in them are copies. Form is inherent in the particulars and these are said to participate in the form.
When a type has value semantics each instance is a particular which participates in an abstract form. For example, the Swift value 42 as Int participates in our abstract notion of the integer 42. This relationship allows us to ignore any differences between the particulars and reason in the abstract. This stands in stark contrast to entities which have state, identity and usually form a complex graph whose dynamic behavior we can only attempt to comprehend.
Some values (such as integers) are atomic while others are aggregates. This distinction can be a little bit subtle: a UInt could expose a Bool property corresponding to each bit. While that is true, the bits are an artifact of one way to represent an integer. The integer's value is intrinsic and does not rely upon an underlying collection of bits.
On the other hand, the value of a tuple of type (UInt, UInt) is clearly an aggregate - it's value is composed of two unsigned integer values placed in a specific arrangement. [Int] also an aggregate values. It places any number of integers in a specific arrangement. Aggregate values can only be composed of parts that are also values: a tuple of type (Int, AnyObject) is not a value.
The essential operations of a value are in intimate relationship to the structure of the value and are the fundamental building blocks upon which composite operations may be assembled. All essential operations on a value must be pure and must only accept values as arguments and return values as results. These constraints bound a referentially transparent world that facilitates equational reasoning. When essential operations on values are composed this property is preserved. If the type obeys any interesting algebraic laws they should be mentioned in its documentation as a further aid to reasoning.
It isn't important that we precisely define which operations are essential and which are not. What is important is that a type offering value semantics provide referentially transparent behavior in most or all cases. Without a foundation constructed with values and pure functions this is not possible. For example, if the operations that read and write individual parts of an aggregate value were not pure it would be impossible to write a pure operation over it. Further, if the elements of an aggregate value were addressed with non-value arguments (indices, etc) we would not be able to address them without leaving the world of values.
While almost all value-semantic types should implement Equatable it is not strictly necessary to preserve referential transparency and would therefore be an excessive requirement. For example, a pure function whose context only captures values has value semantics but functions are not likely to ever conform to Equatable. When Equatable cannot be implemented behavioral equivalence is still required in order to preserve referential transparency. Generic code that relies upon both value semantics and equality can simply compose the constraints AnyValue and Equatable.
When Equatable is implemented the implementation must be reflexive (x == x), symmetric (if x == y then y == x) and transitive (if x == y && y == z then x == z).
When an aggregate value conforms to Equatable its implementation must be congruent with the results of any members that project a part of the aggregate which also conform to Equatable. This is simply another way of saying that such members must be pure.
While an object reference (regardless of its type) is not a value, an ObjectIdentifier is a value. It represents a point in an abstract space of object identifiers. While the value is an identifier the value itself has no identity. At the same time, the object it identifies clearly has an identity - If it didn't, it couldn't have an identifier! Even when a reference has type AnyObject we are required to consider concrete, dynamic details such as reference cycles and the potential to share state every time the reference is shared (down casting possibly on any object reference or existential).
It is crucial that copying or storing a value have no observable impact on the behavior of a program. This carries the implication that a value may not hold a strong reference to any object that may be referenced outside the implementation of the type. If it could, the lifetime of a shared object (and the entire subgraph it strongly references) becomes dependent upon the lifetime of the value and its copies. When the lifetime of that object ends the behavior of an arbitrary number of weak or unowned references that may exist anywhere in the program will immediately change.
This also implies that no class can truly have value semantics even when it only consists of let stored properties of value-semantic types. A program is able to form any number of weak and unowned references to instances of these classes. If we allow the language to recognize them as having value semantics we will have to reckon with the potential to change the behavior of weak and unowned references in all code that relies upon the AnyValue constraint.
It is also crucial that there be no observable impact when one value is replaced with another or a value goes out of scope. While value types in Swift do not have deinitializers they may hold references as part of their implementation and therefore may cause deinitializers to run when they are mutated or go out of scope. Any deinitializer that runs when this happens must be pure.
The design presented in this document follows the philosophies of progressive disclosure and pragmatism that are pervasive in Swift. The primary goals of the design are to:
- Formalize the semantics many Swift programmers already assume when working with value types.
- Highlight potential misuse of value types that do not have value semantics.
- Improve our ability to reason about the large subset of Swift code that lives in the world of values and pure functions by having the compiler provide static proofs of these semantics up to the use of
unsafeannotations and other low-level constructs. - Facilitate safety in the presence of concurrency.
- Allow experts to design sophisticated implementations that cannot be proven correct by the compiler.
- Do all of the above without unnecessarily permeating our code with annotations.
All syntax presented in this document is provisional and subject to bikeshedding and improvement by the community. The emphasis in this document is placed on the semantics and the way the features interact to produce a cohesive design that makes a surprisingly useful set of tradeoffs (in the opinion of the author).
The solution is to leverage the observations made at the outset and mitigate the issues discussed in the motivation by making pure the default for all declarations in a type recognized as having value semantics and further, making value semantics the default for all value types. Value types with value semantics will be required to include the impure modifier on any members that are not pure. Value types that do not have value semantics will be required to include a nonvalue modifier on their declaration. Classes will never have language-recognized value semantics for several reasons covered in the section on value semantics.
When a programmer attempts to add an impure member to a value type they will be required to decide whether 1) this was a mistake and they intend the member to be pure, 2) the type they are writing does not have value semantics, or 3) they want to add an impure member to a value semantic type. Requiring this decision will significantly increase the clarity of the semantics of our value types and their members. It also has the advantage of using annotations the way they should be: to indicate deviations from the norm.
This is a significant change but is extremely attractive. It is by far the best way to accomplish goals 1, 2 and 6 stated above. One big reason for this is that it recognizes the value semantics and purity we all know a large amount of existing Swift code has without requiring any additional syntax to be added to that code (specifically value types composed exclusively of types with value semantics whose members don't access shared mutable state globally or via arguments).
If this change is too drastic at this point in the Swift's evolution the design can be easily modified to require a value annotation on all types that wish to be recognized as having value semantics. This would be really unfortunate as it violates the principle of progressive disclosure: new Swift programmers would face the distinction between value types that have value semantics and those that don't much too soon. It would also litter our code with value annotations. Despite these downsides, it would still provide the intended benefits.
The good news is that a semantic-preserving mechanical migration is possible. Migration is discussed further in the source compatibility section of this document.
The design presented here introduces language support for pure functions in the form of the pure, impure and preserves(pure) declaration modifiers, the pure(dependsOn:) declaration clause and the unsafe(pure) statement and expression modifier.
A pure declaration must meet all of the following rules:
- The stored variable context rule: stored variables (
var) are onlypurewhen declared in a value type. - The closure rule: a
pureclosure may not capture a function that isn't alsopure. Closures may also not capture astrongreference (except indirectly as a property used in the implementation of a value-semantic type). This rule is not strictly necessary for purity but is extremely useful as it provides all pure functions with value semantics. Copying aweakorunownedreference has no observable side effects while copying astrongreference does. The context of animpurefunction is unknown and thus must be assumed to contain astrongreference. The alternatives to this rule are to not recognize value semantics for any function values or to allow thevaluemodifier to be used with function types. The former is unacceptable while the latter introduces questionable complexity. - The body rule: when a declaration includes a body:
- The impure declaration reference rule: it may only reference declarations that are known to be
pureunless theunsafe(pure)modifier appears at the beginning of the statement or expression referencing the declaration. In many cases the purity of a member of a generic or existential type will be unknown. - The weak and unowned dereference rule: it may not unwrap or dereference any
weakorunownedreferences accessed via arguments without including theunsafe(pure)modifier at the beginning of the statement that does so. The behavior of these operations could change during the execution of the body in question and is therefore inconsistent with referential transparency unless there is a guarantee that this will not happen. - The pointer rule: it may not access the contents of a pointer or buffer without including the
unsafe(pure)modifier at the beginning of the statement that does so. - The
deinitrule: it may not cause any strong reference to an object that may be unique to be dropped unless the object is known to have a puredeinitor theunsafe(pure)modifier appears where the reference is overwritten or otherwise relinquished. Any deinitializers that are invoked only because of a write to aninoutargument are exempted: the caller owns the semantic consequences of these deinitializers. The author believes that rules and semantics included in this document imply that compiler will only need to the consider deinitializer of objects created directly by the body when it does not include any use of theunsafe(pure)modifier (with the possible exception of references included in result from a helper that is a value type that does not have value semantics).
- The impure declaration reference rule: it may only reference declarations that are known to be
- The reference result rule: no reference to an object created by the function may be returned directly. Only references acquired from an argument or by calling another pure function may be returned. This rule is necessary in order to preserve referential transparency: object instances are observably unique. New instances may be returned indirectly as part of a value type so as long as the value is always the same with respect to purity regardless of the identity of the reference it contains. This rule could be relaxed if we wish to support what D calls pure factory methods. These methods would need to include an additional annotation, perhaps
pure(factory). - The
pureoverride rule: when a subclass overrides apuremember it must preserve purity. - The
impureoverride rule: when a subclass overrides animpuremember with apuremember it may not callsuperunless it includes theunsafe(pure)modifier (thesupermember is treated the same as any otherimpurecode a body wishes to access). - The subclass
deinitrule: if a class has apuredeinitializer any deinitializers defined by subclasses must also bepure. Apuredeinitializer is allowed to clean up resources (such as deallocate a buffer) but may not cause any observable side effects to happen. - The
@objcrule: an@objcmember may not bepure. - The
publicrule: oncepure, apublicmember must remainpure. Making apurememberimpureis a breaking change. - The
openrule: anopenmember may only be declaredpurewhen it is first added. Addingpurelater is a breaking change for subclasses.
It is possible to relax these rules in limited contexts where a reference is known to be unique by adding language support for copy-on-write. This would minimize the need to use unsafe(pure) by facilitating the implementation of copy-on-write value-semantic types.
An extension, function, method, property, subscript, initializer or closure may include the pure declaration modifier. When used on an extension, the modifier serves as a default for all members declared within the extension following the behavior of default access control modifiers.
In a pure extension, the impure modifier may be used to override the default. This may be useful when an impure helper is used in the implementation of an otherwise pure extension.
This rule applies to top-level functions, initializers, members of its arguments, members of stored properties if it is a method, and members of all locals and return values. In other words, it applies to all code the function may explicitly invoke.
A simple example of a pure function:
pure func addTen(_ value: Int) -> Int {
return value + 10
}A simple example of a pure extension:
pure extension UInt {
func addTen() -> UInt {
return self + 10
}
impure func times(_ body: () -> Void) {
for _ in 0..<self {
body()
}
}
}The unsafe(pure) modifier enables a pure function to have an implementation that cannot be verified by the compiler. It is intended almost exclusively for use by library authors. There are several avenues we can and should pursue to minimize the need for it even then.
An alternative would be to require the unsafe(pure) annotation on the signature of the function or member. The statement modifier is preferable for at least two reasons:
- It is an implementation detail that has no impact on the semantic contract made with callers. In some cases it may even be possible to remove it as additional features such as language support for copy-on-write are added.
- It is important that a programmer using this modifier be aware of each statement in the body that is doing something that cannot be verified as pure by the compiler.
The approach is very similar to try and await, but may be applied to statements in addition to expressions because it is possible for assignment to require its presence. Like try and await, unsafe(pure) distributes across any subexpressions.
The following example demonstrates usage (it is not intended to represent a good way to implement memoization):
var cache: [Int: Int]
pure func memoizedComputation(_ value: Int) -> Int {
pure func implementation(_ value: Int) -> Int {
/* perform complex computation here */
}
// assume some kind of synchronization around access to the cache
if let result = pure(unsafe) cache[value] {
return result
}
let result = implementation(value)
pure(unsafe) cache[value] = result
return result
}In order to avoid excessive annotation in the body, libraries implemented using lower-level constructs may choose to use an impure helper:
pure func computeResult(from value: Double) -> Double {
return unsafe(pure) fancyImplementationUsingAssembly(value)
}
func fancyImplementationUsingAssembly(_ value: Double) -> Double {
// a highly optimized algorithm that cannot be verified as pure
}Function types may include the pure modifier. We have two reasonable options for placement: pure (Int) -> Int and (Int) pure -> Int. The former is more consistent with declarations (where it must precede the declaration because it is applied to non-function declarations). The latter is consistent with the placement of throws and async.
When discussing this it is worth observing that there is a crucial difference between pure and throws or async. Purity represents the absence of an effect rather than the presence an effect. Maybe this distinction warrants the different placement that happens to coincide with the placement used by declarations.
A higher-order function may have purity that is conditional upon the purity of its function arguments. A generic function may have purity that is conditional upon the purity of the implementations of members of a type argument. The most important case for generic functions is when the provided type argument has value semantics but is not constrained as such: in that case all members are known to be pure unless the protocol requirement was specifically annotated as impure.
There is a relatively large design space available to support conditional purity in the language. The important axis is that the more precise we allow annotations to be the more often a conditionally pure function may be treated as pure by the compiler. We have to pay for an increase in purity with increasingly verbose annotations. We will have to choose a tradeoff somewhere along this axis.
Evaluating our options regarding condition purity in depth is beyond the scope of this document. With that in mind, we will consider one option for supporting conditional purity that sits somewhere in the middle of the spectrum. The syntax is a provisional and a bikeshedding exercise may improve it.
The important property of a function with conditional purity is that it preserves purity when its dependencies are pure.
We can introduce a conditionally pure function with the preserves(pure) declaration modifier:
// pure when both lhs and rhs are pure
preserves(pure) func addResults(_ value: Int, _ lhs: (Int) -> Int, _ rhs: (Int) -> Int) -> Int {
return lhs(value) + rhs(value)
}
pure func callAddResults(with value: Int) -> Int {
let lhs: pure (Int) -> Int = { $0 * 2 }
let rhs: pure (Int) -> Int = { $0 + 2 }
return addResults(value, lhs rhs)
}One important point to observe in the above example is that the argument types do not include the pure annotation. This is semantically analogous to rethrowing functions where the weakest possible type requirement (the supertype) appears in the signature.
This modifier also makes the purity of a function dependent upon the value semantics of a generic argument in addition to the purity of a function argument:
// pure when T: AnyValue
preserves(pure) func areEqual<T>(_ lhs: T, rhs: T) -> Bool {
return lhs == rhs
}In many cases the purity of a function may not depend upon all function arguments and all generic types. This may be especially true in the case of generic types with higher-order methods. These methods often do not touch the value directly, but instead allow the function argument to do something with it. In this case a pure(dependsOn:) clause can be used in the declaration:
extension Array {
preserves(pure) func last(where predicate: (Array<Element>.Iterator.Element) throws -> Bool) rethrows -> Array<Element>.Iterator.Element?
pure(dependsOn: predicate)
}In this example, without the pure(dependsOn:) clause the purity of last would have also depended upon Element: AnyValue.
One modification would be to require the pure(dependsOn:) clause in all conditionally pure functions. This would provide greater clarity at the expense of verbosity in the simple case.
Another possible modification would be to simply make conditional purity work exactly like rethrows - it would make purity conditional upon the purity of all function arguments and would ignore generics altogether. This would greatly limit the number of functions that can be considered pure and would place generics in opposition to purity. In the opinion of the author this is simply not an option.
The requirement that all members of a value-semantic type must be pure unless otherwise annotated provides a point of leverage for conditional purity where we get a lot of semantic bang for relatively little syntactic buck.
In most cases the purity of a closure will be specified by a type context. If the context requires a pure function and the closure directly accesses a global var or calls a non-pure function or otherwise violates the requirements of verified purity without using the pure(unsafe) modifier a compiler error will result. When a programmer wishes to ensure the closure is considered pure, the pure modifier may be placed prior to the argument list. This may be useful when the closure is provided as an argument to conditionally pure function.
preserves(pure) func callWithTen(_ body: (Int) -> Int) -> Int {
return body(10)
}
// ensure the compiler treats both the closure and callWithTen as `pure`
// and therefore ensuring `make100` is inferred to have type `pure (Int) -> Int`
let make100 = callWithTen { pure int in
return int * int
}
It is possible for a pure function to accept a non-pure function argument, but it may not call that argument, even with the pure(unsafe) modifier is included with the calling expression. This is because there is no way for a function to preserve purity when it calls an arbitrary non-pure function.
pure func makeFunctionPair(_ first: () -> Void, _ second: () -> Void) -> (() -> Void, () -> Void) {
return (first, second)
}
// compiler error, cannot call non-pure function argument in a pure function
pure func (_ body: () -> Void) {
// pure(unsafe) cannot be used to call a non-pure argument
pure(unsafe) body()
}A protocol may include the pure declaration modifier in the declaration of any requirement (except for associatedtype requirements. All conforming types must provide a pure implementation of that requirement. A refining protocol may introduce a pure requirement where none existed in the base protocol. Here is a simple example:
protocol Foo {
func doSomething()
}
protocol Bar: Foo {
pure func doSomething()
}Note: no classes will be able to conform to a protocol with a pure property or subscript setter requirement. For this reason we may wish to require protocols containing these requirements to refine AnyValue (which is introduced shortly).
In some cases it may be desirable to be able to constrain a generic type with a requirement that some members be pure even when a constraining protocol does not require that. This could easily become unwieldy pretty quickly. The author recommends we do not include a mechanism as elaborate as this when pure functions are first introduced. If experience provides concrete examples of how such a feature is necessary we can consider an enhancement in the future.
Fortunately, in many cases the AnyValue constraint introduced below will be appropriate and will provide a guarantee of purity for all members (modulo impure protocol requirements).
The design presented by this document introduces language support for value semantics in the form of the nonvalue and preserves(value) declaration modifiers, the value(dependsOn:) declaration clause, the unsafe(value) stored property declaration modifier and the AnyValue protocol to which all value-semantic types automatically conform (and to which no other types may conform).
All value types must either meet the requirements of value semantics or include either the preserves(value) or nonvalue value type declaration modifier. Value semantics will be inferred for tuples where all constituent types have value semantics.
A value-semantic type must meet all of the following rules:
- The stored value rule: all stored property or case-with-associated-value declarations must have value-semantic types or include the
unsafe(value)modifier. When theunsafe(value)modifier is used the member may not be visible outside the implementation. If a type references a generic type argument it will value semantics when it is constrained toAnyValueor if declaring type includes thepreserves(value)modifier making its semantics conditional upon the provided type argument. - The
impuremember rule: all members must be eitherpure, preserve purity or include theimpuredeclaration modifier.
These rules follow the philosophy of progressive disclosure. A programmer does not need to be aware of value semantics until it becomes semantically necessary. Their value types will often be usable with APIs that require value semantics. When their types are rejected not usable with such an API it is for a very good reason: they were probably trying to do something that would lead to a bug. At that point the programmer should be motivated to learn more about value semantics and think carefully about what they were doing.
The stored value rule requires the programmer to acknowledge when a value type is not a simple aggregate of value-semantic types. In this case the programmer must take responsibility for ensuring the implementation has value semantics. Requiring this annotation alongside each storage-containing declaration that does not have value semantics ensures the programmer understands exactly what state they are responsible for handling carefully.
These members cannot be part of the API contract the type makes with users. If they were the type would not have proper value semantics. Currently, this means these declarations cannot be public. If a feature is added to Swift supporting intra-module structure (such as submodules) it may be possible to further tighten this rule to better support submodule libraries within a single app.
The requirement that unsafe(value) declarations cannot be public currently precludes a value-semantic enum from containing an associated value that does not have value semantics. If non-public enum cases are added to the language these cases could have associated values that do not have value semantics with the author of the type taking on the semantic responsibility of value semantics.
The impure member rule is necessary in order to ensure the members of a value-semantic type provide referential transparency by default. Impure members should be relatively rare exceptions that the author of the type considers carefully. When they are necessary they should be clearly identified to alert users to the unusual behavior using an impure annotation. This will make the impure nature of the operation clear to both the author and the user of the code.
With this rule, pure can become the default for value-semantic types and the compiler will produce an error when an impure member does not include the impure annotation. This is the right default for a referentially transparent type.
In a pure functional language all arguments and results have value semantics. Value types that do not include the nonvalue modifier and their members that do not include the impure modifier will be very close to a strict (as in not lazy) pure functional subset of Swift. It may be desirable to include a third rule that establishes this subset and further increases the semantic clarity of value types for both authors and users:
The nonvalue member rule: all members which have a concrete or type-bound argument or return type that does not have value semantics must include the nonvalue (or impure) declaration modifier. Generics types introduced by the member itself are not required to have value semantics because the caller (not the declaring type) controls the type that will be bound.
A good example of the exception for generics is map - it should not be necessary to constrain the transform's result toAnyValue or declare map with nonvalue.
If we do include this rule we will probably need to allow an exception for thrown errors (which are otherwise treated identically to any return value throughout this document). On the other hand, it may be possible to avoid this exception if typed errors are added by making the default error type for pure throwing functions Error & AnyValue.
Many generic types have conditional value semantics. This document refers to these as value-preserving types. Array and Optional are good examples. They meet the requirements of value semantics when the contained type meets the definition but they do not when it does not.
When a generic value type has conditional value semantics the preserves(value) modifier is used in its declaration:
preserves(value) struct Array<Element> {
// implementation
}By default the semantics of a value-preserving type are conditional on all type arguments. In some cases this will be excessive:
preserves(value) struct ID<UnderlyingValue, IdentifierSpace> value(dependsOn: UnderlyingValue) {
var value: UnderlyingValue
}This only is a pseudo-realistic example. In real code UnderlyingValue would probably be constrained to AnyValue or perhaps something more specific.
As with unconditional value semantics their members must have pure semantics when all unconstrained types underlying their essential operations are values. However, members of these types are not required to be pure when the type argument their semantics depends on does not have value semantics.
Conditional purity has already been discussed. It would be excessive to require the preserves(pure) annotation on all members of a conditionally value-semantic type. Instead, members of a conditionally value-semantic type will by default have purity that is conditional on the semantics of the type. When the type has value semantics its members must be pure or include the impure annotation. When the type itself does not have value semantics its members will have unspecified purity by default.
In either case an explicit purity modifier may be provided for any member. This will allow any member to be unconditionally pure or to have purity that is conditional on generic or higher-order arguments of the member itself. For example, Array.map has purity that is conditional upon the transform, not the semantics of Element.
Even when the type argument does not have value semantics a value-preserving type will exhibit some important behavior in common with proper value semantics: copies are independent up to the boundary of the container and deinitialization of the container itself will not result in observable side effects (any observable side-effects will be due to deinitialization of the contents).
We will want to be able to leverage these weaker guarantees in generic code that does not require full value semantics. Some types meeting these weaker requirements will not be value-preserving generic types. UnsafePointer is a good example. Perhaps the weaker guarantees could become semantic requirements of a marker protocol to which value-semantic and value-preserving types implicitly conform. The design of such a feature is beyond the scope of this document.
Value semantics and purity are very strong API contracts. We may wish to require public value types to be explicitly annotated to specify value or nonvalue semantics. If we do this we may also want to require public members of value-semantic types to be explicitly annotated with pure or impure semantics. We generally require all semantic contracts to be explicitly declared by an API author and this policy would follow that convention.
On the other hand, it is extremely unlikely that a library author would implement a type that happens to have value semantics and exclusively pure members while not intending to support value semantics. A type not intended to have value semantics will usually include stored values that do not have value semantics and / or impure members. They will already be prompted by the language to consider the semantics of the type they are writing. Maybe this is good enough. The alternative is unfortunate: it would require a lot of annotations on public types that have value semantics.
Under the design presented in this document all pure function types have value semantics. Non-pure function types will not have value semantics.
Key paths in their current form will not have value semantics. This is because they are implemented as classes and also because they could capture a subscript that does not have value semantics. It is highly desirable to support pure key paths that have value semantics. Such key paths would not have non-value captures and would guarantee purity when accessed. The design of such an enhancement is beyond the scope of this document.
Do metatypes have value semantics? This is an interesting question, especially when we consider metatypes of reference types. This largely depends on whether we consider static members to be essential to the metatype value or we consider them globals that are simply namespaced via the metatype, but inessential to the metatype value. There certainly are interesting use cases where they are treated as values. For example, if they were Hashable they could be used as dictionary keys. The author is interested in hearing what the community has to say about this topic.
When a user writes generic or existential code that composes the AnyValue constraint with other constraints it is extremely desirable for that code to be able to reason about behavior in the same way we would with a concrete value-semantic type, specifically that its members are pure. For this reason, an impure member of a value-semantic type should not be allowed to meet a protocol requirement with unspecified purity. It may only meet a requirement explicitly annotated as impure. This allows the AnyValue constraint to compose with other constraints in a way we can easily reason about: all members are known to be pure unless otherwise annotated.
Here is an example:
protocol Animal {
var isHungry: Bool { get }
mutating func run()
mutating func eat()
}
extension Animal {
func runUntilHungry() {
while !isHungry {
run()
}
}
}
pure func makeAnimalThis is not allowed:
protocol Loggable {
func log()
}
struct Value: Loggable {
var value: Int
// error: impure member `log` of value-semantic type `Value` cannot fulfill protocol requirement with unspecified purity
impure func log() {
print("value: \(value)")
}
}On the other hand, if the protocol was declared like this there would be no error:
protocol Loggable {
impure func log()
}All members provided in an extension of a protocol that refines AnyValue (directly or indirectly) must be pure unless they include the impure modifier. Further, members provided in any protocol extension which introduces such a constraint are also required to be pure unless they include the impure modifier. This extends the impure member rule and the pure default to protocol extensions which only apply to value-semantic types.
protocol Foo: AnyValue {
func foo() -> String
}
extension Foo {
// This default implementation must be `pure` but does not require a modifier because `Foo` refines `AnyValue`
func foo() -> String {
return "foo"
}
// This extension method must also be `pure` but does not require a modifier because `Foo` refines `AnyValue`
func bar() -> String {
return "bar"
}
}
protocol Bar {}
extension Bar where Self: AnyValue {
// This extension method must be `pure` but does not require a modifier because the extension constrains `Self` to `AnyValue`
func bar() -> String {
return "bar"
}
}If the design in this document is implemented protocols will be able to specify value or reference semantics (assuming class-constrained protocols imply reference semantics). In that future it is quite likely that most protocols specify either value or reference semantics.
Extensions of class-constrained protocols will of course continue to have members with unspecified purity by default. This section discusses the purity of members declared in extensions to the remaining protocols which do not require either semantic.
Many members of these extensions will have pure behavior when the conforming type has value semantics. This is because the members contained in a protocol extension are usually implemented strictly in terms of requirements of the protocol and value-semantic types must provide a pure implementation of all protocol requirements unless the protocol requirement was explicitly specified impure.
There are several options for recognizing this conditional purity:
- We could have the compiler infer purity of these members when it is not specified and they are used on a value-semantic type.
- We could make the default be unspecified purity, requiring an annotation for all such members where conditional purity is desired.
- We could make them have a default of purity conditional upon the semantics of the conforming type.
Inference may be difficult to implement and would provide a less clear programmer model. Requiring explicit annotations would produce a lot of boilerplate and likely result in the annotations often being omitted (and therefore leaving members with unrecognized purity).
This leaves the last option. This option coincides nicely with the requirement that value-semantic types must provide pure implementations of protocol requirements unless the requirement itself was declared impure. As long as members in these extensions do not directly have impure behavior they would not require annotation. If a member does directly have impure behavior and is available on a value-semantic type it is congruent with the design presented by this document to require annotation.
We could use a marker protocol or a protocol with a copy requirement to indicate value semantics. The author believes this is not the right design for two primary reasons. First, the design in this document includes compiler verification beyond simply checking the presence of members fulfilling protocol requirements. If a protocol were used it would be a "magic" protocol assigned special meaning by the compiler. Second, the author believes that value semantics is an contract with such importance that it should be established by the initial declaration of the type. This is essential if we want value-semantic types to have pure members by default.
This design has the obvious consequence of preventing retroactive specification of value semantics, even if the implementation of the type is known to have value value semantics. Users who require value semantics will need to either convince the author of the type to remove the nonvalue modifier if it is a value type or wrap the type if it is a reference type. This is intentional. Only the author can commit to continue providing a value-semantic implementation in the future. It will also encourage library authors to swiftly (pun intended) update their code to reflect the intended semantics.
The next section covers some features that can help to mitigate the pain of writing wrappers.
The features discussed in this section are not essential to the design presented in this document and would likely not be added immediately. It stands on its own and significantly strengthens the semantics of a lot of Swift code. However, in time they can complete and strengthen the design. They can complete the design by supporting the use cases that might otherwise be more convenient or only possible with value-semantic reference types. They can strengthen the design by addressing a large number of use cases for the unsafe modifiers and therefore reducing the need to use them.
The use cases for value-semantic reference types are: heap allocation, polymorphic implementation, polymorphic interface (i.e. subtyping), implementation sharing and retroactive value semantics of third party reference types. As was just discussed, retroactive conformance to the value semantic contract is in the opinion of the author not a good idea for any type regardless of whether or not it is a reference type. This is not something we should support. The other use cases are all addressed by features discussed in this section.
Copying large value types can be expensive. Heap allocation can be used to avoid this cost. Without indirect structs we are forced to use classes to accomplish heap allocation. We should be able to include the indirect modifier in the declaration of a struct whose values we always want stored on the heap. We should also be able to include the indirect modifier on the declaration of any property whose type is a value type. The language would manage copy-on-write of these heap allocated values.
Indirect structs have a significant advantage over immutable classes: they fully support Swift's mutability model for value types.
Here is an example of how indirect would be used:
struct Song {
var name: String
var artistName: String
var albumName: String
var length: TimeInterval
}
indirect struct Person {
var firstName: String
var lastName: String
indirect favoriteSong: Song
// many other properties
}We should also allow the optimizer to automatically place instances of value types on the heap if we are confident that the optimizations will have a significant positive impact. Explicit indirect annotations could provide useful hints to the optimizer when optimizing other types. For example, it might be possible to store both people values in a Pair<Person> in the same heap allocation. If we do this we will also need to include a direct modifier to allow the programmer to take manual control when necessary.
We can reduce the number of cases where unsafe(pure) and unsafe(value) will be necessary in the implementation of value-semantic types by adding language support for copy-on-write. There has been some prior work in this area, although no official proposals have been drafted and the topic has not seen much discussion on the evolution mailing list.
The author is not an expert in this area. The sketch that follows is not intended to reflect a realistic design, only to present general ideas about what might be possible.
struct CustomCollection<Element> {
// `cow` is a new kind of stored property decalaration
// It may only be used for non-public properties.
// It may only be used with types that provide copy-on-write hooks (maybe via a protocol).
// It provides read-only access throughout the implementation of the declaring type.
// Write access is only available in `cow` blocks inside `mutating` methods.
private cow buffer: CowBuffer<Element>
mutating func append(_ element: Element) {
// A `cow` block specifies one (or more?) `cow` properties.
// When the type of the `cow` property is a variable sized buffer
// the minimum capacity the buffer should contain
// after the method completes may also be specified.
cow(buffer, minimumCapacity: buffer.count + 1) {
// Inside the `cow` block a new name binding `uniqueBuffer` may be mutated.
// The contents of `buffer` have already been copied and initialized.
// This does not require `unsafe(pure)` because the buffer is unique and
// simply represents part of the result value of `inout self`.
uniqueBuffer.append(element)
}
}
}In this example the compiler would check uniqueness of the buffer when the cow block executes. If the buffer is not unique or does not have the correct capacity it is copied prior to the body of the block being executed.
In some cases it may be more efficient for the implementation to have more control over the process of transferring elements from the old buffer to the new buffer.
extension CustomCollection {
mutating func shuffle() {
cowUninitialized(buffer) {
inPlace {
// `buffer` is already unique and can be mutated in this block.
// The shuffle will be done in place.
}
transfer {
// When this block runs a new `uniqueBuffer`
// has been allocated with the the necessary capacity
// but has not been initialized.
// Read only access to the original `buffer` is available.
// In this example, the new elements will be initialized
// in the correct position, avoiding unnecessary initialization
// of elements in their original position and subsequent
// rearrangement of the new buffer.
}
}
}
}It may also be useful to allow a maximum capacity to be specified for the buffer to avoid retaining large buffers when they are no longer necessary (because many elements have been removed).
Finally, there may be some cases where a type includes more than one cow property and needs to perform mutating operations on them simultaneously. This could be supported either by allowing nesting of cow and cowUninitialized blocks or by allowing multiple cow properties to be specified in a single cow block.
If we add language support for copy-on-write along these lines it may also provide the necessary information for the compiler to synthesize the non-mutating variation of the method which returns a new value without leaving performance on the table. In the non-mutating variation the uniqueness check could be skipped with the transfer code path always being used.
There are several other advantages to having the language recognize mutating and non-mutating method pairs. This topic has been discussed in the past and may be worth revisiting.
Existentials can already be used to write code that is dynamically polymorphic over value types that conform to a protocol. The design presented in this document introduces the AnyValue protocol which can be composed with other protocols to create value-semantic existentials.
There are some use cases for dynamic polymorphism that are not possible using existentials in their current form. For example, polymorphism using a generic base class has an analogue in an existential formed using a protocol with a bound associated type. Austin Zheng drafted a comprehensive proposal to enhance existentials to include this capability (as well as many others).
Adopting the features described in his proposal would address most of the use cases for dynamic polymorphism over value-semantic value types. One use case they would not address is combining existentials with generics. With an immutable class hierarchy, an instance with a type of a generic base class can be provided to generic code which is constrained to the generic base class (with bound type arguments).
Existentials do not currently conform to their protocol so an existential with a bound associated type would be rejected by a generic constraint using the same protocol and same associated type binding. Loosening this restriction is possible in some, but not all, cases. Detailed discussion of this topic is beyond the scope of this document.
Automatic forwarding can address two use cases that might otherwise be covered by immutable, value-semantic reference types: polymorphic implementation and implementation sharing.
Polymorphic implementation (such as class clusters) would be accomplished by forwarding to a value-semantic existential. Implementation sharing would simply be accomplished by using composition along with forwarding. It is worth noting that this form of implementation sharing would allow forwarding to more than one member. In both cases, automatic forwarding would eliminate the boilerplate required by the language today when forwarding is necessary.
The author has previously worked on a draft proposal for introducing an automatic forwarding. This draft is outdated and would not be brought forward as-is (a second draft with some design important changes was partly finished). Nevertheless, it still provides an example of the kind of mechanism we could introduce to automate forwarding. The embedding feature in Go provides an example of automatic forwarding in a popular language.
There are a number of possible features in the space of value subtyping that might also enhance the usability of value-semantic value types. These features are largely orthogonal to the present discussion but are referenced for the sake of completeness.
As with the introduction of any new keywords there is some potential for conflicts with existing code. This may influence the final choice of syntax.
Swift does not currently acknowledge any types as having value semantics or any functions as being pure. Obviously, because of this no Swift code currently relies on these constraints. The design presented here is semantically backwards compatible. The conservative migration is straightforward: simply add the nonvalue annotation to all value types.
The conservative approach leaves a lot to be desired. The most beautiful aspect of the design presented in this document is the way it assigns purity and value semantics to a lot of existing Swift code with no syntax changes. If we are going to the work of adding language support for purity and value semantics we want as much code to be formally recognized as possible. The migrator should not modify code which will compile under this design without annotation.
Additionally, there will be many cases where code will be recognized as pure as soon as its dependencies have been fully migrated, but not until then. We cannot control how soon dependencies will migrate and we do not want to penalize users who migrate early with a less pure migration. We should provide a post-migration way to have nonvalue annotations removed after dependencies have been migrated. It should be possible to run this post-migration process at any time allowing for adoption of formal purity and value semantics incrementally as each dependency is migrated. This post-migration step could take the form of a "remove nonvalue type modifier" refactoring.
A (very) naive migration algorithm might looks something like this:
- Start with a program that compiles without error
- Import a fully annotated standard library and Foundation
- Attempt to compile the code as-is
- When a compiler error indicating a violation of purity or value semantics is encountered add a
nonvalueannotation on the value type containing the declaration that produced the error. - Recompile all previously compiled declarations that depend upon the type that was annotated in step 3
- Continue until all code in the program compiles without error
A variation on this algorithm could allow a programmer to intervene in step 4 and decide whether to place annotations on or in the member or to place the nonvalue annotation on the type itself as in the fully automated algorithm. This is probably unnecessary as it would not be difficult to search for nonvalue following the migration, remove the annotation for types intended to have value semantics, and then resolve the compiler errors.
One interesting thing to observe is that this is a migration that may uncover bugs or help programmers understand the semantics of values and references better when nonvalue annotations are required that they do not expect. When this happens it may produce short-term frustration but long-term gratitude.