1270: Functional

Explain xkcd: It's 'cause you're dumb.
(Difference between revisions)
Jump to: navigation, search
Line 21: Line 21:
The example above is not tail recursive because the multiplication cannot be evaluated until after its right operand has been calculated. This next example performs its multiplication before the final step - the recursion - and is, thereby, tail recursive.
The example above is not tail recursive because the multiplication cannot be evaluated until after its right operand has been calculated. This next example performs its multiplication before the final step - the recursion - and is, thereby, tail recursive.
e.g. factorial(x) : factorial2(x, 1);  factorial2(x, p): x == 1 ? p : factorial(x-1, x * p)
e.g. factorial(x) : factorial2(x, 1);  factorial2(x, p): x == 1 ? p : factorial2(x-1, x * p)
Cueball is making the pun that "(functional programming) is an end unto itself", which would be both figuratively and literally correct.
Cueball is making the pun that "(functional programming) is an end unto itself", which would be both figuratively and literally correct.

Revision as of 07:32, 27 September 2013

Functional programming combines the flexibility and power of abstract mathematics with the intuitive clarity of abstract mathematics.
Title text: Functional programming combines the flexibility and power of abstract mathematics with the intuitive clarity of abstract mathematics.


Ambox notice.png This explanation may be incomplete or incorrect: if that's the recursion pun I think it is, Randall needs a caning.
If you can address this issue, please edit the page! Thanks.

White hat is asking to what end Cueball uses functional programming.

Recursion refers to functions that invoke themselves at some point to perform a smaller part of their computation - except where the task at hand is simple enough not to require it.

e.g. factorial(x): x == 1 ? 1 : x * factorial(x-1)

Tail recursion refers to a recursive function whose final operation is to invoke the function itself - crucially with no subsequent computation involved. This means that instead of pushing each level of recursion onto the stack, the compiler can simply arrange for the recursive call to jump to the start of the function with the new parameters - effectively turning a recursive call into an iterative loop, whilst retaining the simplicity of a recursive call.

The efficiency and elegance are the literal rewards of tail recursion.

The example above is not tail recursive because the multiplication cannot be evaluated until after its right operand has been calculated. This next example performs its multiplication before the final step - the recursion - and is, thereby, tail recursive.

e.g. factorial(x) : factorial2(x, 1); factorial2(x, p): x == 1 ? p : factorial2(x-1, x * p)

Cueball is making the pun that "(functional programming) is an end unto itself", which would be both figuratively and literally correct.

A simple example of tail recursion is adding a list of numbers together by adding each number one at a time to the 'rest'.

Every time the function is called, all it does is add the first number to 'whatever every other number in the list adds up to'. To figure out 'what every other number in the list adds up to', the function just calls itself, passing every other number in the list.

Eventually it will call itself asking what the sum of no numbers are, which is pretty easy: 0.

This seems a bit convoluted, but actually works out fine because if, say, you ask for the sum of the numbers 1, 2 and 3:

sum( [1, 2, 3] )

this is exactly the same as asking:

1 + sum( [2, 3] )

which is exactly the same as asking:

1  + ( 2 + sum( [3] ) )

which is exactly the same as asking:

1 + ( 2 + ( 3 + sum( [] ) ) )

and if here we can say the sum of no numbers is '0', sum( [1, 2, 3] ) is exactly the same as:

1 + ( 2 + ( 3 + ( 0 ) ) ) )
1 + ( 2 + ( 3 ) )
1 + ( 5 )

In most functional languages, you can write this out really simply. e.g.:

sum [] = 0
sum ( first_thing_to_sum:everything_else_to_sum ) =  first_thing_to_sum + sum( everything_else_to_sum )

or if you're using a less functional language, something like:

function sum(list_of_things to sum):
   if list_of_things_to_sum is empty:
      return 0
      return first thing in list + sum(everything_else_in_list)

The first bit in both cases is the special case for when you've run out of anything to do. This stops the function calling itself forever and never returning, which is the terminating call, or the 'tail call' mentioned above (the end unto itself).


[White Hat stands behind Cueball, who is sitting at a computer]
White Hat: Why do you like functional programming so much? What does it actually get you?
Cueball: Tail recursion is its own reward.
Comment.png add a comment!


Am i the only one considering this can be presented also in opposition to Object Oriented Programming, where tail recursion is very difficult to achieve at execution time, and impossible to achieve at compilation time, due to the possibility of method overloading? 15:17, 30 September 2013 (UTC)

