Slashdot Mirror
Purely Functional Data Structures
In Okasaki's introduction he says that the "[...] benefits of functional languages are well known, but still the vast majority of programs are written in imperative languages such as C. This apparent contradiction is easily explained by the fact that functional languages have historically been slower than their more traditional cousins, but this gap is narrowing."
Indeed, OCaml has a reputation for being "as fast as C," yet it contains automatic memory management and supports object-oriented, as well as functional, programming. It's also probably the most widely used functional language outside academia (except perhaps Lisp/Scheme).
I mention OCaml not just because it's fast, free and popular, but because Okasaki uses a related language - ML - in his book. The ML family of languages are the standard strict, functional languages (Standard ML of New Jersey is perhaps the reference implementation but see also standardml.org). Okasaki also includes an appendix with examples in Haskell, which is the standard lazy functional language.
The difference between lazy and strict languages is the order in which code is evaluated. Most languages are strict. Unlike most languages, Haskell only evaluates something when it is absolutely necessary. Each parameter to a function, for example, is passed as a "thunk" of code, not a value. If the value is not required inside the function, the parameter is left unused; if it is required (say as part of a result that needs to be displayed) then the thunk is evaluated. This evaluation may trigger a whole slew of evaluations of functions that "should" have been called earlier (from a Java programmer's point of view).
Laziness is both good and bad. The bad side is obvious: the order in which code is executed my be very different from the order in which the program was written and some serious book-keeping is necessary in the compiler to juggle the thunks of code and their final values. The reordering of code could cause mayhem for IO operations, for example (in practice, of course, Haskell includes a solution to this problem).
The good side is that laziness can help make programs more efficient and, while the definition of ML doesn't include laziness, individual ML implementations -- including OCaml and SML/NJ -- include it as an extra.
Much of Purely Functional Data Structures (the second of three parts) focuses on how to use laziness to make data structures efficient. Lazy evaluation allows book-keeping actions to be postponed, for example, so that the cost of maintaining the data structure in an efficient form can be averaged across several read/write operations (improving worst case limits - avoiding a very slow response if the data happen to be in a "bad" order).
An understanding of how the efficiency of algorithms is rated (the big-O notation) is one piece of knowledge that this book does assume, along with a basic grasp of what Stacks, Queues, Trees, etc, are.
This lazy boost in efficiency is needed because, even though functional languages may be getting faster, it's not always possible for them to implement the efficient algorithms used in imperative (non-functional) programming.
But I'm getting ahead of myself, because I haven't described what a functional language is, or why it is useful. These are the topics of the first part of the book, which explains how functional languages, which make it impossible to change variable values by direct assignment, support persistent data structures. This section is fairly brief, and while it's a good refresher course for someone who's not had to worry about such things since studying at university, it's not sufficient as an initial introduction to functional programming in general.
There's a good explanation of functional programming in the Wikipedia, but, in all honesty, I don't see how anyone can really "get it" without writing functional code (just as I, at least, couldn't understand how OOP worked until I wrote code that used objects).
So forgive me for not telling you why functional programming is good (This paper is one famous attempt), but perhaps a better question to focus on is "Why should you spend the time to investigate this?" The best answer I can give is that it leads to a whole new way of thinking about programming. Describing functional programming as "excluding assignment to variables" doesn't do justice to the consequences of such a profound change (one I found almost unimaginable - how can you program without loop counters, for example?).
There's a practical side to all this too - learning new ways of thinking about programs makes you a better programmer. This ties in closely with the final part of Okasaki's book, which explores a few fairly esoteric approaches to data structures. Who would have thought that you can design data structures that parallel the way in which you represent numbers? Some of this is pretty heavy going - I can't say I understood it all, but I'm taking this book with me on holiday (it's slim - just over 200 pages) and I'll be bending my brain around some of the points in the last few chapters as I lie in the sun (here in the southern hemisphere it's late summer).
So just who would benefit from this book? It seems to me that it's most valuable as a second book on functional programming. There are a bunch of texts (and online guides) that can get you started in functional programming. This one goes further. It shows how to exploit the features of functional languages to solve real problems in applied computing. Admittedly, they are problems that have already been solved in imperative languages, but you might find that you, too, come to enjoy those famous benefits of functional languages. The algorithms in this book let you enjoy those benefits without paying the price of inefficiency.
Andrew Cooke last reviewed for Slashdot The Aardvark is Ready for War . You can purchase Purely Functional Data Structures from bn.com. Slashdot welcomes readers' book reviews -- to see your own review here, read the book review guidelines, then visit the submission page.
As opposed to what, Data Structures that don't work? Yeah, we need more books on those...
Management prefers dysfunctional programming.
blonde... brunette..
Nice to see some actual content on Slashdot!
By the way, this reminds me of the recent article on Domain Specific Languages over on Martin Foweler's website. Another aspect of programming worth investigating.
Who said Freedom was Fair?
Is 'OCaml' pronounced 'Oh-Camel', 'Ach-amel'...? Akin to the 'Line-Ux' versus 'Lin-Ux' confusion.
I recommend Thin Client's and Fat Fiber!
You know, your computer is not a typewriter, so you really could have rewritten that part of your review...
that supports GOTOs. Those are the best!
I guess what I'm saying is that I've used languages like Perl and Python considerably and ignored the functional aspects of the language, probably much to my disadvantage. I think a good study of a purely functional language could really improve my perl, python, or ruby.
I took a course back in university that used Scheme to teach some programming concepts. As with any course, we had to use Scheme to solve some problems on coding assignments. I remember a general rule everyone learned in the class: if your solution to the problem was more than a handful of lines, it was probably wrong. The solutions were very elegant, but very difficult to debug and very difficult to reason about.
I always save my last mod point to mod up a good troll. You people are too serious.
Are you serious?
I agree that functional programming languages are quite useful, but speaking as a coder who learned functional programming just last year in class, I can say that functional languages are a lot more complicated than procedural languages.
Sure, once you get good at it you can bang out a functional program easily, and maintenance can be a breeze once you know how to write the code. However, reading and understanding code that ISN'T yours can be damn near impossible sometimes, especially when you're a newbie.
I'm not discounting the use of functional languages, I'm just saying they are harder to learn than procedural languages.
Another way to think about functional programming is as constructor-based programming. Problems are solved by constructing lots of temporary objects that are a little closer to the solution, until you're finally in a position to construct the answer.
You can do this in any language, but to be efficient, you need an good garbage collector and a compiler that can optimize out most of the temporary objects.
But then again, I majored in math, not programming, so maybe I'm biased.
Nice review!
:)
:)
I just got this book and it's clear the author has really done his research. His writing style is also very clear, concise and well thought out. Not overly chatty or pandering, yet not dryly accademic either. Precisely the kind of computer book I'd want to write!
I'm glad the reviewer didn't try to talk a lot about why people should be interested in functional programs, however I must say that the ability to write large complex algorithms in very few lines, and prove mathematically that it works is simply a miracle in some situations. If you need to write a compiler (or do any other set of complex alogirthms on large recursive data structures, especially those that could take advantage of tagged unions, like Abstract Syntax Trees do) you should check out OCaml. And it doesn't hurt that it can figure out the type of all your functions and variables for you
Oh, and if you happen to get this book, and want to play with OCaml, you can get the OCaml translation of the data structures in this book here.
I dont' know if very many programmers will ever program in a purely functional language, however it seems that languages of the future will have to include things like first class functions and closures, as they are incredibly useful. I know Ruby and Python already support a lot of it.
Oh and in case anyone's wondering, it *IS* possible to encapsulate things like notion of state, error handling, and I/O in a purely functional language ("side effect free" language) using something called monads. Now there's a fun concept to wrap your brain around!
Hope some people here are brave enough to dig into a book like this that requires a bit of math, and more than a little faith at some points
Cheers,
Justin Wick
I bought this book about 6 months ago. I *love* it. The author did an excellent job showing many interesting algorithms. I did have to read it a few times to make sense of it, as I am not as engaged in the functional programming community as I would like. I still have trouble figuring out how to apply the banker's method and the physicist's method when determining the amortized performance of functional algorithms.
Anyway, the book was a great read. I was really surprised to learn how efficient some of the functional data structures could be.
Good discussion as well on the use of suspensions (lazy evaluation for specific blocks of code) in programming.
Engineering and the Ultimate
I agree that functional programming languages are quite useful, but speaking as a coder who learned functional programming just last year in class, I can say that functional languages are a lot more complicated than procedural languages.
I don't know how you can say that the languages are more complicated. Scheme, for example, is the simplest language I know of, in terms of syntax and semantics.
I think you're confusing this with how difficult it is to think functionaly when you've been raised to think imperatively. Functional programming is a different paradigm than imperative programming, and as such, you have to think differently. If you've been programming imperatively for a while, learning another imperative langauge is often straight forward; you learn the basics of the syntax, what the language provides natively, and how you can construct what it does not provide. You already know how to solve problems with that style of language.
Learning a functional language, however, is more than just having to learn a different syntax and set of rules (assuming you've been raised imperatively). You have to learn a different way of solving problems. And until you've done that for quite some time (I, for example, have not), I don't think you're qualified to make the judgement calls you did.
Also, since this was this guy's thesis, it's also available online
See http://www-2.cs.cmu.edu/~rwh/theses/okasaki.pdf.
I suggest you get the book, however, as it's a great read.
Engineering and the Ultimate
Heaps:
Trees:
Queues:
There's also a lot of other things, such as some interesting ways of doing numerical representation in functional languages (lazy numbers!) Even talks about trinary/quaternary numbers, as discussed before on slashdot.
Also if you'd like to see the source code without buying the book (you cheap bastard!) you can find it here.
But I hope you buy the book
Cheers,
Justin
If you only just learned it last year in class, no wonder you find it complicated. You probably have much more experience with imperative languages. Indeed, when you think about programming, your thoughts are probably imperative. Just as a native English speaker might think Japanese is complicated (even after "learning it in class last year"), a native imperative programmer will find functional programming difficult at first.
You know how they say, once you know one programming language, learning another is easy? Yes, once you know C++, picking up Java is a sinch, and you can probably even read someone's Python code without even learning the language first. But, this is because all of these languages are imperative. If someone tells you to write something in LISP, you may be able to figure out the syntax pretty easily, but no doubt you'll find yourself using imperative constructs like "progn". And, when you do that, the language seems very difficult to use indeed, because it was never supposed to be used that way. I made this mistake once myself.
Anyway, point is, it's not really fair for you to be judging functional languages until you've practiced them as much as the imperative ones. Personally, my imperative experience still dwarfs my functional experience by a factor of thousands... but I've now convinced myself that, for most purposes, functional languages are superior.
but speaking as a coder who learned functional programming just last year in class, I can say that functional languages are a lot more complicated than procedural languages.
Wouldn't you be a little bit more qualified to comment if you had several years of experience with both functional and imperative languages, first?
I can say that functional languages are a lot more complicated than procedural languages
What?? More complicated? No no no.. They are certainly not more complicated. For instance the funcitonal languages:
(display "Hello World") -Scheme
main =
do
putStr "Hello World" - Haskell
vs
#include
main () {
printf("hello world"); }- C
#!/usr/bin/perl
print "hello world"; - perl
Now those differences are subtle, but A. The functional languages are easier to read(and I think most any none biases person would aggree with me) B. No whacky syntax, hell scheme syntax is only () C. The data types are simple, Pointers? please. Ect ect. The thing that makes functional programming difficult is the lack of an imperative control flow. Which is how people tend to solve problems. For instance if you want to sum up the numbers 1 through 8, in an imperative language it'd be
tol = 0
for i = 1 to 8
tol += i
end for
in scheme it'd be
(define (sum a b)
(if (equal? a b)
b
(+ a (sum (+ 1 a) b)))
which is confusing. And not obvious. But as for other people's code, that is always the case. Well I've never seen a language that oculd get around that anyhow, the closest I think is java.
Network effects are what rules the programming tools industry. Network effects are whim to fashion. Fashion is ruled by those with the legitimacy to glamorize.
I love functional programming. If I had my way, my projects would all use functional programming languages. I don't have my way however, and there are two reasons.
1. Few commercial tools: Functional languages are under represented in the commercial space. With the exception of Franz Lisp and a few other lisp dialects, there is little commercial support. That may not be a killer for everyone, but I would like an environment with a good form designer and a large library to back me up. One I could give to another coder and expect them to be productive with it. Emacs works as an IDE for me, but I can't force that on others...
2. Fewer programmers: The vast majority of programmers seem unable/unwilling/whatever to grasp the concepts and work with functional code. If you need to build a team of programmers, it is much harder to find those who can do functional programming (and when you do, they rock, but are expensive and in high demand).
In the end, I use commonly used commercial tools so I can work with other people. Internally I use a lot of non commercial tools (LAMP model) and so I can sometimes indulge in my functional side there, but rarely can I do functional programming for my business clients.
Sig under construction since 1998.
The course was pretty mind-blowing. He knows his stuff. It was a bit freaky to watch him grading programming assignments by just reading them, not running them, and yet never missing a mistake.
I would recommend the book not just as an introduction to advanced data structures in functional languages, but as a guide to some of the more interesting data structures of the last fifteen years, regardless of implementation language.
-- Phil Gross
Programming in a functional language allows you to be more concise and expressive. Some studies indicate that development time is 4 times shorter, and the resulting code is 4 times smaller and is much easier to read.
Take a language like Ocaml.
It is a functional language with imperative features (loops, mutable data structures), modular organization, has object orientation, compiles to portable byte code (like Java and the JVM) as well as compiling to native code that runs as fast as C, has garbage collection, and a good standard library.
I'm thinking the reason why there are such few people picking up functional programming is the same reason the US still uses the imperial system for measurement.
While the rest of the world is on the metric system, the U.S. still uses the strange imperial system, that uses things like 12 inches to a foot, 3 feet to a yard, 16 ounces to a pound. That's because the US is entrenched in a mindset and there's no driving reason to change. This is the same reason why people have been stuck on imperative languages. Imperative languages have been the overriding paradigm because in the past, processing time and memory were expensive and imperative languages. This is no longer the case but there is a huge momentum of imperative language that that rolls on like a giant snowball, reinforced by industry and entrenched upon the next generation of computer programmers.
How did I discover Ocaml?
I was investigating rapid prototyping languages to add to my toolbelt and ran across Ocaml. I was drawn to it because it has done extremely well in the ICFP contests, especially in the lightning division (24 hour submission).
Also it ranks impressively in the great language shootout by Doug Bagley, in terms of Lines of Code, Execution Speed, and memory consumption.
http://www.bagley.org/~doug/shootout/