Talk:1270: Functional

Explain xkcd: It's 'cause you're dumb.
Revision as of 20:48, 30 September 2013 by (talk)
Jump to: navigation, search

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, 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:  |x| = \begin{cases} x & x>0 \\ -x & \text{else}\end{cases}.

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)