I'm getting the adblock message at the top.. on mobile. On an unrelated note, I laughed and I don't even get it. Edit: I'm also seeing an ad while seeing the message. 06:03, 27 September 2013 (UTC)

This shouldn't be in comic discussion. I have written an updated version of our ad plugin that should only display a message to people using adblock, but we're using a sitenotice for now to test the waters. We'll take it down in about a day, promise!
Also, would you be complicit if I were to move this to the relevant forum? Davidy²²[talk] 06:13, 27 September 2013 (UTC)

I removed that misguided explanation about lists that was not tail recursive. I'm also wondering if we should also mention that tail call optimization is also applicable to mutually recursive functions. In fact proper functional languages will always apply it whether the functions are recursive or not. Maybe emphasize the fact that "The efficiency and elegance are the literal rewards of tail recursion."?

I feel like the examples should be in Haskall[sic], because that is the major functional language... 09:48, 27 September 2013 (UTC) GBGamer117

I think Haskell is more common, but I agree. And to emphasize the clarity, usually if/else blocks are avoided using pattern matching. I.e. tail-recursive factorial can be written as follows:
 fac2::Integer->Integer-> Integer  -- optional function header
 fac2 acc 0 = acc
 fac2 acc n = fac2 (acc*n) (n-1)
 fac::Integer-> Integer
 fac = fac2 1
