6 ms·

What is a functional programming language?

50 points by bendmorris 16y ago

knowtheory 16y ago
I think we would be remiss to mention that fundamentally the Lambda Calculus and Turing Machines are mathematically equivalent, as proved in the Church-Turing Thesis (http://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis http://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis ). And while it is true that there are functional features that are unsupported in the basic syntax of imperative languages, you can still do equivalent computation, and after all "Whoever does not understand LISP is doomed to reinvent it" :P
- cyrus_ 16y ago
  54. Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy. —Alan Perlis, Epigrams on Programming
  - knowtheory 16y ago
    ha, that's great. I have to say learning about Lisp and the Lambda Calculus renewed my interest in computation and programming back in university. I really find Turing machines quite dull. Perhaps i did not adequately disclaim my statements though. Having to hack a LISP into your imperative language is neither easy, maintainable or recommended. Just cause you can do it, doesn't mean you should ;) The rest of the epigrams: http://www-pu.informatik.uni-tuebingen.de/users/klaeren/epigrams.html http://www-pu.informatik.uni-tuebingen.de/users/klaeren/epig...
Zak 16y ago
The author claims that Clojure tries to do OO. While Clojure does allow interaction with Java's object model, I think it's quite a stretch to say that it tries to do OO. Use of Java interop features for purposes other than interacting with a Java library or framework is generally discouraged.
- swannodette 16y ago
  The article is a year and a half old. Clojure doesn't "try" to do OO- multimethods always worked pretty well, and with 1.2.0 it does OO very well. Clojure design philosophy is essentially "OOP: The Good Parts".
  - peregrine 16y ago
    As someone new to clojure I gotta say that multimethods are pretty nice.
  - mahmud 16y ago
    For there to be "Good Parts" of OOP, there would have to be a single kind of OOP. P.S. Smalltalk.
    - jfoutz 16y ago
      i always miss interfaces in smalltalk. sometimes i really want a guarantee that the receiver will actually listen when i send a particular message. Even if you don't agree with that part, interfaces are really nice because the system will tell you, "hey, you forgot to add a method to respond to X. you got the other four, but spaced out this one. you should do something about that."
    - loewenskind 16y ago
      That doesn't follow. If we define "OOP" to encompasses everything that anyone calls OOP then it's very possible for there to be "good parts" and "bad parts" in that set. P.S. Smalltalk is a beautiful language with a great deal to offer anyone, but multimethods are superior. The fact that multimethods don't require multiple dispatch patterns demonstrates this.
cyrus_ 16y ago
The lambda calculus admits no notion of mutability, while the Turing machine is all about mutating locations on a tape. So I would argue that functional programming is really about immutability. A language is a functional programming language if its standard library includes and is written specifically for immutable data structures. Mutable data structures, if they exist, are second class citizens. Whether there is an object system is completely orthogonal. Whether there are first-class functions is also completely orthogonal.
- jmillikin 16y ago
  This is a very odd definition; it would exclude many languages typically considered "functional", such as Haskell.
  - cyrus_ 16y ago
    Haskell's core data structures are immutable (ADTs, tuples, records, etc.) -- what do you mean?
    - jmillikin 16y ago
      I'm assuming anything in the "base" library counts as core; in it, you have pointer/buffer manipulation (Foreign.* ), synchronized mutable containers (Control.Concurrent.* ), ST (Control.Monad.ST), and various mutable containers (IORef, STRef, HashTable). It's true that Haskell has many immutable types, but that's true of almost any language. Haskell is no more immutable than Java or C#, and certainly nothing like truly immutable languages such as Coq or Agda.
      - gwern 16y ago
        Stuff in the sinbin (or the 'IO monad') are definitely second-class citizens in the language and community. And not all of those examples are mutable - the whole point of ST is that it's safe for it to be implemented using mutation while still being treated as having immutable semantics, this doesn't mean the compiler or library actually use mutation in ST code.
scottjad 16y ago
Functional means whatever the person saying it means by it. Trying to give an all or nothing definition is doomed to failure and counter-examples.
- knowtheory 16y ago
  “When I use a word,” Humpty Dumpty said, in a rather a scornful tone, “it means just what I choose it to mean—neither more nor less.” “The question is,” said Alice, “whether you can make words mean so many different things.” “The question is,” said Humpty Dumpty, “which is to be master that’s all.” Alice was too much puzzled to say anything, so after a minute Humpty Dumpty began again. “They’ve a temper, some of them—particularly verbs, they’re the proudest—adjectives you can do anything with, but not verbs—however, I can manage the whole lot! Impenetrability! That’s what I say!” and just for completenesses sake: Alan Perlis — 48. The best book on programming for the layman is "Alice in Wonderland"; but that's because it's the best book on anything for the layman.
  - rufus_t 16y ago
    It, and "Through the Looking-glass", are very good books on programming for programmers, too. If you haven't read them since you were liddle, you're missing out.
- gtani 16y ago
  FP means different to lispers, ML'ers and typeclassists (haskell, scala). Here's my attempt at a def http://news.ycombinator.com/item?id=2075192 http://news.ycombinator.com/item?id=2075192

