Functional Programming with Python

by Alexey Kachayev, 2012

About me

Position: CTO at Kitapps Inc.
Production experience: Python, Java, JS, Go, Scala, Clojure, Erlang
Looked at: Haskell, Lisp, Scheme

Goals

Short functional paradigm presentation
Dispel popular myths about FP
Characterize Python & FP relations
~~Why should I care?~~ How can I make my code better?

More How, less Why

About functional

Imperative programming (С/C++, Java)
Declarative programming
- Functional programming (Haskell, Scheme, OCaml)
- Logic programming (Prolog, Clojure core.logic)

IP = computation in terms of statements that change a program state
FP = computation as the evaluation of mathematical functions and avoids state and mutable data

About functional

Avoid state
Immutable data
First-class functions
Higher-order functions
Pure functions
Recursion, tail recursion
Iterators, sequences, lazy evaluation, pattern matching, monads....

About functional

"Imperative terminal"

$ ./program1
$ ./program2 --param1=1
$ ./program3

"Functional terminal"

$ ./program1 | ./program2 --param1=1 | ./program3

Programming task

Calculate partially invalid string with operations: "28+32+++32++39"

Programming task

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

"28+32+++32++39", 0
"28", 0
"32", 28
"", 60
"", 60
"32", 60
"", 92
"39", 92
131

Programming task

Functional style = apply transformation (and compositions)

from operator import add
expr = "28+32+++32++39"
print reduce(add, map(int, filter(bool, expr.split("+"))))

"28+32+++32++39"
["28","32","","","32","","39"]
["28","32","32","39"]
[28,32,32,39]
131

map/reduce/filter

Readability VS. conciseness
Technical aspects VS. operation substance
Code reusage ("pluggability")

Python hints

Module "operator"

>>> operator.add(1,2)
3
>>> operator.mul(3,10)
30
>>> operator.pow(2,3)
8
>>> operator.itemgetter(1)([1,2,3])
2

Python hints

Module "itertools"

>>> list(itertools.chain([1,2,3], [10,20,30]))
[1, 2, 3, 10, 20, 30]
>>> list(itertools.chain(*(map(xrange, range(5)))))
[0, 0, 1, 0, 1, 2, 0, 1, 2, 3]
>>> list(itertools.starmap(lambda k,v: "%s => %s" % (k,v), 
...                        {"a": 1, "b": 2}.items()))
['a => 1', 'b => 2']
>>> list(itertools.imap(pow, (2,3,10), (5,2,3)))
[32, 9, 1000]
>>> dict(itertools.izip("ABCD", [1,2,3,4]))
{'A': 1, 'C': 3, 'B': 2, 'D': 4}

Can we avoid loops?

>>> name = None
>>> while name is None:
...    name = raw_input()
...    if len(name) < 2:
...        name = None

Recursion

def get_name():
    name = raw_input()
    return name if len(name) >= 2 else get_name()

Tail recursion?

Erlang

fib(N) -> fib(0,1,N).
fib(_,S,1) -> S;
fib(F,S,N) -> fib(S,F+S,N-1).

Python

sorry...

Functions

First-class

def add(a, b):
    return a + b

add = lambda a,b: a + b

def calculations(a, b):
    def add():
        return a + b

    return a, b, add

Functions

High-ordered function

Pass function as argument

map(lambda x: x^2, [1,2,3,4,5])

Functions

High-ordered function

Function returns function as result

def speak(topic):
    print "My speach is " + topic

def timer(fn):
    def inner(*args, **kwargs):
        t = time()
        fn(*args, **kwargs)
        print "took {time}".format(time=time()-t)

    return inner

speaker = timer(speak)
speaker("FP with Python")

Functions

High-ordered function

I've already saw this...

@timer
def speak(topic):
    print "My speach is " + topic
    
speak("FP with Python")

Functions

How to write good code
dealing with functions?

Partial function application

The process of fixing a number of arguments to a function, producing another function of smaller arity

Simply-typed lambda calculus:

papply : (((a × b) → c) × a) → (b → c) = λ(f, x). λy. f (x, y)

Oh, never mind...

Partial function application

def log(level, message):
    print "[{level}]: {msg}".format(level=level, msg=message)					

log("debug", "Start doing something")
log("debug", "Continue with something else")
log("debug", "Finished. Profit?")

def debug(message):
    log("debug", message)

Partial function application

Simplify...

def log(level, message):
    print "[{level}]: {msg}".format(level=level, msg=message)					

from functools import partial
debug = partial(log, "debug")

debug("Start doing something")
debug("Continue with something else")
debug("Finished. Profit?")

Currying

The technique of transforming a function that takes multiple arguments in such a way that it can be called as a chain of functions each with a single argument

