Talk:Functional programming

Archives

/Archive 1

FA nomination

I'm adding it now. This article has seemed to be stable, is one of the better ones I've worked on, and seems to have ironed out the roughness in some wording. LotLE×talk 18:19, 19 June 2006 (UTC)

This FAC nomination will fail for the same reason as the PL FAC nomination. Ideogram 19:07, 19 June 2006 (UTC)

What reason was that. I'm looking this over and it appears to be a fairly easy to read and comprehensive discussion on the subject.--MONGO 20:59, 19 June 2006 (UTC)

Not enough citations. Ideogram 21:27, 19 June 2006 (UTC)

conceives vs views

I'm not going to argue with you on this. Ideogram 18:47, 20 :June 2006 (UTC)

formatting bug

You have a bug in the formatting of the Higher order functions section; two paragraphs run together. I don't know how to fix this. Ideogram 02:04, 21 June 2006 (UTC)

python examples

Using python examples is an excellent idea. Ideogram 17:49, 21 June 2006 (UTC)

I think it's a good choice. Of course, it is (mostly) my favorite language. But in contrast to Lisp, it doesn't demand knowledge of a "special" syntax (or non-syntax, as Lispers like to claim); in contrast to Haskell, the imperative example is actually possible :-); in contrast to Perl, there isn't a lot of special punctuation for laypeople to get distracted by. I considered using an outright pseudo-code, but doing so would both be ill-defined, and would hardly differ much from the Python examples. LotLE×talk 18:02, 21 June 2006 (UTC)

It's a good choice because it's your favorite language. Rely on your strengths. Ideogram 18:13, 21 June 2006 (UTC)

Why wouldn't the imperative example be possible in Haskell? Haskell has imperative features you know (heck, it's even explained a few lines up under the "state" section). I think a this example is very bad, mostly due to the fact that you need to define the compose function, which despite the comment diverts attention from the point. I think a much better idea would be to use some random imperative language for the imperative version (e.g. Python), and a modern FP language for the FP version (e.g. Haskell). I don't think this example shows off the two different techniques, there's too much clutter. —Preceding unsigned comment added by 83.248.109.172 (talk • contribs)

In the discussion in the archive, you'll see that considerable objection was raised in the past about the article being too Haskell-specific. That tends to weigh against Haskell examples where something more "neutral" can illustrate the point. Moreover, using two different languages to illustrate a difference in coding style (where one language works perfectly well), is a big detriment... it looks like it's contrasting the PLs rather than the styles. But in any case, it's hard to see why Haskell would be any more clear for the FP code. Where Python reads:

target = map(compose2(F,G), source_list)

I suppose you might write Haskell as:

target = map (compose F G) source_list

Which, frankly, fails to add some dramatically better clarity. In fact, with a suitable 'compose2' and 'map*' definition, it might be:

target = map* (compose2 (F,G), source_list)

...yes, I know you could write it other ways in Haskell. And in Python also, and in most any language. As to defining the support function 'compose2', that serves two important, though subtle, purposes: (1) It reduces claims from imperative fans that we falsely "cherry-pick" FP code to be dramatically shorter than imperative (the equal length of the samples was carefully chosen); (2) It gives a very brief feel for what is genuinely typical in FP of "building up" HOFs (of course 'compose' is a standard function in many languages, but showing how one builds a HOF in general is useful). LotLE×talk 14:50, 15 July 2006 (UTC)

The point isn't to use Haskell, or any other specific language (perhaps curly-braced pseudo code would be easiest to understand for the majority of readers?), the point is to show of the "flavour" of functional programming, which the current example simply doesn't achieve (dominated as it is, by the definition of "compose"). At the very least this definition should me moved out of the example (showing just what a typical functional programmer would write) and explained in the text (and maybe even give the definition, though I'm not sure it's needed - maybe a link to a Wikipedia page on function composition?). In fact, I'm not sure there even needs to be an imperative comparison (which would remove the claims that we cherry pick examples) - this isn't an advocacy article. I think a short pseudo-code example showing off some HOFs, and the typical "expression style" of programming would be quite enough - I'm not convinced that people who would appreciate this code example need an imperative comparison (shouldn't they look in the imperative article for examples of how typical imperative programming looks?).

Also, I think it may be neat to actually name these examples (i.e. put them in a method). If you do this as well as use a functional language for the examples (supporting easy currying, i.e. partial application) you can show off the "playing with functions as values" one sees in FP. For example:

foo xs = map (f . g) xs -- first version

foo = map (f . g) -- currying, equivalent to first version

Here we simply note that if we partially apply map (by passing (f . g) to it) we get a function which takes a list, which is exactly what we want foo to be, so there is no need to go through the intermediate step of naming the list and then applying it to map explicitly. This is difficult to show off in a language such as Python, but would probably help show off the "flavour" of FP quite a bit. —Preceding unsigned comment added by 83.248.109.172 (talk • contribs)

It would be a lot better, anon, if you would register an account, and especially if you would sign your talk comments.

This article was recently FAC nominated, and as in past talk page discussion, the FAC commentators emphasized the desirability of contrasting with imperative code; the section doing so was recently added (by me) specifically to address that FAC concern. I quite agree(d) with that comment: a large majority of readers of this article will certainly be more familiar with imperative programming than they had been with FP. A contrast isn't there for advocacy (nor for condemnation; occasionally we see some of each in edits), but simply to highlight differences with a style that is more familiar to nearly all readers.

Btw. 'compose' also needs definition in the Haskell prelude. If you really wanted, you could put the same thing in site.py for Python. But the Python version is less of a jump for readers than understanding:

-- function composition

(.) :: (b -> c) -> (a -> b) -> a -> c

f . g = \ x -> f (g x)

LotLE×talk 17:33, 16 July 2006 (UTC)

The point remains. If you want to show off FP compared to imperative you should do it in a way that gives you an idea of what the typical FP programmer would write. The current example is dominated by the definition of compose2 which is something you wouldn't see in any FP language because it will be defined in the standard library already. If you must use a far too trivial example and compare it with some other language, at least leave the "emulation-definitions" out of it (explain it in the text, perhaps) since they wouldn't be part of any *real* FP solution. And again, I don't think the example really shows off anything all that significant. You should show things that emphasize "functions as values" a whole lot more (such as the example I gave above where you leave off the arguments to a function definition because the RHS is a function). —Preceding unsigned comment added by 83.248.109.172 (talk • contribs)

Purity

What about contrasting purely functional and purely imperative programming? Effectively, that means PCF, Scheme, or Haskell vs WHILE or Assembly. The "imperative" Python example uses constructs that were directly inspired by functional programming, like 'foreach'. More pure examples (belonging to no particular language):

i = 0
while i < count(source_list):
trans1 = G(item)
trans2 = F(trans1)
target[i] = trans2
i = i + 1

vs

compose = λf. λg. λx. g(f(x))
map = λf. λlist. append(f(head(list)))(map(f)(tail(list)))
target = map(compose(F)(G))(source_list)

Vagary 04:12, 4 May 2007 (UTC)

Not Scheme, which isn't purely functional, surely! But overall, I can see nothing whatsoever to recommend this change. The imperative version is still Python, rather than "no particular language." It uses 'while' rather than 'for' — I suppose to look a bit more like C — but is no more nor less imperative than the more readable 'for'.

The actual lambdas are kinda cool, I admit. But the point of the example is to contrast different styles within one actual programming language, not to invent loosely defined new languages "because we can". It's not clear whether the hypothetical 'append()' function is or is not purely-functional: given the short example, I can imagine different semantics, which sort of defeats the nominal point. LotLE×talk 14:26, 4 May 2007 (UTC)

My point is that 'for...in...' has a very functional feel to it (list-oriented rather than array-oriented), and the definition of compose is less functional than it could be and kind of syntax-heavy. The while-loop and tail-recursion are the fundamental repetition constructs in the two programming styles, so if we're just going to have one example it should include it. Vagary 21:42, 7 May 2007 (UTC)

If we wanted to stick with Python, the above examples would look like this:

target = []
i = 0
while i < len(source_list):
trans1 = G(source_list[i])
trans2 = F(trans1)
target.append(trans2)
i = i + 1

vs

compose = lambda f: lambda g: lambda x: g(f(x))
map = lambda f: lambda list: ((len(list) == 1) and [f(list[0])]) or ([f(list[0])] + map(f)(list[1:]))
target = map(compose(F)(G))(source_list)

(Which is so ugly I hope it settles the question of whether Python is a functional language.) Vagary 22:20, 7 May 2007 (UTC)

I agree it's possible to write ugly code in every language. As to this funny idea about 'while' being imperative and 'for' being functional... well, I think it's just silly. I guess it maybe comes out of the 'while' being used in the popular imperative language C... but I hardly think Bash, Fortran and PL/I suddenly becomes functional on that basis (nor all the other dozens of "purely imperative" languages with 'for' constructs). LotLE×talk 05:11, 8 May 2007 (UTC)

Not 'for', 'foreach'. It exists almost exclusively in object-oriented languages, all of which have some functional influence. The current imperative example is not imperative so much as it is multi-paradigm. And Python is a functional language in only a degenerate sense. Vagary 05:25, 9 May 2007 (UTC)

