You are viewing chaource

 
 
03 July 2008 @ 11:44 am
Why functional programming is almost dead (and has always been)  
Is LISP dead? -- Well, it doesn't look any deader than usual to me. — David Thornley, reply to a question older than most programming languages

Programming is broadly divided into imperative and functional styles. In the imperative style we have variables that represent locations in memory. Variables have values, and we can change those values. So most of the time we manipulate the state of objects stored in memory, make new objects etc. Eventually the state of some objects stored in memory becomes what we want to compute, and that's the result. The oldest (and still alive) imperative language is Fortran.

In the functional style, variables (as a rule) are immutable; they can be assigned once and that's it. So variables are not locations in memory but rather labels set for convenience on some constant expressions. (In some functional languages, there are mutable variables too; but these languages are called "impure" functional languages.) In a functional language, most of the time we manipulate functions and values, rather than states of objects. We make new functions from old ones, or recursively transform one function call into another until we get the right function call at the end. The only place where something changes is the arguments of functions and the functions themselves. The result of a computation is a single object (which is, perhaps, a function rather than a number). The oldest (and still alive) functional language is Lisp.

There has been a lot of debate about which programming style is "better". However I haven't ever seen any company advertising a job that needs proficiency in Lisp or in any other functional language (Scheme, OCAML, Haskell, ...). Instead companies want skills in Java, C++, and other imperative languages. Why is that?


An example program to compute the average of a list of N numbers:

Imperative style (C):

float average(int N, float* given_list)
{
  int sigma = 0, i = 0;
  for (; i < N; i++)
  {
    sigma += given_list[i]; 
  } 
  return (sigma/N);
}


This program will initialize the counter i and the result accumulator sigma, then update sigma as it goes through the first N elements of the given array. Note that there is no easy way to determine the length of the array given the array pointer; so the length N is passed explicitly and the program has no way to determine whether the value N is correct. The program crashes if N is out of bounds.

Pure functional style (OCAML):

let average (N:int) (given_list:float list) = float_sum(list, 0) /. float_of_int(N)

let rec float_sum(given_list:float list, result:float) = match given_list with
 | [] -> result 
 | first :: tail -> float_sum(tail, first +. result)


This program computes the sum of all the elements in the given list and divides by N. The auxiliary function float_sum(l, result) returns (result + sum of the list l). The argument labeled result here plays the role of the accumulator sigma in the above C code. It is initialized in the first (and only) call of float_sum. Care has been taken to write the function float_sum in a tail-recursive style, so that the compiler can optimize this code. A non-tail-recursive style would be

let rec float_sum(given_list) = match given_list with
  | [] -> 0
  | first :: tail -> first + float_sum(tail)


The program does not check that given_list actually has length N. It is possible to make the program do so, at the expense of further complicating the auxiliary function float_sum. But my head already hurts trying to write this much in a pure functional style with correct tail recursion, using the insane syntax of OCAML.

Proponents of Fortran say that Fortran is easier to use, and that you can't get good performance, good parallel code on supercomputers, fast matrix multiplication, etc., without Fortran. Other imperative languages compete in the compiler features, portability, richness of libraries, syntax conventions, facilities for rapid GUI prototyping, and development environments. Proponents of Lisp and other functional languages say that functional languages are much more powerful than any imperative language, that functional languages have solid mathematical foundation, and that good optimizing compilers can give you the same performance as imperative languages. There is an outstanding example of the functional language SISAL that was designed specifically for fast numerics and for producing automatically parallelizable code for arbitrary supercomputers. SISAL outperformed Fortran (by factor 6 or so) on a Cray parallel computer. Nevertheless, SISAL never got any use outside the lab (LLNL), and in a few years the LLNL project group on SISAL was cancelled. Today SISAL is so dead that I couldn't even find a working link for the language manual (despite the presence of a sisal.sf.net project). A language that seems to be more alive is OCAML. That language also has provisions for optimized numerics and gets occasionally used, mostly by researchers. The degree of aliveness can be judged by the number of books written about the language. There are a total of three books on OCAML in existence.

It seems that functional programming is somehow so unattractive that no amount of technical merit can make people actually start using Lisp or any other functional language. Entire projects and corporations can be persuaded to switch from Fortran to C++, from C++ to Java, and from Java to .NET, but not to a functional programming language.

This is puzzling. I would like to understand this phenomenon. My short answer so far: Functional style is inherently difficult and goes against people's intuition about the real world and about calculations.

Programming language needs to be designed for people's understanding and not only for specific tasks and/or computer architectures. A very powerful language such as OCAML allows you to write very short code (they call it "expressive" code) but requires a lot of thought and concentration to write that code so that it works at all. (When it works, it usually works correctly.) There are perhaps too few programmers who are able to use OCAML (or Lisp) effectively, compared with a large number of programmers who have studied Pascal or Basic at school and subsequently C++ or Java at college. Functional languages are perhaps too complicated for the kind of workforce we have.

Why is C++ or Java easier? I think it's the imperative style that is easier. Yes, you can pass a function as an object in C++ or Java when it suits you, but most of the time you program in the imperative style because the language invites you to do so and makes purely functional style much more difficult.

