September 9, 2011 at 08:07Functional thinking: Thinking functionally, Part 1
- Transfer
Let's imagine for a moment that you are a lumberjack. And thanks to your best ax in the area, you are the most productive woodcutter in the camp. But once someone appears, beginning to extol the virtues of a new paradigm in the cutting of forests - chainsaws. Due to the seller’s persuasiveness, you buy a chainsaw, but don’t know how it works. When you make incredible efforts, you try to tear or rock the tree, applying in practice your new paradigm. And quickly concluding that this very newfangled chainsaw is nonsense, you return to the usual thing - to cut down the forest with an ax. And then someone comes and shows how to start a chainsaw.
This story may seem familiar to you, putting functional programming in place of the chainsaw. The problem is a completely new programming paradigm - not learning a new language. Moreover, the language syntax is just the details. The whole subtlety is to learn to think differently. This is why I ended up here - a chainsaw engine and a “functional” programmer.
So welcome to Functional thinking. This series explores the subject of functional programming, but does not carry the exclusive thrust of describing functional languages. As I will show later, writing code in a functional style concerns design, compromises, various reusable pieces of code, and serves as the basis for other conjectures. To the extent possible, I will try to show the concepts of functional programming in Java (or languages close to Java) and move on to other languages to highlight the possibilities that are currently not available in Java. I do not just climb into the jungle, talking about rather unusual things such as monads ( monads ). On the contrary, I will gradually lead you through a new way of thinking.
This and a couple of the following parts will serve as a quick tour of subjects related to functional programming, including basic concepts. Some of these concepts will be discussed in more detail below, while I will gradually expand the application context throughout the series. As a starting point for our tour, I will show you two different implementations of the solution to the problem. One is written in an imperative style and the other with some functional features.
Starting a conversation about different styles of programming, you need code to compare. As a first example, I will give a variation of one problem, which is discussed in my book The Productive Programmer , as well as the first and second parts of Test-driven design . At a minimum, I chose this code because in these two publications it is considered quite deeply. There is nothing wrong with the design extolled in these articles, but I want to offer below a reasonable justification for a different approach.
The essence of the requirements is that when a positive number is greater than 1 at the input, you need to classify it as perfect (perfect), abundant (excess) or deficient(insufficient). Perfect is the number whose divisors (with the exception of himself, as a divisor) are equal to him in total. Similarly, the sum of the divisors of an excess number is higher than himself, and an insufficient number is less.
An imperative class that satisfies the above requirements is presented below:
Listing 1. NumberClassifier, the imperative solution to the problem
A few points to note in this code:
Using the same TDD techniques, I created an alternate version of the classifier, which you can see in Listing 2:
Listing 2. Slightly more functional number classifier
The difference between the two versions of classifiers is barely perceptible, but quite important. The main difference - is informed of the removal code shared state ( shared state ). Getting rid of it is one of the important features in functional programming. Instead of dividing the state as intermediate results between methods (the factors field in Listing 1), I call the methods directly, which allows me to get rid of it. From a design point of view, the factors () method becomes longer, but prevents the factors field from leaking out of the method. It is also worth noting that the second version may consist solely of static methods. No accumulating variables used from method to method, which allows me to get rid of the need for encapsulation through scope (scoping ). All these methods will work fine if you send a parameter of the required type to the input. (This is an example of pure function ( pure function ), kotseptsii, which I will discuss later in the next section).
Functional programming is a broad and fairly rapidly developing field in computer science, which causes an increasing interest. There are new functional languages in the JVM (such as Scala or Clojure) and frameworks (Functional Java or Akka) along with statements about the occurrence of fewer errors, greater productivity, better readability, greater dividends, etc. Instead of immediately covering the whole subject of functional programming, I will focus on several key concepts, completing the story with some interesting conclusions.
At the very center of functional programming is a function (drum roll sounds), just like classes, they are the main abstraction in object-oriented programming (OOP). Functions form the “building blocks” for processing and are imbued with some features that are absent in traditional imperative languages.
Higher-order functions can use other functions as arguments as well as return them as a result. We do not have such a construction in Java. The closest we can do is use a class (usually an anonymous class) as a wrapper for the method needed to execute. There are no standalone functions (or methods) in Java , so they cannot be returned by others or passed as parameters.
This feature is important in functional languages for at least two reasons. First, the ability to use higher order functions allows you to make an assumption about how parts of the language are shared. For example, you can get rid of all categories of methods in a class hierarchy by building a common mechanism that bypasses lists and applies one or more higher-order functions for each element. (I will soon demonstrate an example of such a construction.) Secondly, with the ability to use functions as return values, you create an excellent opportunity for building very dynamic and adaptable systems.
The problems solved by using higher-order functions are not unique to functional languages. However, the approach by which you solve the problem is different when you start to think “functionally”. Notice the example method in Listing 3 (torn from a larger piece of code) that provides secure access to data:
Listing 3. Potentially reusable code template
The code in Listing 3 contains initialization, performs some work, completes the transaction if successful, or rolls back ( rollback ) and finally produces the release of resources. Of course, the template part of this code can be reused, and we usually implement this in OOP by creating a structure. In our case, I will combine 2 “ Gang of Four Design Patterns ” patterns : the Template Method and the Command pattern) The template method assumes that I need to move the repeating piece of code up the inheritance hierarchy, leaving the implementation of the algorithm in child classes. The “Command” pattern allows encapsulating behavior in a class with well-known execution semantics. Listing 4 shows the result of applying these two patterns to the code in Listing 3:
Listing 4. Refactored order code
In Listing 4, I pulled out the general parts of the code into the wrapInTransaction () method (as you could see, the semantics of which are based on a simplified version of the TransactionTemplate in the Spring framework), passing the Command object as a piece of code to execute. The essence of the addOrderFrom () method comes down to defining an anonymous inner class to create an instance of the command class by wrapping a couple of expressions.
Wrapping the desired behavior in a team class is pure Java artifact design that does not contain the ability to separate this behavior. All behavior in Java must be placed inside the class. Even language designers quickly spotted a flaw in such a design - looking back into the past, it’s a bit naive to think about the impossibility of existence of behavior that is not tied to the class. JDK 1.1 fixed this flaw by adding anonymous inner classes, which at least add syntactic sugar to create a large number of small classes with just a few functional methods - not structural ones. As an interesting essay about this aspect in Java, I can recommend “Execution in the Kingdom of Nouns” (Steve Yegge) .
Java forces me to instantiate the Command class, even if I just want to define one method. The class itself does not provide any advantages: it does not contain fields, the constructor (not taking into account the standard one), or any state. This is just a wrapper for the behavior implemented inside the method. In a functional language, this is solved by using a higher order function.
If I decide to leave Java for the moment, I’ll get closer to the ideal in functional programming using closures . Listing 5 demonstrates the same refactored example, but using Groovy instead of Java:
Listing 5. Using Groovy closures instead of command classes
In Groovy, everything inside curly braces {} is blocks of code that can be passed as parameters, mimicking higher-order functions. Behind the scenes, Groovy implements the Team pattern for you. Each closure block in Groovy is actually an instance of a special Closure type that contains the call () method, automatically executed at the time of placing parentheses () after the variable indicating the instance of the closure. Groovy allows you to implement some, comparable to “functional”, behavior, building appropriate data structures, adding syntactic sugar to the language. As I will show in the following parts, Groovy also contains other functional programming features that lie outside the boundaries of Java. Also in the future I will come back for some interesting comparison of closures and higher-order functions.
Functions in a functional language are treated as objects of the first class, which means that functions can appear wherever possible using any other language construct (such as variables). Their presence allows you to use functions quite unusual and encourages you to think differently about potential solutions. For example, in the application of relatively general operations (with some nuances) to standard data structures. This in turn causes a fundamental shift in thinking in functional languages - focusing on the result rather than the intermediate steps.
In imperative programming languages, I have to think about every elementary step in the algorithm. The code in Listing 1 demonstrates this. To implement the classifier of numbers, I need to determine exactly how to collect the divisors, which in turn means the need to write specific code in order to go through a cycle to determine among the numbers of divisors. But crawling lists with operations on each item seems like a pretty common thing. In Listing 6, look at the overridden number classifier code using the Functional Java framework:
Listing 6. Functional number classifier
The main difference between Listings 6 and 2 is two methods: sum () and factors () . sum () takes advantage of the foldLeft () method with respect to the List class in Functional Java. This specific kind of manipulation with lists is called catamorphism ( catamorphism ), which is a generalization for the clotting of lists ( list folding ). In this case, “folding the list” means:
Note that this is exactly what you do when you summarize the list of elements: start at 0, add the first element to get the result, add the second and further until you go around the whole list. Functional Java makes it possible to use a higher-order function (Integers.add in this example) and uses it for you. (Undoubtedly, Java doesn’t actually have higher-order functions, but you can write a great analogue in the case of restrictions imposed by the data structure or type.
Another intriguing method in Listing 6 is factors (), which illustrates the advice “focus on the result, not the intermediate steps”. What is the essence of the problem of determining number divisors? In other words, given the list of all possible numbers up to the one under consideration, how can I distinguish from them those that are its divisors? This suggests the use of a filtering operation - I can filter out a complete list of numbers, excluding those that do not meet my criteria. Usually it reads: we take a range of numbers from 1 to the one in question, filter the list with code inside the f () method , which is a way in Functional Java that allows you to create a class with specific types and return values.
This code illustrates a much larger concept - such as a trend in programming languages in general. In the past, developers had to handle a lot of annoying things like memory allocation, garbage collection, pointers. Over time, many of these languages and runtimes have taken care of themselves. Just as computers become more and more powerful, we take out routine tasks that can be automated into languages and runtimes. As a Java developer, I’m used to succumbing to the language for all memory issues. Functional programming extends these powers to include more specific details. Over time, we spend less and less time caring for the steps necessary to solve the problem and think more in the terminology of the processes. Throughout the series, I will demonstrate many examples of this.
Functional programming is more a mindset than a set of tools or languages. In this first part, I began to describe some of the topics of functional programming, from simple design decisions to rethinking some ambitious problems. I rewrote a simple Java class to make it more “functional,” then I began to dive into some topics that distinguish a functional programming style from a traditional, imperative one.
Two important, promising concepts were also considered here. First, concentrate on the result, not the steps. Functional programming tries to present problems in a different light, because in your hands there are various “building blocks” that help you find solutions. The second trend that I will show throughout the series is the delegation of simple things to programming languages and runtimes, which allows us to focus on the unique aspects of programming problems. In the next part, I will continue to consider the basic aspects of functional programming and their application in software development today.
PS Many thanks to CheatEx for reviewing the translation. Most likely, to be continued ...
This story may seem familiar to you, putting functional programming in place of the chainsaw. The problem is a completely new programming paradigm - not learning a new language. Moreover, the language syntax is just the details. The whole subtlety is to learn to think differently. This is why I ended up here - a chainsaw engine and a “functional” programmer.
So welcome to Functional thinking. This series explores the subject of functional programming, but does not carry the exclusive thrust of describing functional languages. As I will show later, writing code in a functional style concerns design, compromises, various reusable pieces of code, and serves as the basis for other conjectures. To the extent possible, I will try to show the concepts of functional programming in Java (or languages close to Java) and move on to other languages to highlight the possibilities that are currently not available in Java. I do not just climb into the jungle, talking about rather unusual things such as monads ( monads ). On the contrary, I will gradually lead you through a new way of thinking.
This and a couple of the following parts will serve as a quick tour of subjects related to functional programming, including basic concepts. Some of these concepts will be discussed in more detail below, while I will gradually expand the application context throughout the series. As a starting point for our tour, I will show you two different implementations of the solution to the problem. One is written in an imperative style and the other with some functional features.
Number classifier
Starting a conversation about different styles of programming, you need code to compare. As a first example, I will give a variation of one problem, which is discussed in my book The Productive Programmer , as well as the first and second parts of Test-driven design . At a minimum, I chose this code because in these two publications it is considered quite deeply. There is nothing wrong with the design extolled in these articles, but I want to offer below a reasonable justification for a different approach.
The essence of the requirements is that when a positive number is greater than 1 at the input, you need to classify it as perfect (perfect), abundant (excess) or deficient(insufficient). Perfect is the number whose divisors (with the exception of himself, as a divisor) are equal to him in total. Similarly, the sum of the divisors of an excess number is higher than himself, and an insufficient number is less.
Imperative number classifier
An imperative class that satisfies the above requirements is presented below:
Listing 1. NumberClassifier, the imperative solution to the problem
public class Classifier6 {
private Set _factors;
private int _number;
public Classifier6(int number) {
if (number < 1)
throw new InvalidNumberException(
"Can't classify negative numbers");
_number = number;
_factors = new HashSet>();
_factors.add(1);
_factors.add(_number);
}
private boolean isFactor(int factor) {
return _number % factor == 0;
}
public Set getFactors() {
return _factors;
}
private void calculateFactors() {
for (int i = 1; i <= sqrt(_number) + 1; i++)
if (isFactor(i))
addFactor(i);
}
private void addFactor(int factor) {
_factors.add(factor);
_factors.add(_number / factor);
}
private int sumOfFactors() {
calculateFactors();
int sum = 0;
for (int i : _factors)
sum += i;
return sum;
}
public boolean isPerfect() {
return sumOfFactors() - _number == _number;
}
public boolean isAbundant() {
return sumOfFactors() - _number > _number;
}
public boolean isDeficient() {
return sumOfFactors() - _number < _number;
}
public static boolean isPerfect(int number) {
return new Classifier6(number).isPerfect();
}
}
A few points to note in this code:
- a large set of Unit tests is needed (partly due to the fact that I wrote it for discussion in the TDD aspect)
- class consists of a large number of related methods, which as such is a side effect ( side effect ) for use in a TDD
- performance optimization built into calculateFactors () method . The essence of this class is the collection of divisors in order to add them together and eventually classify them. Divisors can always be paired. For example, if the input number is 16, then when I determine the divisor 2, I also use 8, since 2 * 8 = 16. If I collect the divisors in pairs, I just need to check on them that make up the square root of the number in question, which is exactly what the calculateFactors () method does .
(Slightly more) functional classifier
Using the same TDD techniques, I created an alternate version of the classifier, which you can see in Listing 2:
Listing 2. Slightly more functional number classifier
public class NumberClassifier {
static public boolean isFactor(int number, int potential_factor) {
return number % potential_factor == 0;
}
static public Set factors(int number) {
HashSet factors = new HashSet();
for (int i = 1; i <= sqrt(number); i++)
if (isFactor(number, i)) {
factors.add(i);
factors.add(number / i);
}
return factors;
}
static public int sum(Set factors) {
Iterator it = factors.iterator();
int sum = 0;
while (it.hasNext())
sum += (Integer) it.next();
return sum;
}
static public boolean isPerfect(int number) {
return sum(factors(number)) - number == number;
}
static public boolean isAbundant(int number) {
return sum(factors(number)) - number > number;
}
static public boolean isDeficient(int number) {
return sum(factors(number)) - number < number;
}
}
The difference between the two versions of classifiers is barely perceptible, but quite important. The main difference - is informed of the removal code shared state ( shared state ). Getting rid of it is one of the important features in functional programming. Instead of dividing the state as intermediate results between methods (the factors field in Listing 1), I call the methods directly, which allows me to get rid of it. From a design point of view, the factors () method becomes longer, but prevents the factors field from leaking out of the method. It is also worth noting that the second version may consist solely of static methods. No accumulating variables used from method to method, which allows me to get rid of the need for encapsulation through scope (scoping ). All these methods will work fine if you send a parameter of the required type to the input. (This is an example of pure function ( pure function ), kotseptsii, which I will discuss later in the next section).
Functions
Functional programming is a broad and fairly rapidly developing field in computer science, which causes an increasing interest. There are new functional languages in the JVM (such as Scala or Clojure) and frameworks (Functional Java or Akka) along with statements about the occurrence of fewer errors, greater productivity, better readability, greater dividends, etc. Instead of immediately covering the whole subject of functional programming, I will focus on several key concepts, completing the story with some interesting conclusions.
At the very center of functional programming is a function (drum roll sounds), just like classes, they are the main abstraction in object-oriented programming (OOP). Functions form the “building blocks” for processing and are imbued with some features that are absent in traditional imperative languages.
Higher-order functions
Higher-order functions can use other functions as arguments as well as return them as a result. We do not have such a construction in Java. The closest we can do is use a class (usually an anonymous class) as a wrapper for the method needed to execute. There are no standalone functions (or methods) in Java , so they cannot be returned by others or passed as parameters.
This feature is important in functional languages for at least two reasons. First, the ability to use higher order functions allows you to make an assumption about how parts of the language are shared. For example, you can get rid of all categories of methods in a class hierarchy by building a common mechanism that bypasses lists and applies one or more higher-order functions for each element. (I will soon demonstrate an example of such a construction.) Secondly, with the ability to use functions as return values, you create an excellent opportunity for building very dynamic and adaptable systems.
The problems solved by using higher-order functions are not unique to functional languages. However, the approach by which you solve the problem is different when you start to think “functionally”. Notice the example method in Listing 3 (torn from a larger piece of code) that provides secure access to data:
Listing 3. Potentially reusable code template
public void addOrderFrom(ShoppingCart cart, String userName,
Order order) throws Exception {
setupDataInfrastructure();
try {
add(order, userKeyBasedOn(userName));
addLineItemsFrom(cart, order.getOrderKey());
completeTransaction();
} catch (Exception condition) {
rollbackTransaction();
throw condition;
} finally {
cleanUp();
}
}
The code in Listing 3 contains initialization, performs some work, completes the transaction if successful, or rolls back ( rollback ) and finally produces the release of resources. Of course, the template part of this code can be reused, and we usually implement this in OOP by creating a structure. In our case, I will combine 2 “ Gang of Four Design Patterns ” patterns : the Template Method and the Command pattern) The template method assumes that I need to move the repeating piece of code up the inheritance hierarchy, leaving the implementation of the algorithm in child classes. The “Command” pattern allows encapsulating behavior in a class with well-known execution semantics. Listing 4 shows the result of applying these two patterns to the code in Listing 3:
Listing 4. Refactored order code
public void wrapInTransaction(Command c) throws Exception {
setupDataInfrastructure();
try {
c.execute();
completeTransaction();
} catch (Exception condition) {
rollbackTransaction();
throw condition;
} finally {
cleanUp();
}
}
public void addOrderFrom(final ShoppingCart cart, final String userName,
final Order order) throws Exception {
wrapInTransaction(new Command() {
public void execute() {
add(order, userKeyBasedOn(userName));
addLineItemsFrom(cart, order.getOrderKey());
}
});
}
In Listing 4, I pulled out the general parts of the code into the wrapInTransaction () method (as you could see, the semantics of which are based on a simplified version of the TransactionTemplate in the Spring framework), passing the Command object as a piece of code to execute. The essence of the addOrderFrom () method comes down to defining an anonymous inner class to create an instance of the command class by wrapping a couple of expressions.
Wrapping the desired behavior in a team class is pure Java artifact design that does not contain the ability to separate this behavior. All behavior in Java must be placed inside the class. Even language designers quickly spotted a flaw in such a design - looking back into the past, it’s a bit naive to think about the impossibility of existence of behavior that is not tied to the class. JDK 1.1 fixed this flaw by adding anonymous inner classes, which at least add syntactic sugar to create a large number of small classes with just a few functional methods - not structural ones. As an interesting essay about this aspect in Java, I can recommend “Execution in the Kingdom of Nouns” (Steve Yegge) .
Java forces me to instantiate the Command class, even if I just want to define one method. The class itself does not provide any advantages: it does not contain fields, the constructor (not taking into account the standard one), or any state. This is just a wrapper for the behavior implemented inside the method. In a functional language, this is solved by using a higher order function.
If I decide to leave Java for the moment, I’ll get closer to the ideal in functional programming using closures . Listing 5 demonstrates the same refactored example, but using Groovy instead of Java:
Listing 5. Using Groovy closures instead of command classes
def wrapInTransaction(command) {
setupDataInfrastructure()
try {
command()
completeTransaction()
} catch (Exception ex) {
rollbackTransaction()
throw ex
} finally {
cleanUp()
}
}
def addOrderFrom(cart, userName, order) {
wrapInTransaction {
add order, userKeyBasedOn(userName)
addLineItemsFrom cart, order.getOrderKey()
}
}
In Groovy, everything inside curly braces {} is blocks of code that can be passed as parameters, mimicking higher-order functions. Behind the scenes, Groovy implements the Team pattern for you. Each closure block in Groovy is actually an instance of a special Closure type that contains the call () method, automatically executed at the time of placing parentheses () after the variable indicating the instance of the closure. Groovy allows you to implement some, comparable to “functional”, behavior, building appropriate data structures, adding syntactic sugar to the language. As I will show in the following parts, Groovy also contains other functional programming features that lie outside the boundaries of Java. Also in the future I will come back for some interesting comparison of closures and higher-order functions.
First-class functions
Functions in a functional language are treated as objects of the first class, which means that functions can appear wherever possible using any other language construct (such as variables). Their presence allows you to use functions quite unusual and encourages you to think differently about potential solutions. For example, in the application of relatively general operations (with some nuances) to standard data structures. This in turn causes a fundamental shift in thinking in functional languages - focusing on the result rather than the intermediate steps.
In imperative programming languages, I have to think about every elementary step in the algorithm. The code in Listing 1 demonstrates this. To implement the classifier of numbers, I need to determine exactly how to collect the divisors, which in turn means the need to write specific code in order to go through a cycle to determine among the numbers of divisors. But crawling lists with operations on each item seems like a pretty common thing. In Listing 6, look at the overridden number classifier code using the Functional Java framework:
Listing 6. Functional number classifier
public class FNumberClassifier {
public boolean isFactor(int number, int potential_factor) {
return number % potential_factor == 0;
}
public List factors(final int number) {
return range(1, number+1).filter(new F() {
public Boolean f(final Integer i) {
return number % i == 0;
}
});
}
public int sum(List factors) {
return factors.foldLeft(fj.function.Integers.add, 0);
}
public boolean isPerfect(int number) {
return sum(factors(number)) - number == number;
}
public boolean isAbundant(int number) {
return sum(factors(number)) - number > number;
}
public boolean isDeficiend(int number) {
return sum(factors(number)) - number < number;
}
}
The main difference between Listings 6 and 2 is two methods: sum () and factors () . sum () takes advantage of the foldLeft () method with respect to the List class in Functional Java. This specific kind of manipulation with lists is called catamorphism ( catamorphism ), which is a generalization for the clotting of lists ( list folding ). In this case, “folding the list” means:
- Take the initial value, apply the specified operation to it paired with the first element of the list
- Get the result and apply the same operation to together with the next element
- Repeat until the end of the list is reached.
Note that this is exactly what you do when you summarize the list of elements: start at 0, add the first element to get the result, add the second and further until you go around the whole list. Functional Java makes it possible to use a higher-order function (Integers.add in this example) and uses it for you. (Undoubtedly, Java doesn’t actually have higher-order functions, but you can write a great analogue in the case of restrictions imposed by the data structure or type.
Another intriguing method in Listing 6 is factors (), which illustrates the advice “focus on the result, not the intermediate steps”. What is the essence of the problem of determining number divisors? In other words, given the list of all possible numbers up to the one under consideration, how can I distinguish from them those that are its divisors? This suggests the use of a filtering operation - I can filter out a complete list of numbers, excluding those that do not meet my criteria. Usually it reads: we take a range of numbers from 1 to the one in question, filter the list with code inside the f () method , which is a way in Functional Java that allows you to create a class with specific types and return values.
This code illustrates a much larger concept - such as a trend in programming languages in general. In the past, developers had to handle a lot of annoying things like memory allocation, garbage collection, pointers. Over time, many of these languages and runtimes have taken care of themselves. Just as computers become more and more powerful, we take out routine tasks that can be automated into languages and runtimes. As a Java developer, I’m used to succumbing to the language for all memory issues. Functional programming extends these powers to include more specific details. Over time, we spend less and less time caring for the steps necessary to solve the problem and think more in the terminology of the processes. Throughout the series, I will demonstrate many examples of this.
Conclusion
Functional programming is more a mindset than a set of tools or languages. In this first part, I began to describe some of the topics of functional programming, from simple design decisions to rethinking some ambitious problems. I rewrote a simple Java class to make it more “functional,” then I began to dive into some topics that distinguish a functional programming style from a traditional, imperative one.
Two important, promising concepts were also considered here. First, concentrate on the result, not the steps. Functional programming tries to present problems in a different light, because in your hands there are various “building blocks” that help you find solutions. The second trend that I will show throughout the series is the delegation of simple things to programming languages and runtimes, which allows us to focus on the unique aspects of programming problems. In the next part, I will continue to consider the basic aspects of functional programming and their application in software development today.
PS Many thanks to CheatEx for reviewing the translation. Most likely, to be continued ...