50 points by bendmorris 16y ago

I think we would be remiss to mention that fundamentally the Lambda Calculus and Turing Machines are mathematically equivalent, as proved in the Church-Turing Thesis (http://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis http://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis ). And while it is true that there are functional features that are unsupported in the basic syntax of imperative languages, you can still do equivalent computation, and after all "Whoever does not understand LISP is doomed to reinvent it" :P

cyrus_ 16y ago
54. Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy. —Alan Perlis, Epigrams on Programming
- knowtheory 16y ago
  ha, that's great. I have to say learning about Lisp and the Lambda Calculus renewed my interest in computation and programming back in university. I really find Turing machines quite dull. Perhaps i did not adequately disclaim my statements though. Having to hack a LISP into your imperative language is neither easy, maintainable or recommended. Just cause you can do it, doesn't mean you should ;) The rest of the epigrams: http://www-pu.informatik.uni-tuebingen.de/users/klaeren/epigrams.html http://www-pu.informatik.uni-tuebingen.de/users/klaeren/epig...

Zak 16y ago

The author claims that Clojure tries to do OO. While Clojure does allow interaction with Java's object model, I think it's quite a stretch to say that it tries to do OO. Use of Java interop features for purposes other than interacting with a Java library or framework is generally discouraged.

swannodette 16y ago
The article is a year and a half old. Clojure doesn't "try" to do OO- multimethods always worked pretty well, and with 1.2.0 it does OO very well. Clojure design philosophy is essentially "OOP: The Good Parts".
- peregrine 16y ago
  As someone new to clojure I gotta say that multimethods are pretty nice.
- mahmud 16y ago
  For there to be "Good Parts" of OOP, there would have to be a single kind of OOP. P.S. Smalltalk.
  - jfoutz 16y ago
    i always miss interfaces in smalltalk. sometimes i really want a guarantee that the receiver will actually listen when i send a particular message. Even if you don't agree with that part, interfaces are really nice because the system will tell you, "hey, you forgot to add a method to respond to X. you got the other four, but spaced out this one. you should do something about that."
  - loewenskind 16y ago
    That doesn't follow. If we define "OOP" to encompasses everything that anyone calls OOP then it's very possible for there to be "good parts" and "bad parts" in that set. P.S. Smalltalk is a beautiful language with a great deal to offer anyone, but multimethods are superior. The fact that multimethods don't require multiple dispatch patterns demonstrates this.

cyrus_ 16y ago

The lambda calculus admits no notion of mutability, while the Turing machine is all about mutating locations on a tape. So I would argue that functional programming is really about immutability. A language is a functional programming language if its standard library includes and is written specifically for immutable data structures. Mutable data structures, if they exist, are second class citizens. Whether there is an object system is completely orthogonal. Whether there are first-class functions is also completely orthogonal.

jmillikin 16y ago
This is a very odd definition; it would exclude many languages typically considered "functional", such as Haskell.
- cyrus_ 16y ago
  Haskell's core data structures are immutable (ADTs, tuples, records, etc.) -- what do you mean?
  - jmillikin 16y ago
    I'm assuming anything in the "base" library counts as core; in it, you have pointer/buffer manipulation (Foreign.* ), synchronized mutable containers (Control.Concurrent.* ), ST (Control.Monad.ST), and various mutable containers (IORef, STRef, HashTable). It's true that Haskell has many immutable types, but that's true of almost any language. Haskell is no more immutable than Java or C#, and certainly nothing like truly immutable languages such as Coq or Agda.
    - gwern 16y ago
      Stuff in the sinbin (or the 'IO monad') are definitely second-class citizens in the language and community. And not all of those examples are mutable - the whole point of ST is that it's safe for it to be implemented using mutation while still being treated as having immutable semantics, this doesn't mean the compiler or library actually use mutation in ST code.

scottjad 16y ago

Functional means whatever the person saying it means by it. Trying to give an all or nothing definition is doomed to failure and counter-examples.

knowtheory 16y ago
“When I use a word,” Humpty Dumpty said, in a rather a scornful tone, “it means just what I choose it to mean—neither more nor less.” “The question is,” said Alice, “whether you can make words mean so many different things.” “The question is,” said Humpty Dumpty, “which is to be master that’s all.” Alice was too much puzzled to say anything, so after a minute Humpty Dumpty began again. “They’ve a temper, some of them—particularly verbs, they’re the proudest—adjectives you can do anything with, but not verbs—however, I can manage the whole lot! Impenetrability! That’s what I say!” and just for completenesses sake: Alan Perlis — 48. The best book on programming for the layman is "Alice in Wonderland"; but that's because it's the best book on anything for the layman.
- rufus_t 16y ago
  It, and "Through the Looking-glass", are very good books on programming for programmers, too. If you haven't read them since you were liddle, you're missing out.
gtani 16y ago
FP means different to lispers, ML'ers and typeclassists (haskell, scala). Here's my attempt at a def http://news.ycombinator.com/item?id=2075192 http://news.ycombinator.com/item?id=2075192