Forth Func Prog Sweden MeetUp 2020

Forth Func Prog Sweden MeetUp 2020

spe schme

Harald Achitz

Developer / Programmer

me

C++ for fun …​ ctional programmers …​ ???

Disclaimer

message

A intro and tutorial

nutshell1

A intro and tutorial

  • History of C++

  • The language and the standard library

  • Functional ideas and concepts in C++

  • Some code

  • Most important C++ basics (imho)

  • Notable literature

The history of C++

cpphist1

The history of C++

  • 1982 development starts

  • 1985 first commercial implementation

  • 1998 C++ iso standard, language and std library

  • …​ long break (minor update 03)

  • 2011 C++11

  • 2014 C++14

  • 2017 C++17

  • 2020 C++20

The future of C++

C++ is too complex. We need to make it smaller, simpler, and cleaner.

And please add these two features.

And whatever you do, don’t break my code!

— Stroustroup: p1962r0

The language and the standard library

C++,the language

Anybody who comes to you and says he has a perfect (programming) language is either naive or a salesman.

Clearly, I reject the view that there is one way that is right for everyone and for every problem.

— Stroustroup

C++,the language

A multi-paradigm programming language

C++,the language

A multi-paradigm programming language

Where imperative programming
meets object oriented programming
meets generic programming
meets functional programming

(…​ style)

C++,the language

A multi-paradigm programming language

It’s huge, where to start?

C++,the language

A multi-paradigm programming language

Within C++, there is a much smaller and clearer language struggling to get out

— Stroustroup

C++, The standard library

The STL

The Standard Template Library

(HP Software Technology Lab)

STL intro, October 1995

Alexander Stepanov
Silicon Graphics Inc.
2011 N. Shoreline Blvd.
Mt. View, CA 94043
stepanov@mti.sgi.com

Meng Lee
Hewlett-Packard Laboratories
1501 Page Mill Road
Palo Alto, CA 94304
lee@hpl.hp.com

The origins of the STL

alexSTLorigin

The origins of the STL

It is the result of over 15 years of research in generic programming that I’ve done in different places, with different collaborators, and in different programming languages.

— Stepanov; BYTE Magazine Oct.95

Basic structure

  • algorithm

  • container

  • iterator

  • function object

  • adaptor

Standard 1998

  • algorithm

  • container

  • iterator

  • function object

  • adaptor

  • io (stream)

  • utilities

  • memory allocation
    allocator

  • design documents

Standard today

  • algorithm (+ parallel)

  • container

  • iterator

  • function object

  • adaptor

  • .. everything plus

  • threading

  • filesystem

  • type traits (made public)

  • new vocabulary types

  • ranges

  • …​ plus plus plus

It’s huge, …​ and still growing

Where to start ?

std::algorithm

include algo

Motivating examples

  • Filter

  • Map

  • Reduce (fold)

Filter

std::vector<int> data = {1,2,3,4,5} ;
auto even = [](int v){ return (v & 1) == 0 ;};

std::vector<int> even_numbers ;

std::copy_if(data.begin(), data.end(),
    std::back_insert_iterator(even_numbers),
    even);
//even_numbers => {2,4}

Map

std::vector<int> data = {1,2,3,4,5} ;
auto scale = 1.4 ;

std::vector<double> scaled  ;

std::transform(data.begin(), data.end(),
               std::back_insert_iterator(scaled),
               [scale](int i){return i * scale;});
//scaled => {1.4, 2.8, 4.2, 5.6, 7.0}

Reduce

std::vector<int> data = {1,2,3,4,5} ;

auto v1 = std::accumulate(data.begin(), data.end(),
                         0, std::plus<>());

auto v2 = std::reduce(data.begin(), data.end(),
                      0, std::plus<>());

Transform && Reduce

std::vector<std::string> values{
  "Forth", "functional",
  "programming", "meetup"
} ;
auto char_cout = std::transform_reduce(
      std::execution::par,
      values.begin(), values.end(),
      0, std::plus<>{},
      [](const std::string& s) {
        return s.size();
      });
// char_cout == 32

Some observations

  • We saw dynamic memory management

  • We saw no pointers

  • We saw no new and no delete (or malloc/free)

  • We saw no raw loops

Some functional concepts

  • Higher order function

  • Immutability

  • Recursion

  • Function purity

  • Referential transparency

How do they map to C++, if they do at all

Higher order function

Higher order function

Yes!

C++ has higher order functions

Higher order function

std::vector<int> v;
// ...
auto negatives_to_zero = lift::if_then_else(
                lift::less_than(0),
                [](const auto&) { return 0;},
                [](const auto& x) { return x;});
std::vector<int> result;
std::transform(std::begin(v), std::end(v),
               std::back_inserter(result),
               negatives_to_zero);

Immutability

Immutability

C++ has const

It is not exactly the same.

C++ essentials

C++ essentials, #1

  • Value semantic

  • References are explicit and a type

  • Everything is mutable until declared const

Assignment creates a copy

std::vector<int> a {1,2,3} ;
auto b = a ;   // copy
b.push_back(4);

