Functional Programming Concepts for the Lay Programmer – Part 2

Update: Part 3 is finally available.

After languishing in the drafts folder for over a year and a half,  Functional Programming Concepts for the Lay Programmer – Part 1 now has a friend.

The Easy Stuff, Continued

Mutable/Immutable

In many languages, there are certain data types where, once an instance created, it cannot be changed. That is, any attempt to change the value produces a new object, leaving the old one unaltered. Such data types are known as “immutable” (unchanging).

Generally, functional languages apply this principle to all data types to limit programming with side-effects to things like disk and network access.

Conversely, data structures which can be altered (eg. Lists/Arrays in pretty much any language which supports imperative programming) are known as “mutable”.

Lambda

Also known as anonymous functions, lambdas are functions which can have their definitions placed anywhere a function name would normally be expected as an argument (See “Higher-order Function” in part 1) and, unlike regular functions, don’t need to be assigned a name. While Python’s lambdas are very limited compared to more functional languages, being more reusable expressions than proper functions, this example should still help to clarify the utility of one-off functions:

myList.sort(key=lambda x: abs(x.delta))

In one line, that lets you perform an in-place sort on the absolute values of the objects’ “delta” member variables. I also ran across a slightly more technical explanation in case you want it. I’m told that the implementations of many Ruby APIs are also an excellent example of the utility of lambda-like constructs thanks to Ruby’s anonymous block construct.

Tuples

In every functional or multi-paradigm language I’ve had personal experience with, lists have certain restrictions. For example, in Haskell, the type signature of every element in a list must be the same while, in Python, lists are mutable which, as a side-effect, means they cannot be used as dict (a.k.a. hash/mapping) keys.

The tuple is a list-like data structure which provides a different set of limitations. In Python, tuples are immutable but can be used as dict keys. In Haskell, you can create a tuple with any combination of elements, but every tuple will have a unique type signature. (If you’re familiar with C-like languages, think of a list as an array and a tuple as a simple struct. The implications for function type signatures are essentially the same.)

In both languages, the most common use I’ve found for tuples is allowing a function to return multiple values of varying types without having to define a new, single-use data type.

Generators

Imagine a function which you can leave and re-enter without losing its internal state. That’s what generators are. They’re most commonly useful anywhere you want to iterate over something without having to generate the entire set of values before you start.

Python implements generators, so this bit of example code should make it a bit clearer:

def find_first(thing):
    for fldr, dirs, files in os.walk('/home/me/stories'):
        for fname in files:
            if thing in fname:
                return os.path.join(fldr, fname)

os.walk is a generator which wraps up a depth-first tree traversal as an iterator so you have the option to abstract away the recursion. Each time it resumes, it traverses one iteration further into the algorithm.

What makes generators so special is how simple they are to use:

def thumbnails(img_paths):
    for path in img_paths:
        base, ext = os.path.splitext(path)
        yield base + '_tn' + ext

for thumbpath in thumbnails(list_of_millions_of_paths):
    # Do something

Think of that yield keyword as “return, but let me resume execution where I left off”. I use them for writing things like for block in parse_png(file_handle):

Coroutines

Coroutines are basically the next generalization up from generators. While generators give you a way to return multiple times from a single function, coroutines give you a way to exit and enter a block of code, receiving and sending data as you go without relying on side-effects (see pure function). Wikipedia has examples of how this is useful.

Python 2.5 and above support coroutines using these extensions to the generator syntax:

def coroutine():
    # ...
    input = (yield output)
    # ...

co = coroutine()
while I_am_looping:
   # ...
   return_value = co.send(new_argument)
   # ...

Continuations

If you take one more step from coroutines, you get to continuations. As a friend put it, “continuations are what system calls do”. The operating system saves everything about your program’s current state and goes off to do something else. Then, when the return value of the system call is ready, it restores that saved state and resumes your program where it left off. When a programming language has good support for continuations, you can arbitrarily choose to save the state of a thread of execution, pass it around, and then come back to it later. As another friend put it, “continuations are what you’d use to, say, implement the ‘yield’ keyword”.

If JavaScript had continuations, for example, you wouldn’t need to write so many callbacks. You’d just write what appears to be a blocking code but works asynchronously under the hood. TameJS (JavaScript continuations for Node.JS using C# syntax) and F# (Example 4: Asynchronous programming) provide good examples of how this looks and works.

Alongside anonymous functions and tail recursion, continuations are one of the few functional-programming features that basic, bog-standard Python doesn’t support… but there is a Python web application framework named Nagare (built on Stackless Python) which uses them to provide a very unique approach to writing Python web applications.

Still to Come…

• Map/Reduce/Filter
• Closures
• Metaclasses

Let’s hope that, this time, it doesn’t take me a year and a half to write it.

Functional Programming Concepts for the Lay Programmer – Part 2 by Stephan Sokolow is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.