Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Functional Programming in Python

suci
October 17, 2018

Functional Programming in Python

Python is not a (pure) functional programming language, but a multi-paradigm language. Its features are suitable for implementing programs in a functional style.

The sharing at PYHUG will start with the concepts of functional programming. Then, you will know at functional language features in Python such as first-class functions, lambda expressions and so on. In addition, relevant library modules such as itertools and functools will be briefly mentioned.

What you may get
* You will know what is functional programming
* Get the summary from the official documentation, Functional Programming HOWTO

suci

October 17, 2018
Tweet

More Decks by suci

Other Decks in Programming

Transcript

  1. About me 2 Data Engineer in a manufacturing company Working

    with • data and people Focus on • Streaming process • IoT applications • Data visualization • Engineer culture Shuhsi Lin Lurking in PyHug, Taipei.py and various Meetup sucitw gmail.com
  2. Agenda 1. Basic Concept of Functional Programming ∙ Procedural vs

    Functional 2. Lambda Expression/ Nameless Function 3. First-Class/High-Order Functions 4. Common Patterns ∙ Partial Function Application ∙ Currying 5. More functional thinking 6. More functional programming in Python 3
  3. 4 What we will focused 1. What is Functional Programming

    2. Some common patterns 3. Writing code with a better functional style 4. A path to dive into functional programming in python
  4. “ 5 What will be not focused 1. Compare with

    other programming languages 2. OO in Python 3. Combine and switch back and forth with OO and procedural style
  5. Common Programming Paradigm • Imperative ◦ Tell the “machine” how

    to do something, and as a result what you want to happen will happen (changes in state.) ◦ Use statements that change a program state ▪ Procedural (Languages with functions, C, Pascal, and even Unix shells) ▪ Object-oriented (Java, smalltalk) • Declarative ◦ Tell the “machine”1 what you would like to happen, and let the computer figure out how to do it. ▪ Functional: Evaluation of mathematical functions and avoids state and mutable data (Haskell, Scheme, OCaml) ▪ Logic (Prolog, Clojure core.logic) ▪ Mathematical 8 https://en.wikipedia.org/wiki/Programming_paradigm
  6. 9 Photo by Mitch Lensink on Unsplash Programming Paradigms are

    similar to painting or music styles Python are multi-paradigm
  7. Functional Programming • Has a long story • Lisp 1958

    • Renaissance: F#, Haskell, Erlang • Functions as the fundamental building blocks for any program • Focus on computing results rather than on performing actions • Describe what is to be done and not on how it is to be done • Leads to concise and safe code (less OffByOne mistakes) 11
  8. Features of Functional Programming • 不變性 • 惰性求值 • 高階函數

    • 無副作用 • 一切皆函數 12 • Immutability ◦ Immutable data structures ◦ Preserve state in functions (Avoid state) • Lazy evaluation • First-class/Higher-order functions • Pure functions without side effects ▪ Every function’s output must only depend on its input ▪ Don’t change anything outside of the function • Everything is a function • Recursion instead of loops/iteration (Avoiding Flow Control)
  9. Hmm… Why Should I care • Better understanding other’s codes

    • Big Data and Distributed Computing ◦ Race condition (Multiple threads, Concurrency) ◦ MapReduce ◦ Spark • Deep Learning ◦ "weight tying" - using multiple copies of a neuron in different places is the neural network equivalent of using functions
  10. Advantages of Functional Programming • More modular and in smaller

    building blocks • Better testable (same parameters return same result) • Focus on algorithms • Robust (Absence of side effects) ◦ Referential Transparent (Stateless and no side effect) ◦ Conceptional fit with parallel/ concurrent programming ◦ Can be tested separately (isolation) • Live updates-Install new release while running 15 • Formal provability • Modularity • Composability • Ease of debugging and testing https://xkcd.com/1312/
  11. Python’s Functional Features • Pure functions (sort of) • Recursion-

    try to avoid, recursion limit has a reason • Closures- hold state in functions • Functions as object and decorators • Immutable data types • Lazy evaluation -generators • List (dictionary, set) comprehensions • Functools, itertools, lambda, map, filter 16
  12. Pro and Con for FP in Python 17 Pro •

    Functions as first-class citizens • lambda • Standard library: map/filter/reduce, itertools, operator • Generators can be used for lazy-evaluation (in some cases) Con • Impossible to separate pure / non-pure • Mutable variables • Costly mem copy operations • Imperative style for cycles • No optimization for tail recursion • No pattern matching syntax • Classes-based only type system • No functions overloading mechanism • Functions composition is not implemented in stdlib • Imperative errors handling based on exceptions Python does not promote functional programming even though it works fairly well.
  13. Message from our BDFL 18 http://python-history.blogspot.in/2009/04/origins-of-pythons-functional-features.html Origins of Python's "Functional"

    Features I have never considered Python to be heavily influenced by functional languages, no matter what people say or think. I was much more familiar with imperative languages such as C and Algol 68 and although I had made functions first-class objects, I didn't view Python as a functional programming language. However, earlier on, it was clear that users wanted to do much more with lists and functions. …. It is also worth nothing that even though I didn't envision Python as a functional language, the introduction of closures has been useful in the development of many other advanced programming features. For example, certain aspects of new-style classes, decorators, and other modern features rely upon this capability. Lastly, even though a number of functional programming features have been introduced over the years, Python still lacks certain features found in “real” functional programming languages. …. Guido van Rossum
  14. • Line-by Line • Heavy use of Statements • Also

    heavy use of Expressions • Long functions 20 Procedural Functional • Little use of Statements • Heavy use of Expressions • Single-line functions
  15. 21 $ ./program1 $ ./program2 --param1=1 $ ./program3 "Procedural terminal"

    "Functional terminal" $ ./program1 | ./program2 --param1=1 | ./program3 Procedural and Functional Style only one expression
  16. 22 Procedural and Functional Style A procedural approach! • Functions

    generally consist of multiple statements ◦ Assignments ◦ If-statements ◦ While loops ◦ Etc. Imperative style = actions that change state from initial state to result expr, res = "28+32+++32++39", 0 for t in expr.split("+"): if t != "": res += int(t) print(res)
  17. A functional approach! • Functions consist of only one expression

    • How can we validate input? (One of the many things we will learn later!) 23 # Functional style from operator import add expr = "28+32+++32++39" print(reduce(add, map(int, filter(bool, expr.split("+"))))) Functional style = apply transformation (and compositions) Procedural and Functional Style
  18. What is a State • State (State and statelessness) •

    Side effects ◦ Global variables ◦ Objects with properties ◦ Will influence how functions work • Referential transparency (引用透明) ◦ An expression, in a program, may be replaced by its value (or anything having the same value) without changing the result of the program 25 https://stackoverflow.com/questions/210835/what-is-referential-transparency light.ison = true light.ison = false State change }
  19. Stateless Functions • Always return the same result if given

    the same arguments • Regardless of the program's state 26 You know what you get Functions without side effects Leave the state alone • Do not change the program’s state • Related to but distinct from statelessness Demo
  20. Purity • Functions without “side effects” • No I/O, global

    state change or DB interactions • Limited number of arguments (preferably zero, any greater and may should reactor) • Same input always yields same output Lead to: • Few bugs • More testable code • Code reuse 27 # pure def add(a, b): return a + b additions_made = 0 # not pure def add(a, b): global additions_made additions_made += 1 return a + b
  21. Recursion • Functions often call themselves in FP ◦ And

    again ◦ And again ◦ And again ◦ …. • Recursion is elegant (simpler or easier to read ) • Difficult to follow • Possible to be affected by language’s limitation (maximum recursion depth) ◦ RecursionError: maximum recursion depth exceeded after 1000 recursive calls. • memory intensive? 28 Demo
  22. https://knowyourmeme.com/photos/1246322- sweet-jesus-pooh-thats-not-honey29 Tail Recursion • A recursive function is tail

    recursive when a recursive call is the final execution by the function • Avoid stack exhaustion • Python don’t optimize tail calls ◦ enter Trampolining
  23. Tail Recursion 30 #not really tail recursive! def factorial(n): if

    n==0: return 1 else: return n*factorial(n-1) #tail recursive version def factorial(n, acum=1): if n==0: return acum else: return factorial(n-1, acum*n)
  24. Statements and Expressions 32 Statement • Procedural way • Instructions

    (to write an interpreter) • If, for ,def, class, and so on • Don’t evaluate to something • Cannot print the result Expressions • Functional way • Evaluate to something • Can print the result • Function calls are expressions Demo
  25. Conditional Branching (Flow Control) • Do A if X else

    do B • “If” statement ◦ Cannot be used in lambda expressions • “If” expression ◦ Can used in lambda expressions 33
  26. 35 Photo by Ben White on Unsplash Passing a Function

    as an Argument to another Function
  27. First Class functions can: • Function as object • Be

    stored in variables • Be returned from a function. • Be passed as arguments into another function • Support inline function definitions with anonymous lambda functions High Order Function • A function that returns another function 37 First-Class/High-Order Function First-Class High-Order def add(a, b): return a + b add_function = add add = lambda a,b: a + b
  28. High Order Function 38 • A function that returns another

    function def timer(fn): def timed(*args, **kwargs): t = time() fn(*args, *kwargs) print "took {time}".format(time=time()-t) return timed def compute(): #... timed_compute = timer(compute) timed_compute() Return a function Function as an argument
  29. Higher-Order Function • A function can operate on other function

    39 • Everything is an object • Passed to a function as an argument
  30. 41 Nesting a Function in Another Function • Nested functions

    (Functions inside functions) • Variable scope (Inside and outside of function) def outer(): def inner(): print('Inner:\t\t', x) print('Outer (before):\t', x) inner() print('Outer (after):\t', x) x = 'global' print('Global (before):', x) outer() print('Global (after): ', x) outside of function Global (before): global Outer (before): global Inner: global Outer (after): global Global (after): global def outer(): def inner(): nonlocal x x = 'inner' print('Inner:\t\t', x) x = 'outer' print('Outer (before):\t', x) inner() print('Outer (after):\t', x) x = 'global' print('Global (before):', x) outer() print('Global (after): ', x) Global (before): global Outer (before): outer Inner: inner Outer (after): inner Global (after): global Nonlocal binds a variable to one level higher
  31. 44 Decorators @timing def compute_magic(): dosomething Allow to implement higher

    order functions @a def b(): dosomething return somevalues
  32. Lambda expression in Python 45 A Python lambda is just

    another method to define a function. General syntax lambda arguments: expression input do somethings
  33. Dive into Lambda Expressions Lambda calculus • Mathematical logic •

    A formal mathematical system to express functions Lambda expression in Python • Nameless /Anonymous functions • Expressions, not statements • Without a name 46 from math import sqrt def p_pythagoras(x, y): return sqrt(x**2 + y**2) p_pythagoras(1, 1) l_pythagoras = lambda x, y: sqrt(x**2 + y**2) lambda Useful when • convenient if you quickly need a short function
  34. Function Composition Combining functions 47 def compose(*functions): return functools.reduce(lambda f,

    g: lambda x: f(g(x)), functions, lambda x: x) import functools def compose(*functions): def compose2(f, g): return lambda x: f(g(x)) return functools.reduce(compose2, functions, lambda x: x) https://mathieularose.com/function-composition-in-python/
  35. Reduce 48 functools.reduce(function, iterable[, initializer]) def reduce(function, iterable, initializer=None): it

    = iter(iterable) if initializer is None: value = next(it) else: value = initializer for element in it: value = function(value, element) return value Roughly equivalent to:
  36. So now reduce(). This is actually the one I've always

    hated most, because, apart from a few examples involving + or *, almost every time I see a reduce() call with a non-trivial function argument, I need to grab pen and paper to diagram what's actually being fed into that function before I understand what the reduce() is supposed to do. So in my mind, the applicability of reduce() is pretty much limited to associative operators, and in all other cases it's better to write out the accumulation loop explicitly. Guido van Rossum, 2005 49 from functools import reduce >>> from functools import reduce >>> arr = [1, 2, 3, 4, 5] >>> reduce(lambda x, y : x+y, arr) 15 Voltron: teaching kids distributed computing since 1984 The fate of reduce() in Python 3000
  37. Partial Function Application 53 def add1(num): return add(1, num) add1(1)

    # simpler from functools import partial add1 = partial(add, 1) add1(1) def partial(func, *args, **keywords): def newfunc(*fargs, **fkeywords): newkeywords = keywords.copy() newkeywords.update(fkeywords) return func(*args, *fargs, **newkeywords) newfunc.func = func newfunc.args = args newfunc.keywords = keywords return newfunc What/How functools.partial does Example Return a new function Pre-assigned parameters Useful when • Requires less argument The process of fixing a number of arguments to a function, producing another function of smaller arity
  38. 54 Photo by Thabang Mokoena on Unsplash Currying One argument

    per function Demo Takes multiple arguments into evaluating a sequence of functions, each with a single argument.
  39. 55 Currying Useful when • Requires single (exactly one) argument

    Decomposition of a polyadic function into a chain of nested unary functions def outer(outer_arg): def inner(inner_arg): return inner_arg + outer_arg return inner func = outer(10) func(5) >>> 15
  40. 56 Currying from inspect import signature def curry(fnc): def inner(arg):

    if len(signature(fnc).parameters) == 1: return fnc(arg) return curry(partial(fnc, arg)) return inner @curry def add(a, b, c): return a + b + c add_10 = add(10) add_10_100 = add_10(100) print(add_10_100(1000)) from functools import partial add_10 = partial(add, 10) add_10_100 = partial(add_10, 100) print(add_10_100(1000)) def add(a, b, c): return a + b + c print(add(10,100,1000)) partial (Binding function arguments) currying by a decorator simple function with multiple arguments
  41. 57 https://hackernoon.com/kotlin-functors-applicatives-and-monads-in-pictures-part-1-3-c47a1b1ce251 A monad is a structure that puts a

    value in a computational context https://nikgrozev.com/2013/12/10/monads-in-15-minutes/ Imperative Composition Monad
  42. print( bind(bind(bind(unit(x), f1), f2), f3) ) def f1(x): return (x

    + 1, str(x) + "+1") def f2(x): return (x + 2, str(x) + "+2") def f3(x): return (x + 3, str(x) + "+3") chain the functions log = "Ops:" res, log1 = f1(x) log += log1 + ";" res, log2 = f2(res) log += log2 + ";" res, log3 = f3(res) log += log3 + ";" print(res, log) “glue code” f3(f2(f1(x))) def unit(x): return (x, "Ops:") def bind(t, f): res = f(t[0]) return (res[0], t[1] + res[1] + ";") single chained function invocation Imperative
  43. Disadvantages of Functional Programming • Solutions for the same problem

    are different than procedural/ Object-oriented ones • Not equally useful for all type of problems • Input/ output are side effects and need special treatment • Recursion is “an order of magnitude more complex” than loops/iteration • Immutable data structures may increase run times 60
  44. Pro and Con for FP in Python 61 Pro •

    Functions as first-class citizens • lambda • Standard library support: map/filter/reduce, itertools, operator • Generators can be used for lazy-evaluation (in some cases) Con • Difficult to separate pure / non-pure • Mutable variables • Costly mem copy operations • Imperative style for cycles • No optimization for tail recursion • No pattern matching syntax • Classes-based only type system • No functions overloading mechanism • Functions composition is not implemented in stdlib • Imperative errors handling based on exceptions Python does not promote functional programming even though it works fairly well.
  45. The Missing Pieces for Python • Immutable Data Structures •

    Pattern Matching • Lazy Evaluation • Tail Call Optimization (TCO) • Large Collection of List functions 62
  46. 63 Recap • What is Functional Programming Style • Functional

    V.S. Procedural • Common Functional Design Patterns • Python offers functional features, but not pure functional language
  47. Adopt Functional Thinking • Break the process into discrete steps.

    • 100 % pure FP may be difficult to be implemented ◦ Avoid (mutable) state/side effect in a function, ▪ __init__ ▪ Staticmethod ▪ Type checking/ annotation ◦ Accept fewer side effects. Embrace Python’s OOP and functional styles. ◦ Freeze classes (immutable and frozen data type) • Pure functions as moules (Referential transparency) • Create modified copies, rather than modifying existing objects ( ◦ but expensive, so try to use persistent collections 64
  48. Adopt Functional Thinking • Develop a thinking pattern for why

    FP in your current code ◦ Why currying, monadic, lambda .... • Global variable is evil • Small function is easy to be understood • Rely on the standard lib. ◦ operator, Itertools and functools 65 >>> ss = ["Hsinchu", "PyHug", "2018"] >>> reduce(lambda acc, s: acc + len(s), ss, 0) 16 >>> s s= ["Hsinchu", "PyHug", "2018"] >>> reduce(lambda l,r: l+r, map(lambda s: len(s), ss)) 16 >>> ss = ["Hsinchu", "PyHug", "2018"] >>> reduce(operator.add, map(len, ss)) 16
  49. More about FP in Python • Deep into closure •

    Lazy evaluation (generator List comprehensions • More itertools and functools • Errors handling without exceptions • More design patterns ◦ Memoization, Tail Recursion, Mutual Recursion, Filter-Map-Reduce • Functional data structures, Custom data types 66
  50. Reference 67 1. Functional Programming HOWTO (Python Official Site) 2.

    Udemy (LEARNING PATH: Python: Functional Programming with Python) 3. https://github.com/xgrommx/awesome-functional-programming 4. https://github.com/sfermigier/awesome-functional-python 5. https://www.slideshare.net/ihower/fp-osdc2012v2 6. https://slides.com/apuaa-aa/python-fp#/ 2015 PyconAPAC by Apua 7. https://en.wikipedia.org/wiki/Lambda_calculus 8. https://nikgrozev.com/2013/12/10/monads-in-15-minutes/ more about Monad • fn.py ★2600 - "Functional programming in Python: implementation of missing features to enjoy FP" (unmaintained since 2014). • Coconut - "Simple, elegant, Pythonic functional programming".