assert(a.size() == 3) ;
assert(b.size() == 4) ;

Value arguments are copies

// takes by value, copy construction
void f(std::vector<int> v) {
    // my personal,local mutable data
    b.push_back(4);
}

std::vector<int> a {1,2,3} ;
f(a);
assert(a.size() == 3) ;

C++ essentials, #2

  • Value semantic

  • References are explicit and a type

  • Everything is mutable until declared const

References are explicit and a type

std::vector<int> a {1,2,3} ;
auto& b = a ; // the '&' is important
b.push_back(4);
assert(a.size() == 4) ;
assert(b.size() == 4) ;

C++ essentials, #3

  • Value semantic

  • References are explicit and a type

  • Everything is mutable until declared const

const variables and references

const int num = 42 ; // can not be changed

void f(const std::vector<int>& v) {

    // v.push_back(4);  Compile time error

    // num = 32 ; Compile time error

}

Immutability

Yes, if you want, and you should

You can create immutable data structures

Recursion

Recursion

Yes, you can do recursion if you want

template<class FwdIt, class Comp = std::less<>>
void quick_sort(FwdIt first, FwdIt last,
                      Comp cmp = Comp{}){
    const auto N = std::distance(first, last);
    if (N <= 1) return;
    const auto pivot = *std::next(first, N / 2);
    const auto m1 = std::partition(
        first, last, [=](const auto& elem){
              return cmp(elem, pivot);
    });
    auto const m2 = std::partition(
        m1, last, [=](const auto& elem){
              return !cmp(pivot, elem);
    });
    quick_sort(first, m1, cmp);
    quick_sort(m2, last, cmp);
}

Recursion

Yes, you can do recursion if you want.

Tail call optimization not part of the standard

Recursion

There are loops (for, while, do/while)

Use algorithm!

Pure and RT functions

  • Function purity

  • Referential transparency

Pure and RT functions

  • Function purity

  • Referential transparency

Yes!

Pure and RT functions

Even some C compilers (gcc) taking advantage via function attributes.

int hash (const char *) __attribute__ ((pure));

int square (int) __attribute__ ((const));

This is C, it is up to the user to make guarantees!

Pure and RT functions

C++ hast constexpr.

constexpr int hash (const char *) ;

constexpr int square (int) ;

This is C++, the compiler make the guarantees!

Some functional concepts

Summary
  • Higher order function

  • Immutability

  • Recursion

  • Function purity

  • Referential transparency

But what about pointer!

fear

Pointers in lightspeed

  • A pointer is like a Maybe type.

  • A pointer is just some resource, like a file handler

Maybe …​

void doSomething(const Data* data) {
  if (data == nullptr) {
      // there is no data
  } else {
      // ... we have data
  }
}

Pointer as resources

Why pointers at all?

  • transferer ownership without copy

  • data that does not fit on the stack
    (size, or re-size)

  • OS resource, socket, file descriptor, ..

Resource management in C++

Resource management in C++

Scope

void doSomething(const Data* data) { // scope
  Foo f;
  if (what_ever) {  //scope
    Bar b ;
  } // ~b
  { // scope
    Baz b;
  } // ~b
} // ~f

Resource management in C++

Constructor and Destructor

Resource creation ⇒ Constructor

Resource destruction ⇒ Destructor

Resource management in C++

class Foo{

    // private resources

public:
    Foo(/* arguments* /) {
        /* create*/
    } ;

    ~Foo() { /*release*/} ;
};

Resource management in C++, RAII

Resource Acquisition Is Initialization

Bind the life cycle of a resource to the lifetime of an object.

For objects on the stack the } is the garbage collector ;-)

Helpers classes

std::unique_ptr

A smart pointer that owns a pointer and calls and action when it goes out of scope. There is only one owner. =⇒ This is the right default

std::shared_ptr

A smart pointer that owns a pointer and calls and action when it goes out of scope. Multiple copies can exist, when the last instance goes out of scope, the resource is freed.

std::unique_ptr

std::unique_ptr<Resource> build(int a, int b){
    auto r = std::make_unique<Resource>(a,b) ;
    // whatever with r
    return r ;
}

void fun() {
    auto res = build(1,2);
    res->do_job1() ;
    res->do_job2() ;
}

Today’s C++, no new and no delete

Summary

Pointers are nothing to fear

Templates

We have seen how to use templates

  • std::vector<int>

  • std::unique_ptr<Resource>

  • std::make_unique<Resource>(a,b)

That’s a good start

Ranges

C++ has now a range library

Better composable, can be lazy, hide iterator

Very new, C++20

Ranges

std::vector<int> ints{0,1,2,3,4,5};
auto even = [](int i){ return 0 == i % 2; };
auto square = [](int i) { return i * i; };

std::ranges::for_each( ints |
    std::views::filter(even) |
    std::views::drop(1) |
    std::views::transform(square) ,
    [](const auto& v) { std::cout << v; }) ;

How to continue

Books

IDE

IDE

Just write some C++

Thanks for listening!

theend
questions