January 31, 2008
Functional programming is heating up. In several discussions over the blogosphere and on my blog others think I have no clue what functional programming is. After some consideration, I think they are right. I have no clue.
Well I do know what functional programming is. I’ve used it myself. But I have no clue how to do a business application in FP. Others don’t know either. They talk about Bezier curves, square roots, fix points, y-combinators, power functions or remodel FP into OO and think that’s still FP. Weird.
Suppose I need to write an application. There are customers who can buy products. Based on the customer and the products he bought he can buy other products. Those products he books do cost him money which he needs to pay to the company. I’m quite sure how to design such an application in OO, discuss it with some domain experts and write the code. I also know how to write such an application in a way that other developers in 5 years from now can read, undestand and extend the code.
But how would I write such an application in Lisp? Or Arc? Teach me.
January 25, 2008
Tada-List was written in 579 lines of Rails code. Jeff of Coding Horror writes “[...], I agree with Joseph: it’s an impressive achievement, [...]“. I’m not impressed. If you write a framework for a narrow group of applications, it should be easy to write a small target application with a few lines of code. And they don’t count HTML.Top this: a game written in ZERO lines of code.
Most code is hidden in the framework. Taking it to the extreme, with XL/R and concept programming I could write TaDa List in one line of code:
tada-list
The issue remains. It’s the same with encryption. There is a message and a key. How much information is in the key and the message? If the key is “Hello World” then the message can just be “1″. If the key is “1″ then the message needs to be “Hello World”. How much code is in the framework and the application?
That aside. My biggest achivement in small code size was a 1024 bytes (the boot sector size of an Amiga) boot selector menu with color bars. Impressive if you consider we had to put all the menu text into those 1024 bytes.
January 24, 2008
When browsing and reading code, I often find this:
Date currentDate = new Date();
Someone needs a current date. The line is unclear what the developer really wanted to achieve. Does he want the current date or the current time? The Date class in Java is ambiguous: “The class Date represents a specific instant in time, with millisecond precision. ” and therefore should probably be called Time with Date only representing a day (the better named Time class resides in java.sql, ugh, one of the ugly decisions in Java).
Better name your variables with more meaning. Make your intentions clearer and use Calendar, which is more useful when working with dates[1]:
Calendar today = today();
Date now = now();
The implementation looks like this (use static imports) [2]:
public static Calendar today() {
return Calendar.getInstance();
}
public static Date now() {
return new Date();
}
Please, make your code more understandable for all the developers who follow you.
[1] You probably want to use Joda Time
[2] I know, Calendar stores the time also
January 22, 2008
As people have a need to mention Python and Javascript in mails and comments, as if I’ve never seen them beofre, I just checked my book shelf. The “Javascript-The Definitive Guide” says January 1997: Second Edition, “Programming Python” says October 1996: First Edition, “Java in a Nutshell” says May 1997: Second Edition, I’ve lost the first edition and bought the 2nd because it said “Covers Java 1.1″ on the cover, like the brand new inner classes and reflection :-)
January 21, 2008
On Lambda the ultimte there is a recent post with a language prediction for 2008, which mainly predicts the rise of functional programming and the rise of Scala in particular: “My prediction is a little bit more conservative, but I predict Scala will gain momentum, and at least one high visibility project will use Scala”. Brandon chimes in with “The most important thing to emerge from the discussion is the larger role functional programming will play. It seems like a safe bet.” A safe bet, really? I more sceptical, as written in my post about Qi4j and Scala.
The blogosphere is full of functional programming language advocates and the coming rise of functional programming in application development. But has anything changed since Lisp was invented in 1958? Functional programming languages have existed for more than 50 years now, and didn’t make any inroads into application development. What happend to the acclaimed golden age of functional programing, about which Peter Christensen writes? Will it come back? I dispute in a comment to that post that there ever was a golden age of functional programming, it was a fringe language from the beginning. There was a golden age of Fortran.
John McCarthy - no not THAT McCarthy - invented Lisp back in 1958. From there functional programming gained much appeal to programmers because of it’s clean and consistent style. Everything in Lisp is a list. Even the program itself. Because good programmers have a feel for aesthetics in programming style, they have a warm feeling for Lisp. Functional programming is also a powerful tool for software development. And developers like power. As Paul Graham writes in “Revenge of the Nerds” about power in languages with the aim to praise Lisp:
As an illustration of what I mean about the relative power of programming languages, consider the following problem. We want to write a function that generates accumulators– a function that takes a number n, and returns a function that takes another number i and returns n incremented by i.
He cites an example in Lisp, that implements an accumulator in a nice and pure way:
(defun foo (n) (lambda (i) (incf n i)))
Functional languages excel at mathematical and list processing problems. Most problems to solve in the enterprise are of a different type though. When moving to real problems then, functional programming languages get ugly as an ugly duck. With no swan in sight. Looking at examples from Implementing a blog in Common Lisp: Part 1, we see how ugly it can get. In Java land people a frustrated about XML, but see the brace chaos in Lisp, just to open a database:
; Open the store where our data is stored
(defvar *elephant-store*
(open-store '(:clsql (:sqlite3 "/tmp/blog.db"))))
And defining a blog domain object doesn’t look very readable either:
(defclass blog-post ()
((title :initarg :title
:accessor title)
(body :initarg :body
:accessor body)
(timestamp :initarg :timestamp
:accessor timestamp
:initform (get-universal-time)))
(:metaclass persistent-metaclass))
compared to a Groovy example:
@Entity
class BlogPost {
String title
String body
TimeStamp timeStamp = now
}
or a Java one in Qi4j:
public class BlogPost {
Property<String> title;
Property<String> body;
Property<TimeStamp> timeStamp = now();
}
Another example from nu, the rising functional star for Macos X. This time with the famous Currency converter example which creates a window:
(set @window ((NSWindow alloc)
initWithContentRect:'(125 513 383 175)
styleMask:(+ NSTitledWindowMask NSClosableWindowMask NSMiniaturizableWindowMask)
backing:NSBackingStoreBuffered
defer:0))
(@window setTitle:"Currency Converter")
With an equivalent example in Groovy to build a Swing UI:
def frame =
swing.frame(title:'Frame', size:[300,300]) {
borderLayout()
textlabel = label(text:"Clicked ${count} time(s).",
constraints: BorderLayout.NORTH)
button(text:'Click Me',
actionPerformed: {count++; textlabel.text = "Clicked ${count} time(s)."; println "clicked"},
constraints:BorderLayout.SOUTH)
}
Mostly equivalent with the Groovy example which is still slightly easier to read and understand, even by someone who doesn’t know Groovy. Mainly because Groovy is more expressive and not everything has to be pressed into a list (though the nu example contains more than lists as nu aims for object orientation).
In a discussion about Arc, a functional language, stevecooperorg writes about Lisp and the use of Emacs/Slime:
I’d like to write the next Viaweb, and I’d like to write it in Lisp. But if the basic language is inviting, the rest of the environment is sorta hostile; a shangri-la in a swamp.
That’s another problem of most fringe languages. People - the enterprise? - need to know too much beside the language. Using a fringe editor which most people abandoned in the 80s and “a decent knowledge of system administration” is too high a barrier.
Power is a good thing it seems. From my experience most developers can’t handle power. They misuse it. If your development team is less than 5 developers the chance is high that all of them are alpha developers. And your interviewing process was rigorous of course. Above ten and the chances are high that there won’t be only alpha coders. Power is a dangerous feature of a language then.
Do powerful languages scale? Do dynamical type reference languages, which most functional languages are, scale? Scaling in time and organisation? Does it scale from 6 months to 10 years and does it scale from 2 people to 50? I have my doubts for years and still ask anyone to show me how those languages scale. I really want to know. Others too. Manageability writes about Python and Chandler:
What I find interesting is that Chandler started as a Python project with bold claims such as “Python programs are both concise and readable, this makes it excellent for rapid development by a distributed team” and “Chandler design goals: … design a platform that supports an extensible modular architecture”. I was hoping to see this project as a testament to Python’s viability to large scale development.
The jury is still out, but I wouldn’t bet on scalability. As a project manager during the 90s two of my projects didn’t scale and had to be rewritten, one in Python and one in Perl. But it could just be me.
What happend to Haskell and Erlang, the functional hypes of 2006 and 2007? The Blogosphere has mainly lost interest in those lately. Scala and F# seem to be en vogue in our days. Arc perhaps is next in line to be en vogue. Certainly after Scala, which is next the next thing after Java as Bruce Eckel claims. What has changed from the days of Lisp 50 years ago I asked. Scala and F# are different from Haskell, Erlang - and Lisp. They build on an a proven plattform, on libraries that people know. Scala mostly on the JDK and Java ecosphere, F# on the Microsoft universe and .NET. They both are the most promising functional candidates when it gets to momentum. The transit for C# and Java developers seems to be easiest compared to other languages. Will that be enough for them breaking through into the mainstream?
Will the release of Arc, written as a pet project by Paul Graham the greatest functional rock star, help with functional programming? No, certainly not. Arc lost it’s appeal even before it was released. While waiting for the Arc blessing, people moved on to Scala, Erlang or F#.
Don’t kid yourself. There will be no rise for application and especially enterprise development in functional programming (See what happens when you use a Perl script to do your billing, not that I haven’t screwed up in the past with Java ;-) Which doesn’t mean to stop using functional programming languages. It’s fun, keep going.
Thanks for listening.
I’ve recently started to read the best book on object oriented programming. There are other good books that deepen your understanding of OO like “Refactoring” and “P of EAA” from Fowler, “Design Patterns” from the GoF, the McConnell books, “The Pragmatic Programmer”, the OO books from Robert C. Martin and some others. All recommended to read. But the best I’ve read on OO in the last 15 years is Domain Driven Design from Eric Evans. There are a lot of deep insights about how to build your domain model and structure your objects and classes in that book. Highly recommended.
January 15, 2008
Thanks to all the regular readers of this blog for listening. I know 200 is not as many readers as others have, but I’m thankful for everyone of you (including those with comments who prove me wrong :-)
For those interested the FeedBurnger graph for 2007:
For post listed on DZone the daily readership peaks to 1000-2000.
January 14, 2008
Adding to my last post about BigDecimal and money, and why to never use double, I discovered a BigDecimal Cookbook for financial calculations. Splendid.
Update:: Found The Need for BigDecimal for money caluclations and Representing money.
January 11, 2008
The discussion on how to represent money in applications pops up regularly . Funny lots of people still use double to represent money. During my interviews some people use double for money. Once and for all: Do not use double. Double cannot represent all amounts of money and it has rounding problems. Use a Money class. Represent the amount with a BigDecimal in cents and use BigDecimal.ROUND_HALF_EVEN as your rounding method. Use a distribute algorithm to distribute money to severel slots without losing cents.
Read more about a money class from Martin Fowler or this TSS discussion. Anders writes about Money in .NET.
Rant off. Thanks for not using double anymore.
January 9, 2008
Qi4J is the new kid on the block. Forget Scala (not although but because Bruce Eckel, the author who switches hypes faster than other people switch their underware, declares Scala to be the next big thing). Scala helps you solve CS problems nicely, but not business problems. Qi4j is about composite oriented programming. It’s designed to solve business problems. One of the brains behind Qi4J is Rickard Öberg, the brain behind JBoss. He is one of those geniuses who know that their cleverness hasn’t anything to do with the language they use. Other devlopers think that the tools they use make them into a genius (by association) and dismiss Java in favour of Ruby or Lisp or OCaml or Haskell or Lua. Some even think that Java spoils you for everything. What?
Another of those geniuses is Bob Lee, about whom I said in my Sourcekibitzer interview: “He wrote Dynaop, the best AOP for Java, Guice and now is part of the promising Web Beans project. A very friendly and extremly clever guy - swimming outside the mainstream with better ideas until all others get it too ;-) His style of coding looks aesthetically very pure to me and I like it very much.”[1] I guess the same thing could be said about Rickard.
Back to Qi4J. Why could Qi4J be the next Java? Qi4J tries to solve one of the holy grails of computer science: reuse. Their goal is to create applications by composing, not by writing code. Their solution is to decompose Java objects into fragments. This happens in two dimensions. Horizontally objects are decomposed into mixins. Vertically objects are decomposed into mixins, concerns, constraints and side effects. By splitting a Java class into much smaller fragments with specific roles they hope to increase the reuse of those fragments. So one does no longer write code but compose those fragments into bigger composites.
- Mixins: Containing state, e.g. Name, Person, Adress
- Concerns: Statelessm e.g. TransactionWrapper, Security
- Constraints: Checking parameters, e.g. NotNullConstraint
- SideEffects: Managing side effects, e.g. sending Mail
An example for a PersonComposite could look like this:
@Concerns({Security.class, Transaction.class})
@SideEffect({MailNotification.class})
public interface PersonComposite
extends Person, Name, Adress, Composite
{
}
The PersonComposite is build from a Person (handling e.g. gender), a Name (handling firstName and lastName) and Adress (handling street). The extension of Composite doesn’t look that nice, perhaps they change this in the future. A developer can now use PersonComposite and call getFirstName() and getLastName() on the composite. If he creates an Employee class he can compose it the same way and reuse Name. For storing a House he can reuse Adress.
Qi4J provides standard fragments like a PropertyMixin. With this mixin your Name only needs to look like this:
public interface Name
{
public void setName(@NoEmptyString String name);
public String getName();
}
and Qi4J will fill in the actual state-handling code.
Why is Qi4j probably the next Java? Java is an enterprise language. It solves enterprise problems best (technical, deployment and organisational/ socialogical problems). Other languages solve time-to-market-VC-funded-startup problems best. Still other languages solve computer science problems best. The next language needs to solve my enterprise problems better than Java does, which means fixing Javas holes. One hole is reuse, one is tight coupling, one is dependencies. JavaNG needs to solve those. Does Qi4J help? I might think yes. It has nice ideas and adresses some of the Java problems I have in the enterprise. If DDD takes off, Qi4J or frameworks like Qi4J will take off too.
Qi4j has lots of other goodies I’ll explore in another post.
Thanks for listening.
[1] Beautiful code doesn’t depend on the language. I like modern art. I can see beauty in modern art. Not in all, but in some. I’ve argued with a lot of people who do not see beauty in modern art. Those people believe only using oil on canvas drawing people can create beauty. The same goes for the argument that you need a special language to write beautiful code. You do not. I believe there is beautiful Cobol code around. And I wrote such beautiful programms in 68k.
December 22, 2007
I’ve been playing around with Firefox 3 Beta 2 on my MacBook Pro. Excellent browser so far. The Proto theme looks nice and solid, but the main thing is: Version 3 feels much faster than 2. The rendering is faster as is the user interface. And they took the url completion from Opera, one of the things I really like about Opera (my current browser). One other thing which moved me to Opera are the memory leaks with FF (which have gotten much better with FF3 too). So Firefox 3 might win me back. Only missing the splendid bookmark bar syncing in Opera. It just works from home to work while the Google FF plugin for bookmark syncing is awful.
December 4, 2007
I wrote about fluent interfaces for several times. A comment on my best MarkupBuilder in Java try pointed to a fluent inteface for JAXB. Excellent, thanks Hristo.
November 30, 2007
Using Groovy MarkupBuilders spoiled me for other ways to create HTML pages from code. Others think the same. But in some organizations you have to use Java and can’t use Groovy - at least when you can’t sneak it in.
So I tinkered around in Java to see what’s the best MarkupBuilder I can write with Java. Using DSLs and Fluent Interfaces (times(5).loop), I came up with a nice solution. It’s not Groovy, but it works.
Page page = page(
html(
body(
// A comment
h1("Name games"),
p("Hello ${coolName}, and hello", "id:${id}"),
ul(
new Loop("stefanie", "${name}") {
protected Element each(String item) {
return li(item);
}
}),
loop("[${number}] ", "number", 1, 2, 3),
text("..."),
box("Warning private!"),
p("Are you dynamic?"),
// Some dynamic content
new Action() {
protected String with(Context context) {
return "I'm dynamic, " + context.get("name") + ".";
}
}
)
)
);
There are some tricks to make it better than most such Markup Builders in Java. I tried to use ideas from building DSLs in Java. Those are using static imports and varargs. The body, html and other elements are static imports from a MarkupBuilder class.
public static Element body(String body) {
return new Element("body", body);
}
public static Element body(Element... elements) {
return new Element("body", elements);
}
...
The varargs helps with adding a variable number of childs to an element:
h1(
p("One"),
p("Two"),
p("Three")
);
Another problem is how to put object values into the generated markup. String concatenation leads to noisy code
"Hello " + name + "!"
so I decided to use a expression language where the Java unified expression language comes to mind. There is an open source version available called JUEL. Now I can use
"Hello ${name}!"
Attributes are also treated as expressions and seperated by commas, their names and values seperated with a colon.
p("Hello ${coolName}, and hello", "id:${id}, class:list"),
Loop and Action classes allow for dynamic content.
ul(
new Loop("stefanie", "${name}") {
protected Element each(String item) {
return li(item);
}
}),
I’ve used the template design pattern for this, again with expressions, in a way Spring provides JDBC templates. Another nice idea is with static methods it’s also easy to develop custom, semantic tags, so the developer doesn’t need to know or see the actual HTML markup which is created. For example I used a box “tag” which translates to
public static Element box(String text) {
return div(
p(text)
);
}
Closures in Java 7 will make it much easier to write a MarkupBuilder. The Action and Loop inner classes will go away and the code will be more Groovy like. When they add syntactic sugar to create maps I can drop the “name:value, name:${value}” style for attributes and move to [ "name" : value, "name": value ] instead, which doesn’t need the EL to work. With some small things to add the MarkupBuilder can be used for JSON or XML.
I’m interested and open to all techniques and ideas to improve the markup builder.
Thanks for listening.
November 27, 2007
People most of the time use business logic in their templates, be them JSP, Velocity or Rails. They confuse business logic and UI logic. Those are two different things. I always found it very useful to make UI logic explicit and only have UI logic in my JSPs or templates. So when using IF JSTL tags only test for UI logic not business logic. The examples are for JSP, but nevertheless are valid for other templating engines like Rails or Velocity. Where is the difference between UI and business logic?
<c:if test="${showMenu}">
// show menu
</c:if>
and
<c:if test="${user.loggedIn && user.bookedProducts}">
// show menu
</c:if>
The first example contains only UI logic, the second one contains business logic and should be avoided. With the second version your templating code is depending on your business layer. This makes it hard to refactor or reuse. Somewhere in the controller or an adapter it’s best to translate your business logic to UI logic
boolean showMenu = user.loggedIn() && user.bookedProducts();
Such a sepration makes refactoring and reuse easier and encapsulates the rules how business logic maps to UI logic in one place. You could even write the mapper with rule engines. It also eases the understanding of the template code. Often when using business logic in their templates, people use copy & paste to reuse the logic. So the user.loggedIn code gets distributed over lots of templates. If the logic changes so the menu should only be show for paid users, you need to modify all templates where the logic is used.
<c:if test="${user.loggedIn && user.bookedProducts && user.hasPaid}">
...
</c:if>
(I know about components, sub-templates etc. but people nevertheless use cut & paste for reuse. So make sure they cut&paste the right things)
When externalizing business-to-UI logic into seperate classes, it’s also much easier to test.
public class UserUIState {
private User user;
public UserUIState(User user) {
this.user = user;
}
public boolean showMenu() {
return user.loggedIn() && user.bookedProducts();
}
}
can be easily tested from a Unit test.
User user = with().isLoggedIn().addProduct("Intellij IDEA").create();
UserUIState state = new UserUIState(user);
assertThat( state.showMenu(), is(true));
The test uses fluent interfaces to create a user and a pseudo Hamcrest DSL to specify assertions. The assertions would be nicer written as specs with easyb.
Another aspect of templating is the power of the templating engine. Turing completeness is not a good thing for templating as the power introduces bugs. Less power leads to less bugs. Examples for engines who make this a virtue are String Template and RIFE. The same goes for variables. Never set variables in templates. Never modify state in templates. The best paper on this topic is Terence Parrs
“Enforcing Strict Model-View Separation in Template Engines”.
And of course never use Scriptlets in your JSP or other templating code, the main reason that the developer has to manage two hierarchies in her head. The <html> on one side and the Java { ... } hierarchie on the other.
<% if (loggendIn) { %>
<p>Logged in<p>
<% } %>
With larger pages this leads to bugs. With only one <html> hierarchie, your IDE is able to verify the hierarchie at edit-time which prevents invalid HTML.
You can enfore these rules with code reviews or automatic style and architecture checkers. Probably best to use both to reduce your bug count and enable reusability.
Thanks for listening.
Update: Gavin King got me wrong. Reading simple attributes like "test=${user.loggedIn}" doesn’t contain a lot of “logic” so it’s no must to encapsulate the logic and it leads to unnecessarilly complex code. YAGNI. But "test=${user.loggedIn && user.hasBookProducts && sales.hasPromotion(user)}" does contain logic which should be encapsulated and tested. Perhaps I’m a stronger believer in TDD than Gavin. I wanted to stress that there is a difference between UI and business logic and a lot of people don’t see the difference.
November 23, 2007
When reading about reflection on the beautiful code website I thought about solving some problems with reflection and finding new solutions to old problems. One problem is boring code when writing a copy constructor. A copy constructor is a constructor which takes another object and copies it’s attributes. This is often useful when copying objects or moving objects to different system layers. One example would look like this:
public class Employee {
public Employee(Employee other) {
this.name = other.name;
}
}
There are some pitfalls, especially that you only create shallow copies. And there is always clone() and Serializable, which can also be used to create deep copies without such pitfalls. JBoss provides a fast implementation of this technique. But often copy constructors are quite useful if you’re careful and know what you do. I recently had a discussion on how to support domain objects in different parts of a system. One part might call an entity Employee, another part might call it Person. To make them talk together you can either create a composite, an adapter, a wrapper or use a copy constructor (or find a different solution). In such a case a shallow copy is all you want, because the new object should have the same “identity” as the first and not be a copy.
public class Employee {
public Employee(Person person) {
this.lastName = person.getLastName();
this.name= person.getFirstName();
}
}
This should be easier to implement. Copying bean attributes for large objects isn’t much fun, leads to long constructors and unmaintanable code. What about changes in Person? New attributes? So I tinkered with Java reflection and ended with this:
public Employee(Person person) {
BeanCopier copier = new BeanCopier();
copier.copy(person, this, "name:firstName", "age:");
}
I’ve written a BeanCopier which can - well you guessed it - copy beans. The syntax is easy to learn. A BeanCopier has a copy method which takes a source, a copy and the attributes which should be specially handled. By default all attributes which have the same name and type in source and copy are copied. But if they have different names, like name and firstName, you need to specify “name:firstName”. If a property shouldn’t be copied, you can specify “property:” without a target attribute.
The copy method looks like this (the generics are not needed but I was also tinkering with caching where it was quite handy):
public <T, U>void copy(U source, T destination, String... attributes) {
if (destination.getClass().getName().equals(source.getClass().getName())) {
// copy all fields
} else {
// copy all bean properties
try {
BeanInfo sourceInfo = Introspector.getBeanInfo(source.getClass());
PropertyDescriptor[] sourceDescriptors = sourceInfo.getPropertyDescriptors();
for (PropertyDescriptor descriptor : sourceDescriptors) {
String name = descriptor.getName();
if (!"class".equals(name)) {
String attribute = this.find(attributes, name);
if (attribute == null) {
copyAttribute(source, destination, name);
} else if ((attribute.indexOf(':') >= 0) && !attribute.endsWith(":")) {
int colonIndex = attribute.indexOf(':');
String sourceName = attribute.substring(0, colonIndex);
String copyName = attribute.substring(colonIndex + 1);
copyAttribute(source, destination, sourceName, copyName);
}
}
}
} catch (IntrospectionException e) {
e.printStackTrace();
}
}
}
and the copyAttribute method:
private void copyAttribute(Object source,
Object copy,
String sourceName,
String copyName) {
PropertyDescriptor writer;
PropertyDescriptor reader;
try {
writer = new PropertyDescriptor(copyName, copy.getClass());
reader = new PropertyDescriptor(sourceName, source.getClass());
Object value = reader.getReadMethod().invoke(source);
Class sourceType = reader.getPropertyType();
Class destionationType = writer.getPropertyType();
if (sourceType.getName().equals(destionationType.getName())) {
writer.getWriteMethod().invoke(copy, value);
}
}
The code is rough but works. The type test can be improved to work with super types.BeanCopier can be used outside of constructors, often a wise choice. And be careful with “copying” other objects, you might only create a shallow copy.
Of course, I could have taken a look at commons BeanUtils, but isn’t it much more fun to tinker and find a nice solution yourself sometimes?
Thanks for listening.
November 12, 2007
As several people pointed out in my last post that my version of reversing a string with recursion wasn’t tail recursive despite the fact that I wrongly thought it was. Not that it’s important in the context of a job interview for Java developers, whether one uses tail recursion or not. But I thought nevertheless about a Java tail recursive solution. Reading more about tail recursion in several articles and the comments of the last post, I wrote a new version of the String reversal solution. This time with tail recursion. So as a service to the interested reader:
public String reverse(String str) {
if ((null == str) || (str.length() <= 1)) {
return str;
}
return reverse(str, "");
}
private String reverse(String str, String acc) {
if (str.length() == 0) {
return acc;
} else {
return reverse(str.substring(1), str.charAt(0) + acc);
}
}
Tail recursion means, the last call in the recursive function is a call to the function and there is nothing left to do when the recursive call returns. Why tail recursion? With tail recursion it’s easy for the compiler to remove the recursion and drop the growing stack. So with an optimized tail recursive function you will not run out of stack space what you otherwise would quite easily.
Update: For comparison the non-tail recursive solution.
public String reverse(String str) {
if ((null == str) || (str.length() <= 1)) {
return str;
}
return reverse(str.substring(1)) + str.charAt(0);
}
Update 2: The call stack for the recursive solution for “ABC” would be:
-> reverse(”ABC”)
-> reverse(”BC”) + ‘A’
-> (reverse(”C”) + ‘B’) + ‘A’
-> (”C” + ‘B’) + ‘A’
-> “CB” + ‘A’
-> “CBA”
and for the tail recursive version:
-> reverse(”ABC”, “”)
-> reverse(”BC”, “A”)
-> reverse(”C”, “BA”)
-> reverse(”", “CBA”)
-> “CBA”
Comparing those two the first one increases the stack to a point until it starts to pop the stack. The tail recursive version does not use the stack to keep a “memory” what it has still to do, but calculates the result imediatly. Comparing the source though, in my view the tail recursive version takes all beauty out of the recursive implementation. It nearly looks iterative.
Someone has read my post about interviewing where I wrote about String reversal, but got it totally wrong. Ironic. He didn’t show much attention to detail, took quotes out of context, put things into my mouth that I’ve never said and concluded “Want a job? Reverse a string. The sad state of job interviews today.” This post even got to DZone. So my post could also be titled: The sad state of DZone today.
Most of my interviews are 1h to 1.5h and sometimes 15 minutes of the interview is about reversing a String. This is mainly to get into the thinking of the candidate, see how he deals with fringe cases (null values as arguments) and if he chooses a JDK reverse method or not. Jonethen didn’t pay much attention to detail, so for a starter he got my name wrong, it’s Stephan not Stephen. A minor detail but a sign for what was to come later in his post and the comments.
Jonathan is angered by my mentioning of the recursive version of reversing a string. Although I wrote why I think it’s interesting to discuss a recursive solution, he ignores my arguments and writes
“.. only that he would be much more impressed if someone did write it out.”
I didn’t say that.
“He would probably give higher preference to someone who did use that technique,…”
No I won’t and I didn’t say that either. I said “The best implementation in Java is to use the reverse method of the StringBuffer class in the JDK.” I specifically pointed out that the reverse version is impractical in Java for the immutable String class alone, not to mention the surrogate pairs problem. So to make myself clear again, the best solution is to use the reverse method of the StringBuilder class. Any candidate who uses this method has already impressed me, because from my experience very very few developer know this. Most would write some kind of array swap method. But it’s not the cause I ask this question. It’s to see if someone can write code (which doesn’t need to be compiler ready, he’s no IDE in the end) and get into a discussion about programming, unit testing, fringe cases, how to handle errors, quality assurance and other topics. And if someone has read this blog? Or another blog? And knows the answer? Well good, the answer is just the beginning. And considering that very few developers read blogs and articles to learn something new, I’m happy to interview a candidate who reads blogs in general.
Without getting personal, I look for more attention to detail in the candidates I have than Jonathan did when he did shred my post. And I look with far more attention to detail into candidates than Jonathan did use when reading my post. Ironic.
One poster in the comments of Jonathans post suggested using StringBuilder instead of StringBuffer, because StringBuilder is not synchronized and faster therefore. I think modern VMs can use escape analysis to detect synchronized blocks or methods which can be optimized away, as in the local usage of StringBuffers. There should be no difference between StringBuffers and StringBuilders in modern Java VMs. But it doesn’t hurt to use StringBuilder.
Ending his article: “If a interviewer wants to talk about my past projects with me, then it should not take him long to realize that I am a competent.” Or read a blog, as Jonthan suggested in Blogging gets people hired.
Hopefully he doesn’t read your blog.
Peace
-stephan
PS: I wish I don’t sound the least bit like Hani ;-)
November 11, 2007
Lately I wrote about interview questions, specifically about asking how to write a String reverser method. When searching for a job as a PR-consultant my girl friend was sent a PDF to answer questions - which I guess the company uses to gather fresh ideas - and she had to send the answers back written in the PDF. This got me thinking.
If you have lots of candidates for a programming job, screening them online might safe you some time. You could ask the candidates to write some code, for example “to reverse a String”. How do you determine if the answer is correct? Write a unit test. How do we execute code the candidate entered into a form? Just use a compiler. Janino is a Java compiler which can compile Java source code that it reads from a String:
import org.codehaus.janino.SimpleCompiler;
import java.io.StringReader;
public class Evaluator {
public static void main(String[] args) {
String source =
"import java.util.*;\\n" +
"public class MyReverser implements Reverser {\\n" +
" public String reverse(String str) {\\n" +
" return new StringBuilder(str).reverse().toString();\\n" +
" }\\n" +
"}";
try {
SimpleCompiler compiler =
new SimpleCompiler("Test", new StringReader(source));
Reverser reverser =
(Reverser) compiler.getClassLoader().loadClass("MyReverser").newInstance();
System.out.println(reverser.reverse("Stephan"));
} catch (Exception e) {
e.printStackTrace();
}
}
}
You present an input form, protected with a token you’ve sent the candidate. Making the job easier, you can provide a syntax highlighting editor like codepress. When he enters the code, Janino compiles it, runs a JUnit or TestNG test and tells the candidate if his code is correct or not. Obviously people will cut and paste code into the box when you ask for the answer to a simple problem like string reversal (Google is just one click away). But asking the candidate a more tricky question, which he cannot google might work. Like ask them to write an elevator simulation (state machine with several elevators) and test the result with a unit test.
Even better you could also make them write code to satisfy a Fitnesse story. With fitness it’s easy to add further constraints to the test and you can ask the candidate to extend the test with constraints he considers necessary. Make him write his tests too ;-)
The nice thing with Java, compared to Ruby and PHP, is that Java has a fine grained security concept. With a Java security manager you can make this application safe by preventing access to file and system resoures and still execute the code the candidate entered into the form. The same goes for other languages on top of the VM. So for asking Ruby questions you can use JRuby.
Hope this gives you some ideas about asking interview questions online.
Thanks for listening.
November 9, 2007
Interviewing developers for a programming job is hard and tedious. There are some excellent Guides, like the Joel Guerilla Guide to interviewing, but in the end you need to decide yourself to hire or not to hire. To get a quick idea about their programming abilities I have considered asking the String reverse question. Others have used this question with some success. There are lots of answers to this question which gives you room to explore the candidates skills. Thinking about this myself, I found some answers on how to reverse a String in Java. The answer the candidate gives is a good way to see how he thinks. You could combine this question with one about interfaces and ask for a reverser interface:
public interface Reverser {
public String reverse(String str);
}
The best implementation in Java is to use the reverse method of the StringBuffer class in the JDK. It’s fast, efficient and knows how to handle unicode surrogate pairs, something most other solutions ignore.
public class JdkReverser implements Reverser {
public String reverse(String str) {
if ((null == str) || (str.length() <= 1)) {
return str;
}
return new StringBuffer(str).reverse().toString();
}
}
Not only is the chosen implementation interesting as an answer, but also does the candidate reuse the JDK or not or does he tell you at least “there has to be something in the JDK”. Which is quite as good, because googling in reality will help him find the JDK solution. You don’t want developers to implement everything themselves.
Handling problems
Ask him where the bug is in this code, even if there is none. Or how his code can go wrong. His answers can lead into a discussion about how to handle a null value
- return null
- return “”
- throw NullPointerException
- throw IllegalArgumentException
and the merits of every solution. The second discussion point is how to optimize the solution, like returning the string itself for “” and every one length string (which is a reversal of itself already).
Recursion
Then ask the candidate to write a recursive solution of the reversal problem (which is the most beautiful but least usable one).
public String reverse(String str) {
if ((null == str) || (str.length() <= 1)) {
return str;
}
return reverse(str.substring(1)) + str.charAt(0);
}
Some developers can’t handle recursion in their head. Most candidates will need some time and some help, but actually get to a solution. Those that can’t handle several stages of recursion in their head probably can’t handle complex problems or several layers in their head either.
You can ask them about the efficiency of the recursive solution, ask about Tail Recursion, ask about the ineffeciency of the “+” operation for Strings, how to handle that, about why Strings are immutable (most of the time at least) and ask the candidate how many String objects are created for reversing “Stephan” with his recursive solution. When discussing this one of my developers said “Easy”, he was doing Lisp at the university the whole time, which I didn’t know until then, excellent news!
Ask where the stop condition is in the above code to end the recursion.
More solutions
Some more solutions, one with swapping a StringBuffer in place:
public String reverse(String str) {
if ((null == str) || (str.length() <= 1 )) {
return str;
}
StringBuffer result = new StringBuffer(str);
for (int i = 0; i < (str.length() / 2); i++) {
int swapIndex = str.length() - 1 - i;
char swap = result.charAt(swapIndex);
result.setCharAt(swapIndex, result.charAt(i));
result.setCharAt(i, swap);
}
return result.toString();
}
One with swapping an array:
public String reverse(String str) {
if ((null == str) || (str.length() <= 1)) {
return str;
}
char[] chars = str.toCharArray();
int right = chars.length - 1;
for (int left = 0; left < right; left++) {
char swap = chars[left];
chars[left] = chars[right];
chars[right--] = swap;
}
return new String(chars);
}
and one with appending to a StringBuffer:
public String reverse(String str) {
if ((null == str) || (str.length() <= 1)) {
return str;
}
StringBuffer reverse = new StringBuffer(str.length());
for (int i = str.length() - 1; i >= 0; i--) {
reverse.append(str.charAt(i));
}
return reverse.toString();
}
}
Perhaps the candidate even knows about the tricky XOR swapping solution.
From there it’s an open field. You could ask the candidate to write a JUnit test for his reverse method. Not only can he show how to write a unit test, but what he considers as test cases (”", null, “A”, “Even”, “Odd”, ….).
I hope this helps you in your decision with hire or no hire. And I hope it helps me in the future to decide this question for myself. As Joel said: when in doubt, always no hire.
Thanks for listening.
November 4, 2007
Alex wrote in his latest Java 7 Roundup about my idea of a @license and Paul’s @copyright addendum. I wrote about the idea here.
@License(name = "Apache",version = "2.0")
@Copyright(owner = "Stephan Schmidt")
public class Example {
public void doWhatever() { ... }
}
In the comments of that post Paul Hammant mentioned a @copyright annotation, which could help verify the copyright status of code. The best and easiest way to use @license and @copyright would be to add it at the package level. Few people know that Java got a package level construct called package-info.java where developers can add package level annotations:
“Typically package-info.java contains only a package declaration, preceded immediately by the annotations on the package.”
Hopefully such an annotation would be implemented as a Java standard and used by all major DI containers like Spring, Guice and Apache Composer, because as I wrote in the comments:
“A container could know about licenses and issue a warning when injecting incompatible stuff. This would make some managers in companies happy.”
As I want to pursue the idea further, it would be best to move this with a short JSR into Java 7.
