Jakub is a Java EE developer since 2005 and occasionally a project manager, working currently with Iterate AS. He's highly interested in developer productivity (and tools like Maven and AOP/AspectJ), web frameworks, Java portals, testing and performance and works a lot with IBM technologies. A native to Czech Republic, he lives now in Oslo, Norway. Jakub is a DZone MVB and is not an employee of DZone and has posted 155 posts at DZone. You can read more from them at their website. View Full User Profile

How stateless can you go?

05.04.2011
| 5332 views |
  • submit to reddit

I’ve attended an Oslo Coding Dojo named “How stateless can you go?” lead by Thomas K. Nilsson. The goal was to write a toString() method for a tree structure printing nodes with proper indentation w.r.t. their depth and then to make it as stateless as possible without any other regard (such as performance or cleanliness of the code).

It was very interesting to compare the original, stateful version and the resulting stateless one and to see the solution in various languages (Haskell, Clojure, Groovy, C#, Java, Scala) – it looked actually pretty similar in all.

What I’ve learned is that stateless (i.e. functional-style) code looks much cleaner for you get rid of lot of noise such as local variables and loops. In practice it is important to use a language with an efficient implementation of recursion (especially tail-recursion) and with data structures that lead themselves easily to recursive processing, i.e. make it easy and efficient to process the first element of a collection and do that recursively for the rest without modifying the collection (and providing utility methods like each). It is of course best to have languages that support map/reduce.

You can check the slides and various solutions at GitHub and see our primitive and stateless implementations below. (We did it in a nearly TDD-manner, but I won’t include the test here as it isn’t essential.)

Solution by Jakub & Anders

The Primitive Implementation

 

// ...
@Override
public String toString() {
return toString(0);
}

private String toString(final int nesting) {
String tabs = "";
for (int i = nesting; i > 0; i--)
tabs += "\t";

return tabs + this.content + "\n"
+ printChildren(nesting + 1, new LinkedList(this.children));
}

private String printChildren(int nesting, List children) {
String result = "";
for (Node child : children) {
result += child.toString(nesting);
}
return result;
}
// ...

Going Stateless

Loops removed:

// ...
@Override
   public String toString() {
      return toString("");
   }

   private String toString(final String indentation) {
      return indentation + this.content + "\n"
         + printList(indentation + "\t", new LinkedList(this.children));
   }

   private String printList(String indentation, LinkedList children) {
      if (children.isEmpty()) return "";
      return children.pop().toString(indentation) + printList(indentation, children);
   }
// ...

Cloning the List is perhaps not a good thing from the performance point of view, but that wasn’t the concern here; other languages can deal with that much more efficiently than Java. Anyway I’ve created a version without it (but with ugly integer constants instead):

// ...
   private String toString(final String indentation) {
      return indentation + content + "\n"
         + printList(indentation + "\t", children);
   }

   private String printList(String indentation, List children) {
      if (children.isEmpty()) return "";
      return children.get(0).toString(indentation)
         + printList(indentation, children.subList(1, children.size()));
   }
// ...

Appendix: The Node Class

The rest of the Node class representing the tree to be printed is the same in all our solutions:

package scotsman;

import java.util.LinkedList;
import java.util.List;

public class Node {

   private String content;
   private List children;

   public Node(String content) {
      this(content, new LinkedList());
   }

   public Node(String content, List children) {
      this.content = content;
      this.children = children;
   }

   public Node withChild(Node child) {
      children.add(child);
      return this;
   }

   // toString implementation comes here...

}

Conclusion

Functional programming is cool. Being in Oslo is cool. :-)

From http://theholyjava.wordpress.com/2011/04/29/how-stateless-can-you-go/

Published at DZone with permission of Jakub Holý, author and DZone MVB.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Tags:

Comments

Andrew Osipenko replied on Thu, 2011/05/05 - 7:31am

 I do not agree that functional like code looks more clean.

 How much developers know what's tail recursion?

 And how much developers know what's cycle?

 I would say that functional-like code is easier for mathematicians, while cycle based code is easier for regular developers.

cowwoc replied on Thu, 2011/05/05 - 8:43am

Recursion is not stateless. What do you think is on the stack? Anonymous local variables...

