Slashdot Mirror
What About Functional Languages?
sdavies asks: "Functional languages like Scheme and Haskell are great! (here is a PS viewer) They give programmers new tools for elegance and abstraction. Unfortunately, to the legions of procedural programmers writing in languages like C/C++(/C#), Java, and VB, functional languages are considered obscure and impractical. What is your experience with functional languages, and what do you think is preventing them from being adopted into the mainstream?"
I've always thought about submitting one of these "why not functional?" or "why not ML?" ask slashdots... but I think I know the answer.
My favorite functional language is ML (standard). It isn't "purely functional" like haskell (though we often write purely functional programs); it includes imperative features like assignment and arrays and IO, which are usually useful in real programs.
I work on an ML compiler here at CMU called TILT (which I'd like to think is one of the most advanced research compilers around), so I am sort of biased. But I also know what I'm talking about...
(Incidentally, the FoxNet Web Server is written entirely in standard ML, including the network stack (with ethernet, down to the hardware device driver)!)
Anyway, back to the question. Why does functional programming matter?
Programming functionally is closer to thinking in terms of math. Lots of algorithms and data structures are expressed more beautifully in a functional style. It's almost impossible to write gross hacks if you're programming functionally (most quick hacks actually turn out looking quite beautiful). Programming functionally has some direct advantages in this vein, and I find that I write better code faster when I write functionally. (I'll admit to hating it for a semester! But once I got used to it, I don't want to go back...)
There are some awesome features of most functional languages, most notably: Parametric Polymorphism and Higher Order Functions. (more rarely, such gems as functors and higher-order continuations (aka callcc; think a typed and higher-order setjmp). These all deserve their own posts to explain their incredible benefits. You are missing out if you've never written a program using these features.
But mostly, functional programming is useful for its indirect benefits. Let me explain some of these:
- Concurrency. Writing concurrent programs in a functional language is so much more natural. It's easier to avoid certain kinds of race conditions too, since you don't update variables in a functional language. SML/NJ has an awesome concurrencly package called CML .
- A powerful static type system and type safety. It's difficult to design a language (and many smart people have tried) that's imperative, type safe, and powerful. Features of functional languages like garbage collection and non-updatable values make it easier to define a language with a powerful type system. (in case you're still stuck in the 60s, type safety guarantees that your program CANNOT crash at runtime. No more uninitialized pointers, using memory after it's freed, bad casts, or other plagues of C++ programming).
A powerful static type system gets you a lot:
- Debugging. It's easier to find mistakes in your program. When I program in ML, I get a list of all the type errors in my program when I compile. I can go back and fix these before I have to run my program on test cases, etc. Debugging is so much easier. It's hard to explain how incredibly useful this is compared to programming in C++. Everyone who's used ML can attest to this fact: once your programs typecheck, they Just Work.
- Your programs run faster. Java has a somewhat more mature type system than C++ (it guarantees safety, for instance), but most of this is dynamic. That means all your objects are tagged, and these tags are checked frequently to make sure you're not doing anything wrong! There's no way the compiler can optimize these out; mistakes in the definition of the language (array subtyping) make tags necessary for type-safety. In ML, we don't have to tag values or check them at runtime. Yet we guarantee our programs run safely because we verify all of the types at compile-time!
- Compiler Technology Advances. Most research in programming languages and compilers these days is on languages with interesting type systems. We're seeing fewer and fewer improvements to C compilers, and lots of improvements on "advanced" programming languages. The type system allows you to make more optimizations, because the compiler has more information available to it. Some concrete examples:
Aliasing - a big problem for C/C++/Java compilers. If you've ever looked at the machine code they produce, you've seen this effect. "Why is it fetching that address again??" ... because two pointers may have pointed to the same thing, and in order to preserve the semantics of the language, redundant work is done. When you're not doing updates (functional programming), the compiler doesn't have to worry about aliasing.
Function Calls: Practically every C/C++ compiler treats functions as a black box. Languages with stronger type systems are able to optimize around function calls because much more information (types) are available.
Our TILT compiler that I mentioned earlier does something rather new: Each compilation phase transforms not only the program but its type. We keep the type information around even when we are dealing with assembly language! This enables us to perform some unprecedented optimizations.
- Machine independence. Making a type system usually means hiding away the details of the machine, and this usually means that the execution of your program is completely predictable. (Compare to C/C++ "undefined" behavior!) ML programs are extremely portable.
- Modularity. I was able to understand and start working on the (100,000 line+) TILT compiler in a matter of days rather than weeks because of ML's strong modularity features. The most interesting of these are:
Signature Ascription - This allows you to define abstract data types by naming a type and some operations on it (and their types). This is similar to header files in C (much more refined), but thanks to the type system, you can guarantee that the user can ONLY use your abstract data type the way you intended. They cannot cast, subclass, or use any other tricks to get at your datatype. (Some OO folks have solutions for this too, but they are not as elegant). This is awesome, because it helps you figure out where bugs are. I can attest that this really works; my project this summer is to change the way a very important module works... and so far, I have only experienced one observable effect of changing the representation!
Functors - This is somewhat like C++'s template system (but more refined); allowing you to write programs which operate on modules. (Ie, you give me a module which implements sets, and I'll give you back a module which implementes maps). This is very useful, and since all the work is done at compile-time, incurs no runtime cost.
- Proof-carrying code. You haven't seen this yet, but you will. What if you could download a program off the internet and run it, knowing that it won't do anything wrong? What if it wasn't subject to sandboxing (and slowdown) like Java apps? What if you didn't need to trust the source (certificats/signing)? Proof-carrying code carries a proof of its type-safety (and other safety metrics) with it; your computer verifies the proof and then runs the bare code! You can read more about this here .
Now here are some answers to the question of why not functional?
- RIGHT NOW, functional languages are slower (estimate 2x) than languages like C. Against a "modern" language like Java they fare rather well. Compiler technology is advancing and will fix this! I'd also argue that the other benefits (developer productivity, code maintainability) far outweigh the slowdown.
- Functional is weird for a lot of people. It took me at least 6 months to figure out why it was good, and I consider myself a pretty good hacker. Most people are more comfortable with imperative languages (at first...), possibly because that's usually their introduction to programming.
- There are not many commercial applications for functional programming yet (outside of Ericcson), and some people just program for money.
I would like to see the hacker types of the world pick up some new, interesting languages. Most of these languages don't have powerful marketing engines like Sun or Microsoft behind them, but hacker types are (usually) smart enough to see past that stuff!
I like SML a LOT, but there's a langauge which a lot of people aren't talking about. It's LISP. LISP has a public-domain compiler, an orphan of the Carnegie Mellon University lisp project from about 8 years ago. (CMUCL)
The compiler (Python) is fast; it compiles down to raw machine code, and it's performance is comparable to C, and has been for the last 5 years. (~30% slower at things like matrix multiplication, bench it yourself) , which isn't bad for a compiler that's had a fraction of the effort of EGCS. It can use non-descriptor arguments and structures. It will also use type inference where it can (Roughly, the monomorphic subset of the type system of SML.)
Now, the language Common Lisp is exremely nice. It has a variety of built-in things like lists, hash tables, structures, vectors, multidimensional arrays... It's got a lot of declarative things too. Loops, 'foreach', 'set'... Lisp programs can't crash because it does typechecks too. (Though if Python infers that they're unnecessary, it'll omit them.)
It was the first object-oriented langauge to be standardized. CLOS (Common Lisp Object System) is amazing. You can have dispatch based on multiple arguments unlike java/C++ which is only polymorphic based on the first argument. And you've got multiple inheritence. With the MOP, you can even write your OWN OO system on top of it.
Because the syntax is simple, it makes it easy to have programmed transformations of code 'macros'
A simple example is a 3-way if-then. (:less,
A slightly more complicated example is adding in c-style for-loops. (done with the 'loop' facility)
For a fairly complicated example, there's a package called 'SERIES' which adds in the equivalent of pipes to the language. You 'pipe' data between routines and it transforms the code into minimum-sized loops and other iteration constructs.
For example, if I have a list of triangles. My code looks like I first transform all of the triangles, then texture them, then transform them. again. This requires creating lots of superflouis triangles. SERIES will automagically turn this into a single loop on each triangle 'tranform -- texture -- transform'. Except that it'll handle multiple argument functions that return multiple results, and it'll handle conditionals in the functions. Not all loops can be merged, but it'll do what it can.
This is much like the one example of aspect-oriented programming, which was a realtime handwriting recognition program. It needed to do edge detects, averaging, convolutions. To do each operation in turn would have been horrific in time and space. The loops could be merged manually, but obfuscated the core algorithms and made it difficult to modify. The overhead of doing this transformation manually was a 50x code increase. From 700 lines to 35000 lines!
They implemented a new mini-langauge (Adding 'primitive' things like pointwise, convolve, etc to the language.) and used macro's do that merging automatically made the core algorithm obvious and trivial to change. The result was the core algorithm required only 700 lines of code, and another 1000 lines of code to do the merging and fusing of loops.. 2000 lines of code to do what took 35000 lines of code to do manually!
If you come from LISP, Aspect oriented programming is stupidly obvious. (If you don't, you think, 'wow' look at the cool stuff that they invented, and think that they created it.)
As a much much more complicated example, CLOS itself was implemented through macro's. Can you imagine a language powerful enough that you could 'transparently' layer a high-performance and very flexible OO system on top, WITHOUT REWRITING the underlying layer? Aspect oriented programming will never get this good. :)
Yet another plus of this is that you can runtime-generate and compile code. Want to compile that encryption inner loop to make a custom version for this key? It's as easy as
,key)))
(defun twofish-make-fun (key)
(compile nil `#'(lambda (block) (twofish-encrypt block
This works because the function 'twofish-encrypt' will be declared maybe-inline. Thus it'll be compiled as normal, but the source code will also be saved. Normally, a function call to it will invoke the unspecialized version. But if we compile a call to it that has known arguments, the compiler will fully specialize and inline it, and create a specialized assembly. (This is how CLOS is implemented.)
There are some nice advantages to having a simple syntax. :)
For hackers, there's the advantage that you can download ``Common Lisp The Language'' or the ``Common Lisp Hyperspec'' for a full specification of the language. No spending a hundred bux on a manual. (I'd give links, but I use my personal version so I don't know where to find them on the net anymore.)
Common LISP still has the features of a functional language. It has first-order and higher-order functions or closures. Python has a strong type system and it makes fast code. Your claim that LISP runs slow is false. :) Like SML, it's interactive and incremental compilation. You can redefine functions without quitting. You can even redefine functions that are running in a different thread.
In fact, LISP was found to be almost 50% faster than C/C++ on average. There was a study done about a year ago where they compared C++ and Java. Unlike other study's between langauges, they had a dozen people implement the same program in C++ and Java and then compared the results. They found what you'd expect, Java was slow and sucked memory.
These guys decided to repeat the study, only comparing LISP and Java. Although the fastest implementation was in C++, they found that Lisp programs, as a group, were over 50% faster than the C++ programs as a group. Also, development time was a fraction that of C++ or Java, and the number of lines of code was half. Not only that, the variability in the number of lines of code and development times was signifigantly reduced.
(Tom, I'll be back at CMU in a month, if you want to talk about this, or let me get my greedy hands on the TILT compiler. Send mail to crosby@qwes.math.cmu.edu if interested.)
(are(languages(These), nice)
(Easy(to_write(code(bug_free))))
(If(can(read(you, them)))))
Donate background CPU time to fight cancer.
The language industry is dominated by network effects. There are major costs with using a minority language, and for an individual project these completely outweigh the benefits, even when the benefits are very large. Hence it is generally far better to stay with a majority language. The costs of a minority language include:
So, overall the PMs want to go with popular languages, not for PHM reasons, but for entirely rational local reasons. But rational local decisions turn into globally arbitrary decisions, as the entire herd gallops off in a random direction chosen only because most of the herd thought that most of the herd were headed that way.
The lesson of this is that if you want to introduce a language, you don't concentrate on making it a good language, you try to persuade the herd of programmers, PMs and tool vendors that your language is the Next Big Thing. The important point here is not how much the language will do for productivity, quality and cost, it is to create the perception that everyone else thinks that this language will be the next big thing.
There are two ways to do this. One way is to tackle the whole industry at once. For an object lesson in how to do this, see Java. For an object lesson in how not to do it, see Eiffel. Believe me, I know all about this. I have spent a long time giving presentations extolling the technical virtues of Eiffel, only to have my audience say "y Yes, but in the Real World....". In the Real World what counts is the network effects. And you know what? My audiences were right. It has taken me a long time to realise this.
The other more interesting and more promising way to introduce a new language is to identify a niche market and attack that. Once you have taken over your niche you can expand to nearby niches and start to build momentum. Python is doing exactly this in web serving, for example. Web serving is a good niche because lots of people do it, and productivity and quality generally count for more than raw performance. Projects also tend to be small, so experiments are not the Career Limiting Moves they are for large projects. Education can also be a useful niche if you can afford to take the long view, which is how Pascal, Basic and Unix got started.
Paul.
You are lost in a twisty maze of little standards, all different.
I took a course on Programming Langauges, and we studied Scheme as our first language. It was a major hurdle for many people. This is probably because you have to think in functions and recursively, as opposed to the structured/imperative way of assignment.
;) The fact that it is not typed and makes it a little slower is also a factor. They also hate Lots of Infernal Stupid Parenthesis! =)
The ultimate goal of functional languages is to have everything act as a function of it's inputs. Setting variables should not be necessary. However, it never works out that way. It would be hell to write that many functions. The spirit is still there, tho.
Probably the biggest problem was the fact that a function is a first-class value (i.e., it can be passed as a parameter, returned from a function and assigned to a variable). Writing functions within functions to take care of little recursive problems was a major stumbling block. Instead of single-stepping your way through an algorithm, you thought of a way to write an anoymous function inside another function to take care of a something. This function is not defined - it is created at run-time. The fact that you could return it was weirding people out as well.
Another thing that throws people for a loop is the lack of non-local exits. There is no return in Scheme (or Elisp. I don't know about Lisp, but I would imagine it is similar). Instead, you have a very generalized procedure called call-with-current-continutation that does everything return does and more. It actually allows you to save the state of your program, put it in a variable and use it again later. Thus, you can make generators for infinite data structures. This is hard to grasp, especially after two years of C/C++/Java.
The fact that everything is a list in Scheme and it is not typed can be a bit of a stumbling block.
Structured/imperative programming is a much more natural way to program - at first. When you get some practice in functional languages, you see how incredibly powerful they can be. (this is not to say C/C++ style languages aren't powerful. They just lack some really handy features functional languages have as primitives)
I think people avoid them because of the total paradigm shift that is involved. It really is quite a leap. There is no lack of literature on it, it's just not published by IDG Books or SAMS
Woz
Mostly, there were no implementations. Plus it's sort of like the Micro$oft dominance -- all the good stuff was written in procedural languages (primarily C/C++), so why fight it? But the real question is why did procedural languages win?
What I don't believe is that it is harder or less natural to think functionally than procedurally. It's just what one is taught.
Like recursion, for instance. In my small experience teaching, I saw the light go on with regularity -- you just chip away at the problem, deal with some part of it, and then (recursively!) deal with the remaining simpler problem. Hmm, that doesn't seem so hard.
Most people don't think about transactional database programming as being like FP, but just think about it -- it's just like Backus' Applicative State Transitions, where one computes the proposed new state, validates it so far as possible, and then installs it as the basis for more computation.
Another thing to think about is the long-standing tradition in math of "recurrence" relations, like the Fibonnaci series, or approximations to pi, or whatever. Those are clear examples of things which could be thought of as iterative or recursive, just depending on the color of the lightbulb.
... an idea, the fugitive fermentation of an individual brain ... -- T. Jefferson
Trained staff in a minority language are going to be rare. This does not necessarily make them more expensive (nobody else wants them), but it does make recruitment much harder and more uncertain.
A corollary to this is that programmers are going to be less willing to learn a language that no other employer is going to want. Having a few years of intensive (not an insult, just an example) Eiffel experience on your resume might just be a recipe for unemployment, whereas Java programmers are practically carjacked by prospective employers these days. Acquaintences of mine have quit jobs just to avoid being put into this position.
I think the real reason Java and Perl have been successful is that they were all carefully designed to resemble established, popular languages. Stroustup's stated goal in designing C++ was compatibility with C. Java is basically a simplified C++ with garbage collection. Perl is based in awk, sed and unix shell. All of these languages have marginalized languages that are technically superior in many ways - C++ vs. Ada or Modula, Java vs. Smalltalk, and Perl vs. Python.
Unfortunately, most of the obstacles to the acceptance of a new language are social rather than technical. Backward compatibility and the support of a powerful company are key. A new language faces the same resistance that a new operating system does. Corporations and programmers have made substantial investments in their current toolsets and skills and are very reluctant to throw that time and money away. Something like Java, that looks and feels very familiar, is palatable, but something like Haskell causes panic.
Open source programmers are lucky, though, because there are far fewer constraints on the tools and languages they use. We pride ourselves on making design and implementation decisions on a strictly technical basis, and there's no reason we shouldn't make our choice of languages any other way. There are a number of high quality free implementations of functional languages out there.
I've spent the last few years studying functional programming in my spare time. While I'm not sure that I'll ever use a functional language professionally, there's no question that I'm a much better programmer than I would be otherwise. Libraries like the C++ STL and language extensions like Java's anonymous inner classes make a lot more sense if you've been exposed to closures and generic functions. Studying CLOS makes the limitations of single-dispatch OO systems like C++ and Java clear. But most importantly, functional languages help you see the larger picture - to focus on the architecture of a system without getting lost in implementation details. My experience with functional programming has taught me more about software design than the shelves of OO design pattern books and UML bibles I've waded through.
Any programmer that really loves the craft of programming owes it to themselves to take a walk on the wild side with a functional language or two. I'd recommend Ocaml, a mature, full-featured system that comes with a blazingly fast byte-code and native code compiler, a debugger and profiler, a first-class YACC-like compiler generation tool, a full-featured standard library, and a growing collection of contributed code. If you really want your mind blown, read SICP.