--Chtz (talk) 10:34, 27 September 2013 (UTC)
Addendum: I did not dare to edit that yet, as I am unsure if this actually helps anyone not familiar with functional programming (and I don't think this page should include a Haskell crash course just to explain this comic). --Chtz (talk) 10:43, 27 September 2013 (UTC)
I think the pseudo-code examples currently in the explanation are easy enough to understand regardless of which programming languages one works in, but the [I'm assuming] Haskell example here in the comments makes no sense to me. Saibot84 12:51, 27 September 2013 (UTC)
Even though they are as clear and intuitive as abstract mathematics ... We could write it in a pseudo-functional language like this:
 fac(n):= fac2(1,n)
The main point of the functional programming paradigm is not that all functions return values (as currently stated in the explanation) but that functions don't have side-effects and don't have an internal state (i.e. they can have parameters, but they don't have variables). This makes recursion the only way to implement things which are usually implemented using loops in procedural languages. Tail-recursion has the benefit that it can be optimized very easily. --Chtz (talk) 21:18, 28 September 2013 (UTC)

I thought about the text a little and don't the the interpretation "tail recursion is an end unto itself" is correct. I think what's going on is a pun of the word "reward". "Tail recursion is it's own reword" makes more sense since you are calling the same function but are "rewording" the arguements. To reword means to re-express something with different words. -- 11:31, 27 September 2013 (UTC)

Why would you start a wall of text with TL;DR? Doesn't that belong at the end, followed by a very short synopsis? Smperron (talk) 13:17, 27 September 2013 (UTC)

Oy, this explanation doesn't actually explain anything. To start with, it needs a definition of "functional programming". Also, a single example of recursion should be plenty: this isn't a programmer's textbook. I really, really don't understand the reward/reword "pun" (if it is such a thing); is the "reword" version really in current use in functional programming circles? If it is, you need to highlight the o vs. a difference (bold and underline) to make it pop out - it took me four readings to notice it. Unfortunately, I don't understand these topics enough to even begin to edit the explanation. (Smperron is right: TL;DR belongs at the end, not the beginning, and it really can't be followed by a wall of text like this.) 14:52, 27 September 2013 (UTC)

"tail recursion is its own reword" - The only instance of this on Google is this page. Searching for tail recursion reword on Google also yields no results on the first page that agree with the proposed usage in functional programming circles. I think the pun explanation should be taken out, as it's clearly wrong. -- 15:55, 27 September 2013 (UTC)

I wasn't happy with the pun line this morning, and worked out what was niggling me earlier this evening, so I changed it to point out that the 'tail call' of a 'tail recursive' function is the end for *all* the invocations. That seems punnier to me. SleekWeasel (talk) 22:17, 27 September 2013 (UTC)

So.... can someone explain why the recursion code examples are written in Python? Schiffy (Speak to me|What I've done) 13:30, 28 September 2013 (UTC)

Why not? While python doesn't eliminate tail recursions (i.e., it lacks the optimization mentioned in the explanation) it is well suited to illustrate the idiom/pattern. Even though there's little reason to use the pattern in python, one can show how it'd look like.
In my experience, simple python code can easily be read (often correctly!) by programmers not knowing that language, which cannot be said about many functional languages. Therefore I tend to say that "python is executable pseudo-code", which makes it perfect for explanatory examples. (Unlike actual pseudo-code, it has well-defined semantics, but like pseudo-code, it's mostly readable for programmers not knowing its exact syntax.) --Das-g (talk) 15:01, 28 September 2013 (UTC)
I changed the functional examples to functional pseudo code. In imperative programming languages it rarely makes sense to write tail recursive functions using recursion instead of a loop. (Sure, there are cases, but factorial is not one of them) --Chtz (talk) 23:42, 28 September 2013 (UTC)
Title text

The title-text explanation is not quite right in my opinion. The joke is that abstract mathematics is not intuitive or clear to *anyone*, including mathematicians. Functional programming borrows many concepts from higher-level mathematics, so understanding the concepts behind functional programming often requires an abstract mathematical mind.

In other words, the title-text explanation is wrong because it claims that a contrast is being drawn between mathematicians and non-mathematicians. This is not the case (at least by my interpretation). 12:01, 29 September 2013 (UTC)

Being a mathematician, I can't agree. Even though I would consider myself more an applied mathematician, I find the basic concepts of abstract mathematics quite clear and intuitive (at least to a level which is required to understand functional programming). I do agree that there are many areas of abstract mathematics neither intuitive nor clear to me, but I am quite sure for people working in these areas this is not the case. --Chtz (talk) 21:06, 29 September 2013 (UTC)


In English math, it's sin(x) as an abbreviation for sine of x -- is sinus something specific to programming, or is it just a typo? (talk) (please sign your comments with ~~~~)

I'm not native English, but sine or just sin in programming is correct. Thanks for your help.--Dgbrt (talk) 17:56, 29 September 2013 (UTC)
I'm not sure if sine(x) is any good example at all. It is a function, but as I tried to explain below, that does not make it relate to functional programming. And I would say that sine(pi/2)=1 and sine(90) is approximately 0.894. --Chtz (talk) 20:23, 29 September 2013 (UTC)
A standard calculator works in degrees and so sine(90°) is exactly 1, while when using radians sine(pi/2)=1 is correct. But this doesn't matter, it always describes how to invoke a function and get the result.--Dgbrt (talk) 10:38, 30 September 2013 (UTC)
However, I don't know any programming languages that use degree instead of radians by default. But that was indeed not my point: The point is that sine is an example of a function (independent of the programming paradigm used) and not a good example of functional programming. --Chtz (talk) 11:14, 30 September 2013 (UTC)
There is a difference between functional programming and using functions in imperative programming

@Dgbrt: I'm not reverting your last rewriting, since I'm fearing it will lead to an edit war. I don't doubt that you are a real programmer, but I somehow doubt that you have experience with functional programming (like e.g. Haskell, Lisp, ...). As I tried to explain, functions in functional programming don't have a state and therefore they don't have statements (especially no return statement). They simply describe functions in a mathematical sense, i.e. they have input parameters and result in a value. (They don't return that value, they just have that value). The if-else construct I was using was supposed to describe a case distinction, similar as a mathematician would describe the abs function: <math> |x| = \begin{cases} x & x>0 \\ -x & \text{else}\end{cases}</math>.

Actually, a functional programmer would avoid such if-else constructs and write (for the non-tail-recursive variant)

 factorial 0 = 1
 factorial n = n * factorial (n-1)

And the interpreter/compiler will automatically find the most specialized case of the definition which can be matched to the input arguments: [1]

Here is a demonstration how a valid Haskell program with tail-recursion and the if-else construct would look like: [2] and this is how it (usually) would be written with pattern matching: [3] --Chtz (talk) 20:15, 29 September 2013 (UTC)

You're right, I am a real programmer. And so I try to explain the "recursive" issue to NON specialists. We should EXPLAIN but not ENHANCE the comic. My two cents...--Dgbrt (talk) 20:34, 29 September 2013 (UTC)
Ok, then the question remains if it is not more important to explain functional programming first? Currently, the second paragraph explains the difference between a function and a procedure in imperative programming and then mostly explains recursion for imperative programming (which I doubt will help understanding the comic -- how is it relevant if and where memory is allocated?). In the next paragraph I originally tried to describe how functional programming is different from imperative programming (after some editing there is not much left of it at the moment, it currently again describes more what imperative programming is). I assume there are more people who know recursion but have no idea of functional programming than the other way around. --Chtz (talk) 20:58, 29 September 2013 (UTC)

I'm not sure "which should not work because the return statement is missing" is relevent. In a given language, functions may only return values when a "return" is given (and immediately that one is given, ending all processing), otherwise giving "undefined", or "void" or the equivalent default state for an explicitly stated return-type. But in others they (in the absence of anything else, like an explicitly terminating "return" well within its own code) will use the bare evaluation of the very last statement within it as the return-value of that function/sub/procedure, if in tested at all by the calling-block (although it's prefereble to "return variable" at the end rather than just put "variable" as the last statement, for readability purposes, especially when it isn't "variable" but something that looks like (or is!) an evaulation/function call in its own right). The above being pseudocode (or "composite relatively common dialect code" not far off various common languages), surely the readability is the big concern, not the fact that (in certain languages, but not others) should not work. (Basically, have I just spent a paragaph saying "don't add that above statement, just put a 'return' into the pseudocode and everyone should be happy"? Yes. Yes, I believe I might have. Still.) 15:35, 30 September 2013 (UTC)

This [4] is a valid functional definition of the factorial function. There are no statements in pure functional programming, especially no return statements. (There are ways to simulate them, but that's beyond this conversation). If everyone thinks that we shall just explain recursion and tail-recursion and avoid talking about functional programming, go ahead and revert it back to before my first attempt to describe functional programming. I agree that functional programming can be hard to get at first, especially to programmers used to imperative programming, but I do think it is worth to know about it. If it is just the brace-less syntax that is confusing, we can use this [5] alternative (very uncommon in Haskell, but I agree that it's more important to make the code easy to understand). --Chtz (talk) 15:52, 30 September 2013 (UTC)
Lest I have made myself unclear (and you're replying to me), I'm happy with the code as is. The 'statement' I mentioned, above, was regarding the added explanatory text (not yours) not any code-statement. The other pseudocodes had "return"s in them, however, so for an argument of readability it might be useful to make that "prod" "return prod", although I (especially as a bit of a Perl fanatic) don't mind either way. I can deal with braces substituted by idents, in pseudocode, much as I can read either XML or YAML encoded data, fairly easily. ;) However, we've got quite a technical discussion going which (unlike code, even deliberately obfuscated Perl!) is not so easily untangled into who is replying to which bit and what they are trying to say (and why). Maybe we should switch to Lojban! 20:48, 30 September 2013 (UTC)
There is no agreement yet, if and when we should introduce/explain the concept of functional programming. At the moment the transition is very abrupt, partly because someone changed my first functional example to imperative code. The tail recursive example is at this very moment exactly the same as this valid functional code (written in Haskell). --Chtz (talk) 21:07, 30 September 2013 (UTC)
I agree, this is still chaos! Please explain "An imperative, recursive (but not tail-recursive) implementation can look like this:", I disagree and there is still no prove helping me or other people to understand. And beside: My first recursive program was to solve a one player game, written in Turbo Pascal in the middle of the eighties of the last century. And it was fast even at that time. --Dgbrt (talk) 21:47, 30 September 2013 (UTC)
I guess you mostly disagree on the non tail-recursiveness? Basically, this can be seen as the recursion can't be replaced by a simple replacement of the return statement with another function call, because after the call another operation (the multiplication by n) needs to be performed before the value can be returned. My original attempt on this article was to switch to functional programming at this point, since it does not make much sense to implement such a simple function recursively in an imperative language (admittedly, the transition to functional programming was way to abrupt). When implementing a function which searches inside a tree it often/usually makes sense to implement it recursively even in imperative languages and with some tricks you can also make this comparatively fast (I assume that was the point of your last two sentences?). To come back to 178.98... My intention was to structure the explanation approximately as follows:
1) Describe the difference between functional and imperative programming (assuming that most readers know what imperative programming is -- if we can't assume that, where shall we start?)
2) Give an example of a simple imperative function (e.g. the factorial function) written with typical imperative constructs (loops, assignments)
3) As this is not possible in functional programming introduce the concept of recursion and define the function recursively (this step was clearly to fast)
4) Explain the benefit of tail-recursion and give an tail-recursive example of factorial (also in functional programming)
5) Explain the actual joke!
6) Explain remaining parts (title text, ...) --Chtz (talk) 22:41, 30 September 2013 (UTC)
On your fourth point, the functional programming example is confusing, and strange. Why are you defining two seperate functions, when a single function would do? For example, an easy way to show this is:
 factorial[0] = 1
 factorial[n] = n * factorial(n - 1)
