Kungfuice.com

So I’ve been reading “Programming in Scala” by Martin Odersky, Lex Spoon and Bill Venners and I’ve been coming up with ways to get myself thinking and programming more in Scala.  Since I spent a better part of my week interviewing people I thought I’d take some time to write the famous “Reverse a String” interview question.  This is a pretty straight forward thing to do and thought it would be fun to experiment with some of Scala’s other cool features to get my feet wet.

On my first attempt I wound up with my usual tail-recursive implementation that makes use of an accumulator.

/**
 * Wrapper function.
 */
def reverse(str: String) : String = {
      if ((str == null) || (str.length() <= 1))
          str
      reverse(str, "")
  }
 
 /**
   * tail call recursive with accumulator
   */
  def reverse(str: String, acc: String) : String = {
      if (str.length() == 0)
        acc
      else
        reverse(str.substring(1), str.charAt(0) + acc);
  }

This seemed pretty standard to me.  It doesn’t differ much from the Java implementation I’ve written a hundred times, nor is it really all that interesting.  I decided to jump ahead a few chapters in the book to see what I could accomplish using a left fold.  For those unfamiliar with what a fold left operation is I point you to the Wikipedia entry on it here.  The basic idea as stated in the book ”Programming in Scala“ is this: “A fold left operation (z /: xs) (op) involves three objects: a start value z, a list xs, and a binary operation op.  The result of the fold is op applied between successive elements of the list prefixed by z.”

Ok that seems like it applies very well to what we are trying to accomplish.  Rewritting the above methods into one clean line of Scala code yielded the following

/**
   * This will fold the list left, and should run in constant time allocation
   */
  def reverseLeft[T](xs: List[T]) = (List[T]() /: xs) {(ys, y) => y :: ys}

Pretty beautiful isn’t it?  It’s amazingly simple and achieves the same thing as the tail-recursive implementation.  I can’t express how excited I am to get through this book and really start doing real programming with Scala.

So I guess the next time you go for an interview try and remember this for the answer and see how the interviewers faces light up, either with glee or rage that you didn’t solve it using the standard recursive implementation

Until next time …

kungfuice Scala, Technology, programming Interview, programming, Recursion, scala

A co-worker sent this to me yesterday and I definitely had a good laugh since for many years I’ve joked about calling my kid “URL”, pronounced EAARRLLL.  I definitely think this name is a better though and could definitely lead to some very comical situations.

XKCD A Webcomic

I hope you all enjoy this, now back to work!

kungfuice Technology Funny, Technology

I’ve been working on some stuff that requires me to execute some long running tasks on a server from a web based client.  I really wanted to a way to let the user know what was going on, and I figured a progress bar would be the best way to let them know what was going on and how much longer it was going to be before the task was complete.

Using Ext-JS this task was actually a lot easier then I had originally thought. Ext has these two great classes called TaskRunner and TaskManager.  These classes basically allow you to create a task for execution in a multithreaded manner (we all know that JavaScript is only single threaded so this definitely will never be executed in parallel but we can all dream).  Here’s an example from the Ext API on how to setup a task to run a simple clock that updates every second.

// Start a simple clock task that updates a div once per second
var task = {
    run: function(){
        Ext.fly('clock').update(new Date().format('g:i:s A'));
    },
    interval: 1000; //1 second
}
var runner = new Ext.util.TaskRunner();
runner.start(task);

In my case I wanted to setup a task that would execute every 10 seconds and ask the server what the progress of my longrunning task was.  I then used the information returned from the server to update the progress bar on page.

