Tuesday, April 21, 2009

Origins of Python's "Functional" Features

I have never considered Python to be heavily influenced by functional languages, no matter what people say or think. I was much more familiar with imperative languages such as C and Algol 68 and although I had made functions first-class objects, I didn't view Python as a functional programming language. However, earlier on, it was clear that users wanted to do much more with lists and functions.

A common operation on lists was that of mapping a function to each of the elements of a list and creating a new list. For example:
def square(x):
    return x*x

vals = [1, 2, 3, 4]
newvals = []
for v in vals:
    newvals.append(square(v))

In functional languages such as Lisp and Scheme, operations such as this were provided as built-in functions of the language. Thus, early users familiar with such languages found themselves implementing comparable functionality in Python. For example:
def map(f, s):
    result = []
    for x in s:
            result.append(f(x))
    return result

def square(x):
    return x*x

vals = [1, 2, 3, 4]
newvals = map(square,vals)

A subtle aspect of the above code is that many people didn't like the fact that you to define the operation that you were applying to the list elements as a completely separate function. Languages such as Lisp allowed functions to simply be defined "on-the-fly" when making the map function call. For example, in Scheme you can create anonymous functions and perform mapping operations in a single expression using lambda, like this:
(map (lambda (x) (* x x)) '(1 2 3 4))  

Although Python made functions first-class objects, it didn't have any similar mechanism for creating anonymous functions.

In late 1993, users had been throwing around various ideas for creating anonymous functions as well as various list manipulation functions such as map(), filter(), and reduce(). For example, Mark Lutz (author of "Programming Python") posted some code for a function that created functions using exec:
def genfunc(args, expr):
    exec('def f(' + args + '): return ' + expr)
    return eval('f')

# Sample usage
vals = [1, 2, 3, 4]
newvals = map(genfunc('x', 'x*x'), vals)

Tim Peters then followed up with a solution that simplified the syntax somewhat, allowing users to type the following:
vals = [1, 2, 3, 4]
newvals = map(func('x: x*x'), vals)

It was clear that there was a demand for such functionality. However, at the same time, it seemed pretty "hacky" to be specifying anonymous functions as code strings that you had to manually process through exec. Thus, in January, 1994, the map(), filter(), and reduce() functions were added to the standard library. In addition, the lambda operator was introduced for creating anonymous functions (as expressions) in a more straightforward syntax. For example:
vals = [1, 2, 3, 4]
newvals = map(lambda x:x*x, vals)

These additions represented a significant, early chunk of contributed code. Unfortunately I don't recall the author, and the SVN logs don't record this. If it's yours, leave a comment! UPDATE: As is clear from Misc/HISTORY in the repo these were contributed by Amrit Prem, a prolific early contributor.

I was never all that happy with the use of the "lambda" terminology, but for lack of a better and obvious alternative, it was adopted for Python. After all, it was the choice of the now anonymous contributor, and at the time big changes required much less discussion than nowadays, for better and for worse.

Lambda was really only intended to be a syntactic tool for defining anonymous functions. However, the choice of terminology had many unintended consequences. For instance, users familiar with functional languages expected the semantics of lambda to match that of other languages. As a result, they found Python’s implementation to be sorely lacking in advanced features. For example, a subtle problem with lambda is that the expression supplied couldn't refer to variables in the surrounding scope. For example, if you had this code, the map() function would break because the lambda function would run with an undefined reference to the variable 'a'.
def spam(s):
    a = 4
    r = map(lambda x: a*x, s)

There were workarounds to this problem, but they counter-intuitively involved setting default arguments and passing hidden arguments into the lambda expression. For example:
def spam(s):
    a = 4
    r = map(lambda x, a=a: a*x, s)

The "correct" solution to this problem was for inner functions to implicitly carry references to all of the local variables in the surrounding scope that are referenced by the function. This is known as a "closure" and is an essential aspect of functional languages. However, this capability was not introduced in Python until the release of version 2.2 (though it could be imported "from the future" in Python 2.1).

Curiously, the map, filter, and reduce functions that originally motivated the introduction of lambda and other functional features have to a large extent been superseded by list comprehensions and generator expressions. In fact, the reduce function was removed from list of builtin functions in Python 3.0. (However, it's not necessary to send in complaints about the removal of lambda, map or filter: they are staying. :-)

It is also worth nothing that even though I didn't envision Python as a functional language, the introduction of closures has been useful in the development of many other advanced programming features. For example, certain aspects of new-style classes, decorators, and other modern features rely upon this capability.

Lastly, even though a number of functional programming features have been introduced over the years, Python still lacks certain features found in “real” functional programming languages. For instance, Python does not perform certain kinds of optimizations (e.g., tail recursion). In general, because Python's extremely dynamic nature, it is impossible to do the kind of compile-time optimization known from functional languages like Haskell or ML. And that's fine.

21 comments:

  1. back to python now. miss its functions :D

    ReplyDelete
  2. Really, Python is so dynamic that it can't tell when 'return' is returning a function call and thus can't do tail-call optimization?

    Or is it unneeded/undesirable for some particular philosophical reason? (I am not familiar with all the stackless vs. core Python issues, so maybe that could make a future post, how the philosophies involved are incompatible)...

    Thank you for writing all of this down, it is a lot more important than it might seem at the time...

    -Doug

    ReplyDelete
  3. it's a shame that blogspot (at the time of this writing) does not preserve the whitespace indentation that's necessary for Python code. :P

    ReplyDelete
  4. Argh. Fixed the whitespace.

    Regarding tail optimization: that's a long topic, maybe I'll get to it in a future post on my other blog.

    ReplyDelete
  5. You could fix the whitespaces in CSS:

    blockquote {
    white-space: pre;
    }

    ReplyDelete
  6. but? missing indentation in examples?

    ReplyDelete
  7. You think Python could detect tail recusion, until you find out someone monkey patched your function into something else in a different thread my eval'ing an opaque string.

    ReplyDelete
  8. I hate that Python doesn't have Tail-Call Optimization, though it does have the best stack traces of any language I've seen, which mostly makes up for it.

    Not being able to cleverly recurse isn't so bad when you never have to deal with anonymous "you tried to get the head of an empty list" exceptions!

    ReplyDelete
  9. Lua manages to have Tail-Call Optimization in a dynamic language, though I honestly don't know how much I'd use it.

    ReplyDelete
  10. Seems like this is the TCO week for Python. Two blog posts that discussed this topic were published independently about the same time on Monday. This is now the third one.

    http://www.teamrubber.com/blog/python-tail-optimisation-using-byteplay/
    http://fiber-space.de/wordpress/?p=349

    ReplyDelete
  11. you article is very interesting for me

    ReplyDelete
  12. I don't see why Python's dynamic nature would make it impossible to do TCO, after all Erlang can do it and it is just as dynamic.

    ReplyDelete
  13. @Alex could you be a bit more specific. Evaling a 'def ...' or a 'module.thing = lambda ...' won't change a function definition, it will provide a new function definition that might be bound to the same name. I don't know enough Python internals to know how much the actual byte code of a function can be changed (I had been assuming those are immutable, same as string contents).

    ReplyDelete
  14. New blog post in response to the tail recursion discussion: http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html

    ReplyDelete
  15. How appropriate that the anonymous function patch is itself anonymous.

    ReplyDelete
  16. Perhaps it's worth pointing out that Algol 68 has anonymous functions (but no closures).

    ReplyDelete
  17. @reinierpost: really? No closures in Algol 68? What's your definition of closures? I'm pretty sure functions can reference variables in outer scopes, and functon objects can be passed around. What's missing for "closures"?

    ReplyDelete
  18. re: Closures - Compare Python to Algol 68...
    # Python #
    from math import *
    root = lambda x: lambda y: exp(log(y)/x);
    square_root = root(2); cube_root = root(3);
    print square_root(64), cube_root(64)
    # Algol 68 #
    MODE F = PROC(REAL)REAL;
    PROC root = (REAL x)F: (REAL y)REAL: exp(ln(y)/x);
    F square root = root(2), cube root = root(3);
    print((square root(64), cube root(64), new line))
    Output: 8.0 4.0

    The key point about scoping is that with Algol 68 each argument "x" exists only on the LOC stack. Hence when "root" returns "x" becomes out of scope (off the stack). In python each "x" is in HEAP, then "follows" square_root and cube_root until these functions are no longer referenced.

    Quick fix for Algol 68 could be to put x on the HEAP eg.
    PROC root = (HEAP REAL x)F: (REAL y)REAL: exp(ln(y)/x);
    And let the garbage collector sort out x's closure.

    Minor other differences: Algol 68 is "IMPLICIT NONE", (useful for picking up bugs prior to runtime).

    ReplyDelete
  19. Neville, this probably doesn't belong in this comment thread any more, but I'm not sure I understand. Are you saying that the Algol68 example doesn't work? Can you mail guido@python.org so we can sort this out a bit more efficiently than in a comment thread? (I don't have an a68 compiler handy to experiment, sorry. :-)

    ReplyDelete
  20. Guido: one thing that blew up for me was returning functions. This is confirmed at

    http://enthusiasm.cozy.org/archives/2005/04/original-closures

    ReplyDelete
  21. Hi, Guido :-) Misc/HISTORY records that lambda et alia were introduced in Python release 1.0.0 (26 January 1994), and that the code was contributed my Amrit Prem.

    ReplyDelete