It is easier to learn programming in the imperative style a direct manipulation of state accords with people's intuition. It's easy to imagine a variable as a box with a number in it (or perhaps with an object in it). It's easy to build a complete and adequate mental model for what is going to happen with the box when the computer runs your program; you just go through your program statement by statement and update the contents of the boxes.

The fact that a Fortran program becomes unmanageable for very large projects (regardless of the degree of object-orientedness, structured-ness, use of libraries, etc.) may be apparent but will not deter Fortran use until it's too late. This is similar to the fact that people will eat cakes despite knowing that it will possibly ruin their health.

Why is imperative style unmanageable? Unmanageable means that the functioning of the program as a whole becomes difficult or impossible for humans to understand in all detail. Understanding is roughly equivalent to being able to produce an (informal) proof of correctness for the program. Computer scientists have stidied formal languages and found that it is very difficult to prove correctness of programs in general, but this task becomes much easier for purely functional programs. This is so because manipulation of values in memory cannot be converted into a concise algebraic description of the logic of the program, but evaluation of constant expressions is equivalent to some reasonably straightforward algebraic constructions (lambda-calculus). When proving correctness of a program, it is helpful to construct invariants, that is, conditions that remain valid in a given place in the program. In the imperative style, a given place in the program can be visited many times (in a loop, or in different function calls), and then invariants are frequently broken because many memory locations have changed. This is the basic reason why it is so difficult to make sure a complicated program works correctly if one writes in the imperative style.

In the pure functional style, any expression is constant and so can be computed once and for all; it does not matter in which order the expressions are computed. So an invariant at a given place in the program is only a single condition to be checked, namely that a certain expression (made of constants) has a desired value. Also, optimization is much easier if everything is a constant. The compiler can then decide when to copy a object to a new memory location and when to keep the initial object and simply pass a pointer. The programmer never has to think about pointers, memory allocation, or out-of-bounds errors. In principle, the correctness of programs can be verified automatically (at least in some simpler languages).

However, there seems to be a hefty price to pay. The "constants" are not just numbers; they are sometimes quite complicated objects, e.g. functions that take a number of other functions and return objects containing other functions of the same kind. The programmer has to build an adequate and complete mental picture for a rather intricate computational environment, say, of OCAML. The computer is not anymore a simple collection of memory cells with numbers. OCAML (and most other functional languages) has many kinds of complicated objects not reducible to numbers; for example, polymorphic functors - functions that construct new functions out of old functions using complicated type-dependent rules. The programmer cannot simply say that "everything is an expression": the human brain does not work like that. To reason effectively about a program, the programmer will have to imagine each kind of OCAML object as a separate beast with different properties. The programmer will not be productive without knowing exactly how the language compiler will handle each particular (quite complicated) language construction (parameterized function types, partially parameterized function types, recursive functions, nonrecursive functions, lazy-evaluated functions, partially-matched function definitions, etc.).

For instance, I know that tail recursion is desirable even though it's sometimes more difficult to achieve (as in the float_sum example above) than non-tail recursion. My next thought is that I would like to compute the length of the list without traversing the list twice, because I know that it's not optimal and should be avoided (but only if the particular language implementation does not provide a O(1) function to get the length of the list!). I need to think about how to accomplish this new task, again with only tail-recursive calls. Well, OCAML supports also the imperative style - why not use it just for this? Maybe there is a reason to use the pure functional style; maybe the code will be parallelizable in that case; but I don't know that. The language does not tell me about that, but I need to know that to be productive.

How many other such tricks will I need, and how many other tricky situations do I have to learn about in order to produce efficient programs in OCAML? (I can just feel how I am losing interest for OCAML rather quickly...) In an imperative language such as Fortran or C++, the connection between the language and the machine is tight, and I know how to choose an efficient implementation of an algorithm, both in terms of memory and in terms of speed. In a functional language I can only guess which of the many possibilities is efficient. If the imperative-style function is as efficient as pure functional style, I will use the imperative style because it's easier. Maybe it would have been just as easy for me, had I studied Lisp at school instead of Pascal. But I doubt that learning about a very powerful and complex language such as Lisp is easier than learning about an easy language such as Pascal.

In fact, I learned about Lisp and Prolog at about the same time as I was going through PL/I and Pascal tortures at school. I was not impressed by any of these languages, functional or not. They all appeared equally artificial and mysterious because I didn't get an adequate mental model of their implementation. For me, a programmable calculator was fully understandable and hence useful; other programming languages were just for show. But maybe it's been different for other people.

So it seems that functional programming has largely failed to attract significant interest because it's hard. It's hard in the same way as abstract mathematics is hard, because functional programming emphasizes the same things as abstract mathematics: immutable, permanent functional relationships between objects, rather than the numerical data contained in the objects. Mathematics not only emphasizes deep logical connections between things, connections that are often counterintuitive and not at all apparent to superficial perception. Mathematics actually requires one to think only in terms of those abstract and counterintuitive connections. Mathematics requires you to develop a very specific mental capacity for abstract relationships and a specific, dynamically trainable intuition for those counterintuitive things. This is a formal kind of intuition that trusts a formalism more than it trusts a gut feeling, and such that the gut feeling is prepared to change when the formalism dictates so. Only very few people are mathematicians. Similarly, only very few people are comfortable with functional programming style and use it. (It seems that the people especially productive with a functional language are precisely the people who have implemented it and hence have a more or less complete mental picture of its inner workings.) Sure enough, those people are productive and get great results. But you can't have millions of college graduates with that kind of skills. Nobody knows how to teach those skills. MIT requires CoSci students to learn Scheme in its 6.001 course, but this does not seem to produce a massive number of students who are productive using functional languages.

