Lambda the Ultimate

Referential transparency have nothing to do with FPL definition. It is about purity.

Pure PL :== PL in which any procedure call may be replaced to its result without changes in program semantics.

But sometimes people erroneously think that Pure Functional PLs is (Pure Functional) PL instead of (Pure) (Functional) PLs.

I don't think most people use these terms the way you think they're used. Why do you suppose SML so often referred to as a "mostly functional" language? (See, for example, the Wikipedia entry.) Dave MacQueen says, when asked, that it's mostly because of references, SML's most obvious non-referentially transparent feature.

But ML defined as just FPL in Wikipedia.

ML is a general-purpose functional programming language developed by Robin Milner and others in the late 1970s at the University of Edinburgh,[1]"
ML is often referred to as an impure functional language, because it does not encapsulate side-effects, unlike purely functional programming languages such as Haskell.
wikipedia.org/wiki/ML

that in imperative languages using loops; you generally cannot (using the debugger) determine anything about any iteration of a loop other than the current/most recent.

The more general problem is that much information generated by a program which is semantic garbage (has no further effect on the program's result) is nonetheless useful for debugging. TCO and explicit loops are two ways of ensuring that certain types of semantic garbage are reclaimed, thus enabling a tighter bound on space requirements--both of which have the effect of making this information not [ed: inserted] available for debugging.

As an aside; anybody know of any debuggers which do the reverse of TCO--turning loops into explicit recursion so the programmer can inspect, if s/he wants, any prior iteration of the loop?

I never thought about it quite that way before, but that is a really great idea.

Bil Lewis' Omniscient Debugger (a DanFest video describing it) effectively does that and much more.

where 'procedure' is understood to allow or observe side-effects

It is more convenient to call mentioned PL constructions "procedures" to avoid confusion with mathematical functions regardless of side effects presence.

We have no real power to re-define "functional programming" here to include TCEO

LtU is best place to elaborate controlled vocabulary for CS.

arguments against it would be sufficient to deter us

Okay, this is the answer: "TCOE strictly belongs to other level of abstraction than FPL definition".

LtU is best place to elaborate controlled vocabulary for CS.

Even if it weren't off-topic, neither LtU nor its community has protocols for reaching consensus, fairly displaying and judging arguments, and so on.

It is more convenient to call mentioned PL constructions "procedures" to avoid confusion with mathematical functions regardless of side effects presence.

By which metric and for whom is this more convenient?

Okay, this is the answer: "TCOE strictly belongs to other level of abstraction than FPL definition"

Of course. And because it's on the LtU foru^H^H^H^H blog, people will consider that answer useful and meaningful. Right?

By which metric and for whom is this more convenient?

Mathematical function is a set of pairs with extra feature that there is no different pairs with equal first projections.

Procedure definition is a language construction mentioned in grammar and semantics formulae such that there is coconstruction "procedure call" such that proper replacement of call with definition and arguments substitutions does not change program semantics.

People reasoning about programs often has both notions in mind and will be confused if both have same names.

people will consider that answer useful and meaningful. Right?

Right.

First, I agree wholeheartedly that "we" do not get to define "functional programming" any more than we get to define "good programming", and that discussions about what should be included in that term are unhelpful.

However, I think you're selling proper tail calls a little short here. There's no need to define them in terms of implementation techniques. You can look at Clinger, Proper Tail Recursion and Space Efficiency, 1998, for a definition purely in terms of the space consumption of particular (classes of) programs.

Also, we regularly expect language definitions to require certain performance characteristics. For example, references into arrays should be "constant time" (modulo memory hierarchies). Requiring that isn't appropriate for every language specification ever, but can certainly be appropriate.

Yeah, I definitely agree that TCO is a big deal; it forces the implementer to commit to a resource semantics for the language that they have to live up to.

In fact, this can even be a reason why a language spec may wish to be silent about TCO -- promising it can make certain optimizations illegal. For example, if you want to unbox floating-point numbers in a polymorphically- or dynamically-typed language, you have to wrap any function that yields/produces floats with boxing/unboxing coercions --- but adding these wrappers can turn tail calls into non-tail-calls.

The same thing happens with things like deforestation. You can't have it and the obvious compositional semantics for space usage at the same time, because whether or not a list construction will actually allocate real memory depends on the context in which it is used. That is, something like map (+) (zip xs ys) will normally build a list, but something like sum (map (+) (zip xs ys)) won't allocate.

Coming up with a good story for this, that simultaneously lets compilers deforest and lets programmers reason about the space usage of their programs, would be a worthy endeavor, IMO.

No science can be done in nebulous marketing terms that people understood differently. So importance of clear and rigorous vocabulary is supreme.

I don't think the term FPL as such plays any role in the science of PLT.

Okay, FPL is not in PLT and FPL definition is offtopic on LtU.

FPL definition is offtopic on LtU

I don't think anyone was suggesting that.

It is just the case that

• the question has been thoroughly discussed here and elsewhere
• it has consistently not produced any useful insights into the nature of programming languages

The discussion of more specific design and stylistic features have tended be more useful. Catch-all terms like "functional programming" may be a useful short-hand, but they seem to be inherently too vague to be nailed down.

As you say, rigorous terminology is very useful for serious study. Experience shows that some expressions don't lend themselves to this rigour. FP and FPL are among these.

Or to put it in terms the theorists might grok: PLT ⊂ LtU

Backus' definition of "functional programming" would probably exclude every currently used programming language that claims being "functional programming". The only language that I can think of that might meet his requirements is Joy.

excludes, among other things, C++, Java, and probably a few others that aren't as commercially successful (and scientifically controversial).

Fortunately, the terms are frequently used as marketing terms more than anything else; were science needs precision; science uses other terminology alongside (or instead of) fuzzy terms like FP and OO.

Andreas' suggestion is close to my preferred definition; to change the focus a little, I say that the root of FP is functional programming style, which conforms to the positive (emphasize & encourage) and negative parts of Andreas' criterion. An FP language is then one that supports FP style well, a pure FPL is one that discourages non-FP styles.

The nice thing about this definition is that it leads to more interesting questions than "is language X an FPL?"; more along the lines of "what distinguishes FP style?", and "what makes it compelling?". The Advantages of pointfree? story seemed more fruitful than the other discussions linked to here, maybe for that reason.

While I'm talking about programming style, a plug for Frideman's Object-Oriented Style seems in order: the focus on the formal characteristics of a programming paradigm works effectively here.

I'd also like to add that the emphasis and encouragement is not achieved by just throwing anonymous functions in. The primitives of the language must play ball (e.g. expression-if instead of statement-if) and the standard (or non-standard) library must pay heavy tribute to #1 and #2.

(off-topic: what's the point of statement-if anyway?)

is there a succinct definition / explanation of it? i seem to recall there being long-winded debates on LtU about what it really means :-)

...is that a language is referentially transparent when the β and η transformations are always valid program equivalences.

This is true of purely functional, total programming languages. It is not true of either Haskell or ML. For ML, equational reasoning fails for function types. For Haskell, equational reasoning fails for sum types.

This is not a valid program equivalence for function expressions in ML, but is valid in Haskell:

  e != (fn x => e x)

The following is not a valid program equivalence for sum expressions in Haskell, but is valid in ML:

   e != case e of 
         Left x -> Left x 
         Right y -> Right y

This difference is intimately tied to the difference in evaluation order.

Furthermore, note that the notion of equivalence used here is insensitive to performance considerations beyond termination. Switching between call-by-value and call-by-name can cause in exponential differences in runtime in practice.

There are relevant discussions on the LtU:
What are the properties of "Functional Programming Languages"?

It is interesting that you link to that older thread. Seems like we were already pretty bored with that topic there. ;-)

