Talk:Functional programming/Archive 3

Archive 1

Archive 2

Archive 3

Gabage collection

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

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

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

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

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

Obtuse beginning

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

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

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

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

Further comment, on the "huh" items:

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

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

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

Merge proposal

Someone put this big merge notice on the main article:

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

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

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

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

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

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

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

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

Humor

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

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

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

combinatory logic

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

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

Efficiency

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

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