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>

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.

Automatic Mid-tier Cache!

I have been thinking about this for a while. I started to work on a Silverlight project last year which was a nifty little business app. One of those apps that is just sitting down and working, you know, a web server, an average DB with a few million records, and a silverlight client with a bunch of forms, grids, and menus.

Everything was straightforward and brainless, like just follow a pattern and do the job. However, I was deeply dis satisfied from one aspect of the project. The Caching. What I could not accept was that in 21st century, when you have Entity Framework and IQueryable, you should still manually cache your data when it is appropriate and do all the pointless work of cache invalidation and loading, etc. Apart from the pain of working on something that should have been automated, I wouldn’t trust a programmer to decide which parts of the data should be cached and which part shouldn’t be. Not that I don’t believe they can do a good job on that, they don’t have enough information (at the time of dev work) to decide on it.

Caching strategy should be based on user behaviour and is subject to change by passage of time. For example at some stage lots of QLD pharmacies are queried, but next week NSW users decide to get ready for their conferences and start hammering the system for NSW pharmacies.

Le me be clear about my expectations of a caching system. It should have the following charachteristics:

  1. It should know what users are going to query a lot and cache that (and only that) part of the database.
  2. It should be able to re-use the caches. For example if I say 1.”Give me all QLD pharmacies”, and next one says 2.”Give me all QLD Chemists Warehouses”, the cache manager should be smart enough to run this new query 2., over the results of query 1. which has been retrieved a few minutes ago.
  3. It should optimize the indexes for performance based on the user queries.
  4. It should change the cache when user behaviour changes.
  5. It can call back the database only if there is absolutely no way of answering the query from cache.

Above requests seems to be a lot, but not really in 2011. All these methods are possible, in fact DBMSs do those kind of stuff for ages. We also have IQueryable, which makes it even easier to have a decent caching system.

So let me write a few examples:

Q1: Pharmacies.Join( … Address …).Join( … State …).Where( s => s.Sate = “QLD”).Select(…)

Q2: Pharmacies.Join( … Address …).Join( … State …).Where( a =>a.Sate = “QLD” && a.PostCode > 4000 && a.PostCode<4079).Select(…)

Q3: Pharmacies.Join( … Address …).Join( … State …).Where( s => s.Sate = “QLD”).GroupBy(…).Where( pg => pg.Count() > 4).Select(…)

Q4:  PharmacyStaff.Where(ps => ps.Position == “Manager”).Select(…)

Q5: Pharmacies.Join( … Address …).Join( … State …).Join(…PharmacyStaff…).Where( s => s.Sate=”QLD” && s.Position == “Manager” ).Select(…)

Users login to our system  and do stuff that will cause the above queries to be issued. Normally they will all be issued against the database, but it means that our caching strategy is stupid as a donkey. Really what I would expect is that only Q1 and Q4 are ran against the database. Q2, Q3, and Q4 are all subsets of Q1, hence if we already have those results from Q1, such a waste to run these new queries against the database. Why not look at the Expression Tree and figure out that Q2 is forms a query which is a subset of Q1. Then change the queries as below:

Q1: not changed…

Q2: Q1.Where(a => a.PostCode > 4000 && a. PostCode<4079).Select(…)

Q3: Q1.GroupBy(…).Where(…)

Q4: not changed…

Q5: Q1.Join(…Q4…).Select(…)

Check out the above queries. Aren’t they much better. We don’t expect user or programmer to waste his time on translating those queries. The caching system should do that. It should be an IQueryable that reads the ExpressionTree and translates it into a new ExpressionTree that uses existing data in the cache if there is no need to query database.

This specially make  sense in CLOUD, where you have to pay for querying your SQL Asure.

Enough talking about the dreams, lets become realistic! I did a bit of research and as I expected no such caching manager exists (if you know some tell me and save my hair). So I decided to do it myself. Check the Auto-mid-tier-cache project which I have already started. I haven’t gone far with it yet. It is just a proof on concepts and it implements no IQueryable. It uses a set of objects defined by myself for Relational Algebra operators. It does the very basic of view-matching to find what query is subset of what other, and it is able to translates queries to run against the database or cache alternatively.

I ran it and it worked fine and a bunch of benchmark analysis proved its effectiveness. What is left now is to complete the view-matching and write an IQueryable on top of it. Lot of work but it is worth it.

I forgot to say that you can limit the cache size by setting cost upper-bound. Next issue is that it does not keep itself up-to-date, but this is really another story.

