XNSIO
  About   Slides   Home  

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

Archive for the ‘Functional’ Category

Presenting Functional Conf 2014, Asia’s Premier and First Conference on Functional Programming

Thursday, June 12th, 2014

We are delighted to announce the first Functional Programming conference in Asia. Functional Conf will be hosted in Bangalore, India on Oct 9-11th. This is your golden opportunity to meet the Functional Programming community.

For over 35 years, functional programming has been a hot research topic. However in the last 5 years, driven by the need to build massively concurrent systems and to handle big-data, we’ve experienced a rapid adoption of functional programming concepts by diverse companies, ranging from tech start-ups to financial institutes.

These days, functional programming is at the heart of every, new generation programming technologies. Companies are employing functional programming to enable more effective, robust, and flexible software development. This has given birth to a very vibrant community of functional programmers, who are constantly exploring ways to bring functional programming concepts to the world of enterprise software development.

Functional Conf is designed to bring the growing community of functional programmers together under one roof. At Functional Conf:

  • participants can understand the fundamentals concepts behind functional programming,
  • they can learn how others are using functional programming to solve real world problems,
  • practitioners can meet peers and exchange their experience,
  • experts can share their expertise on practical usage and gotchas in functional programming concepts.

If you are interested in presenting at the Functional Conf, please submit your proposals at http://confengine.com/functional-conf-2014

Registrations have already started. Register now at http://booking.agilefaqs.com/functional-conf-2014

To know more about the conference, please visithttp://functionalconf.com

Refactoring Teaser IV Solution

Sunday, September 27th, 2009

Its been a while since the Fourth Refactoring Teaser was posted. So far, I think this is one of the trickiest refactorings I’ve tried. Refactored half of the solution and rewrote the rest of it.

Particularly thrilled about shrinkage in the code base. Getting rid of all those convoluted Strategies and Child Strategies with 2 main classes was real fun (and difficult as well).  Even though the solution is not up to the mark, its come a long long way from where it was.

Ended up renaming IdentityGenerator to EmailSuggester. Renamed the PartialAcceptanceTest to EmailSuggesterTest. Also really like how that test looks now:

28
29
30
private final User naresh_from_mumbai = new User("naresh", "jains", "mumbai", "india", "indian");
private final Context lets = new Context(userService, dns);
private final EmailSuggester suggester = new EmailSuggester(userService, dns, randomNumberGenerator);
32
33
34
35
36
@Test
public void suggestIdsUsingNameLocationAndNationality() {
    List<String> suggestions = suggester.optionsFor(naresh_from_mumbai);
    lets.assertThat(suggestions).are("[email protected]", "[email protected]", "[email protected]", "[email protected]");
}
38
39
40
41
42
43
@Test
public void avoidRestrictedWordsInIds() {
    lets.assume("naresh").isARestrictedUserName();
    List<String> suggestions = suggester.optionsFor(naresh_from_mumbai);
    lets.assertThat(suggestions).are("[email protected]", "[email protected]", "[email protected]", "[email protected]");
}
45
46
47
48
49
50
@Test
public void avoidCelebrityNamesInGeneratedIds() {
    lets.assume("naresh", "jains").isACelebrityName();
    List<String> suggestions = suggester.optionsFor(naresh_from_mumbai);
    lets.assertThat(suggestions).are("[email protected]", "[email protected]", "[email protected]", "[email protected]");
}
52
53
54
55
56
57
@Test
public void appendCurrentYearWithFirstNameIfIdIsNotAvailable() {
    lets.assume().identity("[email protected]").isNotAvailable();
    List<String> suggestions = suggester.optionsFor(naresh_from_mumbai);
    lets.assertThat(suggestions).are("[email protected]", "[email protected]", "[email protected]", "[email protected]");
}

EmailSuggester’s optionsFor() method turned out to be fairly straightforward.

26
27
28
29
30
31
32
33
34
public List<String> optionsFor(final User user) {
    List<String> ids = new ArrayList<String>();
    List<String> variations = asList(user.lastName, user.countryName, user.countryMoniker, user.city);
    for (String variation : variations) {
        UserData data = new UserData(user.firstName, variation, user.lastName);
        data.addGeneratedIdTo(ids);
    }
    return ids;
}

