Easiest way to remember Covariance and Contravariance

I have seen people struggling to remember the definition of co and contra variance. Below are a few lines of code that help you keep it in mind. Just ignore the fancy names but remember that in .Net we use <in T> and <out T> instead of the fancy names when defining the type of variance allowed in generics. That should be enough for 100% of times.


in: CollectionAdder<Cat> is CollectionAdder<Animal> // Can add cats to a list of animals
 CollectionAdder<Dog> is CollectionAdder<Animal>
BUT:
 CollectionAdded<Animal> is NOT CollectionAdder<Cat> // Can not add animals to a list of cats (animals can be dogs)

out: CollectionGetter<Cat> is NOT CollectionGetter<Animal> // Can not read cats out of a list of animals (animals can be dogs)
BUT:
 CollectionGetter<Animal> is CollectionGetter<Cat> // Can read a bunch of animals out of a list of cats, all cats are animals by the way
 CollectionGetter<Animal> is CollectionGetter<Dog>

Advertisements

An IoC Container for Dart (with Autofac like API)

I enjoy throwing Darts, and have been using it quiet a bit recently. The OO nature of Dart makes it suitable for most OO design patterns. I use the inversion of control patter almost everywhere, but Dart did not have a good IoC container library that I knew of. Hence, in order to give something back to the community I wrote a lightweight IoC container based on the API of my favorite “Autofac”. The main reason for this choice was that a C# programmer who has already worked with Autofac can start using “Autodart” in a few minutes!

Below is a sample of how Autodart can be used:

class Baz{
}

class Bar{
  Baz baz;
  Bar(this.baz);
}

class Foo{
  Bar bar;
  Foo(this.bar);
}
void main(){
  var b = new AutoBuilder();
  b.register((c, p) => new Baz())
    .As("Baz")
    .singleInstance();

  b.register((c, p) => new Bar(c.resolve("Baz")))
    .As("Bar")
    .instancePerLifetimeScope();

  b.register((c, p) => new Foo(c.resolve("Bar")))
    .As("Foo"); //Default is .instancePerDependency()

  var c = b.build();

  var foo = c.resolve("Foo") as Foo;
  var foo2 = c.resolve("Foo") as Foo;

  assert(foo != foo2);
  assert(foo.bar === foo2.bar);
  assert(foo.bar.baz === foo2.bar.baz);

  /*
    Other supported API include:
    b.register(..).As(..).externallyOwned();
    c.resolveLazy("Foo") as Lazy<Foo>;
    var childScope = c.createLifetimeScope();
    c.dispose(); //Disposes all disposables in the scope
  */
}

Autodart supports the following scopes: SingeInstance (Singleton), InstancePerLifetimeScope (Nester Scopes), and InstancePerDependency.

It also defines the Disposable concept, and manages the scopes for Disposable objects.

Shortcomings: There is no auto wiring, as Dart does not yet support reflection. Also there is still no “Type” type in Dart, so string type names are used as keys. I would update the library as soon as dart adds support for reflection.

Simple Workflow Engine, Re-designed and Simplified (even more)

Redesigning SWE, a simple workflow engine:

I totally redesigned the SWE project, as I had to use the state machines in one of my own projects, and learned from its experience. The API for SWE is highly simplified. Everything gets done with only one public class “SateMachine<SO, RT>”. This class implements  four interfaces:

  • IStateMachineBuilder
  • IStateMachineController
  • IStateMchine
  • IStableStateMachine

To create and use a state machine is very simple. Each state has also got a very simple concept.

All that matters is:
State: Has a name, does some stuff, and decides what the next step is.

Below is a simple Light; on – off example:

Var smBuilder = StateMachine<Lamp, Lamp>.Create("On")
.State("On", (s, l) =>
{
    l.IsOn = true;
    return StateMachine.NamedState("Off");
})
.State("Off", (s, l) =>
{
    l.IsOn = false;
    return StateMachine.NamedState("On");
});
Var sm = smBuilder.BindTo(theLamp);

//Usage: each call, alternates the lamp between on and off.
While(true){
    sm.Process();
    Thread.Sleep(10);
}

