Friday, August 31, 2007

F# Algorithm Sample

But here is a "short description" of a problem:
Both the computer and the user have a row of units, each unit has a value. The rows are aligned face to face (like in a 2xn chess table). Each unit fights the unit in front of it. The unit with the biggest value wins. If 2 units have the same value, the computer wins. If the user knows how the computer will position its units in the row, how can the user position his units in order to minimize his loses. Write a program which computes this win/loss score. (some test data is provided).

And here is my sample:

1 let rec without_max ascending_sorted_list =

2 match ascending_sorted_list with

3 | [] -> []

4 | x::[] -> []

5 | x::y::xs -> x::without_max(y::xs)

6

7 let rec acc (me:list<int>, computer:list<int>, saved:int) =

8 match me, computer with

9 | x::xs, y::ys -> if x <= y then acc(xs, without_max(computer), saved)

10 else acc(xs, ys, saved+x)

11 | [], [] -> saved

12 | _ -> failwith "unequal arrays"

13

14 let save_creatures (me:list<int>) (computer:list<int>) =

15 let ascending_sort = List.sort(fun (x:int) (y:int) -> x.CompareTo y) in

16 acc(ascending_sort(me), ascending_sort(computer), 0)

17

18 let _ =

19 let a = save_creatures [5;15;100;1;5] [5;15;100;1;5] in

20 let b = save_creatures [15;15;15;15;15] [15;15;15;15;15] in

21 let c = save_creatures [1;3;5;7;9;11;13;15;17;19] [2;4;6;8;10;12;14;16;18;20] in

22 let d = save_creatures [2;3;4;5;6;7;8;9;10;11] [10;9;8;7;6;5;4;3;2;1] in

23 print_int a; print_int b; print_int c; print_int d


I had fun ;)

Wednesday, August 08, 2007

Injection Doctor

