Mastering Functional C++


The Presentation inside:

Slide 0

Functional C++ @KevlinHenney


Slide 1


Slide 2


Slide 3

https://twitter.com/mfeathers/status/29581296216


Slide 4


Slide 5

recursion idempotence mathematics unification pattern matching higher-order functions monads pure functions functional immutability programming declarative first-class functions lambdas currying non-strict evaluation statelessness lists


Slide 6

class heating_system { public: void turn_on(); void turn_off(); ... };


Slide 7

class timer { public: timer(time_of_day when, command & what); void run(); void cancel(); ... }; class command { public: virtual void execute() = 0; ... };


Slide 8

class turn_on : public command { public: explicit turn_on(heating_system & heating) : heating(heating) { } void execute() override { heating.turn_on(); } private: heating_system & heating; }; class turn_off : public command { public: explicit turn_off(heating_system & heating) : heating(heating)


Slide 9

class turn_on : public command { public: explicit turn_on(heating_system & heating) : heating(heating) { } void execute() override { heating.turn_on(); } private: heating_system & heating; }; class turn_off : public command { public: explicit turn_off(heating_system & heating) : heating(heating) { } void execute() override { heating.turn_off(); } private: heating_system & heating; };


Slide 10

class timer { public: timer( time_of_day when, void execute(void * context), void * context); void run(); void cancel(); ... };


Slide 11

void turn_on(void * context) { static_cast<heating_system *>(context)->turn_on(); } void turn_off(void * context) { static_cast<heating_system *>(context)->turn_off(); }


Slide 12

class timer { public: timer(time_of_day when, function<void()> what); void run(); void cancel(); ... };


Slide 13

timer on( time_on, std::bind(&heating_system::turn_on, &heating)); timer off( time_off, std::bind(&heating_system::turn_off, &heating));


Slide 14

timer on(time_on, [&] { heating.turn_on(); }); timer off(time_off, [&] { heating.turn_off(); });


Slide 15

William Cook, "On Understanding Data Abstraction, Revisited"


Slide 16

[](){}


Slide 17

[](){}()


Slide 18


Slide 19


Slide 20

paraskevidekatriaphobia, noun  The superstitious fear of Friday 13th.  Contrary to popular myth, this superstition is relatively recent (19th century) and did not originate during or before the medieval times.  Paraskevidekatriaphobia (or friggatriskaidekaphobia) also reflects a particularly egocentric attributional bias: the universe is prepared to rearrange causality and probability around the believer based on an arbitrary and changeable calendar system, in a way that is sensitive to geography, culture and time zone. WordFriday.com


Slide 21

struct tm next_friday_13th(const struct tm * after) { struct tm next = *after; enum { daily_secs = 24 * 60 * 60 }; time_t seconds = mktime(&next) + (next.tm_mday == 13 ? daily_secs : 0); do { seconds += daily_secs; next = *localtime(&seconds); } while(next.tm_mday != 13 || next.tm_wday != 5); return next; }


Slide 22

std::find_if( ++begin, day_iterator(), [](const std::tm & day) { return day.tm_mday == 13 && day.tm_wday == 5; });


Slide 23

class day_iterator : public std::iterator<...> { public: day_iterator() ... explicit day_iterator(const std::tm & start) ... const std::tm & operator*() const { return day; } const std::tm * operator->() const { return &day; } day_iterator & operator++() { std::time_t seconds = std::mktime(&day) + 24 * 60 * 60; day = *std::localtime(&seconds); return *this; } day_iterator operator++(int) ... ... };


Slide 24


Slide 25


Slide 26

http://www.adampetersen.se/articles/fizzbuzz.htm


Slide 27

http://www.adampetersen.se/articles/fizzbuzz.htm


Slide 28

enum fizzbuzzed { fizz = -2, buzz = -1, fizzbuzz = 0, first = 1, last = 100 }; constexpr fizzbuzzed fizzbuzz_of(int n) { return n % 3 == 0 && n % 5 == 0 ? fizzbuzz : n % 3 == 0 ? fizz : n % 5 == 0 ? buzz : fizzbuzzed(n); }


Slide 29

When it is not necessary to change, it is necessary not to change. Lucius Cary


Slide 30

const


Slide 31

&


Slide 32

&&


Slide 33


Slide 34

Immutable Value References to value objects are commonly distributed and stored in fields. However, state changes to a value caused by one object can have unexpected and unwanted sideeffects for any other object sharing the same value instance. Copying the value can reduce the synchronization overhead, but can also incur object creation overhead. Therefore: Define a value object type whose instances are immutable. The internal state of a value object is set at construction and no subsequent modifications are allowed.


Slide 35

Copied Value Value objects are commonly distributed and stored in fields. If value objects are shared between threads, however, state changes caused by one object to a value can have unexpected and unwanted side effects for any other object sharing the same value instance. In a multithreaded environment shared state must be synchronized between threads, but this introduces costly overhead for frequent access. Therefore: Define a value object type whose instances are copyable. When a value is used in communication with another thread, ensure that the value is copied.


Slide 36

class date { public: date(int year, int month, int day_in_month); date(const date &); date & operator=(const date &); ... int get_year() const; int get_month() const; int get_day_in_month() const; ... void set_year(int); void set_month(int); void set_day_in_month(int); ... };


Slide 37

Just because you have a getter, doesn't mean you should have a matching setter.


Slide 38

class date { public: date(int year, int month, int day_in_month); date(const date &); date & operator=(const date &); ... int get_year() const; int get_month() const; int get_day_in_month() const; ... void set(int year, int month, int day_in_month); ... }; today.set(2015, 9, 14);


Slide 39

class date { public: date(int year, int month, int day_in_month); date(const date &); date & operator=(const date &); ... int get_year() const; int get_month() const; int get_day_in_month() const; ... }; today = date(2015, 9, 14);


Slide 40

class date { public: date(int year, int month, int day_in_month); date(const date &); date & operator=(const date &); ... int get_year() const; int get_month() const; int get_day_in_month() const; ... }; today = date { 2015, 9, 14 };


Slide 41

class date { public: date(int year, int month, int day_in_month); date(const date &); date & operator=(const date &); ... int get_year() const; int get_month() const; int get_day_in_month() const; ... }; today = { 2015, 9, 14 };


Slide 42

"Get something" is an imperative with an expected side effect.


Slide 43

class date { public: date(int year, int month, int day_in_month); date(const date &); date & operator=(const date &); ... int get_year() const; int get_month() const; int get_day_in_month() const; ... };


Slide 44

class date { public: date(int year, int month, int day_in_month); date(const date &); date & operator=(const date &); ... int year() const; int month() const; int day_in_month() const; ... };


Slide 45

Conversions Overloading Derivation Genericity Mutability


Slide 46


Slide 47

Referential transparency is a very desirable property: it implies that functions consistently yield the same results given the same input, irrespective of where and when they are invoked. That is, function evaluation depends less—ideally, not at all—on the side effects of mutable state. Edward Garson "Apply Functional Programming Principles"


Slide 48

Asking a question should not change the answer. Bertrand Meyer


Slide 49

Asking a question should not change the answer, and nor should asking it twice!


Slide 50

A book is simply the container of an idea like a bottle; what is inside the book is what matters. Angela Carter


Slide 51

// "FTL" (Functional Template Library :->) // container style template<typename ValueType> class container { public: typedef const ValueType value_type; typedef ... iterator; ... bool empty() const; std::size_t size() const; iterator begin() const; iterator end() const; ... container & operator=(const container &); ... };


Slide 52

template<typename ValueType> set<int> c { 2, 9, 9, 7, 9, 2, 4, 5, 8 }; class set { public: typedef const ValueType * iterator; ... set(std::initializer_list<ValueType> values); ... bool empty() const; std::size_t size() const; iterator begin() const; iterator end() const; iterator find(const ValueType &) const; std::size_t count(const ValueType &) const; iterator lower_bound(const ValueType &) const; iterator upper_bound(const ValueType &) const; pair<iterator, iterator> equal_range(const ValueType &) const; ... private: ValueType * members; std::size_t cardinality; };


Slide 53

template<typename ValueType> array<int> c { 2, 9, 9, 7, 9, 2, 4, 5, 8 }; class array { public: typedef const ValueType * iterator; ... array(std::initializer_list<ValueType> values); ... bool empty() const; std::size_t size() const; iterator begin() const; iterator end() const; const ValueType & operator[](std::size_t) const; const ValueType & front() const; const ValueType & back() const; const ValueType * data() const; ... private: ValueType * elements; std::size_t length; };


Slide 54

In computing, a persistent data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure. (A persistent data structure is not a data structure committed to persistent storage, such as a disk; this is a different and unrelated sense of the word "persistent.") http://en.wikipedia.org/wiki/Persistent_data_structure


Slide 55

template<typename ValueType> class vector { public: typedef const ValueType * iterator; ... bool empty() const; std::size_t size() const; iterator begin() const; iterator end() const; const const const const ValueType ValueType ValueType ValueType & & & * operator[](std::size_t) const; front() const; back() const; data() const; vector pop_front() const; vector pop_back() const; ... private: ValueType * anchor; iterator from, until; };


Slide 56

template<typename ValueType> class vector { public: typedef const ValueType * iterator; ... bool empty() const; std::size_t size() const; iterator begin() const; iterator end() const; const const const const ValueType ValueType ValueType ValueType & & & * operator[](std::size_t) const; front() const; back() const; data() const; vector pop_front() const; vector pop_back() const; ... private: ValueType * anchor; iterator from, until; };


Slide 57

template<typename ValueType> class vector { public: typedef const ValueType * iterator; ... bool empty() const; std::size_t size() const; iterator begin() const; iterator end() const; const const const const ValueType ValueType ValueType ValueType & & & * operator[](std::size_t) const; front() const; back() const; data() const; vector popped_front() const; vector popped_back() const; ... private: ValueType * anchor; iterator from, until; };


Slide 58

template<typename ValueType> class vector { public: typedef const ValueType * iterator; ... bool empty() const; std::size_t size() const; iterator begin() const; iterator end() const; const const const const ValueType ValueType ValueType ValueType & & & * operator[](std::size_t) const; front() const; back() const; data() const; vector popped_front() const; vector popped_back() const; ... private: ValueType * anchor; iterator from, until; };


Slide 59


Slide 60

I still have a deep fondness for the Lisp model. It is simple, elegant, and something with which all developers should have an infatuation at least once in their programming life. Kevlin Henney "A Fair Share (Part I)", CUJ C++ Experts Forum, October 2002


Slide 61

lispt


Slide 62

template<typename ValueType> class list { public: class iterator; ... std::size_t size() const; iterator begin() const; iterator end() const; const ValueType & front() const; list popped_front() const; list pushed_front() const; ... private: struct link { link(const ValueType & value, link * next); ValueType value; link * next; }; link * head; std::size_t length; };


Slide 63

Hamlet: Yea, from the table of my memory I'll wipe away all trivial fond records. William Shakespeare The Tragedy of Hamlet [Act I, Scene 5]


Slide 64

Garbage collection [...] is optional in C++; that is, a garbage collector is not a compulsory part of an implementation. Bjarne Stroustrup http://stroustrup.com/C++11FAQ.html


Slide 65

assert( std::get_pointer_safety() == std::pointer_safety::strict);


Slide 66

Ophelia: 'Tis in my memory locked, and you yourself shall keep the key of it. William Shakespeare The Tragedy of Hamlet [Act I, Scene 3]


Slide 67

A use-counted class is more complicated than a non-usecounted equivalent, and all of this horsing around with use counts takes a significant amount of processing time. Robert Murray C++ Strategies and Tactics


Slide 68

template<typename ValueType> class vector { public: typedef const ValueType * iterator; ... bool empty() const; std::size_t size() const; iterator begin() const; iterator end() const; const const const const ValueType ValueType ValueType ValueType & & & * operator[](std::size_t) const; front() const; back() const; data() const; vector popped_front() const; vector popped_back() const; ... private: std::shared_ptr<ValueType> anchor; iterator from, until; }; Uses std::default_delete<ValueType[]>, but cannot be initialised from std::make_shared


Slide 69

template<typename ValueType> class list { public: class iterator; ... std::size_t size() const; iterator begin() const; iterator end() const; const ValueType & front() const; list popped_front() const; list pushed_front() const; ... private: struct link { link(const ValueType & value, std::shared_ptr<link> next); ValueType value; std::shared_ptr<link> next; }; std::shared_ptr<link> head; std::size_t length; };


Slide 70

{ list<Anything> chain; std::fill_n( std::front_inserter(chain), how_many, something); } On destruction, deletion of links is recursive through each link, causing the stack to blow up for surprisingly small values of how_many.


Slide 71


Slide 72

Concurrency


Slide 73

Concurrency Threads


Slide 74

Concurrency Threads Locks


Slide 75

All computers wait at the same speed.


Slide 76

Some people, when confronted with a problem, think, "I know, I'll use threads," and then two they hav erpoblesms. Ned Batchelder https://twitter.com/#!/nedbat/status/194873829825327104


Slide 77

Shared memory is like a canvas where threads collaborate in painting images, except that they stand on the opposite sides of the canvas and use guns rather than brushes. The only way they can avoid killing each other is if they shout "duck!" before opening fire. Bartosz Milewski "Functional Data Structures and Concurrency in C++" http://bartoszmilewski.com/2013/12/10/functional-data-structures-and-concurrency-in-c/


Slide 78

Mutable Unshared mutable data needs no synchronisation Shared mutable data needs synchronisation Unshared Shared Unshared immutable data needs no synchronisation Shared immutable data needs no synchronisation Immutable


Slide 79

The Synchronisation Quadrant Mutable Unshared mutable data needs no synchronisation Shared mutable data needs synchronisation Unshared Shared Unshared immutable data needs no synchronisation Shared immutable data needs no synchronisation Immutable


Slide 80


Slide 81

std::string fizzbuzz(int n) { return n % 3 == 0 && n % 5 == 0 ? "FizzBuzz" : n % 3 == 0 ? "Fizz" : n % 5 == 0 ? "Buzz" : std::to_string(n); }


Slide 82

void fizzbuzzer( channel<int> & receive, channel<std::string> & send) { for(int n; receive >> n;) send << fizzbuzz(n); }


Slide 83

int main() { channel<int> out; channel<std::string> back; std::thread fizzbuzzing(fizzbuzzer, out, back) for(int n = 1; n <= 100; ++n) { out << n; std::string result; back >> result; std::cout << result << "\n"; } ... }


Slide 84


Slide 85

Message 3 Message 1 Sender Receiver A Receiver B In response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and determine how to respond to the next message received. http://en.wikipedia.org/wiki/Actor_model


Slide 86

Multithreading is just one damn thing after, before, or simultaneous with another. Andrei Alexandrescu


Slide 87

Actor-based concurrency is just one damn message after another.


Slide 88

Go with the flow. Queens of the Stone Age


Slide 89


×

HTML:





Ссылка: