Introduction to Functional Programming

Event:PyCon Italia 2010
Presenters:Michele Simionato, Nicola Larosa
Date: 2010-05-08

My goals for this talk

First: two misconceptions

  1. FP means map, filter, reduce
  2. FP means Haskell

What functional means

Less is more

Point 1: immutable bindings

>>> for item in sequence:
        do_something(item)

Let's see ...

root = Tkinter.Tk()
text = Tkinter.StringVar()
label = Tkinter.Label(root, textvariable=text)
menubar = Tkinter.Menu(root)
menu = Tkinter.Menu(menubar)
menubar.add_cascade(label='File', menu=menu)
for item in ['F1','F2', 'F3']:
    def showmenu():
        text.set(text.get() + '\n%s' % item)
    menu.add_command(label=item, command=showmenu)
root.config(menu=menubar); label.pack()
root.mainloop()

The usual hack

root = Tkinter.Tk()
text = Tkinter.StringVar()
label = Tkinter.Label(root, textvariable=text)
menubar = Tkinter.Menu(root)
menu = Tkinter.Menu(menubar)
menubar.add_cascade(label='File', menu=menu)
for item in ['F1','F2', 'F3']:
    def showmenu(item=item):
        text.set(text.get() + '\n%s' % item)
    menu.add_command(label=item, command=showmenu)
root.config(menu=menubar); label.pack()
root.mainloop()

This is still a hack

A simpler example

lst = []
for i in 0, 1, 2:
    def f():
        print i
    lst.append(f)

lst[0]() #=> 2
lst[1]() #=> 2
lst[2]() #=> 2

A partial solution

lst = []
def append_f(i):
    def f():
        print i
    lst.append(f)

for i in 0, 1, 2: # mutation is still there
    append_f(i)

lst[0]() #=> 0
lst[1]() #=> 1
lst[2]() #=> 2

The question

We need a way to compute a loop without rebinding the loop variable:

def loop123():
    for i in 1, 2, 3:
        <do_something(i)>

loop123()

Clearly we need to introduce a new scope at each iteration

The answer: recursion

Convert the function containing a loop in a recursive function with an additional argument (the loop index):

def loop123(i=1):
    if i > 3:
        return
    else:
        <do_something(i)>
        loop123(i+1) # tail call

loop123()

Another example: enumerate

Here is an example of a for loop used to build a data structure:

def enumerate(values, i=0, acc=()):
   if i >= len(values):
       return acc
   else:
       return enumerate(
         values, i+1, acc + ((i, values[i]),))

The trick is to use an (immutable) accumulator

The importance of tail calls

A note on pattern matching

Pattern matching is used a lot in functional languages; in Scheme is especially used in macro programming; in ML and Haskell is used everywhere, even to define functions:

fun fact n = fact' (n, 1)
and fact' (0, acc) = acc
  | fact' (n, acc) = fact' (n-1,  acc*n);

In Erlang is used to destructure the messages sent to the Erlang lightweight processes.

TCO and debugging

There has been some heated debate last year due to Guido's dismissal of TCO.

In all fairness I must notice that TCO does not prevent debugging:

;; tco.ss
(let loop ((x -3))
  (/ 1 x)
  (loop (add1 x)))

(but I agree that iterative is better than recursive)

The pragmatist voice

Python programs written in functional style usually won’t go to the extreme of avoiding all I/O or all assignments; instead, they’ll provide a functional-appearing interface but will use non-functional features internally. For example, the implementation of a function will still use assignments to local variables, but won’t modify global variables or have other side effects. -- Andrew Kuchling

Example: collecting objects

def collect_mail(mails):
    storage = {}
    for mail in mails:
        client = mail.getclient()
        kind = mail.getkind()
        date = mail.getdate()
        stored = storage.get((client, kind))
        if stored is None or stored.date < date:
            storage[client, kind] = mail
    return storage

For purists at all costs ...

... use a helper function

def _collect_mail(storage, mail):
   # a left-folding function: acc,obj->new-acc
   client = mail.getclient()
   kind = mail.getkind()
   date = mail.getdate()
   stored = storage.get((client, kind))
   if stored is None or stored.date < date:
       return update(
           storage, (client, kind), mail)
   else:
       return storage

... then reduce is your friend

def collect_mail(mails):
   return reduce(_collect_mail, mails, {})

Point 2: immutable data

namedtuple

>>> from collections import namedtuple
>>> Point = namedtuple('Point', 'x y')
>>> p1 = Point(0, 0)
>>> p2 = p1._replace(x=1)
>>> p2
(1, 0)
>>> p1 is p2
False

(requires copying the full structure in Python). Python also lacks immutable dictionaries (say Red/Black trees).

Generators are mutable

Many Python programs (especially the ones using list/generator comprehension and the itertools module) are considered in functional style even if they are not functional from a purist POV:

>>> it123 = iter([1, 2, 3])
>>> for i in it123: print i,
...
1 2 3
>>> for i in it123: print i,
...

The functional way: streams

Looping over a stream does not mutate it:

> (import (srfi :41 streams))
> (define str123 (stream-range 1 4))
> (stream-for-each display str123)
123
> (stream-for-each display str123)
123

Yet another difference between Python and a true functional language

3: confined side effects?

Side effects and unittests

Usual recommendations

All the usual recommendations to make code more testable, such as

are recommendations to make code more functional.

Database connections (bad)

db = DBSession() # singleton

def read(...):
db.read_data( ... )
def write(data, ...):
db.write_data(data, ...)
if __name__ == '__main__':
db.init(dsn)

Database connections (good)

def read(db, ...):
db.read_data( ... )
def write(db, data, ...):
db.write_data(data, ...)
if __name__ == '__main__':
db = DBSession(dsn)

FP and databases

Functional design and SQL

References

http://www.phyast.pitt.edu/~micheles/scheme/TheAdventuresofaPythonistainSchemeland.pdf http://www.haskell.org/ http://clojure.org/ http://docs.python.org/howto/functional.html http://www.defmacro.org/ramblings/fp.html http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf http://srfi.schemers.org/srfi-41/srfi-41.html http://funcall.blogspot.com/2009/05/you-knew-id-say-something-part-iv.html