Java.next: Memoization and functional synergy

Core functional features and how the Java.next languages implement and combine them

Both Scala and Clojure are functional languages, and Groovy includes many functional features through libraries. This Java.next installment explores how memoization is implemented in the Java.next languages and how the combination of functional features leads to concise power.

Neal Ford, Director / Software Architect / Meme Wrangler, ThoughtWorks

Photo of Neal fordNeal Ford is Director, Software Architect, and Meme Wrangler at ThoughtWorks, a global IT consultancy. He is also the designer and developer of applications, instructional materials, magazine articles, courseware, and video/DVD presentations, and he is the author or editor of books spanning a variety of technologies, including the most recent Presentation Patterns. He focuses on designing and building large-scale enterprise applications. He is also an internationally acclaimed speaker at developer conferences worldwide. Check out his website.



18 February 2014

Also available in Chinese Russian Japanese

About this series

The Java™ legacy will be the platform, not the language. More than 200 languages run on the JVM, and it's inevitable that one of them will eventually supplant the Java language as the best way to program the JVM. This series explores three next-generation JVM languages: Groovy, Scala, and Clojure, comparing and contrasting new capabilities and paradigms, to provide Java developers a glimpse into their own near future.

All programming languages are adding functional features as runtimes become powerful enough to accommodate performance or memory overhead. One of the many benefits of functional programming is that you can offload cumbersome or error-prone tasks to the runtime. Another is the ability to combine functional features concisely in your code.

In this installment, I explore memoization in the Java.next languages. Then, using a Clojure example, I show how the synergy among functional features enables generic solutions to common problems.

Memoization

The word memoization was coined by Donald Michie, a British artificial-intelligence researcher, to refer to function-level caching for repeating values. Today, memoization is common in functional programming languages, either as a built-in feature or as one that's relatively easy to implement.

Memoization helps in the following scenario. Suppose you have a performance-intensive function that you must call repeatedly. A common solution is to build an internal cache. Each time you calculate the value for a certain set of parameters, you put that value in the cache, keyed to the parameter value(s). In the future, if the function is invoked with previous parameters, return the value from the cache rather than recalculate it. Function caching is a classic computer science trade-off: It uses more memory (which we frequently have in abundance) to achieve better performance over time.

Functions must be pure for the caching technique to work. A pure function is one that has no side effects: It references no other mutable class fields, doesn't set any values other than the return value, and relies only on the parameters for input. All the methods in the java.lang.Math class are excellent examples of pure functions. Obviously, you can reuse cached results successfully only if the function reliably returns the same values for a given set of parameters.

Memoization in Groovy

More on memoization

I describe the mechanism of memoization in Groovy, including performance comparisons, in the "Functional features in Groovy, Part 3" installment of my Functional thinking series. That article also shows more-detailed memoization syntax for all three Java.next languages.

