Editing 1270: Functional
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 8: | Line 8: | ||
==Explanation== | ==Explanation== | ||
+ | {{incomplete|The concept of functional programming is not explained yet, it is debated if that should be explained before explaining recursion or afterwards or if at all?}} | ||
[[White Hat]] questions [[Cueball]]'s faith in {{w|functional programming}}. [[Cueball]] responds saying, "Tail recursion is its own reward." | [[White Hat]] questions [[Cueball]]'s faith in {{w|functional programming}}. [[Cueball]] responds saying, "Tail recursion is its own reward." | ||
− | + | Functional programming is a famous paradigm (or style) in modern programming that favors functions that can be evaluated like mathematical functions, i.e., the value returned only depends on the input given. {{w|imperative programming|Imperative programs}} often make use of one or more variables that are external to the function that is currently executing. This means that an "imperative function" may return a different result for the same input due to changes in a non-local variable, whereas a "functional function" will in theory ALWAYS return the same result for a given input, though in practice the functional programming languages also support the non-local variables. | |
− | + | Unlike {{w|Procedural programming|procedures}}, functions always return a value. For example, {{w|Sine|sine(x)}} returns 1 when x is 90°. Furthermore, the function may call itself (usually with slightly different parameters), thus effectively starting a loop. This is called {{w|Recursion (computer science)|recursion}}. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | Unlike {{w|Procedural programming|procedures}}, functions always return a value. For example, {{w|Sine|sine(x)}} returns 1 when x is 90°. Furthermore, the function may call itself (usually with slightly different parameters), thus effectively starting a loop. This is called {{w|Recursion (computer science)|recursion}}. | ||
− | In order to {{w|Iteration|iterate}}, imperative programs usually use {{w|Loop (programming)|loops}}. Functional programs usually use recursion instead. | + | In order to {{w|Iteration|iterate}}, imperative programs usually use {{w|Loop (programming)|loops}}. Functional programs usually use recursion instead. |
For example, the {{w|factorial}} function (e.g. "factorial(5) = 5 x 4 x 3 x 2 x 1") can be coded imperatively as: | For example, the {{w|factorial}} function (e.g. "factorial(5) = 5 x 4 x 3 x 2 x 1") can be coded imperatively as: | ||
Line 52: | Line 35: | ||
return 1 | return 1 | ||
− | In this situation, the recursion stops when the argument (n) is not greater than zero. Without the conditional definition, it would be an infinite loop. {{w|Tail recursion}} is a special case of recursion whose very '''last''' operation is to invoke the function itself or return a definite value. The previous example is not tail-recursive, since after the call to "factorial(n-1)", the returned value has to be multiplied by n. | + | In this situation, the recursion stops when the argument (n) is not greater than zero. Without the conditional definition, it would be an infinite loop. {{w|Tail recursion}} is a special case of recursion whose very '''last''' operation is to invoke the function itself or return a definite value. The previous example is not tail-recursive, since after the call to "factorial(n-1)", the returned value has to be multiplied by n. |
This (functional) example is tail recursive inside the helper function: | This (functional) example is tail recursive inside the helper function: | ||
+ | <!-- This is a valid Haskell definition of the factorial function: http://ideone.com/OrCUMp | ||
+ | It is not really helpful to jump from imperative to functional at this point. --> | ||
factorial(n) = factorial_helper(n, 1) | factorial(n) = factorial_helper(n, 1) | ||
Line 75: | Line 60: | ||
In functional programming, tail recursion is detected by the compiler or interpreter and can be executed as efficiently as loops in imperative programming languages. This makes tail recursion an essential programming technique in functional programming. | In functional programming, tail recursion is detected by the compiler or interpreter and can be executed as efficiently as loops in imperative programming languages. This makes tail recursion an essential programming technique in functional programming. | ||
− | Cueball is making a play on words where "Tail recursion is its own reward" is used both in the | + | Cueball is making a play on words where "Tail recursion is its own reward" is used both in the "it is 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". |
− | The title text | + | The title text says that to {{w|Abstract mathematics|abstract mathematicians}} functional programming is both powerful and flexible, as well as intuitive and clear since it comes very close to the way mathematicians usually describe functions. The humorous contrast is that, to non-mathematicians including the software engineers, functional programming can be exactly the opposite (thus being non-intuitive and unclear as abstract mathematics appears to them). Even the mathematicians often spend years of work to discover the subtle mistakes in the lengthy proofs. This leaves the reader unclear as to whether the statement is sarcastic or not. And it is also a reference to a common saying among the fans of functional programming about the imperative programming language, 'C': "C combines the flexibility and power of {{w|assembly language}} with the user-friendliness of assembly language", which is a humorous take on the original saying "C combines the flexibility and power of {{w|assembly language}} with the user-friendliness of a high-level language". |
==Transcript== | ==Transcript== | ||
− | :[White Hat stands behind Cueball, who is sitting at a computer | + | :[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? | :White Hat: Why do you like functional programming so much? What does it actually ''get'' you? | ||
:Cueball: Tail recursion is its own reward. | :Cueball: Tail recursion is its own reward. | ||
Line 89: | Line 74: | ||
[[Category:Programming]] | [[Category:Programming]] | ||
[[Category:Recursion]] | [[Category:Recursion]] | ||
− |