Sunday, September 21, 2014

Functional Programming in Mainstream Languages, Part 1: What and Why

(Jump to Table of Contents)
John Backus worked for IBM from 1950 until 1991 and was the principal developer of FORTRAN, one of the first high-level programming languages.  He is immortalized in the acronym BNF, which stands for "Backus-Naur Form" (or sometimes "Backus Normal Form").  In 1977 he received the ACM Turing Award (the "Nobel prize of Computer Science"); his award lecture was titled "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs."  This was in a way a reaction to FORTRAN, and describes the vision of functional programming.

The "von Neumann style" is a model of computation that is very close to the way computers actually work.  Its main component is the memory, which is composed of individually-addressable cells.  Each memory cell can be read and modified by the computer executing a program, which is also stored in memory.  This model was very useful for building early computers, and was naturally taken as the basis for the first high-level languages.  The closer the model of the language is to the hardware model, the easier it is to compile programs to machine instructions that the hardware can execute directly.

Backus, however, made the point that the language model can be more abstract than the hardware model.  While this puts a greater strain on compiler writers, it can free (or "liberate") programmers from a lot of the drudgery that is involved in programming directly to the hardware model.

The most basic principle of functional programming is the absence of any side effects.  This means that functional programming language do not have the concept of variables as places (representing memory cells) that can be changed.  Values in functional programs are immutable; that is, they can't change.  This concept extends to data structures as well; for example, lists, maps, and "objects" in functional languages can't be modified, in total or in part.  And it also extends to interactions of the program with the outside world.

This may seem like an impossible restriction; how can you describe a computation without changing values?  In fact, it is quite easy and natural, but it does take some getting used to, especially if you are used to programming in imperative languages.  These include most mainstream languages, in which variables and mutable data structures are the norm.

The major benefit of functional programming is its very simple computational model, which is very close to mathematical thinking.  Because values in a functional program can't change, functional programs enjoy the property of referential transparency.  This means that if an expression has some value, it will always have the same value.  (This is not true in imperative languages; just think of a parameterless function that returns pseudo-random numbers.)  This means that you can use the well-known substitution principle from mathematics: if a=b then you can replace a by b everywhere it appears.  This is not true in imperative languages, since even if a=b now, they may be different after any change that may affect one or both of the expressions.  The computational model of imperative languages therefore must incorporate the notion of time; every assertion may be true at one time and false in another.  This results in a much more complicated model.

Most programmers don't bother thinking about the computational model underlying their programming language, but it is crucial for writing, understanding, and reasoning about programs.  A simple model makes all these simpler.  Programming in a language that has a complex model is like walking around with a heavy weight on your back; you don't notice you're carrying it until it is suddenly gone.

Another important property of functional programs, which is becoming increasingly important, is that it is much easier to parallelize them.  Imperative programs suffer from problems such as race conditions and non-atomic updates, which are a result of side effects.  By eliminating side effects, functional programs get rid of these undesirable consequences as well.  One commercially-successful functional language that makes great use of this fact is Erlang.

The functional paradigm is Turing-complete; that is, it can express any computation that any conceivable machine can perform.  However, creating functional analogues of mutable data structures is complicated (although this work can mostly be relegated to library writers).  It is therefore unrealistic to expect most programmers to abandon mainstream languages in favor of functional languages.

Since functional programming is predicated on the lack of side effects, it seems to be inherently contradictory to imperative programming.  However, in the last decade or two, there is a growing movement to incorporate functional programming techniques into scripting and object-oriented languages, including JavaScript, Ruby, Scala, and, more recently, Java 8.  There is also much academic work on the integration of the functional and object-oriented paradigms; so much so, that one of the predictions of Murphy-Hill and Grossman in their paper "How Programming Languages Will Co-evolve with Software Engineering: A Bright Decade Ahead" (Future of Software Engineering, 2014) is the blurring between these paradigms (see my review of that paper).

How can these conflicting paradigms be reconciled?  The point is that even if you want to use side effects (including assignment and mutation of data structures), you don't have to go the whole hog and use them everywhere.  By making some of your data structures immutable, you will reap some of the benefits of functional programming.  Bertrand Meyer, one of the gurus of object-oriented programming, includes the Command-Query Separation principle in the chapter on designing class interfaces in his landmark book, Object-Oriented Software Construction (2nd Edition).  This principle requires methods to be either queries, which return information but don't mutate objects, or commands, which mutate objects but don't return any results, but not both.  This separation results in some measure of referential transparency, because it tends to reduce the number of mutations.

In addition to immutability, the most important aspects of functional programming that are also relevant to imperative languages are high-order functions and streams.  In following posts I will show examples of functional programming techniques, both in (fully or mostly) functional languages, as well as in mainstream languages including Java 8.

This series of posts has the following parts:

Introduction
Part 1: What and Why

Higher-order functions
Part 2: Java 8 (Introduction)
Part 3: Java 7 and Java 8
Part 4: JavaScript
Part 5: Scala
Part 6: Xtend
Part 7: Haskell

#functionalprogramming