Quoting from your own linked article: C#, D, ECMAScript, Java, Javascript, Perl, PHP, Python, REALbasic, Ruby, Smalltalk, Tcl, tcsh, Daplex, Unix shells, and Visual Basic. One notable language without foreach is C.. Like I said, basically you seem to equate imperative==C, which is far too narrow. It's hard to see Perl, PHP, Tcl, tcsh, bash, VB, etc. as particularly OOP; but even if they were, OOP is a variant on imperative (i.e. not functional), which is the point at issue. Not one of the languages listed in that other article is FP (Tcl comes closest, I reckon). LotLE×talk 21:50, 9 May 2007 (UTC)

Okay, then foreach isn't functional, but it's also not imperative: it's OOP. It still doesn't belong in an elementary example of imperative programming. (And for the record: OOP started with Simula, which was heavily inspired by Algol, which was inspired by LISP.) Vagary 07:10, 12 May 2007 (UTC)

WTF?

Why did you add a {{fact}} tag to almost every sentence of the article, Ideogram?! Is this some sort of WP:POINT thing again? LotLE×talk 01:30, 28 June 2006 (UTC)

Would you stop that? I thought you wanted FA status; this is the level of citation you need for FA status. Revert if you don't think it's helpful. Ideogram 10:42, 28 June 2006 (UTC)

Good Article

Congratulations everyone. Good work! --Ideogram 19:52, 8 July 2006 (UTC)

spreadsheets

An anonymous editor recently added a badly worded claim about spreadsheets (and narrowly Excel) being the most familiar FP systems. I took it out, of course. But I wonder if the general idea is worth mentioning concisely later in the article (not lead). There is something FP-ish about spreadsheets formulas; and there are a class of readers who will be familiar with them. Opinions? LotLE×talk 15:56, 18 July 2006 (UTC)

It's probably worth mentioning spreadsheets in the context of FP, although I'm not sure how best to do it. References would probably help, I suppose. Here are a couple for starters:

• The haskell.org "haskellwiki" says in its intro to FP: Anyone who has used a spreadsheet has experience of functional programming. In a spreadsheet, one specifies the value of each cell in terms of the values of other cells. The focus is on what is to be computed, not how it should be computed.
• Simon Peyton Jones has a 2003 International Conference on Functional Programming paper titled Improving the world's most popular functional language: user-defined functions in Excel, which shows in the introduction how spreadsheets can be considered a functional programming language.

--Allan McInnes (talk) 18:30, 18 July 2006 (UTC)

R and S-Plus

Is there a citation for why both R and S-Plus should be considered functional languages? The R FAQ 2.1 "What is R?" mentions that R was influenced by Scheme for it's semantics. In FAQ 3.1 "What are the differences between R and S" the key instance of this appears to be that R has lexical scoping and S does not. This is certainly interesting but I'm not too sure if this automatically qualifies R as a functional language, and it certainly says nothing about S and S-Plus. Abcarter 15:51, 28 August 2006 (UTC)

I added a couple external links to the R article that discuss in some greater detail the FP basis of R. See the three part series Statistical programming with R mentioned there. I haven't worked with S-Plus (R is derived from it: conceptually not in implementation), but I was really happy to see the addition of both, since they are a very interesting little corner of the FP world; and it's relevant that prominent systems for statistical programming chose to use an FP style. R does not wholly eschew mutability, but then, neither does Lisp/Scheme. LotLE×talk 16:37, 28 August 2006 (UTC)

Along the same lines, we could probably add a reference to Mathematica (see here for example), which is widely used in the math community. But I'm not sure we want to get into a situation where we catalog every possible language that provides functional programming capabilities. Perhaps it would be worthwhile to add a small section somewhere discussing the fact that FP has popped up in languages and tools that aren't targeted at professional programmers (spreadsheets - see refs above - statistical and mathematical tools, etc). That belies FP's reputation among programmers as being "hard" and "unintuitive" (of course that last statement is just my opinion, although if I'd love to see someone dig up a reference that backs it up). --Allan McInnes (talk) 16:45, 28 August 2006 (UTC)

Well yeah, there's a danger of too much expansion. But I like R muchly :-)! (Enough so that I didn't add it myself, but was simply happy to see its addition)... and I don't actually care about Erlang or J/K. I wouldn't mind adding Mathematica in the same clause as R/S-plus; perhaps change the parenthetical to "(statistics and symbolic math)". LotLE×talk 16:54, 28 August 2006 (UTC)

Conversely, I don't really care about J/K or R/S-plus that much, but I know Erlang is widely used in industrial settings (and is often held up by the FP community - at least in the circles I frequent - as the poster-child for FP being used in the "real world"). That said, I'd be happy to see Mathematica added in the way you suggest. --Allan McInnes (talk) 17:12, 28 August 2006 (UTC)

Well I'll complete the hat trick by saying I care a great deal about J/K and not that much about R/S or Erlang. I would add that I'm not too sure I would call K an FP language though it does have a type of lambda expression and functions are first-class objects. I don't think I'm trying to be a purist here, but I do think there is a fairly strict notion of what an FP language is in academia and the way notions of FP have emerged outside of academia are somewhat orthogonal to this endeavor. This is a distinction that I think is important to express in the paragraph in question.Abcarter 19:53, 28 August 2006 (UTC)

Do you think we three have a good comedy act, Allan McInnes and Abcarter? We can do our "Who's on first?" bit. On the purity point, I'd definitely say that being pure or "strict" aren't really needed for examples that are given in some general sense. After all, Lisp is one of the best know "FP languages", while actually being decidedly non-pure (mixed paradigm). I haven't worked with J/K, but in having read descriptions, they definitely seem to empahsize the first-class functions, the list/matrix element-wise application, and promote a programming style based on computations rather than flow. And the same is quite strongly true of R (in fact, Erlang isn't really pure-functional either, is it?) LotLE×talk 19:54, 28 August 2006 (UTC)

Either a good comedy act, or the makings of a balanced article :-)

As for Erlang's purity, my understanding is that it's about as pure as languages like SML or OCaml - no mutable variables, but it does permit side-effects for IO and for message-passing between processes. But side-effects are minimized as much as possible within a process (in fact that's considered one Erlang's selling points for constructing robust apps). --Allan McInnes (talk) 20:24, 28 August 2006 (UTC)

(outdent) Who said there wasn't assignment in OCaml? Take a look at http://www.ocaml-tutorial.org/the_structure_of_ocaml_programs for some discussion (quick Google search, maybe better links exist). E.g. (from the URL):

OCaml C/C++
let my_ref = ref 0;; int a = 0; int *my_ptr = &a;
my_ref := 100;; *my_ptr = 100;
!my_ref *my_ptr

Not to say it's recommended, but it's there. LotLE×talk 20:36, 28 August 2006 (UTC)

A fair point. I was aware of refs (SML has them too IIRC). But as you say, their use is discouraged. Similarly, in Erlang one can use the concurrency constructs to produce something like mutable variables. Hence my statement that Erlang was "about as pure as SML or OCaml". Heck, Haskell even provides things like IOrefs. It just does them through a monadic framework, so the underlying mechanism is pure.

Getting back to the original point, I don't think that the "fairly strict ideas of what FP is in academia" to which Abcarter alluded are actually as restrictive as he implied. Referentially transparent IO is pretty much impossible without lazy evaluation, which has led some people to joke that the only real functional programming language is Haskell. Yet most people consider languages like SML, OCaml, and Erlang to be FP languages. From what I've heard about K, it may well qualify too. Of course, references to that effect would be very welcome :-) --Allan McInnes (talk) 21:10, 28 August 2006 (UTC)

IPL

This is a trivial point but it's been bugging me for at least a month. Does anyone have any citation for saying IPL is a functional language. The information of interest that I've found is that it was perhaps the first langauge to work with lists and to implement a notion of recursion. I haven't heard it mentioned in any of the literature that I've come across so far, in particular it is not mention in Backus' paper nor Hudak. If IPL is the first language to implement recursion doesn't it make more sense to simply state that it provided one of the key mechanisms that makes the functional approach possible? Abcarter 19:53, 28 August 2006 (UTC)

Have at it, I'm sure the wording introducing IPL could be improved. LotLE×talk 19:58, 28 August 2006 (UTC)

A Plea for the Concept of Pure Functional Languages

Moving the discussion at the end of "R and S-Plus" to a separate section since the issues are general and I think we may be going round this more than a couple times.

The concept of a pure functional language is essential to understanding the functional programming paradigm. The concept restricts a program to the evaluation of functions, where every function is characterized strictly in terms of their inputs and outputs. Let me say immediately that I am not providing a definition of functional programming; in saying that a pure FL is essential, I am only laying claiming that it is one several features that need to be explicated. With that caveat out of the way let me make a few preliminary remarks.

