Functional Programming in C++ with Javier Arias at Huawei

Security Level: Functional Programming in C++ Javier Arias www.huawei.com javier.arias1@huawei.com Huawei Confidential HUAWEI TECHNOLOGIES CO., LTD.

Introduction HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 2 Page 2

Introduction What is Functional Programming Getting started with FP Function Objects Creating new functions from old ones (partial, curried, composition and lifting) Purity: Avoiding mutable state Lazy evaluation Ranges Functional data structures Algebraic data types and pattern matching Monads Template metaprogramming Functional design for concurrent systems Testing and debugging Introduction HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 3 Page 3

1 What is Functional Programming FP was born in academia during the 1950s The most popular programming languages have started introducing features inspired by FP languages. FP is a style of programming in which the main program building blocks are functions as opposed to object and procedures What is Functional Programming HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 4 Page 4

1 What is Functional Programming Imperative HOW to do something You command the computer to do something by explicitly stating each step it needs to perform in order to calculate the result OO popular Imperative paradigm OO is based on creating abstractions for data, hide the internal representation inside an object and provide only a view via API Declarative Intent to do something You state what should be done, and the programming language has the task to figuring out how to do it. FP popular Declarative paradigm FP create abstraction on the functions. This lets you create more-complex structures than the underlying language provides FP makes code understandable by minimizing moving parts OO makes code understandable by encapsulating moving parts What is Functional Programming HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 5 Page 5

1 What is Functional Programming Thinking functionally Define Input and the output and which transformations you should perform to map one to the other. The Task do not care where the Input comes from. Split bigger programming problems into smaller. Each function is highly specialized to do one simple task without concerning itself about the rest. The independent tasks must able be to easily compose another task. What is Functional Programming HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 6 Page 6

1 What is Functional Programming Benefits of FP The code is much shorter and concise Using existing abstractions: It makes the code safer and shorter The abstractions have been tested, your code will be potentially less exposed to bugs Your program will improve over time even if you do not change a single line What is Functional Programming HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 7 Page 7

1 What is Functional Programming Is C++ an OO language? C++ was born as C with Classes Templates and STL, made C++ a multi-paradigm language. STL was created using the template system combined with a few FP techniques (by Alexander Stepanov, critic of OOP) STL vector template uses compile-time polymorphism, as opposed to the dynamic or runtime polymorphism provided by inheritance and virtual member functions The collection of STL algorithm C++11,C++14 and C++17 introduced syntactic sugar like auto and lambdas What is Functional Programming HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 8 Page 8

2 Getting started with FP Higher-order Functions Functions that take other functions as arguments or that return new functions Let you define abstract behaviors and complex control structures Most of the standard algorithms are implemented as loops is not a reason to use handwritten loops instead. In the same way, while, if, and others are implemented using gotos, but you do not use goto statement. Getting started with FP HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 9 Page 9

2 Getting started with FP Compose Functions filter: (collection<T>, (T bool)) collection <T> Filter construct takes a collection and a predicate function (T bool) as arguments and returns a collection of filtered items Transform: (collection<In>, (In Out)) collection<Out> Transform and Map do not need to contain items of the same type as the input collection You can compose filter and transform. Using the output of filter as input to transform, and transform returning just a member from the object. Getting started with FP HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 10 Page 10

2 Getting started with FP STL algorithms Many higher-order functions They provide efficient implementations of many common programming patterns Using them allows you to implement program logic with less code and fewer bugs It allows you to replace easily for another version Example std::accumulate: sum all items in a collection, std::reduce will do the same task parallelized. Getting started with FP HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 11 Page 11

2 Getting started with FP STL algorithms: std::accumulate f: (R, T) R This algorithm is an implementation of a general concept called folding or reduction This high-order function abstract the process of iterating over recursive structures (vectors, lists, trees and so on) and gradually build the result you need It passes the result to the function along with the next item collection. This is repeated until all items from the collection are processed and it returns the result of type R It can be used left or right fold way The addition can be replace with an arbitrary binary operation Getting started with FP HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 12 Page 12

2 Getting started with FP STL algorithms: std::find_if This algorithm is an implementation of trimming This algorithm searches the first item in the collection that satisfies the specified predicate and return the iterator pointing to the first element that satisfies the predicate STL algorithms: std::partition & std::stable_partition This algorithm takes a collection and a predicate, and returns a reordered collection with the items that satisfy the predicate are moved to the beginning and an iterator to the first element that does not satisfy the predicate Getting started with FP HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 13 Page 13

