Immutable Data and Memoization in C#, Part 2

By jay at April 22, 2013 21:10 Tags: , , , ,

tl;dr: Memoization can be associated with the ConditionalWeakTable class, which allows the addition of memoized computation results to immutable types. This makes the memoized results live as long as the instances that was used to create it.

 

In the first part of this article, we discussed a bit the Memoization pattern in C#. In this second part, we will discuss how to alleviate the memory management issue for memoized computation results.

 

ConditionalWeakDictionary to the rescue

In .NET 4.0 – quite a while ago now – a new class was added, the ConditionalWeakTable, to help in the creation of dynamic languages based on the DLR, where there was a need to be able to attach data to existing type instances, much like a fictional extension property could be. This topic is not covered much, and since it has to do with the GC, it is often misunderstood.

The idea is pretty simple: It is a dictionary that takes an type instance as a key, and a value associated to it. The key is stored as a weak reference, meaning that the data is held as a hard-reference as long as the key lives. When the key is collected by the GC, the hard-link is removed, making the data available for collection if it’s not referenced anywhere else.

Here’s how to use it:

More...

Immutable Data and Memoization in C#, Part 1

By jay at April 18, 2013 20:49 Tags: , , , ,

TL;DR: Immutable data and memoization are functional programming concepts that can be applied to C# programming. These patterns have their strengths and weaknesses, discussed a bit in this article. 

 

I’ve grown to not being a great fan a data mutability.

Data mutability can introduce a lot of side effects in the code, and it can be pretty complex to go back in time to know what a specific state was before the code failed. This gets worse when multiple threads are involved, and that tends to happen a lot more these days, now that even phones have multiple cores.

Sure, we can use IntelliTrace to ease that kind of debugging, but that’s pretty much limited to issues you already know about. That means you’re reacting to issues that already happened, you’re not proactively preventing those issues from happening.

So, to address this more reliably, there’s the concept of immutability. When a set of data is built, it cannot change anymore. This means that you can pass it around, do computation with it, use it any place you want, there’s not going to be any subtle concurrency issues because the data changed under your feet.

More...

Cancellation with Async F#, C# and the Reactive Extensions

By jay at April 16, 2013 20:25 Tags: , , , ,

TL;DR: C# 5.0 async/await does not include the implicit support for cancellation, and needs to pass CancellationToken instances to every async method. F# and the Reactive Extensions offer solutions to this problem, with both implicit and explicit support for cancellation.

 

My development style has slowly shifted to a more functional approach, during the past year. I’ve been peeking a F# for a while and that shift to a more functional mindset in C# lends me toward understanding a lot better the concepts behind core features of F#, and more specifically the async “support” in F#.

It’s known that F# inspired a lot the implementation of C# async, but having looked at the way it’s been implemented in F# gives me some more points against the “unfinished” implementation in C#.

 

Recently, now that people are effectively using async, in real-world scenarios, problems are starting to bubble up, and some to giggle. Async void, async void lambdas, the fact that continuations run mostly on the UI thread when not taken care of properly, obscure exception handling scenarios, the “magic” relation to the SynchronizationContext, that it does not address parallelism, and one that’s been pretty low-key, cancellation.

More...

Toying around with F# Queries, Rx, Portables Libraries, Windows [Phone] 8 and the Zip operator

By jay at January 02, 2013 22:42 Tags: , , ,

Agreed, that’s a lot of keywords. Yet, they fit one another in a very interesting way.

I find more and more that F#, particularly regarding the way my development trends are going, is getting more and more of a fit regarding the immutability and flexibility needs.

Given that, I thought I’d give a try at running some F# Query Expressions using custom Rx operators, on Windows Phone 8, using Portable Libraries.

More...

A C# Traverse extension method, with an F# detour

By Jay at May 17, 2009 09:10 Tags: , ,

Cet article est disponible en Français.

The Traverse extension method in C#

Occasionally, you'll come across data structures that take the form of single linked lists, like for instance the MethodInfo class and its GetBaseDefinition method.

Let's say for a virtual method you want, for a specific type, discover which overriden method in the hierarchy is marked with a specific attribute. I assume in this example that the expected attribute is not inheritable.

You could implement it like this :

    

    private static MethodInfo GetTaggedMethod(MethodInfo info)
    {
        MethodInfo ret = null;

        do
        {
            var attr = info.GetCustomAttributes(typeof(MyAttribute), false) as MyAttribute[];

            if (attr.Length != 0)
                return info;

            ret = info;

            info = info.GetBaseDefinition();
        }
        while (ret != info);

        return null;
    }