We use in project X a slightly wrapped PicoContainer. The implementation of several service are registered in the container explicitely. Sometimes people forget to register it, and unfortunately the container fails with an "UnsatisfiedConstructor" error. The error appears only at run-time (we don't have test-coverage for container configuration), and it's misleading: if we need a class A which needs B,
and we forgot to register B, we get the error on class A (which is, per se, OK).

The solution (proposed) is to instantiate recursively all the services, and to build for each (failed) instantiation a histogram: the more points we get for a service, the "more" needed it is, the probability to
have there the "injection-problem" will be bigger. For the previous example A will get 1 point and B 2 points.

And here is the source:


public class Memoize {

private readonly Func _func;

public Memoize(Func func) {

_func = func;

}

private IDictionary _cache = new Dictionary();

public R Call(T value) {

R result;

if (_cache.ContainsKey(value)) {

result = _cache[value];

} else {

result = _func(value);

_cache[value] = result;

}

return result;

}

}


class InjectionExplorer {

private Func<IEnumerable<Type>, Type> _greediest_ctor_params;

public InjectionExplorer() {

_greediest_ctor_params = new Memoize<IEnumerable<Type>, Type>(GreediestConstructorParametersWorker).Call;

}

public IEnumerable<Type> RequiredTypes(Type t) {

return _greediest_ctor_params(t);

}

private ConstructorInfo Greediest(Type t) {

ConstructorInfo greediest = null;

int greediest_param_length = -1;

foreach (ConstructorInfo ctor in t.GetConstructors()) {

if (ctor.GetParameters().Length > greediest_param_length) {

greediest = ctor;

greediest_param_length = ctor.GetParameters().Length;

}

}

if (greediest == null) { throw new Exception("No ctor was found"); }

return greediest;

}

private IEnumerable<Type> GreediestConstructorParametersWorker(Type t) {

ConstructorInfo ctor = Greediest(t);

return Enumerables.Do.Map<Type, ParameterInfo>(ctor.GetParameters(), delegate(ParameterInfo info) { return info.ParameterType; });

}

}

class InjectionDoctor {

private readonly IEnumerable<Type> _types;

private readonly Func<object, Type> _instantiate;

private readonly InjectionExplorer _explorer;

private readonly IDictionary<Type, int> _failed_instantiations;

public InjectionDoctor(IEnumerable<Type> types, Func<object, Type> instantiate) {

_types = types;

_instantiate = instantiate;

_explorer = new InjectionExplorer();

_failed_instantiations = new Dictionary<Type, int>();

}

public void Examine() {

Enumerables.Do.ForEach(_types, TryInstantiate);

}

public void PrettyPrint() {

string print_format = "{0} -> {1}";

Console.WriteLine(print_format, "Type", "Failed Instatiation Count");

foreach (KeyValuePair<Type, int> failed_instantiation in SortFailedInstatiationsByFailedCount()) {

Console.WriteLine(print_format, failed_instantiation.Key, failed_instantiation.Value);

}

}

private IEnumerable<KeyValuePair<Type,int>> SortFailedInstatiationsByFailedCount() {

List<KeyValuePair<Type, int>> pairs = new List<KeyValuePair<Type, int>>();

foreach (KeyValuePair<Type, int> failed_instantiation in _failed_instantiations) {

pairs.Add(failed_instantiation);

}

pairs.Sort(delegate(KeyValuePair<Type, int> x, KeyValuePair<Type, int> y) { return y.Value.CompareTo(x.Value); });

return pairs;

}

private Type Instantiable(Type candidate) {

if (candidate.IsArray) {

return Instantiable(candidate.GetElementType());

}

return candidate;

}

private void TryInstantiate(Type candidate) {

Type instantiable = Instantiable(candidate);

if (HasFailedInstatiations(instantiable)) {

CountFailedInstantiation(instantiable);

return;

}

try {

_instantiate(instantiable);

} catch (Exception) {

CountFailedInstantiation(instantiable);

TryInstatiateRequiredTypes(instantiable);

}

}

private void TryInstatiateRequiredTypes(Type candidate) {

Enumerables.Do.ForEach(_explorer.RequiredTypes(candidate), TryInstantiate);

}

private bool HasFailedInstatiations(Type candidate) {

return _failed_instantiations.ContainsKey(candidate);

}

private void CountFailedInstantiation(Type candidate) {

if (! HasFailedInstatiations(candidate)) { _failed_instantiations[candidate] = 0; }

_failed_instantiations[candidate] += 1;

}

public int FailedInstatiations() {

if (! HasFailedInstatiations(typeof(T))) { return 0; }

return _failed_instantiations[typeof (T)];

}

}



Unit-Test sample:

class B {

private readonly C _c;

public B(C c) {

_c = c;

throw new Exception("poof");

}

}

class C {

public C() {

throw new Exception("poof");

}

}

class D {

}

class E {

private readonly C[] _cs;

public E(C[] cs) {

_cs = cs;

}

}

class A {

private readonly B _b;

private readonly D _d;

public A(B b, D d) {

_b = b;

_d = d;

}

}

[TestClass]

public class InjectionDoctorSpecifications {

private DefaultPicoContainer _container;

private InjectionDoctor _doctor;

[TestInitialize]

public void BeforeEachTest() {

_container = new DefaultPicoContainer();

}

private void Register(IEnumerable<Type> types) {

foreach (Type t in types) {

_container.RegisterComponent(new CachingComponentAdapter(new ConstructorInjectionComponentAdapter(t)));

}

}

[TestMethod]

public void should_detect_instantiation_failures() {

IEnumerable<Type> types = new Type[] {typeof (A), typeof (B), typeof (C), typeof (D), typeof(E)};

Register(types);

_doctor = new InjectionDoctor(types, _container.GetComponentInstanceOfType);

_doctor.Examine();

//_doctor.PrettyPrint();

Assert.AreEqual(1, _doctor.FailedInstatiations<A>());

Assert.AreEqual(2, _doctor.FailedInstatiations<B>());

Assert.AreEqual(3, _doctor.FailedInstatiations<C>());

Assert.AreEqual(0, _doctor.FailedInstatiations<D>());

Assert.AreEqual(1, _doctor.FailedInstatiations<E>());

}

}



The output of the PrettyPrint looks like:
Type -> Failed Instatiation Count
Tests.C -> 3
Tests.B -> 2
Tests.E -> 1
Tests.A -> 1

Additionally we could add a method bool InjectionDoctor.HaveAllInstantionsSucceded()
ps. The Blogger Code Formatter is not playing nice with the generics: the InjectionDoctor takes as parameter in constructor a function f(Type) -> object. In this way we make the InjectionDoctor container-agnostic.
pps. source-code on request.

Wednesday, August 01, 2007

Mixing Peer (extension objects in c# 2.0)

In project X we have a big hierarchy of objects/interfaces:
Eintrag
- Artikel
- NeuFormArtikel
- NormalArtikel
- AbdaArtikel
- Verweis
- AbrechnungsEintrag

(The hierarchy is bigger, but this is enough for our purpose.)
We have a case, where in a View we must display a union of fields from this hierarchy. i.e. AbdaArtikel.Preis if the object has such a property, otherwise null/string.Empty.

We have several options:
- use a visitor for the whole hierarchy
- use a PropertyMapper (reflection-fluent-interface-based machinery) (looks pretty slick, enables a very declarative way of mapping, maybe I will post about it)
- extend/pull the AbdaArtikelPreis into the Eintrag (if we need it there)
- mix in a generic visitor:

Since the objects/interfaces in the hierarchy are Nhibernate BOs, they are proxied, i.e., in our configuration, we cannot use generic methods in BOs. But we can extend the BO with an object which can:
  1. we define Eintrag.Peer() { return new EintragPeer( this ); }
  2. now we can extend the peer/mixing with generics

public class EintragPeer {

private readonly Eintrag _extended;

public EintragPeer( Eintrag extendable ) { _extended = extendable; }

public R TryMap(Func func, R otherwise_default) where T : Eintrag {

if ( _extended is T ) { return func( _extended as T ); }

return otherwise_default;

}

public void TryApply(Action action) where T : Eintrag {

if (_extended is T) { return action(_extended as T); }

}

}



  1. Now we can use it as:

Preis eintrag_preis = eintrag.Peer().TryMap(

delegate(Artikel artikel) { return artikel.Preis; },

Preis.Null);



Other variations can be build on that.

Thursday, July 19, 2007

"Agile" Process Disentanglement

How FUBAR can an "agile" process be, that this book is needed?
How deep in the jungle is the team, that we need a silver-magic-map to bring it back on the driving-road?

Wednesday, July 18, 2007

Functional idioms, Take Three

In a hypothetical project in which the Law of Demeter is completely ignored navigation through objects is allowed: we can do A.B.C.D.E.DoSomething(). This has a lot of negative effects, already spoken/written, I'm not going into details.
  • My 1st suggestion would be to play by the rules, and pull the DoSomething(...) through the hierarchy up to A, where you need it.
  • But what if you cannot do it ("it is not the way we do it in this project") ? What if, to make the matters worse, every element in the chain could be null (and not a NullObject) ? The chain would explode in a cascade of if-then-else-s to check every element for null, etc...
    • Comega has something like int? = A.B.C.GetSomeIntValue(...)
    • We (C#) could do:

created.PackungsgroessenEinheitText = Chain.On.Nullables<IArtikel, INormalArtikel, Packungsgroesse, string>(

artikel,

delegate(IArtikel x) { return x as INormalArtikel; },

delegate(INormalArtikel x) { return x.Packungsgroesse; },

delegate(Packungsgroesse x) { return string.Format("{0} {1}", x.Menge, x.Einheit); }

);

    • we navigate throught the chain with delegates. The navigation is interrupted on the 1st null hit.
    • If we watch the "chain" implementation:

public class Chain {

private Chain() {}

public static Chain On { get { return new Chain(); } }

public R Nullables(S input, Func fun_1)

where S : class

where R : class {

if (input == null) {

return null;

}

return fun_1(input);

}

public R Nullables(S input, Func fun_1, Func fun_2)

where S : class

where R1 : class

where R : class {

return Nullables(Nullables(input, fun_1), fun_2);

}

public R Nullables(S input, Func fun_1, Func fun_2, Func fun_3)

where S : class

where R1 : class

where R2 : class

where R : class {

return Nullables(Nullables(Nullables(input, fun_1), fun_2), fun_3);

}

}




Monday, July 09, 2007

Functional Idioms, Take Two

My friend Ralf has extended the Enumerating module, adding a fluent interface.
  • Since the mini-project lives, I think we should create a sourceforge acount for it.
    • I have extended the interface with IsEmpty, Count, ApplyOnce, ...
  • I really like the fluent interface. SelectThenCollect is no longer necessary, we can do Select(...).Collect(...)
    • if in the initial Enumerable we have m elements and we select n from them, SelectThenCollect is O(m). Select(...).Collect(...) will take O(m)+O(n). (in the current implementation).
  • Open Question: the current implementation does eager-evaluation: the select is computed when the method is called. Do we need a lazy-implementation? It could look like a query definition, and the code will be more declarative:
    • IEnumerating query = Enumerating.On(several_things).Select(IsEven).Collect(ItsColor);
    • IEnumerable result_items = query.Eval();
    • The solution might cache, the specified delegates, for a later (lazy), usage. This might lead to some unwanted side-effects: the garbage collector will not release the objects referenced in the delegates in the query definition, until ... (the query is released).
    • Through laziness we could work on very large (infinite) data streams.

Tuesday, July 03, 2007

Sudoku Solver: TDD or not

In this blog people are comparing Peter Norvig's solution with Ron Jeffries TDD tries. (read the post, [some] good comments, other links to reddit comments, etc.)

It is a nice problem to chew on, for me, as Unit-Test/TDD agilist: I think that a TDD approach does not lead to discover constraint satisfaction algorithms, it should lead to a clean, testable, SRP driven architecture. If I remember well, the XP books say that you should start with a "metaphor", a design starting point.

disclaimer: this an echo post, i just wanted to link to AIMA.

Thursday, June 28, 2007

Logging and Unit-Testing

Imagine the following situation:

1 public class SomeService {

2 private static ILogger _logger = new Logger<SomeService>();

3 //...

4 public void DoSomething() {

5 _logger.Debug("I log something cheap {0}", _service.DoSomething());

6 //...

7 if (_logger.IsDebugEnabled()) {

8 _logger.Debug("I log something expensive {0}", _service.DoSomethingElse());

9 }

10 }



How do we want to test that logging works in this situation?
A proposed solution was:

13 [Test]

14 public void should_log_something() {

15 using(disable_appenders_and_introduce_new_appender = new MagicStringAppender()) {

16 _service_under_test.DoSomething();

17 Assert(disable_appenders_and_introduce_new_appender.AllMessages.Contains("I log ...");

18 }

19 }



And here is what I don't like about it:
  1. Static creation of ILogger: by this we make ourselves dependent of the concrete implementation of Logger class. This will pull other dependencies (like log4net) in the environment, despite the fact that these are irrelevant for the test. The logger will be created when the class(type) is instantiated.
  2. The check-before logging for expensive log operations, is too low-level. A macro might help (TRY_LOG_DEBUG(...)), or maybe delaying the expensive operation into a lazy delegate: _logger.Debug(Func a_delayed_string_generator). The only objection might be that wrapping the costly operation in a delegate creates an extra object, making in the worst case scenario, the logging even more expensive. (From what I know, delegates & closures are pretty cheap).
  3. Maybe we don't know which operations are cheap and which are expensive, maybe in time a cheap log call will evolve to an expensive one. I would prefer a uniform lazy_delegate or macro solution.
  4. We are trying to unit-test a scope which is too big: if the service sends a message to the logger interface, if log4net (and its wrapper) receive the message, if according to the configuration, the log message is sent to the right appender, etc... Suppose that we change the config, and log4net, and the test fails. Then we have a lot of fun debugging. We will say: "why isn't working, I haven't changed anything in months". Because the scope is too big, we have no chance to do a binary chop.
  5. We have built another big machinery to manipulate log4net at the wrong end. This machinery must be maintained and support (for example when we want to switch to another log engine)
What I would do (probably better):
  1. Explicitly specify that we want to log in constructor. Either inject an ILogger or an ILoggerFactory.
  2. Test only that the service sends a message to the ILogger interface (a mock or a stub recorder)
  3. Try to use a delegate for delayed/expensive computations.
  4. Use a main logger for the critical exceptions (like OutOfMemory)
---
Update:
- the post it is not about what am I trying to log, it is about "how" I am trying to log. (suppose the expensive operation is dumping a complex object tree to a human-readable-not-xml representation)
- I am not a proponent for logging-testing, but some people would like to do that (logging gives a chill-fuzzy feeling: "I don't know what I have implemented, QA also doesn't have a clue, and now we are relying on log files, on a production-customer-machine. hmmm..."

Friday, June 15, 2007

F# FizzBuzz

I'm trying to learn F# as the "pragmatic-learn-a-new-changing-the-way-you-think-programming-language-every-year" (sorry about that, it must be the german influence).

Here are my FizzBuzz exercises, based on F# Active Patterns:

First try:

let (| fizz|_ |) x = if x % 3 = 0 then Some("fizz") else None

let (| buzz|_ |) x = if x % 5 = 0 then Some("buzz") else None

let (| fizzbuzz|_ |) x = if x % 15 = 0 then Some("fizzbuzz") else None

let print_fizzbuzz (x:int) =

let display text = print_string text; print_newline() in

match x with

| fizzbuzz text -> display text

| fizz text -> display text

| buzz text -> display text

| _ -> x.ToString() |> display

let _ = for i = 1 to 20 do print_fizzbuzz i done



Second try: refactor the recognizers to a single parameterized recognizer:


let (| is_multiple|_ |) n text x = if x % n = 0 then Some(text) else None

let print_fizzbuzz (x:int) =

let display text = print_string text; print_newline() in

match x with

| is_multiple 15 "fizzbuzz" text -> display text

| is_multiple 5 "fizz" text -> display text

| is_multiple 3 "buzz" text -> display text

| _ -> x.ToString() |> display

let _ = for i = 1 to 20 do print_fizzbuzz i done


(* we do get a warning that the syntax for the parameterized recognizers is under review and it might change in the future release *)

Please post or backlink for improvements :D

Tuesday, June 05, 2007

APIs, handling dependencies, agile architecture

Somebody said recently that Resharper is "not so lovely" since it cannot handle thousand of files... My argument is that the need to work simultaneously (in a solution) is a smell, and the fact that Resharper crashes at type-parsing with a "System.OutOfMemoryException" exception should amplify the smell (increase our awareness).

I think we have only two cases: inside the membrane, or outside the membrane. The core of the cell represents a service implementation, the membrane represents service definition, outside the membrane are the service consumers/users. Actually outside the membrane, is inside another membrane: the whole architecture should be splitted in components.

If we are inside we are working on the implementation of a certain service(object, component). Inside a component we have limited visibility, up to a component interface (the membrane). Maybe some other interfaces, or stand-alone components (without external dependencies, for examples enumerating). All refactorings, type-parsing should occur without problem in this component.

If we are outside, we are service consumers. But we cannot talk to the "core" of the cell, we see only the membrane: the component interface. So we are not influenced by the changes in the implementation of the service (aka the "core").

What happens if you are a producer and you need to modify service definition. If we don't have a few consumers, we could load all the required components in a solution (producer + all consumers), and refactor the whole thing. If we have many consumers, we need to use public API techniques: we declare the whole interface as obsolete, we declare and implement the new one. After x weeks we delete the old interface (the consumers are responsible for refactoring their own code).

Isolating the change, is a fundamental principle in designing maintainable architectures. In a world without membranes, we are just hurting each other.

Tuesday, April 10, 2007

Higher-Level Abstractions on Enumerations

I am not the only one missing a higher-level of abstraction in .Net.
I feel that I wrote thousand times find, select, collect as foreach ...
statement, without the clarity (declarativeness) needed.
Here is my shot
(very lightweight at it):


Thursday, February 01, 2007

Static Considered Harmfull

Let's imagine the following situation:


static class Service {
static void DoSomething(...)
}

class Client {
Client() {}

void Action() {
Service.DoSomething(...)
}
}



We have the following smells:

1. Tight-Coupling
- The client object is tight-coupled with the Service class.
- We cannot exchange, polymorphically, the Service.DoSomething(...)
with another service FunkyService?.DoSomething.


2. "Lying" Constructor
- The client's constructor doesn't declare all the dependecies.

3. Tight-Coupling Propagation
- If the class Service has dependencies to other static classes
(methods, instances, properties), than these dependencies propagate into
the client. The "inoffensive" Service.DoSomething(...) is just the tip of an iceberg of singletons.

Proposed Solution:
In an OO world, responsabilities are realized by objects.
Unfortunately in static-typed langugages classes ARE NOT objects.
(in smalltalk/ruby they are, we don't have this problem)

So let's do it right from the beginning:


interface IService {
void DoSomething(...)
}

[Inject]
class Service {
void DoSomething(...)
}

class Client {
Client(IService service) { _service = service }
void Action(service.DoSomething(...));
}



Benefits:
- we are unattached from the implementation of the IService.DoSomething
- we have explicitely defined the responsability of the client to delegate/ask a
query to the IService implementor
- We can provide different implementations to the IService
- UnitTesting is easier: if the implementation of the IService has been tested,
then in the Client's unit-tests we are only interested in the call to IService,
which we can mock.
- Instance creation is handled by dependency injection container
(if you need only one, create just only one)


An example in ruby (classes are factory objects):
http://onestepback.org/articles/depinj/