That's why software companies list Java and C++ as requirements but not Lisp or OCAML. If there were some way of producing millions of abstract thinkers who can learn to be productive in a purely functional style with a minimum of imperative style, surely there would have been a job market for those people. Functional languages are perhaps more powerful than imperative-style languages, but functional languages are not better languages because functional languages are not suitable for ordinary people to learn and use.
 
 
( 33 comments — Leave a comment )
Serguey Zefirovthesz on July 4th, 2008 08:19 am (UTC)
The situation about functional programming languages looks like situation about high-level imperative languages of Brooks (of Mythical Man-Month fame) era.

Then high-level languages were competing with assemblers and, especially, macro-assemblers. Those assemblers were big and expressive, you, for example, could write a hello-world program using macros and it will be as short as C, or Fortran or PL/1 version. And developer effectiveness wasn't that different for assemblers and C. I assume the difference between 2 and 5 times of LOC for assemblers and HLPLs of that era.

But HLPL relieved programmers from register counting and allowed them to easily integrate different pieces of program complex. They exclude one (the most notable) row of building equations.

Today situation is like that. FP like Haskell exclude mutable state and we can combine different data transformers in very complex ways. And difference between Haskell and C++ LOCs is about 3-8 times in favor of Haskell.

In 70-s only very advanced types used HLPL. Today the very advanced use Haskell.

All in all, I suggest that FP is silver bullet (make developers effective ten times their previous bests) of today. Just as HLPL was silver bullet of 70-s.
chaourcechaource on July 5th, 2008 06:36 am (UTC)
This is an interesting comparison (macro assemblers vs. Algol). However, this is still a comparison between imperative-style languages. The best programmers are effective in any language, but their methodologies will not be adopted widely. I am still not sure that FP will ever become as popular as imperative languages.

I looked at your blog; it seems that you are a fan of Haskell. Which book would you recommend to read as a first book on Haskell for an amateur programmer like me?
Serguey Zefirovthesz on July 5th, 2008 09:37 am (UTC)
High-level languages took away some freedoms of assemblers.

FPLs take away freedom from HLLs.

That's my main point.

As for the book... I don't know. I didn't read them. I mostly read online papers. ;)
(Anonymous) on July 9th, 2008 07:46 pm (UTC)
Book recomendation
Hi chaource, I was a teaching assistant for a course on Haskell and we were using the book "Programming in Haskell" by Graham Hutton. It's price is OK and its very well written. I personally like it very much. So here you go :-) Check out the first pages at: http://books.google.ch/books?id=olp7lAtpRX0C&dq=graham+hutton+haskell

best regards,
Simon
(http://people.inf.ethz.ch/meiersi/)

PS: I quite like Haskell's way of doing your sum example: Just call the fully polymorphic standard library function 'sum' which works for every type that has the function (+) implemented, i.e., is a member of the Num type class. Then it's the libraries authors problem, to provide an efficient implementation -- which is actually pretty simple: sum xs = foldl' 0 (+) xs. But the important point is that the language gives the possibility to abstract to this level and thus provides tools to improve your everyday productivity, as more tasks can be done once and for all. :-)
(Anonymous) on July 9th, 2008 11:54 pm (UTC)
Book recommendation
I would thoroughly recommend Real World Haskell as an introduction to the language for someone who is already a programmer. It's not published yet (due out later this year), but you can already read drafts of most chapters at http://book.realworldhaskell.org/beta/index.html.

I like it because it gives a clear introduction and uses lots of useful and fun example projects to show how you can actually get stuff done in the language.
chaourcechaource on July 10th, 2008 01:42 pm (UTC)
Re: Book recommendation
Thanks for interesting recommendations!
pozorvlakpozorvlak on July 9th, 2008 11:27 pm (UTC)
Why am I not surprised to see you here? :-)

Anyway, you should probably read Brooks again, because one of his main points is that there is no silver bullet :-)
(Anonymous) on July 9th, 2008 09:59 pm (UTC)
Your argument is based on a flawed premise. Functional programmers aren't going to sit around writing tail recursive loops all day the way C programmers rewrite linked list manipulation. They write "average n list = sum list / n" and move on.

Secondly, I have to doubt your credentials severely if you find writing a tail recursive loop to sum numbers to be "difficult." Boring? Sure. Difficult? Hardly.

Your argument rests on poor reasoning: people know imperative languages therefore, they know imperative languages. Most people who come into university and emerge as productive programmers had arrived already knowing how to program, in my experience. Anyone who seriously did not understand computer programming prior to university is most likely going to be featured on The Daily WTF someday if they go onto a programming career. And of course if they arrive with imperative programming experience then they are most likely going to biased towards it throughout. And how do they arrive with imperative programming experience? Through being exposed to it by popularity. So, extrapolating, what you are arguing is that "imperative programming is popular therefore it is easy to learn."

It is difficult for me to understand why someone would argue that programmers are not "abstract thinkers." It is practically the whole point of working with computers. If you are dealing with people who are not "abstract thinkers" you have much worse problems than not being able to teach them functional programming skills.

