7 ms·

What is a functional programming language?

66 points by e1ven 17y ago

twism 17y ago
Didn't know clojure tries to do OO
- lg 17y ago
  Aside from all the Java crap it has multimethods, but it doesn't really make sense to call them OO because there's no object that they're attached to.
  - jrockway 17y ago
    OO is not about methods, it's about the data. Single-dispatch OO is just a special case of multimethod-based-OO, anyway. (Remember the whole "sending a message to an object" thing? You do that with both variants. In the single-dispatch case, the method is a structure in the metaclass instance. In the multiple-dispatch case, some other helper object finds the right method. Same idea, though.)
    - mahmud 17y ago
      You put it much better than I did; facts without rhetoric :-)
    - lg 17y ago
      Multimethods are ambient actions. You could implement them with functions and any sort of type system. Maybe also a way to have variable-length parameter lists. If that's OO then functional programming is object-oriented programming.
      - xtho 17y ago
        Multimethods means that a method is dispatched not only on basis of the receveiving object (or read: first argument) but on basis of all arguments. The term is inherently related to OOP: http://en.wikipedia.org/wiki/Multimethod http://en.wikipedia.org/wiki/Multimethod
      - jrockway 17y ago
        Yes, functional programming is very similar to OO. OO: class SomeType { <data> ; SomeOtherType function1() { this.whatever ; ... } } FP: data SomeType ... f1 :: SomeType -> SomeOtherType f1 this = whatever this >> ... Same idea, different syntax. (Type classes will allow polymorphism, if that's what you're after.) You are thinking of the abstraction in terms of its implementation. There is no reason why a method in a class would physically be in that class; the class just acts as a namespace: class Foo { method } Foo.method(); and (defmethod Foo.method ...) (Foo.method) are the same.
  - mahmud 17y ago
    Do you realize single-dispatching methods in class-based OOPLs are nothing but constrained generic functions? they're curried on one argument and nailed flat to the ground with a staple gun. I don't know about Clojure, but Common Lisp's "multimethods" are OOP on steroids; you could layout your code vertically in a parent/child class heirarchy and it would look no different than a "normal" class-based inheritance tree; all you have to do is visualize the method call in prefix mode: object.method (arguments) = method (object arguments) In essence, you could model Java and similar languages with a fixed and constrained Common Lisp. You just have to take its wheels off and lay it flat on bricks. Interested parties can go and learn CLOS for the full story. Spoiler, though: not long after, Lisp will start to hover! you just can't hold somethings down. If you thought of objects in terms of a vertical class heirarchy, or a side-ways call chain or what have you; CLOS will make your visualization planes intersect and show you new dimensions you never imagined..
  - scott_s 17y ago
    It's still OO, it's just not the style most people are familiar with. One can implement multimethhods in Java and C++, it's just cumbersome. (In fact, Stroustrup has said he wanted C++ to be able to do multiple dispatch at the language level, but he never found an expression and implementation that satisfied him in terms of performance and the type system.) CLOS has had multimethods for years, and that is indeed OO.
- Avshalom 17y ago
  I'm going to guess he meant clisp, clojure has a page specifically stating it doesn't do OO. (though of course with tuples and multimethods...)
  - scott_s 17y ago
    Clojure has a page specifically stating it doesn't take the traditional object-oriented approach - the Java/C++/C# one people are most familiar with: http://clojure.org/multimethods http://clojure.org/multimethods
- davars 17y ago
  It doesn't. Objects imply state and a set of methods to mutate that state, which is incompatible with Clojure's immutable-by-default design. Instead it provides tools that facilitate the same things as OO features: polymorphism via multimethods and inheritance via ad hoc hierarchies on names.
antipax 17y ago
Really enjoyed the explanation of how addition falls out of the lambda calculus, as I'd never seen that before.
- ambulatorybird 17y ago
  You can also do sequencing (assuming applicative order) and conditionals: 'a; b' ==> (fn x -> b) a true = fn x -> fn y -> x false = fn x -> fn y -> y if = fn p -> fn -> c -> fn a -> p c a
