Definition of Functional Programming Language

Functional PL :== PL with ability to pass procedures as arguments to other procedures, return procedures as result of other procedures, and store procedures in data structures.

But can we call functional PLs without tail call elimination obligation (TCEO)?
TCEO gives ability to do global jumps, it affects programming style heavily. Also, many helloworldistic programs that come to mind when FP theme arise in conversation employs TCEO.

Maybe it worth to include TCEO in FPL definition?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Minefield

You're asking if a requirement to optimize tail calls should be part of the definition of the term Function Programming Language, but your definition fails to mention referential transparency. I see a flamewar on the horizon.

Referential transparency

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.

Parsing

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.

People make mistakes

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

FP = Marketing Term?

Functional Programming is far from a rigorously defined term, being more a concept or goal than a specific set of rules. We could make the term meaningless by saying that FP can be done in any language. Or we could make it equally nebulous by saying that no PL truly captures functions in the mathematical sense. Anyhow, other than preventing others from brandishing themselves with an unearned FP claim, what is the purpose in using TCO as a dividing line?

Along a different path, I think Dave Herman presents an interesting perspective into the TCO debate. There are definite advantages to having TCO in that it opens up the possibilities for constructing and combining functions. However, there is a loss of debugging information as the stack trace no longer contains a complete accounting. From Linguistic Tools for Diagnostics:

I've written before about how the stack gets misunderstood as a history thanks to non-tail-recursive languages. Of course, stack traces are indispensable: they're essential for debugging, and they're also useful for reporting crash information from live applications.

But this conflates two very different language requirements in one feature: the need for nested (unbounded, if your language isn't broken) function application, and the need for diagnostics of dynamic errors.

It's interesting to note

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?

Great idea

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

Omniscient Debugging

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

terminology discussion off-topic

Related: 4b, 6b.

The argument as to whether "functional programming" should even allow "procedures" at all (where 'procedure' is understood to allow or observe side-effects) has been something of a holy-war topic on other forums, and no doubt on this one (err... this 'blog'... yeah).

We have no real power to re-define "functional programming" here to include TCEO or not, but I suspect the arguments against it would be sufficient to deter us even if we had power (i.e.

  • "optimizations are important, but they're part of the implementation concerns due only to limited computation resources, and are not part of the operational semantics of the language."
  • "If a functional programming language that obligates tail-call optimization is implemented using some alternative optimizations such as compacting the stack, are programs in it suddenly not functional programming?"
  • "What next? Do we require Garbage Collection to be part of the 'definition' for functional programming? While we're at it, let's require stack-based implementations and Von Neumann architectures..."

where 'procedure' is

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

Elaborating vocabulary for CS...

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

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.

Space Optimization

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

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.

The definition of a functional programming language

is a language that uses as it's fundamental model of computation the Lambda Calculus. I expanded on this further in this blog post. I don't generally pimp my own blog posts like this, but it's directly relevant to this discussion.

PL semantics may be given in

PL semantics may be given in terms of various formal systems. One PL may have several definitions in different systems. For example, you can not claim that "fundamental model" of Concurrent Clean (certainly FPL) is lambda calculus but not, say, graph rewriting system.

Also, denotational semantics of all PLs usually given in lambda calculus.

So, how to define "uses fundamental model of computation"?

Importance

I agree with all the refrains already posted, but I can't help myself...

Does anything hang on how we define the term functional (or any of the other classificatory "paradigms")? Do these names serve any purpose aside form being convenient labels, universally understood to be of only heuristic value?

No science can be done in

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

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

Slightly exaggerated

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

Extremely understated

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.

Improper inference

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

Even published authors who write textbooks

don't seem to quite agree on the definition of "functional programming". The various definitions which have been promulagated have a non-empty intersection--which is a good thing--but there's a lot of design space out there which is not subject to consensus.

A debate on the topic here on LtU might be fun--but it's not gonna go anywhere, and even if we all were to come to an agreement, so what?

Maybe we should just convince John Backus to go Alan Kay on us, claim ownership of the term, and try and exclude all those nasty and heretical languages that he doesn't like. :) (How'd that work out for Kay, anyway?)

Backus' definition of FP

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.

And Kay's definition of OO

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.

No exhaustive list of features

For me, I consider functional programming to be the business of constructing programs by composing functions through application.

A functional programming language is one that actively supports the programmer in this endeavour.

I guess this includes optimisations like tail call elimination, but also things like let statements (which acknowledge the horizontal growth in syntax of this style of programming), a 'silent' application operator and maybe even good support for defining infix operators.

Certainly, one can do imperative programming in Haskell or ML and equally one can do functional programming in C#. However, the fact that such behaviour is, on the whole, quite painful is why only the former are functional programming languages (at least, in my eyes).

Two properties

IMHO, a suitable definition of functional programming language is neither hard nor particularly controversial, as long as you keep it flexible enough. You can say a language is functional if it

1. emphasizes and encourages use of first-class and higher-order functions, and
2. de-emphasizes and discourages use of mutable state and side effects.

Both of these requirements affect the syntactic as well as the semantic design of the language and can be realized in various ways. A language is purely functional if it takes (2) to the point where it actually achieves referential transparency.

Language and style

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.

This I too agree with

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

referential transparency?

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

The shortest definition...

...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

There are relevant discussions on the LtU:

What are the properties of "Functional Programming Languages"?

Deja snooze

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...

More relevant discussions

There are relevant

There are relevant publications:

Résumé

Refusing (and resisting) to give precise meaning to terms in use and claiming that its undefinedness and contradictions are its intrinsic properties you exibit intellectual dishonesty, antiintellectualism and unscientific behaviour.

On LtU, there are worhship to authorities instead of thinking and reasoning, opinions instead of knowledge, idle talking and monkeyshines instead of collaboration.

There are lots of things I don't understand — say, the latest debates over whether neutrinos have mass or the way that Fermat's last theorem was (apparently) proven recently. But from 50 years in this game, I have learned two things: (1) I can ask friends who work in these areas to explain it to me at a level that I can understand, and they can do so, without particular difficulty; (2) if I'm interested, I can proceed to learn more so that I will come to understand it. Now Derrida, Lacan, Lyotard, Kristeva, etc. — even Foucault, whom I knew and liked, and who was somewhat different from the rest --- write things that I also don't understand, but (1) and (2) don't hold: no one who says they do understand can explain it to me and I haven't a clue as to how to proceed to overcome my failures. That leaves one of two possibilities: (a) some new advance in intellectual life has been made, perhaps some sudden genetic mutation, which has created a form of "theory" that is beyond quantum theory, topology, etc., in depth and profundity; or (b) ... I won't spell it out. — Noam Chomsky

This is ridiculous

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.

Back at you

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

There is no body

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.