Then there's the continual adoption of functional programming features into mainstream languages like Java, C#, Perl, and Python. This is evidence that perhaps education is having an effect, slowly.
(Anonymous) on July 9th, 2008 10:24 pm (UTC)
no fair comparison
In your C program, why did you write a 'for' loop? Why didn't you build it yourself using 'if' and 'goto'? Well, obviously because you'd go nuts if you did. But in O'Caml, you used the equivalent of 'goto' (general recursion) instead of the equivalent of 'for' (a higher order function, 'foldl' in Haskell, probably similar in O'Caml). Higher order functions are the control structures of functional programming.

Now suppose you traverse a list twice to get the sum of its contents and its length. You have two fors in C and two folds in Haskell. Of coure that's wasteful, you want to fuse them. You can always(!) do that in Haskell, but turning two loops right after each other into one in C can produce wrong results. Rules in pure functional programming always hold, while in imperative programming, all rules come with a host of side conditions that are hardly ever fulfilled.

Considering all that, here's the average, written as a single, tail recursive traversal, in a style I'd call more natural, even though you may disagree:

average = uncurry (/) . foldl (\(a,l) x -> (a+x, succ l)) (0,0)

(Anonymous) on July 10th, 2008 12:00 am (UTC)
Re: no fair comparison
Here's the same thing expanded slightly to make it (IMHO) a bit easier to read:

average xs = sumxs / lengthxs where
(sumxs, lengthxs) = foldl (\(a,l) x -> (a+x, l+1)) (0,0) xs
chaourcechaource on July 11th, 2008 09:36 am (UTC)
Re: no fair comparison
That "for" is an equivalent of "goto" is a good idea. I am not quite sure that all algorithms accomplished by "for" loops in C can be rewritten using "foldl" or other high-level functions from the standard library. Most probably the programmer will have to write their own high-level functions. This is a much more abstract task than the usual stuff done in Fortran. But there is more: Being productive with this kind of programming requires an understanding of the implementation of high-level functions in the particular compiler. Such implementation is probably based on some high-brow mathematics. I think that the extra levels of abstraction and complexity is what scares people away from functional programming.
wren gayle romanowinterkoninkje on July 13th, 2008 07:15 am (UTC)
Re: no fair comparison
Higher-order programming isn't that hard to think about. I'll grant that it can be hard to think about thinking about (i.e. to worry about the theory), but people do higher-order programming all the time in non-functional languages, and they actually have the harder task since they're doing it in languages which don't support doing so directly. Mark Dominus wrote just recently about the fact that Java developers do this every day and have been doing it for years.

Many of the classical "patterns" in OOP such as the strategy, visitor, iterator, and command patterns are the result of not having first-class and higher-order functions. Now I've said below that most folks don't get OOP either, but many of the classical patterns embody the heart of the paradigm. And Java, C++, Objective-C, and C# programmers around the world consider these patterns of algebra passing, abstract folds, mapping, and defunctionalization to be run of the mill.

Sure, functional languages give them funny names like morphism, functor, and monad but that's just because they're the sort of folks to tackle programming with the same intellectual rigor as they do mathematics and other formal disciplines. The ideas are fundamental and after enough coding non-functional programmers stumble onto the same things, they just give them cuddlier names. If you want to argue that functional languages are destined to fail because they assume their users are smart enough or interested enough to care about the theory, that's a whole different kettle of fish. They're not going to dumb it down for you, but you don't need to know why the theory works in order to use it.
chaourcechaource on July 13th, 2008 07:40 am (UTC)
Re: no fair comparison
So you are saying that the full power of OOP ("all that one can do in C++ with templates") is probably also too difficult for the average programming public. This seems to agree with my main statement. Sure enough, really good programmers (a rare fish to find) will use all these methods in any language.

I'm not sure that FP is "destined to fail." I'm just trying to understand the title of this thread.
wren gayle romanowinterkoninkje on July 13th, 2008 09:27 am (UTC)
Re: no fair comparison
Well, the full power of OOP is better than C++ with templates. Monkey patching, Object>>become, and other true OO tricks are much nicer than trying to hack that functionality together in C++. Also, implementation-based types are antithetical to the OO paradigm, which means C++'s whole class/inheritance mechanism is fundamentally broken for modeling OOP.

All that aside, the full functionality of C++ is far beyond the ken of the average professional programmer, let alone the average public. There are folks out there who know it, but they need to know every detail of how the compiler works in order to do so. Of course knowing the details of how a particular compiler transformation is applied using hardware-specific knowledge in one language does not port well to other languages. On the other hand, a firm understanding of type theory, recursion, data structures, and algorithms will serve well in any language of any paradigm.

