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

The end


Thank you for attention!

  • Alexey Kachayev
  • Email: kachayev@gmail.com
  • Twitter: @kachayev
  • Github: kachayev


This presentation:

https://github.com/kachayev/talks