Functional Programming with Python

by Alexey Kachayev, 2012

• 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

• 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

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

"Imperative terminal"

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

"Functional terminal"

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

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

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

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"

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).

sorry...

Functions

First-class

return a + b

add = lambda a,b: a + b

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

return a, b, add

High-ordered function

Pass function as argument

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

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")

High-ordered function

I've already saw this...

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

speak("FP with Python")

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

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

>>> 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]

Pure

def is_interesting(topic):

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"}

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"}

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

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

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())
)

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
<functools.partial object at 0x109798c58>
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

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"

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
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
• Functions composition is not implemented in stdlib
• Imperative errors handling based on exceptions

Python & FP

Python

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

Scala

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

Clojure

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

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"
• Learn You a Haskell for Great Good! (http://learnyouahaskell.com/)
• Learn You Some Erlang for Great Good! (http://learnyousomeerlang.com/)

The end

Thank you for attention!

• Alexey Kachayev
• Email: kachayev@gmail.com