Showing posts from 2008

Trampolining for recursion...

In essence, CPS (continuation passing style) is a method of calling functions where instead of returning a value, you pass the results to another function (the continuation) provided as an argument. I wont go too deep into the reasoning behind this, as it's usually not used directly but rather as a middle representation of programming languages by some compiler/interpreter (read more on the wikipedia link).

The big downside is that you're bombarding the stack with function frames for every call, going deeper and deeper, but never returning (you just keep passing what would be the return value to another function).

One nifty method of avoiding this is to use a trampoline. A trampoline resembles a stream/lazy-list to anyone who's read SICP. Essentially, instead of calling functions from within another function, you return a bounce "call" to the trampoline which makes the call for you, doing the same with the return value of that call until it gets a land (a non-bounc…

Python: know when to be lazy

Lazy is good. One Python trend I've noticed quite a bit is the severe under-usage of generators. I often see list comprehension being used in situations where building a temporary list is not only wasteful, but more work.


print sum([x * 2 for x in something])

In this case, LC is being used to build a temporary list whose only purpose is to be iterated by "sum". Instead of constructing this list, why not pass an iterable object to "sum" and have it accumulate the sum from that? Well, not only can you, but it's even less to type (a whopping two characters less):

print sum(x * 2 for x in something)

Simply excluding the square brackets takes it from a list-comp to a generator expression, which is lazily evaluated. To demonstrate, proof that generators don't actually compute anything until they are pulled:

def f(x):
print x

a = [f("LC") for x in xrange(10)]
b = (f("GE") for x in xrange(10))

print "outside"

print "…

GAE: Batch operations

Given the limit on individual requests with GAE, doing things like batch updates to your database (live) can be an interesting challenge. I recently had to update all of the votes for Challenge-You! to support a new rating system. The best approach I found was an AJAX-style solution. Have one request that returns a list of references to the entities you need to change (or if you're working with more than 1000 entities, you might want to partition the list into chunks by date or some other order, and work with one chunk at a time). Keeping those references in a stack in Javascript, pop them off one-by-one and send each to the controller that applies the change, repeating until the stack is empty. If the operations aren't too expensive, you could even send a handful of them per-request to speed things up. It's also trivial to implement some kind of progress bar or other graphical update to keep you informed.

And example of the Javascript code (using jQuery) that handles the c…

Speed kiddies

Speed kiddie:

Someone who learns or uses a low-level (often compiled) language for the constant coefficient performance increase. These people often have no regards for computational complexity and are usually confused by asymptotic notation. They frequently suffer from severe cases of premature optimization and believe that manageability comes second to runtime speed (in all applications). You can often find them trolling around web-forums bragging about their pointer or bit manipulation skills (the code is generally characterized by non-reusable design and a significant lack of readability).

"What do you mean my algorithm runs at O(n!)? It's twice as fast as yours with this small test set""How do you write efficient code in Python... It doesn't even have pointers!""I don't need to write readable code, I'm not going to forget my own code...""High level languages are for the weak, real men enjoy pain... PAIN!!!""Lisp …

Javascript == bad

Along the way while writing Epy, I've noticed some things about Javascript (a language I once considered perfectly reasonable) that are in serious need of a revamp (at least at the time of writing this). Here are just a few of the (many) issues I have with Javascript:

Namespaces. In the world of most Javascript, everything is global or function-scope, there seems to be no use of namespace or module-style development at all. It's possible to simulate namespaces by wrapping entire modules in an object definition, but this is usually too much of a hassle for practicality.Objects. Javascript's object system is, well, crap. Sure, it's ad-hoc like Python, but it has no formal way of creating simple constructors. You can use the "this" object in a function, or create a new instance of "Object" to append methods to, but there are no standards for constructing an object.
Objects do not support destructors. Many might argue that a memory-safe language like Js d…