// Juanpe Bolívar
// https://sinusoid.al

postmodern

immutable

data structures

Part I

The tragedy
of the
value based
architecture

mutability ⇒ ( pass by value ⇒ copying )

root cause cause problem


const auto v0 = vector<int>{};
const auto v1 = v0.push_back(15);
const auto v2 = v1.push_back(16);
const auto v3 = v2.set(0, 42);


assert(v2.size() == v0.size() + 2);
assert(v3[0] - v1[0] == 27);

immutable data structure

one with all methods
marked const

persistent data structure

old values are preserved

structural sharing

no copying
compact history
fast comparison

immer
a library of immutable data structures

https://sinusoid.es/immer

idiomatic
this is C++ not Haskell
performant
cache-efficient, benchmark-driven
customizable
stackable allocators, optional GC, thread-safety

Part II

in search of a magical vector


const auto v0 = list<char>{{'a'}};
const auto v1 = v0.push_front('b')
                  .push_front('c');
const auto v2 = v1.push_front('d');
const auto v3 = v1.push_front('e');

Chris Okasaki
Purely Functional Data Structures
https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

Ralf Hinze and Ross Paterson
Finger Trees: A General-purpose Data Structure
http://www.staff.city.ac.uk/~ross/papers/FingerTree.html

Phil Bagwell
Array Mapped Tries. 2000
RRB-Trees: Efficient Immutable Vectors. 2011
https://infoscience.epfl.ch/record/64394/files/triesearches.pdf https://infoscience.epfl.ch/record/169879/files/RMTrees.pdf

Rich Hickey
Value, Identity and State. 2009
https://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey

Radix Balanced Tree

$M=2^B$ $M=32$ $B=5$ $\left\lceil\log_{32}(2^{32})\right\rceil = 7$

Radix Balanced Search

v[17] → 01 00 01 v.set(17, 'R')

Relaxed Radix Balanced Tree

Operations

$$\text{effective}\ O(1)$$

Random access
Update
Push back
Slice right/right

$$O(\log(n))$$

Concat
Insert
Push front

Embedding
Radix balanced tree

$$M=2^B$$ $$M_l=2^{B_l}$$

$$ B_l^{\mathit{opt}}(B, T) = \left\lfloor \log_2\left( \frac{\mathit{sizeof}_* \times 2^B} {\mathit{sizeof}_T} \right) \right\rfloor $$


vector<int> myiota(vector<int> v, int first, int last)
{
    for (auto i = first; i < last; ++i)
        v = v.push_back(i);
    return v;
}


vector<int> myiota(vector<int> v, int first, int last)
{
    auto t = v.transient();
    for (auto i = first; i < last; ++i)
        t.push_back(i);
    return t.persistent();
}


vector<int> myiota(vector<int> v, int first, int last)
{
    auto t = v.transient();
    std::generate_n(std::back_inserter(t),
                    last - first,
                    [&] { return first++; });
    return t.persistent();
}

reference counting ➡ r-values are transients


vector<char> say_hi(vector<char> v)
{
    return v.push_back('h')        ⟵―― named value: v
    return move(v).push_back('h')  ⟵―― r-value value
            .push_back('i')        ⟵―― r-value value
            .push_back('!');       ⟵―― r-value value
}

and they compose ➡ say_hi(say_hi(...))


vector<int> myiota(vector<int> v, int first, int last)
{
    for (auto i = first; i < last; ++i)
        v = std::move(v).push_back(i);
    return v;
}

The Holy Grail

A Hash Array Mapped
Trie for C++

Phil Nash

https://www.youtube.com/watch?v=imrSQ82dYns

Is this fast?

Summing a $10^5$ element vector ($\mu s$)

Ten $10^4$ element concatenations ($\mu s$)

Building a $10^5$ element vector ($\mu s$)

Building a $10^5$ element transient vector ($\mu s$)

Mutating all $10^5$ element vector ($\mu s$)

