As computers become more powerful and the programs that run them grow more complex, programmers are increasingly trying to make their lives easier by turning to an idea that dates to the early days of computer languages, an approach called functional programming.
“Functional programming’s on a long steady burn, starting 30 or 40 years ago,” says Simon Peyton Jones, a researcher at Microsoft Research in Cambridge, U.K., where he focuses on the functional language Haskell.
Programming languages break down into broad categories. There are imperative languages, which say, “do this, then do that,” specifying a series of steps to accomplish a task. Functional languages, on the other hand, rely on functions, which are mathematical operations.
“A function is just basically a piece of an algorithm,” says Iavor Diatchki, a senior research and development engineer at Galois, a software company in Portland, OR. “It’s something that you can give some inputs and it computes some outputs.” For instance, “plus” is a basic function; it says to take two integers and combine them to produce one integer as a result.
Functional languages operate at a higher level of abstraction, automating a lot of the details that underlie a particular operation. That makes it easier to write programs quickly. Years ago, when computers were slower, that ease came with a cost, Diatchki says; the program’s default steps were not always the most efficient, and a programmer could make it run better by taking the time to tweak the details. That has changed. “Computers are a lot faster, so things like that don’t matter all that much,” says Diatchki, who argues that making better use of a programmer’s time has become more important. “Also, the kind of software we write tends to be a lot more complicated, so some of these small performance issues are not nearly as important. What’s important is that you manage to put all the pieces together and get the program to work.”
Higher-level languages are more productive, says Sergio Antoy, Textronics Professor of computer science at Oregon’s Portland State University, in the sense that they require fewer lines of code. A program written in machine language, for instance, might require 100 pages of code covering every little detail, whereas the same program might take only 50 pages in C and 25 in Java, as the level of abstraction increases. In a functional language, Antoy says, the same task might be accomplished in only 15 pages.
Additionally, the less a developer writes, the less opportunity he has to include something that causes a problem. “As you remove details, you remove the potential for error,” Antoy says. Higher-level languages also lead to programs that are easier to modify if the underlying machine architecture changes.
Another important aspect of functional programming is that functions do not change the data with which they work. Having immutable data makes it easier to do parallel processing. If two processors are manipulating the same data at the same time, one processor may alter the input to the other; if that happens in the wrong order or at the wrong time, the results could be incorrect. In functional programming, each processor would only need to read the original data, which would remain unaltered.
The fact that the computational state of the system does not change makes it easier to understand what exactly a program is doing, says Antoy. “It’s more difficult to reason about computation in which there is a state,” he says. Object-oriented imperative languages such as C, Java, or Python change their state as they run. “If you have a computation in which you have variables that can change over time, when you reason about this you don’t know what the value of the variable is at that time, so it’s like shooting a moving target. You want to reason about something and things keep changing.”
Because the state does not change, functional languages are attractive for programs that require a high level of security, such as those used by financial institutions, where functional programs are becoming increasingly popular, says Philip Wadler, a professor of theoretical computer science at the University of Edinburgh in the U.K. and one of the creators of Haskell. “You need to be able to write a program pretty quickly and still have high assurance it’s going to do what you expect,” Wadler says. For instance, the New York-based international trading firm Jane Street Capital uses Ocaml, a dialect of ML, one of the earliest functional languages.
Wadler is also a senior research fellow for IOHK, a Hong Kong-based company designing cryptocurrency, a digital form of money of which bitcoin is the most well-known example. The ease of creating and validating programs written in functional languages makes them than appealing for such applications, Wadler says. “There’s a huge amount of money that’s at stake there.”
Matter of Opinion
Just what counts as a functional language can be open to interpretation. “Haskell and ML are widely considered to be functional. Languages like C++ or C and even Java are considered to be imperative,” Diatchki says. “Then there are languages like Scala, which sort of depends on who you talk to whether they’re functional or imperative, because they support both styles.” Often, programmers choose the style that suits them best, or even employ both in different parts of their code.
To Diatchki’s thinking, imperative languages are more like recipes, laying out a series of steps to accomplish a task, while functional programming is more like a calculator, except that it manipulates more than just integers. “You type in a big expression and say, ‘what is the result now?'” He would not consider a language functional, he says, unless it treated functions as ‘first-class citizens’; in other words, the functions can be used as arguments for other functions, and be returned as values by still other functions.
While much of the work in functional programming originated with academia—Haskell was created in 1990 by academics who were doing much the same work, but needed a common language to share their findings—it is increasingly finding a place in industry. For instance, Google’s MapReduce, used for searching the Web, draws heavily on ideas from functional programming, Wadler says. Map applies a function to a large collection of data— finding instances of a term on scattered Web pages, say—and reduce then accumulates what it returns, presenting the search results as a new page.
Facebook uses Haskell to filter spam from postings. Microsoft supports F#, a dialect of Ocaml, in its Visual Studio development environment. A functional language developed by industry, Erlang, was created by the Stockholm, Sweden-based telecommunications company Ericsson for telephone systems and now is used to build scalable real-time systems for banking, e-commerce, and instant messaging; the messaging and Voice-over-IP program Whatsapp is written in Erlang.
Laboratory Space
Peyton Jones sees functional programming as a laboratory for trying out new ideas in programming that then find their way into other languages. “Functional programming has been an effective seedbed of ideas,” says Peyton Jones. “It started off extremely impractical, but nevertheless intellectually appealing, and that very practicality forced a series of ideas to come to the surface that have then turned out to be useful much more broadly.” For instance, garbage collection, an automated approach to managing memory, started out in functional programming but has since been more widely adopted. It has also been a test-bed for static type checking, which looks through the program for errors before runtime and can vastly reduce the number of bugs in a program.
In fact, Peyton Jones says, there is a lot of work among functional programming researchers on developing richer type systems, which verify the accuracy of a program. The theorem prover Coq is a dependently typed functional language able, because of its type structure, to verify mathematical statements, though it is difficult to write programs in, he says.
He sees functional programming moving toward formal verification, giving developers greater confidence a program will do what it is designed to do. “The more people care about reliability, about knowing that something is true, that money depends on it or people’s lives depend on it, the more they’re going to care about this,” Peyton Jones says.
Of course, Diatchki says, it is not only functional programmers who care that what they write works correctly. “It’s just that functional programming seems to be blurring the line between writing the program and verifying it.”
The style also lends itself to new variations. Antoy and Michael Hanus, a professor of computer science at the University of Kiel, Germany, are studying functional logic programming, which adds a concept called determinism. That allows them to attack problems where no precise algorithm is known, and some trial and error is required. “This is quite convenient when you have to compute with partial or incomplete information,” Antoy says, or when getting precise and complete information is inconvenient.
Peyton Jones believes functional programming is becoming more popular as more developers learn about it. Eventually, he says, its distinction from imperative languages will all but evaporate, as the useful features of one approach seep into the other. “They are kinds of ends of the spectrum that are converging,” he says. “When the limestone of imperative programming has worn away, the granite of functional programming will be revealed underneath.”
Further Reading
Diatchki, I.S., Hallgren, T., Jones, M.P., Leslie, R., and Tolmach, A.
Writing systems software in a functional language: An experience report PLOS 2007 http://yav.github.io/publications/plos07.pdf
Antoy, S. and Hanus, M.
Functional Logic Programming, CACM 43, April 2010, doi:10.1145/1721654.1721675
Bernardy, J-P., Boespflug, M., Newton, R., Peyton Jones, S., and Spiwack, A.
Linear Haskell: Practical linearity in a higher-order polymorphic language, Proceedings of the ACM on Programming Languages 2, 2017 https://www.microsoft.com/en-us/research/publication/retrofitting-linear-types/
Vazou, N., Choudhury, V., Scott, R.G., Newton, P.R., Wadler, P., and Jhala, R.
Refinement reflection: Complete verification with SMT Principles of Programming Languages (POPL), Los Angeles, 8–13 January 2018. https://dl.acm.org/citation.cfm?doid=3177123.3158141
Functional Programming and Haskell https://www.youtube.com/watch?v=LnX3B9oaKzw
Join the Discussion (0)
Become a Member or Sign In to Post a Comment