1. Yes this is what I'm referring to when I say that academia has a strict notion of functional programming. I see something like this definition or its reduction to the prescription of "No side effects" in numerous articles and course notes that I've found in my research.
2. :Academia has a strict notion of what constitutes purely functional programming (well, mostly). But a language does not need to be purely functional in order to be considered a functional programming language. In fact most functional programming languages are impure. The comp.lang.functional FAQ has a brief discussion of the question "what is a functional programming language?" I don't see a problem with mentioning languages that are impure, but generally considered functional (here again, I'll point to the comp.lang.functional FAQ, and specifically the list of "functional programming languages" inclued therein) --Allan McInnes (talk) 04:06, 29 August 2006 (UTC)
3. ::Happy to agree with the "mostly" and didn't mean to imply there wasn't any disagreement or fuzzy edges. Also agree that many languages are generally considered to be FPLs even though they have side-effects. However see my original remarks in point 6 below; I still want to say that a functional language looks upon side-effects as a "bad thing", perhaps unavoidable but needing to be handled in a special way. I did find the Functional Language FAQ definition to have the broadest and most inclusive meaning when compared to what I had seen elsewhere in the literature, but give me some time so I can provide some citations. Note, it's at some odds with the list. It matches what I have been tending to see called an FPL, but it is somewhat restrictive: Scheme, but no Lisp, no APL nor J or K. Abcarter 12:04, 29 August 2006 (UTC)
4. :::J is listed there. It is a bit odd that Lisp isn't, but I just take that as meaning that "Lisp" is a family of languages rather than one exact thing... though I'd expect Common Lisp to be specific. LotLE×talk
5. ::::Sorry, missed that and that's interesting. I'm fairly certain that J and K are roughly the same in terms of the expressiveness of their functions, but don't know much about J's general view of assignment and side-effects. Good point to investigate. Abcarter 20:28, 29 August 2006 (UTC)
6. The concept is vital in academia because it sets up a research program: since programs are restricted to consisting only of functions how can the expressive power and flexibility of functions be extended? The results of this research program has been impressive. And this is what bothers me about the section on Erlang, R and J/K, it fails to capture the interplay between academic research that is pursuing a very idealized goal and a variety of more practical languages that are picking and choosing from the fruits of their labor. If you think about it Erlang, K, Mathematica and R are a remarkably eclectic set of languages that in practice have almost nothing to do with one another.
7. :Section?! I just see the one sentence on it. Well, and the rather brief section on "FP in non-functional languages". Actually, if you had been around here a while longer, you'd notice an earlier round of complaints that there was too much focus on Haskell... which basically means on pure-FP. Some of that criticism had been excessive, even at the time, but I tend to thing that a more expansive tone for general usage is better... albeit certainly with sufficient explanation of the contrast with pure-FP for the hybrid languages (which I think we have). LotLE×talk 01:45, 29 August 2006 (UTC)
8. ::Yep, it's just a sentence, writing quickly and wanted to refer back to the entry. I should mentioned that before I entered the discussion I read through all of the discussion archives. I remember the criticisms of Haskell quite clearly because I thought they were completely off-base. If you had to pick one language that best exemplifies the functional programming approach what would you choose?
9. ::I don't think I have a problem with an expansive tone, but it may only be part of the story. LetTake the list that Allen indicated in his replay to me, list. The entry on FP should be able to provide some explanation for why these languages are listed and not others. Abcarter 12:04, 29 August 2006 (UTC)
10. When someone says, "Yes it's has functional elements but it is not a pure functional language", he means that the language has side-effects.
11. The same meaning is implicitly understood on this discussion page with the remarks on Erlang, Ocml and Lisp. And here an aside: using terms like "pure" and "impure" is asking for trouble because in normal usage they have such strong normative content. But I do intend them as neutral terms. I've heard excellent things about R, find Python delightful, and my livelihood wholly dependent on K. I wouldn't call any of them functional. I may well be corrected on one or more of these languages in the next few days, but whether I am or not will have little effect on my general opinion of these languages.
12. K is a judgement call. It has a number of very strong functional features: besides treating functions as first-class objects, K is all about sequences of pure functions. But it just doesn't care about side-effects. In the end it is a variant of APL that has added those functional elements that extend the natural expressive power of APL.
13. I think academics would view languages such Erlang and the ML family of languages as FP because they take side-effects seriously. Yes they have destructive assignment and other kinds of side effects, but their occurrence is systematically minimized. The design of these languages still share the same concerns as the design of Miranda and Haskell, they are still part of the same general research project.
14. It is only with the concept of a pure FL that you can really apply formal systems such as the Lambda Calculus. The previous points about Erlang and ML can be expanded: Erlang and ML are still FP languages because they approximate the ideal.

Abcarter 01:28, 29 August 2006 (UTC)

There's a distinction worth making between three ideas here: functional programming, functional programming languages, and pure-functional programming languages. It's analogous to the same distinction worth making regarding structured or object-oriented languages.

Functional programming is a programming style. It can be done in almost any language. (I'd argue that it would be impractical to do in a language that doesn't have functions, such as some microcomputer BASICs.) But you can write functional code in C just as much as you can in Haskell, even though C doesn't make it especially easy to do.

Moreover, you can combine functional and imperative programming in the same program, by writing some parts of the code in a functional style and others not. It is not unusual to do this in Lisp, for instance; or to (similarly) write code initially in a functional style, and then use non-functional techniques (such as destructive operators) in optimizing it.

A functional programming language is a language which provides tools for functional programming, and emphasizes it within the language. For instance, I would expect such a language to have various higher-order functions built in, such as map and filter (under whatever names). Ideally, implementations would support optimizations useful for functional style, such as tail-call elimination.

A pure-functional programming language is one that places obstacles in the way of non-functional programming. Not only is it discouraged in the common programming style, it is actively resisted by the language -- for instance, lacking primitives for assignment to variables.

This distinction can also be made wrt structured or object-oriented programming. It is possible to write object-oriented code in C, by implementing your own object system. But C does not natively support or encourage OO, so it is not an object-oriented language. It does support and encourage structured programming, but it permits nonstructured programming (it has goto), so it is a structured language but not a pure structured language. Pascal, which lacks goto, is a pure structured language.

In contrast, Java is an object-oriented language; it not only supports OO, but requires you to use it, more or less: you can't write code that isn't part of a class; and classes make up the standard library. It isn't quite a pure OO language, because not everything is an object, as is the case in (e.g.) Ruby. --FOo 04:38, 29 August 2006 (UTC)

Very happy with this set of distinctions and it could form a basis for a lot of what I would want to argue for. A few comments

1. I think understanding the notion of a pure FP is important towards understanding FP in general.
2. :I don't think anyone's disagreeing with that. In fact, the existing article has an explicitly identified section on purely functional programming. --Allan McInnes (talk) 17:42, 29 August 2006 (UTC)
3. ::OK, I was being coy here. To rephrase: understanding the notion of a pure FPL is essential towards understanding FP in general. Now we may have a disagreement. Abcarter 21:19, 29 August 2006 (UTC)
4. :::Perhaps a disagreement with someone else. But I agree with you. I'm just not sure that I understand what it is you want to see beyond the existing discussion of pure FP. Although I'm sure that discussion could bear some improvement, it seems to me that you're suggesting some other, more wide-ranging changes to the article. If so, what are they exactly? --Allan McInnes (talk) 21:37, 29 August 2006 (UTC)
5. Agree that much the same relation can be seen with structured and object-oriented programming. I do think the issues with these approaches are less problematic. For example, while you get heated discussions about what Java got right about OO you rarely hear someone say that it isn't an OO language. I think you're more likely to hear that kind of thing in the FP community.
6. :Er... I've heard people complain that Java isn't "purely OO". I've heard Alan Kay state that C++ "isn't what I had in mind when I created the term OOP" (even though most people seem to think of C++ as OO). The actual characteristics of an "OO language" are still up for debate. --Allan McInnes (talk) 17:42, 29 August 2006 (UTC)
7. ::Yeah, basically agree. My own sense is that the FP debate tends to be coached more in terms of what is or is not a functional langauge, but it's a very subjective judgement. Certainly nothing interesting to discuss. Abcarter 21:19, 29 August 2006 (UTC)
8. I would probably relabel "Pure Functional Language" to something else, like "Canonical". There appears to be general agreement that languages like Erlang and the ML family are functional and for exactly the reasons you mention, they actively resist the creation of side-effects. I think the idea of a pure functional language is quite restrictive and while an important conception is not quite what is meant.
9. :Such relabelling would be original research. "Pure" has a specific and widely used meaning in the theory of FP. We should give that definition and use it, but we shouldn't choose some word of our own out of fear that readers might think we mean "without sin", or "undiluted", or whatever other meaning "pure" has. Besides, "canonical" has, to my ear, an even more biased connotation. LotLE×talk 17:14, 29 August 2006 (UTC)
10. :I agree with LotLE here. --Allan McInnes (talk) 17:42, 29 August 2006 (UTC)
11. ::Nolo Contendere. I'll watch myself in the future. Abcarter 21:19, 29 August 2006 (UTC)
12. What you're calling "Functional Programming Languages" is a very broad list. More problematic there are substantial differences regarding the degree to which some languages support functional programming.
13. :Ultimately, we should not be coming up with a list of FP languages, or even making the classifications. We should be relying on existing, citable references to make that classification (and to provide a definition of what constitutes a "functional programming language"). Things like the already mentioned comp.lang.functional FAQ, Hudak's paper on the history of FP, and so on. --Allan McInnes (talk) 17:42, 29 August 2006 (UTC)

Abcarter 12:07, 29 August 2006 (UTC)

Proposed Changes

As Allen suspects, I'm suggesting some substantial changes to the article. Allow me to be more explicit.

1. The concept of a pure functional language should be incorporated into the lead section as one of the conceptions of functional programming.
2. The lead section should be followed by a section on the core idea of functional programming. This would expand on three points
   1. The motivation for pure functional languages and their benefits.
   2. The relation between pure functional languages and the development of more expressive functions.
   3. The motivation for a more pragmatic conception of functional programming.

A couple of comments. First, by "expressive functions" I just mean concepts like recursion, curried functions, combining forms, first-class functions, closures and continuations that expand the expressiveness of a function. Second, while I do begin with a heavy emphasis on the notion of pure functional language, its my intent that I end on a broader conception that's in keeping with the present tone of the article.

I haven't made any attempt at these changes because I'm still thinking through how to write this and more important I wanted to sound out some of my ideas with the present editors. Abcarter 01:30, 30 August 2006 (UTC)

