Platforms, Evolution, and Software's Cambrian Explosion

Last week, the New York Times reported on the release of Google Apps. The offering sounds pretty compelling:

[Rebecca Wettemann, vice president of Nucleus Research] noted that a business may spend about $80,000 on a systems administrator to manage e-mail and desktop office software. For the same amount of money, Google Apps allows a business to support 1,600 users, she noted. Simply in terms of staffing, “this may be a better proposition even if Microsoft were free,” Ms. Wettemann said.

As usual, your mileage may vary:

[Dave Girouard, Google’s vice president and general manager for enterprise] said Google’s products were not replacements for Excel or Word, which he admits are more powerful. But he added that for smaller businesses and for certain groups of employees within larger companies, Google Apps could be a substitute for Microsoft’s products.

That is to say, very large companies, organizations that care deeply about information flow, or teams that advanced features will continue to see value in more traditional offerings from vendors like Microsoft.

Of course, this news isn't particularly earth shattering. Tim O'Reilly, for one, has been talking about Software as a Service for many years. You can view this announcement Google Apps as part of an ongoing ballet between Microsoft and Google, Microsoft and the rest of the industry, or Google and the rest of the industry. Or you could view it further validation of the concept of software as a service, or of the web as a platform.


I look at it differently.

Computing is a young field, and still in the midst of its Cambrian Explosion. New platforms emerge periodically. Some platforms become wildly successful, while others fade away with nary an artifact of their existence. The web is certainly the most successful platform in recent memory.

A great platform, like the web, reinvents the industry: it throws out old assumptions, brings new tools and new practices to bear on software development, and makes the impossible not only possible, but ubiquitous. Most importantly, a new platform gives us a clean page to start thinking about how to build systems. Given a great new platform, greenfield projects become the rule, not the exception; the only way to truly adopt a new platform is to throw out the old applications and start anew.


Yes, greenfield projects that require scrapping the old and starting from scratch are a good thing. But there are a few caveats.

As Joel Spolsky points out, rewriting an entire project simply because it's ugly or poorly engineered is never a good idea. This is just the siren song of second system syndrome, and it should always be avoided. Joel points out that the Netscape engineers were wrong to embark on a grand rewrite project in 1998, and lists similar projects that attempted to rewrite existing code, all of which failed. (Had Mozilla been a commercial software project, it would have failed just as surely as Quattro Pro and Copland did. Mozilla succeeded in the long run simply because it wasn't a commercial project, and it had the luxury to take years to complete.)

These lessons simply do not apply in the context of Google Apps. Starting a desktop office suite may have been a good idea in the early 1990s, before Microsoft Office established its monopoly and dominated the category. Today, starting a desktop office suite from scratch is either foolish, insane or both (except when the laws of physics and economics are suspended, as in open source projects that take years to complete).

Why is Google's office suite special? Not because it's Google. The rules didn't apply because Google Apps isn't a "desktop office suite." Writing a office suite for the desktop is still a bad idea, for the same reasons it was a bad idea ten years ago. But Google didn't do that. They solved an existing problem on a new platform (and bought some key components to hasten the process).

This is precisely what PC software vendors did 25 years ago, with packages like 1-2-3, dBase, and WordPerfect -- provide new solutions to old problems on a new platform. This is why Google is clever, not stupid.

By solving an existing problem on a new platform, Google Apps sidesteps the need to maintain or mimic all of the bug fixes that took years to identify with Microsoft Office. This renders many of Joel's objections to software rewrites moot, and makes it not only feasible, but desirable to rewrite applications from scratch. The same is true for the thousands of apps that were rewritten in Java, Perl, Python, and other languages to move to the web, and move away from the bugs, constraints, and limitations of earlier platforms -- desktops, mainframes and dialup terminals.

Not only are these rewrites a good idea, but a rewrite on a new platform in a new language is an excellent idea, especially when those new languages offer a higher level of productivity.


Claiming the "new platform exemption" doesn't make a rewrite project instantly magical and wise. Plenty of platforms come and go without changing the computing landscape. If you lived through the 1990s tech bubble, you may remember Microsoft Bob, Windows for Pen Computing, Pointcast, Marimba, BeOS, OS/2, Newton, MagicCap, OpenDoc and Pink. None of these efforts produced a viable platform. In hindsight, efforts to rewrite applications for these platforms turned out to be a complete waste of time.