Nullsafe dereference operator (?.) in C#

Nullsafe dereference operator (?.) as exists in some languages is a handy and nice pattern which saves a few bugs. Null references are serious problems and as people say nearly 70% of all bugs in the industry are directly or indirectly related to “Object reference not set to an instance of an object!”

However, there is noway to completely avoid null references, unless you write in a fully functional programming language like HASCUL. Some object oriented languages like groovy support a notion of nullsafe dereference operator which helps your null checks to be simpler. Here is the syntax in groovy:

bossName = Employee?.Supervisor?.Manager?.Boss?.Name

The above code returns the Name of the boss of the manager of the supervisor of an specific employee. It checks if any part of the right operand is null. If employee has no supervisor or supervisor has no manager, etc. bossName will become “null”.

Writing the above code in C# becomes like this:

bossName = Employee != null && Employee.Supervisor != null && Employee.Supervisor.Manager != null && Employee.Supervisor.Manager.Boss != null ? Employee.Supervisor.Manager.Boss.Name : null;

Pretty ugly, isn’t it? We can make a bunch of C# functions that takes us as closer to the groovy syntax of groovy. Note that nullsafe operator is going to be used in many places and inside the loops and it is not efficient to define any class for just a null check. Anyway a simple function won’t add much overhead.

//Groovy:
bossName = Employee?.Supervisor?.Manager?.Boss?.Name
 //C#:
 bossName = Nullify.Get(Employee, e => e.Supervisor, s => s.Manager, m => m.Boss, b => b.Name);

 

This one looks much more beautiful and more readable and this the the Nullify (static) class:

 public static class Nullify
 {
 public static TR Get<TF, TR>(TF t, Func<TF, TR> f) where TF : class
 {
 return t != null ? f(t) : default(TR);
 }

 public static TR Get<T1, T2, TR>(T1 p1, Func<T1, T2> p2, Func<T2, TR> p3)
 where T1 : class
 where T2 : class
 {
 return Get(Get(p1, p2), p3);
 }

 /// <summary>
 /// Simplifies null checking as for the pseudocode
 /// var r = Pharmacy?.GuildMembership?.State?.Name
 /// can be written as
 /// var r = Nullify( Pharmacy, p => p.GuildMembership, g => g.State, s => s.Name );
 /// </summary>
 public static TR Get<T2, T2, T3, TR>(T1 p1, Func<T1, T2> p2, Func<T2, T3> p3, Func<T3, TR> p4)
 where T1 : class
 where T2 : class
 where T3 : class
 {
 return Get(Get(Get(p1, p2), p3), p4);
 }
 }
 

UPDATE:

Below is the alternative way by using extension methods. It is really your preference to decide which way is better. Above approach might have slightly less overhead since it just adds a single function call in the IL code and is more concise for short expressions, but the code is shorter in the bottom approach and visually looks better for larger expressions.


 public static TOut NullSafe<TIn, TOut>(this TIn obj, Func<TIn, TOut> memberAction)
 {
 //Note we should not use obj != null because it can not test value types and also
 //compiler has to lift the type to a nullable type for doing the comparision with null.
 return (EqualityComparer<TIn>.Default.Equals(obj, default(TIn))) ? memberAction(obj) : default(TOut);

 }

 //Usage:..

 Employee.NullSafe( e => e.Supervisor ).NullSafe( s => s.Boss ).NullSafe( b => b.Name );

 
Posted in C#. 6 Comments »

Authorization Rule Library in SAF and how to use it with RIA Services and Silverlight

A problem of applying rules by decorating objects using attributes is that there is no concept of re-usability. For example, we want NationalAdmins, StateAdmins, and Managers to be have all permissions over everything. Also permissions for my customer, customer_address, customer_emails, etc. are all similar. Normally you should apply all authorization attributes to every part of the model.

SAF provides an ImportAuthorizationAttribute that solves this problem.

public class AuthorizationMetadata
{
    [Grant...]
    [Grant...]
    public class AdminGroup { }

    [Deny...]
    [Deny...]
    [Deny...]
    public class RestrictedWriteGroup {}

    [Grant...]
    public class TitleViewersGroup {}
}

You can use AuthorizationMetadata class to centralize all your authorization rules. You can then use it in your model as follows:

[ImportAuthorization(SourceType=AuthorizationMetadata.AdminGroup)]
public partial class Model
{
}

What else do you want?