How DWiki uses partial function evaluation

December 9, 2006

As part of a longer entry, Muharem Hrnjadovic asks:

I would love to see examples or code snippets that are made possible and/or improved greatly by leveraging functools.partial().

I'm not sure that my example qualifies, but I'll take a shot at it.

DWiki has a WSGI-like processing pipeline to handle requests; they get passed from function to function, possibly getting mutated on the way down and possibly having the results mutated on the way back up.

The pipeline functions look like this:

def TimeLayer(next, request):
  t0 = time.time()
  resp = next(request)
  td = time.time() - t0
  request.log("Time: %.3g sec" % td)
  return resp

Notice how next is called: there is no hypothetical next_next parameter. This means that there's a disconnect between how these functions want to be called and how they want to call the next step in the pipeline (and how the outside world wants to start the pipeline); they want to know the next function to call, but they don't want to have to know the next function's next function (and so on down the line).

The answer is partial function evaluation. All of the next functions, and the function called at the top of the entire pipeline, are partially evaluated functions with the next parameter filled in in the process of building the pipeline.

DWiki predates Python 2.5 and the functools module, so it currently uses a closure and lambda-based approach. However, functools.partial is clearly the better way to write the function that assembles the pipeline; it would come out roughly like this:

def genDwikiStack(stklst):
  # The bottom function takes no
  # next argument.
  cur = stklst.pop()
  while stklst:
    nxt = stklst.pop()
    cur = functools.partial(nxt, cur)
  return cur

(This can also be written as a reduce one-liner, assuming you have more than one function in stklst and you change it so that stklst is bottom to top instead of top to bottom.)

One of the small issues with DWiki's current lambda-based approach is that stack backtraces are somewhat confusing and overly verbose, since they alternate real functions with the lambdas that wrap them. One potential advantage of a real implementation of partial function evaluation is avoiding this, although I suspect that the current implementation doesn't.

Comments on this page:

By DanielMartin at 2006-12-09 21:53:58:

(This can also be written as a reduce one-liner, assuming you have more than one function in stklst and you change it so that stklst is bottom to top instead of top to bottom.)

Or even if you don't make those assumptions:

def genDwikiStack(stklst):
  return reduce(lambda x,y:functools.partial(y,x),reversed(stklst))

reversed returns a sequence iterator that runs in reverse (so no new list is created), and if reduce isn't given an initializer, it returns the only element when handed a sequence with just one element.

This code doesn't work when stklst is empty, but then again neither did the original version.

By DanielMartin at 2006-12-09 22:13:50:

And I have to wonder why Python gave this operation a new name ("partial evaluation") instead of sticking with the standard computer science term: currying. The thing is, "partial" is a word with several different meanings already, even several different meanings I could imagine within computer science. "Curry" is a term with no other meaning outside the kitchen.

If I see a function named "curry", and don't know the term, I'm going to go look it up. If I see a function named "partial", though, I might be tempted to think that I know what it means without necessarily looking up the definition.

By cks at 2006-12-09 22:59:34:

The Python people generally tilt towards clear descriptive names, so I suspect that they felt 'partial function evaluation' was a better name than 'currying'; although the latter is the more technical term, it is (much) more confusing to people who don't already know it.

Written on 09 December 2006.
« What I want out of a Linux partitioning program
Weekly spam summary on December 9th, 2006 »

Page tools: View Source, View Normal, Add Comment.
Login: Password:
Atom Syndication: Recent Comments.

Last modified: Sat Dec 9 20:24:49 2006
This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.