tag:blogger.com,1999:blog-19694240298316315092018-09-16T23:42:50.885-07:00Crafting AbstractionsCody Griffinnoreply@blogger.comBlogger3125tag:blogger.com,1999:blog-1969424029831631509.post-83435344116640243492012-10-10T12:48:00.001-07:002012-10-10T13:06:21.185-07:00The Paradox of Software ComplexityA common principle in user interface design is the conservation of complexity. Every task has some fundamental, irreducible complexity. Designers can either hide this complexity behind a simple interface or expose it to the user through a richer, more complex interface. What if a designer adds useless widgets to the interface? Because complexity is added beyond what the user needs, the interface has been complicated. This same principle applies when designing abstractions in software; hiding complexity behind abstractions is one way our limited minds can build complex software! After all, it is much easier to reason about structures and functions than raw memory addresses and stack frames. Herein lies the paradox - partitioning software into abstractions is fundamentally a complication. <br/><br/>Complexity can be looked at as the "inter-connectedness" of the parts of a system. The more parts and connections between them, the more complex the system becomes. An abstraction takes some of these connected parts and hides them behind a new part. We have hidden the details, and the top-level is now (hopefully) simpler. The complexity from the details does not just go away; it is only hidden behind the abstraction. On top of this, we now have a new part and its new connections. The system is now complicated! If an abstraction is not worth the cost of this complication, then it is a bad abstraction. <br/><br/>For this reason, good abstractions are highly coherent and minimally coupled. A perfect example is a C compiler. A good compiler can abstract away the details of the machine code and free our minds to build higher-level abstractions. The programmer still has to worry about managing resources, but can have the convenience of functions and loops rather than the moves and jumps that are implemented by the CPU. In specific cases, a programmer will need to know these hidden details <a href="http://www.joelonsoftware.com/articles/LeakyAbstractions.html">anyway</a>. A C compiler is so decoupled that it does not need to be shipped with the binaries it produces. The C standard library, however, is supported by a platform-specific runtime library. This allows a lot of higher-level, platform-dependent parts to be abstracted away too. We can continue to hide complexity with virtual machines, network stacks and GUI toolkits. Every part hidden is another part we can afford to build. <br/><br/>In a perfect world, this article would have ended after the last sentence. As we covered earlier, there is a complication - all of these abstractions add unnecessary complexity. Their fundamental complexity does not just go away; somebody has to manage that complexity. To make matters worse, it is sometimes necessary to understand some of the abstracted details anyway. These leaky, complicated abstractions often result in performance, maintenance and security issues. Sometimes the complication pays off: the software components can be reused or divided more efficiently among a team. Other times, the cost of this complication will scale much faster than the software. Cody Griffinhttps://plus.google.com/116676205271053533228noreply@blogger.com2tag:blogger.com,1999:blog-1969424029831631509.post-42857010209678628922012-09-22T12:56:00.002-07:002012-09-25T21:06:24.367-07:00Improving on TuplesIn the <a href="http://blog.codygriffin.com/2012/09/a-case-for-tuples.html">previous</a> article, we saw how a tuple is really just a struct disguised as an array. A tuple simply maps a struct's types to an index. Just as we can iterate over an array at run-time, we can iterate over a tuple's elements at compile-time. For example, we can implement a simple linear search and iterate over the tuple until an element of the given type parameter is selected. If no element of that type is found, then the code won't compile. Because all of this happens at compile-time, there is very little run-time overhead. <pre class="brush:cpp"><br />//------------------------------------------------------------------------------<br />// Recursively iterate over tuple<br />template <int N, typename A> <br />struct TupleGetType { <br /> typedef typename std::tuple_element<N, A>::type ElementN;<br /> template <typename T><br /> typename std::enable_if<std::is_same<T, ElementN>::value, T&>::type<br /> static getType(A& tuple) {<br /> return std::get<N>(tuple);<br /> }<br /><br /> template <typename T><br /> typename std::enable_if<!std::is_same<T, ElementN>::value, T&>::type<br /> static getType(A& tuple) {<br /> return TupleGetType<N-1, A>::template getType<T>(tuple);<br /> }<br />};<br /><br />//------------------------------------------------------------------------------<br />// Terminate at first element<br />template <typename A> <br />struct TupleGetType<0, A> {<br /> typedef typename std::tuple_element<0, A>::type Element0;<br /><br /> template <typename T><br /> typename std::enable_if< std::is_same<T, Element0>::value, T&>::type<br /> static getType(A& tuple) {<br /> return std::get<0>(tuple);<br /> }<br /><br /> template <typename T><br /> typename std::enable_if<!std::is_same<T, Element0>::value, T&>::type<br /> static getType(A& tuple) {<br /> static_assert(std::is_same<T, Element0>::value, <br /> "No element of type T in std::tuple");<br /> }<br />};<br /><br />//------------------------------------------------------------------------------<br />// Convenient wrapper<br />template <typename E, typename T> <br />E& getType (T& tuple) {<br /> return TupleGetType<std::tuple_size<T>::value-1, T>::template getType<E>(tuple);<br />}<br /><br /></pre> Now we don't have to worry about the positions of elements within the tuple. Although this isn't the prettiest or most readable code, the stink is safely encapsulated by the getType function. Of course, there is an obvious limitation: if the tuple has more than one element with the same type, only one will ever be returned by getType. We will explore the upside of this limitation in a moment. <br/></br>We've already mentioned that tuples are basically equivalent to structs. More importantly, they allow us to define a collection of heterogeneous types using template parameters at compile-time. Because of this parameterization, tuples are incredibly useful when writing abstractions. A great example is a type-safe publish/subscribe mechanism: <pre class="brush:cpp"><br />//------------------------------------------------------------------------------<br />// Simple event handler interface<br />template <typename Event><br />struct Handler {<br /> virtual void onEvent(Event event) = 0;<br />};<br /><br />//------------------------------------------------------------------------------<br />// Our main event registrar<br />template <typename... Events><br />struct EventRegistrar {<br /> // Publish an event of event type E<br /> template <typename E><br /> void pub(E event) {<br /> for (Handler<E>* e : handlers_<E>()) {<br /> e->onEvent(event);<br /> }<br /> }<br /><br /> // Subscribe to the event type E<br /> template <typename E><br /> void sub(Handler<E>* pHandler) {<br /> handlers_<E>().push_back(pHandler);<br /> } <br /><br />private:<br /> // Get the list of Handler<E>s<br /> template <typename E><br /> std::list<Handler<E>*>& <br /> handlers_() {<br /> return getType<<br /> std::list<Handler<E>*><br /> >(eventHandlers_);<br /> }<br /><br /> // tuple of lists of handler<> pointers<br /> std::tuple<<br /> std::list<Handler<Events>*>...<br /> > eventHandlers_;<br />};<br /></pre>And its usage: <pre class="brush:cpp"><br />//------------------------------------------------------------------------------<br />// Some trivial event definitions.<br />struct EventA {};<br />struct EventB {};<br />struct EventC {};<br /><br />//------------------------------------------------------------------------------<br />// Handler for EventA<br />struct HandlerA : public Handler<EventA> {<br /> void onEvent(EventA a) {<br /> std::cout << "EventA Fired!!!" << std::endl;<br /> }<br />};<br /><br />//------------------------------------------------------------------------------<br />// This one handles two events<br />struct HandlerBC : public Handler<EventB><br /> , public Handler<EventC> {<br /> void onEvent(EventB b) {<br /> std::cout << "EventB Fired!!!" << std::endl;<br /> }<br /><br /> void onEvent(EventC c) {<br /> std::cout << "EventC Fired!!!" << std::endl;<br /> }<br />};<br /><br />//------------------------------------------------------------------------------<br /><br />int main () {<br /> // Define an event registrar for events A, B and C<br /> EventRegistrar<<br /> EventA, <br /> EventB, <br /> EventC<br /> > reg;<br /><br /> // Define two handlers, one for handlers event A, and one for events <br /> // A and B.<br /> HandlerA handlerA;<br /> HandlerBC handlerBC;<br /><br /> // Subscribe to event types<br /> reg.sub(&handlerA);<br /> // We must tell the registrar which event we want to register<br /> // in this case because otherwise it is ambiguous<br /> reg.sub<EventB>(&handlerBC);<br /><br /> // Publish some events<br /> reg.pub(EventA()); // triggers event<br /> reg.pub(EventB()); // triggers event<br /> reg.pub(EventC()); // no event triggered<br /><br /> // Nothing was subscribed to EventC (our handlerBC had<br /> // only been added to the EventB registry). Subscribe<br /> // to EventC<br /> reg.sub<EventC>(&handlerBC);<br /><br /> // Publish another EventC <br /> reg.pub(EventC()); // triggered event<br /><br /> // The following should fail with compiler errors<br /> #ifdef FAIL_SUB<br /> reg.sub<EventC>(handlerA);<br /> #endif<br /><br /> #ifdef FAIL_PUB<br /> struct EventZ {};<br /> reg.pub(EventZ());<br /> #endif<br /> <br /> return 0;<br />}<br /><br /></pre>Everything is parameterized by type. As you can see, type parameters "flow" more easily between the different layers of our abstractions. There is little syntactic noise. Parameterizing by types also gives us type safety. The pieces of code guarded by FAIL_SUB and FAIL_PUB will actually provide compiler errors: handlerA can't possibly subscribe to EventC and the registrar has no clue what EventZ is. <br/><br/> What if we do want to store multiple elements of the same type in a tuple? We could revert and use tuple indices to address these elements; but as we saw previously, this is ugly and error-prone. Throwing away all of this context makes it far too easy to mix up variables when using the tuple. What if instead, we wrap the type in a struct and create an entirely distinct type? We can even provide some constructors and casts to make this new type more natural to use. <pre class="brush:cpp"><br />template <typename T, typename N><br />struct NewType {<br /> NewType()<br /> : value_() {<br /> }<br /><br /> NewType(const T& value)<br /> : value_(value) {<br /> }<br /><br /> T& operator=(const T& value) {<br /> return value_;<br /> }<br /><br /> operator T& () {<br /> return value_;<br /> }<br /><br /> typedef T Type; <br /> T value_;<br />};<br /><br />template <int N><br />struct Tag;<br /></pre> Now we have a way to provide context other than with named variables. The Tag<> template just provides an easy way to define anonymous tags. <pre class="brush:cpp"><br />typedef NewType<float, Tag<0>> Position;<br />typedef NewType<float, Tag<1>> Velocity;<br /><br />std::tuple<Position, Velocity> mv(0.0f, 10.0f);<br />getType<Position>(mv) += getType<Velocity>(mv) * 100.0f;<br /></pre> We can also use named tags if there is a concern of clashing types later on: <pre class="brush:cpp"><br />struct PosTag;<br />struct VelTag;<br />typedef NewType<float, PosTag> Position;<br />typedef NewType<float, VelTag> Velocity;<br /><br />std::tuple<Position, Velocity> mv(0.0f, 10.0f);<br />getType<Position>(mv) += getType<Velocity>(mv) * 100.0f;<br /></pre> These type names can provide just as much context as variable name, but this obviously doesn't mean that every struct should be replaced with a tuple. Tuples really only have an advantage when building parameterized abstractions. In the next article, we will look at defining some key operations that can be used to create a basic type-safe relational algebra in C++11. Cody Griffinhttps://plus.google.com/116676205271053533228noreply@blogger.com1tag:blogger.com,1999:blog-1969424029831631509.post-53236906984274118732012-09-18T19:10:00.000-07:002012-09-25T21:07:19.785-07:00A Case for Tuples One of the more exciting new features in C++11 is the std::tuple template. A tuple is a struct pretending to be an array; the variable names are replaced with anonymous tuple indices. By replacing identifiers with more abstract indices, we can create a more abstract object. For example, cartesian coordinates (x, y) and complex coordinates (phase, magnitude) could both be represented by tuple<float, float>. Unlike an array, the elements can have different types. <br/><br/>Consider any C-style struct. The struct's member variables can be mapped directly to tuple elements. The first variable and index zero could be paired, followed by the second variable and index one. This would continue until the last member variable was paired with index N, where N is one less than the number of variables in the struct. With this mapping, it just so happens that the tuple’s elements are in the same order as the struct’s records, though this need not be the case. Regardless of the chosen mapping, a tuple abstracts away the names of the members, so instead of “position” and “velocity”, we have element one and element two. <br /><br/>To demonstrate a tuple’s abstraction potential, here is a simple example: <br /><br/><pre class="brush:cpp"><br />struct Move {<br /> float velocity_;<br /> float position_;<br /><br /> Move(float pos, float vel) <br /> : velocity_ (vel)<br /> , position_ (pos) {<br /> }<br /><br /> inline update(float dt) {<br /> position_ += velocity_ * dt; <br /> } <br />};<br /></pre>Let’s reimplement this class using a tuple instead of member variables: <br /><br/><pre class="brush:cpp"><br />template<typename T><br />struct Integrate {<br /> std::tuple<T, T> tuple_;<br /><br /> Integrate(T s, T ds) <br /> : tuple_ (ds, s) {<br /> }<br /><br /> inline update(float dt) {<br /> std::get<1>(tuple_) += std::get<0>(tuple_) * dt; <br /> } <br />};<br /></pre>We’ve successfully abstracted away all of the context about “moving”. Now this implementation can be used for other tasks such as calculating throughput for a network interface. Without this context, unfortunately, the abstraction is more difficult to use. A name is obviously better than an index, so it seems as if we’ve taken a step back. Lets instead focus on what we get by abstracting away this context. What if we wish to add another “order” to the integration? For example, we are developing a game and we want to allow acceleration of a game entity due to gravity. We can add another element to our tuple: <br /><br/><pre class="brush:cpp"><br />template<typename T> <br />struct Integration2 {<br /> std::tuple<T, T, T> tuple_;<br /><br /> Integration(T s, T ds, T ds2) <br /> : tuple_ (ds2, ds, s) {<br /> }<br /><br /> inline update(float dt) {<br /> std::get<1>(tuple_) += std::get<0>(tuple_) * dt;<br /> std::get<2>(tuple_) += std::get<1>(tuple_) * dt;<br /> }<br />};<br /></pre>Without the context, it is easy to see that this is a pattern that can be generalized. Why have two different definitions of this class when instead we could have a single template that can define any number of iterated integrals? <br /><pre class="brush:cpp"><br />// "Recursive" Case<br />template <int N><br />struct UpdateTupleImpl {<br /> template <typename...T><br /> static void update(std::tuple<T...>& tuple, float dt) {<br /> UpdateTupleImpl<N-1>::template update<T...>(tuple, dt);<br /> std::get<N+1>(tuple) += std::get<N>(tuple) * dt;<br /> }<br />};<br /><br />// Terminal Case<br />template <><br />struct UpdateTupleImpl<1> {<br /> template <typename...T><br /> static void update(std::tuple<T...>& tuple, float dt) {<br /> std::get<1>(tuple) += std::get<0>(tuple) * dt;<br /> } <br />};<br /><br />// Wrap it up in a helper - deduce template parameters <br />template <typename...T><br />inline void integrate(std::tuple<T...>& tuple, float dt) {<br /> UpdateTupleImpl<sizeof...(T)-1>::template update<T...>(tuple, dt);<br />}<br /><br />// Example<br />std::tuple<float, float, float> vel(1.0f, 5.0f, 10.0f);<br />integrate(vel, 100.0f);<br />integrate(vel, 100.0f);<br />float position = std::get<1>(vel);<br /></pre>Along with demonstrating C++’s ability to define powerful abstractions, this example also shows how ugly and verbose the language can be. Our template parameters can be any mix of types (we can have floats, doubles and ints mixed for example), but all the types must support the += operator and float multiplication. This example isn't supposed to be useful or used in practice; it is just a simple demonstration of abstraction using tuples. <br/><br/>In the example above, the “recursive” case isn’t actually recursive. Because it is the template parameter that varies, it is actually calling a completely different function with each iteration. We also know the number of iterations at compile-time, so the functions are inlined and the implementation is as efficient as the more concrete example. <br /><br/>We’ve already covered one of the major disadvantages of a tuple: the loss of context caused by abstracting away identifiers. Not only do we have to know what a tuple’s elements’ values represent whenever we use it, we must also know the values’ types and their positions within the tuple. Something very interesting happens if every element of the tuple has a different type. It becomes possible to unambiguously address a tuple element by its type alone, thus abstracting both identifiers and tuple element positions away. Its even possible for the type names to contain enough context to make up for losing the identifiers. <br /><br/><pre class="brush:cpp"><br />typedef Integration<Velocity, Position> Mover;<br />// initial velocity, and initial position<br />Mover mv({0.0f}, {100.0f});<br />update(mv, 100.0f);<br />update(mv, 100.0f);<br />float position = getType<Position>(mv.tuple_);<br /></pre>Unfortunately std::tuple does not have a uniqueness constraint. Even if it did, we’d have to define the unique types for the tuple. The <a href=http://blog.codygriffin.com/2012/09/improving-on-tuples.html>next article</a> in this series will address these issues with an alternative to std::tuple.Cody Griffinhttps://plus.google.com/116676205271053533228noreply@blogger.com4