.NET Open Sourced

Pretty cool that .NET got open sourced, even more cool is that it is MIT license with the Source Code on Github.

Also pretty funky that they are offering a fully featured version of Visual Studio for free and shipping supported Linux and OS X runtimes. Mono has give us this for a long time, but it is a nice that the gaps in Mono are going to be filled.

Lots of cool stuff coming in this area, such as the new Roslyn compiler (C# written in C# now not C++) which will open up some crazy compiler as a service meta-programming voodoo. Mono is a C# implementation of C# and has again been ahead of its time in this space, but Roslyn seems to be generating some crazy buzz around code introspection and IDE features.

Most interesting thing in .NET space for me though is not any of this but is simply the F# language, which itself is written in F#, and has been the most pioneering and exciting language in the .NET space for a number of years due to its ability to innovate a add new powerful features with relative ease.

I hope that C# and .NET keep pushing forward and we don’t see a Java-‘6-8’-esk stagnation period. Doesn’t look like it in week one anyway –> ‘One Week of Open Source’

William Gibson on ‘Zero History’ Interview

I listened to this on Sunday morning over a few nice coffees. Super interview… well worth the listen.

Roman Numerals Elixir Kata

A fun little test driven kata which will introduce you to the basics of elixir.

A rule I try to follow for this is to try and keep my solution less than 20 lines of code.

Devlog: Rails Testing

Completed the Rails Testing for zombies courses on CodeSchool tonight.

I liked it, I always found starting a new rails app always triggered my testing OCD and it was nice to get an insight into the strategies one can take to test a rails app without overdoing it.

The course covers how to unit test and integration test your rails app with fixtures using TestUnit, so you are given a good idea of the tools at your disposal out of the box. As a well as that you are introduced to other popular testing gems which make your life easier such as Shoulda, Capybara and FactoryGirl. I will touch on each of there briefly to give you a taste of what they are all about…

During the Unit Testing section you are introduced to Shoulda gem which is described as an alternative syntax that is easy on the fingers and the eyes.

1
2
3
4
class UserTest < Test::Unit::TestCase
  should have_many(:posts)
  should_not allow_value("blah").for(:email)
end

As the course starts to dig into integration testing you are also introduced to Capybara which provides a interaction based DSL for defining your integration tests that supports multiple drivers. Capybara tests when executing act like a headless browser of sorts giving you more control over the interactions with your site or api, following redirects more naturally for example which is something not handles by vanilla rails integration tests so well.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 describe "the signin process", :type => :feature do
  before :each do
    User.make(:email => 'user@example.com', :password => 'password')
  end

  it "signs me in" do
    visit '/sessions/new'
    within("#session") do
      fill_in 'Email', :with => 'user@example.com'
      fill_in 'Password', :with => 'password'
    end
    click_button 'Sign in'
    expect(page).to have_content 'Success'
  end
end

Lastly you are introduced to FactoryGirl, which is an alternative to using the built in test fixtures provided by rails out of the box.

Read on →

Integrated Tests Are a Scam

Found this gem in a tweet from @david_whitney, and as he says the title is trolly but none the less is an excellent talk on automated testing.

Integrations Tests Lead to Bad Design

  • An interesting point is made (and I am paraphrasing) that the more integration tests we have the less design feedback we get, leading to sloppy design as we don’t feel the same feedback & design pressure…

What Failed and Where?

  • Integration tests may highlight failures, and the name of the test may go a long way to saying what failed, but pin pointing the actual location and reason for the failure is often lost in the generalization of the test itself.
Read on →

HTTP Status Code Decision Diagram

The best HTTP Status Code decision diagram I have seen to date. Source: https://raw.githubusercontent.com/for-GET/http-decision-diagram/master/httpdd.png

Devlog: Ruby Bits 1 & 2

Completed the RUBY BITS courses on CodeSchool. Again… I was impressed with the content, as a casual rubyist I got plenty out of doing this.

I really enjoyed this course, I took away a lot of useful idioms which I will put to good use (when I get the chance).

The meta-programming a DSL creation in RUBY BITS part 2 were great… adding methods to classes dynamically is pretty bad-ass for drying up code.

I always wanted default method implementation on interfaces in C#, dunno why I brought this up other than in Ruby that would never ever be an issue with the features you have at your disposal… very few languages lead to as much developer happiness.

Just one of those languages I would love to write everyday if I could. Moving onto Rails Testing for zombies course next…

…that said Elixir has hit v1.x and the Dave Thomas “Programming Elixir” book has been released, so that will most likely eat up the next month or two of my life.

Tunes: Mesterházy - Körzeti Varázslóhivatal (2002)

Tunes: Minimal Mondays | 04 | Hooked On

My IDM binge continues….

Devlog: Real Time Web With Node.js

Completed the Real Time Web with Node.js course on CodeSchool

Another impeccable course, produced to the usual high standards which I have come to expect with each and every CodeSchool module. Go give these guys money and do a few courses, worth every penny.

I have completed a couple of node.js projects to date and am currently working on a biggin’, so I didn’t find this course very challenging, but I did find it fun, another great jingle and lots of great content.

The examples go a long way to show how much you can do with so little code, walking students through using socket.io and redis to build a chat client and a Q&A system.

Something I learned was how to use redis effectively, the course got me started and provided useful tips such as limiting size of a list to 10 items for example:

1
2
3
4
5
6
7
8
9
var redis = require("redis"),
    client = redis.createClient();
//... on last meeting submitted ...
var meeting = JSON.stringify(lastMeeting)

// Use LPUSH & LTRIM in tandem
client.lpush('recent_meetings', meeting, function(err, reply) {
  client.ltrim('recent_meetings', 0, 9) // 10 Items Max
})
Read on →

Devlog: A Sip of CoffeeScript

Completed the CoffeeScript course on CodeSchool.

I love these list comprehensions… I don’t think I will be writing straight JS for a while.

1
2
3
4
5
6
7
8
9
10
# Eat lunch.
eat food for food in ['toast', 'cheese', 'wine']

# Fine five course dining.
courses = ['greens', 'caviar', 'truffles', 'roast', 'cake']
menu i + 1, dish for dish, i in courses

# Health conscious meal.
foods = ['broccoli', 'spinach', 'chocolate']
eat food for food in foods when food isnt 'chocolate'

Refactoring Ruby With Monads

A plain & simple, practical and short introduction to monads and how they can be put to add some elegance to your code!

Do yourself a favour and take 30 mins to add some very slick refactoring tricks into your toolbelt.

Devlog: What I’ve Been Learning

These last few months I have been learning more than usual and in this post I talk a little about some of the things that have caught my interest. All of this is outside of work as my day job is working on a Trading platform written in C#.

Another goal of this post is to kick start my blogging again which I have completely got out of the way of doing over the last 2 or so years.

Erlang & Elixir

Partially inspired by my functional programming binge and a chat I had with Joe Armstrong at ReactConf; I have been getting stuck into Erlang, Elixir and the Phoenix web framework.

I feel these will play a big part in my future. The BEAM VM is fascinating and the powerful distributed programming model via the OTP libraries is something different and interesting. I look forward to digging into these topics on my blog in the coming months as I become more familiar with them.

I am working on an ‘anonymous’ location broadcast server to use these technologies in anger and I have found this has helped me achieve those A-HA moments that are so important when it comes to learning something and making it stick.

Node.js

I’ve been working away on a personal project (which will be launched at outloud.io some time in the future) using node.js, express.js, postgreSQL, passport.js, mocha, chai, chai-as-promised, Q, db-migrate, node-env…

Read on →

Responding in a Timely Manner

Earlier this year I was fortunate enough to attend ReactConf in London, this was one of the sessions. In an earlier post I spoke of how you should should check out Martin Thompson’s videos as they are the proverbial a gold mine of knowledge on building fast and scalable systems.

In this talk Martin defines different levels of “Real Time”, touching on the importance of being responsive and practical tools and advice to achieve that in the real world.

The talk is broken into the following sections:

  1. How to Test and Measure
  2. A little bit of Theory
  3. A little bit of Practice
  4. Common Pitfalls
  5. Useful Algorithms and Techniques

You can find the full conference playlist on youtube here

Enjoy!

The Ridge Stand

Came across this on kickstarter (here). I want one of these… so slick! Shipping end of 2014 and taking pre-orders now.

The Ridge Stand by NewBee Design

Rise of the Phoenix - Elixir Web Framework by Chris McCord

Elixir Conf 2014 - Keynote: Think Different by Dave Thomas

Debug Podcast: The Ganatra Trilogy

A wonderful series of Debug Podcasts where the guest @NitinGanatra, former iOS Apps Director at Apple, speaks about the evolution of the products over the years from a technical insiders perspective. Very enjoyable and eye openning 6 hours of Apple geek goodness…

Algorithms: Design and Analysis Videos

List of resources related to Algorithm Design and Analysis:

Devlog: Functional Programming Principles in Scala

Coursera – Principles of Reactive Programming

About the Course

This course introduces the cornerstones of functional programming using the Scala programming language. Functional programming has become more and more popular in recent years because it promotes code that’s safe, concise, and elegant. Furthermore, functional programming makes it easier to write parallel code for today’s and tomorrow’s multiprocessors by replacing mutable variables and loops with powerful ways to define and compose functions.

Scala is a language that fuses functional and object-oriented programming in a practical package. It interoperates seamlessly with Java and its tools. Scala is now used in a rapidly increasing number of open source projects and companies. It provides the core infrastructure for sites such as Twitter, LinkedIn, Foursquare, Tumblr, and Klout.

In this course you will discover the elements of the functional programming style and learn how to apply them usefully in your daily programming tasks. You will also develop a solid foundation for reasoning about functional programs, by touching upon proofs of invariants and the tracing of execution symbolically.

The course is hands on; most units introduce short programs that serve as illustrations of important concepts and invite you to play with them, modifying and improving them. The course is complemented by a series of assignments, most of which are also programming projects.

Introsort

Some notes on IntroSort…

Introsort or introspective sort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted. This combines the good parts of both algorithms, with practical performance comparable to quicksort on typical data sets and worst-case O(n log n) runtime due to the heap sort. Since both algorithms it uses are comparison sorts, it too is a comparison sort.

Introsort was invented by David Musser in Musser (1997), in which he also introduced introselect, a hybrid selection algorithm based on quickselect (a variant of quicksort), which falls back to median of medians and thus provides worst-case linear complexity, which is optimal. Both algorithms were introduced with the purpose of providing generic algorithms for the C++ Standard Library which had both fast average performance and optimal worst-case performance, thus allowing the performance requirements to be tightened.

Source: Wikipedia | David Musser Paper ‘Musser (1997)’

.NET 4.5 introduces Introsort in place of Quicksort

In the Microsoft .NET Framework 4.5, an Introsort implementation is used instead of simple QuickSort.

If the sort is not successfully completed, the results are undefined. This method uses the introspective sort (introsort) algorithm as follows:

  • If the partition size is fewer than 16 elements, it uses an insertion sort algorithm.
  • If the number of partitions exceeds 2 * LogN, where N is the range of the input array, it uses a Heapsort algorithm.
  • .NET 4.5 IntroSort ImplementationSource
    1
    
    IntroSort(left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length));
    
  • Otherwise, it uses a Quicksort algorithm.