Tero Kadenius replied on Thu, 2011/05/05 - 10:40am

Functional style definitely tends to lead to cleaner code. Unfortunately Java is probably the worst language to showcase the superiority of functional style. You have to build your own tools and the results are cumbersome at best. However, I still believe there is value trying to make java code less imperative. Removing state has several benefits. I'd say unnecessary state and side effects are the number one culprits for untestable, unmaintainable spaghetti code. Code with side effects also encourages bad separation of concerns.

A good article on the subject by Neal Ford: http://www.ibm.com/developerworks/java/library/j-ft1/

Soylent Green replied on Fri, 2011/05/06 - 3:39am

cowwoc is completely right, what about the stack?

Having read the android howto's carefully you might find a paragraph dealing with a restricted max stack depth. I guess that might be true for any none fullblown environment aka embedded/mobile systems. So you buy some sort of esoteric "better readability" (how can I measure readability by the way. There must be some way for to be able to define sort of total order on programming fragments? readability(f1) < readability(f2)...I'm just curious, who can give me a clue) 

Afai remember my years at univesity on subject computer science the pure functional style programming was some sort of academical education...it's some sort of training in first place and even the teachers told us that nobody would really do that for the sole purpose of being labeled "100% functional". what does it buy me to be 100% functional anyways apart from being able to attach a lable to my programm, I mean, name the explicit business value...And there were even lessons on how to avoid bad style of recursion (was it tail-recursion?) and how to transform it into the "right" style of recursion. What the heck, do we really want to take care about that for the sake of "functional purism" and an obscure better readybility

Tero Kadenius replied on Fri, 2011/05/06 - 9:10am in response to: Soylent Green

Soylent Green:
Before you go critisising recursion because it eats all your stack space, I advice you to google "tail call optimization". If you are on a platform where it isn't supported, it obviously has to be taken into account. If something requires imperative style, then go for it. There are no 100% truths. As usual, it's all about the context.

I believe the topic was not to be taken literally, but instead provoke discussion. Ie. the purpose is not to strive for functional purism but to think about how we can enhance the code we write.

You wanted the explicit business value. Well, here goes: testability and maintainability.  Two quality attributes that when done correctly result in lower costs. Have you ever maintained a piece of code with a lot of unnecessary mutable state sprinkled all over the place? Me too. It's slow and error-prone (= more expensive to the customer).

Jacek Szymanski replied on Sat, 2011/05/07 - 3:58am in response to: Tero Kadenius

Before you go critisising recursion because it eats all your stack space, I advice you to google "tail call optimization".
None of the above posted examples is tail recursive. Try to make them so, and the entire readability "gain" is more than gone. And this is a fairly trivial example.
You wanted the explicit business value. Well, here goes: testability and maintainability.
Not so fast. Recursion has its place and so do loops. If you replace a loop with recursion, you either have to worry about the recursion depth and stack size (say hello to your debugger), or make sure the code is tail recursive (which is often counter-intuitive and makes the code less readable, not more) and that the environment supports tail recursion which may or may not be the case. Either way, it seems to me that it's best to just leave loops alone.
Have you ever maintained a piece of code with a lot of unnecessary mutable state sprinkled all over the place?
If it were really unnecessary, you should get rid of this mutable state altogether, not just try to hide it beneath the recursion.

Tero Kadenius replied on Sat, 2011/05/07 - 5:30pm in response to: Jacek Szymanski

Jacek Szymanski:
I'm afraid you misunderstood my comment. As I said, it's all about the context. I was not promoting the use of recursion everywhere. Removing unnecessary mutable state != use recursion for everything. I definitely wasn't claiming that it's the use of recursion that automatically improves testability and maintainability. What I was saying, is that it is often beneficial to strive for more functional (style) code.

Jacek Szymanski replied on Sun, 2011/05/08 - 2:29am in response to: Tero Kadenius

Tero Kadenius: We are in context of the posted examples, where recursion (non-tail recursion) was used in place of a loop. You can and should remove unnecessary state where it is really unnecessary, but it does not mean switching to functional style, the imperative style will do just as well. In fact, it will do better as imperative style is usually more intuitive and thus easier to understand. Loops and recursion are a very good example of this: to remove imperative style loops, you either have to replace them with plain recursion thus crippling the code and risking stack exhaustion, or to use proper tail recursion which is harder to read, thus less maintainable.

