Functional thinking: Thinking functionally, Part 2

In the first part of the series, I began a discussion of some features of functional programming, showing the manifestations of these ideas in Java and other more functional languages. In this article I will continue my review, paying attention to the functions - first-class objects, optimization and closure. But the main topic of this article is control: when you want it, when you need it and when you just need to score.

First-class functions and control

Using the Functional Java library, last time I demonstrated the implementation of a number classifier with the isFactor () and factorsOf () methods written in functional style, as shown in Listing 1:

Listing 1. Functional version of the number classifier

import fj.F; import fj.data.List; import static fj.data.List.range; import static fj.function.Integers.add; import static java.lang.Math.round; import static java.lang.Math.sqrt; public class FNumberClassifier { public boolean isFactor(int number, int potential_factor) { return number % potential_factor == 0; } public List<Integer> factorsOf(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(factorsOf(number)) - number == number; } public boolean isAbundant(int number) { return sum(factorsOf(number)) - number > number; } public boolean isDeficiend(int number) { return sum(factorsOf(number)) - number < number; } } 

In the isFactor() and factorOf() methods, I delegated the traversal algorithm to the framework, which itself decides how best to bypass the range of numbers. If the framework (or the language itself, if you use for example the functional languages ​​Clojure and Scala) is able to optimize the underlying implementation, then you automatically benefit from it. And although at first you will not want to shift this functionality onto other people's shoulders, still note that this follows a basic trend in programming languages ​​and environments. Over time, the developer is increasingly abstracting from parts that the platform can handle more efficiently. I never care about memory management in the JVM, because the platform allows me to forget about it. Of course, at times, this makes some things more complicated, but it’s a good compromise for the benefits you get in everyday writing. Constructions of a functional language, such as: higher-order functions and functions — objects, allow me to rise one more step higher in the abstraction ladder and focus on what the code should do, and not how it should do it.

Even with the Functional Java framework, programming in this style in Java looks awkward, because the language doesn't actually have the necessary syntax and constructs. How is the functional approach implemented in the languages ​​meant for it?
')

Classifier in Clojure

Clojure is a functional Lisp designed for the JVM. Take a look at the Clojure number classifier - Listing 2

