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)