30

I understand very clearly the difference between functional and imperative programming techniques. But there's a widespread tendency to talk of "functional languages", and this really confuses me.

Of course some languages like Haskell are more hospitable to functional programming than other languages like C. But even the former does I/O (it just keeps it in a ghetto). And you can write functional programs in C (it's just absurdly harder). So maybe it's just a matter of degree.

Still, even as a matter of degree, what does it mean when someone calls Scheme a "functional language"? Most Scheme code I see is imperative. Is it just that Scheme makes it easy to write in a functional style if you want to? So too do Lua and Python. Are they "functional languages" too?

I'm (really) not trying to be a language cop. If this is just a loose way of talking, that's fine. I'm just trying to figure out whether it does have some definite meaning (even if it's a matter-of-degree meaning) that I'm not seeing.

dubiousjim
  • 4,722
  • 1
  • 36
  • 34
  • 11
    Actually I wish kids toying with Perl/Python/Ruby/C# would cease to tag their questions `functional-programming` as soon as there is an anonymous function in the ugly pile of steaming punctuation they produce as a code example. I'm not interested in their questions, but some of the questions that do interest me have nothing but the `functional-programming` tag to distinguish them. It should, as you point out, be functional-languages, bu no-one uses that tag. – Pascal Cuoq Feb 18 '10 at 20:07
  • 3
    @Pascal - I disagree completely. There are plenty of functional programming techniques that are useful in a variety of languages that aren't "pure functional languages". It's the same as programming in an object oriented manner in a language that allows multiple paradigms. If you're interested in pure functional languages, then perhaps there should be a separate tag for that... or look things up by the tags for those specific languages. – RHSeeger Feb 19 '10 at 14:05
  • @RHSeeger In theory, I would agree with your point of view (I wouldn't use the word "pure" but "traditional", as "pure" may evoke "without side-effects", which is another debate entirely). In practice, if I read through the awkward syntax in one of the questions I refer to, I realize after a moment it's **nothing more** than a "fold". It's great that the kids are enthusiastic and share, but it feels a little off-topic (for lack of a better categorisation), the same way a question about the sum of the first n integers on mathoverflow would. – Pascal Cuoq Feb 19 '10 at 14:57
  • On the other hand, there are completely agnostic "functional-programming" questions (usually about persistent data structures). I am interested in persistent data structures and I want to see these questions, but they do not have any specific language tag. As you point out, such data structures can be implemented in any language, even one not usually categorized as functional language. – Pascal Cuoq Feb 19 '10 at 15:01
  • Nobody uses "pure functional languages"--Haskell is close, but just see how far you get without using `IO`. Really, all languages are multiparadigm if you try hard enough, but some are more multiparadigm than others. Being able to toss in a few trivial idioms borrowed from functional programming doesn't mean much. How many of the languages Pascal mentioned have decent support for most of Brian's list? On the other hand, it doesn't really bother me; if it means more people exposed to functional concepts, so much the better! – C. A. McCann Feb 19 '10 at 15:33
  • 5
    And speaking of OOP, if you think Pascal here is unhappy, go find some Smalltalkers and ask them if C++ "supports object-oriented programming". – C. A. McCann Feb 19 '10 at 15:37
  • 1
    @Pascal: While you may be interested in some of the more complex aspects of functional programming, there are many simpler elements (such as fold) that people are still trying to understand. I read the functional-programming tag to further my knowledge about programming in a functional style because I find it a very useful style, but I don't use any pure/traditional functional languages. I just happen to see the many benefits that specific elements of functional programming bring to the process as a whole (a big one being much easier automated testing). – RHSeeger Feb 19 '10 at 20:24
  • 1
    @PascalCuoq describing programmers in other languages as "kids toying" and describing their code as a steaming pile isn't very classy (and a bit vulgar). – Andrew Grimm Sep 06 '12 at 23:07

10 Answers10

16

Among people who study programming languages for a living, "functional programming language" is a pretty weakly bound term. There is a strong consensus that:

  • Any language that calls itself functional must support first-class, nested functions with lexical scoping rules.

A significant minority also reserve the term "functional language" for languages which are:

as in languages like Agda, Clean, Coq, and Haskell.

Beyond that, what's considered a functional programming language is often a matter of intent, that is, whether is designers want it to be called "functional".

Perl and Smalltalk are examples of languages that support first-class functions but whose designers don't call them functional. Objective Caml is an example of a language that is called functional even though it has a full object system with inheritance and everything.

Languages that are called "functional" will tend to have features like the following (taken from Defining point of functional programming):

  • Anonymous functions (lambda expressions)
  • Recursion (more prominent as a result of purity)
  • Programming with expressions rather than statements (again, from purity)
  • Closures
  • Currying / partial application
  • Lazy evaluation
  • Algebraic data types and pattern matching
  • Parametric polymorphism (a.k.a. generics)

The more a particular programming language has syntax and constructs tailored to making the various programming features listed above easy/painless to express & implement, the more likely someone will label it a "functional language".

Community
  • 1
  • 1
Norman Ramsey
  • 198,648
  • 61
  • 360
  • 533
  • would like to accept a combo of this answer and Brian's. Should I just edit & merge them? – dubiousjim Feb 23 '10 at 19:21
  • @profjim: seeing as how Brian's answer is a duplicate, it might be better to link it. Or if you feel having the information duplicated here is worthwhile, then go for it. Either way, edit until you're happy :-) – Norman Ramsey Feb 24 '10 at 02:37
