Saturday, April 7, 2012

Using Set Theory, Ruby, and Map/Reduce to Implement Portable Class Libraries Feature in VS 11


How it all started...

I crunk up my Mac and began perusing the web.

Checked out a pretty nice article from my man Thomas P on joinads.

Man was I craving some F#.

I had to show my usual love...you know..Tweet dat and +1 dat!!

Once I got over to the Googleplex I began to scroll my feed.

Came across my man Hanselman and decided to check out the hype with a new feature coming in VS 11.

It's this multi targeting guy that allows you to implement an assembly that can be deployed across multiple Microsoft Platforms (Xbox, Silverlight, etc.)

So what does this mean?

Well...let's take Silverlight for example.

It's a subset of the CLR and .NET Framework so certain libraries available in say...an MVC app wouldn't be available in Silverlight.

So VS would proceed to remove those libraries that can't be used across both platforms.

So you're basically at the mercy of the platform that can support the least amount of libraries. You're only as strong as your weakest link, right?

Lets take an example

say we have the following platforms

Silverlight = [a, b, c]
MVC = [a, b, c, d]
Xbox = [a, b, c, d, e]

What's the expected output?

Easy...everything in Silverlight!!

[a, b, c]

It can only support libraries a, b, and c.

MVC and Xbox can also support d and e, but they're SOL here b/c their little sister can't hold her liquor.

Sorry Orteguitas...life isn't fair...

What would I expect in a comparison of MVC and Xbox?

[a, b, c, d]...

Ok..I think you get it by now, right?

I've said all that to say this...what if you had to implement this logic?

What would you do?

How many lines of code do you think it would take?

These are questions that I'm always pondering.

It's like..."Hey Antwan, what if LCD tv'S didn't exist and you had to be
the guy to implement them?"

A chin rub and shot of Gatorade later and I'm off to the races..

Haha..sike...I eventually embrace the reality of it all and reluctantly tell my brain that there's noway I'd have been able to make electricity, the first airplane or even the world's first LCD tv...ha..I wish.

But programming is something that I've managed to become pretty good at..and that
my friends...means there's hope.

So what if I had to implement this feature in VS?

Well...I spent a few minutes thinking it over and I came right back to the very foundations of our profession and the bit munching concoction of semiconductors, circuitry, and hardware that we hold so dear to our hearts...math!!

Wait...I'm having a flash back...discrete mathematics from college...oh no..the pain..the horror..is that a turing machine? I'm having a mental aneurysm...

Ok...back to the show..

It's simple set theory if you think about it.

Take the intersection of all the sets..and well...you're done.

We've already implemented this very scenario...at least at a high level..
now lets get into some code..

I couldn't decided whether I'd do this guy in Ruby, C#, or F#...cuz as we all know...loops are just my thing. Enumerable - Enumerable - Enumerable!!

All 3 languages provide pretty sweet implementations of Enumerable...but I've yet to publish any content in Ruby...so here goes.

We'll start out with some tests and then work our way to the final implementation.

Off the top of my head...I know that LINQ provides a native implementation of intersect, but not sure about Ruby...a quick Google aaaaaaand...

Drum role please...

Bam!!

Found it...

Here's the syntax

ary & other_ary → new_ary

we're golden.

Before we get started, I just want to take a brief moment to highlight our plan of attack.

We're going to use aggregation here..you know..take 2 values, generate a result, and push that result through the pipeline as new state to be combined with the next element of our sequence (acculamators).

This concept if the basis of Sum, Product, etc...

so something like

[ 1, 2, 3, 4, 5 ].inject(:+) # => 15

in Ruby..

What inject is doing here is enumerating the sequence, taking 2 values at a time,
adding them together, and returning a new value to be added.

So it goes

Iteration    Seed    CurrentValue

1               1          2
2 3          3
3 6          4
4 10         5

done...break loop

15 is our final answer..

Make sense?

The cool thing about inject is that you can abstractly pass any "function" to it and have that function applied to all elements in your sequence.

We could multiply all numbers if we wanted

[1,3,5,7].inject(:*) # => 105

What you're seeing is a shorthand syntax to inject.

In it's more explicitly form you'd do something like

[1,3,5,7].inject(0) {|sum, element| sum+element}         # => 16
[1,3,5,7].inject(1) {|product, element| product*element} # => 105

passing in a block.

We're using the more succinct shorthand syntax...gotta love that MRI sugar, yea?

I've covered this kinda thing in F# in a previous blog post..so nothing new..jus thought I'd share that again since it's such an essential and rudimentary concept.