As for the title of the thread, I believe Anonymous was pointing out that your sample code for making a comparison between OCaml and C was intentionally convoluted to paint OCaml in a harsh light because the programs are not comparable in terms of idiomatic construction. (E.g. if you're using primitive recursion instead of folds, why not use if/goto instead of for-loops or pointer arithmetic instead of array indexing?)
wren gayle romanowinterkoninkje on July 13th, 2008 07:41 am (UTC)
Re: no fair comparison
I am not quite sure that all algorithms accomplished by "for" loops in C can be rewritten using "foldl"

foldl isn't the primitive, foldr is. foldl can't handle all for-loops because it's strict in the length of the list (ruling out infinite loops), but foldr can handle it just fine (in conjunction with the list constructors (:) and [] (or build, or unfoldr,...)). For any data type, provided you can build and destroy it you can perform every operation on it. (Lazy) lists embody sequentiality (among other things), which combines with the previous sentence to explain why they're as ubiquitous in functional languages as for-loops are in procedural ones.

init; for (pre; cond; post) block => init; pre; while (cond) {block; post} => foldr block init (iterate post pre)
wren gayle romanowinterkoninkje on July 10th, 2008 08:53 am (UTC)
In regards to the myth that imperative programming is somehow easier, I'm always reminded of a story my (now retired) discrete mathematics professor told me.

Just before retiring, all the incoming freshmen were taught C++ in their introductory courses. It was hard because computer programming is hard, but they basically figured it out by sophomore year. In their sophomore and junior years they made it to his classes and had to learn Prolog and Maple. And every year he would have students flocking to his office, tearing their hair out, complaining that these languages made no sense, and wondering how anyone could possibly think this way. At the old college he taught at way back before "computer science" existed, he started off teaching Lisp to the freshman computational mathematicians. It was hard because computer programming is hard, but they basically figured it out by sophomore year. In the operating systems course they were introduced to this brand new language: C. And every year he would have students flocking to his office, tearing their hair out, complaining that this language made no sense, and wondering how anyone could possibly think this way.

People think imperative programming is easier than functional programming simply because they're more familiar with it and they've been taught to think that way from the beginning. Reorganizing how to think and solve problems is exceptionally hard the first few times you try, but it gets easier the more you do it. And this has absolutely nothing to do with functional languages.

If you raise someone on C, C++, or Java and then you try to get them to switch their thinking to object-oriented programming they will fail miserably. No, those aren't OO languages, those are struct languages. I'm talking about real OO languages: fully dynamic, interface typed, actor model, message passing OO. Languages like SmallTalk, Ruby, Python, Perl. The entire methodology of how one frames a problem is entirely different between these sets of languages. If functional languages are hard because mathematics is hard, then OO languages should be easy because objects in the real world are easy. And yet time and again students fail to grasp even the basic tenets of the paradigm.
wren gayle romanowinterkoninkje on July 10th, 2008 08:53 am (UTC)
(part 2)

If you raise someone on that trifecta and then try to switch them over to logic programming their brains will break when you try to explain how unification is different than equality, or when you try to explain what a "variable" is. If you try to switch them to constraint programming their brains will break when you tell them to solve a system of equations simultaneously for all their values. These two paradigms might seem the same as functional programming because they're also mathematically based, and yet they're quite different indeed. They'll be easier to explain to a functional programmer because the ideas of immutable data, pattern matching, and recursion patterns over algebraic data types are already familiar, but extending the concept of pattern matching to unification and extending from deterministic solutions for equations to nondeterministic control flow will both take a little while to get used to.

If you raise someone speaking only English from birth and then you move them off to Greece, or Sudan, or Pakistan, or Japan, it'll take them a goodly while before they'll understand what's said around them. It's not that Greek, Arabic, Urdu (Persian, Punjabi,...), or Japanese are hard and unnatural ways to think and speak. Anyone raised speaking only those languages find it perfectly natural, and being brought to America (Australia, Britain,...) they'll find English unfathomable for quite some time. The process of learning a new language, natural or artificial, is about learning new ways to structure your thoughts.

If you've never stepped outside a monoculture, even the idea that there are different ways to think will come as a shock (cf. struct vs OO), but it'll be just as shocking as the monoculture evolves to incorporate more and more of the features from other languages and other programming cultures. Contrary to what you claim, functional languages are making their way into industry as I'm sure Yahoo, Galois, Google, and Microsoft will agree. Imperative languages have more jobs because it's cheaper to employ plug compatible interchangeable engineers and colleges churn them out since industry wants the cheap labor; that doesn't mean they're decent programmers or decent jobs. If you want to get ahead today, it doesn't matter what languages you like, you better be able to think functionally even when using a dysfunctional language.
chaourcechaource on July 11th, 2008 09:31 am (UTC)
Re: (part 2)
Your examples are interesting, but I am not quite convinced that functional languages are "just different". I would, however, disregard the opinions of American freshmen or sophomores as to the value of what they study.

In your example, students first exposed to Lisp were struggling with C, and students first exposed to C++ were struggling with Prolog. It would be convincing if the software industry also had such waves of popularity of functional vs. imperative vs. logic programming languages. The industry does not follow the developments in the academic computer science community. If programming paradigms were all equal, one would expect that the industry will want a functional/logic/etc. language whenever it's fashionable in the academic world. But this is not what we see. It seems that students might be learning Lisp, Smalltalk, Prolog, or whatever in college, but the "real world" wants something entirely unrelated.

It was exactly my point that imperative programming helps churn out cheap "plug-compatible" engineers, while functional or other more abstract programming is expensive in terms of labor force. You can't train a large number of programmers who are productive in anything but a very dumb language. The situation with mathematics is similar. You can train a large number of people to operate calculators or to solve a fixed set of problems with Mathcad or whatever; but you can't train a large number of people to be productive about proving theorems in functional analysis.
wren gayle romanowinterkoninkje on July 13th, 2008 08:12 am (UTC)
Re: (part 2)
The industry does not follow the developments in the academic computer science community.

You have obviously never worked in the industry. They take a very great interest in academia and in what the academic community is teaching their future employees. Do you think the students fund the departments? Industry doesn't dote on the coattails of academia, but they certainly do take interest. Given the power dynamics as they stand today, it is academia which is following on after industry's lead. And yet for some reason these paradigms still live and thrive.

Prolog is used by industries to solve (NP-)hard constraint problems. Why do you think there are so many proprietary implementations trying to optimize it? Putting Haskell on your resume ensures that Microsoft will respond. The last few years Python programmers have had an open market for decent jobs precisely because it was the language noone knew; if you knew it, that meant you were with-it enough to be proactive, and smart enough to learn something without someone teaching it to you.

If I were running a company I would be with those Python and Haskell folks. I'd much rather have a small group of very intelligent people who are capable of solving very hard problems, because those are the problems that people will pay to have solved. But then I know a little something about the effects of working in large teams.
(Anonymous) on July 13th, 2008 01:24 am (UTC)
Wow
Algebra is inherently "difficult" too, and most people don't use it every day. Does that mean we shouldn't learn/teach it?
If you want to solve "difficult" problems, you're going to need better abstractions (which almost always require more "up front" investment because they seem "difficult" when you learn them). Haskell takes longer to learn than C, but Haskell is easier to use than C once you starting writing difficult programs.

I don't see why you make your life so difficult with your FP example, why not just do something like (Haskell code, O'Caml will be similar): "avg list n = foldr (+) 0 list / n"? It's easy, the "foldr" means "fold the given operator into the list (right associative), with 0 as the base case". So it sticks a "+" in between each element of the list, with a 0 at the end. Once you know what a fold is you can write stuff like that without having to type out the details (contrast with your for loop where you manually have to babysit a loop variable etc.).

