Thursday, February 09, 2006

What is wrong with people who write about functional programming?

A couple years ago, after hearing here and there about "functional programming", I decided to learn about it and got a book from the library. I found a book on OCaml and began to read. An hour or two I gave up, finding the book both dry and hard to understand.

Later I attended a course on "programming paradigms" where I learned basic Haskell. After studying Haskell for a little while, I came across the paper "Why Functional Programming Matters" (WFPM). Its objective was to convince the reader that functional programming is good, and it started off well enough, but utterly failed as soon as it started talking about how to write functional code. I found myself baffled when it introduced the line "sum = reduce add 0" on the fifth page. I examined the paper carefully for several minutes to figure out what it meant, and continued reading. Unfortunately, every new line of code was a new puzzle, and I soon gave up on it.

Now that I know Haskell and lambda calculus a little better, I have tried to learn about Haskell's type system by reading "A Gentle Introduction to Haskell" (GIH). It quickly struck me that this "introduction" wasn't "Gentle" at all! I can't see how anyone could understand it without already having a knowledge of lambda calculus and at least one functional programming language--preferably Haskell.

What strikes me about all these explanatory materials is that they are unaware of their own obtuseness. WFPM uses phrases like "It is now obvious that" and "can be derived just by parameterising the definition" (my emphasis). GIH's very name suggests easiness, and its introduction says it is "for someone who has experience with at least one other language, preferably a functional language". But excluding Haskell, I know at least 5 programming languages, none of which could prepare me for GIH at all.

So to be blunt, I wonder if there is something wrong with the brains of the people who write this stuff. How can they fail to see that their writing cannot be understood without a solid prior understanding of the subject matter, and that it suffers from excessive brevity? Functional programming does matter, and I do believe a gentle introduction to Haskell is possible, but I don't know if there are any writers out there who have explained these things properly.


At 11/21/2008 2:14 AM, Blogger Luke said...

It would appear that there is some "clicking", or epiphany (or multiple) required to "get" functional programming (FP). Sure, a few tidbits can be appreciated by understanding a little bit about FP, but what about the real fun stuff? Once you "get" FP, the syntax and basic ideas become so natural that they become almost unconscious and unexplainable.

What I think we really need is someone who knows nothing about FP but interested in learning it. That person needs to write down what it took to transition from an imperative programming mindset to a functional one. Unfortunately, most people seem disinclined to do anything while learning except grin and bear it. And thus, learning remains a pain for the next person who comes along. (Clearly, this would need to be done my multiple people and the result aggregated.)

With that said, what have you written about how you came to understand FP? I can't say that I've written much, but I also haven't come that far in understanding FP -- I get lazy evaluation, a bit about partial application, and can start appreciating the beauty of recursion, but I haven't gotten anywhere near monads, etc. Hopefully I'll write more when I actually get around to learning Lisp and Haskell.

At 11/21/2008 9:06 AM, Blogger Qwertie said...

I thought it was clear from the above that I didn't know enough about FP to write about it...

That said, I did learn some FP not long after, as I was forced to for a uni course. I didn't learn enough to be really comfortable, though; I especially didn't get monads but it was helpful to see monads in terms of C#:

But still I am not comfortable yet, and that article didn't really explain for me how monads would be useful in C# (though the advantage of passing around an "environment" makes sense in Haskell)

At 11/21/2008 7:29 PM, Blogger Luke said...

Ahah, but my point is that by the time you "know enough about FP to write about it", you will tend to write documentation not suitable to prior-you. If you wait too long to write about FP, you'll forget what it took to make you understand it. Does this make sense?

At 11/21/2008 10:39 PM, Blogger Qwertie said...

Yes, it does. But as long as I can remember what it was that I had difficulty learning, I can explain it to prior-me.

From this article it looks like, in 2006, I had trouble with the syntax. Today I look at "sum = reduce add 0" and see that

- it is defining a function called sum, but for a programmer of imperative languages this looks like a variable assignment statement. The paper therefore needs to explain the difference.

- sum returns reduce(add(0)) ... or is that (reduce(add))(0)? I'm pretty rusty. I can also tell that this somehow involves higher-order functions or at least partial evaluation (currying), and I recogize "reduce" as a standard and fairly fundamental function in FP.

