// 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


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.

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});
        }
    });
}
          

Conclusion

github.com/arximboldi/immer
github.com/arximboldi/ewig
github.com/arximboldi/lager

@sinusoidalen
https://sinusoid.al
thanks.

Afterword

programming and

programming:

the last 4000 years

Juanpe Bolívar
https://sinusoid.al




github.com/arximboldi/immer
github.com/arximboldi/ewig
github.com/arximboldi/lager

@sinusoidalen
https://sinusoid.al
thanks.