This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

For arrays that are sorted by using the Heapsort and Quicksort algorithms, in the worst case, this method is an O(n log n) operation, where n is the Length of array.

You can view the full source for .NET 4.5 sorting implementation here: .NET 4.5.1 QuickSort

.NET 4.5 IntroSort ImplementationSource
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
private void IntroSort(int lo, int hi, int depthLimit)
{
    while (hi > lo)
    {
        int partitionSize = hi - lo + 1;
        if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold /* 32 */)
        {
            if (partitionSize == 1)
            {
                return;
            }
            if (partitionSize == 2)
            {
                SwapIfGreaterWithItems(lo, hi);
                return;
            }
            if (partitionSize == 3)
            {
                SwapIfGreaterWithItems(lo, hi-1);
                SwapIfGreaterWithItems(lo, hi);
                SwapIfGreaterWithItems(hi-1, hi);
                return;
            }

            InsertionSort(lo, hi);
            return;
        }

        if (depthLimit == 0)
        {
            Heapsort(lo, hi);
            return;
        }
        depthLimit--;

        int p = PickPivotAndPartition(lo, hi);
        IntroSort(p + 1, hi, depthLimit);
        hi = p - 1;
    }
}

You can view the latest (MIT licensed) Mono implemention on Github: Mono.C5 Sorting.cs