2 Getting started with FP STL algorithms: std::remove & std::remove_if This algorithm is an implementation of filtering This algorithm moves to the beginning all items from a collection items that satisfy a predicate and returns the iterator pointing to the first element that does not satisfy the predicate. It does not remove items. STL algorithms: std::copy_if This algorithm copy all the items that satisfy the predicate you are filtering on o new collection. Getting started with FP HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 14 Page 14

2 Getting started with FP Writing your own higher-order functions You can make function type the template parameter, the compiler will determine the exact type, they user can pass anything that can behave like a function Use STL algorithm whenever possible Recursion and tail-call optimization TCO In pure FP language, loops does not exist. Functions that iterate over collections are usually implemented using recursion GCC, Clang and MSVC support TCO, sometimes they optimize mutually recursive calls, and some functions that are not strictly tail-recursive, but close enough. With tail recursion, the recursive call is the last thing in the function. You need the intermediary results (an additional argument that you will pas from call to call). Folding is nothing more than a nicer way to write tail-recursive functions Getting started with FP HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 15 Page 15

3 Function Objects (FO) Function is a named group of statements that can be invoked from other parts or from the function itself. Anything that can be called like a function is a function object C++14 allows us to rely on the compiler to deduce the return type from the expression in the return statement This is useful when you are writing generic functions that forward the result of another function C++11 allows you to wraps a function in another function forwarding references. Function Objects HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 16 Page 16

3 Function Objects (FO) Function pointers: is a variable that stores the address of a function that can be called later through a that pointer Function pointers and function references are also FO Call operator overloading: C++ provides a way to create types that behave like functions. Create a class and overload the call operator. Function Objects HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 17 Page 17

3 Function Objects (FO) Creating Generic FO Instead of creating the class template Make the call operator a template member function The compiler will automatically deduce the type argument when invoking the call operator With the function template, you can create a function object that can work on a multitude of types Function Objects HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 18 Page 18

3 Function Objects (FO) Lambdas C++ lambdas are syntactic sugar for creating unnamed functions objects Under the hood C++ turn lambda New Class Lambdas allow you to create FO at the place where you want to use them Lambdas helps you keeping the code localized and not polluting the program namespace Syntax: Function Objects HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 19 Page 19

3 Function Objects (FO) Closures A Closure is an evaluation of a Lambda Under the hood C++ turn Closure an instance of the Lambda class, an object containing some state or environment along with code that should be executed on that state The name created by C++ is not accessible to the user Using lambda avoids boilerplate code and allow you to keep the logic of your code localized. Function Objects HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 20 Page 20

3 Function Objects (FO) Wrapping FO std::function can wrap any type of FO It allows you to use a function between separate compilation units It saves a FO as a member class that cannot be templated on the type of that FO It is a template on the signature of the FO The template argument specifies the return type of the function and its arguments Std::function introduces performance penalties because is based in virtual member function calls Function Objects HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 21 Page 21

4 Creating new functions from the old ones OO gives you the tools to combine and modify types FP lets you combine and specialise functions Partial function application Creating a new function object from an existing one by fixing one or more of its arguments Currying functions Unary functions Creating new functions from the old ones HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 22 Page 22

4 Creating new functions from the old ones Partial function application C++17 provides std::bind. You can bind function arguments in any order. With the placeholder you are allow to select which argument to bind, and to reverse arguments Std::bind makes the compiler hard to optimize It uses many complex template metaprogramming techniques Lambdas can be an alternative to std::bind More efficient but verbose syntax The unbound arguments lambda arguments The bound arguments the captured value The lambda body invokes the function You need all the arguments in advance Creating new functions from the old ones HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 23 Page 23

4 Creating new functions from the old ones Currying functions Unary functions chained functions instead of n-nary functions make_curried can transform any function into its curried version You do not need the number of arguments in advance Currying needs the arguments in order Creating new functions from the old ones HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 24 Page 24

4 Creating new functions from the old ones Function composition You pass result of one function return to another Function lifting Allows you to transform a give function into a similar function that is applicable in a broader context Instead of applying the algorithm to a string collection of strings Creating new functions from the old ones HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 25 Page 25

5 Purity: Avoiding mutable state The issue: Having several components in the software system be responsible for the same data, without knowing when another component is changing the data Pure function: it does not modify the state, always maps the same output to the same input. Only uses its arguments to calculate the result. How design software in a way that keeps mutations and side effects to a minimum Purity HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 26 Page 26

