Chapter 9. Nondeterminism by need
This chapter is the most abstract part of this book, and it is not required for initial understanding of the later chapters. You are welcome to skip ahead to chapter 10, as long as you promise to come back here at a later time.
In chapter 3, we introduced functional programming as one of the tools of the Reactive trade. The second part of this book has up to this point been concerned with splitting a problem into encapsulated modules that interact only via asynchronous message passing, an act that is fundamentally impure: sending a message to an external object implies that the state change of that other object cannot be modeled within the sender. It is necessarily a side effect. That is not incidental; it is the sole reason to compartmentalize.[1]
Tracking the sending of a message as an effect can of course be done, but the gain is small. It would have to be done in close proximity to the place it originates, and the modules in our hierarchical decomposition are intended to be small.
It seems at first sight that the design we have chosen is fundamentally at odds with one of the core paradigms that we advertise. But this contradiction is not real, as you will see now, during a journey that could be titled “The Gradual Expulsion from Paradise.”
9.1. Logic programming and declarative data flow
Ideally, we would want to specify input data and the characteristics of the solution, and the programming language would do the rest for us. An example is to specify that, given a list of values, we demand in return a list that contains the same elements, but in ascending order; for this, we would say that the nth element should always be greater than the (n-1)th element. The interpreter for our program would then figure out a sorting algorithm and apply it to any input we supplied to the resulting program—but it would first tell us that the input list could not contain duplicate elements. Having such a programming language would free us from the concerns of how the inputs were combined and processed; the computer would automatically figure out the correct algorithm and perform it. This process would be fully deterministic as far as the formulated desired characteristics were concerned.
Research in this direction led to the discipline of logic programming and the creation of programming languages like Prolog and Datalog in the 1980s. Although not quite as advanced as the aforementioned ideal—which does sound too good to be true in the sense of “do what I mean”—these languages allow us to state the rules of a domain and ask the compiler to prove additional theorems that then correspond to the solution for a given problem. Logic programming so far has not had significant influence on mainstream software development, foremost due to its disadvantages with respect to runtime performance in comparison with imperative languages that are much farther removed from paradise.
A step toward the mainstream takes us to pure functional programming, expressing programs and algorithms with functions and immutable values, where a function is an example of such a value. This way of programming is close to mathematics in that functions describe transformations that can be composed with other functions without having to specify the input values up front—a program can first calculate which sequence of functions to apply and then feed the inputs to them. Compared with logic programming, we trade decent runtime performance for the duty of figuring out the correct algorithms ourselves. Instead of generating the algorithm for us, the compiler can at best verify that the algorithm we provided has the desired properties. This verification requires the use of a type system that is powerful enough to encode the characteristics we want. In this camp, we find a large number of languages to choose from, including Haskell, Coq, Agda, and, recently, Idris. Many of the code samples in this book are written in the Scala language, which can express pure functional programs but incorporates support for mutability and object orientation as well.
Programming in a pure functional style means the evaluation of every expression always yields the same result when given the same inputs. There are no side effects. This enables the compiler to schedule evaluation on an as-needed basis instead of doing it strictly in the order given in the source code, including the possibility of parallel execution. The necessary precondition for this is that all values are immutable—nothing can change after it has been created. This has the very beneficial consequence that values can be freely shared among concurrently executing threads without any need for synchronization.
A close cousin of the functional paradigm is dataflow programming. The difference is that the former focuses on functions and their composition, whereas the latter concentrates on the movement of data through a network (more precisely, a directed acyclic graph) of connected computations. Every node of this network is a single-assignment variable that is calculated once all inputs of its defining expressions have been determined. Therefore, the result of injecting data into the processing network is always fully deterministic, even though all computations within it conceptually run in parallel. Dataflow programming is, for example, part of the Oz language,[2] but it can also be embedded in a language like Scala using composable Futures, as shown in chapter 3.
See http://mozart.github.io/mozart-v1/doc-1.4.0/tutorial/node8.html for more details on dataflow concurrency.
9.2. Functional reactive programming
A hybrid between the application of (pure) functions and the description of a processing network is functional reactive programming (FRP), which focuses on the propagation and transformation of change: for example, from measurements that arrive from a sensor to a GUI element on the human operator’s screen. In its pure form, FRP is close to dataflow programming in that it determines the changes to all input signals of a given transformation before evaluating it. This restricts implementations to run effectively single-threaded in order to avoid the problem of glitches, which refers to the phenomenon that the output of an element fluctuates during the propagation of an update throughout the network.
Recently, the term FRP has also been used for implementations that are not glitch-free, such as Rx.NET, RxJava, and various JavaScript frameworks like React, Knockout, Backbone, and so on. These concentrate on the efficient propagation of events and convenient wiring of the processing network, compromising on mathematical purity. As an example, consider the following functions:
f(x) = x + 1 g(x) = x - 1 h(x) = f(x) - g(x)
In mathematical terms, h(x) would always be exactly 2, because we can substitute the definitions of the other two functions into its body and witness that the only variable input cancels out. Written in the aforementioned frameworks, the result would be 2 most of the time, but the values 1 and 3 would also be emitted from time to time (unless you took care to manually synchronize the two update streams for f and g).
This deviation from fully deterministic behavior is not random coincidence, and it is also not due to defects in these frameworks. It is a consequence of allowing the concurrent execution of effectful code, meaning code that manipulates the state of the universe surrounding the program. Both aspects—concurrency and effects—are essential to achieve good performance on today’s hardware, making nondeterminism a necessary evil. Another angle on this is presented in languages like Bloom[3] that employ the CALM[4] correspondence to identify those parts of a program that require explicit coordination, expressing the rest as so-called disorderly programming.
See www.bloom-lang.net/features for an overview.
Consistency and logical monotonicity. For a formal treatment, see Ameloot et al., “Relational Transducers for Declarative Networking,” Journal of the ACM 60, no. 2 (2010), http://arxiv.org/pdf/1012.2858v1.pdf.
Glitch-free applications can be written using frameworks that are not glitch-free. The only problematic operations are those that merge streams of updates that come from a common source and should therefore show a certain correlation. Processing networks that do not contain such operations will not suffer from nondeterminism.
9.3. Sharing nothing simplifies concurrency
When concurrency as well as stateful behavior are required, there is no escape from nondeterminism. This is obvious when considering the distributed execution of components that communicate via asynchronous message passing: the order in which messages from Alice and Bob reach Charlie is undefined unless Alice and Bob expend considerable effort to synchronize their communication.[5] The answer to Bob’s question, “Have you heard from Alice yet?” would thus vary unpredictably among different executions of this scenario.
For example, Alice could wait until Bob has heard back from Charlie—and told her so—before sending her message.
In the same way that distribution entails concurrency, the opposite is also true. Concurrency means two threads of execution can make progress at the same time, independent of each other. In a non-ideal world, this means both threads can also fail independently, making them distributed by definition.
Therefore, whenever a system comprises concurrent or distributed components, there will be nondeterminism in the interaction between these components. Nondeterminism has a significant cost in terms of the ability to reason about the behavior of the program, and consequently we spend considerable effort on ensuring that all possible outcomes have been accounted for. In order to keep this overhead limited to what is required, we want to bound the nondeterminism we allow in a program to that which is caused by the distributed nature of its components, meaning that we only consider the unpredictability in the messaging sequence between encapsulated modules and forbid any direct coupling between them.
In this sense, the term shared-nothing concurrency means the internal mutable state of each module is safely stowed away inside it and not shared directly with other modules. An example of what is forbidden is sending a reference to a mutable object (for example, a Java array) from one module to another while also keeping a reference. If both modules subsequently modify the object from within their transaction boundary, their logic will be confused by the additional coupling that has nothing to do with message passing.
The strategies to deal with nondeterminism can be classified into two groups:
- We can reject those orderings of events that are problematic, introducing explicit synchronization to reduce the effect of nondeterminism to a level at which it no longer changes the program’s characteristics.
- Alternatively, we can restrict the program to use of operations that are commutative, which means the order in which they
are executed has no influence on the final result of the distributed computation.[6]These are called conflict-free replicated data types (CRDT). See Shapiro et al., INRIA (2011), http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.231.4257&rep=rep1&type=pdf.
The former involves a runtime cost for coordination, whereas the latter involves a development cost for restricting the exchanged dataset to be expressible efficiently in a conflict-free representation.
9.4. Shared-state concurrency
The final step of the journey away from paradise brings us into the world of threads and locks and atomic CPU instructions, and it can be argued whether this corresponds to the necessary evil (that is, the here and now) or places us directly in Hell. The background for this scenario is that current computers are based on the Von Neumann architecture, with the extension that multiple independent execution units share the same memory. The way data are transferred between CPU cores is therefore by reading to and writing from this shared memory instead of sending messages directly, with the consequence that all cores need to carefully coordinate their accesses.
Programming with threads and synchronization primitives maps directly to this architecture,[7] and it is your duty to embed the correct level of coordination in your program because the CPU would otherwise operate in its fastest possible and most reckless mode. The resulting code contains a tightly interwoven web of business logic and low-level synchronization, because memory accesses are so ubiquitous.
We are glossing over the fact that threads are an illusion provided by the operating system to allow more concurrent executions than the number of available CPU cores.
The problem with this code is that synchronization protocols do not compose well: if Alice knows how to conduct a conversation with Bob without getting confused, and Bob knows how to converse with Charlie, that does not mean the same way of talking with each other will allow a shared group conversation among all three of them. We also know from social experience that getting a larger group of people to agree on something is disproportionately more difficult than achieving agreement between just two persons.
9.5. So, what should we do?
Along the journey from paradise toward the netherworld, we have gradually lost the ability to predict the behavior of our programs. Toward the end, it became nearly impossible to validate a design by reasoning about the way it is built up from simpler parts because the interplay between the building blocks entangles their internal behavior. This leads to the necessity of performing extensive testing and hopefully exhaustive verification scenarios for programs that are constructed directly upon threads and locks.
Threads and low-level synchronization primitives are important tools for situations where performance requirements or the nature of the problem (such as writing a low-level device driver) force us to exercise precise control over how the CPU instructions are carried out. This situation is one that most programmers will rarely find themselves in. We can in almost all cases rely on someone else to have solved that level of the problem for us. An example is the implementation of an Actor framework that uses low-level features to provide users with a higher level of abstraction.
Retracing our steps, we see that going from shared-state concurrency to shared-nothing concurrency eliminates an entire class of problems from the application domain. We no longer need to concern ourselves with the way CPUs synchronize their actions, because we write encapsulated components that only send immutable messages that can be shared without issues. Freed from this concern, we can concentrate on the essence of distributed programming for solving our business problems, and this is where we want to be in case distribution is necessary.
The next step backward removes the need for concurrency and distribution, enabling the resulting program to shed all nondeterminism and greatly enhance the power of reasoning about the composition of a larger application from simple pieces. This is desirable because it eliminates yet another class of defects from the application domain. We no longer need to worry about having to manually ensure that things run in the correct sequence. With FRP or dataflow, we reason only about how data are transformed, not how the machine executes this transformation. Pure functional programming allows us to compose the application of calculations much in the same way we would write them down mathematically—time no longer plays a role.[8]
Roland’s favorite analogy is cooking: “I know in principle how to cook all parts of a meal, and in practice I can also do it one part at a time (for example, concentrating on the meat until it is finished), but as soon as I try to do several things at once, I start making mistakes. It would be nice if time could be eliminated from this process, because that would allow me to do one thing after the other without the hassle of switching my focus repeatedly. This is much like the difference between explicit concurrency and declarative programming.”
Absent an efficient and proven implementation of logic programming, this last step brought us to the place we want to be: a fully deterministic, reasonable programming model. The tools to program in this way are widely available, so we should use them wherever we can.
The dividing line between concurrent nondeterminism and reasonable determinism is established by the need for distribution. A distributed system can never be fully deterministic because of the possibility of partial failure. Employing a distributed solution must always be weighed against the associated cost; and apart from the distributed parts of a program, we should always strive to stay as close to functional and declarative programming with immutable values as is feasible.
In chapters 4–8, we have detailed the reasons why and when distribution is necessary and useful; the desire to stay nondistributed as long as possible does not change this reasoning. The contribution of this chapter is to present a weight on the opposite side of resilience, scalability, and responsibility segregation. You will have to place both on the scales and balance them well for each design you develop. For further reading on this topic, we recommend the literature detailing the design of the Oz language, in particular Peter van Roy’s paper “Convergence in Language Design.”[9]
Peter van Roy, “Convergence in Language Design: A Case of Lightning Striking Four Times in the Same Place,” Proceedings of the 8th International Conference on Functional and Logic Programming (2006): 2–12, https://mozart.github.io/publications.
9.6. Summary
This chapter has taken you all the way from pure, deterministic programming approaches via shared-nothing concurrency to threads and locks. You have seen that all these tools have a place in your tool belt and that you should be careful to stay as close to the initially mentioned paradigms as you can. Only employ nondeterministic mechanisms where needed, whether for scalability or resilience. In the next chapter, we will complete part 2 of this book by coming back to where we set out from in chapter 1: considering how messages flow through applications.