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.

My tenuous Tennyson link

What's the simplest way to put it? My great aunt was the Baroness Tennyson. Yeah, that Tennyson, but a couple of generations down from the poet, and only for a little while. And to call her my great aunt might be a stretch. Before she was the Baroness, she was the widow of my grandmother's step-brother. 

Nonetheless, this tenuous link got me curious about the autobiography of her husband the Baron. It is called From Verse To Worse, which I found to be an auspiciously clever, humorous, and self-deprecating title. The Wikipedia page about him proved tantalizing, particularly in its claim that the autobiography was reminiscent of P. G. Wodehouse. So, I called in another ILL (Inter-Library Loan) favor from my long-suffering wife and got it.

And so far, it does not disappoint. Though I must admit that, for an American, I have a bit of a bias towards all things British, probably from watching too much BBC via PBS as an impressionable child and adolescent. It may also be explained by nature or nurture since my grandfather had a similar bias towards all things British. And here I'm talking about my grandfather on the Jewish side of my family, in which, to my knowledge, nobody ever entered the peerage. My mom says he used to ask her why she couldn't act less Italian and more British. In my defense, at least I have none of that fascination with the Royal Family that so many Americans seem to suffer from.

Some choice quotes from what I've read so far:
At Farringford I started to ride on a Shetland pony called "Dumps." He was about twenty years old then, and the most infernal little brute, and got me off just as he liked. (p. 21)
Previous to this he had been pensioned off in a cottage on the Farringford Estate, where he lived on hard boiled eggs cooked fifty at a time, and on dried goat's flesh. (p. 23)
There are two other memories of mine connected with Suez and Port Said, and these are of passing the Spanish Transports full of troops going out to fight in the Philippines, and of riding in a donkey-race with some of the other passengers, which I won. My mount was called Ta-ra-ra-boom-de-ay. (p. 28)
Amidst these glorious scenes of nature, we had a strange contrast in observing one of the most cruel practices of mankind. In the midst of the grilling heat of the Red Sea, we passed close to two ships taking cargoes of slaves from the interior of Africa to the opposite shore. They were all manacled together and looked a piteous spectacle. (p. 28).
What countries still had slavery at this time (1899)?

I will end there on this sobering note, hopefully with more updates to come, if again some night I cannot sleep. Unfortunately I think I can't scan and post the book since according to my cursory research on UK copyright, it won't be in the public domain until 70 years after the author's death, which will be 2021. I suppose I could try to get the publisher, if they still exist in some form, to release the rights ....

20 October 2011

Partial function application in Perl and PHP

Lately I've been playing with the idea that the only language feature you need to support the functional style is partial application.

I've even been playing with the more extreme idea that the even if you have other language features associated with the functional style, perhaps it is a good idea to limit yourself to partial application. The language features I'm thinking of avoiding are anonymous, nestable, and lexically-scoped functions.

I'll leave it to another post to explain these ideas. All I really want to do here is share my implementations of partial application in Perl and PHP.

Of course these implementations rely on all those features mentioned above: anonymous, nestable, and lexically-scoped functions. So the style I'm experimenting with uses all those features, but only here, in the implementation of the partial application function!