Most languages, C++ included, use lexical scope1. This means that the scope of a variable access is determined at compile time by the environments2 inside which it is defined. When we access a variable named a in a member function, the compiler searches the enclosing blocks, the enclosing function, the enclosing class, its superclasses, thread local storage, and global storage. Since the variable to access is determined entirely by compile-time knowledge, this is also known as static scope.
You, my reader, intelligent creature that you are, may be saying to yourself, “The headline says ‘dynamic scope’. I guess that’s the opposite of the static scope I’m used to from C++… I wonder what that’s like.”
I’m so very glad you asked.
Dynamic scope, as the name suggests, is resolved not at compile time, but at run time. When we access a variable named a, instead of moving upward through a hierarchy of enclosing environments known at compile time, we move up the call stack and search for a mapping from a to some variable in the environments of our calling functions.
Dynamic scope used to be the norm; the original LISP was dynamically scoped. After Scheme showed that static scoping was not only desirable but tractable, even with higher order functions3, it became standard even among high level languages. Generally, you don’t want dynamic scope; it makes reasoning about code much harder.
However, are a few cases remain where it can be useful. Common Lisp uses DEFVAR to declare a dynamically scoped variable. Some dialects of Scheme have fluid-let as part of their libraries for the same purpose. Dynamic scope can be useful where some bit of state depends on a chain of calling functions, but only a few functions in the call chain care about it. A pretty-printer might use it to track the indent level, or different functions along the call-chain may add information relevant to logging, when most functions in the middle don’t actually log.
A popular alternative is to build an omnibus object carrying a number of unrelated variables that every function in a system takes and passes to functions it calls whether it has any need for it or not. To my mind a parameter passed to every function containing ninety unrelated variables is no better than ninety global variables, and worse because it’s usually a disorganized mess that everything finds its way into, rather than designing for separation of concerns.
For personal fun, I decided to implement dynamic scope as a library in C++. I am a Schemer, but one who likes adverbs, so I call it fluidly_let.
Overview
The implementation is simple. A fluid<T> contains a pointer to an object of type T. Whenever a fluidly_let is constructed, it constructs its internal variable of type T in accord with the arguments provided, saves the fluid<T>’s current pointer and replaces it with the pointer to the newly constructed T. When the fluidly_let is destroyed, it restores the fluid’s old pointer.
Thus we have dynamic scope semantics, as we quite literally reach up into a caller’s stack frame to resolve a variable with reasonably low overhead: one pointer dereference.
There are some limitations. Both fluid and fluidly_let are uncopyable and immovable since they work by shuffling pointers around. If you have a multithreaded program, every fluid must be thread_local. This trick also only works with actual function calls. It does not work for tasks dispatched on a reactor, coroutines, or other asynchronous stuff.
fluid
This is the dynamically scoped variable. It’s a pointer plus some storage for the value it’s initialized with. I was tempted to leave out the std::aligned_storage, but I decided it was better to be able to have a value for the fluid on construction rather than requiring a separate fluidly_let to initialize it.
To use it, just declare it somewhere, treat like a normal C++ variable, (It’s effectively a fancy, schmancy std::reference_wrapper), and call fluidly_let on it when you want to declare a new binding.4
Most of the functionality is in base.
template<typename T>
class fluid : public _fluid::base<T, !::std::is_default_constructible<T>()> {
friend class fluidly_let<T>;
::std::aligned_storage_t<sizeof(T)> initial;
using base = _fluid::base<T, !::std::is_default_constructible<T>()>;
public:
using value_type = T;
fluid() noexcept(::std::is_nothrow_default_constructible<T>())
: base(_fluid::default_construct<T>::if_i_can(&initial)) {}
template<typename ...Args>
explicit fluid(Args&& ...args)
noexcept(noexcept(T(::std::forward<Args>(args)...)))
: base(::new (&initial) T(::std::forward<Args>(args)...)) {}
~fluid() {
//
// This is me being nice to you. If this test fails it
// means you are bad and wrong and ought not destroy the
// `fluid` when we're five miles down the stack with a few
// hundred `fluidly_let`s to unmake before we go. What did
// you do, dynamically allocate it and call delete? Why
// would you do that?
//
assert(static_cast<T*>(base::ref) ==
reinterpret_cast<T*>(&initial) ||
static_cast<T*>(base::ref) == nullptr);
//
// The downside of placement new
//
if (!base::empty()) {
base::ref->~T();
}
}
};Construction
This part requires some explanation.
fluid() noexcept(::std::is_nothrow_default_constructible<T>())
: base(_fluid::default_construct<T>::if_i_can(&initial)) {}I like to write code that doesn’t lay traps for its user. That’s one reason I avoid ‘zombie’ or ‘empty’ states in classes I define and let the user employ std::optional if they need something nullable. I also hate it when templates only work with default-constructible types given that I (as I just said) don’t allow a default-constructed empty state in my classes. Additionally, there may be no non-dummy value available until some function binds one.
So, I made a compromise. If T is default-constructible, then fluid<T> will never be empty. Otherwise fluid<T> default constructs as empty and accesses to it throw exceptions until a new value is bound into it. The user is allowed (and encouraged!) to initialize it with a non-default constructor.
template<typename T, bool = ::std::is_default_constructible<T>()>
struct default_construct;
template<typename T>
struct default_construct<T, true> {
static T* if_i_can(void* space) {
return ::new (space) T;
}
};
template<typename T>
struct default_construct<T, false> {
static T* if_i_can(void*) {
// Apparently I can't.
return nullptr;
}
};This just takes the address of the std::aligned_storage in fluid<T> and, if the type is default constructible, constructs it there and returns its address. Otherwise it just returns nullptr which base recognizes as empty.
References
This is where the yelling starts. Mostly by me, to be fair. I believe that libraries should be as widely applicable as possible and that references are first-class values. Other people disagree. That’s why std::optional doesn’t allow references. They make the nonsensical claim that there’s no obvious right behavior on assignment to an optional reference5 and that std::optional is a container6.
All my library types do allow references when possible. Here’s the version of fluid for references. We don’t need a std::aligned_storage here because all we store is a pointer to whatever the reference references. This is also why we don’t have an assertion. There’s no ‘known’ value that tells us there are no outstanding fluids, and I don’t want to use extra space just to catch an error.
template<typename T>
class fluid<T&> : public _fluid::base<T, true> {
friend fluidly_let<T&>;
using base = _fluid::base<T, true>;
public:
using value_type = T&;
fluid() noexcept
: base(nullptr) {}
explicit fluid(T& v) noexcept
: base(::std::addressof(v)) {}
};base
Most of the work of fluid is here, since only the initialization differs between references and non-references. We pass in CanBeEmpty as a separate parameter since it can’t be reliably inferred from T, given that T can be a reference type. We have two specializations.
Possible Emptiness
If we can be empty, we must check and throw an exception when someone accesses us. Come the Revolution (i.e. C++20), we won’t throw exceptions, we’ll just declare a contract requiring that the fluid be nonempty.
template<typename T>
class base<T, true> {
void throw_if_empty() const {
if (empty())
throw empty_fluid("You cannot access an empty fluid.");
}
protected:
T* ref;
public:
base(T* ref) noexcept
: ref(ref) {}
base(const base&) = delete;
base& operator =(const base&) = delete;
base(base&&) = delete;
base& operator =(base&&) = delete;
bool empty() const noexcept {
return !ref;
}
T& operator *() const {
throw_if_empty();
return *ref;
}
operator T&() const {
return *(*this);
}
T* operator ->() const {
throw_if_empty();
return ref;
}
};The Fast Path
If we know we’ll never be empty, don’t waste time checking whether we are. Also, we can declare all our access methods to be noexcept.
template<typename T>
class base<T, false> {
protected:
T* ref;
public:
base(T* ref) noexcept
: ref(ref) { }
base(const base&) = delete;
base& operator =(const base&) = delete;
base(base&&) = delete;
base& operator =(base&&) = delete;
bool empty() const noexcept {
return false;
}
T& operator *() const noexcept {
return *ref;
}
operator T&() const noexcept {
return *ref;
}
T* operator ->() const noexcept {
return ref;
}
};In a Bind
fluidly_let is similar to std::lock_guard. You declare it and then it sits there until it gets destroyed. This kind of thing makes me wish C++ had anonymous variables. I wonder if we can convince them to use %_ or something to represent a variable that can be defined and can go out of scope and be destroyed but nothing else.
Internally we just construct val, store f.ref in old and then store a pointer to val in f.ref. On destruction we put old back into f.ref so everything is back the way the function that called us left it.
template<typename T>
class fluidly_let {
fluid<T>& f;
// This is the value that we set.
T val;
// And this is the old value.
T* old;
public:
template<typename ...Args>
fluidly_let(fluid<T>& f, Args&& ...args)
noexcept(noexcept(T(::std::forward<Args>(args)...)))
: f(f), val(::std::forward<Args>(args)...), old(f.ref) {
f.ref = ::std::addressof(val);
}
~fluidly_let() {
f.ref = old;
}
fluidly_let(const fluidly_let&) = delete;
fluidly_let& operator =(const fluidly_let&) = delete;
fluidly_let(fluidly_let&&) = delete;
fluidly_let& operator =(fluidly_let&&) = delete;
};References
Another version for references. References are special since you can’t have a pointer to them.
template<typename T>
class fluidly_let<T&> {
fluid<T&>& f;
// The previous resident in the fluid
T* old;
public:
fluidly_let(fluid<T&>& f, T& val) noexcept
: f(f), old(f.ref) {
f.ref = ::std::addressof(val);
}
~fluidly_let() {
f.ref = old;
}
fluidly_let(const fluidly_let&) = delete;
fluidly_let& operator =(const fluidly_let&) = delete;
fluidly_let(fluidly_let&&) = delete;
fluidly_let& operator =(fluidly_let&&) = delete;
};Conclusion
And there you have it: a fun, little exercise to implement a defining characteristic of obsolete languages nobody cares about in C++. As usually happens in C++, the actual design is dirt simple and only becomes complicated because of all the special cases.
Source
An include file with all the code you see here, plus bonus code like #include statements, namespace declarations, and the exception we throw can be found here!
The ‘scope’ of a variable access refers to the hierarchy of name to variable mappings in force at the site of the access. If I access a variable by name in one function, local variables in a different, unrelated function are simply not in scope. Local variables in the function where the access is performed are.
For our purposes a ‘name’ within a scope identifies a ‘variable’, a location in memory, from which ‘values’ can be read and to which they can be stored.↩
An ‘environment’ is, for our purposes, a single set of name to variable mappings. In C++ a single block is an environment, as is a class.↩
Functions that return other functions. In Scheme, I can return functions and call them thus:
(define (f v) (lambda () (let ((v' v)) (set! v (+ v 1)) v'))) (define g (f 5)) (define h (f 1)) (g) ; Returns 5 (g) ; Returns 6 (h) ; Returns 1 (h) ; Returns 2 (g) ; Returns 7Each function returned from
fhas a separate, mutable variable (initially initialized to the parameter off) of its own. You could return several functions from one invocation and see that they share the same environment. Garbage collection ensures that all the variables referenced by the returned functions last only as long as the functions referencing them do.Algol family languages and C used static scope before Scheme, but one could not manipulate functions as values. C has function pointers, but those are just references to existing top-level functions with the global environment as their enclosing scope.
In its attitude of “pay for what you use”, C++ gives you first-class functions, but requires you to specify what you capture and whether to do it by copy or reference. Managing the lifetimes of any captured variables is also up to you, with a little help from
std::shared_ptrandstd::unique_ptr.↩Bear in mind the difference between creating a new binding and mutating a variable. If a
fluidreferences a mutable variable and our function mutates it, then that mutation persists and our callers see it. When we create a new binding withfluidly_let, that binding is visible to functions we call, but only lives until the end of the block containing thefluidly_let.↩There is. It’s the behavior that
boost::optional, upon whichstd::optionalis based, uses. Anoptionalis, essentially, a nullable, reseatable static box. You have to dereference it. It allows you to default initialize it as empty even if the type it contains doesn’t allow default initialization and has no empty state. References are one such type. The rebinding semantics onfoo = barmight be thought of as a special case for references, though I think of the lack of rebinding as an optimization for object types that define assignment to have the usual semantics. Havingfoo = barbe the same asfoo = std::nullopt; foo.emplace(bar)in the case of nonemptyfoowould be more correct (and those who want the assignment operator of the contained type can use*foo = bar). But giving object types the special case of non-rebinding semantics gives better performance without the user having to check for empty before every assignment.↩This is begging the question. If we say that something doesn’t work with references merely because it’s a container, we’re relying on the assumption that references aren’t first-class and things shouldn’t work with them.↩