Sounds a lot like moving into the realm of advocacy rather than neutral description. This isn't John Hughes' Why Functional Programming Matters after all: it's not our place to push FP as "more expressive". That said, I can see maybe a clause, conceivably an entire sentence, that mentioned "pure functional" within the lead. I think the later section on the topic is pretty good, but a brief foreshadowing might be OK for the lead. LotLE×talk 05:32, 30 August 2006 (UTC)

The practitioners of functional programming see benefits to this approach and there is some consensus regarding these benefits. They could be wrong, in some instances that's my own tentative opinion, but how is it advocacy if I list these benefits with a citation?

Why is it a point of contention to say that functions capable of recursion are more expressive than functions that cannot perform recursion? More generally isn't this a distinguishing feature between the functional and imperative approach? In imperative programming there is a division of labor between expressions and statements, while with functional programming all the work is done with expressions. Historically APL and Lisp are critical to the development of functional programming because these languages were the first to develop types of higher order functions. Without these function types it would be difficult to see how a program could consist entirely of functions (if you don't have recursion then loop statements are essential). More recently these elements have been incorporated into non-functional languages because independent of any concerns with side-effects or referential transparency, notions like mapping functions, closures and type identification are pretty damn cool and make life easier for the programmer.

I'm proposing more than just adding a sentence. The first paragraph will need to be restructure so that the different conceptions are related to one another.

I'm also prosing that the concept of pure function be given more priority, not in a section by itself, but in the one I outlined above. The concepts of higher-order functin and recursion are auxiliary to the conception of a program composed only of functions that are charcterized strictly in terms of their inputs and output.Abcarter 12:22, 30 August 2006 (UTC)

OK, I haven't heard anything for awhile so I've made the proposed changes to the lead. Most of the changes are additions and I tried to keep changes to the original text to a minimum. The one exception is the second sentence that I thought spoke most directly to my concerns of pure function so I worked it into the changes. I added the intro sentence because I think the first thing the reader should be aware of is that there is no agreed definition. I also added a sentence on the broader conception of FP to more clearly coordinate it with the rest of the section.

I'm sure you'll let me know what you think :) Abcarter 17:35, 31 August 2006 (UTC)

---

I've been fussing a lot about the notion of a pure functional language because it embodies some points that I think are essential to understanding FP, but I've just realized that there is a different way to express my concerns that could be less contentious. The functional style means to perform tasks with pure functions, mathematical functions that can be characterized strictly in terms of a mapping from one domain to another. Languages like Miranda and Haskell only allow pure functions. There are many other functional languages that include assignment and other types of statements that effect state, but nonetheless merit the term because there is still a strong emphasis on pure functions to do the heavy lifting. More generally any program is functional to the extent to which it achieves its goal through the use of pure functions.Abcarter 13:58, 30 August 2006 (UTC)

Circumlocutions

A recent change to the lead introduced what sounds to me like a very tin-eared circumlocution that digressed into "the many definitions". Almost every article on WP starts with the actual title of article, and is followed by a simple predicate that gives the broadest sense of the term. Whenever a reader needs to read through a one-hand/other-hand dialogue before finding out what the topic is, you know something is wrong. Let's take a look at versions, and see if something really needs changing:

Comparison

Prior consensus	Abcarter rewrite	Comment
Functional programming is a programming paradigm that conceives computation as the evaluation of mathematical functions and avoids state and mutable data.	The definition of Functional programming is a matter of some disagreement. The common thread is a conception of computation as the evaluation of mathematical functions and avoids state and mutable data.	In consensus version, first six words already tell reader "what it is" (a programming paradigm). Ok, which paradigm? The one "that conceives computation as...". In the Abcarter version, I can read the entire first two sentences, and still be scratching my head wondering "so what IS IT?!"
Functional programming emphasizes the application of functions, in contrast to imperative programming, which emphasizes changes in state and the execution of sequential commands.	The narrower conception is seen in the field of language-design and stands in opposition to imperative languages. In contrast to imperative languages that operate by modifying state, functional languages consist solely of the execution of mathematical functions so that mutable data and other side effects are entirely avoided.	pending
Functional programming is defined more by a set of common concerns and themes than any list of distinctions from other paradigms.	The broader conception views functional programming more as a set of common concerns and themes than any list of distinctions from other paradigms.	I would probably be happy with a slight rephrasing of the consensus to read: "A broad conception of functional programming defines a set of common concerns and themes rather than a list of distinctions from other paradigms." I'm fine with that, just be sure to keep parallel structure with the previous part on the narrower conception.
Often considered important are higher-order and first-class functions, closures, and recursion.	The result is a functional style that makes use of the concepts that have been highlighted by or have emerged from the development of functional languages. The more central of these concepts are higher-order and first-class functions, closures, and recursion.	The consensus version is more concise, more encyclopedic in tone, and more accurate. And most of all, it avoids complex circumlocution I have no problem with it being reworded. But how is it inaccurate?
Other common features ...	Other common features ...	sentence looks unchanged
Functional programming languages have largely been emphasized in academia ...	Functional programming languages have largely been emphasized in academia ...	final para looks unchanged

LotLE×talk 17:37, 31 August 2006 (UTC)

Discussion

I added the intro sentence because I thought it was true and anyone wanting to learn about functional programming should know that from the start. Presumably this is the reason the FP FAQ does the same thing when giving a definition of "functional programming language" and "pure functional programming language". Beginning with the broadest meaning has it's own bias because the the breadth of the meaning is a part of the controversy, certain it is part of the disagreement I have with you.

On a side note why revert all my changes when the only objection you express is with the first sentence. Delete that and we can discuss it.