12

I would say that a functional language is any language that allows functional programming without undue pain.

Randolpho
  • 55,384
  • 17
  • 145
  • 179
9

I like @Randolpho's answer. With regards to features, I might cite the list here:

Defining point of functional programming

namely

  • Purity (a.k.a. immutability, eschewing side-effects, referential transparency)
  • Higher-order functions (e.g. pass a function as a parameter, return it as a result, define anonymous function on the fly as a lambda expression)
  • Laziness (a.k.a. non-strict evaluation, most useful/usable when coupled with purity)
  • Algebraic data types and pattern matching
  • Closures
  • Currying / partial application
  • Parametric polymorphism (a.k.a. generics)
  • Recursion (more prominent as a result of purity)
  • Programming with expressions rather than statements (again, from purity)

The more a particular programming language has syntax and constructs tailored to making the various FP features listed above easy/painless to express & implement, the more likely someone will label it a "functional language".

Community
  • 1
  • 1
Brian
  • 117,631
  • 17
  • 236
  • 300
4

Jane Street's Brian Hurt wrote a very good article on this a while back. The basic definition he arrived at is that a functional programming language is a language that models the lambda calculus. Think about what languages are widely agreed to be functional and you'll see that this is a very practical definition.

Lisp was a primitive attempt to model the lambda calculus, so it fits this definition — though since most implementations don't stick very closely to the ideas of lambda calculus, they're generally considered to be mixed-paradigm or at best weakly functional.

This is also why a lot of people bristle at languages like Python being called functional. Python's general philosophy is unrelated to lambda calculus — it doesn't encourage this way of thinking at all — so it's not a functional language. It's a Turing machine with first-class functions. You can do functional-style programming in Python, yes, but the language does not have its roots in the same math that functional languages do. (Incidentally, Guido van Rossum himself agrees with this description of the language.)

Chuck
  • 234,037
  • 30
  • 302
  • 389
  • Surely if I write a language which models the SKI-calculus it will still be functional. Yes, that's intertranslatable with the (untyped) lambda-calculus. But so too is any Turing complete language. – dubiousjim Feb 18 '10 at 20:54
  • 1
    @profjim: SKI calculus is itself based on lambda calculus, so yes, a language based on that would be based on lambda calculus. And it's true that lambda calculus is Turing-equivalent, but the two models are very different from a level of human understanding, which is the domain that programming languages work in. Your objection is like noting that both a car and a boat are made of similar atoms, so there can't be any effective difference between them — it's true on some levels, but not on the one we normally deal with. – Chuck Feb 18 '10 at 21:01
  • 2
    Perhaps it was introduced to you that way, but historically it was developed independently (and I think earlier). I agree in some intuitive sense they *look* more similar than either does to C, and the translation schema is shorter in one case than the other. But I don't think there's anything more to it than that. I'm not saying there's no effective difference between anything, I'm saying why should "mode of transportation" be defined in terms of "models a car" when there are also boats. – dubiousjim Feb 18 '10 at 21:11
  • 1
    profjim is correct, combinatory logic as invented by Schönfinkel and developed by Curry predates Church's λ-calculus by a decade or so. The motivation behind the combinator calculus approach was as a construction of formal logic without need of quantified variables; that some combinator bases allow universal computation was unintentional (and perhaps frustrating, because Turing-completeness is roughly equivalent to an inconsistent logic). – C. A. McCann Feb 18 '10 at 22:34