Looks like you're intentionally complicating things to stack the argument in your favour. Either that or doing it out of ignorance, which is fine (we can't know everything before we've learnt it) but it's not a good starting position to be in if you're going to talk about what's "inherent" about this or that technique.

I had a very hard time learning Haskell, as I was a die hard C programmer at the time. It was very painful and frustrating, and I'm sure I did condemn the language multiple times thorughout. But I stuck with it, and I'm a better programmer for it (in Haskell, and C).
It *feels* unnatural because you have a massive gap in your repertoire for solving problems. Algebra feels the same way before you understand it too. It's not algebra that's at fault, it's your own deficient skills (and I mean that not in an insulting way, but in a matter-of-factly way - we all lack skills before we learn about something). It's easy to blame the language for your own shortcomings, but it's far more satsifying in the long run to assume that any "friction" is largely going to be due to yourself, and rectifying the situation by learning whatever you're having problems with (even though you'll want to quit probably just a few days in). In fact, the "weirder" a language is, the more likely it is that you're actually going to become a better programmer for knowing it. Learning C# if you know Java won't make you better in any way, other than adding a bullet point to your CV. Learn FP, stick with it, don't quit. Eventually it'll "click" and you'll get it. When it does, I'm sure your imperative programs will be much nicer with fewer bugs etc. (there seems to be pretty much a 100% consensus about that from people like me, who were imperative programmers first and then learnt FP), and you'll have another tool in your arsenal (and believe me, FP is coming - multicore is the killer app)
chaourcechaource on July 13th, 2008 07:18 am (UTC)
Re: Wow
I believe your point is that massively multicore CPUs will introduce a demand for automatic parallelization which only FP can provide reliably. If so, FP will eventually make it, but I don't think it will dominate the mainstream programming languages. Your example with algebra is a good one. Indeed, we "should" teach and learn algebra. The question is, how many people can actually master algebra at a decent level of proficiency, so that e.g. learning the basic outline of lambda-calculus then takes a day of browsing some online tutorials. How many people really understand college-level algebra beyond memorizing the formulas? Judging from the mistakes students make, about 10% of science/math students can make it.

It's not easy for me to imagine what other people's reactions are to algebra, or to Haskell. It is easy for me to learn anything that's based on algebra because of my mathematics background, but it will probably be much more difficult for a non-mathematically inclined person.

For example, every Haskell tutorial mentions "monads" as Haskell's way to do I/O. I always took this as a sign that it's too much of an academic language to make an impact. Now, I happen to know the basics of category theory from my student days, but I still don't know what monads are. Nor do I wish to spend time learning it if I don't need to. Thanks to the posts above, I started to look at Haskell tutorials and concluded that the Haskell I/O can be thoroughly explained to beginners without mentioning monads or category theory (although those tutorials do mention them). I can't yet judge whether advanced Haskell programmers need to understand something at all about category theory. If so, I would say that Haskell is unsuitable for the general programming public.

It is also true, as you say, that it takes time until one's bag of tricks includes a relevant FP repertoire such as foldr. However, my point is not that programmers need to learn about foldr in Haskell the way they need to learn about printf in C. I think Haskell programmers need to learn much more about the implementation of Haskell in the particular compiler than C programmers. I've seen the statement that it's easy to write extremely inefficient FP code. This is probably because it's quite difficult to guess which FP code will be efficient, unlike the C code.

An example is the factorial function. Most tutorials give a straightforward Haskell implementation such as

fact 0 = 1
fact n = n * fact (n-1)

Suppose I wanted to program a fast-working function. Then I need to know whether the above is good, or whether I rewrite this in a purely tail-recursive version, or maybe I should use foldr if it's more efficient,

fact n = foldr (*) 1 [ 1 .. n]

Now, I happen to know that multiplying integers in order from 1 to n is a rather inefficient way to compute the factorial if n is of order 1000. A much better algorithm is to split the range 1 .. n into two ranges, say [1 .. p] and [p .. n], compute the products of these ranges, and multiply the results. The value of p must be chosen for efficiency as a certain function of n which I forget now (it's either n/2 or something much more complicated). More generally, given a list of integers, one can devise a similar strategy for efficient computation of the product. The question is how to implement that in a functional style without losing efficiency. Do I create a lazy stream of lists, or do I use tail recursion with lists as dummy arguments, or some clever library function that's implemented in the core for speed? I have no idea! The compiler will do some optimization, of course, but I expect to need a lot more experience with FP before I can produce space- and time-efficient Haskell programs.
wren gayle romanowinterkoninkje on July 13th, 2008 08:55 am (UTC)
Re: Wow
For example, every Haskell tutorial mentions "monads" as Haskell's way to do I/O.

The beautiful bit is you don't need to know anything about category theory in order to use them, it's just another language feature. You don't need to know why they work, you just need to learn the syntax and the rules for how to work with them. In that way they're no different than language features like classes and inheritance, or threads, or garbage collection. Most beginning programmers know nothing about why the rules of OOP work the way they do, about why certain types must be covariant or contravariant with inheritance, for instance. Heck, many experienced OO programmers don't know why they must be that way; that's why Java got it wrong with arrays, thus breaking numerous parts of the language. Most programmers know the rules of making the compiler accept their program but know nothing about type theory. Does that mean types are too hard? Safe use of casting and pointers is something even experienced C programmers have issues with. Does that mean C is too hard for hobbyists to learn?

With regards to your factorial example, an algorithm is an algorithm. You can always do the same algorithm in Haskell and achieve the same performance benefits over the naive implementation. Most programmers don't know algorithms either, they have libraries for that just like Haskell does. To program efficiently in Haskell you don't need to know anything about how the STG is implemented. The biggest thing you need to know is how to avoid space leaks and frivolous wasting of memory. The second thing to learn is to convert "almost" tail recursive functions into truly tail recursive ones.
chaourcechaource on July 13th, 2008 03:31 pm (UTC)
Re: Wow
Would you suggest a tutorial or a book that teaches how to avoid "space leaks"? (I assume these are not really leaks but programs that unnecessarily require huge amounts of heap memory.) Tail recursion is so far the only thing I know to keep in mind while doing functional programming; as I said in my post, I expect lots of other tricks there.

I agree that type theory is too hard. Somebody from the FP community said in an essay that most people (=cosci students) do not even get pointers. I also have an impression that C++ is just too hard to understand fully for an average programmer.
wren gayle romanowinterkoninkje on July 14th, 2008 06:03 am (UTC)
Re: Wow
Leaks typically mean unintentionally holding onto memory (hence not letting the GC do its job), though it also includes frivolous use of heap (the subject of deforestation papers). So it's not quite the same thing as a "leak" in C/C++, i.e. if you loose the pointers you can't free the memory.

I don't know of any good books off hand, but the GHC manual on profiling gives a good explanation of the tools to determine whether you have a leak and how to narrow down where it is. One trick in particular is that if you have a list that you need to recurse multiple times for some reason (e.g. taking averages), if you can reorganize your code to work in a single pass then that allows the list to be collected after you've processed each element, rather than holding onto the whole list at once. This is a particularly common bug when reading from files. For most file munging you don't need the whole thing in memory at once, so it's best not to try. This generalizes to any recursive data structures, natch.

Don Stewart has a number of good papers on deforestation, of which Rewriting Haskell Strings is an excellent introduction on the topic, as well as offering a very efficient way to deal with strings. GHC already implements common deforestation techniques for lists, so all you need to know is about which functions are "good producers" and "good consumers" (see the bottom of the page on rewrite RULES), though having some understanding of what the problem is and a vague notion of how the techniques work can be helpful for writing your code to take advantage of it.

There's been a lot of work done on optimizations, and in particular how to make them automatic, but it's mostly research papers. Since the Haskell community is very academically oriented (it is a research language that escaped the lab, afterall) most folks don't mind, even the non-academics/hobby-academics, but it can be off-putting for people who aren't used to looking in university publications for tips and tricks :) The Real World Haskell book doesn't have a lot on optimizations, but it is an excellent introduction to the language and to good coding techniques.
(Anonymous) on July 13th, 2008 12:00 pm (UTC)
Re: Wow
I don't think programming is a profession that everyone is "supposed" to do. It does require an above-average intelligence, I'll grant you that, but I don't see that as a problem.
I don't think you get my point. *Writing* a C program requires huge amounts of intelligence because the language encourages you to get it wrong, and makes it extremely difficult to find the bugs and to maintain the application. In contrast *writing* Haskell is easy, it's just takes a bit more intelligence to *learn* Haskell.
So you have a very hard limit to who can do programming either way. You need to be smart to do it, but for very different reasons. You don't need to be smart to learn C, but you need to be very smart to actually use it to produce anything of value because it's such a bad tool (unproductive, error prone, tedious etc.).
Would you rather "spend" your intelligence doing tedious error-prone book-keeping in a language that anyone can learn, or by learning better abstractions that lets you produce useful things faster, with fewer bugs and without the maintenance headaches? Personally I know what I'd go for.

Regarding performance; have you tried performance tuning C lately (I do this every day btw, as a game developer)?
Very few CPUs actually match C in semantics anymore. C is "low level" yes, but it's low level with respect to twenty year old CPUs, not w.r.t. to modern CPUs (which, incidentally, are essentially doing graph reduction internally, i.e. they're pretty much functional except they have an imperative ISA with a huge chunk of transistors essentially "decompiling" the assembly into a graph so they can get instruction level parallelism).

