Functional thinking: Thinking functionally, Part 1
Let's imagine for a moment that you are a woodcutter. And thanks to your best ax in the area, you are the most productive lumberjack in the camp. But one day someone appears, beginning to praise the merits of a new paradigm in the cutting of the forest - chainsaws. Due to the credibility of the seller, you buy a chainsaw, but do not know how it works. Making incredible efforts, try to pry or shake the tree, putting into practice your new paradigm. And quickly concluding that this most new-fashioned chainsaw is nonsense, returning to the usual business of cutting wood with an ax. And then someone comes and shows how to start a chainsaw.
This story may seem familiar to you by putting functional programming in place of a chainsaw. The problem with a completely new programming paradigm is not learning a new language. Moreover, the syntax of the language is just details. All the subtlety is to learn to think differently. This is why I ended up here - a chainsaw and a “functional” programmer.
So welcome to Functional thinking. This series explores the subject of functional programming, but does not have the exclusive focus to describe functional languages. As I will show later, writing code in a functional style relates to design, compromises, various reusable pieces of code and serves as the basis for other conjectures. As far as possible, I will try to show the concepts of functional programming in Java (or languages ​​close to Java) and move on to other languages ​​in order to highlight the features that are currently missing in Java. I do not immediately climb into the jungle, talking about rather unusual things, such as monads. On the contrary, I will gradually lead you through a new way of thinking.
')
This and a couple of the following parts will act as a quick tour of the subjects related to functional programming, including basic concepts. Some of these concepts will be discussed in more detail in the future, as I will gradually expand the application context throughout the series. As a starting point of our excursion, I will show you two different implementations of solving the problem. One is written in an imperative style and the other is with some functional features.
Starting a conversation about different programming styles, you need a code for comparison. As a first example, I will cite a variation of one problem, addressed 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 that is exalted in these articles, but I want to offer a rational justification for a different approach below.
The essence of the requirements is that when entering a positive number greater than 1, you need to classify it as perfect (perfect), abundant (redundant) or deficient (insufficient). Perfect is the number whose divisors (with the exception of himself, as a divider) in the amount equal to him. Similarly, the sum of the divisors of the excess is higher than itself, and the insufficient is less.
An imperative class satisfying the above requirements is presented below:
Listing 1. NumberClassifier, the imperative solution to the problem
A few points in this code that should be noted:
Using the same TDD techniques, I created an alternative 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 the classifiers is subtle, but important enough. The main difference is the deliberate deletion from the shared state code. Getting rid of it is one of the important features in functional programming. Instead of sharing the state as intermediate results between the methods (the factors field in Listing 1), I call the methods directly, which allows us to get rid of it. From a design point of view, the factors () method becomes longer, but prevents field factors from flowing outside the method. It is also worth noting that the second version may consist solely of static methods. No accumulative variables used from method to method, which allows me to get rid of the need for encapsulation through scoping . All these methods will work fine if you send a parameter of the required type to the input. (This is an example of a pure function, the concept, which I will discuss later in the next section).
Functional programming is a broad and rather actively developing area in computer science, which is causing increasing interest. There are new functional languages ​​in JVM (such as Scala or Clojure) and frameworks (Functional Java or Akka) along with statements about the occurrence of a smaller number of errors, greater productivity, better readability, larger dividends, etc. Instead of immediately covering the whole subject of functional programming, I will focus on a few key concepts, completing the narration with some interesting insights.
At the very center of functional programming, there is a function (drum sounds), as well as classes are the main abstraction in object-oriented programming (OOP). Functions form “building blocks” for processing and are imbued with certain features that are not found 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 thing we can do is use a class (usually an anonymous class) as a wrapper for the method needed to be executed. 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 used together. For example, you can get rid of all the categories of methods in a class hierarchy by building a general mechanism, bypassing lists and applying 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 to build very dynamic and adaptable systems.
Problems solved using higher order functions are not unique to functional languages. However, the approach by which you solve a problem is different when you start thinking “functionally”. Notice the example method in Listing 3 (torn from a larger piece of code) that provides secure access to the data:
Listing 3. Potentially reusable code template
The code in Listing 3 contains the initialization, does some work, completes the transaction if it succeeds, otherwise rollbacks and finally releases the resources. Of course, the template part of this code can be reused, and we, as a rule, implement this in OOP by creating a structure. In our case, I will combine the 2 Gang of Four Design Patterns patterns: the Template Method and the Command Pattern. The template method assumes that I need to move the duplicate part of the code up the inheritance hierarchy, leaving the implementation of the algorithm in the child classes. The “command” pattern allows you to encapsulate 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 rendered the common parts of the code into the wrapInTransaction () method (as you could see, the semantics of which is based on a simplified version of the TransactionTemplate in the Spring framework), passing the Command object as a piece of code for execution. The essence of the addOrderFrom () method comes down to defining an anonymous inner class ( anonymous inner class ) to create an instance of a command class, wrapping a couple of expressions.
Wrapping the desired behavior in a command class — a pure artifact of Java design that does not contain the ability to separate this behavior. All Java behavior must be placed inside a class. Even the designers of languages ​​quickly spotted a flaw in such a design - looking back, it was a little naive to think about the impossibility of the existence of behavior not tied to the class. JDK 1.1 fixed this flaw by adding anonymous inner classes that, at a minimum, add syntactic sugar to create a large number of small classes with only a few functional methods - not structural ones. As an amusing essay about this aspect in Java, I can recommend “Execution in the Kingdom of Nouns” (Steve Yegge) .
Java forces me to create an instance of the Command class, even if I only want to define one method. The class itself does not provide any advantages: it does not contain fields, the constructor (without taking the standard into account) or any state. This is only a wrapper for behavior implemented within a method. In a functional language, this is solved using a higher order function.
If I decide to leave Java for a moment, I will approach the ideal in functional programming using closures . Listing 5 shows the same refactored example, but using Groovy instead of Java:
Listing 5. Using Groovy closures instead of command classes
In Groovy, everything inside the curly braces {} are blocks of code that can be passed as parameters, simulating 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 type of Closure, which contains a call () method that is automatically executed when the parentheses () are placed after the variable that indicates the closure instance. Groovy allows you to implement some, comparable to the "functional" behavior, building the appropriate data structures, adding syntactic sugar to the language. As I will show in the following sections, Groovy also contains other functional programming capabilities that lie beyond Java. Also, in the following, 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 the functions rather unusual and pushes to think differently about potential solutions. For example, in the application of relatively common operations (with some nuances) to standard data structures. This in turn causes a fundamental shift in thinking in functional languages ​​- focusing on the result, not the intermediate steps.
In imperative programming languages, I have to think about every elementary step in an algorithm. The code in Listing 1 demonstrates this. To implement the classifier of numbers, I need to determine exactly how to collect dividers, which in turn means the need to write specific code to go through the loop to determine among the numbers of dividers. But bypassing the lists with the operation on each element seems to be quite a familiar thing. Look in Listing 6 for the redefined number classifier code using the Functional Java framework:
Listing 6. Functional number classifier
The main difference between Listings 6 and 2 are two methods: sum () and factors () . sum () takes advantage of the foldLeft () method for the List class in Functional Java. This specific type of list manipulation is called catamorphism, which is a generalization of list folding . In this case, “folding the list” means:
Notice that this is exactly what you do when you summarize the list of elements: start at 0, add the first element, get the result, add the second one and further, until you go around the entire list. Functional Java makes it possible to use a higher order function (in this example, Integers.add) and apply it for you. (Undoubtedly, in Java there are actually no higher order functions, but you can write a great analogue in case of limitations imposed by the data structure or their type.
Another intriguing method in Listing 6 is factors () , which illustrates the advice “concentrate on the result, not the intermediate steps”. What is the problem of determining the divisors of the number? In other words, given the list of all possible numbers before the considered one, how can I select from them those that are its divisors? This suggests the use of filtering operations — I can filter the complete list of numbers, excluding those that do not satisfy my criteria. Usually read: we take a range of numbers from 1 to the considered one, we filter the list with code inside the f () method, which is a way to use Functional Java to create a class with specific types and return values.
This code illustrates a much larger concept - such as the trend in programming languages ​​in general. In the past, developers had to handle a large number of annoying things, like memory allocation, garbage collection, pointers. Over time, a lot of it took languages ​​and runtime under its care. Just as computers become more and more powerful, we take out everyday, amenable to automation tasks in languages ​​and runtime environments. As a Java developer, I’m used to giving up all memory-related problems to the language. Functional programming extends these powers to cover more specific details. Over time, we spend less and less time taking care of the steps needed to solve the problem and think more in the terminology of the processes. In the continuation of the series, I will demonstrate many examples of this.
Functional programming is more of a cast of mind than a set of tools or languages. In this first part I began to describe some topics of functional programming, from simple design solutions to rethinking some ambitious problems. I rewrote a simple Java class to make it more “functional”, then began to dive into some topics that distinguish the functional programming style from the traditional - imperative.
It also reviewed two important, promising concepts. The first is to focus on the result, not the steps. Functional programming tries to present problems in a different light, because there are various “building blocks” in your hands 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 runtime environments, allowing us to focus on the unique aspects of programming problems. In the next part, I will continue to look at the basic aspects of functional programming and their use 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 by putting functional programming in place of a chainsaw. The problem with a completely new programming paradigm is not learning a new language. Moreover, the syntax of the language is just details. All the subtlety is to learn to think differently. This is why I ended up here - a chainsaw and a “functional” programmer.
So welcome to Functional thinking. This series explores the subject of functional programming, but does not have the exclusive focus to describe functional languages. As I will show later, writing code in a functional style relates to design, compromises, various reusable pieces of code and serves as the basis for other conjectures. As far as possible, I will try to show the concepts of functional programming in Java (or languages ​​close to Java) and move on to other languages ​​in order to highlight the features that are currently missing in Java. I do not immediately climb into the jungle, talking about rather unusual things, such as monads. On the contrary, I will gradually lead you through a new way of thinking.
')
This and a couple of the following parts will act as a quick tour of the subjects related to functional programming, including basic concepts. Some of these concepts will be discussed in more detail in the future, as I will gradually expand the application context throughout the series. As a starting point of our excursion, I will show you two different implementations of solving the problem. One is written in an imperative style and the other is with some functional features.
Number classifier
Starting a conversation about different programming styles, you need a code for comparison. As a first example, I will cite a variation of one problem, addressed 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 that is exalted in these articles, but I want to offer a rational justification for a different approach below.
The essence of the requirements is that when entering a positive number greater than 1, you need to classify it as perfect (perfect), abundant (redundant) or deficient (insufficient). Perfect is the number whose divisors (with the exception of himself, as a divider) in the amount equal to him. Similarly, the sum of the divisors of the excess is higher than itself, and the insufficient is less.
Imperative number classifier
An imperative class satisfying the above requirements is presented below:
Listing 1. NumberClassifier, the imperative solution to the problem
public class Classifier6 { private Set<Integer> _factors; private int _number; public Classifier6(int number) { if (number < 1) throw new InvalidNumberException( "Can't classify negative numbers"); _number = number; _factors = new HashSet<Integer>>(); _factors.add(1); _factors.add(_number); } private boolean isFactor(int factor) { return _number % factor == 0; } public Set<Integer> 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 in this code that should be noted:
- a large set of unit tests is needed (partly because I wrote it for reasoning in the TDD aspect)
- the class consists of a large number of related methods, which in this form is a side effect for use in TDD
- The performance optimization built into the calculateFactors () method. The essence of this class is the collection of dividers in order to further add them and ultimately classify them. Dividers can always be paired. For example, if the number at the input is 16, then when I define the divisor 2, I also use 8, because 2 * 8 = 16. If I collect the dividers in pairs, I just need to check for them, which are 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 alternative 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<Integer> factors(int number) { HashSet<Integer> factors = new HashSet<Integer>(); 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<Integer> 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 the classifiers is subtle, but important enough. The main difference is the deliberate deletion from the shared state code. Getting rid of it is one of the important features in functional programming. Instead of sharing the state as intermediate results between the methods (the factors field in Listing 1), I call the methods directly, which allows us to get rid of it. From a design point of view, the factors () method becomes longer, but prevents field factors from flowing outside the method. It is also worth noting that the second version may consist solely of static methods. No accumulative variables used from method to method, which allows me to get rid of the need for encapsulation through scoping . All these methods will work fine if you send a parameter of the required type to the input. (This is an example of a pure function, the concept, which I will discuss later in the next section).
Functions
Functional programming is a broad and rather actively developing area in computer science, which is causing increasing interest. There are new functional languages ​​in JVM (such as Scala or Clojure) and frameworks (Functional Java or Akka) along with statements about the occurrence of a smaller number of errors, greater productivity, better readability, larger dividends, etc. Instead of immediately covering the whole subject of functional programming, I will focus on a few key concepts, completing the narration with some interesting insights.
At the very center of functional programming, there is a function (drum sounds), as well as classes are the main abstraction in object-oriented programming (OOP). Functions form “building blocks” for processing and are imbued with certain features that are not found 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 thing we can do is use a class (usually an anonymous class) as a wrapper for the method needed to be executed. 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 used together. For example, you can get rid of all the categories of methods in a class hierarchy by building a general mechanism, bypassing lists and applying 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 to build very dynamic and adaptable systems.
Problems solved using higher order functions are not unique to functional languages. However, the approach by which you solve a problem is different when you start thinking “functionally”. Notice the example method in Listing 3 (torn from a larger piece of code) that provides secure access to the 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 the initialization, does some work, completes the transaction if it succeeds, otherwise rollbacks and finally releases the resources. Of course, the template part of this code can be reused, and we, as a rule, implement this in OOP by creating a structure. In our case, I will combine the 2 Gang of Four Design Patterns patterns: the Template Method and the Command Pattern. The template method assumes that I need to move the duplicate part of the code up the inheritance hierarchy, leaving the implementation of the algorithm in the child classes. The “command” pattern allows you to encapsulate 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 rendered the common parts of the code into the wrapInTransaction () method (as you could see, the semantics of which is based on a simplified version of the TransactionTemplate in the Spring framework), passing the Command object as a piece of code for execution. The essence of the addOrderFrom () method comes down to defining an anonymous inner class ( anonymous inner class ) to create an instance of a command class, wrapping a couple of expressions.
Wrapping the desired behavior in a command class — a pure artifact of Java design that does not contain the ability to separate this behavior. All Java behavior must be placed inside a class. Even the designers of languages ​​quickly spotted a flaw in such a design - looking back, it was a little naive to think about the impossibility of the existence of behavior not tied to the class. JDK 1.1 fixed this flaw by adding anonymous inner classes that, at a minimum, add syntactic sugar to create a large number of small classes with only a few functional methods - not structural ones. As an amusing essay about this aspect in Java, I can recommend “Execution in the Kingdom of Nouns” (Steve Yegge) .
Java forces me to create an instance of the Command class, even if I only want to define one method. The class itself does not provide any advantages: it does not contain fields, the constructor (without taking the standard into account) or any state. This is only a wrapper for behavior implemented within a method. In a functional language, this is solved using a higher order function.
If I decide to leave Java for a moment, I will approach the ideal in functional programming using closures . Listing 5 shows 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 the curly braces {} are blocks of code that can be passed as parameters, simulating 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 type of Closure, which contains a call () method that is automatically executed when the parentheses () are placed after the variable that indicates the closure instance. Groovy allows you to implement some, comparable to the "functional" behavior, building the appropriate data structures, adding syntactic sugar to the language. As I will show in the following sections, Groovy also contains other functional programming capabilities that lie beyond Java. Also, in the following, 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 the functions rather unusual and pushes to think differently about potential solutions. For example, in the application of relatively common operations (with some nuances) to standard data structures. This in turn causes a fundamental shift in thinking in functional languages ​​- focusing on the result, not the intermediate steps.
In imperative programming languages, I have to think about every elementary step in an algorithm. The code in Listing 1 demonstrates this. To implement the classifier of numbers, I need to determine exactly how to collect dividers, which in turn means the need to write specific code to go through the loop to determine among the numbers of dividers. But bypassing the lists with the operation on each element seems to be quite a familiar thing. Look in Listing 6 for the redefined 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<Integer> factors(final int number) { return range(1, number+1).filter(new F<Integer, Boolean>() { public Boolean f(final Integer i) { return number % i == 0; } }); } public int sum(List<Integer> 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 are two methods: sum () and factors () . sum () takes advantage of the foldLeft () method for the List class in Functional Java. This specific type of list manipulation is called catamorphism, which is a generalization of list folding . In this case, “folding the list” means:
- Take the initial value apply to it together with the first element of the list the specified operation.
- Get the result and apply the same operation to the following item.
- Repeat until the end of the list is reached.
Notice that this is exactly what you do when you summarize the list of elements: start at 0, add the first element, get the result, add the second one and further, until you go around the entire list. Functional Java makes it possible to use a higher order function (in this example, Integers.add) and apply it for you. (Undoubtedly, in Java there are actually no higher order functions, but you can write a great analogue in case of limitations imposed by the data structure or their type.
Another intriguing method in Listing 6 is factors () , which illustrates the advice “concentrate on the result, not the intermediate steps”. What is the problem of determining the divisors of the number? In other words, given the list of all possible numbers before the considered one, how can I select from them those that are its divisors? This suggests the use of filtering operations — I can filter the complete list of numbers, excluding those that do not satisfy my criteria. Usually read: we take a range of numbers from 1 to the considered one, we filter the list with code inside the f () method, which is a way to use Functional Java to create a class with specific types and return values.
This code illustrates a much larger concept - such as the trend in programming languages ​​in general. In the past, developers had to handle a large number of annoying things, like memory allocation, garbage collection, pointers. Over time, a lot of it took languages ​​and runtime under its care. Just as computers become more and more powerful, we take out everyday, amenable to automation tasks in languages ​​and runtime environments. As a Java developer, I’m used to giving up all memory-related problems to the language. Functional programming extends these powers to cover more specific details. Over time, we spend less and less time taking care of the steps needed to solve the problem and think more in the terminology of the processes. In the continuation of the series, I will demonstrate many examples of this.
Conclusion
Functional programming is more of a cast of mind than a set of tools or languages. In this first part I began to describe some topics of functional programming, from simple design solutions to rethinking some ambitious problems. I rewrote a simple Java class to make it more “functional”, then began to dive into some topics that distinguish the functional programming style from the traditional - imperative.
It also reviewed two important, promising concepts. The first is to focus on the result, not the steps. Functional programming tries to present problems in a different light, because there are various “building blocks” in your hands 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 runtime environments, allowing us to focus on the unique aspects of programming problems. In the next part, I will continue to look at the basic aspects of functional programming and their use in software development today.
PS Many thanks to CheatEx for reviewing the translation. Most likely, to be continued ...
Source: https://habr.com/ru/post/128063/
All Articles