Talk:Functional programming/Archive 3

Archive 1

Archive 2

Archive 3

Gabage collection

A recent edit [1] removed mention that functional languages are garbage collected, and I think this is probably not a good change. Functional languages try to minimize side effects, and memory management is... well nothing but side effects. (You altering some state by allocating/freeing memory, which is inherently a side effect)

Plus, I know of no functional languages that lack garbage collection, and would argue that any language without GC is not a functional language. (It wouldn't even make it possible to avoid side effects) Tejoka (talk) 23:22, 8 October 2008 (UTC)

It seems that there are at least a few FP languages that don't use garbage collection - see this thread at Lambda the Ultimate - but that doesn't necessarily mean that they use manual memory management (more likely something like region inference). Perhaps the way forward is to add back the deleted text, but modify it to talk about (the more generic) automatic memory management, rather than specifically identifying garbage collection. --Allan McInnes (talk) 23:50, 8 October 2008 (UTC)

GC had been mentioned as a reason why functional languages are sometimes thought of as slower than imperative languages. This is based on several assumptions that are not necessarily correct. For example, the use of stack memory removes the need for heap management. Internal list memory management is often complex and a particular functional language will have different techniques for maximizing efficiency and how automatic GC comes into this varies. Several functional languages have the types that can be manually allocated or freed (impure though it may be). I would welcome a section on GC in this and its history wrt FP, but a rationale for poor performance compared to imperative languages doesn't seem like the right place for it. 66.241.94.208 (talk) 09:07, 12 October 2008 (UTC)

I think it is worth mentioning that most (not all) FP languages use GC. GC is an implementation technique, generally not part of the language per se, so it's not the case that the language semantics require side effects. If you had infinite memory you would not need GC. Generally the language is specified in a way that the program has the illusion of infinite memory. You might alternatively say that block-structured imperative languages have the "while" statement (etc.) as a way of getting rid of the "go to" statement, but of course the underlying implementation of "while" loops still use jump instructions at the machine level. We would still say that blocked structured languages foster a goto-less style and some of them even lack the goto statement. 67.122.210.149 (talk) 12:00, 30 November 2008 (UTC)

Obtuse beginning

"In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions [HUH?] and avoids state and mutable data [HUH?]. It emphasizes the application of functions [HUH?], in contrast with the imperative programming style [HUH? HUH? HUH?] which emphasizes changes in state..."

I'm admittedly just a light-duty part-time coder, but I can usually understand tech descriptions of things I'm not familiar with. This beginning is totally obtuse. (The [HUH?] interpolations are my own.) For example, if I don't know what functional programming means, why would you expect me to understand what "mutable data" means? (Yes I know what those two words mean individually, but I have no idea what they mean in this context.)

The ideal encyclopedia article is comprehensible to interested non-experts. Experts aren't going to look the topic up in Wikipedia anyway. —Preceding unsigned comment added by 71.243.10.93 (talk) 21:57, 18 November 2008 (UTC)

We should add some material about functional data structures, but the reality is that functional programming is a relatively advanced topic in programming and the article may never be completely understandable by beginners (articles about advanced math and science topics are often the same way). As for mutability, think of the computer's memory as a grid of squares in which you can write down numbers and look them up later. Mutability means that in addition to writing down new numbers in empty squares, you can also erase existing numbers from old squares and write other numbers in their place. Functional programming is (among other things) a programming style in which you only write down new numbers and never erase old ones. That means that traditional imperative data structures like hash tables (where you add new entries by modifying the table) don't fit into functional style, and you instead use alternative structures like AVL trees (where you add an entry by making a new tree that shares structure with the old tree). If you want to get a high level (but POV) overview, look at John Hughes' paper "Why FP Matters" in the external links section of the article. 67.122.210.149 (talk) 01:38, 30 November 2008 (UTC)

Further comment, on the "huh" items:

• Mathematical functions: I hope at least informally, the concept of mathematical functions (like square root, sine, cosine, etc) is familiar to most programmers. Does it really need to be explained? The difference between a mathematical function and the more general notion of a "function" used in, say, C programming, is that a C function can have side effects and lack referential transparency. Referential transparency means that if you call a function f(x) twice with the same argument, you will get the same result both times. That might not happen with a C function, if it (say) modifies a global variable, or reads data from a socket, etc. (So how do you do referentially transparent I/O, in (say) Haskell? With special values called "actions" that are outside the scope of the article, but basically they are functions whose input is "the external state of the world", and the language enforces that you can supply each such input to an action exactly once).
• Imperative programming: that means you write your program as a series of steps that the computer is to carry out, i.e. with assignment statements, "while" loops, and so on. Almost all conventional languages are like that. In functional programming, you just say what you want the end result to be, and the compiler figures out the steps.
• State and mutable data: mutable data is explained above, state mostly means the same thing. In functional programming you tend to pass most non-constant data around as arguments rather than keeping it as state.

I don't have good ideas about how to modify the lead paragraph to address these issues. I see there was a lot of negotiation that got it to where it is, so I'm reluctant to mess with it without prior agreement. 67.122.210.149 (talk) 11:53, 30 November 2008 (UTC)

Since the "huh" items required explanation, I've added that very same explanation to the article so that it benefits and can be understood by everybody. Diego (talk) 16:10, 30 November 2008 (UTC)

Merge proposal

Someone put this big merge notice on the main article:

{{Mergefrom | Applicative programming language | Talk:Functional programming#Merge proposal |date=November 2008 }}

That other article looks like a pretty small stub. I don't have an opinion yet on whether merge is worthwhile, but I'm sure that the matter doesn't need a big banner on this article. I notice that the editor who placed the banner on the two articles has not yet commented on why the merge should or should not happen. Let's have that discussion on one talk page or the other. LotLE×talk 00:05, 25 November 2008 (UTC)

That other article looks wrong, too. Lisp is not an applicative language in the sense it seems to intend. --FOo (talk) 05:00, 25 November 2008 (UTC)

FWIW, the term "applicative" as I've read it is most suited to Lisp/Scheme of any language. The other article conveys the meaning poorly, but the sense of the term usually refers to the fact that Lisp applies its operations to its own source code... i.e. data structures simply are source code without the distinction between method/function and data that exists in many languages.

I can imagine there being an article just on applicative programming languages, if the meaning were better explained (and appropriately cited). I don't think it would need to be all that long, and it would certainly have prominent pointers back here. But it could make sense. I guess that means a "vote" of: very weak no merge. LotLE×talk 05:49, 25 November 2008 (UTC)

I've never heard the term "applicative" used to refer to the ability to treat code as data (or vice versa). The term "applicative" is most commonly used as a synonym for "functional": applicative languages define programs in terms of function applications. See, for example, the introduction of Stephen Gilmore's popular tutorial on Standard ML, the Webster's Online definition, or indeed Backus' classic functional programming call-to-arms. --Allan McInnes (talk) 07:38, 25 November 2008 (UTC)

I'm surprised that the sense I mention doesn't pop up more prominently in a search. But it does occur in, e.g., http://www.citeulike.org/user/pedagand/article/205727, http://home.pipeline.com/~hbaker1/LinearLisp.html, http://209.85.173.132/search?q=cache:fIidAjh0lVgJ:mcs.une.edu.au/~comp318/Lectures/OldStuff/Lecture_01/lecture_01.pdf+applicative+programming+lisp&hl=en&ct=clnk&cd=43&gl=us&client=firefox-a, etc. Still, the overall "take away" is that Allan McInnes is right that I somehow got an atypically specific meaning in my mind. LotLE×talk 08:16, 25 November 2008 (UTC)

Given that some functional languages are not applicative (at least Concatenative languages), it would be unwise to merge Applicative with Functional. —Preceding unsigned comment added by 198.253.49.6 (talk) 19:22, 5 March 2009 (UTC)

Humor

I resisted the urge to add this to the external links section:

• Conrad L. Barski, M.D. "Functional Programming is Beautiful". A humorous critique of functional programming, in comic book form.

67.122.210.149 (talk) 11:19, 30 November 2008 (UTC)

combinatory logic

I'd appreciate it if some explanation could be added to the description of combinatory logic in the history section to justify its presence there. I don't understand this edit summary [2]. I've certainly never seen Haskell explained in terms of combinatory logic. I've always seen it described in terms of lambda calculus. By contrast, the relation between Lisp (or Haskell) with lambda calculus is obvious and pervasive. It's true there are some esoteric languages like Unlambda that are defined in terms of S and K, but I'm not sure what that has to do with the broad history of functional programming that the history section should present. Maybe the combinatory logic paragraph could be moved further down in the article and expanded slightly, e.g. explaining general recursion as the application of a fixpoint combinator. 67.122.210.149 (talk) 01:01, 15 December 2008 (UTC)

The edit summary is a bit unclear to me as well since, as you mentioned, the lambda calculus forms the basis for Haskell. However, Haskell was one of the first languages to implement lazy evaluation, which used techniques of graph reduction based on combinatory logic. Also, the two approaches are essentially equivalent, and combinatory logic has historic precedent. Perhaps, the present passage emphasizes combinatory logic a bit more than needed, but I feel like we're splitting hairs. A B Carter (talk) 01:02, 30 December 2008 (UTC)

Efficiency

The section on efficiency of FP versus imperative programming had a statement that "For purely functional languages, the worst-case slowdown is exponential" and cited the paper "Space-time trade-offs in structured programming" by DeMillo, Eisenstat and Lipton. This reference, however, was a long way from proving the point. First of all, the cited paper was a short proof of a particular lower bound of the combinatorial relationship between graphs and did not explain the analogy with programming paradigms. An earlier paper by the same authors, "Space and Time Hierarchies for Classes of Control Structures and Data Structures" (JACM, 1976), defines the application to programming paradigms, but it compares only structured programs with goto programs; no mention is made of functional or pure-functional programming. Even if we were interested in goto programs, the strong bound shown in the later paper is not exponential: it claims that a simulation of goto programs by structured programs either runs logarithmically slower or is exponentially larger in the number of statements. Ezrakilty (talk) 16:02, 29 January 2009 (UTC)

A possible citation for the line about lazy evaluation would be from . While it does not directly address functional vs. imperative programming, it points out how lazy evaluation ensuring cost is not paid unless needed, and talks about the memory leak dangers. The simple example of this is an 1000x1000 matrix with all fields initialized to 10. Lazy evaluation strategies allow you to avoid writing any of that actual memory unless you need to update the cells. A trivial example of an asymptotic increase in efficiency by applying lazy evaluation is to create this matrix and then never use it. The eager evaluation strategy requires 1000*1000 writes, the lazy evaluation requires 0. More detail on this can be found by looking at cost amortization. This part thou seems to be a very weak argument as lazy evaluation is not a feature of functional languages.JMBattista (talk) 20:00, 6 June 2009 (UTC)

Phony contrived examples

It's unhelpful to the reader when concepts are introduced or compared using phony examples -- contrived code snippets that supposedly depict a particular style or concept, but in fact do not represent the way any programmer would actually work.

The following example is currently in the article:

# imperative style
target = [] # create empty list
for item in source_list: # iterate over each thing in source
   trans1 = G(item) # transform the item with the G() function
   trans2 = F(trans1) # second transform with the F() function
   target.append(trans2) # add transformed item to target

It is intended to illustrate "imperative" style by eliminating composition, and to contrast with "functional" examples that use it. However, this is a flat lie: imperative-style programmers use composition all the time, even in languages that are even less "functional" than Python, such as C.

Using contrived examples like this amounts to lying to our readers. Unless someone can come up with a really freakin' good justification for things like this, I'm going to remove them. --FOo (talk) 19:46, 25 November 2007 (UTC)

I don't understand this point at all. Of course imperative code that stores intermediate results is used all the time. I write such things on a daily basis (even though I "wrote the book" on FP in Python). There's nothing either wrong, nor even atypical, about the imperative example (other than perhaps being a little bit simpler than most "real life" code). This very simple case can, of course, be done as a listcomp, but if it had a dozen intermediate values, maybe a nested loop, some 'if' blocks, and so on, doing something a lot like this "loop over items, collect intermediate values" is exactly what most everyone does in an imperative style. LotLE×talk 21:25, 25 November 2007 (UTC)

What is it you would like better, anyway? To write "imperative" code that was "as FP as possible"?! Of course you can do that... but it would completely eliminate the point of contrasting coding styles. This isn't a game of coding golf, as an anon poster seems to want; nor is it a tutorial in "best Python practices" or whatever. If you are so overwhelmed by the presence of listcomps in Python, just write the same thing in Pascal instead (except that won't work, since it lacks first-class functions). LotLE×talk 21:36, 25 November 2007 (UTC)

The obvious way that a programmer who didn't use list comprehensions (for whatever reason) would do it is:

target = []
for item in source_list:
   target.append(F(G(item)))

I'm not objecting to having an example of imperative-style code. I'm objecting to having an example that erroneously implies that there exists any programming style that eschews composition. Treating composition as if it were a feature of "functional programming", which must be eschewed in order to create an imperative-style program, is simply lying to our readers. Composition is a normal feature of all sorts of programming languages that cannot even pretend to Python's level of functional-ness. --FOo (talk) 09:39, 26 November 2007 (UTC)

To put it another way: It's not that the example in the article says anything wrong about functional programming. Rather, it claims to be contrasting functional style with a different style, which it labels "imperative". The chief characteristic of that style is that every operation must be done as a separate command, with no composition or other combination of operations. However, this style is a fiction.

Sure, there are cases where people store intermediate results -- generally when those results are going to be used as well, or when they are the result of a long complicated expression. However, what the example here claims is that "imperative" is a style, and that style requires eschewing composition. This is a simply false claim. --FOo (talk) 09:46, 26 November 2007 (UTC)

I'm sorry, this argument looks more sophistical every time Fubar repeats it. Obviously no programming language eschews composition... well, maybe assembly, or some obscure research language. The point for an article on FP, is that pure-FP doesn't allow intermediate results to be stored in the manner that typical imperative code often does. The temporary-value style becomes more "natural" as examples get longer... but snippets in articles like this are, almost by definition, not fully fleshed out programs. The code given is enough to illustrate the point being made, without containing extraneous extras.

If you really want an example where composition, listcomps, etc. become less obvious to the "golfers" here, it only takes adding a line or two, e.g.:

# imperative style
intermed = [] # store intermediate results
target = [] # create empty list

for item in source_list: # iterate over each thing in source
   trans1 = G(item) # transform the item with the G() function
   intermed.append(trans1)
   trans2 = F(trans1) # second transform with the F() function
   target.append(trans2) # add transformed item to target

Of course I could think of some clever way to stick that all into a listcomp, or add some sort of composition. But doing so suddenly becomes "clever" rather than "normal" coding. I certainly don't advocate adding such gratuitous extra lines to the article itself... but for the talk page, it more than suffices to refute the absurdly repeated claim that imperative programmers never (or rarely) store intermediate values. LotLE×talk 18:34, 26 November 2007 (UTC)

How about remaking the examples using C# 3.0? It supports both programming paradigms and has common C-style like syntax, which is well known by most of people. The syntax of Python is not that universal and thus difficult to understand for a non-open source fanatic. --Maxim reality (talk) 08:22, 24 July 2008 (UTC)

This is ridiculous. No competent programmer would ever use the code it LotLE's second example. Secondly, the whole point of the "Coding Styles" section seems flawed. Does encapsulating a for loop in a separate achieve anything semantically? That is the only difference in the end. I hope functional programming is more than a paradigm encouraging hundreds of minuscule functions. Interestingly, both the imperative coding examples will compile to the same thing as any decent compiler (IDK about JIT) will use registers for local variables. The FP example compiles the same with an additional function call.

A good example illustrating the difference between imperative programming and FP would use global state. OpenGL is a good example of global state in C, it stores state for everything :P. However good programmers minimize scope as much as possible. I really don't see the difference this section is trying to make. Ultimately it becomes a matter of aesthetics, that is, syntax + standard libraries. Comparing the two examples in python won't show the difference in succinctness, comparing something like haskell and C might. Either way the examples just don't cut the mustard, they are just too similar. 70.27.182.206 (talk) 21:20, 9 September 2010 (UTC)

It's true that this example could be more illustrative, but mainly because the structure of the "functional" code snippet is not typically functional. List examples are not a good example anyway. The real difference between the two styles is not function composition (which can be done on both), but iteration versus recursion - which is hidden behind the 'map' function whose definition is not shown. Diego Moya (talk) 08:50, 10 September 2010 (UTC)

I've replaced the list example with an algorithmic one. Diego Moya (talk) 09:28, 10 September 2010 (UTC)

Clojure

LauBJensen has repeatedly added Clojure to the lead, in the list of "notable functional programming languages used in industrial and commercial applications by multiple organizations". Clojure, while no doubt a nifty language, is also quite new. So I'm skeptical of claims that it's (a) notable (ok, I've heard of it, but does that make it "notable"?), and (b) widely used in industry. I've asked for references, and the only one forthcoming so far has been a link to Lau's own consultancy website. This strikes me as both a conflict of interest, and a relatively poor indicator that Clojure is widely used. Is there any reason to believe that Clojure is actually notable and widely used? If so, does anyone have references to back that up?

On a related note, I'd prefer not to see the lead become crammed with a list of everyone's favourite functional language. Perhaps it would be helpful to have a more concrete set of criteria for inclusion in the lead than "notable" and "widely used in industry". Any suggestions? Some threshold number of industrial users perhaps? Longevity? Something else? If we can't come up with something, and the list continues to grow, perhaps it'd simply be better not to include it in the lead (i.e. move it in to the body of the article).

--Allan McInnes (talk) 06:11, 27 August 2009 (UTC)

I see that Lau has again added Clojure, this time with a link to his own consultancy, and a link to a blog as a reference. The blog in this case merely reports that Rich Hickey (creator of Clojure) gave a talk somewhere. Again, this hardly indicates wide use. I suppose it might indicate notability. The fact that the Pragmatic Programmers have a Clojure book is perhaps a better indication of notability. But it'd be nice to see some indication of wide industry use, which is after all what the list in question is about. I'm having trouble finding any references to that effect. --Allan McInnes (talk) 06:30, 27 August 2009 (UTC)

I agree with Allan McInnes here. Slightly reluctantly, since Clojure really does look like an interesting language that is gaining traction. And moreover, the second link Lau added is to my friend Chas Emerick, whose company Snowtide I even did a little bit of work for some years back. But while Chas likes Clojure, that's not a big industry player. I think it quite likely that in a couple years this addition will be merited, but not yet. LotLE×talk 07:37, 27 August 2009 (UTC)

As I'm sure you are aware I'm quite new to Wikipedia and therefore I'm probably uknowingly stepping on a few peoples toes. I will maintain my position that your personal oppinion of any given language does not change the facts and so does not belong on informative pages. Nor should those oppinions be permitted to slur the facts. I know of several companies that use Clojure. Among those are 2 of Denmarks largest Energy companies, customers in the national health care industry and others. In America, Chas Emerick is primarily using Clojure now for new developments and the fact that you dont regard him of a 'big player' is irrelevant. Secondly, flightcaster.com has a large data-crunching engine which is entirely made in Clojure as you can read on Clojure Google Group. So looking at this objectively, yes Clojure is used in industry, by several companies in several areas of industry. Please then, do not try to express your personal oppinions on Wikipedia and thereby slur the truth for those looking to get acquanted with industry-grade functional languages. If anyone should for any reason still feel that this addition is not merrited, please search yourselves for as many references as you would like to satisfy your personal criteria instead of battling on a public Wiki page. Thank you.

--LauBJensen (talk) 11:48, 28 August 2009 (GMT+1)

Please don't assume that you know what my personal opinions are, or how they impact my editing. In general, your best bet in Wikipedia is to assume good faith on the part of other editors. Regardless of my personal opinions of Clojure, the fact remains that it is a relatively new language, and thus there is likely to be certain amount of skepticism around claims about its notability or industrial uptake. Wikipedia's policy on verifiability makes it quite clear that assertions, particularly controversial ones, need to be backed up by references to reliable sources. As I mentioned above, neither a link to your own consultancy website nor a mention of the language in a blog post really count as good citations for establishing notability or wide industrial uptake. As the editor wishing to add this material to the article, the burden of evidence falls on you. If, as you say, it's easy to search around and find "as many references as you would like", then you should have no trouble in providing good reliable sources.

Since you are new to Wikipedia, I'd encourage you to have a look through Wikipedia's policies and guidelines. In particular, it would be worth your time to take a look at the policy on verifiability, the policies around how not to use Wikipedia, and Wikipedia's general editing policies. Thanks.

--Allan McInnes (talk) 23:43, 28 August 2009 (UTC)

Thank you for the links, Ive looked through them. Although some of it borders on relevance I maintain my position that since Clojure is used in industry it belongs on the list, regardless of this communities personal language preferences. I will add another reference. Please refrain from editing page based on previous given arguments which are false. Instead I'll recommend to you, to put valid arguments on this page for further discussion. The fact remains: Clojure is widely used in industry. Its verifiable.

Regarding my reference to Snowtides blog: The point was not to look at the content of the blog, but the fact that a Software development company uses Clojure. I'm also adding ThinkRelatives Clojurepage, to show you a 3.rd company using Clojure. /Lau —Preceding unsigned comment added by LauBJensen (talk • contribs) 06:04, 29 August 2009 (UTC)

As I've already mentioned, if it's verifiable then you should have no trouble providing references from reliable sources. A blog entry is not a reliable source. Your own consultancy website is not exactly a reliable source either. Your repeated posting of a link to it is a clear conflict of interest. I realize that you are posting it to provide a reference rather than to promote your company, but by posting you are also bordering on self-promotion, which the Wikipedia community tends to frown upon.

Please note that the list in the lead is not intended to be a comprehensive list of every functional language used in industry. It is merely intended to make clear the fact that, despite popular mythology to the contrary, functional programming is not restricted to academia. The four FP languages that are listed are well-established, have wide name recognition, have been around for a relatively long time, have been used in industry for quite some time, and have had their use widely reported. Clojure is a great language. Rich Hickey has done a really nice job on its design, and I think he's implemented seem really cool features. But I'm afraid that Clojure just doesn't come anywhere near the stature and notability of Erlang, Haskell, OCaml, or Scheme. Since you appear determined to add Clojure to the article, please consider inserting it further down the article (with appropriate references), in a section on industrial use of FP (in general the lead should summarize the article, so the fact that we mention industrial use means we really need an article section on it anyway). To that section we can also add mention of other FP languages that are being used in industry, such as Lisp, Scala, F#, SML, and so on. The Commercial Users of Functional Programming conference is a goldmine for examples.

--Allan McInnes (talk) 06:24, 29 August 2009 (UTC)

The new link you have added is a better reference than the others. --Allan McInnes (talk) 06:27, 29 August 2009 (UTC)

I've gone ahead and created a Use in industry section, as I outlined above. Clojure is included in that section. --Allan McInnes (talk) 09:37, 29 August 2009 (UTC)

The current link goes to somebody's training course, which seems a bit weak, and possibly promotional. I'd prefer some kind of evidence of significant industrial projects being done in Clojure in order to mention Clojure in that section. There is certainly plenty of such evidence (such as CUFP presentations) for Erlang, Haskell, and so forth. 67.122.211.205 (talk) 16:07, 27 September 2009 (UTC)

I agree, the link to the training course website seems self-promotional and does not look like a good-faith reference. Imho, it should be removed. Sohail Mirza 20:34, 4 January 2010 (UTC) —Preceding unsigned comment added by Mirzmaster (talk • contribs)

I changed the cite from the training course to a recent InfoQ article about a medical application. I had already looked around for better evidence of industrial use of Clojure without finding any. Clojure seems pretty marginal for this article to begin with. It's a Lisp dialect whose influence and relevance to FP (as a topic in computer science) is pretty slim (the case for Scala is much stronger). The InfoQ article gives the impression that the application it describes is one of the first times anyone did anything serious with Clojure. I decided against removing Clojure completely in order to avoid edit warring, and because it actually does seem to be getting some traction in the Lisp community. I guess the brief mention is ok. 66.127.55.192 (talk) 05:19, 26 January 2010 (UTC)

Footnotes

Two related issues. I think we overcite some claims, especially in the lead. For example, I really don't think we need four sources to demonstrate that Scheme is "used in industry"; one or two solid ones is more than enough for that point.

Second issue, which will make playing with the first one easier. I'm not sure when it was added, but I reasonably noticed the option of using a "<references> ... </references>" block in the References section to list named refs. These names can then be referred to inline, where needed, without requiring a large and visually disruptive citation template within the text flow. What is produced for the rendered page is identical, but it makes it much easier for future editors. Take a look at my recent edits to see how it works.

Now that I've moved some of the lead refs down to the bottom for safe keeping, I will prune some of them from use as citations in the lead. But they are mostly still used later in article for more specific points, so the current arrangement makes it more flexible to add or remove them from the body/lead as seems best (i.e. they stay available in article). LotLE×talk 19:21, 6 October 2009 (UTC)

Good idea! Thanks for tackling this. --Allan McInnes (talk) 21:31, 6 October 2009 (UTC)

Remove broken link?

"Functional Programming" — Chapter 4 of Advanced Programming Language Design by Raphael Finkel, an introductory explanation of functional programming —Preceding unsigned comment added by Timhoooey (talk • contribs) 02:39, 29 November 2009 (UTC)

I removed it. 66.127.55.192 (talk) 02:07, 27 January 2010 (UTC)

Efficiency

Before, here was a claim that an exponential slowdown is possible, with a reference to a paper. But the paper does not claim that there exist non-pure programs whose most efficient functional variant is exponentially less efficient! However, the logarithmic argument is quite well-known and obvious; so I guess that the person who wrote about exponential slowdown misunderstood the paper. —Preceding unsigned comment added by 93.92.202.116 (talk • contribs)

With respect to efficiency, it should be mentioned that the Fibonacci-example is unfortunate, as the "functional" version is very slow (I guess ~ 2^N) due to the redundant computation. Much more efficient would be a tail-recursive approach, which is admittedly harder to understand for the beginner, see e.g. http://en.literateprograms.org/Fibonacci_numbers_%28Scala%29 Regards Zoglala (talk) 11:35, 18 October 2010 (UTC)

Good point, I fixed it. 75.57.242.120 (talk) 12:24, 10 March 2011 (UTC)

Is functional not declarative?

Functional programming is not categorized under declarative languages, though in fact it should be, in my opinion. The categorization isn't really backed up by citations also... How did this come to be? Or am I missing a vital point here? :) — Preceding unsigned comment added by GerardVanHelden (talk • contribs) 15:57, 18 November 2011 (UTC)

I don't think of them as meaning the same thing, or of functional programming as necessarily being declarative. Functional programming is sort of a nebulous concept, but I'd say its main characteristics are that higher-order functions are first-class values, and that syntactic terms denote unique values (i.e. in pure functional programming, data is immutable). 67.117.145.9 (talk) 09:02, 3 March 2012 (UTC)

Functional certainly makes better headway into declarative than say assembly (which I'll use as a noble example of imperative) .. but compare it to math, and it`s easy to see that it falls short . . so its not a simple yes|no , but to the extent that it is yes, we`re only in the foothills . . .

haskell`s syntax is especially good at declarative in the extent that algorythms can be defined `declaratively`.. but this usage (`declarative`) isn`t that common.

Ebmkhfpfclbkjkjpefepoeoiaggoaonh (talk) 02:44, 4 March 2012 (UTC)

I think of declarative as meaning (e.g.) SQL or Prolog, where you state the data relationships you want, and leave the algorithms up to the compiler/interpreter. Functional programming still involves writing algorithms. 67.117.145.9 (talk) 07:01, 4 March 2012 (UTC)

Actually, no: your understanding of functional is as yet incomplete, you often do not need to type up (or even figure out) the algorithm . . . for example, i can start with the mathematical identity [ factorial (x) = x * factorial (x - 1) ; and factorial (1) = 1 ; for positive integers ] .. and then define the function factorial (x) to return 1 if x is one, and x times factorial (x - 1) otherwise .. the machine ends up doing a loop (building a stack from x..1, and then multiplying 1..x), yet we never told it explicitly to do that .. likewise for fibonacci: 1 for x < 3 and fibo (x-1) + fibo (x-2) otherwise . . . i get even more of a benefit in the case of quicksort = quicksort (lowerhalf) <cat> quicksort (upperhalf) ... I don`t need to figure out the complexities of how the machine actually accomplishes the sort .. I'v merely used the identity that for any sorted list, the upperhalf is after the lower half (and used recursion - devide and conquer) . . . but this is a lot like implicitly defining a value or a function in math .. and it`s at this point that you see we`re only in the beginning of this. Even something simple like fahrenheit can point to where this gets taxing to the cpu (even practically intractable, in that a solution will not be found anytime soon on even a powerful machine/s) -- the slope of fahrenheit (celcius) is 1.8 and fahrenheit ( 0 ) = 32 is sufficient information to derive the algorithm, but without some expert system that knows the rules of math, something like an ambiguous evaluator would need to search an algorithm space like a solver. The search space can be kept quite small in this case (a few hundred) and even a netbook can do this, but fahrenheit (celcius) is a very simple algorythm .. it`s very easy to come up with other examples with huge search spaces.

technical note: informally i said upper|lower half, but in reality it`s not likely to be cut exactly in half (0.5), the machine just picks a value (like the first element in the list) and puts everything below that in the lower `half` (which isnt necesarily exactly 0.5) and everything equal|above in the upper `half` ... for example in python: [ j for j in x if j < x[0]] is the lower `half` ... for an unsorted list (x), there`s a 50/50 chance of each value being above or below x[0] Ebmkhfpfclbkjkjpefepoeoiaggoaonh (talk) 07:46, 5 March 2012 (UTC)

Choose languages that are good examples of functional

There is some discussion on which languages should be included in the introductory paragraph, and obviously some `me too` going on.

Haskell is an excellent example: it exists to realize functional, so even if its only an academic project, it is a well known one and a good example -- i`m not saying it is only an academic project - it isn`t (eg. google perl & haskell)

Some would argue that Haskell is more functional than scheme (or at least further along) .. and that scheme more so than lisp .. but both scheme and lisp are historically important . and good examples of functional in themselves

We don`t have to limit the list to just these three (they are just good, easy examples) .. for example: a case can be made for including clojure on the basis of the widespread familiarity of java (making the article accessable to a wide audience) even if clojure itself isnt in widespread use .. but only if clojure was itself a good example of functional programming - eg. can you do quicksort and pass in a custom (ad hoc) comparison function `(cmp a b)`

My last test (cmp a b) actually brings up an important point: while you technically can do this in plain java (eg. new functional.wrapper () { boolean exec (Object a, Object b) { return a . cmp ( b ); }}) it`s hardly natural -- look at how ugly that is ! ... so yes, you can do functional in java .. but its completely against the grain of the wood .. I would not include java in the list of functional languages (java is widely seen as an excellent example of imperative oo) .. but I can see including clojure in a subsequent paragraph (java is widely known, a java programmer can try it out -- succinct salient working examples are often worth a thousand words)

Excel is a poor example of functional -- eg. show me quicksort in a spreadsheet (and do so passing in an ad hoc comparison function `cmp a b`) .. its not even imperative .. you would have to list the sort in the cells, at which point you the human are actually sorting the data, and just typing it up in excel .. at which point we can say that html or microsoft word is a good example of a functional programming language (they are not!) Ebmkhfpfclbkjkjpefepoeoiaggoaonh (talk) 03:01, 4 March 2012 (UTC)

I don't understand what point you're trying to make about Java, which is an imperative/OO language without a doubt, or Clojure, which is a functional-ish LISP dialect that hasn't been very influential or notable so far (though it is mentioned briefly). Scheme of course was tremendously influential and Haskell is where current development is happening. Excel was mentioned because far more people use it than everything else put together, and Simon Peyton Jones (co-author of that paper) is a leading figure in the FP world. I would have to say on pure technical grounds, calling Excel an FPL is a bit of a stretch, but it has some of the relevant characteristics (it deals with a pile of immutable data). 67.117.145.9 (talk) 07:07, 4 March 2012 (UTC)

It`s too much of a stretch regardless of who`s doing the stretching (excel as fp) .. the java issue is in response to above posts that hinged on the degree to which clojure is used -- I'm saying that the first consideration is the merits of clojure as functional .. I would not list it as a prime example, nor would I devote more than a sentence or two in the whole article .. java is hugely popular, and its easy to load up clojure in plain vanilla java and start working with functional . . in fact I would point out that it is a lisp dialect, and you can do a lot of lisp programming in it (eg. you can probably get through most or all of sicp in it)

I'd also point out that I already spelled out that java is not functional, rather it is imperative oo (you could have just copied/pasted from my post and saved your fingers some effort) .. i get the sense that this article is too polarized/polarizing . . I'm laying out what a solid argument in favor of clojure is, while stopping short of actually advocating it: clojure is not a glowing example of functional, but it is a practical one - in fact, for a lot of people, clojure may be the quickest easiest way to program in something like lisp|scheme - and they can run it on anything with a jvm.

Ebmkhfpfclbkjkjpefepoeoiaggoaonh (talk) 02:27, 5 March 2012 (UTC)

Conflict of Interest . . Excel

This source is from Microsoft (simonpj@microsoft.com), so there is a conflict of interest issue.

Also, the purpose of the article is not to make the case that spreadsheets are functional .. quite the contrary . .

"From a programming language point of view, then, spreadsheets lack the most fundamental mechanism that we use to control com- plexity: the ability to define re-usable abstractions. In effect, they deny to end-user programmers the most powerful weapon in our armory. Can you imagine programming in C without procedures, however clever the editor’s copy-and-paste technology? In this paper, we describe a possible extension to Excel that sup- ports user-defined functions (Section 4). It turns out that support for functions is closely associated with better ... " -- from the source pdf

Here the author points out the lack of ` ... the ability to define re-usable abstractions ...`. This is a knife in the heart of any argument for excel being functional - from the authors themselves .. and easily recognizable to a functional programmer .. without it you can`t do most of the canon of functional programming. (using functions does not `functional programming` make)

The one instance where the author even comes close (but not quite) to saying that a spreadsheet is remotely functional is by his own admission, odd and trivial -- and true of any thing with functions .. (this is not the definition of functional programming) .. the vast majority of programming languages are capable of functional in this trivial sense (and much more so than a spreadsheet) .. so are we going to include the vast majority of languages in the introductory paragraph ? and as good examples of fp?

further more, he`s advocating extentions to excel - it does not actually do what he`s advocating.

There is conflict of interest, a profound lack of notability (can you find an other source anything like this?), all on top of absurdity (that excel is FP is much more than a stretch).

YOU are saying spreadsheets are a good example of functional programming - the authors are NOT !!

The source article is not actually about functional programming, it happens to have an author who is known for functional programming -- if he writes an article about steak at the mall, that will be an article that is not about functional programming by an author known for functional programming.

Calling a spreadsheet functional programming is the most bizarre part of the whole article .. you need to make a case for it .. and you won`t be able to -- spj didn`t even try! Ebmkhfpfclbkjkjpefepoeoiaggoaonh (talk) 05:31, 5 March 2012 (UTC)

Please be careful when removing references, you left a dangling error in the References table (and you did that twice). Diego (talk) 06:57, 5 March 2012 (UTC)

ok, thanks for the tip Ebmkhfpfclbkjkjpefepoeoiaggoaonh (talk) 07:58, 5 March 2012 (UTC)

The idea that SPJ has a conflict of interest because he works for MS Research is completely unconvincing (he's not trying to edit the article or to sell Excel). SPJ is an authority about functional programming, so if he says spreadsheets are FPL's, we should report that. [3] has several other references to spreadsheets as functional programs. So I'm planning to put the comparison back into the article, with an additional cite or two. Note: I commented about this from another address in an earlier section. 64.62.206.2 (talk) 03:37, 18 May 2012 (UTC)

Relying too much on `referential transparency`

There is more to FP than just that .. referential transparency is not the single defining characteristic of FP; it is the single defining characteristic of referential transparency .. so if the only intersect of some x with FP is referential transparency: then that x should go in the article on referential transparency (if at all) rather than here. Ebmkhfpfclbkjkjpefepoeoiaggoaonh (talk) 05:56, 5 March 2012 (UTC)

There's not really any uniform or clear definition of functional programming. It's a slightly nebulous term, but referential transparency is a characteristic associated with it. 64.62.206.2 (talk) 03:41, 18 May 2012 (UTC)

In 'Coding Styles' section - the lisp example is for *factorial* NOT *fibbonacci* (it ought to be for fibbonacci)

Can someone give the lisp code for Fibbonacci please? — Preceding unsigned comment added by Lastoftheoldcontemptibles (talk • contribs) 08:59, 28 May 2012 (UTC)

I'm having trouble saving the edit, but the code looks like this:

(defun fib (n &optional (a 0) (b 1))
  (if (= n 0)
       a
    (fib (- n 1) b (+ a b))))

67.119.3.105 (talk) 10:46, 27 October 2012 (UTC)

I added the above Lisp code but I'm thinking of removing most or all of those Fibonacci examples (they might be better placed in the separate articles about the individual languages). The SML one in particular is bad, since it uses a double recursion (exponential time). If it stays, somebody should at least fix that problem. As an alternative to Fibonacci, it might be useful to show how to convert a direct recursive version of factorial, to a tail-recursive version using a helper function. 67.119.3.105 (talk) 20:12, 4 November 2012 (UTC)

SML Fibonacci removed

I removed the SML example for the reason described above. I don't want to try rewriting it without first installing SML on my computer to test the rewrite, and I don't feel like doing that. But I didn't want to leave the existing wording in place, since it gave a wrong impression that SML was somehow unusually capable of directly expressing the mathematical definition of the function. Of course all the other languages could have done it the same way, at the same performance cost.

removed section

SML A fibonacci function written in SML using pattern matching bears a direct resemblance to its formal mathematical definition: fun fibonacci 0 = 1 | fibonacci 1 = 1 | fibonacci n = fibonacci(n-1)+fibonacci(n-2); In a SML interactive interpreter the function can be called as fibonacci 15; This form allows a mathematician to turn a mathematical function into a computer function with little training in the syntax of the computer language.

67.119.3.105 (talk) 00:54, 6 November 2012 (UTC)

Strategy pattern mis-charactersiation

"for example, the strategy pattern simply dictates use of a higher-order function"

This is incorrect. A strategy interface could have two methods on it, which would require two higher order functions. — Preceding unsigned comment added by 122.59.194.155 (talk) 09:27, 29 January 2013 (UTC)

Functional programming in non-functional languages

The elephant in the room is javascript. Readers of this article are most likely using a client with an embedded javascript engine... Javascript/ECMAScript should be at the top of the list of non-functional languages having "functional features". — Preceding unsigned comment added by Kwagmire (talk • contribs) 23:02, 27 July 2014 (UTC)

author bias

this article is written with a clear bias by the author. — Preceding unsigned comment added by 38.88.190.138 (talk) 20:34, 20 August 2014 (UTC)

Functional Programming not mathematical functions

It is a style of simply building a program using functions. The functions are complete of them selves. Not having side effects or creating them. Functional programming is present in early languages as described about lisp. We can say every computer action is mathematical. And that is correct. However puting everything in the same class does not help. Computers work with characters that are encoded as numbers. That being said means the leadin should express the concepts in layman terms.

Functional programming languages should not be part of the definition. Functional programming has been utilized almost from the beginning of computer development. Functions waere utilized before programming language devalopment. Early computing utilizing subroutines were common on the first stored memory computers. Many programs were nearly all calls to Subroutines that implemented higher level operations. Multiply and divide were subroutines on early machines having only add and subtract. Having care memory subroutines remained in memory when the computer was shut down.

As a programmer we think of functions as being typed. Therefore a mathematical function is one that is of numeric type.

Functional programming is more a concept of functions being defined such that they always operate consistantly. But a useful program has to operate on something external. A function that reads data is not consistant in what it returns. A pure functional language is of little use as it has no input abilities.

An example of a pure functional language would be early Mathcad versions. Before I/O was added. Like a spread sheet all input data is coded in the source. Pure functional languages would have input data coded into the program. And that is workable for some applications like mathcad. Design (engineering) active documents are a good example of usable (practical) functional programming languages.

VisSim is another graphical (functional) programming language. In actuality some functions are dependent on their current state. Integration for example. But sense integration is a mathematically defined function having long history I think such functions built into the language may be exceptions. Aftor all it is a time dependent simulation language.

Anyway functional programming is a hard thing to explain.

An example of a functional language having input is Treemeta. The input stream is the input to the function and its output an abstract syntax tree representation of of its input.

A syntax rule describes a language phrase to be recognized and returns success or failure. A rule always does the same thing with the same input character sequence. It is consistent as the same input always produces the same output.

Every syntax rule is compiled into a function. Because all rules take the same input argument (the position in the input stream) there is no need of a syntax rule having an argument list. The outputs are to language defined stacks.

For example a mathematical expression is a sequence of terms that are added or subtracted. Or could be a single term. Likewise a term is a sequence of factors (or divisors)...

An expression rule describes the mathematical form and it's transformation:

expr = term $(('+':ADD|'-':SUB)term!2)

It is assumed that term will transform it's input in the same manor.

The language has three stacks. The call stack(containing function returns), node stack(contains nodes created by the : operator), and parse stack that contains tokens and abstract tree structures created from nodes and parsed elements by the ! operator. The result of the expr would be a single term or an ADD or SUB tree on the parse stack. i.e. ADD[term,term] an ADD tree.

I would argue that these languages are unique functional programming languages having input. Steamerandy (talk) 21:06, 16 January 2015 (UTC)

Functional design programming

Functional design was practiced on large scale programming project. Reservation systems are an example. Designed top down define all subsystems and functions before puting any code down. All functions were defined in detail as to their input, output and function. Layers of detail before coding. The allowed many programmers to work on the project. Forty plus programmers simultaneously worked on the Ramada Inn reservation systeam. The TWA flight reservation system was done the same way as many large scale projects are done. Very few of these functions have side effects. All side effect functions dealing with I/O or transaction messagong. The Ramada reservation system was a 40 man year project implemented in less then a year.

Top down functional design is closely related to functional programming. Steamerandy (talk) 21:52, 16 January 2015 (UTC)

D language?

http://en.wikipedia.org/wiki/Functional_programming#D <- Why is D chosen as an example of an imperative language that also does functional programming? This trend of filling all Wikipedia pages with advertisements of D makes me vomit. I don't see any reason why D should be considered in this context. It's an unpopular language without formal semantics.. The language author didn't even know what higher order functions are some years ago (see Jon Harrop vs Walter Bright). 84.250.47.87 (talk) 03:00, 17 February 2015 (UTC)

D is pretty similar to C. I found the example helpful in its familiarity. Even if it is unpopular (currently ranked 15th on langpop, over the other example languages) and despite any faults it may have for functional programming (?), it is useful for examples just by being familiar to C-family programmers. --72.226.86.106 (talk) 18:54, 10 July 2015 (UTC)

The section on non-functional languages

First-class functions have slowly been added to mainstream languages. For example, in early 1994, support for lambda, filter, map, and reduce was added to Python. Then during the development of Python 3000, Guido van Rossum called for the removal of these features.[44] However, he later changed his mind, and only reduce was removed,[45] though it remains accessible via the functools standard library module.[46]

This seems to equate first-class functions with lambda, map, filter, and reduce. Python had first-class functions from the beginning (Guido: "... I had made functions first-class objects..."[4]). Python shouldn't be listed as a language that added first-class functions.

C/C++ has passing of function pointers, and C++ templating allow them to be used without fully specifying type. The C++ standard <algorithm> header has many functions which take functions as parameters, and the <functional> header helps make and use function objects. C++11 added anonymous function support, and those lambdas can have closures. Functions are no more and no less first-class than before.

Javascript deserves a mention. Douglas Crockford calls it a "Lisp in C's clothing".[5] It has first-class functions, closures, and anonymous functions, and it's common to pass functions as arguments. --72.226.86.106 (talk) 00:53, 11 July 2015 (UTC)

Fixing the lede

I've reverted Ruud Koot's lede, as it's against WP:JARGON and WP:TECHNICAL, which requires us to provide a description that can be understood by anyone. If the current English intro contains bad English grammar, then let's work in fixing the grammar, but the article still should start with a description that uses layman terms. The more technical description can also be provided right afterwards, for increased precision.

Can you please exactly identify what are the problems with the current wording? Diego Moya (talk) 19:52, 11 August 2013 (UTC)

"a style of building the structure and elements computer programs" isn't grammatically correct English, nor is "not in the program's state". It is not possible to begin discussing the semantics of a piece of writing if it doesn't even begin to be syntactically correct. Exactingly what do you think is wrong with the original lede? —Ruud 21:41, 11 August 2013 (UTC)

It requires the reader to already understand the concepts of "programming paradigm", "computaton", "evaluation" and "application of functions", "state", "mutable data" and "lambda calculus" in order to begin making sense of the definition. The new definition states earlier the main practical aspect of FP, that functions always return the same value given the same input; this follows the advice to write one level down, providing a definition based on concrete and simple concepts instead of complex abstractions. Diego Moya (talk) 06:27, 12 August 2013 (UTC)

I very much prefer Ruud Koot's lede to the current one. It's much more clearly written, and gives a more informative overview of the topic. Functional programming is a programming paradigm, so I don't understand the aversion to mentioning that in the lead sentence (and I don't see the need for a definition like "a style of building the structure and elements of computer programs" which is so vague that it is useless). If a user can't understand what computation or evaluation of a function is, they are not going to be able to understand what functional programming is, no matter how much you dumb down or oversimplify the lead. It's good to avoid unnecessary jargon, but some subjects simply require the reader to have some prerequisite knowledge. For instance, the article manifold doesn't try to target itself towards users who have no idea what a topological space or neighborhood is -- you just can't talk about the subject without bringing these up. Likewise, you cannot accurately talk about functional programming without discussing evaluation, program state, or the lambda calculus. Anyhow, I support reverting back to Ruud Koot's version, and making whatever improvements you want to that, rather than trying to fix the current one. -- Mesoderm (talk) 08:14, 12 August 2013 (UTC)

It's a matter of style (and the current lede includes the term "programming paradigm", so I don't understand where you see any aversion to mentioning it). Nobody is suggesting removing those terms for precision, it's just that there's no need to have them in the first sentence. Other topics that are not functional programming deal with computation, lambda calculus and evaluation, so those are not definitory of FP; but using functions that always return the same result to build programs is unique to this paradigm, so it's a good definition. (And no, I don't think that FP is an essentially complex subject nor that it requires understanding lambda calculus to grasp it). Diego Moya (talk) 13:17, 12 August 2013 (UTC)

I'm sorry, I misspoke -- I didn't intend to say that you had an aversion to including programming paradigm in the first sentence - I meant an aversion to including it with just a wikilink without the (oversimplified/incorrect) definition. Anyhow, I don't want to argue about this either, but I don't think it's just "a matter of style". I think in this case, it's also a matter of being incorrect, oversimplified, and less readable. But now that I've made my view clear on this, I'll let other editors decide what to do about it. -- Mesoderm (talk) 18:55, 12 August 2013 (UTC)

My holiday is over and I'm not planning to spent much time on pointless arguing over over lede sections the comming months, so I'll keep it brief:

1. "building the structure and elements of computer programs" is a vague and confusingly worded synonym for "computer programming". Saying that "functional programming is a style of computer programming" carries the exact same information, except that is can be understood instead of misunderstood.
2. "based on pure functions that produce results that depend only on their inputs and not on the program state":
   • "based on" is one of those ambiguous phrases that should be avoided. As not all functional programming is done purely, "emphasizes" would probably be a more appropriate choice. A verbal noun is missing in this sentence, it should probably be "evaluation".
   • I would say that "pure function" is unnecessary jargon here, one should only have to be thinking about functions in the mathematical sense of the word.
   • "and not on the program state": Depending on how you define program state, this is not even correct. It is mutable state that is avoided in functional programming. But talking about mutable state only makes sense when you are thinking about imperative languages (which wouldn't be an unreasonable assumption to make for most readers, however): an explicit contrast with imperative languages needs to be made, like the previous lede did.
3. "It is a declarative programming paradigm, which means programming is done with expressions and uses no implicit state.": "Done with" is, again, too vague. This is, as currently phrased, not even an accepted definition of declarative programming. "Used no implicit state" duplicates the previous sentence.
4. "In functional code," More duplication of what has already been said (although, arguably, this time it is stated more clearly.)
5. "Eliminating side effects..." Where do these "side effects" suddenly come from? As an expert I know that having functions depend on mutable state is a from of side effect, but we haven't even introduced mutable side effects yet. Any poor PHP programming is going to be hopelessly lost by now.

It would be more effective to improve the previous lede—there certain is much room for improvement there as well—than to continue with this trainwreck: it is even less accessible to layman than the previous lede. —Ruud 17:35, 12 August 2013 (UTC)

Functional versus pure functional in lede

The first sentence is

In computer science, functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.

This sounds like "pure functional programming" to me, rather than just "functional". I would say functional programming is a style where you compose functions to get results, as opposed to getting results via a step-by-step process. I would consider the following functional, though not pure functional (or a good idea).

def get_five_ints():
    return list(map(lambda _: int(input("Enter an integer: ")), range(5)))

"Functional" is a manner of abstraction, but "pure functional" gives the nice guarantees like referential transparency and lazy evaluation. --72.226.86.106 (talk) 02:37, 11 July 2015 (UTC)

The lede - as opposed to?

"so calling a function f twice with the same value for an argument x will produce the same result f(x) each time"

As opposed to all those other computer languages where calling f(x) produces different results each time for the same x? Perhaps there is an important idea there but if so it is pretty fucking badly expressed. Is it just that there are no global variables? If so, yawn. Greglocock (talk) 06:41, 24 April 2017 (UTC)

@Greglocock: I've tried to clarify, let me know if that's enough. It's not just about global variables, but having no state that is not captured in the arguments and return values. Diego (talk) 12:45, 24 April 2017 (UTC)

P.S. Technically you can have global variables in a pure functional language, as long as they're immutable. "Global" is a term describing the scope of a variable, not its changes in state. Having no state changes in any variable in the whole program is a rather strong requirement, which changes the programming paradigm significantly with respect to imperative programming. Diego (talk) 12:52, 24 April 2017 (UTC)

Thanks. So b=2*a is ok, but a=2*a is not? I can see that that is more robust in general, if a tad inconvenient for incrementing indices. Greglocock (talk) 00:31, 25 April 2017 (UTC)

Yes, that's pretty much the essence; destructive updates to named variables are not allowed. The typical way of "incrementing indices" is passing the increased value to a recursive call; functional programming depends heavily on recursion. Diego (talk) 06:16, 25 April 2017 (UTC)

@Greglocock: rand() will produce different results each time. scanner.nextInt() can produce new results each time. With a pure function, a compiler could theoretically decide that a result isn't used so the call is unneeded, or that a result is used a lot and it can be cached. A skipped call to rand() or scanner.nextInt() will affect the results of a program, while a skipped call to fibonacci(n) should not.

Most uses for incrementing indices are made unnecessary in functional programming languages. You would typically use a higher-order function like map, which roughly corresponds to the head of a for-loop, and give it another function, which roughly corresponds to the body of a for-loop. Many other languages have support for these concepts. C++'s <algorithm> library, Java's Stream interface, and Javascript's Array methods all have some kind of map/filter/reduce equivalent, which take a sequence and a function and return a transformed sequence or an aggregate value.

It is theoretically possible to allow updates to named variables within the body of a function, as long as the variables are local. The D programming language allows such updates in its pure functions.[6] --96.232.200.75 (talk) 20:20, 13 June 2017 (UTC)