The Functional Style — Part 1
Want to learn more about the functional programming style? Check out this first installment of the series on functional programming and how to use it.
Join the DZone community and get the full member experience.Join For Free
Functional programming is a very hot topic nowadays. People are increasingly interested in functional and hybrid-functional languages, such as Haskell, Scala, F#, and Clojure, and functional programming is one of the most popular requested topics for discussion in conferences and programming communities. Since you're reading this, maybe you are interested to find out more about it too; if so, this article series on functional style is meant for you. I have been motivated to write this because I feel that there is a need for more literature explaining how to program in the functional style. I want to illustrate this with helpful code examples and highlight some of the benefits from the functional style.
Functional programming is often discussed in very academic and mathematical terms, but I don't want to go there. That isn't how I learned it myself. I'm not a computer science graduate, and I was never formally taught it. I learned how to program at home, as many 90's adolescents did, and my learning has continued for more than 20 years with professional experience. Moreover, at no time have I ever felt like I knew everything I needed to know about functional programming. I have always been attentive to the current developments in my field and am keenly interested in its history. This series of articles is aimed at similar people — pragmatic programmers who love their field and learn best by writing code, who are humble enough to realize there is always more to learn, and practical enough to see the profit in doing so.
Therefore, over the course of this nine-part series, I want to cover the topics that I think are important in functional programming. I will try to explain first-class and higher-order functions, map and reduce, currying, function composition and monads, lazy evaluation, and persistent data structures. All will be illustrated with code examples wherever possible. Most (but not all) of the code will be in Java, Groovy, and Clojure.
Topics you will not find in this series include monoids, functors, applications, and category theory. If you want to know more about those things, then I recommend reading Bartosz Milewski's Programming Café. This is a good place to start, and the author begins with the discussing the basics. I will include a small amount of algebra because I think it is reasonable to assume some acquaintance with mathematics in an audience of computer programmers. These articles are aimed at people who are new to functional programming, not people who are new to programming in general. I would be very interested to see whether neophytes find it any harder to learn programming in the functional rather than the imperative style, but that is not the purpose of this series.
Should I Learn a Functional Language?
Not necessarily — indeed, my main aim in this series is to demonstrate the functional style, to show how it can be adopted in many languages, and the benefits of learning this type of programming. I will use Java and, to a lesser extent, C# to illustrate many points in this series. Nevertheless, languages that are not designed for functional programming shall, henceforth, be referred to as imperative languages — because they are all, in some way, flawed for expressing functional code.
Functional code can be expressed, obviously, in languages that have been created specifically for functional programming. Haskell is generally considered the purest functional language. It was born out of academia and its community likes to think about and discuss programming in very mathematical terms. Another popular functional language is Clojure. This is a dialect of Lisp that runs on the Java virtual machine. Not all Lisps are properly functional languages, but Clojure is explicitly designed for functional programming and has excellent support for concurrency.
Haskell and Clojure exist, in a way, at opposite ends of the FP spectrum. Clojure is dynamically typed while Haskell is statically typed — and very strongly so. You may be aware that a religious war has been raging for decades in the object-oriented programing world between static and dynamic typing. It is being fought in FP, as well.
Two languages that are often thought of as functional, Scala and F#, are actually hybrids. They support both functional and imperative styles of programming, leaving the choice left to the programmer. F# is part of the .NET family and compiles to run on the Common Language Runtime. Scala, like Clojure, runs on the JVM.
What Is Functional Programming?
I remember looking up functional programming when I first heard of it and reading about it in this quote from Wikipedia:
In functional code, the output value of a function depends only on the arguments that are passed to the function, so calling a function f twice with the same value for an argument x produces the same result f(x) each time.
Functions with this character are said to be "pure." When functions are not pure, the reason is that they depend on state that may change outside the function. This external state might be in the form of global variables, or objects, and it might be in a file, database, or any number of other things. Functional programmers refer to changes of state as side effects:
Eliminating side effects, i.e., changes in state that do not depend on the function inputs, can make it much easier to understand and predict the behavior of a program, which is one of the key motivations for the development of functional programming.
Functional programming, therefore, is programming that avoids these side effects wherever possible. But understanding it this way, intellectually, was insufficient for me to see the real strength of programming in the functional style. In the end, it was learning Clojure, which also taught me how to make good use of the Java streams API, that showed me the benefits of functional programming. I find that I now view programming problems differently, and the functional style permits me to express my intent much more directly in my code.
Side Effects and Imperative Languages
Imperative languages consist of all languages not explicitly designed for functional programming. This includes all the procedural and object-oriented languages, like Fortran, Algol, C, Smalltalk, C++, Java, C#, etc. Imperative means giving orders — do this, do that. The purpose of these orders is to cause side effects. A side effect means that some state somewhere was changed.
Elements in most imperative programming languages can be broken into three classes:
- Control structures: if-then-else, loops, etc.
- Statements: assign a variable, reassign a variable, call a procedure, etc.
- Expressions: code that yields a value.
Of these three, statements are the imperative part of imperative programming. Statements cause side effects. Now, almost everyone agrees that global variables are a bad thing. Why is that? They're bad because a global variable can be changed at any time by a statement anywhere in the code, which makes the code very difficult to understand and debug. This is why we prefer to keep globally-accessible data constant. Functional programming takes this idea further and asserts that it is better to not modify local, private variables.
Functional programming is, therefore, programming without statements, more or less. In general, only control structures and expressions are used, and even the control structures are actually expressions. Consider this simple code:
if (myVar == "foo") return "myVar was foo"; else return "myVar was something else";
This can be expressed more succinctly using the ternary operator:
return (myVar == "foo") ? "myVar was foo" : "myVar was something else";
if statement has been transformed into an expression, while the meaning has been kept exactly the same. Not only is it arguably cleaner, but now there is only one return statement. This gives us a taste of what functional programming should look like.
The avoidance of changing state means that iteration also needs to be treated differently. Indeed, in functional programming, iteration tends to take a different form entirely. But, we are getting a little ahead of ourselves — this will all be made clearer later.
Getting Started With Functional Programming
A good place to begin would be to pin down a practical definition for functional programming. That is to say: (1) what it is in particular that makes a programming style functional, as opposed to imperative, and (2) what it is, in particular, that makes a functional language? I have found this phrase effective in understanding function programming:
Functional programming imposes discipline on mutating state.
To mutate state means to change the value of something after it has already been assigned. For example, consider the following code snippet:
int x = 0; x = x + 1;
Initially, the symbol
x was associated with the value
0. This is the assignment. Then, it is associated with a new value, which happens to be the old value plus one. This is reassignment, and the act of reassignment has mutated state: x was zero, now it is one.
For those of us steeped in imperative programming, mutating state is so common that we tend not to give it a second thought. But, let's take a step back — maybe it isn't quite as natural as we think. My introduction to computer programming came from reading the manual for the BBC BASIC programming language that shipped with the BBC micro. In it, I remember seeing a statement of the form: LET X = X + 1.
It confused me. I was already familiar with equations, having been introduced to algebra at secondary school, but that statement made no sense. How could
X be equal to
X plus one? The manual, clearly written for an audience with a working knowledge of math but no experience of computing, acknowledged the weirdness. It explained that it is not an equation at all; it is an imperative statement with two sequential steps:
- Evaluate the expression on the right-hand side of the equals sign
X + 1
- Assign the result to the symbol on the left-hand side
The weirdness arises from the fact that it is permissible for the same symbol
X to be involved in both steps of the statement. Were it written like this, it would not have been weird: LET Y = X + 1
That is the same as a first-order polynomial, and it is completely unambiguous. In principle, there is no reason why you could not write programs that avoid using the same symbol on both sides of an assignment statement. In practice, for any reasonably complex program, you may end up with a lot of symbols, possibly an uncountable number. But, you would also have a program that did not mutate any state.
Why Don't we Program That way Already?
These two different approaches to programming, to mutate state or not, can be traced back to the very dawn of modern computing. In 1936, Alonzo Church published a formal system in mathematical logic for expressing computation that he called lambda calculus. Around the same time, Alan Turing created a theoretical model for devices called "turing machines" that could carry out calculations by manipulating symbols on a tape. These two ideas were subsequently brought together into a formal theory of computation known as the Church-Turing Thesis, and it laid the foundation for modern computing.
A turing machine is stateful; it holds one symbol inside the machine, which can be changed, and it can also write and overwrite symbols on the tape. By contrast, lambda calculus is a purely mathematical approach that has no concept of state. Lambda calculus was influential on one of the earliest programming languages, Lisp, but, on the whole, the imperative stateful programming style exemplified by FORTRAN has dominated. The reasons are easy to discern, mainly, processing speed and memory. Early computers had little of either. Also, the basic programming instructions of all computers right up until the present day are imperative: add these two numbers, store the result here, compare these two numbers, set a status flag, etc. The very first programs were written using this instruction set for lack of any other language to write them in. The first high-level languages, in order to be practical, were still strongly influenced in their design by the machines they ran on. It was only later that the functional programming style started to catch on.
What Makes a Language Functional?
If we agree that functional programming is programming with discipline on reassignment, this also gives us a useful definition of a functional language. Here is my definition, and you may choose to accept it or not:
A functional language makes all data immutable by default.
In a functional language, if a symbol is destined to be reassigned, it must be declared in a certain way, and the language imposes some kind of ceremony to be followed when this will occur. If a language has first-class functions or it supports lambda expressions, I don't consider those things, by themselves, a functional language. These are features typical of functional languages, but they have been added to modern imperative programming languages, as well. These features enable programming in the functional style, but it still doesn't make them functional languages per se.
To illustrate by example, C is most decidedly not a functional language. In C, everything is mutable by default, unless you explicitly make it immutable:
int mutable = 0; const int immutable = 1;
The same is true of Java and C#. By this measure, Ruby is even less functional. In Ruby, "constants" are identified by their name beginning with a capital letter, but you can still change its value. Doing so merely produces a warning.
Scala, Kotlin, and F# all sit on the fence; these languages make you choose whether a symbol is supposed to be variable, or whether its value will never change. In Scala:
val immutable : Integer = 0; var mutable : Integer = 1;
However, Kotlin has a more Java-like syntax:
val immutable = 0; var mutable = 1;
F# leans a bit more to the functional side, because all "variables" are immutable unless you say otherwise:
let x = 0 let mutable y = 1;
In all three languages, the collection types (list, map, set etc.) are immutable. Mutable versions are available on request. These languages can be considered hybrid-functional; they make the programmer decide whether they are going to write functional or imperative code.
In Clojure, the bias is much more firmly on the functional side. Sure, you can put this in your code if you want:
(def foo "foo") (def foo "bar")
But, if you make use of the symbol
foo anywhere in your program, the value will always be "bar," never "foo." The second definition supersedes the first, and your code analysis tool may flag the first definition as unused. The closest thing Clojure has to a variable assignment is
(let [foo "foo"] (do (println (str "originally: " foo)) (let [foo "bar"] (println (str "inside: " foo))) (println (str "afterwards: " foo))))
When you evaluate this form, it prints:
originally: foo inside: bar afterwards: foo
We can see that
let has not actually modified the value of foo at all; it has created a new scope in which the symbol
foo is bound to the value "bar," but, outside of that scope, it is still bound to the original value
Similarly, Clojure's collection types list, set, vector and map are all immutable. Once created, they can never be changed. If I have the following list:
(def my-list (list 1 2 3))
(cons 0 my-list) will yield a new list
(0 1 2 3), but
my-list still contains only
(1 2 3). Maps, sets, and vectors all behave similarly. If you really want to change the value of something in Clojure, you must define it as
(def foo (atom "foo"))
And, then, use
reset! to change its value. In Clojure, functions that mutate state are indicated with a ! character:
(do (println (str "was: " @foo)) (reset! foo "bar") (println (str "is now: " @foo)))
This will print the following:
was: foo is now: bar
Clojure presents a higher barrier to cross if you want to change the value of something. Not an insurmountable barrier certainly, but it makes the programmer make sure that they want to change the value of this thing. Here, I am now changing its value. Even the way you must reference the value is different. As the name atom suggests, the language guarantees atomicity when you do change it.
In Haskell, variables are only "variables" in the mathematical sense that x is a variable in the equation that defines a straight line,
y = mx + c. You may vary
x to calculate the corresponding values for
y , but this is merely a notation for describing something immutable — a straight line. You cannot mutate state in pure Haskell, when you need to do it you have to use monads (I'll explain those much later). If you compare the bubble-sort implementations in Ruby and Haskell using this blog post as an example of how to mutate state, I think you'll agree it looks simpler in the imperative language. I doubt Haskell programmers would write imperative programs in Haskell. With that said:
Haskell is, first and foremost, a functional language. Nevertheless, I think that it is also the world's most beautiful imperative language. ( Simon Peyton Jones)
So, by my definition, Haskell and Clojure are functional languages. They force the programmer to be clear about where the mutable state is, and they impose discipline on how the mutating is done. Moreover, both languages, by their design, direct the programmer away from programming in imperative statements. I may have used
do in the Clojure snippet above, but I think that is the only time I have ever used it. I will use Clojure a lot in this series of articles, but I will not use
do again. I think it unnecessary, and we will not pine for its absence.
In part one, we have discussed a fair amount about functional programming, but that only opens a whole world of questions. How do you program that way? Why would you want to? Before we can really answer the second question, we need to begin to answer the first. In the next installment, we will take our first baby steps in functional programming. In particular, we will tackle the problem of how to implement loops without mutating any state and how functional languages manage to do this while avoiding the apparent inefficiencies.
This article was first published on the Codurance blog.
Published at DZone with permission of Richard Wild, DZone MVB. See the original article here.
Opinions expressed by DZone contributors are their own.