//Create the success handler for the Ajax request
function successHandler (response, options) {
    if(response) {
        try {
           var json = Ext.util.JSON.decode(response.responseText);
        } catch (err) { return; }
        if (!json.done) {
           //update the progressBar by parsing the percentage updated
           //by the server and returned in the json response.
           percentage =json.results[0].strPercent;
           progressBar.updateProgress(json.results[0].percentage,
                                     'Task ' + percentage + ' Complete';
        }
        else { progressBar.updateProgress(1, 'Done'); }
}
 
var task = {
	run: function() {
		Ext.Ajax.request({
			url: 'mystatus'
			success: successHandler,
			params: { processId: processId }
		});
	},
	interval 10000; //10 seconds
}
 
var runner = new Ext.util.TaskRunner();
runner.start(task);

Now I’ve let some code out here for handling the failure case of the Ajax request and a couple of other functions for handling what I’m actually doing on the server but you can start to see that with the combination of the TaskRunner and the ProgressBar adding “background” worker threads to your interface becomes a lot easier.

Unfortunately this solution is not necesarilly optimal since the client will constantly be polling the server asking what’s going on.  A much better solution to this would be to implement a comet based service that allowed the server to merely report to the user its status and when it was complete.

Currently Ext does not have any comet handling functionality, but if you watch for my next post I’ll show how you can implement a comet based Servlet in Tomcat 6 and create a client that will listen for updates from the server.

kungfuice Javascript, programming

< ![endif]–>After the NFJS conference this weekend I have been spending more and more time working in Scala and trying to learn the ins-and-outs of the language.  One of the neat things I came across was tail recursive algorithm optimization within the language itself.

When writing in a functional language like Scala you rely heavily on recursive algorithms to do your work, instead of iterative algorithms more present in OO languages like Java. This leads to an interesting problem with running functional languages within the JVM.

The Java Virtual Machine does not have support for tail-recursive algorithm optimizations.  What does that mean? Basically the JVM cannot spot when to optimize calls stacks for recursive algorithms. Well who cares right? If you’re writing in Java this issue doesn’t usually come up since most of us simply write our loops and are happy with the performance the JVM offers us.

However, when you are writing a lot of recursive algorithms you quickly start to see how tail-recursive algorithms help makes your code more efficient.

For those of you who don’t remember what a tail-recursive algorithm is, here is a short little explanation:

“A Tail-recursive function is a function that ends in a recursive call to itself (effectively not building up any deferred operations). Tail recursive functions have the ability to re-use the same stack frame over and over and therefore are not bound by the number of available stack frames.  Many people have written the simple factorial function recursively, but many have noticed that if you pass it a value of N that is large enough you will see a dreaded Out of Memory exception.

The reason for this is due to the factorial functions deferred operation statement that comes at the end of the method. Let’s look at the simple factorial algorithm

1
2
3
4
5
6
7

//INPUT: n is an Integer such that n >= 1
int fact(int n) {
   if (n == 1)
      return 1;
   else
      return n* fact(n-1);
}

H You can see that at then end of the algorithm we have a deferred operation of multiplying n with the next value computed from factorial, this goes on and on until we finally hit a factorial function that returns one, at which point the stack is popped and everything returns nicely. However we are now bound by the available stack frames in terms of computing n (Also by the max size of an int, but that’s beside the point).

In a tail-recursive algorithm you do not see this deferred execution, and therefore the same stack frame can be reused over and over again. Here is the same algorithm rewritten using a tail-recursive algorithm.

1
2
3
4
5
6
7
8
9

//INPUT: n is an Integer such that n >= 1
int fact(int n) {
    return fact_support(n, 1);
}
 
int fact_support(int n, int acc) {
    if (n == 0) return acc;
    else return fact_support(n-1,acc*n);
}

As you can see there are no deferred operations in this example we have effectively gotten rid of having to use n number of stack frames. Each call to fact_support brings with it the current accumulated sum, and thus does not need to wait to “pop” the stack and rely on the stack pop to accumulate the sum of the factorials.

As you can see tail-recursive optimizations are very important to languages where recursion is relied on heavily. Without this type of optimization many of the recursive algorithms are now bound by the number of available stack frames.

So that can’t be so hard right? Why not just write all your algorithms to use tail-recursion? Well for one it’s not always possible to do this, but also it puts a lot of work in the hands of the developer. We have this beautiful thing called the JVM that should be able to spot cases where optimization can occur.

Unfortunately the JVM doesn’t know how to spot this optimization, therefore the Scala compiler must look at ways of optimizing your code. Even more unfortunate the Scala documentation explicitly states that you should not rely on the Scala compiler making this optimization.

It may optimize your code, but it may not as well, so really the only way to be sure is to write your algorithms guaranteeing that tail-recursion is being utilized from the get-go.

It would be really nice to see the JVM improved to allow for this type of optimization to be done in the Hotspot, and there has been talk about improving the JVM to support functional languages, but I guess time will only tell.

kungfuice Computers, java, programming algorithms, java, programming, scala

I’ve spent my weekend in Boston at the local No Fluff Just Stuff conference and I figured I’d write a little summary of what I observed and learnt over the weekend.

To start this was my first conference that I’ve attended besides some small ones while in College and University, and I have to say that it was both exciting and disappointing.

Heading into the weekend I was very excited to hear Brian Goetz and Ted Neward give talks about cool things like Java Concurrency, The Java Memory Model, Hacking the JDK, Scala etc, and I expected most people at the conference to be of the same mind set.

I found through talking with many attendees that most people seemed to share a different set of values as to what was important to them. I found this to be very interesting as it really showed me the difference between people who are developing for the “Enterprise” or big business and people like me who develop more for a technology based company.

When I heard people talking about Groovy and Grails I couldn’t understand why anyone would be so interested in a language that performed as poorly as Groovy (Yes I know it’s been getting better but when you start from incredibly slow, and move to just being a little less incredibly slow I hardly see this as an improvement) I started to see that there really is a difference between the enterprise developer and the developer.

I think this was an amazing aspect of this conference is that it really opened my eyes to the other side of the coin, to the developers that work hard to create the applications that we use every single day from our Banks, Insurance companies etc and the different set of requirements that their applications have to deal with then what I’m used to.

I also have to say that after this weekend I am VERY VERY glad to be working where I am. Some of the horror stories I heard from people as to how they have to work, the lack of tools support that they face, and an overall management’s lack of letting things change made me cringe in pain and a few times I just wanted to give them a hug to tell them that it would all be OK (Yes sometimes it really was that bad like the guy who told me they were still using Java 1.4.2 because his boss thought if it works don’t fix it!)

So after sitting back over the weekend and getting over the initial culture shock that I faced meeting a lot of these developers, I have to say that this conference helped me in a way I never thought it would.

Sure I learnt all about the Java Memory Model, and how I can modify byte code on the fly with tools like BCEL, but more importantly I learnt what other developers have to go through on a daily basis and what it’s like to be an Enterprise developer in the real world.

All I have to say to that is, thank god I don’t have to deal with that shit every day.  Overall though I definitely would recommend this conference to someone working in the Enterprise world, I definitely got value out of it though with my talks with Brian and Ted and I have to say that if they weren’t there this show definitely would of been a wash for me.  So thanks Brian and Ted for really opening my mind and eyes to some cool new ways of doing things.

kungfuice Computers, java, programming Boston, Computers, Conference, java, NFJS 2008, No fluff just stuff, programming