Rewriting a program from scratch to target a powerful new platform does make sense. This was true in the 1980s with the PC, the 1990s with the web, and today with the AJAXified, RESTful web. Looking at the software industry in this way, it's certain that new platforms will emerge in the future. Most of them will fail, but a couple may be so powerful that they change all the rules.


How do you prepare for the next great platform? Really powerful new platforms tend to come along with new languages, so being nimble and learning how to learn new languages helps. Sticking with a single language and platform is generally a losing plan for a lengthy career. The software industry is dynamic, and needs practitioners that are able to adapt quickly. Failure to adapt to changing market demands is a recipe for deep specialization, obsolescence, or entry into management.

Learning new programming languages isn't sufficient; NewtonScript may have been interesting for a while, but it was a total dead end. Many lackluster platforms were built around C++, and none caught the imagination like web stacks for Java, Ruby or Python. Pascal, xBase and BASIC were strong contenders in the early PC era, but now those skills are nearly to worthless. Environments like Smalltalk and Common Lisp remain some of the most powerful ever created, but they have yet to lead to a widely adopted platform; this may or may not be an important concern.

How should you choose which languages to learn? One way is to follow the trends, and see where the industry is moving. In the 1990s, objects were big and getting bigger, so C++ was a good place to start, at least until Java came out and simplified that model. Smalltalk was a better choice, since all of the key concepts to object oriented programming start there. With a background in these fundamentals, picking up new languages like Python, Objective C, C#, and Ruby much easier.

Today, there's a move to simplify object oriented systems. Closures are a hot topic, which means looking into functional languages like Haskell, *ML and Lisp/Scheme. Prototype-based languages are becoming popular, which means looking deeply into JavaScript, but also Io and Lua, or going back to the source and studying Self. However, if you understand class-based languages, prototype-based object oriented programming isn't a huge jump. Better to focus on a functional language instead.

Although I have a lot of respect for the ML and Lisp language families, my money is on Haskell (surprise, surprise). First, Haskell is directly influencing C# 3.0 and the other .Net languages, via new technologies like LINQ. Microsoft's C# team isn't alone here; features from Haskell are slowly percolating into Java and Perl as well.

Additionally, Haskell takes a strong stance on functional programming, by forcing programs to be pure and side-effect free. This approach can be quite severe, but it does have some key advantages. The lack of side effects leads to a shared-nothing programming model, which eliminates entire classes of bugs for multithreaded programs. And with massively multi-core/multi-CPU systems in the near future, a better threading model is going to be a key feature of the next great platform. Transactional support for threads via STM can't hurt, either.


While I'd like to say that Haskell has all the indications of becoming the next great platform, I don't believe it is. However, the next great platform is likely to be strongly influenced by languages like Haskell. Since we don't know what that platform will be, it's best to go to the source and get a sneak preview of what we should expect to see soon. That platform, when it arrives, will be another game-changer, making the apps we develop today obsolete, just as Google Apps is making desktop office suites obsolete today.

FFI in Haskell

I mentioned yesterday that one of the implementation characteristics of the next big language should be a simple foreign function interface.

Here's an example from a recent project. I needed to create UUIDs. Looking around, I found RFC 4122, which describes UUID generation, and helpfully provides a sample implementation in C. Unfortunately, that code generates random UUIDs that aren't very random (32 bits of randomness in a 128 bit value).

Now, I could reimplement this code (or something similar) in Haskell, and fix the lack-of-randomness issue. Or I could find another UUID generator, and reimplement that directly. But really, my goal here is to grab random 128-bit UUID values and move on. Getting distracted by a research project isn't part of the plan.

A little googling found that a version of uuid_generate(3) is bundled within e2fsprogs. My target system has e2fsprogs installed, so that's a plus. And, interestingly enough, 'man uuid_generate' on my MacBook turns up this manpage:

UUID_GENERATE(3)                                              UUID_GENERATE(3)

NAME
       uuid_generate,  uuid_generate_random, uuid_generate_time - create a new
       unique UUID value

SYNOPSIS
       #include <uuid/uuid.h>

       void uuid_generate(uuid_t out);
       void uuid_generate_random(uuid_t out);
       void uuid_generate_time(uuid_t out);

....

AUTHOR
       Theodore Y. Ts'o

AVAILABILITY
       http://e2fsprogs.sourceforge.net/

