30 October 2011

All you need is partial application

I've been struggling to program in the functional style for many years now. Part of the struggle was I didn't really have a good sense of what others had done, so I was fumbling around in the dark. Though reinventing the wheel has its advantages and pleasures, it is best done by choice rather than through ignorance. Google is great, but imperative brainwashing is greater: in the beginning I didn't even know what words to search for to find that I was far from alone. And this was even with the benefit of an expensive education that included an introduction to LISP as an undergrad and a grad class on semantics that used Scheme for its exercises!

The other part of the struggle was that, as with most people, at work I didn't have the luxury of using languages intended to support the functional style.

That brings me to what I want to share here, which is that I've come to a tentative, and, to me, surprising conclusion about some language features that are not needed to support functional programming.

The following features are associated with functional programming.

  • Anonymous functions.
  • Nested functions with lexical scope (NFLS).
  • Partial application. 

There are certainly others (pattern matching?) but they're not my concern here.

My tentative conclusion is that you can get by just fine with only partial application. I don't know of any language that does this, but I've been experimenting with limiting myself to this style, and it has been working out quite well.

First of all, people (including formerly me) make too big of a deal about whether a language supports anonymous functions. To me it is a syntactic red herring because it doesn't matter that much if you have to introduce a name. We are all guilty about caring way to much about brevity (and syntax in general). A more charitable interpretation is that support for anonymous functions is emphasized because it is a good signal that the language has other, more substantive support for functional programming.

Now, NFLS is a more substantive feature, though I think it is still somewhat superficial. Here I'm distinguishing NFLS from closures. NFLS is a syntactic construct whereas closures are a semantic construct: a function bound up with its environment. Closures are a natural consequence of having first-class functions, i.e. functions as values, in a language that supports NFLS.

But my insight, which may be obvious to others but was not to me, is that you don't have to have NFLS to have closures. In particular, you can form closures by partial application, and it is not too inconvenient to have that be the only way to form closures.

To put it another way, to program functionally, you have to be able to pass functions around, i.e. you have to be able to have higher-order functions. In addition, those functions passed around need to have an environment that consists of more than the arguments provided at their call site. So you need closures. But you can get by with partial application alone, i.e. you can get by without NFLS.

For my experiments, I've implemented partial application as a function in Perl and PHP. The implementation uses NFLS, but I don't use NFLS anywhere else in my code; I just use partial application.

I actually think it is not only okay to program this way: it may actually be desirable. I think it may be a simpler mental model that there are just functions, syntactically, i.e. no NFLS, and two ways to apply them: partially and completely.

I also wonder whether in new languages it might be simpler to support partial application as a primitive rather than support the syntactic complexity of NFLS and anonymous functions.

I will close by noting that I have purposefully avoided here any mention of the classic topic (well, classic within some circles) of how objects can be used instead of closures in languages that have no way to form closures. This is the way most higher-order programming gets done today, without the programmer even knowing it, and therefore without any of the fear or disdain that often result when explicit higher-order programming comes up against imperative brainwashing.

No comments:

Post a Comment