At the Oregon technology firm Galois, the programming language of choice is not C++, Java or Perl. Instead, the firm has embraced a lesser known, but up and coming language known as Haskell. That language and a few of its cousins－including Erlang, OCaml, Scheme and F#－represent a fork in the road for programming languages: they are not “procedural”
Some academic researchers are following the same path. That’s the case for Andy Adams-Moran, who first met Galois’s other two of the firm's three co-founders in the early 1990s at the University of Glasgow, which at the time, he says, was “the heart of functional programming for the world.” Functional programming research later spread to Sweden; Cambridge, England; New South Wales, and later still, to Galois’ home in Portland. Adams-Moran, a native Australian, has worked in most of them. At the thirteenth annual International Conference on Functional Programming held last October in Vancouver, Adams-Moran participated in the Commercial Users of Functional Programming workshop, which he has previously co-chaired. “The idea is to get companies like us together to swap success stories and exchange advice－in our quest to bring functional programming into the commercial sector,” he says.
The workshop’s attendance has grown markedly, with progress measured one “enlightened” programmer at a time. Call it programming nirvana. On the Ars Technica blog, Ryan Paul wrote that "for some programmers, learning to see the ineffable theoretical perfection of functional programming languages is a profoundly illuminating experience that opens the mind to a completely new way of perceiving and understanding computer programming.”
The primacy of mathematical functions
The essential idea behind functional programming is implicit in the name: functional languages are designed first and foremost to deal with mathematical functions. “This is a programming model in which functions are first class－meaning that you can do with functions everything you can ordinarily do with strings and integers,” says Matthew Fluet, a research assistant professor at the Toyota Technological Institute at Chicago and the publicity chair for the ICFP conference. “You can store functions in data structures, pass them to other functions, and get them back as return values."
Fluet says that a consequence of giving functions first-class status is that "a function's meaning is now dependent upon the values of the variables to which it refers, even after the function has been returned or stored in a data structure. In order to avoid changing a function's meaning after it has been created, functional programming languages disallow updates to variables." In a procedural language, for example, you might set i to i+4 in a loop, whereas in a functional language, you would define i=7 and j to be i+4. “You don’t update a value, but create a new value derived from an old one. Hence, loops end up using function arguments as ways of saying: ‘here’s a brand new value within the loop.’ We do this so that when I hand you the ‘plus-one’ function, you don’t expect the meaning of that function to change just because you’ve updated that variable in the generating function. You can drill down into loops and create new strings, and you can also drill down into recursive functions and generate new functions. The guiding principle is that the meanings of the functions, and by extension, the values they contain, don’t change. Rather, the computation generates new values, with new interpretations of those values as you go along until you finally get some interesting results.
“It can be eye-opening to see what you can do when you pass around functions as these first class values. With functional programming, we break down programs into very small pieces－called ‘combinators’
Fluet says there are two language groups: "call by name" and "call by value." The first, which includes Scheme, the ML languages like OCaml, and Erlang, calls a procedure and then evaluates all of its arguments down to values. "The other evaluation strategy, sometimes referred to as 'lazy,' essentially asks: why bother evaluating some expression down to a value if I’m handing it off to some function that isn’t going to look at that value. Let’s hold it as an unevaluated expression until a value is needed by another procedure. The decisions on whether to evaluate are delayed until runtime. With this approach, it’s much easier to program with what you might call an ‘infinite data structures.’ You never realize the “infinite-ness” of the structure because nobody actually demands to look at all of it. Haskell and Clean are examples of this approach."
Both have found niches. “The ‘call by value’ strategy is perhaps a bit more intuitive. It’s easier to look at your program and determine how it’s going to behave in terms of using compute cycles and memory. On the other hand, the ‘call by name’ strategy makes it easier to look at a program and see what its final answer will be. So there are philosophical and practical reasons to adopt either of them.” The 'call by name' strategy does present some challenges. In Haskell, even basic I/
Michael Sperber, a software consultant based in Tubingen, Germany, says that functional programming’s biggest benefit is its versatility in handling abstraction. “You have two similar pieces of code that you want to merge into one. In doing so, it’s easy to imagine, with any language, abstracting over numerical values and character strings. Functional programming languages differ in that any entity in the programming language can be abstracted. Whereas, for example, in object oriented languages, you can abstract over an object in a general way, but not a class.”
Of course the primary things functional programming abstracts are functions. Doing so “is a very natural way to systematically develop code and not have to worry about the mechanics. In object oriented programming, you have to force what you are trying to accomplish into the world of objects, classes and methods. Some problems fit that model and some don’t, and when they don’t, your program will look different from your mental model of how you were going to solve the problem. For example, when I do object oriented programming in Java, I want to abstract over classes all the time. But the language doesn’t let me do it, so I have to find some kind of work-around and that means I’m spending time worrying about how the mechanics of the language work instead of how I want to solve my problem.”
Tim Sheard, a professor of computer science at Portland State University, says that functional programs often require less lines of code precisely because they are good at building abstractions. “You can see some sort of pattern, give that pattern a name, and then you can reuse it. That’s a much more powerful technique than some of the other organizing principles. Object oriented language’s tree-like, hierarchical structure doesn’t compare in power to the functional abstraction approach, where you can reuse a pattern anywhere after you give it a name. In a functional language, you can take just about any pattern and recognize it. That’s not true with many other languages. It’s all well and good to talk about programming design patterns, but often, I can’t actually capture that pattern as an abstraction in my language. In functional languages, that happens less often: things usually get expressed right within the language. I don’t have to write a book about design patterns; I can write a library, instead, and post it for millions of people to use.”
What had been missing in functional languages was performance: compared with, say, C++, higher level languages require “smarter” compilers in order to generate efficient machine code. Adams-Moran credits Simon Peyton Jones of Microsoft Research with being the driving force behind GHC, the Glasgow Haskell Compiler. Peyton Jones, who taught at Glasgow University until 1998, was one of just a handful of Haskell researchers in the late 1980s and early 1990s.
“They have been joined by a second generation of compiler hackers, with about 50 contributors and many more contributing libraries－for writing Web applications, numerical calculations, compilers,” Adams-Moran says. “A high-level language requires a lot more work on the part of the compiler, but there is also a lot more opportunity for optimization. In particular, the GHC performs 50 to 100 different optimizations, depending on the package you use. Because Haskell is a functional language, these are correctness-preserving transformations－meaning you can do as many as you like without affecting accuracy. There are whole program optimizations, and at the back end, a run-time system and code-generator that have been tuned for the last 15 years.”
Adams-Moran says that Haskell has particular advantages in multi-core environments. “When you are dealing with something mathematical, it doesn’t matter when the various parts are evaluated－there are fewer interdependencies, and when they are, they’re made absolutely explicit in the code, allowing the compiler to make intelligent decisions.” Even before multi-core, Moore’s Law was giving an assist to Haskell. “We have a Web server running in-house whose performance, even without running on a multicore processor, is good enough. We had it within 10 percent of Apache two years ago.”
Financial apps－and more
While advocates insist that every application under the sun can benefit from functional programming, some applications stand out, with the investment banking sector (or what remains of it), a stand-out. “The banks come up with fancy new derivative products, promising their client that they will have a price in a couple of hours, which leaves only a very short amount of time to write the code,” says Michael Sperber. He says that functional programming can reduce source code by a factor of five to fifteen. “I know I am probably about 10 times as fast writing in a functional language than I am in writing Java code or C++ code.”
Beyond that, the range of applications grows more diffuse. The program committee for the ICFP’s Commercial Users of Functional Programming included representatives from Intel, IBM, Credit Suisse, and Ericsson. An Ericsson acquisition, Ellemtel (now Ericsson Utvecklings AB), had the distinction of originating its own functional language, Erlang, around 1990. While telecommunications was the target application, Fluet says that the company has committed enough resources to make Erlang “a good general purpose language, useable not just on their devices, but PCs. Some of the biggest industrial users have come out of the Erlang community, including a number of full-time consultants.”
Galois started doing its own commercial work in 2000, focusing on contract-based research and development. “Haskell had clear benefits, but it wasn’t quite ready for full-scale end user programs,” Adams-Moran recalled. “It took us a while to hit upon information assurance: essentially, writing secure applications that mimic the capabilities of the wider Internet, but more securely, with the ability to sequester information. You can see how that would be of interest to the U.
Galois has also used functional programming for generating VHDL (VHSIC--Very high speed integrated circuits－Hardware Description Language) netlists, which are used to describe integrated circuits. The company recently spun off another firm, Signali Corp, which designs and implements complex algorithms for field programmable gate arrays.
Finding functional programmers
One obvious impediment to the growth of functional programming is programmer education. “Europe has a lot more emphasis on functional programming in the undergraduate curriculum than the U.
“I think functional programming is about to become an extremely important part of the arsenal that we use to program programs,” says Portland State University’s Tim Sheard. “All of a sudden I’m starting to see it used in industry, in lots of different places.” Sheard recalls a colleague, seemingly set in his ways, who became a Haskell convert. The department offers an elective undergraduate class in Haskell and some students have actually chosen to come to the class after reading about functional programming in news groups－a fact Sheard finds amazing. “Usually, students pick a school because friends go there, because of the football team, because the weather is nice, because it’s a party school. Or they might look and say this department is strong because US News and World Report says it’s good. But to actually look at what the faculty members do is extraordinary. That has never, ever happened to me before.”
Sidebar: The ICFP Programming Contest
Since 1998, the International Conference on Functional Programming has featured a programming contest that gives contestants from around the world 72 hours, including a 24-hour lightning round, to solve a problem posted on the contest’s website:
The problems vary, and each contest is organized by a different institution. Here’s a sampling:
- In 1999, Harvard and the University of Virginia asked contestants to write an optimizer to improve the state machines generated by a high-level compiler, which in turn, determines the behavior of characters in a mobile game.
- In 2004, the University of Pennsylvania challenged players to design an ant colony that can gather the most food while fending off competing colonies. Submissions were in the form of code for a finite state machine describing the “neural wiring” for the ants.
- In 2005, a group organized around PLT looked for two programs to control the behavior of a “Robber-Bot” and “Cop-Bot” in a virtual Hyde Park, Chicago.
- In 2006, Carnegie Mellon University asked contestants to investigate an ancient codex dating back to 200 BC that was written by the “Cult of the Bound Variable.”
- In the 2007 contest, Utrecht University in The Netherlands looked to help an extraterrestrial named Endo by repairing his DNA.
This year’s contest was organized by Tim Sheard of Portland State University, John Reppy of the University of Chicago－both for the second time－and nine of their colleagues. The challenge: create a control system for the next NASA mission to Mars. “We tried very hard to come up with a problem that we thought was language-neutral, that gave no language a benefit,” says Sheard. “If it was a problem that was designed for functional languages and a functional language won, then it wouldn’t mean much.” The design team seems to have succeeded: this year’s winning entry was coded in Java.
The 2008 task description, the longest to date, took as its operating parameters actual rover models. Contestants were given information on the rectangular region of Mars where the contest took place, the location of the intended destination, a formula for its linear speed that takes drag and acceleration into account, the ranges of its visual sensors, and more－the syntax for a variety of messages from rover to controller, as well as controller commands for breaking, rolling, accelerating and turning－which control a pair of state machines. The contest was run as a series of elimination heats, each composed of trials. Each trial consisted of five runs on a given map, with the score determined by time, with penalties for incomplete runs. The lowest two scores of each trial were discarded and the remaining three were averaged. The lower the ultimate score, the better. Entries needed to run in the contest’s LiveCD Linux environment.
Sheard thinks the contest says less about the state of functional programming than it does about the state of the programmers, themselves. “There is a tremendous spirit of cooperation,” he says. For example, contestants began posting their own obstacle maps, giving other people a chance to try them.
Even so, one would expect that in a functional programming contest, the winning entry would use a functional language. Is that the case? Here, according to Wikipedia, are the winners:
| Year | First Prize | Second Prize |
|---|---|---|
| 1998 | Cilk | OCaml |
| 1999 | OCaml | Haskell |
| 2000 | OCaml | OCaml |
| 2001 | Haskell | Dylan |
| 2002 | OCaml | C |
| 2003 | C++ | C++ |
| 2004 | Haskell | Haskell and C++ |
| 2005 | Haskell | Dylan |
| 2006 | 2D | D |
| 2007 | C++ | Perl |
| 2008 | Java | － |
The picture for first place is complicated by 2D, a language invented for the 2006 contest that used C++, Haskell, and Python, among others. (Cilk, the 1998 winner, is an MIT language for supercomputers that is not a functional language.) So looking just at the pure-bred winners, functional language entries took first place six times out of 10. Second prize winners include two entries in Dylan, a functional language created in the 1990s at Apple Computer. The score: about 5.