Dart, an effort from google to liberate the Web

I enjoy writing javascript code, but to be honest, the fact that javascript has no types, and anything imaginable is a valid code in javascript – therefore not much productivity tooling is possible – makes me not a fan of it for serious development.

I may dislike JS for serious development sometimes, but there are times that I truly hate JS!

When I say I sometimes hate JS, I am not joking, and it is not related to the features and looks of the language either. The sole reason for my feeling is that JS is the “Dictator” of the web. It imposes itself on you! It doesn’t care if you believe it is the right tool for your job or not, you “have to” love it! It kicked flash out, killed other competitors and now, it is the sole ruler of the web. The great dictator of the web if you like. And I hate dictators, even if they are not evil.

As is the case in any other dictatorships, there are liberating movements here and there. Google have been a pioneer of such movement from the GWT times. Microsoft tried to challenge JS power with Silverlight, a move that was repressed quickly. Google acted smarter, it did not try to challenge the power of JS, it worked with it and tried to make JS to bend to democratic “reforms”. By chromium’s V8 and other efforts to improve performance of JS, it became possible to compile to JS.

I don’t think compiling JS would completely solve the problem (I would much rather we had some VM specifications for browser instead of a language), but it is the best hope for now. The proof is that in 2012, close to two decades from the first version of JS, we still don’t have a complex JS based product that works fine. Even the most expensive and sought after products fail supporting different browsers gracefully. Yahoo mail has a big team of best JS devs in the world working on it, and yet after years, it still sucks in Chrome.

Dart however, is a lovely language. It stands somewhere between strongly typed languages like Java and C#, and java script. It takes best of the two worlds and has a modern, but familiar syntax, which is quick to learn and coding in Dart needs close to zero boilerplating.

  main() {
    print("Hello world! From Dart!");
  }

What makes Dart different, is that it compiles to JS. It is designed to compile to JS from scratch. Hence, you could imagine it would do the job better than others.

Other things that make Dart different are that first, it is supported by google, and second it has a couple of nice IDEs from start. Google support makes me believe Dart has a future (a bright one maybe) and good tooling makes it useful from the earliest version.

In the next posts, I will talk about some libraries I have developed for Dart. And in the future I would use Dart more often.

How to run most of the recursive functions iteratively!

A Helper to run recursive functions iteratively

Last night I wanted to write an iterative binary tree traversal algorithm. I first wrote it recursively, but I struggled to translate it to iterative! I was mentally exhausted. I had only 3 hours of sleep the previous night and I was up for more than 12 hours, so I decided to draw a tree to get some visual help. When I gazed to my tree, I realized nodes are doing marshal art! I eventually couldn’t come up with the right solution after half an hour of trying to convince my brain to get up. This morning when I woke up I thought about the problem again and I solved it in 10 seconds. I am not here to talk to you about how to make the tree traversal iterative, I want to tell you how to make many recursive functions iterative.

I decided to write a helper, such that next time I wanted to convert a recursive function to iterative even if I was sleep, be able do it with closed eyes. Although this helper may not work for all cases it works for many common ones.

Why do we want to make a recursive function iterative?

There are two answers to this question. First answer is simply performance. For simple solutions the iterative functions performs much better than the recursive one due to the overhead of function calls and stack operations. For more complex solutions though, this overhead can become negligible comparing to the actual work done at each recursive step.

Second reason for making a recursive call iterative is to avoid Stack Overflow. I am talking about the exception you get when the function call stack is full, not the website that you can ask programing questions.

I can’t help you with the first problem, but I can help you avoid stack overflow.

How to make it iterative?

There is an straightforward way to translate recursive functions to iterative ones using a stack. Basically by simulating what actually happens at machine level with an object which we call the RecursionHelper.

First divide your recursion code to subrecursive chunks. Generally a recursive function has three parts: Termination condition, recursive calls, and stuff to do on the current object. We have to divide the function into steps. For example consider recursively calculating sum of the items in an array:

int Sum(int index, int[] array)
{
 if (int >= array.Length) return 0;

var sumofrest = Sum(index+1, array);
 return array[index]+sumofrest;
}

Let us divide the above recursive function to its steps:

int Sum(int index, int[] array)
{
 //This is the termination condition
 if (int >= array.Length)
 //This is the returning value when termination condition is true
 return 0;

//This is the recursive call
 var sumofrest = Sum(index+1, array);

//This is the work to do with the current item and the
 //result of recursive call
 return array[index]+sumofrest;
}

Now send all this steps to the Recursive Helper:

int Sum(int[] ar)
{
 return RecursionHelper<int>.CreateSingular(i => i >= ar.Length, i => 0)
 .RecursiveCall((i, rv) => i + 1)
 .Do((i, rv) => ar[i] + rv)
 .Execute(0);
}