I puts quotes around the word "function" up above because this is merely functional programming. I've managed to pick up a lot about in through F#, C# (LINQ), and a variety of other sources over the years. It'd only behoove you as a developer to pick up a functional language at some point during your career. So much of the very code that you write on a daily basis can be tied back to functional programming; and that implicit marriage feels even better once one gets to that point that he/she can explicitly detect it. Everything just starts to make sense.

Ok, I digress.

Didn't I say we'd get into some code? Oh yea...right..just didn't wanna leave anyone behind. I'm sure
the average dev that comes across this post will have jumped to the source by the time they got past
paragraph 2..haha.

If you'd like to see more of those cool Ruby samples I posted above, just checkout the Pickaxe Book. All those samples come straight from that book verbatim. A great read for any novice Ruby dev such as myself and even for the most experienced of Rubyists.

Ok so lets get started.

I'll start with a class to track our library instances and a stub implementation to detect compatibility.

platform.rb

class Platform

    attr_reader :name, :libraries

    def initialize(name, libraries)
        @name = name
        @libraries = libraries
    end
end

portable_class_lib.rb

require './platform'

module PortablePlatform
    def PortablePlatform.get_compatible_libraries(platforms)
    end
end
We'll keep this guy short and sweet...just a few test cases.

portable_platform_lib_tests.rb

require './portable_class_lib'
require 'test/unit'

class TestPortableClassLib < Test::Unit::TestCase
    def test_3_platforms_with_3_common_libraries
        xbox_libraries = %w{ System System.Web.Mvc System.ServiceModel System.Runtime.Serialization }
        xbox = Platform.new('Xbox', xbox_libraries)    

        silverlight_libraries = %w{ System System.ServiceModel System.Web.Mvc }
        silverlight = Platform.new('Silverlight', silverlight_libraries)

        mvc_libraries = %w{ System System.Web.Mvc Mvc.Core System.ServiceModel }
        mvc = Platform.new('ASP.NET MVC', mvc_libraries)

        platforms = [xbox, silverlight, mvc]

        compatible_libraries = PortablePlatform::get_compatible_libraries(platforms)

        expected_output = %w{ System System.ServiceModel System.Web.Mvc }

        assert_equal(expected_output, compatible_libraries)
    end

    def test_3_platforms_with_2_common_libraries
        xbox_libraries = %w{ System System.Web.Mvc System.ServiceModel System.Runtime.Serialization }
        xbox = Platform.new('Xbox', xbox_libraries)    

        silverlight_libraries = %w{ System System.ServiceModel }
        silverlight = Platform.new('Silverlight', silverlight_libraries)

        mvc_libraries = %w{ System System.Web.Mvc Mvc.Core System.ServiceModel }
        mvc = Platform.new('ASP.NET MVC', mvc_libraries)

        platforms = [xbox, silverlight, mvc]

        compatible_libraries = PortablePlatform::get_compatible_libraries(platforms)

        expected_output = %w{ System System.ServiceModel }

        assert_equal(expected_output, compatible_libraries)
    end

    def test_3_platforms_with_no_common_libraries
        xbox_libraries = %w{ System.Runtime.Serialization }
        xbox = Platform.new('Xbox', xbox_libraries)    

        silverlight_libraries = %w{ System }
        silverlight = Platform.new('Silverlight', silverlight_libraries)

        mvc_libraries = %w{ System.ServiceModel }
        mvc = Platform.new('ASP.NET MVC', mvc_libraries)

        platforms = [xbox, silverlight, mvc]

        compatible_libraries = PortablePlatform::get_compatible_libraries(platforms)

        assert_empty(compatible_libraries)
    end
end

And the test results...

Run options: 

# Running tests:

FFF

Finished tests in 0.001343s, 2233.8049 tests/s, 2233.8049 assertions/s.

  1) Failure:
test_3_platforms_with_2_common_libraries(TestPortableClassLib) [-:40]:
<["System", "System.ServiceModel"]> expected but was
<nil>.

  2) Failure:
test_3_platforms_with_3_common_libraries(TestPortableClassLib) [-:21]:
<["System", "System.ServiceModel", "System.Web.Mvc"]> expected but was
<nil>.

  3) Failure:
test_3_platforms_with_no_common_libraries(TestPortableClassLib) [-:57]:
Expected nil (NilClass) to respond to #empty?.

3 tests, 3 assertions, 3 failures, 0 errors, 0 skips

Failures just as we suspected. Lets plug in an implementation, shall we?

require './platform'