arohner 17y ago
I really enjoyed the distinction between languages based on turing machines and languages based on lambda calculus. I'd had a fuzzy idea of the distinction before, but this article set it out clearly.
jes5199 17y ago
okay, here's the argument as I read it: 1) functional languages are made of lambdas a) when they aren't made of lambdas, it's "just an optimization." 2) non-functional languages aren't made of lambdas b) when they have lambdas, it's just "style"
- silentbicycle 17y ago
  Try this: Functional programming languages have an underlying model based on function composition (with one argument functions, etc.). To the extent that they have arguments with multiple functions, etc., it's ultimately just syntactic sugar and optimizing for common cases - While nobody generally writes the low-level "lambda calculus virtual machine language" stuff by hand outside of academic papers or bootstrapping, Scheme's "let" is implemented in terms of lambda at compile-time. (Scheme without set! is representative.) Imperative languages have a fundamental underlying model of cells in memory and sequential operations that modify them, branch based on them, etc., including an instruction pointer specifying where instructions are currently read. (C is representative.) Intuitively (and without busting out the Greek letters): compare languages for which functions are a list of expressions, and return the value of the last, versus languages for which functions are a list of statements executed sequentially, the last of which can optionally return a value. A lot of other issues are ultimately due to how that choice directs default behavior. Even when a language has the amenities to borrow the other's tools, the defaults channel common usage. Likewise: Relational databases are ultimately based on the relational model, even when parts of SQL fill in conceptually irrelevant details for sake of performance; Prolog is based on backtracking and Horn clauses, and well-structured Prolog can be reasoned about in terms of them, even when cuts are used to avoid wandering about needlessly in known dead ends. The ultimate result would (eventually) be the same. Both models are fundamentally different from pure functional or imperative programming, as well, and the languages built on them are as different as Erlang is from Smalltalk. I'm self-taught and not a mathematician, so I couldn't give a really exhaustive or formal analysis of the distinction -- probably the best way to understand it (and learn quite a bit else, PS) is to work through the exercises in SICP and CTM. The second chapter of SICP includes Church encoding (http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-14.html#%_sec_2.1.3 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-14.html...), among many other things. SICP covers functional programming quite well, but CTM makes the fundamental differences between the different programming models and their strengths and weaknesses clearer. You can use functional idioms in imperative languages, but they may lack features such as tail call optimization or garbage collection, which mean that you're working at cross-purposes to both the semantics of the language and the cases for which its implementation has been optimized. Whether this means attempting to do so is actually infeasible (e.g. stack overflows in Python) or just slow and/or verbose depends on the language. Likewise, modeling problems in functional languages that are intrinsically better-suited to imperative languages can be messy and confusing. (OO is a completely different direction, but as people have wildly inconsistent ideas of what it actually refers to, I'm not going there.)
lutorm 17y ago
This strongly reminds me of listening to the first couple of lectures of SICP.
jberryman 17y ago
That was really well-written. I liked this line: > The Lambda Calculus is innocent of the notion of mutability
anatoly 17y ago
I found this post to be a poor attempt at shoehorning the notional of functional languages into lambda calculus. Sure, functional programming is inspired by lambda calculus, but it doesn't reduce to it, and, what's important, never has - from the very first LISPs on. So, for example, Church's encoding of naturals is introduced, which is totally irrelevant to all practical functional languages. Despite what the author is saying, using computationally sane integers is not "nothing more than an optimization", but a fundamental part of the language (and don't get me started on floats). It's just that actual functional programming languages model a lambda calculus with atoms - basic objects, like integers, that are not functions. It's really OK - not everything needs to be a function! The fact that it's possible, in pure lambda calculus without atoms, to model integers using Church's trick is cool and has theoretical significance - but no relevance at all to functional languages. Similarly, functional programming has always included languages with mutable data. LISP was mutable from day 1, and so was the even more functionally-inclined Scheme. There's nothing in "functional programming", as has been practiced for decades, that necessarily excludes mutable data. Now, "pure lambda calculus" is another story... but it really is another story, one that serves as a motivation for functional programming rather than all of its being. The requirement that a functional language, in the author's opinion, must have tail call optimization, is weird (many LISPs don't have that), and its explanation is weirder yet: a functional language must have TCO because it's based on lambda calculus where everything is done with recursion, so you need infinite stacks (???), but real stacks aren't infinite, so "you need tail call optimization to allow the use of recursion for looping". Well, what if you don't use recursion for looping, just as you don't use Church's encoding for integers, because you are not after all writing in lambda calculus? Overall, I felt that the author let his intuition of what a functional language could be settle too firmly on Haskell (with the understanding that static typing is optional), and is trying to redefine functional programming in accordance with this vision.
- anc2020 17y ago
  Lisp was by all accounts an attempt to make a working lambda calculus[1]. However the machines weren't very quick then and speed was a real issue. Even later on when Scheme was designed, speed was an important consideration, and it probably did affect the resulting language. What the author was saying about TCO was that, based on the fact that all our machines today use stacks, and not wanting to have programs that break(!), any implementations of lambda calculus on these machines must have TCO to allow as much of the lambda calculus as possible to be available in the programming language, lest you reject otherwise correct programs. But make no mistake, Lisp[2] and functional programming languages ARE based on the lambda calculus. The article really did hit the nail on the head. -- [1] "Lisp was originally created as a practical mathematical notation for computer programs, based on Alonzo Church's lambda calculus." -- Wikipedia (http://en.wikipedia.org/wiki/Lisp_%28programming_language%29 http://en.wikipedia.org/wiki/Lisp_%28programming_language%29) (and lots of other sources agree with this) [2] Sorry to say it, but Lisp isn't the center of the Universe. It's a cool trick, but it isn't that great.
JulianMorrison 17y ago
A student once asked his teacher "is Scala a functional programming language?" The teacher gave a shout and began hitting the student mercilessly with a chair, until he was forced to flee the room. The student was enlightened, and wrote his program in Scala.

66 points by e1ven 17y ago

twism 17y ago

Didn't know clojure tries to do OO

lg 17y ago
Aside from all the Java crap it has multimethods, but it doesn't really make sense to call them OO because there's no object that they're attached to.
- jrockway 17y ago
  OO is not about methods, it's about the data. Single-dispatch OO is just a special case of multimethod-based-OO, anyway. (Remember the whole "sending a message to an object" thing? You do that with both variants. In the single-dispatch case, the method is a structure in the metaclass instance. In the multiple-dispatch case, some other helper object finds the right method. Same idea, though.)
  - mahmud 17y ago
    You put it much better than I did; facts without rhetoric :-)
  - lg 17y ago
    Multimethods are ambient actions. You could implement them with functions and any sort of type system. Maybe also a way to have variable-length parameter lists. If that's OO then functional programming is object-oriented programming.
    - xtho 17y ago
      Multimethods means that a method is dispatched not only on basis of the receveiving object (or read: first argument) but on basis of all arguments. The term is inherently related to OOP: http://en.wikipedia.org/wiki/Multimethod http://en.wikipedia.org/wiki/Multimethod
    - jrockway 17y ago
      Yes, functional programming is very similar to OO. OO: class SomeType { <data> ; SomeOtherType function1() { this.whatever ; ... } } FP: data SomeType ... f1 :: SomeType -> SomeOtherType f1 this = whatever this >> ... Same idea, different syntax. (Type classes will allow polymorphism, if that's what you're after.) You are thinking of the abstraction in terms of its implementation. There is no reason why a method in a class would physically be in that class; the class just acts as a namespace: class Foo { method } Foo.method(); and (defmethod Foo.method ...) (Foo.method) are the same.