2

A language (and platform) that promotes Functional Programming as a means of fully leveraging the capabilities of the said platform.

jldupont
  • 93,734
  • 56
  • 203
  • 318
1

A language that makes it a lot harder to create functions with side effects than without side effects. The same counts for mutable/immutable data structures.

Ruben
  • 6,367
  • 1
  • 24
  • 35
0

You can do functional style programming in any language. I try as much as possible.

Python, Linq all promote functional style programming.

A pure functional language like Haskell requires you to do all your computations using mathematical functions, functions that do not modify anything, they just return values.

In addition, functional languages typically allow you to write higher order functions, functions that take functions as arguments and/or return types.

  • I'm pretty sure Lisp is not a pure functional language in that sense. You can modify values of variables. – Niki Feb 18 '10 at 20:17
  • 1
    Most Lisps are not pure. Neither Common Lisp nor Scheme is. Clojure is the only pure Lisp I can think of off the top of my head. – Chuck Feb 18 '10 at 20:17
  • To add to that, it is possible to write "imperative style" code in haskell. But in the haskell model of the world, there is state being passed from one statement to the other. –  Feb 18 '10 at 20:20
  • Lisp is not a pure functional language. Doing IO in lisp is not devoid of side effects. It's also entirely possible to write closures with side effects. – Krypes Feb 18 '10 at 20:23
  • 3
    How does Python promote functional programming? Lambda functions are decidedly second-class citizens and everything is mutable by default. Even Guido agrees that Python is not much of a functional language: http://python-history.blogspot.com/2009/04/origins-of-pythons-functional-features.html – Chuck Feb 18 '10 at 21:44
  • @Chuck: I wrote that it "promotes functional style programming", not that it is a functional language. Doing functional style programming in Python is defintely easier than in Java or C++. –  Feb 20 '10 at 21:16
0

I think the same question can be asked about "OOP languages". After all, you can write object oriented programs in C (and it's not uncommon to do so). But C doesn't have any built-in language constructs to enable OOP. You have to do OOP "by hand" without much help from the compiler. That's why it's usually not considered an OOP language. I think this distinction can be applied to "functional languages", too: For example, it's not uncommon to write functional code in C++ (think about STL functions like std::count_if or std::transform). But C++ (for now) lacks built-in language features that enable functional programming, like lambdas. (Let's ignore boost::lambda for the sake of the argument.)

So, to answer your question, I'd say although it's possible to write function programs in each of these languages:

  • C is not a functional language (no built-in functional language constructs)
  • Scheme, Python and friends have functional constructs, so they're functional languages. But they also have imperative and OOP constructs, so they're usually referred to as "multi-paradigm" languages.
Niki
  • 15,662
  • 5
  • 48
  • 74
0

Haskell for one have different types for functions with side-effects and those without.

That's a pretty good discriminating property for being a 100% functional language, at least IMHO.

Macke
  • 24,812
  • 7
  • 82
  • 118
0

I wrote a (pretty long) analysis once on why the term 'functional programming language' is meaningless which also tries to explain why for instance 'functions' in Haskell are completely different from 'functions' in Lisp or Python: http://blog.nihilarchitect.net/archives/289/on-functional-programming/

Things like 'map' or 'filter' are for a large part also implementable in C for instance.

Zorf
  • 6,334
  • 2
  • 29
  • 24