Das Gut² Buch - gut

From concrete to abstract

An important guiding principle to designing this library is to start from usage of C++ as encountered in the world in order to identify candidates for formalizing in a more general manner.

As much as we'd love a purely theoretical, first-principles basis for all constructs in a library , there exist the ugly reality of reality. Computer programs run on machines, programming languages run on humans, an humans run on biology. Like the biological language of genetics, programming languages like C++ must propagate its existence by evolving new features efficiently, ie, from existing features where possible, and so accumulate a variety of vestigial parts and time bombs.

Self-checking

This is a much more pragmatic consideration. For this library, as much functionality should statically checkable by the compiler itself. This means all functions and types must be constexpr.

This implies no reliance on memory allocations and non-trivial destructors. This also means runtime tests still have a place to test non-trivial destructor types.

Unfortunately most <algorithm> are not constexpr, with some allocating memory underneath the covers, and so cannot be used. But this is acceptable anyway, since we want to extend the notion of algorithms beyond what they currently are. Ranges cover one way of extending algorithms, so this library will go a different direction.

Beware of cargo cults

Cargo cults can appear in many different guises that pretend to be otherwise. Phrases like "idiomatic code", "best practice", "consistent code" (in terms of readability), have become a shield for cargo cult tendencies. Same with the snowclone "X Driven/Oriented Design". And don't get me started on design patterns. They tend to lull the practitioner into a false sense of having worked through a problem.

Ideally every detail, from API design to bit-level implementation, should be justified, but that's not economically possible. We must rely on rules-of-thumb in a lot of situations, but that is the highest level of reverence we should grant them.

Expressing intent is what we're really after, and that is really the goal of "idiomatic code", "best practice" or "consistent code". However, sometimes they get in the way of expressing intent. They are, at best, shortcuts to understanding unfamiliar code, and like all shortcuts, are no use when they lead to the wrong destination. Design is not and should not be driven, or oriented, by any single concern or style. Patterns, like those on living creatures, emerge over time, not imprinted in the beginning. They emerge from simpler, localized rules.

An argument goes that code is read more often than it is written, so readability, and read speed, is more important than clever code. That is only part of the story. Code is not read more often than it is read. Code is only really read under the following situations:

• When it is being written
• When it is being tested as it is being written
• When it is being rewritten because it failed

Code that works doesn't get read. Most people don't read the STL. When reading code for debugging and fixing, the ability to read code fast is not a virtue. Speed reading means details being skipped because of false assumptions made when a piece of code merely resembles a well known idiom. Simple code is as complex as it needs to be for correctness and performance. Familiarity must also be factored when trying to discern whether code is too complex.

To be sure, usability is a high priority for this library. Usability comes from understanding concrete ways of working, not naming conventions. Simplicity is not choosing the inferior, straight-forward code, but code that is easier to reason about. Hint: implicit state management in highly branching control flow may seem easier for not using advanced language or library features, but are harder to reason about because of the combinatorial explosion of state transitions and error states.

Toolless

As much as possible, non-standard tools should be avoided. No code generators, like Qt's moc. No documentation generators, like Doxygen. No dependency on build systems, continuous integration, or packaging. Any proposed library feature that necessitates build systems, continuous integration or packaging is likely badly designed for the purposes of this library.

Widely installed tools, even non-POSIX GNU utilities, are preferred. make for building, awk and inline HTML5 for documentation. HTML5 is a deceptively powerful tool for literate programming, although it isn't a guiding principle for this library. We can only aim for semi-literate programming at best.

Of course, any tool provided by GCC or clang is also preferred.

Code-level principles

No static, global or thread_local state, unless it's non-static inline constexpr for the purposes of testing.

No allocations, but support user-provided buffers a la Elements is a good idea as an alternative.

No RTTI, and therefore no exceptions.

Gather round, let me tell you a story