This method has two states variables and a loop, which makes it a bit harder to stabilize. This is a method that could easily be expressed as a LINQ query, but (as far as I know) there is no way to make a enumeration of a data structure which is part of a linked list.

To be able to do this, which is "traverse" a list of objects of the same type that are linked from one to the next, an extension method containing a generic iterator can be written like this :


    public static class Extensions
    {
        public static IEnumerable<T> Traverse<T>(this T source, Func<T, T> next)
        {
            while (source != null)
            {
                yield return source;
                source = next(source);
            }
        }
    }


This is a really simple iterator method, which calls a method to get the next element using the current element and stops if the next value is null.

It can be used easily like this, using the GetBaseDefinition example :


   var methodInfo = typeof(Dummy).GetMethod("Foo");

   IEnumerable<MethodInfo> methods = methodInfo.Traverse(m => m != m.GetBaseDefinition() ? m.GetBaseDefinition() : null);


Just to be precise, the lambda is not exactly perfect, as it is calling GetBaseDefinition twice. It can definitely be optimised a bit.

Anyway, to go back at the first example, the GetTaggedMethod function can be written as a single LINQ query, using the Traverse extension :


    private static MethodInfo GetTaggedMethod(MethodInfo info)
    {
        var methods = from m in methodInfo.Traverse(m => m != m.GetBaseDefinition() ? m.GetBaseDefinition() : null)
                      let attributes = m.GetCustomAttributes(typeof(MyAttribute), false)
                      where attributes.Length != 0
                      select m;

        return methods.FirstOrDefault();
    }


I, for one, find this code more readable... But this is a question of taste :)

Nonetheless, the MethodInfo linked-list is not the perfect example, because the end of the chain is not a null reference but rather the same method we're testing. Most of the time, a chain will end with a null, which is why the Traverse method uses null to end the enumeration. I've been using this method to perform queries on a hierarchy of objects that have parent objects of the same type, and the parent's root set to null. It has proven to be quite useful and concise when used in a LINQ query.

An F# Detour

As I was here, I also tried to find out what an F# version of this code would be. So, with the help of recursive functions, I came up with this :

    let rec traverse(m, n) =
       let next = n(m)
       if next = null then
           [m]
       else
           [m] @ traverse(next, n)


The interesting part here is that F# does not require to specify any type. "m" is actually an object, and "n" a (obj -> obj) function, but returns a list of objects. And it's used like this :

    let testMethod = typeof<Dummy>.GetMethod("Foo")

    for m in  traverse(testMethod, fun x -> if x = x.GetBaseDefinition() then null else x.GetBaseDefinition()) do
       Printf.printfn "%s.%s" m.DeclaringType.Name m.Name


Actually, the F# traverse method is not exactly like the C# traverse method, because it is not an extension method, and it is not lazily evaluated. It is also a bit more verbose, mainly because I did not find an equivalent of the ternary operator "?:".

After digging a bit in the F# language spec, I found out it exists an somehow equivalent to the yield keyword. It is used like this :

    let rec traverse(m, n) =
       seq {
           let next = n(m)
           if next = null then
               yield m
           else
               yield m
               yield! traverse(next, n)
       }


It is used the same way, but the return value is not a list anymore but a sequence.

I also find interesting that F# is able to return tuples out of the box, and for my attribute lookup, I'd have the method and I'll also have the attribute instance that has been found. Umbrella also defines tuples useable from C#, but it's an addon.

F# is getting more and more interesting as I dig into its features and capabilities...

F#, TryWith, Maybe and Umbrella

By Jay at December 06, 2008 13:49 Tags: , , ,
Cet article est disponible en Français.
 
I've thrown myself a bit in the discovery of F#, and even though I do not intend to make it my first language, I intend to use techniques and features found in it and try to port them into C#. New additions in C# 3.0 make it a good target for functional concepts.

There seem to be a consensus for the fact that F# is not a multi-purpose language, as C# is also not, for instance with the writing of parallel code. C# is not a perfect language for this, but F# seems to be. At the opposite, F# does not seem to be a language of choice for writing GUI code. For my part, and considering that F# if not really official, reusing concepts will be enough for now.

TryWith Extension

Using F#, I had to write this:


   let AllValidAssemblies = [
        for file in Directory.GetFiles(@"C:\Windows\Microsoft.NET\Framework\v2.0.50727", "*.dll") ->
        System.Reflection.Assembly.LoadFile(file)
    ]

This code creates a list of assemblies that can be loaded in the current AppDomain. There is however an issue with the invocation of the Assembly.LoadFile method, because it raises an exception when the file is not loadable for some reason. This is a non-modifiable behavior, even though we would like to return a null instead of an exception.