- mahmud 17y ago
  Do you realize single-dispatching methods in class-based OOPLs are nothing but constrained generic functions? they're curried on one argument and nailed flat to the ground with a staple gun. I don't know about Clojure, but Common Lisp's "multimethods" are OOP on steroids; you could layout your code vertically in a parent/child class heirarchy and it would look no different than a "normal" class-based inheritance tree; all you have to do is visualize the method call in prefix mode: object.method (arguments) = method (object arguments) In essence, you could model Java and similar languages with a fixed and constrained Common Lisp. You just have to take its wheels off and lay it flat on bricks. Interested parties can go and learn CLOS for the full story. Spoiler, though: not long after, Lisp will start to hover! you just can't hold somethings down. If you thought of objects in terms of a vertical class heirarchy, or a side-ways call chain or what have you; CLOS will make your visualization planes intersect and show you new dimensions you never imagined..
- scott_s 17y ago
  It's still OO, it's just not the style most people are familiar with. One can implement multimethhods in Java and C++, it's just cumbersome. (In fact, Stroustrup has said he wanted C++ to be able to do multiple dispatch at the language level, but he never found an expression and implementation that satisfied him in terms of performance and the type system.) CLOS has had multimethods for years, and that is indeed OO.
Avshalom 17y ago
I'm going to guess he meant clisp, clojure has a page specifically stating it doesn't do OO. (though of course with tuples and multimethods...)
- scott_s 17y ago
  Clojure has a page specifically stating it doesn't take the traditional object-oriented approach - the Java/C++/C# one people are most familiar with: http://clojure.org/multimethods http://clojure.org/multimethods