No creative work ever appears fully realized. The expression of ideas is never final, and always changes. The ways a creative work evolves can tell us a lot more about purpose than just its apparent form, just like how phylogenetic trees and fossil environment informs us about a modern organism's behaviour.

To that end...

This is a story all about how my code got flipped, turned upside down. And I'd like to say a few things before we code jam. I'll tell you how I accidentally learned to metaprogram.

Algorithm, interrupted

C++11 came out after disappointingly missing its previous 2009 deadline. Despite that, C++ was generating activity, and the community began pumping out videos online. Like many C++ programmers, I quickly came across C++ Seasoning by Sean Parent.

At that point, other than using the standard containers, I had no clue how templates worked, let alone generic design. Due to C++'s lack of class template argument deduction, and somehow managing to avoid <algorithm>, I didn't know types can be deduced. Like most OO programmers, I only knew abstraction via virtual polymorphism.

After learning how to deduce template arguments, instead of delving into algorithms, I got sidetracked into writing a serialization library.

There are many ways to write the metaprogramming for a serialization library. This mostly involves starting out with a variadic template, then recursively interpret the list of types and dispatch to a specialization or an overload. Sprinkle SFINAE where the compiler is confused by ambiguity.

Even with C++14's relaxed rules about constexpr functions, things like loops only works for values of the same type. For handling lists of types, you either had to do it recursively, or you had to defer to another function that takes your comma separated list of types.

Enter C++17 fold expressions, and if constexpr

Fold expressions and SFINAE-less dispatch turns metaprogramming into regular programming - at compile time. Regular programming deals with values. Loops and conditions deals with values. Metaprogramming deals with types. Partial specializations define and resolve types.

Turning types into values, and values into types.

constexpr values are fickle and lose dependable constexpr-ness easily, such as being passed through functions. So to force values to be constexpr, they must be treated as types. The best way to do this is with the constant library.

constant leverages the C++17 feature of auto template parameters to avoid the need to specify the exact type of a constant. It functions in the same space as std::integral_constant and std::bool_constant with the added benefit of being more natural to use. auto template parameters can be boolean, integer, enum and function pointer. constant therefore allows any constexpr value of those types to be preserved as their own individual type.

By their nature as templates, every unique constant is thus its own type. As such, another use for constants is as tag types for tag dispatch. bool constants can be used for type traits much like std::true_type and std::false_type.

constants of function pointers avoids the need to have to store a function pointer. A constant function pointer takes up as much space as an empty struct, instead of the space of a full pointer or member pointer.

All constants are empty objects and, when used as a base class, benefits from the empty base optimization.

In a general setting, constants can be used in any situation, but in terms of self-documenting code, we may want dedicated constant types that disambiguates usage, specializations and overloaded functions.

An index works just like a constant, except it only accepts a std::intmax_t value. In some contexts, you can't pass a constant as a template parameter, such as when calling an object via a template operator function (eg, subscript). So use index as a constant with the intent of accessing some object at an index known at compile-time.

There's a bit of controversy around the choice of std::size_t as an index type, due to the semantics of unsigned types. One of those semantics is the wraparound behaviour on underflow, since unsigned types don't have negative values. Signed types have negative values, so in contexts where non-negative values are expected, negative values represent a very handy error state. The choice of this library to go with signed integers is about seeing how things develop.

Another frustrating aspect of using std::size_t for indexing is that the related type std::ptrdiff_t is signed and can be used for pointer arithmetic, but not for indexing.

As alluded to above, std::size_t is actually pulling double-duty as both an index and a size, and that doesn't mix with distance/counting either, even though they should have related underlying types but have different high level semantic roles. This library has yet another constant type for expressing the number of objects.

The count type works just like the index type, down to the underlying type. They are not related through base classes, though, for the same reason - to disambiguate the intent of using count instead of index.

On the flip-side is using types as values for regular programming style instead of metaprogramming.

The type library wraps traditional <type_traits> into member functions. If the wrapped trait defines a type alias, the trait wrapper returns a type-as-value.