Memoization is trivial in Groovy, which includes a family of memoize() functions on the Closure class. For example, suppose you have an expensive hashing algorithm, leading you to cache the results for efficiency. You can do so by using closure-block syntax to define the method and calling the memoize() function on the return, as shown in Listing 1. (I don't mean to suggest that the ROT13 algorithm—a version of the Caesar Cipher—used in Listing 1 is performance-challenged, so just pretend that caching is worth it in this example.)

Listing 1. Memoization in Groovy
class NameHash {
  def static hash = {name ->
    name.collect{rot13(it)}.join()
  }.memoize()

  public static char rot13(s) {
    char c = s
    switch (c) {
      case 'A'..'M':
      case 'a'..'m': return c + 13

      case 'N'..'Z':
      case 'n'..'z': return c - 13
      default: return c
    }
  }
}

class NameHashTest extends GroovyTestCase {
  void testHash() {
    assertEquals("ubzre", NameHash.hash.call("homer"))  }
}

Normally, Groovy function definitions look like rot13() in Listing 1, with the method body following the parameter list. The hash() function definition uses slightly different syntax, assigning the code block to the hash variable. The last part of the definition is the call to memoize(), which automatically creates an internal cache for repeating values, keyed on parameter.

The memoize() method is really a family of methods, giving you some control over caching characteristics, as shown in Table 1.

Table 1. Groovy's memoize() family
MethodUse
memoize()Returns an instance of the closure with caching
memoizeAtMost()Sets an upper bound on the number of cached elements
memoizeAtLeast(int protectedCacheSize)Sets a lower limit on the number of cached elements, protecting a certain number of elements from garbage collection
memoizeBetween(int protectedCacheSize, int maxCacheSizeSets a lower and upper bound on the number of cached elements

The methods in Table 1 give you coarse-grained control over caching characteristics — not fine-grained ways to tune cache characteristics directly. Memoization is meant to be a general-purpose mechanism for easily optimizing common caching cases.

Memoization in Clojure

Memoization is built into Clojure. You can memoize any function by using the built-in (memoize ) function. For example, if you have an existing (hash "homer") function, you can memoize it via (memoize (hash "homer")) for a caching version. Listing 2 implements the name-hashing example from Listing 1 in Clojure.

Listing 2. Clojure memoization
(defn name-hash [name]
  (apply str (map #(rot13 %) (split name #"\d"))))

(def name-hash-m (memoize name-hash))

(testing "name hash"
  (is (= "ubzre" (name-hash "homer"))))

(testing "memoized name hash"
  (is (= "ubzre" (name-hash-m "homer")))))

Note that in Listing 1, calling the memoized function requires an invocation of the call() method. In the Clojure version, the memoized method call is exactly the same on the surface, with the added indirection and caching invisible to the method's user.

Memoization in Scala

Scala doesn't implement memoization directly but has a collection method named getOrElseUpdate() that handles most of the work of implementing it, as shown in Listing 3.

Listing 3. Scala memoization
def memoize[A, B](f: A => B) = new (A => B) {
    val cache = scala.collection.mutable.Map[A, B]()
    def apply(x: A): B = cache.getOrElseUpdate(x, f(x))
  }

def nameHash = memoize(hash)

The getOrElseUpdate() function in Listing 3 is the perfect operator for building a cache. It either retrieves the matching value or creates a new entry when none exists.


Combining functional features

Combination through composition

Composition has many meanings in software development. Functional composition refers to the ability to combine functions to get composite results. In mathematical terms, if you have an f(x) function and a g(x) function, you should be able to execute f(g(x)). In software terms, if you have an a() function that converts strings to uppercase and a b() function that trims excess spaces, a composed function would perform both tasks.

In the preceding section and in the last few Java.next installments, I've covered several details of functional programming, particularly as they pertain to the Java.next languages. However, the real power of functional programming lies in the combination of features and the way solutions are approached.

Object-oriented programmers tend to create new data structures and attendant operations constantly. After all, building new classes and messages between them is the predominant language paradigm. But building so much bespoke structure makes building reusable code at the lowest level difficult. Functional programming languages prefer a few core data structures and build optimized machinery for understanding them.

Here's an example. Listing 4 shows the indexOfAny() method from the Apache Commons framework (which provides a slew of helpers for Java programming).

Listing 4. indexOfAny() from Apache Commons
// From Apache Commons Lang, http://commons.apache.org/lang/
public static int indexOfAny(String str, char[] searchChars) {
    if (isEmpty(str) || ArrayUtils.isEmpty(searchChars)) { 
        return INDEX_NOT_FOUND;
    }
    int csLen = str.length();
    int csLast = csLen - 1;
    int searchLen = searchChars.length;
    int searchLast = searchLen - 1;
    for (int i = 0; i < csLen; i++) {
        char ch = str.charAt(i);
        for (int j = 0; j < searchLen; j++) { 
            if (searchChars[j] == ch) {
                if (i < csLast && j < searchLast && CharUtils.isHighSurrogate(ch)) {
                    if (searchChars[j + 1] == str.charAt(i + 1)) {
                        return i;
                    }
                 } else {
                     return i;
                 }

             }
         }
     }
     return INDEX_NOT_FOUND;
}

The first third of the code in Listing 4 concerns edge-case checks and initialization of the variables needed for the nested iteration to come. I'll gradually transform this code into Clojure. For the first step, I remove the corner cases, as shown in Listing 5.

Listing 5. Removing corner cases
public static int indexOfAny(String str, char[] searchChars) {
    when(searchChars) {
        int csLen = str.length();
        int csLast = csLen - 1;
        int searchLen = searchChars.length;
        int searchLast = searchLen - 1;
        for (int i = 0; i < csLen; i++) {
            char ch = str.charAt(i);
            for (int j = 0; j < searchLen; j++) {
                if (searchChars[j] == ch) {
                    if (i < csLast && j < searchLast && CharUtils.isHighSurrogate(ch)) {
                        if (searchChars[j + 1] == str.charAt(i + 1)) {
                            return i;
                        }
		    } else {
		        return i;
		    }
		}
            }
        }
        return INDEX_NOT_FOUND;
    }
}

Clojure intelligently handles the null and empty cases and has intelligent functions such as (when ...), which returns true only when characters are present. Clojure is a dynamically (but strongly) typed, eliminating the need to declare variable types before use. Thus, I can remove the type declarations, resulting in the code in Listing 6.

Listing 6. Removing type declarations
indexOfAny(str, searchChars) {
    when(searchChars) {
        csLen = str.length();
    csLast = csLen - 1;
    searchLen = searchChars.length;
    searchLast = searchLen - 1;
    for (i = 0; i < csLen; i++) {
          ch = str.charAt(i);
        for (j = 0; j < searchLen; j++) {
          if (searchChars[j] == ch) {      
          if (i < csLast && j < searchLast && CharUtils.isHighSurrogate(ch)) {
            if (searchChars[j + 1] == str.charAt(i + 1)) {
            return i;
          }
          } else {
            return i;
          }
        }
        }
    }
    return INDEX_NOT_FOUND;
    }
}

The for loop — a staple of imperative languages — allows access to each element in turn. Functional languages tend to rely more on collection methods that already understand (or avoid) edge cases, so I can remove methods such as isHighSurrogate() (which checks for character encodings) and manipulation of index pointers. The result of this transformation appears in Listing 7.

Listing 7. A when clause to replace the innermost for
// when clause for innermost for
indexOfAny(str, searchChars) {
    when(searchChars) {
        csLen = str.length();                    
        for (i = 0; i < csLen; i++) {            
            ch = str.charAt(i);
            when (searchChars(ch)) i;
        }
    }
}

In Listing 7, I collapse the code into a method that checks for the presence of the sought-after characters and returns the index when they're found. While I'm in neither Java nor Clojure but a strange pseudocode place, this when method doesn't quite exist. But the (when ) method in Clojure, which this code is slowly becoming, does.

Next, I replace the topmost for loop with a more concise substitute, using the for comprehension: a macro that combines access and filtering (among other things) for collections. The evolved code appears in Listing 8.

Listing 8. Adding a comprehension
// add comprehension
indexOfAny(str, searchChars) {
    when(searchChars) {
        for ([i, ch] in indexed(str)) {    
            when (searchChars(ch)) i;
        }
    }
}

To understand the for comprehension in Listing 8, you must first understand a few parts. The (indexed ...) function in Clojure accepts a Sequence and returns a sequence that includes numbered elements. For example, if I call (indexed '(a b c)), the return is ([0 a] [1 b] [2 c]). (The single apostrophe indicates to Clojure that I want a literal sequence of characters, not that I want to execute an (a ) method with two parameters.) The for comprehension creates this sequence over my search characters, then applies the inner when to find the index of the matching characters.

The last step in this transformation is to convert the code into proper Clojure syntax and restore the presence of real functions and syntax, as shown in Listing 9.

Listing 9. Clojure-ifying the code
// Clojure-ify
(defn index-filter [pred coll]           
  (when pred                     
    (for [[index element] (indexed coll) :when (pred element)] index)))

In the final Clojure version in Listing 9, I convert the syntax to proper Clojure and add one upgrade: Callers of this function can now pass any predicate function (one that returns a Boolean result), not just the check for an empty string. One Clojure's goals is the ability to create readable code (after you assimilate the parentheses), and this function exemplifies this ability: For the indexed collection, when your predicate matches the element, return the index.

Another Clojure goal is expressiveness with the least number of characters; Java suffers terribly in comparison with Clojure in this regard. Table 2 compares "moving parts" quantities in Listing 4 to those in Listing 9.

Table 2. Comparison of "moving parts"
ImperativeFunctional
Functions11
Classes10
Internal exit points20
Variables30
Branches40
Boolean operators10
Function calls63
Total184

The difference in complexity is telling. Yet although the Clojure code is simpler, it is also more general. Here I index a sequence of coin flips, modeled as the Clojure :h (heads) and :t (tails) keywords:

(index-filter #{:h} [:t :t :h :t :h :t :t :t :h :h]) 
-> (2 4 8 9)

Notice that the return value is a sequence of all matching index positions, not just the first. List operations in Clojure are lazy when possible, including this one. If I only want the first value, I can (take 1 ) from the result, or I can print them all, as I've done here.

My (index-filter ) function is generic, so I can use it on numbers. For example, I can determine the first number whose Fibonacci value exceeds 1,000:

Laziness

Laziness — deferral of expression evaluation for as long as possible — is another good example of functional languages adding capabilities at little or no cost to the developer. See "Functional thinking: Exploring lazy evaluation in Java" and "Functional thinking: Delving deeper into lazy evaluation" for discussion of laziness and examples in the Java.next languages.

(first 
  (index-filter #(> % 1000) (fibo)))
-> 17

The (fibo) function returns an infinite but lazy sequence of Fibonacci numbers; (index-filter ) finds the first one that exceeds 1,000. (It turns out that the Fibonacci of 18 is 1,597.) The combination of functional constructs, dynamic typing, laziness, and concise syntax yields great power.


Conclusion

Functional programming constructs yield benefits when used piecemeal, but they offer even more advantages when they're combined. All the Java.next languages are functional to one degree or another, enabling increasing use of this style of development.

In this installment, I discussed how functional programming eliminates moving parts — making programming less error-prone — and the benefits of combining functional features. In the next installment, I begin an even more powerful illustration of this concept as I discuss how the Java.next languages make concurrency on the JVM easier.

Resources

Learn

  • ROT13: ROT13 is an example of the Caesar Cipher, an ancient encryption algorithm used by Julius Caesar.
  • Apache Commons: Commons is a popular utility framework in the Java ecosystem.
  • Groovy: Groovy is a dynamic variant of the Java language, with updated syntax and capabilities.
  • Scala: Scala is a modern, functional language on the JVM.
  • Clojure: Clojure is a modern, functional Lisp that runs on the JVM.
  • Functional thinking: Explore functional programming in Neal Ford's column series on developerWorks.
  • "Execution in the Kingdom of Nouns" (Steve Yegge, March 2006): An entertaining rant about some aspects of Java language design.
  • Language designer's notebook: In this developerWorks series, Java Language Architect Brian Goetz explores some of the language design issues that have presented challenges for the evolution of the Java language in Java SE 7, Java SE 8, and beyond.
  • developerWorks Java technology zone: Find hundreds of articles about every aspect of Java programming.

Discuss

  • Get involved in the developerWorks community. Connect with other developerWorks users as you explore the developer-driven blogs, forums, groups, and wikis.

Comments

developerWorks: Sign in

Required fields are indicated with an asterisk (*).


Need an IBM ID?
Forgot your IBM ID?


Forgot your password?
Change your password

By clicking Submit, you agree to the developerWorks terms of use.

 


The first time you sign into developerWorks, a profile is created for you. Information in your profile (your name, country/region, and company name) is displayed to the public and will accompany any content you post, unless you opt to hide your company name. You may update your IBM account at any time.

All information submitted is secure.

Choose your display name



The first time you sign in to developerWorks, a profile is created for you, so you need to choose a display name. Your display name accompanies the content you post on developerWorks.

Please choose a display name between 3-31 characters. Your display name must be unique in the developerWorks community and should not be your email address for privacy reasons.

Required fields are indicated with an asterisk (*).

(Must be between 3 – 31 characters.)

By clicking Submit, you agree to the developerWorks terms of use.

 


All information submitted is secure.

Dig deeper into Java technology on developerWorks


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=1
Zone=Java technology
ArticleID=962784
ArticleTitle=Java.next: Memoization and functional synergy
publish-date=02182014