https://www.explainxkcd.com/wiki/api.php?action=feedcontributions&user=85.218.82.16&feedformat=atomexplain xkcd - User contributions [en]2024-03-28T08:02:38ZUser contributionsMediaWiki 1.30.0https://www.explainxkcd.com/wiki/index.php?title=Talk:1270:_Functional&diff=49608Talk:1270: Functional2013-09-27T08:12:29Z<p>85.218.82.16: </p>
<hr />
<div>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.[[Special:Contributions/50.159.5.112|50.159.5.112]] 06:03, 27 September 2013 (UTC)<br />
: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!<br />
:Also, would you be complicit if I were to move this to the relevant forum? '''[[User:Davidy22|<u>{{Color|#707|David}}<font color=#070 size=3>y</font></u><font color=#508 size=4>²²</font>]]'''[[User talk:Davidy22|<tt>[talk]</tt>]] 06:13, 27 September 2013 (UTC)<br />
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."?</div>85.218.82.16https://www.explainxkcd.com/wiki/index.php?title=1270:_Functional&diff=496071270: Functional2013-09-27T08:08:54Z<p>85.218.82.16: Removed ugly ternaries, put the most simple example which is gcd, removed that list garbage (was false since it was not tail recursive + redundant with first explanation).</p>
<hr />
<div>{{comic<br />
| number = 1270<br />
| date = September 26, 2013<br />
| title = Functional<br />
| image = functional.png<br />
| titletext = Functional programming combines the flexibility and power of abstract mathematics with the intuitive clarity of abstract mathematics.<br />
}}<br />
<br />
==Explanation==<br />
{{incomplete|if that's the recursion pun I think it is, Randall needs a caning.}}<br />
<br />
'''TL;DR:''' After [[White Hat]] questions his faith in {{w|functional programming}}, [[Cueball]] says that "tail recursion is its own reward." This implies the equivalent sentence "tail recursion is an end unto itself," and that's where the pun lies. Tail recursion refers to when a function finishes by going back and calling itself, forming a loop. If you aren't groaning by now, read on.<br />
<br />
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.<br />
<br />
For example, the {{w|factorial}} function has a recursive definition:<br />
<br />
factorial(n) = 1 if n = 0<br />
factorial(n) = n * factorial(n - 1) if n > 0<br />
<br />
which can be coded as:<br />
<br />
factorial(n):<br />
if n == 0:<br />
return 1<br />
else:<br />
return n * factorial(n - 1)<br />
<br />
{{w|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.<br />
<br />
The efficiency and elegance are the literal rewards of tail recursion.<br />
<br />
The {{w|greatest common divisor}} function can be coded as:<br />
<br />
gcd(a, b):<br />
if b == 0:<br />
return a<br />
else:<br />
return gcd(b, a % b)<br />
<br />
Here, the recursive call to gcd is tail recursive since its the last step of the function.<br />
<br />
The first example 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.<br />
<br />
factorial2(n, acc):<br />
if x == 0:<br />
return acc<br />
else:<br />
return factorial2(n - 1, n * acc)<br />
<br />
factorial(n):<br />
return factorial2(n, 1)<br />
<br />
The technique used here is to use a helper function with an additional argument called an accumulator which will accumulate results from previous calls to the function. It is often used to implement tail recursive or iterative versions of recursive functions. This is not applicable for all recursive functions, though.<br />
<br />
Cueball is making the pun that "(functional programming) is an end unto itself", which would be both figuratively and literally correct.<br />
<br />
==Transcript==<br />
:[White Hat stands behind Cueball, who is sitting at a computer]<br />
:White Hat: Why do you like functional programming so much? What does it actually ''get'' you?<br />
:Cueball: Tail recursion is its own reward.<br />
<br />
{{comic discussion}}<br />
[[Category:Comics featuring White Hat]]<br />
[[Category:Comics featuring Cueball]]<br />
[[Category:Programming]]<br />
[[Category:Recursion]]</div>85.218.82.16https://www.explainxkcd.com/wiki/index.php?title=Talk:1266:_Halting_Problem&diff=49211Talk:1266: Halting Problem2013-09-19T16:55:52Z<p>85.218.82.16: </p>
<hr />
<div>I wrote an explanation for the body of the comics, but I believe there are aspects of the title I'm still missing, so I left the incomplete tag in place. [[User:Shachar|Shachar]] ([[User talk:Shachar|talk]]) 07:52, 18 September 2013 (UTC)<br />
<br />
Isn't google already running applications designed to continue running even if some of nodes they run on have a fatal hardware failure? Also, even if the claim would be true in "practical" sense, it would not solve the problem, because as you said, the stopping would be because of reasons external to the actual program. In other words, program running on turing machine will never stop by hardware failure, because turing machine BY DEFINITION doesn't have any. -- [[User:Hkmaly|Hkmaly]] ([[User talk:Hkmaly|talk]]) 08:57, 18 September 2013 (UTC)<br />
:Remembered this is wiki and added it to the actual explanation :-) -- [[User:Hkmaly|Hkmaly]] ([[User talk:Hkmaly|talk]]) 09:10, 18 September 2013 (UTC)<br />
:Several systems are running with redundant nodes. They will not run forever. They are in for example extremely unlikely to outlive the sun. [[Special:Contributions/85.19.71.131|85.19.71.131]] 11:29, 18 September 2013 (UTC)<br />
<br />
"For all practical purposes, this is the correct solution"<br />
:No, it's not. A very practical purpose would be "have my OS kill processes that won't stop". Other one would be "reject installing apps that contain algorithms that don't halt". If the OS assumes "every app will eventually halt" it would kill every process and reject every app. [[User:Osias|Osias]] ([[User talk:Osias|talk]]) 12:15, 18 September 2013 (UTC)<br />
::Changing the paragraph to say "a physical perspective" instead of "all practical purposes" was a good solution. [[User:Osias|Osias]] ([[User talk:Osias|talk]]) 14:16, 18 September 2013 (UTC)<br />
::It would, in fact, kill/reject none since it would find no nonhalters.[[Special:Contributions/178.0.89.106|178.0.89.106]] 20:51, 18 September 2013 (UTC)<br />
<br />
<br />
Google "halting problem" and do a little reeding so you are in the same mindset as Randall. This is a famous computer science problem. You aren't talking about the same thing in comments above. ''&mdash; [[User:Tbc|tbc]] ([[User talk:Tbc|talk]]) 12:30, 18 September 2013 (UTC)''<br />
<br />
What is the joke here? What does "big picture" mean? [[Special:Contributions/62.209.198.2|62.209.198.2]] 16:33, 18 September 2013 (UTC)<br />
:I believe it's related to the quote " In the long run we are all dead." by John Maynard Keynes. [[User:Osias|Osias]] ([[User talk:Osias|talk]]) 18:46, 18 September 2013 (UTC)<br />
<br />
Same kind of humor as in http://www.explainxkcd.com/wiki/index.php?title=221 [[Special:Contributions/176.67.13.14|176.67.13.14]] 18:47, 18 September 2013 (UTC)<br />
<br />
A program with its given input can be seen, as a whole, as a specific program. Therefore the halting function need not take two inputs and is equivalent to a function that takes the two described inputs. Therefore I feel the comment about the number of inputs in the explanation can be removed.<br />
:Yeah, the halting problem on the empty word/input is known to be equivalent to the general halting problem. I think that's the form used in this comic.</div>85.218.82.16