Note: This is a heavily revised version of an earlier post The Cone compiler performs a data flow analysis pass after name resolution and type checking. Given that this sort of analysis is rarely covered by compiler literature, I thought it might be useful to jot down some thoughts about its purpose and intriguing mechanics. Trigger Warning: This blog post is highly technical and brief. It reads more like an organizing outline for a design spec than a typical essay-oriented post.
In 2001, Trevor Jim (AT&T Research) and Greg Morrisett (Cornell) launched a joint project to develop a safe dialect of the C programming language, an outgrowth of earlier work on Typed Assembly Language. After five years of hard work and some published papers, the team (including Dan Grossman, Michael Hicks, Nik Swamy, and others) released Cyclone 1.0. And then the developers moved on to other things. Few have heard of Cyclone and almost no one has used it.
Inheritance makes it easier than any other mechanism (e.g. generics, macros, composition/delegation) to define a type that reuses the state and some methods of other types. After reading my inheritance posts, I hope you are convinced that simplifying inheritance to a namespace-based mechanism ensures we obtain this convenient reuse capability, while avoiding most of the complexity and coupling dangers of traditional inheritance. However, you might still wonder whether real-world code needs inheritance’s reuse capability.
After removing the interface, inversion of control, and protected access capabilities from traditional inheritance, what do we have left (besides composition)? This is what we have: placing a few extra tokens on a derived class causes all named fields and methods of one or more base classes to be absorbed as if explicitly incorporated. Further, certain inherited methods can be customized (overridden) with their own implementation. The primary selling point for inheritance has always been this sort of code reuse.
The execution of a program unfolds over some interval of time. The lifetime of every temporary resource (e.g., variable or object) is the time span between that resource’s “creation” and “destruction”. This lifetime is wholly contained within the typically-longer lifetime of the program. The goal of this post is to explore how versatile lifetime analysis has increasingly become in managing memory efficiently, safely and with better performance. By the end of this post, we will explore exciting new ways to apply lifetime analysis, beyond their current support in Rust.
To complete our three-part series on permissions, which began with Race-Safe Strategies, let’s talk about the transitional nature of reference permissions. When are permissions transitional? When we can safely create a copy of a reference which has a different permission than the reference it copied from. There are several ways in which this can happen, which this diagram summarizes (and the following sections explain): The following sections describe the nature of several one-way transitions that flow downward in the diagram.
In my last post, Race-safe Strategies, one footnote stated “safety issues which look suspiciously similar to race conditions can crop up when a language supports the creation of “interior references” to shared, mutable values of certain types”. Let’s explore that now. I will begin by recapitulating Manish Goregaokar’s excellent post “The Problem With Single-Threaded Shared Mutable”. His post clearly explains why the Rust language wishes to steer developers towards RefCell for shared references over use of Cell, its inflexible shared, mutable counterpart.
I recently made the observation that many people seem unaware of the full collection of constraint mechanisms available for protecting race safety. Someone sensibly asked for a link to an article that provides a modern, comprehensive review. It turns out that the pickings are very slim; the best I could find is this Wikipedia article on thread safety. It’s accurate, but incomplete. To close that gap, let me take a stab here at more comprehensive treatment.
Is it possible to improve on Rust’s single-owner strategy to support more complex data structures? Before digging into this challenge, let’s summarize the story so far… The Promise and Limitations of Single-Owner Rust’s single-owner memory management is a form of automatic memory management; a garbage collection strategy that is distinct from tracing and reference-counting. Fundamentally, it is an improvement on RAII, which automatically finalizes some defined resource at the end of its defined lexical scope.
Most programming languages support only copy semantics. A value passed to a function or stored in a variable is a copy of the original value. We know it is a copy, because any change we make to the copy has no impact on the original value. A few languages, like C++ and Rust, also support move semantics. Unlike a copy, a transfer moves the original value to its new home; that value is no longer accessible at its previous home.