which, though not valid computer code, is valid mathematical syntax, and shows perfectly what a factorial function, in functional programming, does. The explanation would then be:
 factorial[6] = 6 * factorial[6-1] = 6 * 120 = 720
   factorial[5] = 5 * factorial[5-1] = 5 * 24 = 120
     factorial[4] = 4 * factorial[4-1] = 4 * 6 = 24
       factorial[3] = 3 * factorial[3-1] = 3 * 2 = 6
         factorial[2] = 2 * factorial[2-1] = 2 * 1 = 2
           factorial[1] = 1 * factorial[1-1] = 1 * 1 = 1
             factorial[0] = 1
or something similar to that. GBGamer117 (talk) 05:07, 2 October 2013 (UTC)
I would be totally fine (and originally intended) to have this definition at step 3). If you replace your [ ] brackets by ( ) parentheses, or leave them, it is actually valid Haskell code (and as you point out, [clear and intuitive as] valid mathematical syntax). The evaluation, however would rather go like:
 factorial(4) = 4 * factorial(3)
              = 4 * ( 3 * factorial (2)                 )
              = 4 * ( 3 * ( 2 * factorial (1)         ) )
              = 4 * ( 3 * ( 2 * ( 1 * factorial (0) ) ) )
              = 4 * ( 3 * ( 2 * ( 1 * 1 ) ) )
              = 4 * ( 3 * ( 2 * 1 ) ) = 4 * ( 3 * 2 ) = 4 * 6 = 24