I believe your changes are dramatically worse in every clause, and the existing version reflects carefully negotiated consensus. A substantial change to the lead should usually be discussed first on the talk page (with specificity, not just "I think I might want to change it)... and at the least, it is the right of any editor to revert such change in order to bring it to the talk page. There's a guideline that says this somewhere if you want me to dig around for the exact language. But basically, the sequence should be (0) propose change on talk (semi-optional); (1) make change; (2) if no objection, fine; otherwise other editor copies it to talk; (3) dicuss changes on talk, leaving longstanding consensus in place in meanwhile. LotLE×talk 18:04, 31 August 2006 (UTC)

OK, I'm cool with that, just asking for procedure.Abcarter 19:02, 31 August 2006 (UTC)

Concur with LotLE here: the revised first sentence did not follow Wikipedia style. I agree that it's worthwhile to make it clear that the definition of functional programming is somewhat fuzzy. But not in the first sentence. --Allan McInnes (talk) 19:44, 31 August 2006 (UTC)

Never wedded to the intro sentence just to marking the disagreement. But can you give me a citation in Wikipedia where this point of style is discussed?Abcarter 20:26, 31 August 2006 (UTC)

You might try here, here, or here. --Allan McInnes (talk) 20:43, 31 August 2006 (UTC)

I added one sentence at the beginning and shifted the first over. Yes the word "paradigm" has been dropped but otherwise the sentence is unchanged. Are you saying that without the word the sentence is basically without content? And are you also saying that something like a clear conception of functional programming can be provided in two sentences?

Take a look at Object-oriented programming for a good analogy. It begins:

In computer science, object-oriented programming is a computer programming paradigm. Many programming languages support object-oriented programming (ref)....

Actually, I'd rather it not have that initial clause, since the "computer programming paradigm" already conveys the fact that it has to do with computer science. But basically, that's a pretty good example of how articles should read. Or take a look at any Featured Article (in any field of inquiry). I can guarantee that not a single one starts with a circumlocution. What the comp.sci.fp FAQ does is only a loose guideline for us: it's a good source of references, but the stylistic conventions of a FAQ are not close to those of an encyclopedia. LotLE×talk 18:22, 31 August 2006 (UTC)

Is your objection just that I begin the lead with this disputed sentence or with the actual content of the sentence? If only the former then I think we can come to some agreement so long as the initial sentence remains neutral. I looked up "Deconstruction" and it begins with the fact that the term was coined by Derrida. This is a simple fact but it hardly does much to explain the term. The lead is quickly followed by a section talking about its disputed meaning. I'm happy to begin the lead with something like, "Functional Programming is a paradigm first developed in the 70's . . . ". Not that necessarily but something that doesn't bias what I feel is a very real disagreement about meaning.Abcarter 19:02, 31 August 2006 (UTC)

Both. The main thing is that the lead fails to start in standard WP style: "Topic Foo is ...". Discussions of different definitions rarely belongs in the lead at all, but certainly never in the first sentence of the lead. But even for something later in the article, the tone is wrong: "The definition of Functional programming is a matter of some disagreement." That's just extra words to no purpose. If there is disagreement, just explain it without the filler: "According to Gomez, FP is defined by...; in contrast, Lin defines FP as..." There's no need to "vamp until you're ready" to present the actual disagreeing definitions (even assuming there really is such disagreement, which I do not actually believe anyway; as opposed to mild difference in emphasis). LotLE×talk 19:42, 31 August 2006 (UTC)

FWIW, Deconstruction isn't as minimal as you say. It actually starts with a fairly detailed sentence:

The term deconstruction was coined by French philosopher Jacques Derrida in the 1960s and is used in contemporary humanities and social sciences to denote a philosophy of meaning that deals with the ways that meaning is constructed by writers, texts, and readers and understood by readers.

After the first sentence, it indeed gets into different senses, which I probably would not have done if I had worked on the article. I do notice the article is flagged as needing a rewrite, though I have no idea exactly why that is (it may be one editor who thinks so, with others disagreeing, for example). I'd also rather have it start "Deconstruction is a term coined..." just for WP style. But anyway, in ten word we get the "main summary" about its philosophical coining. Read a few words more to find out when this happened, a few more to find out what fields it is used in, and a few more words to get some broad sense of what it is (a philosophy of meaning). It's a pretty good first sentence in unfolding more details as a reader goes along. Even stopping at ten words, you get a good sense, and each new relative clause elaborates a bit more. LotLE×talk 19:52, 31 August 2006 (UTC)

In regards to the sentence beginning "The result is a functional style". The key thing I'm after is to tie together the narrow and broad conception. The narrow conception issues from a largely academic environment that has developed a number interesting mechanisms in its pursuit of functional languages. The broad conception takes a more pragmatic attitude that makes use of these mechanisms where they see fit. If you think I'm mistaken about this connection then explain why, otherwise reword it in whatever way you like so long as this connection is made clear.Abcarter 19:14, 31 August 2006 (UTC)

I've changed the second sentence so that it's back to its original wording. The original is less awkward and under the circumstances more accurate. Adding "A broader conception" to the third sentence is a clear improvement. However the phrase "especially 'purely functional ones'" is out of place. The term "purely functional" hasn't been defined and it appears to make the following sentence imply that some of the listed languages are purely functional. Certainly this has nothing to do with what I've been driving at so this one is your call. Abcarter 04:23, 1 September 2006 (UTC)

I don't care about the "narrower" thing, I was just trying to get the contrast you wanted. But actually, I think the "broader" implies the prior thing was "narrower" well enough by itself. I see the "especially 'purely functional'" as a sort of "forward promise". It's not that readers will know what it means yet at that point, but they know to look for the meaning if they keep reading the article (and if they don't, it's not hard to brush off the parataxis as inessential). Similarly, I don't think readers of the lead (necessarily) yet know what "first-class functions" or "state and mutable data" are... but likewise we've made a promise to explain those ideas later in the article by mentioning them.

Still I'm happy to find a different phrasing. Or even going back. But I think you are right that a concise mention of "pure functional" is worth having in the lad. I guess a whole sentence would be OK, but I like a clause better. We get to a better definition soon enough after the lead (or we will, once that section is improved). LotLE×talk 04:32, 1 September 2006 (UTC)

Pure functions

I've never really liked the examples in the "pure functions" section of the article, nor all that much the text introducing them. They're not really wrong, but they also don't feel like they jump out in pointing the right concept. Every time I read the section, I read it several times to figure out exactly why the samples are as they are... which is more work than should be needed. Anyone (e.g. Abcarter) want to give a try at tightening up that section? LotLE×talk 20:35, 31 August 2006 (UTC)

Well there's one effing serious point of agreement between us. Might be a good point to begin since it would be a good basis for further discussion. I'll see what I can do. Abcarter 21:18, 31 August 2006 (UTC)

This section also lacks an explanation of how one can carry out operations like getting a random number or print out the result of comptations in a purely functional language.

Arbitrary (programming) language changes

An anonymous editor capriciously changed the Python example of imperative vs. FP styles to a Ruby one. Ruby is a perfectly fine language, as are dozens of others, all that might be equivalent to the current example. However, change just as a way of advocating Ruby over Python (or over whatever other multi-paradigm language might be used) is better to avoid. The examples themselves are almost precisely identical, with extremely minor syntax variants (Ruby blocks, for example, are interesting, and different from Python constructs — similar to Smalltalk — but not used in this article).

Moreover, as a minor matter, the Ruby example was also wrong because it reversed the application order of F() and G() between the paradigms. LotLE×talk 05:26, 1 December 2006 (UTC)

Lazy strictness section

I saw the addition of a section on Strict and Non-Strict evaluation. The concept is certainly worth explaining, but what is there is much too long and much too informal/pedantic in tone for what it explains. We need to get that down to no more than half the length of the first pass, perhaps losing the code samples which do very little to help the explanation. LotLE×talk 16:11, 16 December 2006 (UTC)

I was also disappointed at the length of the section, even after I had eliminated a number of topics.

Still the section is around 340 words which is not an outrageous length for a major topic for a subject. The problem for me now is that the present section is fairly integrated. The core notion that needs explaining is lazy evaluation, but this requires understanding the distinction between strict and non-strict evaluation, which in turn requires an understanding of evaluation order. In addition you need explain why non-strict evaluation is the preferred approach for functional languages and then explain why most functional languages nonetheless use strict evaluation (pace the introduction to Functional Programming).

There was a great deal of material I pared away that I would have liked to talk about but didn’t because of length:

1. Normal forms and the Church Rosser theorem
2. Use of graph reduction and combinators to implement lazy evaluation
3. A history of the development of lazy reduction

With the latter point in mind I should mention there is a separate entry on lazy evaluation. This would be the obvious place for a more extended explanation and allow for a shorten entry in the FP entry. However I have some issues with it and it doesn’t provide the right context for what I’m talking about here. I’m thinking of editing it and if I’m able to do so then the section in Functional Programming could be shortened. So give me some time and I’ll see what I can come up with.

The informal style was intentional and was meant to stay within the guide lines set for the Computer Science wikiproject which include:

1. Put the most accessible parts up front.
2. Motivate all concepts
3. Use concrete examples
4. Avoid unnecessary jargon
5. Use a conversational style

The only technical terms I use are evaluation order, strict, non-strict and lazy evaluation. I start with evaluation order because it’s the simplest to understand and end with the most technical term. All terms are given explanations. I don’t mention normal and applicative order reductions because the idea of evaluation order could be understood without them, and evaluation order is all I need to motivate the distinction between strict and non-strict evaluation.

I disagree concerning the importance of the code samples. Again the guidelines support using concrete examples. But independent of the guidelines, most of the texts I looked at that explain lazy evaluation do so with an example much like the one I used. For instance look at Hudak’s article (pg 383), “The Impact of the Lambda Calculus in Logic and Computer Science” by Henk Barendregt (pg. 195), or “Introduction t Functional Programming using Haskell” by Richard Bird (pg 4-5). The only interesting difference is that some of the examples use lambda notation, while mine is a simple arithmetic expression. But lambda notation is not necessary to illustrate the concept of evaluation order. Some articles don’t provide an example, but these were more technical articles that either assumed knowledge of lambda calculus or contained a previous section that explained the concepts of applicative and normal order reductions. Finally, the examples are just not all that long. They take up a bit of space given the formatting but that should not be the criterion to use when discussing the length of entries. Abcarter 15:44, 17 December 2006 (UTC)

Thanks for your contribution. It's a good one. In general, I don't find the tone or style objectionable, aside from the use of "you" to refer to the reader (which just doesn't fit with the Wikipedia feel IMHO). However I agree with LotLE that the section is a little long. Part of the problem is that it spends time providing background on concepts that are not really core parts of this article, and are probably better dealt with via wikilinks.

If the code examples stay, you might consider reformatting tehm to be more horizontal, e.g.:

g(1,4)^2+g(1,4)+1 → (1+4)^2+(1+4)+1 → 5^2+5+1 → 31

--Allan McInnes (talk) 20:57, 17 December 2006 (UTC)

Thanks for the feedback. Agree about the use of "you", it's one of the most common mistakes I make when writing, should have caught it before you did. I took your advice regarding the code samples. The result strikes me as slightly less readable (IMHO) and not worth the savings in space, but if others find it an improvement I'm happy to go with it.

Yep, looks better with the white space. Abcarter 11:29, 19 December 2006 (UTC)

As I mentioned with my reply to LotLE, I agreed that the section is a little long, I just don't know what to do about it. I also agree that the problem is the need to provide background material, but it is not at all clear what concepts are not core to the article. So far in my reading the concepts of non-strict and lazy evaluation only arise for functional languages, with Algol 60 beings the one except. Am I confused on this point? Abcarter 22:49, 17 December 2006 (UTC)

OK, I've taken a second careful look at the entry for "Lazy Evaluation" and I see what the core problem is: the entry treats the terms "lazy evaluation" and "delayed evaluation" as equivalent. "Delayed evaluation" is a far more general term, and may not even have a well-defined definition. If I can split-off "delayed evaluation" into a separate entry, then the entry for "lazy evaluation" can be revised to support the points being made in the FP entry. This could take some time, since I'm new to the group editing this entry and I'm proposing fairly major changes. Abcarter 23:43, 17 December 2006 (UTC)

Changes to Lazy Strictness Section

I took the liberty of making some changes to this section, mostly grammatical changes for clarity (I hope these help). It used to say that infinite data structions would "only be evaluated in a context where a finite subset... is required." This seems an odd thing to say, since in Haskell for example, you can perfectly well evaluate an infinite list. I changed it to say that such data would only be useful in such a context — perhaps that's what OP had in mind? Ezrakilty 22:21, 12 September 2007 (UTC)

Revised some of your changes:

1. Make clear that the implementation of non-strict evaluation was not seen in the initial development of these languages.
2. Indicate that the theoretic benefits of non-strict evaluation was a motivation in the development of lazy evaluation.
3. I may be wrong on this point but I would claim that the functional languages that would claim to be pure are also the functional languages that use lazy evaluation.

I didn't make changes to the remarks on infinite data structures, though I'm puzzled by your remarks, in particular because I think we're both wanting to say the same thing. I would have thought that it is impossible to evaluate an infinite list in its entirety and nothing like this is done in Haskel. What is done is a mechanism that can evaluate the list for any finite sequence, which was the thrust of my original remarks. Am I missing something? A B Carter (talk) 00:45, 13 September 2007 (UTC)

A B Carter, thanks for looking at these issues. I have a couple of responses:

1. I was perplexed by the suggestion made in the original text, to which you reverted, which seemed to suggest that all new functional languages use lazy evaluation. This suggestion comes from one sentence asserting, "the earliest functional languages use strict evaluation" and later, "Lazy evaluation is used by the more recent functional languages." I think this is misleading because it sounds like strict evaluation is an old idea that was thrown out with the advent of lazy evaluation. The fact is, languages continue to be developed on both sides of the spectrum, and I wanted the article to suggest that. Would you mind if I rephrased this again so that a temporal comparison is not made?

I don't think the original statement implied that development of languages using strict evaluations came to a halt. I do think the temporal comparison is important because the concept of lazy evaluation was an impetus in the development of a number of new functional languages and that language developers who are attached to the idea of pure functional programming use lazy evaluation (I could be wrong here, I'll try to dig up some references).

1. Grammatically, I don't understand the transition that begins "This led to the development of lazy evaluation." What is "this"? The previous sentence talks about infinite data structures. I don't think that infinite data structures led to lazy evaluation--I think it was a desire for efficient non-strict evaluation that led to laziness. Infinite data structures are perfectly usable with a call-by-name strategy. At any rate, I think lazy evaluation deserves its own paragraph, since it is so significant for functional languages (moreso than call-by-name, probably).

Agreed that the reference of "this" is unclear. But I did want to show that the desire for non-strict evaluation was the motivation for lazy evaluation. What you originally had is probably better so long as it makes some reference to this need. I'm of two minds about making it a separate paragraph since at the moment it consists of two sentences. The paragraph could certainly be expanded but there have been previous complaints that this section is already too long.

1. Finally, there's the question of evaluating infinite data structures. I would say that I can "evaluate an infinite data structure" in Haskell, though not, of course, in its entirety, as you now qualify it. Here I go:

*Main> [0..]
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,Interrupted.

The program was running just fine, evaluating that infinite list; I just happened to kill it in the middle.

I think it is a mistake to confuse "evaluate" with "evaluate in its entirety" in lazy languages. After all, what can you do with an infinite data structure, if not evaluate it? The original wording, which said, "With non-strict evaluation these structures are only evaluated in contexts where a finite subset of the list is required," suggests to me that the implementation has some intelligence that somehow recognizes and avoids evaluating infinite data structures--but normally the implementation will just start evaluating it, and perhaps it will yield data as it goes. It's relevant that you can evaluate, say, the list of all primes, and in fact this can be useful: it gives you a bunch of primes (though you can't get all of them).