In another post, I show a more advanced use of swe, with a csv parser.

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;
 }
 }
 }
 }
}

Solving a typical interview question with SWE

Lets assume a typical interview question:

Write some code to reverse words in a sentence without using .Net string functions. For example, “this and that” should become “sith dna taht”. We want to preserve space patterns also.

This is the state machine for this purpose:

And I can write it as follows:


public class TextContext
{
public string Text;
public int Pos; //Current position
public string Word;
public string Result;
}

public static void Main()
{
var tc = new TextContex{Text="This and That"};
var sm = new StateMachineBuilder()
.State("Space", c => true, c => { c.Word += " "; c.Pos++; })
.Then(c => c.Pos >= c.Text.Length, "Fine")
.Then(c => c.Text[c.Pos] == ' ', "Space")
.Then("Word", c => {c.Result += c.Word; c.Word = '';})
.State("Word", c => true, c => {c.Word = c.Text[c.Pos] + c.Word; c.Pos++;})
.Then(c => c.Pos >= c.Text.Length, "Fine")
.Then(c => c.Text[c.Pos] != ' ', "Word")
.Then("Space", c => {c.Result += c.Word; c.Word = '';})
.Finish("Fine")
.BindTo(tc);

sm.Start();
while(sm.MoveNext()){};

Console.WriteLn(tc.Result);
}

UPDATE: SWE is re-design. With the new version, the above code will look like the following:

var str = "This and That";
var word = new StringBuilder(); 
var smbuilder = StateMachine<int,string>.Create("word")
.State("leters", (s, i) => {
    if (str[i]==' ') { s.Return(word.ToString()); word.Clear(); return StateMachine.Named("spaces");};
    word.Append(str[i]);
    s.UpldateObject(i+1); //Update the pointer
    return StateMachine.Loop })
.State("spaces", (s, i) => {
    s.UpdateObject(i+1);
    if(str[i]==' ') { return StateMachine.Loop; }
    return StateMachine.Named("letters");
}); 
var sm = smbuilder.BindTo(0);
while(sm.Process()){ if (sm.HasReturn) { Console.WriteLn (sm.GetReturned();) } }

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.

A simple and handy workflow framework

Workflow plays a critical role in business applications, but very few use it (me included). I never used WF in my dev even though I believe workflow is a critical tool for ensuring quality code. The reason is obvious.
In case of WF, usually pain is more than gain. For a simple workflow you’ve got to deal with lots of not so interesting fluff.
The solution is obvious: Cut the crap!
I want to implement a tiny state machine suitable for developing workflows. No crab. Just a little dll to reference with a flexible design. Here comes the story.

Everybody talks about the on-off switch to describe state machine, so do I. Assume the following state machine. A lamp can be in the off or on state and a click will change the state. If it is on will become off and vise versa.

Here comes the code that is required to be implemented with WF state machine. Well, I don’t write the code, its a pretty long story so check the msdn article yourself.

So much crap wouldn’t convince me to use the state machine at all. I also hate to define events and a bunch of codes and classes for such a simple task. This is what I want to do:

var onOffWf = WorkFlow.Start(ILamp)
.State("Off",
	l => l.IsOn, //Enterance condition
	l => l.MakeOff()) //What happens at the state
.Then("On")
.State("On",
	l => k.IsOff, //Enterance condition
	l => l.MakeOn()) //What happens at the state
.Then("Off")

I want all the code to be in one place and also easy to read and understand.

One more thing that I want is to be able to easily save the state of my lamp and its workflow in with my object. For example I want to add a column to my Lamp table (lampId, WorkFlowState) which holds the stat of my lamp. So each time I load my lamp, I continue from where I was before. This is the code that I want to go on to my button OnClick() event:


void OnClick(...)
{
	MyLamp.MoveNext();
}

I also would like to bind the status of my lamp to its state as:

<TextBox ItemSource="{Binding Path=StatusTitle}"/>

onOffWf has a property onOffWf.StatusTitle.

Is that possible? Not with WF. If you know a way let me know quick because I am going to implement this and some time would be spent.