module PortablePlatform
    def PortablePlatform.get_compatible_libraries(platforms)
        platform_names = []

        platform_libraries = platforms.collect do |p|
            platform_names << p.name # go ahead and cache the names so we don't loop twice
            p.libraries # retrieve all libraries
        end

        compatible_libraries = platform_libraries.inject(:&)
        libraries_sorted_by_name = compatible_libraries.sort

        puts "Platforms...\n\n"

        platform_names.sort.each { |name| puts name }

        unless compatible_libraries.any?
            puts "\nHave no common libraries."
            puts "\nUnfortunately you cannot create a portable class library targeting these platforms."

            return libraries_sorted_by_name
        end

        puts "\nHave the following libraries in common...\n\n"

        libraries_sorted_by_name.each { |name| puts name }

        puts "\nTo make a portable class library, you'll need to reference these assemblies."

        libraries_sorted_by_name
    end
end

And now after re-running the tests we get...

Run options: 

# Running tests:

Platforms...

ASP.NET MVC
Silverlight
Xbox

Have the following libraries in common...

System
System.ServiceModel

To make a portable class library, you'll need to reference these assemblies.
.Platforms...

ASP.NET MVC
Silverlight
Xbox

Have the following libraries in common...

System
System.ServiceModel
System.Web.Mvc

To make a portable class library, you'll need to reference these assemblies.
.Platforms...

ASP.NET MVC
Silverlight
Xbox

Have no common libraries.

Unfortunately you cannot create a portable class library targeting these platforms.
.

Finished tests in 0.000913s, 3285.8708 tests/s, 3285.8708 assertions/s.

3 tests, 3 assertions, 0 failures, 0 errors, 0 skips

We're golden!!

So how'd it work? Well, lets take our core algorithm (minus all the output) and our first test case.

def PortablePlatform.get_compatible_libraries(platforms)
    platform_names = []

    platform_libraries = platforms.collect do |p|
        platform_names << p.name # go ahead and cache the names so we don't loop twice
        p.libraries # retrieve all libraries
    end

    compatible_libraries = platform_libraries.inject(:&)
    libraries_sorted_by_name = compatible_libraries.sort
end

def test_3_platforms_with_3_common_libraries
    xbox_libraries = %w{ System System.Web.Mvc System.ServiceModel System.Runtime.Serialization }
    xbox = Platform.new('Xbox', xbox_libraries)    

    silverlight_libraries = %w{ System System.ServiceModel System.Web.Mvc }
    silverlight = Platform.new('Silverlight', silverlight_libraries)

    mvc_libraries = %w{ System System.Web.Mvc Mvc.Core System.ServiceModel }
    mvc = Platform.new('ASP.NET MVC', mvc_libraries)

    platforms = [xbox, silverlight, mvc]

    compatible_libraries = PortablePlatform::get_compatible_libraries(platforms)

    expected_output = %w{ System System.ServiceModel System.Web.Mvc }

    assert_equal(expected_output, compatible_libraries)
end

We started out by storing the names of all platforms in an array in addition to retrieving the actual libraries for each platform. As you may already know, collect is the equivalent of map from a functional perspective.

Now for the set manipulation. Remember when we looked up that intersect syntax a while back?

ary & other_ary → new_ary

Well...we used it here for each set of libraries.

First we intersected the set of xbox libraries with itself, which of course just returned the original set of xbox libraries.

[ System, System.Web.Mvc, System.ServiceModel, System.Runtime.Serialization ]

Then that we took everything the xbox libraries and the silverlight libraries had in common. That yielded

[ System, System.Web.Mvc, System.ServiceModel ]

Finally we were left with the MVC libraries. That intersection yielded...well...the same thing

[ System, System.Web.Mvc, System.ServiceModel ]

Done!!

There's that inject function from earlier when we summed up all our numbers. That aggregate/bulk function that I'm always raving about. We applied it to each set of libraries using the intersect operator as our function. It should be obvious by now that when you use inject you'll be dealing with a generic scenario...

let a = a set of values of type b
let s the seed = the first element of a ,or a value of type b
let f = a function that accepts 2 elements of type b and returns a new element of type b
let o the output = a new element of type b

So basically you start with a sequence of values and end up with one. Sum takes a sequence of numbers and returns an individual number as the result. Just like our algorithm takes a sequence of arrays and returns an individual array as a result. This concept is known as reduce in the functional world. We actually used both map and reduce here...didn't we? Sound familiar? We mapped the platforms to a sequence of arrays, and reduced that sequence of arrays down into an individual one.

I've covered map/reduce before but it's shown up yet again. What a coincidence...

I'd like to take this time to conclude my post...

Shout out to Alicia G in the Show Me...

And I can't leave without giving you a glimpse of my exotic and elaborate lady friend that allowed me to pull off such an amazing feat. Her beauty and elegance are second to none. A hue and texture so rare. Her movements equivalent to the speed and grace of a Cheetah...my dear lady..where would I be without you?

Ladies and gentlemen....Vim

Mac Vim


Duces...













oink oink!!