Simply-typed lambda calculus:

curry: ((a × b) → c) → (a → (b → c)) = λf. λx. λy. f (x, y)

Oh, never mind...

Currying

Segment sum

def simple_sum(a, b):
    return sum(range(a, b+1))

>>> simple_sum(1, 10)
55

Currying

Squares

def square_sum(a, b):
    return sum(map(lambda x: x**2, range(a,b+1)))

>>> square_sum(1,10)
385

Currying

Logarithms

def log_sum(a, b):
    return sum(map(math.log, range(a,b+1)))

>>> log_sum(1,10)
15.104412573075518

Currying

In general...

def fsum(f):
    def apply(a, b):
        return sum(map(f, range(a,b+1)))
    return apply

log_sum = fsum(math.log)
square_sum = fsum(lambda x: x**2)
simple_sum = fsum(int) ## fsum(lambda x: x)

>>> fsum(lambda x: x*2)(1, 10)
110
>>> import functools
>>> fsum(functools.partial(operator.mul, 2))(1, 10)
110

Currying (standard library)

>>> from operator import itemgetter
>>> itemgetter(3)([1,2,3,4,5])
4

>>> from operator import attrgetter as attr
>>> class Speaker(object):
...     def __init__(self, name):
...         self.name = "[name] " + name
... 
>>> alexey = Speaker("Alexey")
>>> attr("name")(alexey)
'[name] Alexey'

Currying (standard library)

>>> from operator import methodcaller

>>> methodcaller("__str__")([1,2,3,4,5])
'[1, 2, 3, 4, 5]'
>>> methodcaller("keys")(dict(name="Alexey", topic="FP"))
['topic', 'name']

>>> values_extractor = methodcaller("values")
>>> values_extractor(dict(name="Alexey", topic="FP"))
['FP', 'Alexey']

>>> methodcaller("count", 1)([1,1,1,2,2]) 
>>> # same as [1,1,1,2,2].count(1)
3

Good function is small function

Bad

>>> ss = ["UA", "PyCon", "2012"]
>>> reduce(lambda acc, s: acc + len(s), ss, 0)
11

Not bad...

>>> ss = ["UA", "PyCon", "2012"]
>>> reduce(lambda l,r: l+r, map(lambda s: len(s), ss))
11

Good

>>> ss = ["UA", "PyCon", "2012"]
>>> reduce(operator.add, map(len, ss))
11

Python hints

types are callable

>>> map(str, range(5))
['0', '1', '2', '3', '4']

classes are callable

>>> class Speaker(object):
...     def __init__(self, name):
...         self.name = name
>>> map(Speaker, ["Alexey", "Andrey", "Vsevolod"])
[<__main__.Speaker>, <__main__.Speaker>, <__main__.Speaker>]

instance methods are callable

>>> map([1,2,3,4,5].count, [1,2,3,10,11])
[1, 1, 1, 0, 0]

Functions

Pure

def is_interesting(topic):
    return topic.contains("FP")

Not pure

def speak(topic):
    print topic

Pure ??

def set_talk(speaker, topic):
    speaker["talk"] = topic
    return speaker

Mutable data

Global variable is evil

and everybody knows why

current_speaker = {name: "Alexey Kachayev", talk: "FP with Python"}

def ask_question(question):
    print "{name}, I have question {question} about your {talk}"

def quit(reason):
    current_speaker = {name: "Andrey Svetlov"} # <-- this will fail
    current_speaker["talk"] = "Oh, boring..." # <-- mutable state

Mutable data

And what about local?

def run_conf():
    speaker = {name: "Alexey Kachayev", talk: "FP with Python"}

    def ask_question(question):
        print "{name}, I have question {question} about {talk}"

    def quit(reason):
        current_speaker["talk"] = "Oh, boring..." # <- same

    name = lambda: speaker["name"]

Purity is cool

map can be pmap
Less bugs
Easier to test
More ways to reuse

Classes and OOP

Mutability...

class Speaker(object):
    def __init__(self, name, topic):
        self.name = name
        self.topic = topic

    def ask(self, question):
        print "{name}, {q}".format(name=self.name, q=question)

    def talk(self):
        print "I'm starting {topic}".format(topic=self.topic)

me = Speaker("Alexey", "FP with Python")
me.name = "Andrey" # <- WTF???

# or ....

me.set_name("Vsevolod") # <- guys, are you serious???

Think functional: Classes and OOP

Mutable dict + partial binding

def ask(self, question):
    print "{name}, {q}?".format(name=self["name"], q=question)

def talk(self):
    print "I'm starting {topic}".format(topic=self["topic"])

from functools import partial
def cls(**methods):
    def bind(self):
        return lambda (name, method): (name, partial(method, self))
    return lambda **attrs: dict(
        attrs.items() + map(bind(attrs.copy()), methods.items())
    )