My point is that C doesn't really give you any good way of guessing what the performance of a piece of code will be anymore either. You only think it does, but when you profile you are surprised all the time.

In either language you'll have to try several strategies, look at the assembly output and profile it. Both languages are far removed from the hardware, Haskell is a few steps "above" it in abstraction, whereas C is a few steps "to the side" of it.

I'm not sure I understood your final point because I don't understand your algorithm (why is it faster to do N multiplications in two separate ranges rather than doing those same N multiplications in one go? Are you talking about concurrency here?). Why would this be more difficult in FP than in C? This just seems like a "high level" versus "low level" argument, and has nothing to do with functional programming. When you're writing code at a higher level, regardless of programming paradigm, then you may sometimes have to be careful not to introduce performance overheads. The tradeoff you make is that you only have to worry about this for the performance sensitive part of your code (profile!), the rest can be written in an "easy" way. Would I rather write a little bit of "low level" Haskell to gain speed in 5% of my code than write my entire application in C? Yes of course! That's a huge win!

Oh, and no you don't need to know about category theory to be an advanced Haskell programmer
chaourcechaource on July 13th, 2008 03:35 pm (UTC)
Re: Wow
That's good; Haskell then has a chance of being widely adopted.

As for the factorial algorithm. No, I wasn't talking about concurrency. When you multiply very large numbers x and y, you use algorithms that are not quadratic but more like linear in the number of digits in x and y. So it's a lot faster to multiply groups of smaller numbers first and then to multiply numbers of roughly equal size in pairs. The straightforward algorithm multiplies (at the last step) a big number, (n-1)!, with n, which is rather wasteful. It's much faster to compute (n/2-1)! , then separately (n/2)*...*n, get two very large numbers, and then multiply them. The gain is similar to that of the heapsort algorithm over bubblesort.
(Anonymous) on July 13th, 2008 04:09 pm (UTC)
Re: Wow
Ah right, I missed where you said that they were large enough to not fit into machine sized integers.