First line creates a recursionHelper and passes in the termination condition. Here termination condition is if i>= ar.Length, and if the condition is true function i => 0 will execute and 0 is returned.
The next two lines are definition of the recursive function divided into steps: Recursive call, which calls the function recursively with i+1, and the result comes back as “rv” for the next step. The “Do” steps does some work and returns (or doesn’t return) some result which can be accessible by other parts of the function. In this case our function definition is finished.
The Execute methods starts the recursive call with initial value of 0.

Let us do this with the binary tree in-order traversal problem:

 void PrintTreeNodes(Node node)
 {
 if (node == null) return; //Termination condition
 PrintTreeNodes(node.Left); //Recursive call 1
 Console.WriteLn(node.Value); //Do stuff
 PrintTreeNodes(node.Right); //Recusive call 2
 }
 

With RecursionHelper:

 void PrintTreeNodes(Node root)
 {
 RecursionHelper<Node>.CreateSingular(n => n == null)
 .RecursiveCall((n, rv) => n.Left)
 .Do((n, o) => Console.Write("{0},", n))
 .RecursiveCall((n, o) => n.Right)
 .Execute(root);
 }
 

The first line sets up the termination condition (n==null). It does not return anything because it is a void function. Next three lines call recursive functions and do the job. Eventually execute runs the function with initial value of root.

You see it is pretty easy to convert any recursive function to iterative. You don’t have to change any code. You should only wrap each nonrecursive part in a Do method and change the recursive call with RecursiveCall method.

Here is the code for RecursionHelper<T>:

 public class RecursionHelper<T>
 {
 private readonly List<Tuple<Func<T, T, T>, bool>> _steps = new List<Tuple<Func<T, T, T>, bool>>();
 private readonly Stack<Tuple<T, int>> _stack = new Stack<Tuple<T, int>>();
 private Func<T, bool> _terminationCondition;
 private Func<T, T> _terminationOperation;

/// <summary>
 /// Creates a single stack recursion manager.
 /// </summary>
 /// <typeparam name="TR">Type of item to recurse for</typeparam>
 /// <param name="terminateCondition">The terminate condition.</param>
 /// <param name="terminationOperation">Operation to run in case termination was true.</param>
 /// <returns></returns>
 public static RecursionHelper<T> CreateSingular(Func<T, bool> terminateCondition, Func<T, T> terminationOperation = null)
 {
 var rv = new RecursionHelper<T>
 {
 _terminationCondition = terminateCondition,
 _terminationOperation = terminationOperation
 };
 return rv;
 }

public RecursionHelper<T> RecursiveCall(Func<T, T, T> func)
 {
 addStep(func, true);
 return this;
 }

public RecursionHelper<T> Do(Func<T, T, T> func)
 {
 addStep(func, false);
 return this;
 }

public RecursionHelper<T> Do(Action<T, T> action)
 {
 addStep((i, o) =>
 {
 action(i, o);
 return o;
 }, false);
 return this;
 }

private void addStep(Func<T, T, T> func, bool isRecursive)
 {
 _steps.Add(Tuple.Create(func, isRecursive));
 }

public T Execute(T initialItem)
 {
 var currentItem = initialItem;
 var currentResult = default(T);
 var currentStep = 0;
 while (true)
 {
 var recursiveContinue = false;
 if (currentStep == 0 && _terminationCondition(currentItem))
 {
 currentResult = _terminationOperation(currentItem);
 }
 else
 for (int index = currentStep; index < _steps.Count; index++)
 {
 var step = _steps[index];
 if (step.Item2) //Step is recursive
 {
 _stack.Push(Tuple.Create(currentItem, index + 1)); //Push the current position and value
 currentItem = step.Item1(currentItem, currentResult);
 recursiveContinue = true;
 break;
 }
 currentResult = step.Item1(currentItem, currentResult);
 recursiveContinue = false;
 }
 currentStep = 0;
 if (!recursiveContinue)
 {
 //Once a function has finished it works, pop the stack and continue from where it was before
 if (_stack.Count == 0)
 return currentResult;
 var stackPopped = _stack.Pop();
 currentItem = stackPopped.Item1;
 currentStep = stackPopped.Item2;
 }
 }
 }
 }
}

A little puzzle

A chicken and a half lay an egg and a half in a day and a half. How many eggs would one chicken lay in three days?

Help: 3 is not the correct answer.

Simple Workflow Engine

In the last post I talked about a workflow engine to define workflows over object quickly and efficiently.

Last night I had some time and implemented the basics of the engine. The lamp example in the previous post works and the code I wrote tend to be really simple and small.

The project is hosted in codeplex (http://swengine.codeplex.com/). Download it and play with it.