Arguably, this is just a difference in usage of "evaluation," in which case I think we should just make sure to phrase it in such a way that these distinctions are clear. — Ezrakilty 12:07, 13 September 2007 (UTC)

As I thought we are in complete agreement about what needs to be said, but oddly at odds with how to express it. But I see your point about the ambiguity of my original wording. I was bothered by "most useful" because this implies that there would still be utility in cases where an infinte part of the structure was needed.

I'll try to make some changes. No doubt we'll go back and forth on this for a bit. In any case it's been a pleasure working with you. A B Carter (talk) 14:26, 13 September 2007 (UTC)

Responding to all three points here, since the indentation is confusing me.

Regarding the relationship of laziness and pureness: I'm not sure whether the motivation you describe is pervasive. I am aware that laziness in a language generally forces pureness, since laziness can make evaluation order unpredicatable and so the sequencing of side-effects would be unpredictable. That would be the reverse of the causation you describe. Could this be what you have in mind?

More generally, I think that the section ought to stick to describing the concept of evaluation order, and steer away from these historical and motivational questions, which might be subjective anyway.

Your re-wording of the point about infinite data structures was effective.

Finally, I think there is a subtle point of confusion here with the term "non-strict." I believe that "strict" has a precise definition (namely, that a functional call will not terminate if any of its arguments fails to terminate), and non-strict would be anything that doesn't meet that definition. As such, "non-strict" could include the call-by-name strategy demonstrated in the examples (and in which an argument may be evaluated more than once) and it could also include a lazy strategy (and others). There is some precedent for "non-strict" being used for call-by-name, but call-by-name is a more specific term. I'll tinker with it. — Ezrakilty 23:07, 17 September 2007 (UTC)

I'm not at all sure that non-strict evaluation is required by a pure functional approach, but it does appear to be a more natural expression of the lambda-calculus, which is why historically the language developers who embraced a pure approach to functional programming used non-strict evaluation.

I think providing historical context and the motivations for a certain direction of development is a substantial aide to understanding the underlying concepts. But the point I'm trying to express clearly needs a citation. Let me do so research.

Happy that we're in agreement regarding infinite data structures.

No comment for the moment regarding your last point. Going to have to mull that one over. — A B Carter (talk) 11:21, 18 September 2007 (UTC)

IPL

The new information on IPL looks interesting and I'm not seriously disputing it. But it isn't common knowledge and really needs a citation. I did try to research the language several months ago and had a difficult time finding out anything about IPL or how it related to functional programming. If you have an article or text I would be very interested in looking at it. Abcarter 18:29, 28 December 2006 (UTC)

Closures and Functional Programming

Does anyone have any good sources that discuss the relation between closures and functional programming? I've been researching this topic for the past couple of weeks, but it's been surprisingly frustrating. Many obvious sources, such as Hudak's review paper, hardly mention them at all. These are the key points that I've been able to come up with so far:

1. Closures is one of the means for implementing first-class functions. Scheme and Common Lisp use closures in this way.
2. There are other ways of implementing first-class functions.
3. Continuations are a type of closure and continuations is one of the fundamental techniques for handling IO in a functional language.

I'm still doing research so these conclusions are tentative and I'm happy to hear a different story. Abcarter 15:07, 30 December 2006 (UTC)

The first two of these points are reasonable statements. The last is not quite right. A continuation can be seen as a first-class function, but is not necessarily relevant to discussing first-class functions. I would not say that continuations are a way of handling IO. Rather, continuations are used to implement various control structures that don't otherwise exist in the language. -- Ezrakilty 23:08, 1 February 2007 (UTC)

When I said that continuations are a type of closure I was not implying that they were first-class functions. In regards to IO, read Section 3.2 of Hudak's article on FPL. Continuations are used in one of the two basic models for handling IO in a purely functional manner. A B Carter (talk) 12:49, 2 February 2007 (UTC)

Clumsy wording

This is quite clumsy in Functional programming language#Pure functions:

Since pure functions do not modify state, no data may be changed by parallel function calls.

I think it was trying to say that parallel calls could not interfere with each other? Shenme 04:13, 8 January 2007 (UTC)

Logarithmic slowdown? What slowdown?

Despite purely functional languages having a reputation for being slower, any imperative algorithm is expressible in these languages with a logarithmic slowdown in the worst case.[citation needed]

Thomas Breuel argues here that imperative algorithms are expressible with no asympotic slowdown. The trick is to use persistent data structures that are implemented with O(1) access to the latest version, but slower access to previous versions. Although he doesn't give a watertight formal argument, this seemed fairly convincing to me. --DavidHopwood 00:05, 30 August 2007 (UTC)

Suggestion: Motivational Analysis

I definitely like the use of concrete illustrations illuminating the concepts in the article. Just the same I think the article would be improved by a more thourough discussion of the motivations for adopting the functional paradigm

---

Philopedia (talk) 18:28, 16 November 2007 (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)

"Functional Programming", not "Pure Functional Programming Languages"

The title of this article is "Functional Programming". If it were "Pure Functional Programming Languages" I could understand the tendency to edit out any mention of "other" languages.

I'm trying to add a single, external link to a project that brings functional (and declarative!) programming to Javascript. Why not? Javascript is running in everyone's browser, so it's easily accessible. What better way to demonstrate the simplicity and elegance of functional programming to the masses? Moreover, there is yet to be a mainstream functional language with wide acceptance. Having been a fan of functional declarative programming for 20 years, I'd settle for convention and stylistic choices in a language I can actually use over some obscure undersupported language.

http://code.google.com/p/fdjs/

Functionalguy (talk) 20:50, 17 December 2007 (UTC)

I don't think there is any concern about the purity of Javascript, but the project linked to does not appear to be well known and consequently comes off as an advertisement. If you can provide an independent citation of its use you will get a better reception. A B Carter (talk) 01:33, 18 December 2007 (UTC)

If you can show me a reference that says an independent citation is necessary to post a blasted link then your point is well taken.

Functionalguy (talk) 02:42, 18 December 2007 (UTC)

Please see WP:EL for a discussion of when it is appropriate to add external links. --FOo (talk) 02:57, 18 December 2007 (UTC)

Exactly. No mention of an independent citation. Functionalguy (talk) 03:33, 18 December 2007 (UTC)

Links should be restricted to the most relevant and helpful. --FOo (talk) 04:54, 18 December 2007 (UTC)

I agree that the link is inappropriate. Wikipedia is not a link farm, and it seems that the project that you're linking to is not particularly notable, and also not particularly relevant. Not to say that it is completely irrelevant, but it seems to me that it is not relevant enough. It is not the purpose of the External Links section to link to every resource that could conceivably be related to the subject of the article. Otherwise, a subject as broad as "Functional programming" would have thousands or millions of external links.