davars 17y ago
It doesn't. Objects imply state and a set of methods to mutate that state, which is incompatible with Clojure's immutable-by-default design. Instead it provides tools that facilitate the same things as OO features: polymorphism via multimethods and inheritance via ad hoc hierarchies on names.

antipax 17y ago

Really enjoyed the explanation of how addition falls out of the lambda calculus, as I'd never seen that before.

ambulatorybird 17y ago
You can also do sequencing (assuming applicative order) and conditionals: 'a; b' ==> (fn x -> b) a true = fn x -> fn y -> x false = fn x -> fn y -> y if = fn p -> fn -> c -> fn a -> p c a

arohner 17y ago

I really enjoyed the distinction between languages based on turing machines and languages based on lambda calculus. I'd had a fuzzy idea of the distinction before, but this article set it out clearly.

jes5199 17y ago

okay, here's the argument as I read it: 1) functional languages are made of lambdas a) when they aren't made of lambdas, it's "just an optimization." 2) non-functional languages aren't made of lambdas b) when they have lambdas, it's just "style"

silentbicycle 17y ago
Try this: Functional programming languages have an underlying model based on function composition (with one argument functions, etc.). To the extent that they have arguments with multiple functions, etc., it's ultimately just syntactic sugar and optimizing for common cases - While nobody generally writes the low-level "lambda calculus virtual machine language" stuff by hand outside of academic papers or bootstrapping, Scheme's "let" is implemented in terms of lambda at compile-time. (Scheme without set! is representative.) Imperative languages have a fundamental underlying model of cells in memory and sequential operations that modify them, branch based on them, etc., including an instruction pointer specifying where instructions are currently read. (C is representative.) Intuitively (and without busting out the Greek letters): compare languages for which functions are a list of expressions, and return the value of the last, versus languages for which functions are a list of statements executed sequentially, the last of which can optionally return a value. A lot of other issues are ultimately due to how that choice directs default behavior. Even when a language has the amenities to borrow the other's tools, the defaults channel common usage. Likewise: Relational databases are ultimately based on the relational model, even when parts of SQL fill in conceptually irrelevant details for sake of performance; Prolog is based on backtracking and Horn clauses, and well-structured Prolog can be reasoned about in terms of them, even when cuts are used to avoid wandering about needlessly in known dead ends. The ultimate result would (eventually) be the same. Both models are fundamentally different from pure functional or imperative programming, as well, and the languages built on them are as different as Erlang is from Smalltalk. I'm self-taught and not a mathematician, so I couldn't give a really exhaustive or formal analysis of the distinction -- probably the best way to understand it (and learn quite a bit else, PS) is to work through the exercises in SICP and CTM. The second chapter of SICP includes Church encoding (http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-14.html#%_sec_2.1.3 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-14.html...), among many other things. SICP covers functional programming quite well, but CTM makes the fundamental differences between the different programming models and their strengths and weaknesses clearer. You can use functional idioms in imperative languages, but they may lack features such as tail call optimization or garbage collection, which mean that you're working at cross-purposes to both the semantics of the language and the cases for which its implementation has been optimized. Whether this means attempting to do so is actually infeasible (e.g. stack overflows in Python) or just slow and/or verbose depends on the language. Likewise, modeling problems in functional languages that are intrinsically better-suited to imperative languages can be messy and confusing. (OO is a completely different direction, but as people have wildly inconsistent ideas of what it actually refers to, I'm not going there.)

lutorm 17y ago

This strongly reminds me of listening to the first couple of lectures of SICP.

jberryman 17y ago

That was really well-written. I liked this line: > The Lambda Calculus is innocent of the notion of mutability

anatoly 17y ago

I found this post to be a poor attempt at shoehorning the notional of functional languages into lambda calculus. Sure, functional programming is inspired by lambda calculus, but it doesn't reduce to it, and, what's important, never has - from the very first LISPs on. So, for example, Church's encoding of naturals is introduced, which is totally irrelevant to all practical functional languages. Despite what the author is saying, using computationally sane integers is not "nothing more than an optimization", but a fundamental part of the language (and don't get me started on floats). It's just that actual functional programming languages model a lambda calculus with atoms - basic objects, like integers, that are not functions. It's really OK - not everything needs to be a function! The fact that it's possible, in pure lambda calculus without atoms, to model integers using Church's trick is cool and has theoretical significance - but no relevance at all to functional languages. Similarly, functional programming has always included languages with mutable data. LISP was mutable from day 1, and so was the even more functionally-inclined Scheme. There's nothing in "functional programming", as has been practiced for decades, that necessarily excludes mutable data. Now, "pure lambda calculus" is another story... but it really is another story, one that serves as a motivation for functional programming rather than all of its being. The requirement that a functional language, in the author's opinion, must have tail call optimization, is weird (many LISPs don't have that), and its explanation is weirder yet: a functional language must have TCO because it's based on lambda calculus where everything is done with recursion, so you need infinite stacks (???), but real stacks aren't infinite, so "you need tail call optimization to allow the use of recursion for looping". Well, what if you don't use recursion for looping, just as you don't use Church's encoding for integers, because you are not after all writing in lambda calculus? Overall, I felt that the author let his intuition of what a functional language could be settle too firmly on Haskell (with the understanding that static typing is optional), and is trying to redefine functional programming in accordance with this vision.

anc2020 17y ago
Lisp was by all accounts an attempt to make a working lambda calculus[1]. However the machines weren't very quick then and speed was a real issue. Even later on when Scheme was designed, speed was an important consideration, and it probably did affect the resulting language. What the author was saying about TCO was that, based on the fact that all our machines today use stacks, and not wanting to have programs that break(!), any implementations of lambda calculus on these machines must have TCO to allow as much of the lambda calculus as possible to be available in the programming language, lest you reject otherwise correct programs. But make no mistake, Lisp[2] and functional programming languages ARE based on the lambda calculus. The article really did hit the nail on the head. -- [1] "Lisp was originally created as a practical mathematical notation for computer programs, based on Alonzo Church's lambda calculus." -- Wikipedia (http://en.wikipedia.org/wiki/Lisp_%28programming_language%29 http://en.wikipedia.org/wiki/Lisp_%28programming_language%29) (and lots of other sources agree with this) [2] Sorry to say it, but Lisp isn't the center of the Universe. It's a cool trick, but it isn't that great.

JulianMorrison 17y ago

A student once asked his teacher "is Scala a functional programming language?" The teacher gave a shout and began hitting the student mercilessly with a chair, until he was forced to flee the room. The student was enlightened, and wrote his program in Scala.