Mutating all $10^5$ element transient vector ($\mu s$)

YES.

Interlude

Ewig
an example application

Part III

Redemption for the
value based architecture


application update(application state, action ev);

void run(const char* fname)
{
    auto term  = terminal{};
    auto state = application{load_buffer(fname), key_map_emacs};
    while (!state.done) {
        draw(state);
        auto act = term.next();
        state = update(state, act);
    }
}


using index = int;

struct coord
{
    index row = {};
    index col = {};
};

using line = immer::flex_vector<char>;
using text = immer::flex_vector<line>;

struct file
{
    immer::box<std::string> name;
    text content;
};

struct snapshot
{
    text content;
    coord cursor;
};


struct buffer
{
    file from;
    text content;
    coord cursor;
    coord scroll;
    std::optional<coord> selection_start;
    immer::vector<snapshot> history;
    std::optional<std::size_t> history_pos;
};

struct application
{
    buffer current;
    key_map keys;
    key_seq input;
    immer::vector<text> clipboard;
    immer::vector<message> messages;
};

struct action { key_code key; coord size; };

example

Undo


edit S1 ♦
edit S1   S2 ♦
edit S1   S2   S3 ♦
edit S1   S2   S3   S4 ♦
undo S1   S2   S3 ♦ S4   S3
undo S1   S2 ♦ S3   S4   S3   S2
edit S1   S2   S3   S4   S3   S2  S5 ♦

Emacs-style undo

Never loose work
Undo is undoable


buffer record(buffer before, buffer after)
{
    if (before.content != after.content) {
        after.history = after.history.push_back({before.content, before.cursor});
        if (before.history_pos == after.history_pos)
            after.history_pos = std::nullopt;
    }
    return after;
}

buffer undo(buffer buf)
{
    auto idx = buf.history_pos.value_or(buf.history.size());
    if (idx > 0) {
        auto restore = buf.history[--idx];
        buf.content = restore.content;
        buf.cursor = restore.cursor;
        buf.history_pos = idx;
    }
    return buf;
  }


buffer record(buffer before, buffer after)
{
    if (before.content != after.content) {
        after.history = after.history.push_back({before.content, before.cursor});
        if (before.history_pos == after.history_pos)
            after.history_pos = std::nullopt;
    }
    return after;
}

buffer undo(buffer buf)
{
    auto idx = buf.history_pos.value_or(buf.history.size());
    if (idx > 0) {
        auto restore = buf.history[--idx];
        buf.content = restore.content;
        buf.cursor = restore.cursor;
        buf.history_pos = idx;
    }
    return buf;
  }

Part IV

Embracing the value based architecture

1. Side effects


file save_file(const char* file_name, text content)
{
    auto file = std::ofstream{file_name};
    immer::for_each(content, [&] (auto l) {
        immer::for_each_chunk(l, [&] (auto b, auto e) {
            os.write(first, b - e);
        });
        os.put('\n');
    });
    return {file_name, content};
}


application update(application state, action act)
{
    ...
    if (act == [ save file ]) {
        state.current.from = save_file(
           state.current.from.name.get().c_str(),
           state.current.content);
        return state;
    }
    ...
}


file save_file(const char* file_name, text content)
{
    auto file = std::ofstream{file_name};
    immer::for_each(content, [&] (auto l) {
        immer::for_each_chunk(l, [&] (auto b, auto e) {
            os.write(first, b - e);
        });
        os.put('\n');
    });
    return {file_name, content};
}


application update(application state, action act)
{
    ...
    if (act == [ save file ]) {
        state.current.from = save_file(
           state.current.from.name.get().c_str(),
           state.current.content);
        return state;
    }
    ...
}

not a pure function!