5 Purity: Avoiding mutable state Greek multiverse theory Return a new copy of the world instead of modifying the current one A clear separation between mutable and pure parts of the system Purity HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 27 Page 27

5 Purity: Avoiding mutable state Mutable and immutable state in a concurrent environment Mutex solve the problem with concurrency by removing concurrency Mutex are a low-level construct that is useful for implementing higher-level abstractions Const C++11 introduced const and constexpr Prevent data mutation You tell the compiler you do not want a variable to be mutable The compiler will give you an error if you try to change the variable Use const as much as you can Purity HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 28 Page 28

6 Lazy evaluation Postpone the work as much as possible and cache the result to do not calculate again C++ does not provide lazy evaluation out of the box, but provide functional tools to simulate it. You can create a class template containing: A FO that defines the computation std::once_flag to check if you can retrieve the computation from a mutable cache Lazy evaluation HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 29 Page 29

6 Lazy evaluation Examples of laziness as an optimization technique: Partial sorting collections, if you can only show k items from n Partial items views in the user interfaces Dynamic programming Expression templates and lazy string concatenation Instead of binary string concatenation You return a definition of the expression it represents You do not perform any concatenation until you ask for the result Lazy evaluation HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 30 Page 30

7 Ranges 2 iterators in the same structure: 1stpointing to the first element in a collection-like 2ndpointing to the element after the last one You can return a complete range as a result of a function and pass it directly to another function without creating local variables to hold intermediary results Range are evaluated lazily. You define the iterators, but it does not evaluate until needed Range do not own data, they cannot change it. Use actions if you need to modify data Ranges C++20 HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 31 Page 31

7 Ranges Filter function for ranges Instead of having filter to return a collection like std::vector It return a smart proxy iterator that point to the first element in the source collection that satisfies the given predicate, and the end iterator will be a proxy for the original collection end iterator Instead of privatizing data, it created a new view of existing data Transform function for ranges In a similar manner to Filter, it will return a view over the existing data, and it returns the result of the transformation function applied to the element from the source collection Ranges C++20 HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 32 Page 32

7 Ranges Delimited and Infinite ranges The end iterator is called sentinel It points to an element after the last element in the collection It is mainly used to test whether you have reached the end Algorithm generality: When you write an algorithm that works on infinite ranges, it will work on a range of any size Ranges C++20 HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 33 Page 33

8 Functional data structures Data structures that are efficient to copy Creating a modified copy of a data structure efficient too Checking which structures would be suited best for any particular case: Immutable linked list Adding/removing elements at the start/end to the linked list costs Immutable vector-like data structures Fast lookup Bitmapped vector trie (COW) Functional data structures HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 34 Page 34

9 Algebraic data types and pattern matching Handle of algebraic data types with pattern matching You can implement error handling having a type that contains either a value or an error Algebraic data types and pattern matching HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 35 Page 35

10 Monads Functor are a collection-like structures that know how to apply a transformation function on their contents A Class template F is a functor if it has a transform (or map) function defined on it The transform function takes An instance f of type F<T1> and a function t:T1 T2 Returns a value of type F<T2> std::optinal is one of the basic functors Functor has a serious limitation when composing Nested functors Monads HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 36 Page 36

10 Monads Monads know everything that functors do, but: They let you create monadic values from normal values The can flatten out nested monadic values A Monad is a functor that has an additional function defined: a function that removes one level of nesting join: M<M<T>> M<T> Instead of return ordinary values, it return monad (functor) instances Intuitively a Monad is something that you can construct and mbind to a function Mbind gets a function that maps values to instances of the monad Monads HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 37 Page 37

10 Monads Monads can be used: Failure handling Handling state with monads Concurrency and the continuation monad Monads HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 38 Page 38

11 Template metaprogramming Metaprogramming is compiler-time programming C++ templates is the main mechanism of metaprogramming decltype returns a constant reference to the type Void_t is a metafunction can be only evaluated only if the tupe you pass as its arguments are valid. Check type properties at compile-time. You can move many common software bugs to compile time Template metaprogramming HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 39 Page 39

12 Functional design for concurrent systems This chapter shows how to implement concurrency using the actor model with light processes and FP techniques to gain asynchronousity Functinal design for concurrent systems HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 40 Page 40

13 Testing and debugging This chapter shows how to implement testing using FP techniques to automatically generate test Testing and debugging HISILICON SEMICONDUCTOR HUAWEI TECHNOLOGIES CO., LTD. Page 41 Page 41

Thank you www.huawei.com