Template classes, concepts and traits in the GUT library define internal type aliases from the template arguments, like in standard types. In addition, they must also define constexpr static functions that return the type aliases as values. This can greatly improve usability by reducing the need to decltype an object just to get at the type alias, because static member functions can be accessed from both the class, and an object of that class.

constants and types rounds out the analogs of fundamental objects. On their own, they have some utility, but remember their existence comes about because of the use of metaprogramming constructs like std::integer_sequence and variadic templates.

To be more generally useful, they must also be composable, like the regular language, into aggregate types such as lists and structured types. To that end, index_list and type_list is provided.

These constexpr list types makes processing of constants at compile time feel natural. The standard counterpart exposes no way of getting to its list of values, requiring them to be re-deduced in a template to be accessible. This library goes the extra step by doing that for you, and all that is needed is to provide a generic lambda to accept the values supplied. The values are supplied as constants so, as discussed above, they retain their constexpr-ness reliably.

These lists also set a standard for other algebraic types in terms coding in a functional style. Similar to ECMAScript arrays, GUT algebraic types provide each, map, filter, and reduce where possible.

In the context of these compile-time lists, this means you can access the list elements on a one-by-one basis, transfrom an element on a one-by-one basis, filter elements on a one-by-one basis, and reduce/fold all the elements. The elements in the reduce/fold case are supplied as a parameter pack expansion to the provided generic lambda.

The type counterpart of index_list is type_list.

type_list is intended to be used in the exact same manner as index_list. Algebraic types should aim to expose its member types as a type_list to simplify compile-time usage.

Now that compile-time values, types and lists have been formalized, most cases of metaprogramming are covered. Compile-time computation for sure is obvious. Generative programming is covered by lists, as any algebraic composition and other kinds of composition of types is made simple with lists. The last kind of metaprogramming, compile-time verification, will be formalized.

Feature detection and special composition types

These libraries are mostly to cover concepts and the detection idiom that is still missing from standard C++.

Feature detection is, unfortunately, the last holdout of user invoked macros. Values and types do not cover anything involving syntactic elements of the language. ie, until we get compile-time reflection. Syntactic elements are things such as member definitions, inner type aliases, expressions and names. Trying to hook them into the type system requires a lot of boilerplate code and non-obvious idioms, so macros are defined to make the process less error prone.

Feature detection creates traits and templated bools that represent some sort of valid expression. Separate macros are defined to detect features in the form of type aliases, member definitions and valid expressions (operator expressions and function calls). As an added bonus, feature detectors for all overloadable operators are defined for the purposes of building blocks for high-level concepts.

Some special place holder types ease the algebraic composition of types.

These are simply empty types that provide for overload and specialization resolution.

Basically Useful Things

The basic building blocks of C++ are values, references, and arrays. Just like with constants and types, we need a formal way of treating values, references and arrays in a generic manner. And just like with those libraries, the way to do that is to make them values.

C++11 introduced std::reference_wrapper. Its only purpose is to hold references and so makes for awkward usage generically. This library provides a more general thing.

The motivation for thing is to allow treating both values and references generically. It is especially helpful when implementing types that may want to wrap and store objects as they are supplied - whether as values or references, and avoid the rigmaroll of compile-time dispatching based on whether it is a reference or not.

An added benefit is for type composition involving inheritance. For example, the simplest way to implement ntuple is by defining its member types as base classes. This is impossible to do with reference types or final classes. Wrapping it first in a thing makes it possible, and it doesn't disable empty base optimization.

GUT has an analogue to std::array in the form of buffer.

It pretty much does the same thing as std::array, except without fill. But given constexpr lambdas (using the immediately invoked lambda technique), you can easily have fill-initialization at compile-time.

Having constexpr arrays is surprisingly handy for metaprogramming. In previous discussions above, the limitations of loops with heterogenous types and compile-time values makes it hard to work with metaprogramming. Still, there are many cases where it is just easier to deal with an array of normal values that can still produce a constexpr result.