std::pair<application, std::function<void(context)>>
application
update(application state, action act)
{
    ...

    if (act == [ save file ]) {
        state.current.from = save_file(
           state.current.from.name.get().c_str(),
           state.current.content);


        return {state, [=] (context ctx) {
            auto file = save_file(
               state.current.from.name.get().c_str(),
               state.current.content);
            ctx.dispatch(save_file_done_action{file});
       }};
    }
    else if (act == [ save file DONE ]) {
        state.current.from = act.file;
        return {state, [](auto){}};
    }

    ...
}

Solution

Do not perform side-effects
Do describe side-effects

2. Modularity

              
std::pair<application, std::function<void(context)>>
update(application state, action act)
{
    if (act == [ save file ]) {
        return {state, [=] (context ctx) {
            auto file = save_file(
               state.current.from.name.get().c_str(),
               state.current.content);
            ctx.dispatch(save_file_done_action{file});
       }};
    }
    else if (act == [ save file OK ]) {
        state.current.from = act.result;
        return {state, [](auto){}};
    }








    ...
}

              
std::pair<application, std::function<void(context)>>
update(application state, action act)
{
    return std::apply(boost::hof::match(
        [&] (save_file_action) {
            return {state, [=] (context ctx) {
                auto file = save_file(
                   state.current.from.name.get().c_str(),
                   state.current.content);
                ctx.dispatch(save_file_done_action{file});
            }};
        },
        [&] (save_file_done_action act) {
            state.current.from = act.result;
            return {state, [](auto){}};
        },
        [&] (terminal_action act) {
            if (act == [save key])
                return {state, [] (context ctx) {
                    ctx.dispatch(save_file_action{});
                }};
        },
        ...
    ), act);
}

              
//
//     How to deal with multiple action types?
//

struct action { key_code key; coord size; };

              
//
//     How to compose model and action types?
//

struct terminal_action { key_code key; coord size; };
struct save_file_action {};
struct save_file_done_action { file result; };
...

using action = std::variant<
    terminal_action,
    save_file_action,
    save_file_done_action,
    ...
>;

              
std::pair<application, std::function<void(context)>>
update(application state, action act)
{
    return std::apply(boost::hof::match(
        [&] (save_file_action) {
            return {state, [=] (context ctx) {
                auto file = save_file(
                   state.current.from.name.get().c_str(),
                   state.current.content);
                ctx.dispatch(save_file_done_action{file});
            }};
        },
        [&] (save_file_done_action act) {
            state.current.from = act.result;
            return {state, [](auto){}};
        },
        [&] (terminal_action act) {
            if (act == [save key])
                return {state, [] (context ctx) {
                    ctx.dispatch(save_file_action{});
                }};
        },
        ...
    ), act);
}

              
std::pair<buffer, std::function<void(context)>>
update(buffer state, buffer_action act) {
    return std::apply(boost::hof::match(
        [&] (save_file_action) { ... },
        [&] (save_file_done_action act) { ...},
    ), act);
}

std::pair<application, std::function<void(context)>>
update(application state, action act) {
    return std::apply(boost::hof::match(
        [&] (buffer_action act) {
            auto [buf, eff] = update(state.current, act);
            state.current = buf;
            return {state, eff};
        },
        [&] (terminal_action act) {
            if (act == [save key])
                return {state, [] (context ctx) {
                    ctx.dispatch(save_file_action{});
                }};
        },
        ...
    ), act);
}

              
struct terminal_action { key_code key; coord size; };

struct save_file_action {};
struct save_file_done_action { file result; };
using buffer_action = std::variant<
    save_file_action,
    save_file_done_action,
    ...
>;

using action = std::variant<
    terminal_action,
    buffer_action,
    ...