I second Andreas' proposed definition, which agrees pretty well with my own.

Some concepts to don't reduce down to all-or-nothing dichotomies. Unfotunately, that doesn't stop zealots and newbs from insisting that they must...

"Declarative" or "Functional"

This is ridiculous and offensive. You're simply insulting and deriding people for refusing to play your game. Taken at face value, your accusations would be quite serious.

No one on LtU is against the precise definition of terms. But we live in reality, for better or worse. When a term of art is currently (already) widely used in a variety of related but distinct senses, it's of course possible to redefine it precisely, but what's the point? You're fighting fire with fire! Or do you think that LtU's new "formal definition" of functional programming will be the Definition to End All Definitions, and that we can then enter a world where everyone agrees to its precise meaning?

In short, the problem is not that we have no precise definition of FP. The problem is that we have too many. Adding one more (or attempting to consecrate an existing definition) will not solve this problem. If you want a precise term, you'll have to invent a new one.

Trying to give a precise definition to a phrase that has historically been used in so many contradictory ways is a colossal waste of time. What's the point? Shall we issue a press release?

August 7, 2009, Lambda the Ultimate, the industry leader in programming languages weblogs, has issued the authoritative definition of "functional programming language." Software developers worldwide have heralded this announcement as a significant leap forward in their ability to deliver correct and usable software within small time and money constraints. In related news, developers who use languages that were previously called functional but that do not fall under LtU's guideline are cautioned to cease using the phrase. LtU legal representatives state, "we have not filed any law suits over misuse of the phrase 'functional programming language' but we aren't ruling out legal action in the future either."