Quick Sort

Quicksort, also known as partition-exchange sort, uses these steps.

  1. Choose any element of the array to be the pivot.
  2. Divide all other elements (except the pivot) into two partitions.
    - All elements less than the pivot must be in the first partition.
    - All elements greater than the pivot must be in the second partition.
  3. Use recursion to sort both partitions.
  4. Join the first sorted partition, the pivot, and the second sorted partition.
C Quick SortSource
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void swap(int *a, int *b) {
  int t=*a;
  *a=*b;
  *b=t;
}

void sort(int arr[], int beg, int end) {
  if (end > beg + 1) {
    int piv = arr[beg], l = beg + 1, r = end;
    while (l < r) {
      if (arr[l] <= piv)
        l++;
      else
        swap(&arr[l], &arr[--r]);
    }
    // swapping elements within the array 
    // to avoid the memory allocation of more arrays.
    swap(&arr[--l], &arr[beg]);
    sort(arr, beg, l);
    sort(arr, r, end);
  }
}
JS Quick SortSource
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function sort(array, less) {

  function swap(i, j) {
    var t=array[i];
    array[i]=array[j];
    array[j]=t
  }

  function quicksort(left, right) {
    if (left < right) {
      var pivot = array[(left + right) >> 1];
      var left_new = left, right_new = right;
      do {
        while (less(array[left_new], pivot)
          left_new++;
        while (less(pivot, array[right_new])
          right_new--;
        if (left_new  <= right_new)
          swap(left_new++, right_new--);
      } while (left_new  <= right_new);
      quicksort(left, right_new);
      quicksort(left_new, right);
    }
  }

  quicksort(0, array.length-1);
  return array;
}
JS (Functional) Quick SortSource
1
2
3
4
5
6
7
8
9
10
11
Array.prototype.quick_sort = function ()
{
    if (this.length <= 1)
      return this;

    var pivot = this[Math.round(this.length / 2)];

    return this.filter(function (x) { return x <  pivot }).quick_sort().concat(
           this.filter(function (x) { return x == pivot })).concat(
           this.filter(function (x) { return x >  pivot }).quick_sort());
}
Ruby Quick SortSource
1
2
3
4
5
6
7
8
9
class Array
  def quick_sort
    return self if length <= 1
    pivot = sample
    group = group_by{ |x| x <=> pivot }
    group.default = []
    group[-1].quick_sort + group[0] + group[1].quick_sort
  end
end
Ruby (Functional) Quick SortSource
1
2
3
4
5
6
class Array
  def quick_sort
    h, *t = self
    h ? t.partition { |e| e < h }.inject { |l, r| l.quick_sort + [h] + r.quick_sort } : []
  end
end

Merge Sort

You start with an unordered sequence. You create N empty queues. You loop over every item to be sorted. On each loop iteration, you look at the last element in the key. You move that item into the end of the queue which corresponds to that element. When you are finished looping you concatenate all the queues together into another sequence. You then reapply the procedure described but look at the second last element in the key. You keep doing this until you have looped over every key. When you complete this process the resulting sequence will be sorted as described above.

Let ni be the number of items in the sequence to be sorted. N is number of integers that each key element can take. Let nk be the number of keys in each item.

The total time to sort the sequence is thus O(nk(ni + N)).

JS Merge SortSource
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function mergesort(list){
  if (list.length <= 1)
    return list;

  var mid = Math.floor(list.length / 2),
    left  = list.slice(0, mid),
    right = list.slice(mid, list.length);

  return merge(mergesort(left), mergesort(right))
}

function merge(left, right){
  var sorted = [];
  while (left && left.length > 0 && right && right.length > 0){
    var b = left[0] <= right[0];
    sorted.push(b? left[0]: right[0]);
    // remove the element which was added to the sorted array
    b? left.splice(0, 1): right.splice(0, 1);
  }
  return sorted.concat(left, right);
}
Ruby Merge SortSource
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def mergesort(list)
  return list if list.size <= 1
  mid = list.size / 2
  left  = list[0, mid]
  right = list[mid, list.size-mid]
  merge(mergesort(left), mergesort(right))
end

def merge(left, right)
  sorted = []
  until left.empty? or right.empty?
    if left.first <= right.first
      sorted << left.shift
    else
      sorted << right.shift
    end
  end
  sorted.concat(left).concat(right)
end

Devlog: Principles of Reactive Programming

Coursera – Functional Programming Principles in Scala

About the Course

This is a follow-on for the Coursera class “Principles of Functional Programming in Scala”, which so far had more than 100’000 inscriptions over two iterations of the course, with some of the highest completion rates of any massive open online course worldwide.

The aim of the second course is to teach the principles of reactive programming. Reactive programming is an emerging discipline which combines concurrency and event-based and asynchronous systems. It is essential for writing any kind of web-service or distributed system and is also at the core of many high-performance concurrent systems. Reactive programming can be seen as a natural extension of higher-order functional programming to concurrent systems that deal with distributed state by coordinating and orchestrating asynchronous data streams exchanged by actors.

In this course you will discover key elements for writing reactive programs in a composable way. You will find out how to apply these building blocks in the construction of event-driven systems that are scalable and resilient.

The course is hands on; most units introduce short programs that serve as illustrations of important concepts and invite you to play with them, modifying and improving them. The course is complemented by a series of assignments, which are also programming projects.