(Turns out that Apple includes this as part of the standard C library. Thanks, Apple!)

A little more lurking, and I see that a uuid_t is merely an array of 16 characters. As the man page says, this is an output parameter. (It's odd to see code like this after programming in high level languages for so long, but this is C, and what are you going to do?)

Next, I started paging through the GHC User's Guide and the Standard Libraries documentation, and came up with this declaration:

foreign import ccall unsafe "uuid_generate" uuid_generate
   :: Ptr Word8 -> IO ()

This declaration is a direct translation out of the man page.

Next, I needed to construct a 16-byte buffer to receive the UUID value from uuid_generate, which requires using some functions in the Foreign library. As soon as uuid_generate finishes, the buffer needs to be translated into a Haskell string. Note that the return value is a 128-bit integer, and I want to convert that into sequence of printable hex digits. Here's the more convenient interface into the UUID generator:

import Foreign
import Numeric   (showHex)

uuid :: IO String
uuid = allocaBytes 16 $ \p -> do
          uuid_generate p
          uuid <- peekArray 16 p
          return $ concat $ map toHex uuid

toHex :: Word8 -> String
toHex w = case showHex w "" of
            w1:w2:[] -> w1:w2:[]
            w2:[]    -> '0':w2:[]
            _        -> error "showHex returned []"

Thats it! Easy Peasy.

Programmer Productivity is Accelerating

In a recent post, Tomasz Węgrzanowski points out Yannis's Law, which states:

Programmer Productivity Doubles Every 6 Years

Yanis's law is phrased to be provocative; the "law" is extrapolated from a single datapoint. Two if you count Tomasz's observation.

Assuming that there is a grain of truth here, I see a few factors that could drive this trend:

• Programming the same old thing over and over again gets boring
• Tools get better
• Libraries get better
• New techniques emerge
• Better platforms emerge

Every so often, I think about a system I was working on in the early 1990s that did a lot of brute force string processing in a mixture of Fortran 66/Fortran 77. String processing in Fortran is an extremely mind-numbing activity, and leads to low programmer productivity, frequent bugs, and regular coffee breaks to clear the head and revisit pages and pages of code with fresh eyes.

By the early 1990s, if you wanted to do massive amounts of brute force string processing, C was the way to go, because it was so much better than everything that came before it. By the late 1990s, if you wanted to do massive amounts of brute force string processing, Perl, Python or Java were the tools of choice, because they were so much better than everything that came before. Every year, computers get faster, and the systems we want to build get bigger. Micromanaging the computer the same way we did 6, 12 or 18 years ago simply isn't an effective way to write software. Which is why we feel the need to write better languages and better tools that get computers to do more of our drudge work.

Tools do get better over time. The compilers, languages, debuggers, SCM tools, bug trackers, and other tools developers use to make systems are always getting better. Simply using revision control is a huge productivity boost over projects that deal with frequent changes without revision control....

XML is simultaneously the most beloved and most reviled artifact of software development of the late 1990s. On the one hand, it raised a great many issues: parsing is a key component of all but the most trivial systems, parsing text is much easier than parsing opaque binary formats, and using a standardized grammar and parsing library is better than faking it with regexes, or worse, writing (and testing, and debugging) a grammar for every format to be parsed. On the other hand, XML is frequently abused, misused and shoved into places it doesn't belong. Nevertheless, adoption of XML is a net benefit, because it eliminates the need to write code for an entire class of problems.

Finally, the biggest productivity improvement in recent memory is the move away from cumbersome desktop programming environments towards web based applications. That topic has been beaten to death for years.


There may not be a whole lot of objective data backing up Yanis's law, but programmer productivity does feel like it's been growing faster than linearly for the last few decades. Maybe the factors aren't 2x every 6 years. Maybe it's 2x every 5 years, or 3x every 10 years.

In any case, programmer productivity is accelerating, and the expectation is that it will continue to accelerate, somehow. What are you going to do to accelerate your productivity over the next 5-10 years?

Design Patterns Aren't, Revisited

If you liked Mark Jason Dominus' take on Design Patterns, you'll probably get a kick out of Tony Morris' take on refactoring:

Ask your average Java (or C#) programmer to ‘write a method that takes a list of integers, adds 10 to each element, converts the result to a String, prepends *** to it and returns the resulting list’.

Tony takes this trivial problem and modifies it a few times to show how a simple and obvious implementation in Java (or the moral equivalent) slowly gets refactored into something so complex, it's hard to see the problem.

The punchline? The solution is dead trivial with higher order functions:

addTenAndConvert = map (("***" ++) . show . (+10))

Note that both the problem and solution here are contrived to highlight Haskell at its best. But the deeper point remains -- refactorings are patterns, and patterns (as commonly used) exist to describe recurring problems due to a language's design. As Mark points out (just like Peter Norvig pointed out before him), problems that merit a "pattern" in one language may not be problems in another language, or may be so trivial as not to merit a name in another language.

Although Mark and Peter Norvig were talking about design patterns, the critique certainly applies to many refactorings, which are really just (re-)implementation patterns.

Haskell: Raising the bar

Last week, Steve Yegge wrote up his thoughts on the key features a language needs to provide today in order to be "great". It's a grab-bag of holy grails, and reads like a new interpretation of Paul Graham's hundred year language.

Paul's essay, now almost 4 years old, is a long-term vision of how Lisp is the ultimate language, or at least how the ultimate language will appear lispy to a Lisp hacker. Steve's essay focuses on the near-term practical issues, like a C-like syntax as a pre-requisite for widespread adoption, minimum performance requirements, and platform agnosticism. Steve also lists a grab bag of language features that any new language needs to provide today to "not suck":

1. Object-literal syntax for arrays and hashes
2. Array slicing and other intelligent collection operators
3. Perl 5 compatible regular expression literals
4. Destructuring bind (e.g. x, y = returnTwoValues())
5. Function literals and first-class, non-broken closures
6. Standard OOP with classes, instances, interfaces, polymorphism, etc.
7. Visibility quantifiers (public/private/protected)
8. Iterators and generators
9. List comprehensions
10. Namespaces and packages
11. Cross-platform GUI
12. Operator overloading
13. Keyword and rest parameters
14. First-class parser and AST support
15. Static typing and duck typing
16. Type expressions and statically checkable semantics
17. Solid string and collection libraries
18. Strings and streams act like collections

Steve's post led to a lot of speculation that $YOUR_FAVORITE_LANGUAGE is actually poised to be the next big language. I'm not going to comment on that here, except to say that Haskell doesn't meet some of Steve's criteria. Haskell isn't especially object-oriented, and the programming community at large is still quite comfortable with objects, uneasy with functional programming, and downright hostile to monads and typeclasses.

Although Haskell may not be Steve's "next big language", it is certainly close to Paul's "hundred year language", or at least on a path leading to the hundred year language. In other words, Haskell may not be important to the mainstream today, or even within the next five years, but it will certainly prove to be important to the industry as a whole.


Steve's focus is primarily on language issues. Paul talks a little about both language and implementation issues. Here is a list of implementation characteristics necessary for a new language to "not suck":

An Open Source Implementation: "Open Source" as a concept label is 10 years old this year, and the advantages of open source (given an active, functioning community) are pretty obvious. The pressure to go open is now hitting Java, and helping JavaScript settle down and grow. The economics aren't in favor of a new, closed language becoming big. Closed languages like K will continue to pop up from time to time, but they will always serve niche markets and never become "big".

A Foreign Function Interface: One of the main advantages of being open source is the ability to reuse code. However, a huge body of code already exists, and isn't written (and won't be rewritten) in a "next big language". Integrating with low level libraries like database drivers, crypto toolkits, XML parsers and graphics processing toolkits are best done using interfaces to native code. Writing glue code that mediates between a language runtime and native code really isn't a productive use of time; it's better to just write declarations in the target language, and let the runtime (or compiler) figure out the rest.

A Big Library: One of the reasons why Java gained widespread popularity in the late 1990s is because development was moving to the web, and Java provided network libraries (including HTTP) in the core environment. Today, a popular language needs libraries that provide HTTP and related protocols, XML and HTML parsing, scripted web client libraries (like WWW::Mechanize), popular database drivers, and a database-agnostic modelling library (like Perl's DBI or HDBC). If these libraries aren't available by default, they should be easily installed through a package management system.

A Package Management System: It's cliché to talk about how Perl's greatest strength is CPAN. But CPAN isn't just a well-structured repository of modules, it's also a utility to install modules from the repository. Thankfully, many language communities have learned the lesson that you need both: Ruby has rubygems and gem, and Haskell has Cabal and cabal-get. The next big language will need to follow the trend and provide both a common repository of libraries, and a means to install them easily.

A Compiler: Steve mentions that the next big language should probably work on both the JVM and .Net, which implies at least two bytecode compilers. But if you haven't chosen a VM for your project yet, you probably want to keep avoiding them. Compiling down to native code (perhaps via C, perhaps using an abstract model like the G-Machine) will certainly help those who don't want to download (and maintain) a big VM just to run your program.

An Interpreter: Paul points out that having an interpreter gives developers flexability, at least during development. Perl, Python and Ruby programmers all know that deployment with an interpreter isn't so bad these days, either. Not having an interpreter makes programming in C (and C++, and Java, and C#) a real PITA. Firing up an interpreter to play with a library or a module really helps answer questions (and isolate bugs) quickly.

A Source-level Debugger: Sometimes, the easiest way to see what a chunk of code does is to step through it line by line. Tools like perl -d and gdb can remove all doubt by showing you what happens inside a running program, without modifying it by adding print statements everywhere.

In practice, you probably don't need both an interpreter and a source level debugger. One or the other should suffice. (Perl doesn't have an "interpreter" per se, but the debugger is often invoked as an interpreter: perl -de0 does the trick.) Having both will help a language become the "next big language," especially when many programmers are coming from environments that have debuggers, but no interpreters.

A Profiler: As Paul points out, it's best to get a program right, then make it fast. Ideally, a program could be written using simple but inefficient data structures. If that's fast enough, then fine. If not, then perhaps a few type declarations could be added to swap out inefficient data structures for more efficient ones. If that doesn't work, then a few hot spots could be optimized by rewriting code. However, this rewriting should be driven by performance data, not dubious dictums like "avoid bignums", or other such nonsense.

A Good Concurrency Model: Steve's list of features are things a language must provide to not suck. Erlang-style concurrency isn't on the list of necessary features, but is on his short list of features needed to make the next big language "great". Paul thinks the ultimate language needs to have a concurrency model deeply ingrained into it, but something that you ask for specifically as an optimization. Paul is right on this one; multi-core CPUs are here and getting denser. Any software we write today will probably be running in some kind of multi-core/multi-cpu architecture. If there's room for a new mainstream programming language today, it needs to get concurrency right, or at least better than raw threads. If not, we'll have to wait for the "next next big language" to fix it.

Open Classes: Language designers may be fantastically brilliant individuals, but they generally aren't clairvoyant. A language designer may create a perfect set of fundamental types, and miss a few operations on those types. Java's designers, for example, made strings a little too complex, and completely botched the date and time types. (To be fair, date and time types are almost always botched.) In order for a language to evolve, types need to evolve, including the fundamental ones. Ruby allows this kind of evolution via monkey patching. The next big language should allow this kind of evolution, ideally scoped to a single module rather than changed globally throughout an entire program.


If you read between the lines, GHC delivers most of these features today. This is a testament to the abilities and foresight of the GHC team, as well as the functional programming community as a whole. (Many of these features have been available in various Lisps for decades. Some are available today, with less lengthy histories.)

Haskell in general, and GHC in particular is a little short in some areas. There isn't a big library of Haskell code yet, but Cabal is vibrant and growing. Source level debugging is still a holy grail, but work on the GHCi debugger is progressing. (Thanks, mnislaih!)

Interestingly, the way Haskell implements "open classes" is lexically scoped by default. There's nothing stopping you from adding new numeric types (like vectors or sparse matrices), or even declaring strings to be numeric. It's actually much cleaner than monkey patching in Ruby.

On top of all that, Haskell does provide many of Steve's necessary language features:

• Destructuring bind (e.g. x, y = returnTwoValues())
• Function literals and first-class, non-broken closures
• List comprehensions
• Namespaces and packages
• Cross-platform GUI
• Operator overloading
• First-class parser and AST support
• Type expressions and statically checkable semantics
• Solid string and collection libraries
• Strings and streams act like collections

Add that up, and while Haskell may not be the next big language (for the mainstream), it's on the road towards the hundred year language, and it certainly doesn't suck.

Are bugs really important?

Reddit recently highlighted this post from an engineer who interned at Google and Microsoft before taking a job at Yahoo!. The stories are interesting, but this tidbit from an initial interview with Microsoft caught my eye:

I did one screening interview as a freshman on campus where I was rejected without mercy. Apparently the answer to “Can you tell me what was the most difficult bug you faced while programming and what you did to resolve it?” isn’t “My programs don’t have bugs.”

There's a huge body of lore around Microsoft interview questions. This is a common one, not used exclusively at Microsoft.

As I read that post, I started wondering what would my answer be? The longer I thought about it, the more surprised I was that nothing came to mind. This could mean a few things: that I'm not a good candidate for working at Microsoft, that I haven't been programming very long, or that I'm not a very good programmer.

Anyone who knows me knows that I would never want to work at Microsoft, so let's ignore that point. I've been slinging code for about 20 years, professionally for about 15 years, so my lack of a response doesn't necessarily imply a lack of experience. On most projects, I'm one of the developers that's brought in to solve the hard problems, so I don't think a lack of response is an indication that I'm just pulling a paycheck and not doing any real work.

The point of a question like this is to see how well and how deeply a candidate relates to his code. It's an obvious trap to elicit a response like "my programs don't have bugs", which is merely an indication that the interviewee (a) hasn't been programming very long and (b) hasn't worked on any project larger than a homework assignment. But if it elicits an animated and involved response from the interviewee, it shows he has a deep and detailed knowledge about his code and the platform he uses to develop software.

Unfortunately, this particular question places the focus on bugs. I wonder if this offers some insight into software development practices at Microsoft. Could it really be that their software development regimen is simply a never-ending bug squashing expedition into an ever-increasing blob of code? It's amusing to think so, but I doubt it.


The more I thought about it, the more I realized that I don't think about my career as moving from one bug to another. Over the years, I've picked up a variety of tools and techniques for isolating and fixing bugs. Some are mundane, like peppering print statements or invoking a source level debugger like perl -d or gdb. Some are more complex, like using test fixtures, constructing test data, or gathering diagnostics with a profiler. The skills are important; the bugs aren't.

But I occasionally do remember the bug. One that does come to mind involves a grammar I was writing from an incomplete and contradictory spec. The operator precedence was specified one way, but the expectation was the inverse. I implemented the precedence as specified, which did not result in the desired behavior. This led to many hours of meetings over a few weeks to determine that the spec was, in fact, wrong. The solution was to twiddle a couple lines of code, maybe 5 minutes to fix. Thirty minutes if you include the obligatory stop at the coffee shop to blow of some steam.

What matters for a professional software developer is preventing bugs from occurring in the first place, or quickly isolating bugs when they do occur. On that same project, I needed to test the grammar, so I wrote a test harness to run the parser capture its output, and compare the output to an expected value. I wrote another program to generate these inputs via brute force: running through all combinations of terms and operators, hunting for both successful parses and expected failures. In the end, I had a few thousand test cases that acted as a pretty complete set of regression tests.


Since I started working in Haskell, I find that I think even less about the bugs.

In many cases, a bug is a symptom that you're working on a large system, and the assumptions made in one part of the system violate the assumptions made in another part. A classic case is a memory leak, where the library assumes the caller manages a block of memory, but the caller fails to call free() when necessary. Or the opposite situation, where the library manages memory, and the caller calls free() needlessly.

However, in a Haskell program, these kinds of problems simply don't happen, or at least don't happen with nearly the same frequency. Each function acts as its own little world. The net result is that when debugging a particular function, you can ignore the rest of the universe and focus on one small piece of the puzzle in isolation.

Another advantage to Haskell is that many bugs don't happen because the type checker catches them. For example, if I want a single value out of a list, then I can't use map, which returns a list. Instead, I need to use a fold, or post-process the result of map with a function like head or last. In either case, the type checker will prevent me from running a program with this kind of bug.

All of which makes it easier to focus on the problems to be solved, and the tools needed to solve these problems, and ignore mundane details like bugs.

What's wrong with the For Loop, Revisited

I got a little bit of heat on yesterday's post on closures vs. for loops.

First, Cale pointed out that my expansion of foldl wasn't exactly right. Actually, it was a valid expansion of foldl', not foldl. For the purposes of that discussion, I wanted to focus on the concept of left and right folds, not the specifics lazy vs. strict evaluation. If you look at the ghc library docs, you'll find over a dozen variations on the theme of a "fold".

Cale, as always, was prompt, elucidating, helpful and correct. Thanks, Cale!


A few readers also pointed out that my discussion of the power of closures didn't include a single closure. Funny, that. Strictly speaking, curried functions, anonymous functions and sections aren't closures per se. Although I was trying to explain closures, I wound up explaining higher order functions instead.

At one point, I thought about posting a pedantic rebuttal, but really, that doesn't help anyone. So let's call this a fair cop and move on.

Closures are like a gold pass -- if a language provides both first class functions and closures, then it enables higher order programming. Pascal offers neither, and I remember writing sort and search code for every little type I wrote in my data structures class. C, for example, doesn't quite provide first class functions, and it certainly doesn't provide closures. But C does provide function pointers, which can approximate higher order programming in certain limited scenarios. I remember how wonderful it felt when I realized that library functions like qsort and bsearch meant I didn't need to write (and debug) nearly as many sort and search functions anymore.

But I promised you a closure, so here's a function with a closure:

main = do out <- open "out.txt" WriteMode
          mapM_ (\i -> hPutStrLn out $ show i) [1..10]

Or, more idiomatically:

main = do out <- open "out.txt" WriteMode
          mapM_ (hPutStrLn out . show) [1..10]

Interestingly, here's a different version of that same function that sends output to standard out. Note how similar this code is to the previous example:

main = mapM_ (putStrLn . show) [1..10]

The key here isn't about functions that have bindings to their outer environments. It's about higher order programming. And I should have said that yesterday.

Turns out that if you take some random programming language, add closures and first class functions, you can start to do some pretty amazing things.

Maybe the debate about adding closures to Java isn't really about adding closures to Java. Maybe it's about bringing higher order programming to Java, where the most vocal part of the debate involves complaining about the proposed syntax, or questioning the value making a large language definition even larger..

What's Wrong with the For Loop

Closures in Java are a hot topic of late. A few really smart people are drafting a proposal to add closures to a future version of the language. However, the proposed syntax and the linguistic addition are getting a lot of push back from many Java programmers.

Today, Elliotte Rusty Harold posted his doubts about the merits of closures in Java. Specifically, he asks "Why Hate the for Loop?":

I don’t know what it is some people have against for loops that they’re so eager to get rid of them. This isn’t the first or even the second time CS theorists have revolted against for loops (or equivalent).

It's unfair to single Elliotte out for doubting the value of the lowly little closure. Mostly, he's complaining that he doesn't see the value in closures in Java, after having read Bruce Tate's recent column on the subject. (Bruce uses Ruby for illustration):

Listing 1. The simplest possible closure

3.times {puts "Inside the times method."}

Results:
Inside the times method.
Inside the times method.
Inside the times method.

times is a method on the 3 object. It executes the code in the closure three times. {puts "Inside the times method."} is the closure. It's an anonymous function that's passed into the times method and prints a static sentence. This code is tighter and simpler than the alternative with a for loop, shown in Listing 2:

Listing 2: Looping without closures

for i in 1..3 
  puts "Inside the times method."
end

Given this lackluster introduction to closures, it's hard for me to see their real value. This first comparison is, at best, a subtle nuance. The rest of the examples in Bruce's article on developerWorks are equally trivial, dubious and unenlightening.

I'll ignore Elliotte's issues with Ruby style; it's not worth quibbling over. I'll also ignore the debate over the current syntax proposal for closures in Java, and the larger issue on whether or not closures belong in Java at this point. I don't have a horse in that race, and I honestly don't care how, when, or if it ever gets resolved.

Nevertheless, Elliotte does raise an important question: Why hate the for loop?

Here's a common example:

double sum = 0;
for (int i = 0; i < array.length; i++) {
  sum += array[i];
}

What's going on here? I've been programming for years, and I'm comfortable speed-reading this idiom; it's obviously a summation of a set of values in an array. But to actually read this block of code, I need to process about 30 tokens spread out over four lines. Sure, there's some syntactic sugar that could shave off a few tokens. But that's a lot of stuff to write and get correct just to do a simple summation.

Want proof? Here's the very next example from Elliotte's article, lifted verbatim:

String s = "";
for (int i = 0; i < args.length; i++) {
  s += array[i];
}

Spot the bug? If that code compiles and gets past code review, it could take weeks to get a bug report, and weeks more to get a fix ready. And these are simple for loops. Imagine how much more complex these things get as the loop bodies get larger, and possibly nested. (If you're still not worried about bugs, think about the possible typos. Then think about how often you write loops like this.)

If you could write a simple for loop in one line, with less repetition and fewer symbols, it should be both easier to read and easier to write. Because it's concise, there's much less likelihood that it will lead to bugs, and when bugs do occur, they should be easier to spot.

How would closures help here? Here's the first example, in Haskell:

total = sum array

OK, that was cheating. sum doesn't use closures. It is defined in terms of a fold, which does take closures:

total = foldl (+) 0 array

Here's the second example, idiomatically and with closures:

s = concat array
s = foldr (++) [] array

Admittedly, using odd-looking functions with names foldl and foldr to explain closures may not make sense to programmers more familiar with for loops. But it does highlight the key failing of for loops: they conflate three separate kinds of operations -- filtering, reduction and transformation.

In the two for loops above, the goal was to take a list of values and reduce it to a single value. Functional programmers call these operations "folds". The way a fold works is by starting with an operation (a closure) and a seed value, and visiting the first element of the list. The operation is applied to the seed and the first value, producing a new seed. The fold then performs with the operation with the new seed and the next value in the list, all the way down to the last value, when the result of the last operation becomes the result of the fold.

Here's a demonstration:

s = foldl (+) 0       [1, 2, 3]
  = foldl (+) (0 + 1) [2, 3]
  = foldl (+) 1       [2, 3]
  = foldl (+) (1 + 2) [3]
  = foldl (+) 3       [3]
  = foldl (+) (3 + 3) []
  = foldl (+) 6       []
  = 6

Haskell provides a few fold functions; foldl starts examining the list from the beginning and works its way to the end, and foldr, which starts from the end and works its way backwards to the beginning. Other variations exist, but these are the two fundamental ones.

Of course, folds are a very primitive operation, and it would be very confusing if for loops were thrown out and replaced with various foldl and foldr incantations. Instead, higher level operations like sum, prod and concat are defined in terms of folds. And your code is then written in terms of these higher-level reducing operations, making your code more concise, easier to read, easier to write, and easier to understand.

But not every for loop is a reduction. Consider this one:

for (int i = 0; i < array.length; i++) {
  array[i] *= 2;
}

This operation is a transformation, what functional programmers call a map:

new_array = map (*2) array

The way map works is by examining every element of a list, applying a function to each element, and building up a new list with all the new values. (Some languages do this in-place.) It's a much easier operation to understand. sort does something similar, in that it takes a list and returns (or modifies) a list.

The third kind of for loop is a filter. Here's an example:

int tmp[] = new int[nums.length];
int j = 0;
for (int i = 0; i < nums.length; i++) {
  if ((nums[i] % 2) == 1) {
    tmp[j] = nums[i];
    j++;
  }
}

Here we have a very simple operation that's almost completely hidden by the needless complexity of using a for loop, and two independent indices. If filtering is a fundamental operation, it should be as easy as a fold or a map, and in fact, it is:

odds = filter (\i => (i `mod` 2) == 1) nums
odds = filter isOdd nums -- more idiomatic

This, at the heart of it all, is what's wrong with the for loop: it conflates (at least) three separate kinds of operations, and focuses on a minor detail: walking over a series of (index) values. But really, fold, map and filter are three different ways to process a list of values, and they need to be handled differently. Using closures to pass in the body of a loop also makes it easier to split the what from the how. I could write anonymous functions each time I traverse a list, or I could reuse a well known function (like isOdd, (+) or sqrt).

If closures aren't an esoteric feature, but deeply baked into a language and its standard library, there's no need to mess around with these low level operations. Instead, we can create higher level actions that say what they do, like sum and prod.

Furthermore, thinking in these terms makes it easier to think about more complex operations, like mapping a tree, filtering a vector, or folding a list into a hash.


Finally, Elliotte did some handwaving about parallelized execution on multiple cores, and how code like 3.times {...} is "worse" than a for loop. Sadly, I think he's missing the point. True, there are some computations that need to be serialized, and some that may be parallelized. But figuring out which is which is a difficult compiler optimization if your only tool is a for loop. If you can split up the serial computations (i.e. foldl and foldr) from the possibly parallelized computations (i.e., map and filter), it's much easier for the compiler to figure out. Not only that, but you could explicitly ask for a serial or parallel version of map if you know your data better than your compiler.