Anyway, I still don't see how this is in any way more difficult for FP.
chaourcechaource on July 13th, 2008 04:15 pm (UTC)
Re: Wow
Of course, in FP one has a choice of techniques to implement this kind of algorithm, or any other kind of recursive algorithm. My concern was that I (having started to look at Haskell quite recently) have no idea which technique is space/time efficient. But another post in this thread said that it's basically useless to try to guess this; instead one needs to implement several solutions and profile the results. This makes sense and basically answers my concerns.
(Anonymous) on July 13th, 2008 08:58 pm (UTC)
Re: Wow
As a general rule a "loop" in an imperative language is a tail recursive function in a functional language. So if you want fast performance, then that will almost always be the best bet. However, I don't think you should start worrying about that until you know for a fact that it's too slow to do it the easy way (i.e. "product [m..n]"). This isn't any different from any other language. You try it the nice "idiomatic" way first, and if it's too slow you can start writing something less nice to get it faster. This has nothing to do with FP vs imperative, it's just about high level languages vs low level languages. In high level languages you do sacrifice a certain amount of predictability in return for a much more productive programming environment. But like I said, these days even C is highly unpredictable.
chaourcechaource on July 13th, 2008 04:13 pm (UTC)
Re: Wow
A quick calculation shows that the optimal splitting is [1 .. p] and [ p+1 .. n] where p is determined by a somewhat complicated function of n. Namely p is such that squaring the number p! takes twice as long as squaring the number ( (p+1)*(p+2)*...*n ) .
chaourcechaource on January 7th, 2009 10:14 am (UTC)
Re: Wow
No, scratch that, it's wrong ... the optimal splitting point is something else.
(Anonymous) on January 6th, 2009 10:42 pm (UTC)
Think high-level
Here's how I'd write it in OCaml (with long variable names for clarity):

let average list =
  let sum_and_length (cur_sum, cur_len) element = (cur_sum +. element, cur_len +. 1.0) in
  let (sum, len) = List.fold_left sum_and_length (0.0, 0.0) list in
  sum /. len


You'll rarely need to write explicit recursion, and once you learn the higher order functions, you'll see how powerful they are. Working with higher level code is also much safer. For example, using fold_left there's no risk of an off-by-one error that could happen in C if you mess up with the for loop condition by accident, which would cause a runtime crash.
( 33 comments — Leave a comment )