Pacific Connection(英語)
Functional Programming on the Cusp of Commercial Success
2008年12月22日
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’
The workshop’
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’
“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’
Both have found niches. “The ‘call by value’ strategy is perhaps a bit more intuitive. It’
Michael Sperber, a software consultant based in Tubingen, Germany, says that functional programming’
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’
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’
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’
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’
Galois started doing its own commercial work in 2000, focusing on contract-based research and development. “Haskell had clear benefits, but it wasn’
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’
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’
The problems vary, and each contest is organized by a different institution. Here’
- 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’
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’
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.
バックナンバー
Pacific Connection(英語)
- Charting the New World of Neogeography
- Threaded Building Blocks: Intel's James Reinders on writing parallel code for C++
- Sipping Cappuccino at 280 North
- Functional Programming on the Cusp of Commercial Success
- On Fedora’s Fifth, Project Manager Paul Frields Looks Upstream
- Embedded Computing for the Rest of us: Project Sun SPOT
- Cloud Computing Vendors Reaching Out to Developers
- OpenStreetMap: The Map that Anyone Can Edit
- Magnatune: “Open Source” Music Turns a Profit
- Keeping it Loose at LugRadio Live USA