For example, you may use fold expressions coupled with <type_traits> to statically check that a parameter pack meets some criteria. But this can only be done on a per-element basis. Sometimes you need to compare adjacent types, or even perform some kind of O(n) algorithm to test on conditions between all elements. Encoding these kinds of properties as a plain array simplifies the syntax of compile-time verification by avoiding the type system.

With these general "object generalizers" in place, it is now much easier to build types on top of other types. But before that, there are a few stray abstractions that can also come in handy.

In addition to reliable constexpr handling of numerical values, regular numerical values also need better abstractions for runtime values for which we know some compile-time constraints. The candidates for this are integers and bitfields, in contexts where we know something about, say, their maximum and minimum values.

The underlying type for integer is signed due to reasons addressed above. The size of the underlying type is defined based on the maximum number of bits needed to represent the desired range, up to the number of bits supported by std::intmax_t.

Even though it represents a runtime value, and the bitsize of the underlying type allows a greater value than the specified maximum, limiting the bitsize of an integer is still useful for limiting the potential damage of out-of-range values. For example, when used as an index to an array, we know the maximum size of array, and it will rarely require the full std::size_t range. If we accidentally overflow on the index, at least we won't be accessing memory that is gigabytes away.

The language provides bitfields, and the standard provides std::bitset, but normal bitfields have unspecified layout and non-portable endianness. Bit sets only allow single bit members. bitfield fills the gap by providing predictable bit packing layout and big endianness. Fields can be of arbitrary bitsize up to std::uintmax_t, and are packed. The size of the entire bitfield is not limited to a register sized type.

Fields are accessed via proxies addressed via an index, and there is a facility to "cast" a bitfield to a different layout. No reinterpret_cast or union punning is used, so there is no undefined behaviour. The "cast" merely changes the underlying bit offsets used for masking, shifting and or-ing.

It is interesting that it straddles between basic types and composed types. It does so in order to provide features that emulate the lower level types, such as indexed access, but also higher level ideas, such as arbitrary size and layout.

Besides the obvious use for network packet headers and hardware registers, bitfields can also be used as a packed index for a multi-dimensional array. As with integer, a range-limited multidimensional index reduces the impact of overflow. A side benefit is that the index doesn't take up the space of rank * sizeof(std::ptrdiff_t) bytes. We can just take as much space as needed to index each extent of the array.

Algebraic types

Despite the grandiose category name, it is not intended for the library to adhere to any pure theoretical notions of type algebra. The types introduced here aim to be maximally composable with the minimal syntax, but there will always be corner cases where abstractions breakdown.

C++11 introduced the first algebraic type tuple as an extension of pair. From there, C++17 introduced the widely known algebraic types optional and variant. From a metaprogramming view, they are a bit cumbersome to use. std::apply and std::visit are very annoying to write. GUT implements the same algebraic types, but with the aid of the metaprogramming constructs defined above.

This library's implementation of algebraic types follows the overarching goal of this library to be unified, meaning it should reuse its own first class types as much as it can.

All algebraic types, as the name implies, should decompose just as easily as they are composeable. They should all support the same general interface:

Indexed and typed construction and assignment.

Given an index or type qualifier, construct or assign to the member object that matches the qualifier.

Structured binding support.

Language support for syntactically pulling out objects of member types.

The higher order operations are the safer alternative if not all objects of member types are necessarily valid.

Array layout alternatives.

Store as arrays of member types, rather than an array of the whole type.

If the regular type has bookkeeping, keep the bookkeeping in its own separate object.

Higher order operations:

map

Transform each valid member object to another object.

each

Apply function on each valid member object.

filter

Remove member types not matching some criteria, preserving any valid member object.

call

Call each valid member object that is callable with the supplied arguments.

reduce

Folds all valid member objects into another object.

Topological types

