Tail Recursion in Python using Pysistence

A topic that occasionally comes up in Python development is that of tail recursion. Many functional programmers want to see tail recursion elimination added to the Python language. According to Guido, that ain’t gonna happen. And to be fair, I agree. Tail recursion can be tricky not only for new programmers, but for old timers as well.

However, that doesn’t mean that we need to give up on the concept altogether. This is a problem that is hardly new. Functional languages have been implementing tail recursion in environments hostile to it for a while now using a trampoline approach. Let’s see how the newest version of pysistence implements that algorithm:

def trampoline(func, *args, **kwargs):
    """Calls func with the given arguments.  If func returns 
       another function, it will call that function and repeat
       this process until a non-callable is returned."""
    result = func(*args, **kwargs)
    while callable(result):
        result = result()
    return result

This makes it much easier to implement things functionally (using pysistence’s functional lists):

def iter_to_plist(seq):
    seq = iter(seq)
    def inner(accum):
        try:
            return partial(inner, accum.cons(seq.next()))
        except StopIteration:
            return accum
    return inner(pysistence.make_list())

>>> trampoline(iter_to_plist, xrange(1000))
PList([999, 998, 997, 996, 995, 994, 993, 992, 991, 990, 989, 988, 987, 986, 985

That was more work than writing this in a language that does tail recursion automagically. But it wasn’t too bad now was it? Ultimately, I think this approach works for a few reasons:

  1. It’s explicit. The user is well aware of what’s happening because they’re returning a callable.
  2. It makes functional programming more natural. Instead of using true recursion and risking blowing the stack or converting this into a loop and continually reassigning to a variable, you can make the algorithm work without side effects.
  3. It lets Python stay imperative.

For me personally, this is a great set of arguments. I love Python and I love functional programming. The more functional programming I can do in Python, the better. But there are very few things in programming that are free, right? Here are some of the disadvantages:

  1. It’s ugly. I don’t deny this. But this alone is not an argument against it. If you are the kind of person who wants nothing but beautiful code, I’d argue that you’ve chosen the wrong language. Python tends to be beautiful when possible, but ugly when it has to be. Besides that this is the best you’re going to get without modifying the language itself or adding macros.
  2. It isn’t very performant. Insert your favorite quote about not needing to be blazing fast, just good enough here. Besides that, it can be optimized in C if need be.
  3. Who needs more ways to do functional programming? I’m not going to join any flamewars on this one. But I will point you to the advantages of functional programming in Python’s own functional programming HOWTO.

How to Write: A Programmer's Guide

typewriter

I love writing. I think I have talent in writing. But that doesn’t necessarily mean what I’m writing is good. To become a good writer, you need to put in work and experience. Here are some things I’ve learned along the way:

Practice makes perfect – It’s indisputable that great athletes like Michael Jordan and Wayne Gretzky have a lot of talent. But that doesn’t mean that they were able to go into the major leagues on their first try. Similarly, you might have talent, but it takes practice to unlock that talent. If you don’t have talent, you can still become good at writing. It just takes more time and patience. Blogs are perfect for this. Rest assured of one thing: if your writing sucks, nobody will read your blog. That’s actually a good thing because that means you can write all the stupid things you want and no one will read them until you get good at writing.

I know you’ve heard it a thousand times before. But it’s true – hard work pays off. If you want to be good, you have to practice, practice, practice. If you don’t love something, then don’t do it. -Ray Bradbury

Write because you want to – How many people have you met that “really needed to start blogging”? Don’t write because you think it’s good for your career or because programmers “need” to have a blog. I write about programming because I love writing and programming. If you love programming but not writing, then chances are your time is better spent writing code.

Love is easy, and I love writing. You can’t resist love. You get an idea, someone says something, and you’re in love. -Ray Bradbury

Just write it down – When you write something the first time, it will suck. Therefore, if it doesn’t suck at first, it hasn’t been written down.

Writing is no trouble: you just jot down ideas as they occur to you. The jotting is simplicity itself—it is the occurring which is difficult. -Stephen Leacock

Edit – In this sense, writing isn’t a whole lot different than coding. When you start coding something, the most important thing is just to start coding and not worry about it being perfect. But no code worth writing is perfect the first time around. You have to test it, break it, and make others read it to see if it’s clear. Writing for humans is no different. You must be as merciless in your writing as you are with your code.

I’m not a very good writer, but I’m an excellent rewriter -James Michener

The Wolf in Sheep's Clothing

simplicity

The idea of simplicity has been on my mind a lot recently. I have yet to meet a developer who doesn’t believe in it. So everyone believes in simplicity, shouldn’t we have a lot of simple code? Well, no. The other thing that every developer I’ve ever met agrees with is that there isn’t enough simple code out there. This implies a few possibilities:

  1. Programmers don’t believe in simplicity as much as they claim.
  2. Programmers don’t agree on what simplicity is.
  3. Programmers mistake other things for simplicity.

I ultimately think our situation is a combination of these three things. Numbers 1 and 2 are just the nature of the beast. Sure, everyone wants simple code, but let’s face it: deadlines can make that difficult. And the fact that very few people can define simplicity (and I don’t claim to be one of them) much less agree what it is makes it even harder.

But number 3 is the nasty one. I see it all the time. I’ve even done it myself (I know that’s probably hard for you guys to imagine ;). There’s one thing that I see people confusing with simplicity over and over again: expediency.

In the interest of full disclosure, I think it’s important to note that I haven’t found a good definition of simplicity in the context of software development. But I do know that whatever it is, it isn’t expediency.

Now, business types and “product people” love expediency. And who can blame them? Their job is to make sure a product gets created. Granted, I think they underestimate how important good code is to building a product, but that’s a different subject. Plus, I’m the first person to advocate working smarter rather than harder. I’m not necessarily saying expediency is bad.

The problem is when we confuse simplicity and expediency. Expedient solutions are easy to create. Truly simple solutions are easy to maintain and expand. Sometimes solutions are expedient (easy to create) and simple (easy to maintain). But more often that not, you have to consider the tradeoffs. Do you create something to meet your immediate needs, or do you create something that will meet your future needs?

All I’m getting at is this: it would be really cool if people said “I don’t think we have time for a solution that simple.” rather than playing the simplicity card for themselves. After all, it would be the truth. And I think it would make sure that you aren’t confusing simplicity with expediency.