I'm having trouble accessing that paper I referred to, but I bet the paper didn't explain the syntax (perhaps it didn't explain that the juxtaposition of two words represents a function call, and even if it did, it probably didn't tell the reader the precedence or associativity of the 'juxtaposition operator' -- e.g. does f x + 2 mean f(x+2) or f(x)+2? does x y z mean x(y(z)) or x(y)(z)?).

And it's obvious to me that currying and higher-order functions are a bit too advanced of a concept to introduce so soon in a "gentle introduction". Plus they use the function "reduce". The meaning and usefulness of reduce is clear to any functional programmer, but for a newbie it takes quite some time and several examples to digest.

I was able to access the first two pages of that paper and another thing I noticed was their aloof academia-style terminology. They use terminology that is almost as unfamiliar to programmers of, say, Java, as it would be to people who were totally new to programming.

I guess what I'm saying is, having learned some FP I can still detect the flaws in these tutorials, so hopefully I would be able to write a tutorial that overcomes their problems... if I were so inclined. But, er, I'm not so inclined.

I am comfortable in the imperative programming world I live in. FP in Haskell, etc. is too separate, I think. I'm not willing to totally leave the imperative world in order to program in the functional world. New languages like Nemerle and F# may help bridge this divide btw.

You know what I would really, really like to see in a FP tutorial? I'd like to see how the FP compiler executes the code. I'd like to know about persistent data structures and about the algorithms for making functions efficient that would be inefficient if coded in an imperative language.

For me, it's very important to understand how something works--not just its semantics, but practical low-level details. For example, this C# function is extremely slow for large n:

int fib(int n) {
return n < 2 ? n : (fib(n-1) + fib(n-2));

But the equivalent Haskell is much faster. How does Haskell optimize it? How does it determine that the optimization is necessary?

At 11/21/2008 11:56 PM, Blogger Luke said...

I completely agree that the syntax could definitely use some explaining. I also had some difficulty with that and gave up once the paper got to redtree.

You seem to indicate it's either/or with pure FP and imperative, but do note that one could have sections of an application that are pure FP without the rest being so. I guess you could have implied this with the F#/Nemerle point, but I just wanted to make sure.

Wanting an explanation of how FP compilers optimize without getting deep into FP is kind of iffy. I think the Haskell compilers have some of the most complicated code on earth -- after all, they're kind of like playgrounds for some of the smartest computer scientists around.

At 11/22/2008 12:20 PM, Blogger Qwertie said...

Well, some optimizations could be complex and hard to explain, just as they can be complex for imperative languages. But while optimizations in imperative languages are merely nice to have, optimizations in FP are absolutely essential--they could make the difference between O(2^n) and O(n) time, as in the fibonacci example.

It bothers me that I can't predict the runtime of a functional program, and, well, I happen to be interested in making a compiler so it would be nice to think about incorporating these kinds of algorithms into it. I googled around once for info but didn't find anything.

At 11/23/2008 1:13 AM, Blogger Luke said...

In looking for some FP compiler stuff myself, I found this blog entry, showing how one can move a simple task from imperative to functional style, and then reap parallelization benefits very easily.

On the FP compiler front, I found a fairly simple blog post on Haskell's rewrite rules which allow the compiler to modify your code so fewer intermediate objects are created. There's tail recursion to help with the fundamental, recursive nature of FP. Here's a paper on optimizing lazy functional languages. The stuff is out there, you just have to work a bit to find it. :-p

FP definitely isn't for the feint of heart [yet]. Sometimes, I wonder how many more people would do anything with it if learning the basics were easier. A good example of this is SQL -- the basic syntax sure is simple, but I rarely see anyone doing anything very complicated with it. There's a lot one can do with SQL, especially with windowing functions such as MSSQL2005's row_number(). Unfortunately, most people just don't seem to care about this stuff...

At 11/28/2008 4:13 PM, Blogger Qwertie said...

I just found this terrific and evidently free online book, Real World Haskell.

If the first chapter is any indication, this book will be a terrific way to learn Haskell. People can comment on every paragraph, which, I suspect, has whipped this book into really good shape.


Post a Comment

<< Home