Listing 2. Clojure implementation of the number classifier

 (ns nealford.perfectnumbers) (use '[clojure.contrib.import-static :only (import-static)]) (import-static java.lang.Math sqrt) (defn is-factor? [factor number] (= 0 (rem number factor))) (defn factors [number] (set (for [n (range 1 (inc number)) :when (is-factor? n number)] n))) (defn sum-factors [number] (reduce + (factors number))) (defn perfect? [number] (= number (- (sum-factors number) number))) (defn abundant? [number] (< number (- (sum-factors number) number))) (defn deficient? [number] (> number (- (sum-factors number) number))) 

The best part of Listing 2 is simple enough to understand, even if you are not a harsh Lisp developer, and especially if you can learn to read inside out. For example, the is-factor? method is-factor? It accepts two parameters and checks for equality to zero of the remainder of the division after multiplying the number by factor. Like this perfect? methods perfect? , abundunt? and deficient? should also be easy to understand, especially if you look at Listing 1 with a Java implementation.

The sum-factor method uses the built-in reduce method. sum-factor reduces the list by one element, using the function (in this case, +), taken by the first parameter above each element. The reduce method is represented in various forms in individual programming languages ​​and frameworks. In Listing 1, you saw it as foldLeft() . The factors method returns a list of numbers, so I process elements by element, making up the sum returned from the reduce method from numbers. You can see that once you get used to thinking in terms of higher order functions and functions — first class objects — you can get rid of a lot of noise in your code.

The factors() method may seem like a bunch of random characters. But it can immediately be understood if you once saw list conversions (lists comprehensions ) being one of several powerful features of Clojure. As before, it is easiest to understand the factors method from the inside out. Do not be confused by the terminating language terminology. Clojure's for keyword does not imply a for loop. Think rather of this as the ancestor of all filtering and transforming structures. In this case, I call it to filter the range of numbers from 1 to (number + 1) using the is-factor? predicate is-factor? that returns numbers that satisfy the condition. The output of this operation is a list of numbers that satisfy my criterion, which I transform into a set (set) to remove repetitions.

You get a lot of really cool things from functional languages ​​with an understanding of their specifics and features, despite the initial difficulties in learning.

Optimization

One of the advantages of moving to a functional style is the ability to use higher-order functions provided by a language or framework. But what if you don’t want to give up this control? In my earlier example, I compared the internal behavior of the iterative mechanism with the work of the memory manager: most of the time, it's easier for you not to worry about these details. But sometimes you care about it, as is the case with optimization and others like it.

In the two Java versions of the number classifier, which I showed in the first part, I optimized the code that defines the divisors. The initial simple implementation used a modulus operator (%), which is wildly inefficient to check all numbers from 2 to a given number to check if it is a divisor. You can optimize this algorithm by noting that dividers are always found in pairs. For example, if you are looking for dividers 28, then when you find 2, you can also take and 14. If you collect dividers in pairs, you only need to check numbers down to the square root of a given number.

Optimization that was easy to do in the Java version seems impossible in Functional Java due to the fact that I do not directly control iteration. However, the path to functional thinking requires us to abandon this type of control, allowing us to master others.

I can reformulate the original problem in a functional style: filter all dividers from 1 to a given number, leaving only those that satisfy the isFactor predicate. This is done in Listing 3:

Listing 3. The isFactor () method

 public List<Integer> factorsOf(final int number) { return range(1, number+1).filter(new F<Integer, Boolean>() { public Boolean f(final Integer i) { return number % i == 0; } }); } 

Despite its elegance, the code in Listing 3 is not very efficient as it checks every number. However, by understanding the optimization (to collect dividers in pairs from 1 to square root), I can reformulate the problem:

1. Filter all numbers from 1 to the square root of the given number.
2. Divide the given number into each of these divisors to get a pair divider and add it to the list of divisors.

With this algorithm, I can write an optimized version of the factorsOf () method using the Functional Java library, as shown in Listing 4:

Listing 4. Optimized factors-finding method

 public List<Integer> factorsOfOptimzied(final int number) { List<Integer> factors = range(1, (int) round(sqrt(number)+1)) .filter(new F<Integer, Boolean>() { public Boolean f(final Integer i) { return number % i == 0; }}); return factors.append(factors.map(new F<Integer, Integer>() { public Integer f(final Integer i) { return number / i; }})) .nub(); } 

The code in Listing 4 is based on the algorithm described earlier, with a slightly corrupted syntax required by the Functional Java library. First, I take a range of numbers starting from 1 to the square root of a given number plus 1 (to be sure that I will get all dividers). Then, as well as in the previous version, I filter the result using the module operator wrapped in a code block. I save this filtered result in the factors variable. Further (if to read from within) I take this list of dividers and execute the map() function, which creates a new list, executing my block of code for each element (mapping each element to a new value). My divisor list contains all divisors of a given number less than the square root; now I have to divide the given number into each of them in order to get a list of symmetric dividers and connect it with the original list. In the last step, I must take into account that I keep the dividers in the list, and not in the set. The list methods are convenient for manipulations that were performed earlier, but my algorithm has a side effect: one element is repeated twice if a square root appears among the dividers. For example, if the number is 16, the square root of 4 appears in the list of dividers twice. In order to continue using the convenient list methods, I must call the nub() method at the end to remove all repetitions.

The fact that you give up the knowledge of implementation details when using high-level abstractions like functional programming does not mean that you cannot go back to the little things when necessary. Java basically protects you from low-level problems, but if you decide you need it, you can go down to the right level. Also in functional programming - usually the details are easily left on the conscience of abstractions, except for the moments when they turn out to be really important.

In all the code that I have cited above, the block syntax visually dominates, which uses generalizations and anonymous nested classes as pseudo blocks of code. Closures are one of the most common features of functional languages. What makes them so useful in a functional world?

What's so special about closures?

A closure is a function that stores implicit references to the variables it references. In other words, a function (or method) that captures and preserves the context surrounding it *. Closures are used quite often as a portable execution engine in functional languages ​​and frameworks that are passed to higher-order functions, for example, in map () for transformation. Functional Java uses anonymous inner classes to simulate some behavior of “real” closures, but they are not able to provide the full functionality of the latter, because Java does not support closures. What does this mean?

Listing 5 shows an example of what makes closures special. It is written in Groovy, a language that supports closures directly.

Listing 5. Groovy code illustrating closures

 def makeCounter() { def very_local_variable = 0 return { return very_local_variable += 1 } } c1 = makeCounter() c1() c1() c1() c2 = makeCounter() println "C1 = ${c1()}, C2 = ${c2()}" // output: C1 = 4, C2 = 1 

The makeCouner() method defines a local variable with the appropriate name, and then returns a block of code that uses this variable. Notice that the makeCounter() method returns a block of code, not a value. This code does nothing except increase the value of a local variable by 1 and return it. I explicitly indicated a call to return in this code, which is actually optional in Groovy, but the code without it may seem less clear.

To show the makeCounter() method in action, I assigned a reference to the block to the variable c1 , then called it 3 times. I use Groovy syntax sugar to execute a block of code, consisting in placing parentheses after the variable. Then I call makeCounter() again, assigning a new instance of the code block to the variable C2 . Finally, I run C1 again with C2 . Note that each code block refers to a separate instance of the very_local_variable variable. This is exactly what I had in mind when talking about context capture. Despite the seeming locality of defining a variable inside a method, the closure is still associated with it and stores the state. "

The largest approximation to this behavior implemented in Java is shown in Listing 6:

Listing 6. MakeCounter in Java

 public class Counter { private int varField; public Counter(int var) { varField = var; } public static Counter makeCounter() { return new Counter(0); } public int execute() { return ++varField; } } 

There may be several options for the class Counter, but you still have to face the independent state management. This shows why the use of closures contributes to functional thinking: it allows the environment to control the state. Instead of forcing you to control the creation of fields and monitor the state (including the terrifying prospect of using such code in a multithreaded environment), it allows the language or framework to do the work for you.

In the end, we will still have closures in the next Java releases (which, fortunately, is beyond the scope of this article). The appearance of closures in Java will bring a couple of expected results. Firstly, it will greatly simplify the life of the authors of libraries and frameworks in the work on improving their syntax. Second, it will provide a low-level “common denominator” to support closures in all languages ​​that work in the JVM. Despite the fact that many JVM languages ​​support closures, they have to implement their own versions, which makes the transfer of closures between languages ​​rather difficult. If Java itself defines a single format, all other languages ​​will be able to use it effectively.

Conclusion

Losing control over low-level details in favor of a language or framework is a general trend in software development. We happily disclaim responsibility for garbage collection, memory management, and hardware differences. Functional programming represents a new level of abstraction: concessions to the details of the implementation of the routine functionality for iteration, concurrency, and state management of the environment to the extent possible. This does not mean that you will not be able to regain control if needed - but you must want it and not be forced.

In the next issue, I will continue my journey through functional constructs in Java and its close relatives with a description of currying ( currying ) and partial method application .

Notes

* - Here the author seems to be too diligently moving away from academic terminology. We are talking about free variables in lambda expression. Good intuition about the behavior of closures in different implementations can be obtained from the article in the TFG. A fairly clear formal definition of free and bound variables is given in the Wikipedia article .

PS Thank you CheatEx for their assistance in translating