To work around this, there is a feature in F# that can do this :


    let EnumAllTypes = [
        for file in Directory.GetFiles(@"C:\Windows\Microsoft.NET\Framework\v2.0.50727", "*.dll") ->
        try System.Reflection.Assembly.LoadFile(file) with _ -> null
    ]

The point of the try/with block is to transform any exception into a null reference.

To transpose the creation of this list in C# with a LINQ query, the same problem arises. We must intercept the exception raised by LoadFile and convert it to a null reference.

Here is the equivalent in C#, without the exception handling :


    var q = from file in Directory.GetFiles(@"C:\Windows\Microsoft.NET\Framework\v2.0.50727", "*.dll")
            let asm = Assembly.LoadFile(file)
            select asm;

When LoadFile raises an exception, the execution of the request is interrupted, which is a problem.

Extension Methods can be of a great value here, and even though a normal method could do the trick, we can write this :


    public static class Extensions
    {
        public static TResult TryWith<TInstance, TResult>(this TInstance instance, Func<TInstance, TResult> action)
        {
           try {
              return action(instance);
           }
           catch {
              return default(TResult);
           }
        }
    }


The idea behind this method is to reproduce the behavior of the try/with F# construct. With this method, we can update the LINQ query into this :


    var q = from file in Directory.GetFiles(@"C:\Windows\Microsoft.NET\Framework\v2.0.50727", "*.dll")
            let asm = file.TryWith(f => Assembly.LoadFile(f))
            select asm;


This is creates the same list the F# code does, with null references for assemblies that could not be loaded.

The TryWith method can be overloaded to be a bit more flexible, like calling a method for a specific exception :



    public static TResult TryWith<TInstance, TResult, TException>(
           this TInstance instance, Func<TInstance, TResult> action,
           Func<TException, TResult> exceptionHandler
        )
        where TException : Exception
    {
        try {
           return action(instance);
        }
        catch (TException e) {
           return exceptionHandler(e);
        }
        catch {
           return default(TResult);
        }
    }


By the way, there is an interesting bug with this code. If we execute this :


    string value = null;
    var res = value.TryWith(s => s.ToString(), (Exception e) => "Exception");


The behavior is different depending on whether it is executed with or without the debugger with the x86 runtime. It seems that the code generator "forgets" to add the handler for the TException typed exception, which is annoying. This is not a big bug, mainly because it only appears when the x86 debugger is present. With the x64 runtime debugger, there is no problem though. For those interesting in this, the bug is on Connect.

Maybe Extension

I also added recently in Umbrella an extension named Maybe, which has a behavior rather similar to TryWith, but without the exceptions :


    public static TResult Maybe<TResult, TInstance>(
         this TInstance instance,
         Func<TInstance, TResult> function)
    {
       return instance == null ? default(TResult) : function(instance);
    }


The point of this method is to be able to execute code if the original value is not null. For instance :


    object instance = null;
    Console.WriteLine("{0}", instance.Maybe(o => o.GetType());


This allows the evaluation of the GetType call, only if "instance" is not null. With a method call like this, it is possible to write an "if" block, with inside a LINQ query, this because a bit more complex.

The idea for the code is not new and is similar to the functional Monad concept. It has been covered numerous times, and an implementation more in line with F# can be found on Matthew Podwysocki's Blog.

Pollution ?

When we're talking about pollution linked to Extension Methods, we're talking about Intellisense pollution. We can quickly find ourselves dealing with a bunch of extensions that are useful in the context of the current code, which renders Intellisense unusable. With Umbrella, these two extensions are somehow polluting all types, because they are generic without constraints.

Although these are only two very generic extensions, this can apply to almost any block of code, but they could find themselves better placed in an Umbrella Extension Point, rather than directly on every types.

We could have this :



    object instance = null;
    Console.WriteLine("{0}", instance.Control().Maybe(o => o.GetType());


But I have some issues with this approach : To be able to create an extension point the Control methd has to create an instance of the IExtensionPoint. This add a new instantiation during the execution, although the lambda also creates itself a hidden instance, we're counting anymore... There is also the fact that it lengthens the code line, but is only aesthetics. We'll see what pops out ...

Anyway, it is interesting to see the impact the learning a new language has on the style of writing code with another language that one's been using for a long time...

About me

My name is Jerome Laban, I am a Software Architect, C# MVP and .NET enthustiast from Montréal, QC. You will find my blog on this site, where I'm adding my thoughts on current events, or the things I'm working on, such as the Remote Control for Windows Phone.