X combines the P of Q with the R of Q
« previous post | next post »
The most recent xkcd:
The mouseover title: "Functional programming combines the flexibility and power of abstract mathematics with the intuitive clarity of abstract mathematics."
In order to understand these jokes, you need two or three pieces of background information. As usual, the joke is unlikely to survive the explanation, but you'll be better for it :-)…
First, you need to know by painful experience how difficult it can be to use functional programming to do things that are conceptually simple in procedural terms. As the Wikipedia article explains,
There are tasks (for example, maintaining a bank account balance) that often seem most naturally implemented with state. Pure functional programming performs these tasks, and I/O tasks such as accepting user input and printing to the screen, in a different way.The pure functional programming language Haskell implements them using monads, derived from category theory. Monads offer a way to abstract certain types of computational patterns, including (but not limited to) modeling of computations with mutable state (and other side effects such as I/O) in an imperative manner without losing purity. While existing monads may be easy to apply in a program, given appropriate templates and examples, many students find them difficult to understand conceptually, e.g., when asked to define new monads (which is sometimes needed for certain types of libraries).
If you like such things but happen not to have studied them, you could take a look at the Haskell tutorial "All About Monads", where you'll learn that
To create a monad, it is not enough just to declare a Haskell instance of the Monad class with the correct type signatures. To be a proper monad, the return and >>= functions must work together according to three laws:
1.___(return x) >>= f == f x
2. ___m >>= return == m
3. ___(m >>= f) >>= g == m >>= (\x -> f x >>= g)
The first law requires that return is a left-identity with respect to >>=. The second law requires that return is a right-identity with respect to >>=. The third law is a kind of associativity law for >>=. Obeying the three laws ensures that the semantics of the do-notation using the monad will be consistent.
This is still not quite enough to maintain a bank balance —
Beyond the three monad laws stated above, some monads obey additional laws. The monads have a special value mzero and an operator mplus that obey four additional laws:
1. ___mzero >>= f == mzero
2. ___m >>= (\x -> mzero) == mzero
3. ___mzero `mplus` m == m
4. ___m `mplus` mzero == m
It is easy to remember the laws for mzero and mplus if you associate mzero with 0, mplus with +, and >>= with × in ordinary arithmetic.
The second piece of required background information is the original pattern for the template behind "Functional programming combines the flexibility and power of abstract mathematics with the intuitive clarity of abstract mathematics."
We start with instances of the pattern "X combines the P of Q with the R of S", where Q is known for its P and S is known for its R. Some web examples:
Combines the scope of Solzhenitsyn with the mordant humour of Bulgakov.
… combines the formality of Constructivism with the lively fantasy of Surrealism.
… combines the tangy fruity flavours of cranberry with the roundness of Grand Marnier liquor.
… combines the longer racemes of L. alpinum with the denser flowers of L. anagyroides
… combines the rush of coke with the sensory bliss of Ecstasy.
Back around 1980 or so, some Lisp (or ML?) enthusiast built on this foundation a bitter little remark about the C programming language, which in the Jargon File version is “a language that combines all the elegance and power of assembly language with all the readability and maintainability of assembly language”. [Let me be explicit that this was NOT meant as a compliment.]
There are many variant versions Out There, e.g.
C combines the flexibility and power of assembly language with the user-friendliness of assembly language.
The C language combines all the power of assembly language with all the ease-of-use of assembly language.
C combines the performance of an assembly language with the expressive power of an assembly language.
The C Programming Language — A language which combines the flexibility of assembly language with the power of assembly language.
The concept is that C is barely more abstract (expressive, easy to use, readable, …) than "assembly language", which is basically a symbolic form of the lowest level of machine instructions. And for an interesting take on the issues involved, take a look at Richard Gabriel's classic essay "The Rise of 'Worse is Better'".
So the cited xkcd cartoon turns this around to complain about functional programming language like ML and Haskell (which are not "functional" in the sense of being practical or utilitarian, but in the sense of being conceptually based on mathematical functions).
In appreciating the cartoon, it also wouldn't hurt to understand what "tail recursion" is. For the purposes of the mouseover "combines" joke, all you really need to know about tail recursion is that it's something that has a special status for programs written in functional programming languages. But as Rod Johnson points out in the comments, the fact that "tail recursion" involves a recursive function call, i.e. a function that calls itself (or calls a function that calls a function … that calls the original function), is relevant to the "tail recursion is its own reward joke". The "reward" comes from the fact that "tail" recursion (a recursive call as the last thing a function does) has especially useful implementation characteristics due to potential savings in stack space (though this is actually more relevant to imperative programming languages, as I understand it).
Rod Johnson said,
September 28, 2013 @ 9:26 am
There's more to the tail recursion joke, isn't there? The thing about tail recursion is that it's recursive–the function returns itself as (part of) its result (i.e., it's "its own reward").
[(myl) I think that you're right about the "is its own reward" joke, but not about tail recursion — a tail call is a function call that is the last action of a "function" (which can be a procedural subroutine as well as a "function" in the mathematical sense; and if the function calls itself as its last action, then the tail call is tail recursion.
But the relevant thing is that the function calls itself, not that it returns itself. You're right that a function calling itself connects with the concept of being "its own reward", though. I've modified the post to reflect this.]
GH said,
September 28, 2013 @ 9:44 am
Yes. As explainxkcd puts it: 'Cueball is making a play on words where "Tail recursion is its own reward" is used both in the "it's worth doing on elegance and intellectually satisfying grounds alone" sense and in the sense that "the 'tail call' of a function is its final step, and is the final step (and hence the result/reward) for all levels of a tail-recursive function".'
Wesley Kerfoot said,
September 28, 2013 @ 10:19 am
The potential optimization available with tail-recursive functions is indeed the ability to save in stack space. The language runtime can see that a function is simply calling itself directly and eliminate the previous stack frame after that call. This prevents your program from needing O(n) space where n is the number of recursive calls and just requires constant space. I don't think there's anything special about imperative languages with respect to this, but I know Scheme requires that an implementation do it in order to be considered Scheme.
It is actually possible to implement this optimization yourself in a programming language that does not have it though, it's called "trampolining", here's a python implementation I just wrote http://ideone.com/UjYBLC
Iain Ireland said,
September 28, 2013 @ 10:21 am
In fact, tail recursion is actually much more important for functional programming languages than imperative programming languages. Code that would be written as a loop in an imperative programming language must generally be written as a recursive function in a functional programming language. Tail recursion allows one iteration of the "loop" to be written over top of the previous iteration. Without tail recursion, each iteration of the loop takes up room on the stack. Tail recursion is sometimes a useful optimization for imperative languages, but an absolute necessity for functional ones, to the point that it is often guaranteed in the language standard.
Walter Underwood said,
September 28, 2013 @ 10:33 am
There is one more twist of the form, where swapping the comparison turns a compliment into an insult.
Normal: Combines the beauty of Fiat with the reliability of Ford.
Insult: Combines the beauty of Ford with the reliability of Fiat.
In programming languages, Jamie Zawinski's comment on Perl is typical: It combines the power of C with the readability of PostScript.
[(myl) I hope it was clear that the comments on the C language are meant to be exactly insults of this type, except that the two prepositional phrases reference the same standard.]
mike said,
September 28, 2013 @ 10:50 am
The "X combines the P of Q with the R of S" pattern has also been applied to Perl:
"[Perl] combines the power of C with the readability of PostScript."
… and probably many other languages. I wonder how confident we can be that if the pattern is applied by programmers about programming languages, it's always meant negatively.
As an aside, the cite above is from Jeffrey Friedl's blog (and is actually by Jamie Zawinski), in which Friedl chases down the origins of this oft-heard observation:
"Some people, when confronted with a problem, think 'I know, I'll use regular expressions.'” Now they have two problems."
Michael said,
September 28, 2013 @ 10:56 am
Similar to Walter's car example, Austria has the “railjet” train category, which is said to combine the comfort of flying with the speed of rail travel.
Rodger C said,
September 28, 2013 @ 11:08 am
And I'm from Huntington, WV, which famously combines Northern hospitality with Southern efficiency. I've also heard this of St. Louis and other places in that latitude.
[(myl) Indeed. Similarly, I've heard it said that the French bureaucracy combines Italian efficiency with German punctiliousness.]
Ted McClure said,
September 28, 2013 @ 11:11 am
Is this 'functionally' similar to the description of Washington, DC, attributed to Abraham Lincoln: "A city of northern charm and southern efficiency", using adjectives instead of prepositional clauses?
Rod Johnson said,
September 28, 2013 @ 12:17 pm
Mark: you're right, I meant calls itself.
yoav said,
September 28, 2013 @ 12:40 pm
Somewhat off-topic, but this piece had me make the connection and it seems like a good place to receive answer, so:
Did anyone study/employ tail recursion optimization in the analysis of human sentence processing? (nested relative clauses seem like a good candidate)
And in formal language theory?
D.O. said,
September 28, 2013 @ 1:19 pm
My question is why an elementary operation of, shell we call it, abstract mathematics, namely, distributive law is not used for these witticisms. What's wrong with "Functional programming combines the flexibility and power with the intuitive clarity of abstract mathematics."? Is this intuitive operation, which even middle school students can easily muster, too much to ruin the joke?
Andrew (not the same one) said,
September 28, 2013 @ 1:30 pm
Is this intuitive operation, which even middle school students can easily muster, too much to ruin the joke?
Yes. The basic form is 'combines the P of X with the R of Y', with P and R being desirable qualities. The joke lies in leading you to think you are getting something like that, and then subverting it, either by making P and R undesirable qualities, or by making X and Y the same, or both. If the form of the sentence were not preserved there's be nothing to subvert.
William Ockham said,
September 28, 2013 @ 1:39 pm
Is the set of people who "like such things but happen not to have studied them" an empty set? Functional programming has always struck me as very much an acquired taste.
TonyK said,
September 28, 2013 @ 3:08 pm
Michael, I regularly travel between Budapest and Munich on the Austrian railjet service, and it's comfortable and civilised. (Except of course, during the Oktoberfest.)
Garrett Wollman said,
September 28, 2013 @ 11:06 pm
Just to go a little bit further on tail recursion: theory of computation tells us that *every* loop has an equivalent expressed as tail recursion, and vice versa. Compilers take advantage of this theorem to convert tail calls into loops, since real-life computers are actually imperative and not functional in nature. On the other side, this allows functional languages to implement looping constructs as macros rather than special forms (which in turn means that programmers can build their own rather than being restricted to those offered by the base language).
MattF said,
September 29, 2013 @ 8:58 am
Note that Jamie Zawinski is still around, at jwz.org. He's no longer in the programming game (so much the worse for programming), now owns a nightclub in San Francisco. He still maintains the famous-among-programmers set of over 200 screen savers– downloadable from his website– installed by default on most Linux distributions and on OS X. Includes the classic flying toasters, bouncing cows, jugglers, plumbers nightmares, etc.
MattF said,
September 29, 2013 @ 9:03 am
To make it clear, the OS X version is not installed by default– you need to download it and place the screen savers in the appropriate OS X folder
Pseudonym said,
September 29, 2013 @ 11:08 pm
Sigh.
I've corrected this mistake several times on several different forums. Looks like I have to correct it here, too.
This "law" is not true in general: m >>= (\x -> mzero) == mzero
To see why, consider m = liftIO launchTheMissiles
Belial said,
September 30, 2013 @ 12:38 pm
Ha! ha! ha! Very droll indeed.
Wonks Anonymous said,
September 30, 2013 @ 1:55 pm
Steve Yegge attempted to map the worse-is-better continuum of languages (and other things) onto an ideological scale here:
https://plus.google.com/110981030061712822816/posts/KaSKeg4vQtz
Circe said,
September 30, 2013 @ 2:32 pm
Garrett Wollman said:
This is only true of the LISP family (which are arguably not as "functional" as the ML family). In most (all?) ML family languages, macro facilities are not as powerful as in lisps, and it is typically better to roll a tail recursion by hand (or use list processing functions) than to try to use any generic loping constructs.
Circe said,
September 30, 2013 @ 2:34 pm
Also, important members of the LISP family like EmacsLisp have no tail call optimization.
Matt McIrvin said,
October 2, 2013 @ 11:39 am
In version 1 of the children's programming language Scratch (which is very much not a functional language), tail recursion is the only kind that works! (it's because there are no true function calls, only named broadcasts that can invoke an event-handling script, and state of local variables is not stored in a stack.)
Fortunately they do better in version 2, which adds true function definitions.