>;

              
void run(const char* fname)
{
    auto serv = boost::asio::io_service{};
    auto term = terminal{serv};
    auto st   = lager::make_store<action>(
        application{}, update, draw,
        lager::with_boost_asio_event_loop{serv});
    term.start([&] (auto act) { st.dispatch (act); });
    st.dispatch(load_file{fname});
    serv.run();
}

              
void run(const char* fname)
{
    auto term  = terminal{};
    auto state = application{load_buffer(fname), ...};
    while (!state.done) {
        draw(state);
        auto act = term.next();
        state = update(state, act);
    }
}

              
void run(const char* fname)
{
    auto serv = boost::asio::io_service{};
    auto term = terminal{serv};
    auto st   = lager::make_store<action>(
        application{}, update, draw,
        lager::with_boost_asio_event_loop{serv});
    term.start([&] (auto act) { st.dispatch (act); });
    st.dispatch(load_file{fname});
    serv.run();
}

Lager

Experimental "Redux for C++"
github.com/arximboldi/lager

Value-based architecture
Effects
Concurrency
Time-travelling

3. Time travel

The most valuable values

Juanpe Bolívar

https://www.youtube.com/watch?v=_oBx_NbLghY

4. Concurrency


file save_file(const char* file_name, text content)
{
    auto file = std::ofstream{file_name};
    immer::for_each(content, [&] (auto l) {
        immer::for_each_chunk(l, [&] (auto first, auto last) {
            os.write(first, last - first);
        });
        os.put('\n');
    });
    return {file_name, content};
}


void save_file(const char* file_name, text content, context ctx)
{
    auto file = std::ofstream{file_name};
    immer::for_each(content, [&] (auto l) {
        immer::for_each_chunk(l, [&] (auto first, auto last) {
            os.write(first, last - first);
        });
        os.put('\n');
    });
    ctx.dispatch(save_fail_action{file_name});
}


void save_file(const char* file_name, text content, context ctx)
{
    try {
        auto file = std::ofstream{file_name};
        os.exceptions(std::ifstream::badbit);
        immer::for_each(content, [&] (auto l) {
            immer::for_each_chunk(l, [&] (auto first, auto last) {
                os.write(first, last - first);
            });
            os.put('\n');
        });
        ctx.dispatch(save_done_action{file_name, content});
    } catch (const std::exception& err) {
        ctx.dispatch(save_fail_action{file_name, content});
    }
}


void save_file(const char* file_name, text content, context ctx)
{
    std::async([=] {
        try {
            auto file = std::ofstream{file_name};
            os.exceptions(std::ifstream::badbit);
            immer::for_each(content, [&] (auto l) {
                immer::for_each_chunk(l, [&] (auto first, auto last) {
                    os.write(first, last - first);
                });
                os.put('\n');
            });
            ctx.dispatch(save_done_action{file_name, content});
        } catch (const std::exception& err) {
            ctx.dispatch(save_done_action{file_name, content});
        }
    });
}


void save_file(const char* file_name, text content, context ctx)
{
    std::async([=] {
        try {
            auto file = std::ofstream{file_name};
            os.exceptions(std::ifstream::badbit);
            auto line = std::size_t{0};
            immer::for_each(content, [&] (auto l) {
                immer::for_each_chunk(l, [&] (auto first, auto last) {
                    os.write(first, last - first);
                });
                os.put('\n');
                if (++ line % 10000 == 0)
                   ctx.dispatch(save_progress_action{file_name, line});
            });
            ctx.dispatch(save_done_action{file_name, content});
        } catch (const std::exception& err) {
            ctx.dispatch(save_done_action{file_name, content});
        }
    });
}


void save_file(const char* file_name, text content, context ctx)
{
    ctx.async([=] {
        try {
            auto file = std::ofstream{file_name};
            os.exceptions(std::ifstream::badbit);
            auto line = std::size_t{0};
            immer::for_each(content, [&] (auto l) {
                immer::for_each_chunk(l, [&] (auto first, auto last) {
                    os.write(first, last - first);
                });
                os.put('\n');
                if (++ line % 10000 == 0)
                   ctx.dispatch(save_progress_action{file_name, line});
            });
            ctx.dispatch(save_done_action{file_name, content});
        } catch (const std::exception& err) {
            ctx.dispatch(save_done_action{file_name, content});
        }
    });
}