Tero Kadenius replied on Sun, 2011/05/08 - 9:40am in response to: Jacek Szymanski

Jacek Szymanski:
My comment to "imperative style is usually more intuitive and thus easier to understand." is
that it is functional style that is usually more intuitive and thus easier to understand for
the very same reasons we've already discussed.
 
Unnecessary state places a heavy load on the reader's cognitive capacity.
Functional style avoids this. I'm not a purist but rather a pragmatist.
I don't promote functional style for the sake of it, but for the benefits it offers.
There is much more to functional programming style than using recursion.
If you don't like recursion, then ditch it. There are many other tools you can use
to avoid the drawbacks of imperative programming.

I highly recommend reading http://www.ibm.com/developerworks/java/library/j-ft1/.

Jacek Szymanski replied on Sun, 2011/05/08 - 3:35pm in response to: Tero Kadenius

the very same reasons we've already discussed.
No, you presented no evidence whatsoever, and examples provided by author support my point, not yours.
Unnecessary state places a heavy load on the reader's cognitive capacity.
Unnecessary state is not associated with imperative programming, but with bad design and bad coding habits. You can write bad code in functional style as well.
Functional style avoids this.
No, good design avoids this.
I highly recommend reading

Please... it is so bad, it's even funny. The imperative example looks as if it were written bad on purpose (seroiusly, I wouldn't expect this load of bad design from a first year student), functional ones look nicer at the surface level, but - won't a call to range(1, Integer.MAX_VALUE) make it explode? It is not documented in FJ. Even if it does not - a better imperative solution (e.g. one that preclassifies the number in the constructor) would look even nicer than the functional one, would not unnecessarily repeat a possibly expensive computation and be reusable.

But it really seems to me, that you need to write imperative code badly on purpose to make it look worse than functional one

Tero Kadenius replied on Mon, 2011/05/09 - 9:38am in response to: Jacek Szymanski

I really don't want to turn this into an academic debate. It's not necessary. However, I need to point out that imperative programming is all about state. By unnecessary state I mean state that can be avoided by using a more functional style. It's that simple.

For clarification, a couple of quotes from wikipedia:

In computer science, imperative programming is a programming paradigm that describes computation in terms of statements that change a program state .

[Functional programming] emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state.

In imperative programming, the problems are modelled using state, in functional programming they are modelled using a series of transformations. What you refer as good design leans towards functional programming style and that's a good thing. I agree that you can write bad code in any style.

Jacek Szymanski replied on Mon, 2011/05/09 - 4:12pm in response to: Tero Kadenius

I need to point out that imperative programming is all about state. By unnecessary state I mean state that can be avoided by using a more functional style.
If it can be avoided at all, it can be avoided as well without using "a more functional style". If it can't, functional style can hide it, but it's not gone, it's still there and probably will come out when you least expect it.
What you refer as good design leans towards functional programming style and that's a good thing.

No, quite the opposite. I'd certainly get rid of most of this FJ code and replace with a single loop. (I'm still reffering to the example you provided).

I've come across another explanation of this shockingly bad "imperative" code in the example. Why on earth do they store all factors in a Set in an object field (and why do they always repopulate the set)? WTF? And know what? This seems to be the functional thinking at work: to sum the factors they need them first, so - not to be too functional - they store them. But it's just wrong: one can sum the numbers up while iterating and not store them anywhere. That's imperatively. Functionally, one probably should first generate a list of candidates, then filter them, then sum up - passing appropriate collections as one sees fit. Decide for yourself which style generates more unnecessary objects.

One more thing: while I'm not a big fan of optimization, it's often the case that the functional solution is orders of magnitude less efficient (more often memorywise than timewise) than an equivalent imperative one. I will use again the example you kindly provided: if I tried to, this code would try to cons up a billion element List. Fortunately, FJ would use recursion internally, and probably long before it would hit the heap limit, the stack would overflow. Of course, the imperative solution would just work. Heck, even the horrible imperative solution posted by the author would probably still work when the functional one would long have exploded.

Yes, this was a very good read on why you should avoid the functional.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.