with the authority or clout to define the term by fiat, and make it stick. Science is full of terminology which isn't always defined as precisely as practitioners might like.

But given the nature of scientific advance, that isn't (necessarily) a bad thing. As noted above, modern functional languages have widely different properties than Backus' FP, which is where the term originated; and have their intellectual roots in systems and research that predated Backus' Turing lecture. The term "FP", and many other ambiguous-at-the-edges terms of art, are nonetheless useful, in many cases because they evolve as we learn. If FP were limited to what Backus proposed, the term would swiftly lose value (as modern languages deviate from Backus quite a bit), and instead we'd be arguing about some OTHER term.

When precision is required for scientific communication, it can be provided--either with more specific phrases (for example, a construct such as "strict, side-effect-free functional programming language with mandatory tail-call optimization", which shrinks the design space considerably), or by use of formal rather than natural language.

But when we discuss the meanings of "functional programming language", keep in mind that:

* The term, and other terms of art in the discipline (object-oriented being a biggie), have been used to mean many different things by many different people; and there are numerous arguments that still aren't settled. (Some argue that side effects must be disallowed in any language calling itself functional; others argue about strictness, etc.)

* Some of these debates have gotten quite heated and nasty. It wasn't too long ago that rather nasty flamewars were routinely conducted in the scientific literature of our discipline, between advocates of various competing theories (debates around structured programming and formal methods were two particularly notorious flamefests). Such flamewars still occur, but have generally moved to more approproate forums than the pages of Communications of the ACM and other journals. LtU, in its policies, tries very hard to keep such flamewars from sprouting up here; which is why endless debates on terminology are generally considered out of scope.

* Even if we all agreed that yes, FP languages worth their salt must contain tail-call optimization (and the resulting space guarantees) as part of their specification, the larger world doesn't care. Many notable PLT theorists don't participate here, and probably more than a few of 'em think we're all wet. (The site still does have a reputation among some programmers, we like to think undeserved, of being a den of FP fanatics.)

Lastly, I'm not sure what a Noam Chomsky flame against the lit-crit crowd has to do with us. You're not accusing LtU of engaging in po-mo nihilistic deconstructionism, are you? Nobody's said that an objective definition of the term is not possible--it's just that many such definitions have been promulgated, and there isn't any apparent means for the discipline to come to a consensus on the issue. As a result, we work around the issue, and get on to more important tasks than attempting to claim ownership of a particular label for a particular technical viewpoint.