If we think about algebraic types as reasoning about the composition of values, we can think about topological types as reasoning about the value space of those type compositions. Again, no rigorous mathematical treatment is implied. Their design is based mostly on generalizing the common usage patterns of various schemes of dealing with value spaces of objects.

You can think of this library as being in the same style of abstraction as <algorithm> and <iterator>, or ranges, or streams, but unexpectedly, also functional composition. This library aims to create a greater sense of cooperation between all these different styles of abstractions.

ranges can be thought of as generalizing iterator pairs, and streams can be thought of as turning algorithms into pipelines of execution. This doesn't mean algorithms, iterators and iterator taxonomies are gone. Elements explains that the original concept for iterators was more like coordinates - generalizations of pointers that denote the position of an object in the context of a wider space.

Coordinates therefore need not be addresses to memory, but signposts to a value, whether that value resides in memory, or is the product of a function at a given coordinate in a space. The way a coordinate is connected to another is a property of the space the coordinate belongs, and may not be limited to the old iterator categories.

This library puts functional composition closer to the heart of the abstraction. Whereas the other abstractions are mostly concerned about iterating over a collection of objects, this library is more concerned about defining the properties of the space that objects belong in. Functional composition can be used to define those properties, such as coordinate traversal, value access, projection, and comparison.

Functional composition can also be used to create lazy evaluation. Instead of performing an algorithm immediately, the algorithm can be partially bound with arguments, and be supplied as an argument to another algorithm. It's kind of like creating a template for a pipeline and avoids manually managing intermediate iterators or containers.

The functor library for functional composition builds functions from general expressions. Free functions, member functions, function objects and data member pointers are wrapped in a generic function. Unlike std::function, it does not do type erasure so there is no heap allocation and no virtual dispatch.

This library also provides argument placeholders. functions can bind values to arguments and leave placeholders for unbound arguments. Placeholders can be combined with operators to create generic functions that wrap the expression created by the operator.

Functional composition can be used to hide details like caching calculations, or create a multi-pass algorithm even if the underlying resource is a one-pass stream. This use is like the generalization of pseudo-ranges, like std::ostream_iterator or std::regex_token_iterator. They don't really point to a value or iterate over a container, and in the end is more like a function than a range.

This library chose space as the abstraction primitive, as opposed to iterators, ranges or streams, because most general operations on objects requires knowing where they reside.

Iterators on their own, or in a pair, does not give strong guarantees about the validity of the objects or the iterators themselves under certain operations. In the STL, iterator validity is documented to be governed by their originating container, and further by the container's operation that may explicitly affect or not-affect other iterators.

By abstracting on a space, which is like a generalization of a container, we keep the link between the position and the coordinates intact. While we still have coordinates as a separate abstraction to allow us the same genericized usage, we don't run the risk of operating on invalidated ranges. Ranges are clamped and never exceed their original bounds, so any action that invalidates a space will merely produce an empty space.

A space need not be a memory space or a container space. It can be just a functional space, such as a colour-space (eg YUV to RGB), or a normalized floating-point coordinate space (eg curve arclength to position). The space would be defined by a function and function composition rather than memory. In the same way, another possible use for spaces in conjunction with functors is for shared memory or memory mapped files that you may want to unmap/remap at a later time.

Instead of defining a space in terms of memory positions, you would define a space in terms of boundaries delimited by coordinates and a function taking an argument of that coordinate type.

spaces will implement the <algorithm> as member functions to make it easier to chain them together. Algorithms that modify the underlying space should create new spaces annotated with the imbued properties, such as a predicate or comparator. By doing this, we can reinforce requirements such as whether a space is sorted, or whether a subspace is partitioned according to some predicate, for example.

Extra types

Compile-time strings

Compile time arrays are already possible with buffer. We just need to go one step further to extend the types to allow string manipulation, like concatenation and splitting.

Transactions

As a generalization of what is sometimes called a finalizer. Some kind of sentinel type is created whose sole purpose is to run some kind of cleanup function on destruction.