Speaker = cls(ask=ask, talk=talk)

Think functional: Classes and OOP

>>> me = Speaker(name="Alexey", topic="FP with Python")

>>> me["name"]
'Alexey'
>>> me["topic"]
'FP with Python'
>>> me["talk"]
<functools.partial object at 0x109798d60>
>>> me["talk"]()
I'm starting FP with Python
>>> me["ask"]
<functools.partial object at 0x109798c58>
>>> me["ask"]("WTF")
Alexey, WTF?

bindings are immutable

Think functional: Classes and OOP

If you need mutable implementation...

def cls(**methods):
    def bind(**attrs):
        attrs = attrs.copy()
        attrs.update(dict(map(lambda (n,m): n, partial(m, attrs), 
                              methods.items())))
        return attrs
    return bind

Stop writing classes

Jack Diederich
PyCon US 2012
https://www.youtube.com/watch?v=o9pEzgHorH0

Simplify your code, avoiding classes

Stop writing classes

class Greeting(object):
    def __init__(self, greeting="hello"):
        self.greeting = greeting

    def greet(self, name):
        return "{greet}! {name}".format(greet=self.greeting, name)

hola = Greeting("hola")
print hola.greet("bob")

>>> "hola! bob"

Are you kidding me???

Stop writing classes

def greet(greeting, target):
    return "{greet}! {name}".format(greet=greeting, name)

hola = functools.partial(greet, "hola")

Stop writing classes

Think functional: Data

Assume that we don't have dict

def dct(*items):
    def pair((key, value)):
        return lambda k: value if k == key else None

    def merge(l, r):
        return lambda k: l(k) or r(k)

    return reduce(merge, map(pair, items), pair((None, None)))

>>> me = dct(("name", "Alexey"), ("topic", "FP with Python"))
>>> me("name")
'Alexey'
>>> me("topic")
'FP with Python'
## use this for cls function
>>> me("ask")("WTF")
Alexey, WTF?

Sure, I know about complexity...

Python & FP

Pro

Functions as first-class citizens
lambda
Standard library: map/filter/reduce, itertools, operator
Generators can be used for lazy-evaluation (in some cases)

Python & FP

Con

Impossible to separate pure / non-pure
Mutable variables
Costly mem copy operations

Python & FP

Con

Imperative style for cycles
No optimization for tail recursion

Python & FP

Con

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 & FP

Con

Python

map(lambda x: x*2, [1,2,3])

Scala

List(1,2,3).map(_*2)

Clojure

(map #(* % 2) '(1 2 3))

Haskell

map (2*) [1,2,3]

What did we miss?

Almost everything

Errors handling without exceptions
Pattern matching
Message passing
Functional data structures
Custom data types
Lazy evaluation

Where can I find more?

SICP (http://deptinfo.unice.fr/~roy/sicp.pdf)
Book "Purely Functional Data Structures"
Book "The Functional Approach to Programming"
Coursera "Functional Programming Principles in Scala"
Real World Haskell (http://book.realworldhaskell.org/read/)
Learn You a Haskell for Great Good! (http://learnyouahaskell.com/)
Learn You Some Erlang for Great Good! (http://learnyousomeerlang.com/)

Functional Programming with Python

by Alexey Kachayev, 2012

About me

Goals

More How, less Why

About functional

About functional

About functional

"Imperative terminal"

"Functional terminal"

Programming task

Programming task

Programming task

map/reduce/filter

Python hints

Module "operator"

Python hints

Module "itertools"

Can we avoid loops?

Recursion

Tail recursion?

Erlang

Python

Functions

First-class

Functions

High-ordered function

Functions

High-ordered function

Functions

High-ordered function

Functions

How to write good code dealing with functions?

Partial function application

Simply-typed lambda calculus:

Partial function application

Partial function application

Currying

Simply-typed lambda calculus:

Currying

Currying

Currying

Currying

Currying (standard library)

Currying (standard library)

Good function is small function

Bad

Not bad...

Good

Python hints

types are callable

classes are callable

instance methods are callable

Functions

Pure

Not pure

Pure ??

Mutable data

Global variable is evil

Mutable data

And what about local?

Purity is cool

Classes and OOP

Mutability...

Think functional: Classes and OOP

Mutable dict + partial binding

Think functional: Classes and OOP

Think functional: Classes and OOP

If you need mutable implementation...

Stop writing classes

Simplify your code, avoiding classes

Stop writing classes

Are you kidding me???

Stop writing classes

Stop writing classes

Think functional: Data

Assume that we don't have dict

Python & FP

Pro

Python & FP

How to write good code
dealing with functions?