Talk:Functional programming/Archive 2

Archive 1

Archive 2

Archive 3

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)

"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)