I understand that your library is useful and interesting, and that you want people to find out about it. But that is not what Wikipedia is for. I encourage you to submit it to other, more appropriate venues.

-- Dominus (talk) 04:55, 18 December 2007 (UTC)

Aside from the non-relevance of linking to one library (among hundreds) that do "something FP-ish in a mostly non-FP language", the one linked for JS is listed as "low activity" and has exactly one member. I'm pretty sure that one member is the same person trying to add the link.

There are actually several better known FP-in-JS libraries out there. Mochikit is nice. So is Prototype. JQuery looks very impressive also (not purely FP, but definitely in that direction). But you can say the same of dozens of libraries in dozens of languages. This isn't the place to list them (maybe somewhere like DMOZ). LotLE×talk 09:38, 18 December 2007 (UTC)

Scala advertisement

So a large block of Scala spam was recently added to the history section.

I think it should be removed. Scala is just another multi-paradigm language; if ML, Miranda, and Haskell combined get one paragraph, I see no reason Scala should get an entire paragraph. --Gwern (contribs) 18:19 9 January 2008 (GMT)

Agree, though I'm happy to hear an opposing view. It is particularly inappropriate in the history section which should focus on languages seminal in the development of functional programming. A B Carter (talk) 19:13, 9 January 2008 (UTC)

Right. I mean, Scala might become an interesting hybrid language, but I don't think even its ardent proponents would argue that it has had the impact that, say, ML has had; it's just way undue emphasis. --Gwern (contribs) 22:17 9 January 2008 (GMT)

I agree. I think Scala is a neat language, and I like it a lot. But it's nowhere near as important (yet) to the development of FP as the likes of ML or Haskell. --Allan McInnes (talk) 01:53, 10 January 2008 (UTC)

Fair enough. It wasn't meant to be an advert. I havnt even used Scala yet, I just thought it was getting so much talk it was worth mentioning. Hey, it had me reading about Functional Programming to start with. I do find it odd that you are ignoring the real buzz that is happening in the non-functional camp. Perhaps this buzz is smaller than I think it is. Again, I have no connection with Scala. I just thought it was relevant. And yes, perhaps not in the History section - it just seemed a good place to say "look out for this". A lot of people are saying "scala is going to be big this year". If any of you guys think its relevant on the page then so be it, if not, Ill stop spamming your page. :) --Christiancatchpole (talk) 02:50, 10 January 2008 (UTC)

It has occurred to me for awhile that a separate section on FP and programming languages might be warranted. Most of the remarks regarding different languages in the introduction would be more appropriate in such a section and there are a couple of other points that could also be made. Whether this warrants inclusion of Scala is unclear, but it at least allows for a sensible discussion. A B Carter (talk) 02:12, 11 January 2008 (UTC)

Reference to Haskell in external links

I undid the deletion of the Haskell reference in the external links. Haskell could bear some emphasis. Historically it was developed as an effort to pull together a number of distinct research efforts into a single language and it remains the most prominent language in academic discussions. Haskell is the most actively used pure functional language (it is 35th on Tiobe's Programming Community Index).

More generally I don't see an issue with having links to the major website for a few of the prominent functional languages such as Miranda or ML. A B Carter (talk) —Preceding comment was added at 12:54, 23 March 2008 (UTC)

It seems to me that Haskell gets mentioned several times in the article already. If you truly feel that it merits additional emphasis due to its ancestry, then why not add a section discussing the fact that Haskell "was developed as an effort to pull together a number of distinct research efforts into a single language and it remains the most prominent language in academic discussions." That would be far more informative than just including an external link. I don't particularly see the need to have links to websites for specific languages in this article, since there are already copious wikilinks to specific language articles (all of which no doubt have links to the corresponding language websites) for anyone who's interested in looking at a specific language.

Having said all of that, I really don't care about issue enough to argue about it, so if the preceding is not convincing to you then by all means leave the link in there. --Allan McInnes (talk) 21:07, 23 March 2008 (UTC)

Fair enough. I certainly agree that the history section could be rewritten and expanded. For the moment I'm still for keeping the link, but it's nothing more than a preference. If somebody wants to break the tie go ahead. A B Carter (talk) 19:47, 24 March 2008 (UTC)

I think the links to the websites of various languages should be given in their articles, not in this one. Mention Haskell, Lisp, Miranda, ML, etc. where each is relevant to the overall discussion—but reserve the links to the websites for each for the articles on the individual languages. LotLE×talk 00:02, 25 March 2008 (UTC)

I'm troubled by the haskell.org link as well. Yes, Haskell is a major functional language; as a Haskell fan, I'd like to go so far as to claim it's the most mature and usable FP language. But how does linking to the front page of the Haskell wiki serve this article? It doesn't, no more than linking to cliki.net or scheme.org or whatever would. I don't doubt haskell.org contains a number of fascinating articles on the subject of Functional programming - but link to those then! --Gwern (contribs) 22:33 25 March 2008 (GMT)

APL as a functional language

A comment about a recent reversion of an edit that deleted APL as an example of a functional language. So far as I know, the only time APL has come up on the talk page was a discussion I initiated and where I was of two minds regarding APL's status. The issue remains unclear to me. APL is not listed as a functional language on the FP FAQ page. I checked a few FP texts and none of them mentioned APL, though Lisp was often mentioned. The key points are that APL has neither lambda expressions nor first-class functions. The latter strikes me as a deal-breaker. APL is certainly of historical importance in the development of functional programming, which is why it gets a fairly brief mention in Hudak’s article.

I would rather not get bogged down in an argument about what “is” or “is not” a functional language, but I do think that it is not perspicuous to simply lump together APL, Erlang, Haskell, Lisp, ML, F# and Scheme and call them functional languages. A better approach would be an expanded sentence that pointed out some basic differences.A B Carter (talk) 16:39, 6 May 2008 (UTC)

Well, OK. I can see this argument, and won't argue too much for inclusion of APL with this discussion appearing. My first thought is that J and K are resented in the next paragraph as industry-specific examples, and those are essentially "APL w/o quite as funny characters". So at least in heritage, APL influences FP languages. I wasn't aware APL lacked first-class functions, that surprises me. LotLE×talk 17:08, 6 May 2008 (UTC)

In the APL articles, e.g.: "Operators (aka higher-order functions) take functions as arguments, and return related, derived functions as results. For example the "sum" function is derived by applying the "reduction" operator to the "addition" function. Applying the same reduction operator to the "ceiling" function (which returns the larger of two values) creates a derived "maximum" function, which returns the largest of a group (vector) of values."

That sounds a lot lif first-class functions to me. It might be possible to split some hairs on exactly how higher-order functions combine or support definition...but we're definitely a good distance towards FP there. LotLE×talk 17:18, 6 May 2008 (UTC)

The odd thing is that while APL has higher-order functions, it doesn’t have first-class functions. As you point out, there are operators that take functions as arguments and return new functions as results. However the concept is stratified, you can use operators to manipulate functions but not manipulate other operators. On a more mundane level, you can’t do things like store functions in a list or array. All quite frustrating because APL suggests a style of programming that it is not completely able to support. The key innovation to of A+, the precursor to K, was not getting rid of the funny characters but making functions fully first class. In regards to functional programming APL is a transitional language much like Lisp, and the relation between APL and K is much like the relation between Lisp and Scheme.A B Carter (talk) 21:35, 6 May 2008 (UTC)

Fair enough. I have a vague knowledge about APL, but haven't concretely used it. I think we concur that APL is "transitional" towards FP, and if you wish to remove it from the prominent list in the article, I have no objection. LotLE×talk 15:36, 7 May 2008 (UTC)

Disorganization

Please consider adding some criticisms of FP such as the problem of a lack of structure in large systems and the difficulty in specifying sequential processes in FP. —Preceding unsigned comment added by 12.155.35.210 (talk) 14:59, 16 July 2008 (UTC)

Infinite list example

The infinite list of primes example that recently appeared in the section on non-strict evaluation is certainly a classic example. However, I'm a bit worried that it's too obscure to be of much help in an encyclopedia article. Despite the fact that it claims to be pseudocode, the example itself seems to rely on an (unexplained) Haskell-like syntax that probably isn't familiar to most readers. Any suggestions on how (or if) we should improve the example? --Allan McInnes (talk) 22:49, 1 September 2008 (UTC)

I actually went ahead and changed it to a concrete example, using evens (thinking this would be slightly less scary-looking) and used real Haskell syntax. Although Haskell syntax may not be familiar, at least it is a specific real language and this may aid the reader because it is used elsewhere. Also hopefully the example and description are intuitive enough without a precise understanding of Haskell. If anyone strongly prefers an example using primes I won't object to a change. Ezrakilty (talk) 22:56, 1 September 2008 (UTC)

Re: C# can exhibit functional behaviour

Re: a citation needed claim for the statement "In C# version 3.0 and higher, lambda functions can be employed to write programs in a functional style":

Library

 namespace Functional {
 
   // define the notion of a lambda-function. There's a few so that we can have a number of arguments.
   // they are needed for the type signatures, and C# 3.0 converts them for us. This is required for .NET 2.0
   // (they are included by default in the LINQ library with .NET 3.5)
   public delegate TResult Func<TResult>();
   public delegate TResult Func<TResult, TArg1>(TArg1 arg1);
   public delegate TResult Func<TResult, TArg1, TArg2>(TArg1 arg1, TArg2 arg2);
   public delegate TResult Func<TResult, TArg1, TArg2, TArg3>(TArg1 arg1, TArg2 arg2, TArg3 arg3);
   public delegate TResult Func<TResult, TArg1, TArg2, TArg3, TArg4>(TArg1 arg1, TArg2 arg2, TArg3 arg3, TArg4 arg4);
   public delegate TResult Func<TResult, TArg1, TArg2, TArg3, TArg4, TArg5>(TArg1 arg1, TArg2 arg2, TArg3 arg3, TArg4 arg4, TArg5 arg5);
 
 
  public static class FunctionalFunctions {
 
       // given an enumeration of elements, allow us to "take" the first 'num' elements of it.
       public static TResult[] Take<TResult>(this IEnumerable<TResult> argument, int num)
       {
           if (num < 0)
               throw new ArgumentException("num must be greater than or equal to zero");
           if (num == 0)
               return new TResult[0];
 
           TResult[] r = new TResult[num];
 
           var e = argument.GetEnumerator();
           if (!e.MoveNext())
               throw new ArgumentException("Take cannot take from past the end of an enumerator");
 
           for (int i = 0; i < num; i++)
           {
               r[i] = e.Current;
               if (!e.MoveNext())
                   throw new ArgumentException("Take cannot take from past the end of an enumerator");
           }
 
           return r;
       }
  }
 
   // an infinite "list" defined as a lazilly-evaluated function that recurses on its previous definition
   public class RecursiveInfiniteEnumerator<TResult> : IEnumerable<TResult>, IEnumerator<TResult>
   {
       TResult next, first;
       Func<TResult, TResult> func;
       bool started = false;
 
       public RecursiveInfiniteEnumerator(TResult first, Func<TResult, TResult> func)
       {
           this.first = first;
           this.next = first;
           this.func = func;
       }
       public bool MoveNext()
       {
           if (!started) { started = true; return true; }
           next = func(next);
           return true;
       }
 
       // required interface implementations: 
       public IEnumerator<TResult> GetEnumerator() { return this; }
       System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return this; }
       public TResult Current { get { return next; } }
       public void Dispose() { /* no disposal needed */ } 
       object System.Collections.IEnumerator.Current { get { return next; } } 
       public void Reset() { this.next = first; }
   }
 }