This library would extend the idea to allow the user to specify a transaction. This includes intermediate save points and rollbacks. One potential design is that moving a sentinel creates a savepoint, and destruction during an exception is a rollback. A normal destruction is a commit.

any

Full-blown type erasure would require non-constexpr friendly things like placement new, but for constexpr type erasure, it would be achievable for trivial types that can be converted to and from bytes without reinterpret_cast.

Identified argument binding placeholders.

Variable stack for function composition.

This extends functional composition by allowing repeated arguments to be identified and thus reduce repetition of arguments. For example, a comparator may reference multiple members of an object, and we need to only provide the object argument once.

A variable stack will allow intermediate values to be saved temporarily, and then accessed later via a name. This will make lazy evaluation more efficient by allowing the user to specify exactly what expressions to save, and how to save it.

An even more crazy idea would be exception-style error handling. The variable stack can have frames and emulate the implicit RAII in the language.

cache

A library to hide the method of producing the value behind a value. If its source is updated, the cache value is invalidated and recalculated. Otherwise the saved value is used.

Reference counting

Decouples reference counting from memory allocation.

For example, a resource may be managed by some system and its allocation strategy may not be suitable for a heap allocation.

Compile Time Type Information

An opt-in, explicit, reflection library. Users plug their types into type system, and from there we operate on the types and their compononents programmatically.

Extra unifying features

Serialization and deserialization

The terms are normally used to mean turning objects into a efficient, compact, blob of bytes. In this library, we will extend it to mean plain old human readable printing, as well as to executable forms, like SQLite databases, or even SQL scripts.

Data dependency propagation model

Much has been made about state machines, but I wonder if what we really want is just a way of propagating state throughout the system in a reasonable manner. Alan Kay's original concept of Object-Oriented programming is about extremely late binding between names and their values. Message passing and all the other OO baggage is only there to help achieve late binding.

Extreme late binding means that the value behind a name is not resolved until at the very last moment. It's kind of like lazy evaluation, but with state. Message passing is not really about defining object methods, but rather expressing the binding between objects via some process. Such a process, a function, may link with another object. As messages are passed between objects, state flows through the dependency graph.

Execution context

The GUT library avoids global state at all costs. This is so that no unexpected dependencies and initialization orders can cause trouble. However sometimes there is need for a common state for an application, and some libraries use global functions that manipulate state behind the scenes.

An execution context, which users derive from, will allow common state and state functions to be accessed in a syntactically similar manner, but without entangling the entire program. It will formalize having multiple execution contexts that does not impose a thread, fibre, coroutine model.

Such global state may include allocators, error conditions, and exception states. An execution context can simplify things by allowing users to allocate or throw as they would in the language, calling magic functions that the compiler knows what do do with, but we can limit their actual effect on the application as a whole. We also would eliminate the need to pass those language-like constructs as arguments.

There should be nothing inhibiting having multiple execution contexts because they would not share anything with each other.

Unconstrained extension libraries

Functionality outside the scope of this library will be implemented in other libraries:

SEHR GUT

Supplementary Extensions and Helpers for GUT.

This library can include things that are designed to integrate with the rest of the language and the STL.

One crazy idea is to experiment with formalizing the use of setjmp/longjmp.

CAT GUT

Common Architecture Templates on GUT.

For stuff like Component-Entity-System. Document-Object-Model. Object-Relational-Mapping. Model-View-Controller. Execution-Workflow-Definition.

GUT MicroBIOME

GUT Micro-collection of Basic Input Output Modular Executables.

There will be two modes of use for this library: as a shell executable, and as a library. For example, there will be equivalents for tools like grep, awk and even make that can run from the shell. But moreover, the library interface for these tools will resemble how they are used in the shell.

We aim to make using this as a library be easier than using a shell. We have the tools of the language, like strings and regular expressions, but with the benefit of compile time checking the validity of a command.

The GUT MicroBIOME is where all the GUT libraries come together to rapidly create applications.