| Home | Libraries | People | FAQ | More

## Notes

### Recursive Inlined Functions

An interesting peculiarity of functions like `at` when applied to a Forward Sequence like `list` is that what could have been linear runtime complexity effectively becomes constant O(1) due to compiler optimization of C++ inlined functions, however deeply recursive (up to a certain compiler limit of course). Compile time complexity remains linear.

### Overloaded Functions

Associative sequences use function overloading to implement membership testing and type associated key lookup. This amounts to constant runtime and amortized constant compile time complexities. There is an overloaded function, `f(k)`, for each key type `k`. The compiler chooses the appropriate function given a key, `k`.

### Tag Dispatching

Tag dispatching is a generic programming technique for selecting template specializations. There are typically 3 components involved in the tag dispatching mechanism:

1. A type for which an appropriate template specialization is required
2. A metafunction that associates the type with a tag type
3. A template that is specialized for the tag type

For example, the fusion `result_of::begin` metafunction is implemented as follows:

    template <typename Sequence>
    struct begin
    {
        typedef typename
            result_of::begin_impl<typename traits::tag_of<Sequence>::type>::
            template apply<Sequence>::type
        type;
    };

In the case:

1. `Sequence` is the type for which a suitable implementation of `result_of::begin_impl` is required
2. `traits::tag_of` is the metafunction that associates `Sequence` with an appropriate tag
3. `result_of::begin_impl` is the template which is specialized to provide an implementation for each tag type

### Extensibility

Unlike MPL, there is no extensibe sequence concept in fusion. This does not mean that Fusion sequences are not extensible. In fact, all Fusion sequences are inherently extensible. It is just that the manner of sequence extension in Fusion is diferent from both STL and MPL on account of the lazy nature of fusion Algorithms. STL containers extend themselves in place though member functions such as `push_back` and `insert`. MPL sequences, on the other hand, are extended through "intrinsic" functions that actually return whole sequences. MPL is purely functional and can not have side effects. For example, MPL's `push_back` does not actually mutate an `mpl::vector`. It can't do that. Instead, it returns an extended `mpl::vector`.

Like MPL, Fusion too is purely functional and can not have side effects. With runtime efficiency in mind, Fusion sequences are extended through generic functions that return Views. Views are sequences that do not actually contain data, but instead impart an alternative presentation over the data from one or more underlying sequences. Views are proxies. They provide an efficient yet purely functional way to work on potentially expensive sequence operations. For example, given a `vector`, Fusion's `push_back` returns a `joint_view`, instead of an actual extended `vector`. A `joint_view` holds a reference to the original sequence plus the appended data --making it very cheap to pass around.

### Element Conversion

Functions that take in elemental values to form sequences (e.g. `make_list`) convert their arguments to something suitable to be stored as a sequence element. In general, the element types are stored as plain values. Example:

    make_list(1, 'x')

returns a `list``<int, char>`.

There are a few exceptions, however.

Arrays:

Array arguments are deduced to reference to const types. For example [14] :

    make_list("Donald", "Daisy")

creates a `list` of type

    list<const char (&)[7], const char (&)[6]>

Function pointers:

Function pointers are deduced to the plain non-reference type (i.e. to plain function pointer). Example:

    void f(int i);
      ...
    make_list(&f);

creates a `list` of type

    list<void (*)(int)>

### boost::ref

Fusion's generation functions (e.g. `make_list`) by default stores the element types as plain non-reference types. Example:

    void foo(const A& a, B& b) {
        ...
        make_list(a, b)

creates a `list` of type

    list<A, B>

Sometimes the plain non-reference type is not desired. You can use `boost::ref` and `boost::cref` to store references or const references (respectively) instead. The mechanism does not compromise const correctness since a const object wrapped with ref results in a tuple element with const reference type (see the fifth code line below). Examples:

For example:

    A a; B b; const A ca = a;
    make_list(cref(a), b);          // creates list<const A&, B>
    make_list(ref(a), b);           // creates list<A&, B>
    make_list(ref(a), cref(b));     // creates list<A&, const B&>
    make_list(cref(ca));            // creates list<const A&>
    make_list(ref(ca));             // creates list<const A&>

See Boost.Ref for details.

[14] Note that the type of a string literal is an array of const characters, not `const char*`. To get `make_list` to create a `list` with an element of a non-const array type one must use the `ref` wrapper (see `boost::ref`).