That would actually give a nice example, why this recursion is less efficient than actual tail recursion: During evaluation, you need to build up an entire expression tree which you don't have to do for the tail-recursive way (it does not really matter for this simple function, though).
 factorial(4) = factorial_helper(4, 1) = factorial_helper(3, 4) = factorial_helper(2, 12) = factorial_helper(1, 24) = factorial_helper(0, 24) = 24
The number of numerical operations is actually the same (I omitted the steps of evaluating the products and differences), but you don't have to build up a large expression, before you can actually start multiplying. --Chtz (talk) 07:51, 2 October 2013 (UTC)
Tail Recursion?

Are we really certain "tail recursion" isn't also an innuendo for ongoing sexual relations? Tail is sometimes used as slang, and if it were received regularly, it would be tail recursion. (talk) (please sign your comments with ~~~~)

Explain the concept, not the history?

I think that this page would benefit from simplifying the beginning to explain the concept without providing all of the background. Background can be applied later. I would suggest this:

Recursion is a common programming practice where a function calls itself. This can result in many layers of the function, all of which need to be kept track of until the program can get to the bottom layer. The last step of this process is to return the final value through all of the layers of function calls.
If there is nothing left for a function to do when the lower level returns, then there is no longer a need to keep track of the state of that layer. Instead of creating a new layer, a compiler that is smart enough can overwrite the existing layer with the new layer. This means that the new layer will pass its results directly to whatever initially called the function and not have to waste time passing the results up the stack of function calls. Making use of this optimization is called tail recursion, and it saves both time and memory requirements.
Functional programming is a programming language style that appeals to people who spend a lot of time staring at the notation used to describe higher math. This notation commonly uses recursion and formulas that include entire other formulas as variables in a higher level formula. Tail recursion was first introduced as a more efficient manner of handling recursion within functional programming languages, and they are currently the only programming languages that support this optimization.

Mythobeast (talk) 21:07, 3 March 2014 (UTC)

Frankly, I don't think the point here is about what concept it is. Tail recursion is just one of the many peculiar aspects of functional programming that, frankly, does not make that much different in the long run. (Frankly, a loop is about 20 times easier than tail recursion in about 90% of the cases; same for passing functions around). However, those things are rewarding to play with in and of themselves (and who care about the long run anyway? In the long term, we are all dead). At least that how I think of this slide. magice (talk)
Personal tools


It seems you are using noscript, which is stopping our project wonderful ads from working. Explain xkcd uses ads to pay for bandwidth, and we manually approve all our advertisers, and our ads are restricted to unobtrusive images and slow animated GIFs. If you found this site helpful, please consider whitelisting us.

Want to advertise with us, or donate to us with Paypal or Bitcoin?