we can write code that emulates the functional style:

User code

 using System;
 using System.Collections.Generic;
 using System.Text;
 using Functional;
 
 static void Main(string[] args)
 {
   // evens n = n : [evens (n+2)] -- an "infinite list" of even numbers starting with n
   RecursiveInfiniteEnumerator<int> evens = new RecursiveInfiniteEnumerator<int>(0, x => x + 2);
 
   // take 4 (evens 0)
   var r = evens.Take(4);
  
   // print the result
   foreach(var elem in r)
     Console.WriteLine(elem);
 }

We can even make this a one-liner, thus:

 int[] first_N_Evens(int n){
   return new RecursiveInfiniteEnumerator<int>(0, x => x + 2).Take(n);
 }

In fact, we can also perform lazy evaluation via:

Lazy evaluation in C#

 class LazyEval<T> {
   T cache; bool hasResult;
   Func<T> generator;
   public LazyEval<T>(Func<T> generator){
     hasResult = false; cache = default(T); this.generator = generator;
   }
   public T Value {
     get {
       lock(this){
         if(hasResult)
           return cache;
         cache = generator();
         hasResult = true;
         return cache;
       }
     }
   }
 }

In general, functional code can be put into C# without too much hassle. The supporting libraries are usually a bit cumbersome (as you can see), but because of the lambda-functions introduced with C#3.0, most of the semantics of functional programming can be brought through to C#.

This isn't an article on C#, and thus the above certainly doesn't warrant being included there, but I'm not sure what Wikipedia's policy on self-citing itself is.

Either way, C and C++ can sort of curmudgeonly pretend to be functional by (ab)using various programming patterns (most notably function pointers - eugh) whereas C# actually has the architecture that would be needed to make it functional. That said, it's rarely used. —Preceding unsigned comment added by MattTait (talk • contribs) 01:17, 2 September 2008 (UTC)

Discuss...

MattTait (talk) 01:03, 2 September 2008 (UTC)

That's nice (well, ok, not really - it looks to me like a terrifyingly complex way to achieve what is fairly simple in languages that actually support functional programming). But while the code above does demonstrate that C# can be used to do something resembling FP, that demonstration is original research. Or did you grab that particular code example from some other (citable) source that discusses C#'s FP emulation capabilities? --Allan McInnes (talk) 01:16, 2 September 2008 (UTC)

The library is horrific (which is most of the code) and would be squirreled away in a library somewhere. The code the user writes is roughly the same number of lines as the Haskell equivalent. In fairness, in languages such as Haskell and ML, just because you don't see the definitions of things doesn't mean they're not there.

Re: citableness, F# is the generalisation of C# in the functional sphere (it's properly functional), and C# has a library called LINQ (distributed by Microsoft) which is functional for C#; for example:

 using System.Linq;
...
 
 int[] array = new int[100];
 // populate the array:
 for(int i=0;i<100;i++){ array[i] = i;}
 
 // "Select" is map in Haskell-land.
 // "Where" is filter in Haskell-land.
 // Bear in mind that C# evaluates LTR, so this filters out all even numbers, then multiplies the resulting elements by 2.
 IEnumerable<int> result = array.Where( x => x % 2 == 1 ).Select(x => x*2 );
 
 // print them out
 foreach(int j in result)
   Console.WriteLine(j);

Linq is aimed specifically at database-programmers, thus the choice of "select" and "where" rather "map" and "filter", but the premise is the same.—Preceding unsigned comment added by MattTait (talk • contribs)

Languages like Haskell and ML may well have the same kind of definitions "hidden away". But that's the point isn't it. FP languages (such as Haskell and ML) provide built-in support for the FP style. Thus in the Haskell Standard Prelude the definition of take is just:

take                   :: Int -> [a] -> [a]
take n _      | n <= 0 =  []
take _ []              =  []
take n (x:xs)          =  x : take (n-1) xs

It would be only slightly more complex if you chose to define your own list datatype in terms of Cons and Nil instead of using the built-in one (nor would that manually constructed list type require all of the gory details used in the RecursiveInfiniteEnumerator definition). Yes, the internal language implementation itself includes definitions that make this stuff easier, but then the C# implementation includes all sorts of things that make OO programming easier.

Regarding your other comments: my understanding is that F# is a CLR-based implementation of OCaml, rather than anything to do with C#, so I don't think that's a particularly helpful example. I'm aware of Linq, and the work that Eric Meijer and Co. have done on it. I agree that it could be seen as providing functional capabilities. Please understand, I'm not trying to argue that C# doesn't allow you to do some FP things, what I'm asking for is an actual reference where such things are discussed (you'll note that the mention of FP in C++ within the article includes a citation to something that actually talks about FP in C++. For what it's worth, I'm pretty sure that Meijer or someone working with him has written some stuff about FP in C#, I just don't have the time to dig up the relevant reference right now. --Allan McInnes (talk) 02:16, 2 September 2008 (UTC)

True, and I concede your point that my implementation is perhaps messy - I'm a bit of an efficiency nerd, and thus I wrote a fast implementation of Take, but you could equally well write an implementation recurisvely in C#:

 Stack<T> take<T>(int n, IEnumerator<T> e){
   // take 0 _ = []
   if(n == 0) return new Stack<T>();
   // take (next:as) n = next : (take as (n-1))
   e.MoveNext(); var next = e.Current;

   var r = take(n - 1, e);
   r.Push(next); // cons (if you will)
   return r;
 }

This is almost directly the Haskell implemention you provided, although I'll grant you it's not as elegant.

You legitimately object to my class RecursiveInfiniteEnumerator, but the point is that it implements the ability for C# to define infinitely recursive lists which would not otherwise be possible in C#, and while most of it is gory as you suggest, the total volume of code is low - most of it is just implementing the interfaces required by IEnumerator and IEnumerable. The point is that while the class is huge, it is also massively general. For example, the infinite list of integers is

 new RecursiveInfiniteEnumerator(0, x => x + 1);

The infinite list of powers of two is

 new RecursiveInfiniteEnumerator(1, x => x * 2);

and the infinite list of primes is

 new RecursiveInfiniteEnumerator(2, x => x + 1).Filter(x => IsPrime(x));

so I believe the objection is slightly disingenuous, as the library, while supporting the user code, is certainly not cherry-picked in order to make the code small.

MattTait (talk) 02:52, 2 September 2008 (UTC)

Actually, I don't particularly object to RecursiveInfiniteEnumerator: it does the job you created it to do, and does it well. My point was more that such gymnastics simply aren't necessary in an FP language like Haskell. Anyway, all of this is beside the point. As I mentioned above, I'm not saying that FP can't be done in C#. I'm simply asking for a reference to that effect so that we can comply with Wikipedia's policy on verifiability (and no, what you've posted on this page won't count, since citing it would violate the policy against original research and probably the guideline regarding avoidance of self reference). --Allan McInnes (talk) 06:25, 2 September 2008 (UTC)

There's this post by Sriram Krishnan (who works at Microsoft India on Visual Studio), and demonstrates the concept of currying in C#. There's also this powerpoint presentation (you'll need office2007 for that, sorry) from Microsoft Research Cambridge on the subject.

I haven't found anyone else whose implemented lazy evaluation or infinite recursive lists in C# yet. Ironically if I created a blog it would make it more citable, rather than less. But hey, the Internet is bizzare.

MattTait (talk) 06:51, 2 September 2008 (UTC)

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:

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)

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)