XNSIO
  About   Slides   Home  

 
Managed Chaos
Naresh Jain's Random Thoughts on Software Development and Adventure Sports
     
`
 
RSS Feed
Recent Thoughts
Tags
Recent Comments

Embracing Tail Recursion and Immutability

Consider the following code:

//instance variable
private final List<String> restrictedWords = retrieveRestrictedWordsFromDB();
 
public String findClosestNonRestrictiveWord(String word) {
    for (int i = 0; i < MAX_ATTEMPTS && word.length() > 1; i++) {
        if (!restrictedWords.contains(word))
            return word;
        word = word.substring(0, word.length() - 1);
    }
    throw new IllegalArgumentException(word + " is a restricted word");
}

One would say this code is performant and uses memory optimally (time and space complexity is low) but is not the most expressive (intent revealing) code.

public String findClosestNonRestrictiveWord(final String word, final int count) {
    if (count == MAX_ATTEMPTS || word.length() <= 1)
        throw new IllegalArgumentException(word + " is a restricted word");
    if (!restrictedWords.contains(word))
        return word;
    return findClosestNonRestrictiveWord(trimLastChar(word), count + 1);
}
 
private String trimLastChar(final String word) {
    return word.substring(0, word.length() - 1);
}

I would argue that this code is much easier to understand and has very similar space and time complexity as the iterator based approach in most languages. (I know some JVMs don’t do Tail Call Optimization.)

In this specific case, there is no big win either ways because the MAX_ATTEMPTS is 5. Lets take a slightly more complete example where we have two mutable (non-final) instance variables (note this is a dumbed down version of a complex class.):

public class EmailAddress {
    private static final int MAX_ATTEMPTS = 5;
    private String userName;
    private String domainName;
 
    public EmailAddress(final String userName, final String domainName) {
        if (isEmpty(userName) || isEmpty(domainName))
            throw new RuntimeException("User Name or Domain Name is empty or null");
        this.userName = userName.toLowerCase();
        this.domainName = domainName.toLowerCase();
    }
 
    public String asString() {
        for (int loopCounter = 0; loopCounter < MAX_ATTEMPTS; ++loopCounter)
            if (isEmpty(userName) || isEmpty(domainName))
                throw new RuntimeException();
            else if (!EmailService.isAvailable(userName, domainName)) {
                userName = userName.substring(0, userName.length() - 1);
                domainName = domainName.substring(0, domainName.length() - 1);
            } else
                return userName + "@" + domainName;
        throw new RuntimeException();
    }
 
    private boolean isEmpty(final String token) {
        return token == null || token.length() == 0;
    }
}

Now let’s imagine you had 2 threads calling the asString method. [Blast], this code would blow apart.

Well, not a problem, we can simply make the method synchronized. But wait a second, what does this mean? I can only execute this whole method by one thread. Which means for a single CPU, single threaded application this code performs well. But the moment you have a multi-core concurrent (multi-threaded) application, this code will show no performance improvement. That sucks!

So what might look performant (esp. after compromising on expressiveness) is not really scalable. So what option do we have?

We could create a new instance of EmailAddress for every thread. But what if that’s not under your control?

Another thing we can try is reduce the scope of the two instance variables to method parameter or local copies, but what if you cannot do that trivially?

That’s when we say, embrace tail recursion for expressiveness and immutable objects for concurrency.

public class EmailAddress {
    private static final int MAX_ATTEMPTS = 5;
    private final String userName;
    private final String domainName;
 
    public EmailAddress(final String userName, final String domainName) {
        if (isEmpty(userName) || isEmpty(domainName))
            throw new RuntimeException("User Name or Domain Name is empty or null");
        this.userName = userName.toLowerCase();
        this.domainName = domainName.toLowerCase();
    }
 
    public String asString() {
        return asString(this, 1);
    }
 
    private String asString(final EmailAddress current, final int count) {
        if (count == MAX_ATTEMPTS)
            throw new RuntimeException();
        if (EmailService.isAvailable(current.userName, current.domainName))
            return current.userName + "@" + current.domainName;
        String trimmedUserName = trimLastChar(current.userName);
        String trimDomainName = trimLastChar(current.domainName);
        EmailAddress trimmedAddress = new EmailAddress(trimmedUserName, trimDomainName);
        return asString(trimmedAddress, count + 1);
    }
 
    private String trimLastChar(final String word) {
        return word.substring(0, word.length() - 1);
    }
 
    private boolean isEmpty(final String token) {
        return token == null || token.length() == 0;
    }
}

Notice the two instance variables are final. Which means the EmailAddress object is immutable. Also notice that instead of trimming the original instance variables, we create a new EmailAddress with the trimmed values, which means we don’t manipulate any object level state and two threads are not sharing any data. Hence we avoid the whole synchronization issue.

Please note that in languages that do not support Tail Call Optimization, using tail recursion has similar space and time complexity as recursion. (For long recursive calls you run the risk of stack_over_flow). Also your Stack and Heap memory will grow linearly with every recursion. More about Iteration v/s Recursion and Mutable v/s Immutable.

Concepts borrowed from Functional Paradigm.


    Licensed under
Creative Commons License