This method uses UserData class’ addGeneratedIdTo() method to add an email id to the list of ids passed in.

47
48
49
50
51
52
53
54
55
private void addGeneratedIdTo(final List<String> ids) {
    for (EmailData potential : buildAllPotentialEmailCombinations()) {
        String email = Email.create(potential.userName, potential.domain, dns);
        if (userService.isEmailAvailable(email)) {
            ids.add(email);
            break;
        }
    }
}

This method fetches all potential email address combination based on user data as follows:

57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
private List<EmailData> getAllPotentialEmailCombinations() {
    return new ArrayList<EmailData>() {
        {
            add(new EmailData(firstName, seed));
 
            if (seed != lastName) {
                add(new EmailData((firstName + lastName), seed));
                add(new EmailData((firstName + lastName.charAt(0)), seed));
            }
 
            add(new EmailData((firstName + currentYear()), seed));
 
            if (seed != lastName)
                add(new EmailData((firstName + lastName.charAt(0) + currentYear()), seed));
 
            for (int i = 0; i < MAX_RETRIES_FOR_RANDOM_NUMBER; ++i)
                add(new EmailData((firstName + randomNumber.next()), seed));
        }
    };
}

I’m not happy with this method. This is the roughest part of this code. All the

if (seed != lastName) {

seems dodgy. But at least all of it is in one place instead of being scattered around 10 different classes with tons of duplicate code.

For each potential email data, we try to create an email address, if its available, we add it, else we move to the next potential email data, till we exhaust the list.

Given two tokens (user name and domain name), the Email class tries to creates an email address without Restricted Words and Celebrity Names in it.

30
31
32
33
34
35
private String buildIdWithoutRestrictedWordsAndCelebrityNames() {
    Email current = this;
    if (isCelebrityName())
        current = trimLastCharacter();
    return buildIdWithoutRestrictedWordsAndCelebrityNames(current, 1);
}
37
38
39
40
41
42
43
44
45
46
private String buildIdWithoutRestrictedWordsAndCelebrityNames(final Email last, final int count) {
    if (count == MAX_ATTEMPTS)
        throw new IllegalStateException("Exceeded the Max number of tries");
    String userName = findClosestNonRestrictiveWord(last.userName, RestrictedUserNames, 0);
    String domainName = findClosestNonRestrictiveWord(last.domainName, RestrictedDomainNames, 0);
    Email id = new Email(userName, domainName, dns);
    if (!id.isCelebrityName())
        return id.asString();
    return buildIdWithoutRestrictedWordsAndCelebrityNames(id.trimLastCharacter(), count + 1);
}

Influenced by Functional Programming, I’ve tried to use Tail recursion and Immutable objects here.

Also to get rid of massive duplication in code, I had to introduce a new Interface and 2 anonymous inner classes.

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public interface RestrictedWords {
    RestrictedWords RestrictedUserNames = new RestrictedWords() {
        @Override
        public boolean contains(final String word, final DomainNameService dns) {
            return dns.isRestrictedUserName(word);
        }
    };
 
    RestrictedWords RestrictedDomainNames = new RestrictedWords() {
        @Override
        public boolean contains(final String word, final DomainNameService dns) {
            return dns.isRestrictedDomainName(word);
        }
    };
 
    boolean contains(final String word, DomainNameService dns);
}

This should give you a decent idea of what the code does and how it does what it does. To check in detail, download the complete project source code.

Also I would recommend you check out some the comparison of code before and after.

Iteration v/s Recursion and Mutable v/s Immutable

Tuesday, August 18th, 2009
  Mutable Immutable
Iteration S- H- S- H^
Recursion S^ H- S^ H^
Tail Recursion without Optimization S^ H- S^ H ^
Tail Call Optimization S- H- S- H- *

* Heap size remains the same assuming Garbage collection takes places regularly.

Here, when I say Immutable, I mean the class in which the method (using iterator or recursive) is contained is Immutable. .i.e. the method is trying to update the instance variables, but they are declared final, hence they cannot be modified. Only way to modify them is to create a new object with the updated instance variables.

Legend:

S Stack Memory Size
H Heap Memory Size
Remains the same
^ Increases

For Ex: S^ means Stack size grows.

Embracing Tail Recursion and Immutability

Tuesday, August 18th, 2009

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