vendredi 15 février 2013

Closures from JS to Golang

Introduction

    You remember that weird feeling you had the last time you wrote non-trivial amounts on Javascript? Some sort of constant "this shouldn't be happening impression". Well JavaScript, or more specially ECMAScript the standard on which it is based, follows rules that may seem at times counter-intuitive. However some of those design decisions are the reason why JavaScript is so broadly accessible and generally accepted.

    In this entry, we will be discussing about one of the main aspect you are confronted with when writing code in ECMAScript, Closures. It is important to note though that closures are can not only be found in this language but in a variety of others : C#, Python and Golang to name just a few.

Quick examples


I will try to give an example of the same Closure in JavaScript, C#, Python and Golang. Bonus points for those who already did some functional programming, this is a basic example of currying.

What they are not.


Now that we have a gut feeling about what is a closures we can get in the real stuff. It is important to understand that closures are not our basic function pointers. They are much much more.

What are closures?


Closures are a way to bind a lexical context with a piece of code.

Lexical Context


The lexical context is the sum of every handle and variables that was available when the closure was created. It's its environment at the moment of creation, in other word.

A Wild Functor Appears


Remember writing functors? For most of you, this must seem like a ghost from Christmas past. If we put them in context with what we just saw, functors are a lot like closures. They provide some sort of context that is bound to a function "operator()". We can even rewrite the same sample we used earlier.


Cool eh? I bet you always wanted to know how to emulate JavaScript in C++ [sic].

What is so special about JavaScript then?


In JavaScript every function is a closure. Not only that, functions in JavaScript not only get the lexical context of when they were created but also the execution environment of the callee.


Another thing to remember is that, the this keyword is exactly that, a keyword. It returns the object in which the function you are will be inserted. ( In the case of most anonymous function in JavaScript this means the "window" object.)

As the standard says : 

The this keyword evaluates to the value of the ThisBinding of the current execution context.

Here is an example :


But why should I care about what JavaScript do?

Well, as we mentioned earlier, closures can be found in a variety of languages. If you are a programmer, there are very good chance that you already have written some even if it was unbeknownst to you. Understanding them is therefore essential.

You have been reading about them for some time now, it's time to get into applications. Let's look at another C# example.


You can notice that I have not written what it shown on the console for this one. It's for you to take a guess.

If your guess was all "5", then you are correct. In C#,  for-each  use reference for the iteration variable. Therefore the closure only gets a reference to the "i" variable and in each iteration of the for-each loop, the reference value gets modified.

It is for that reason that when we print them all, we get only "5", it effectively print 6 time the same reference.
If you want to do this sort of things you must use a local temp variable that you set to the loop iterator value and then pass the local variable to the closure.

Useful application of closure in JavaScript.


Not that we have a good feel about what closure are and how to use them. Let us look at a useful application of them in JS. Here is the situation :

A large candy company as launched a online contest to guess the number of bubble gum is produce each year. If you get it right, you win the equivalent of your weight in candy.

Here is a trivial, and broken implementation :

The console.log shows us why this is not exactly what the company wanted in term of difficulty... Now, lets try to do the same thing using closures.

This is more what we had in thought!
As you have probably understood now, this example was to show how to create private variables in a language that doesn't offer a way to do it by default.

Conclusion


In this blog entry, we have learn at what are closure and what is the difference between them and function pointers. We also saw that you can find closures in most modern languages. We have seen what makes there use so peculiar in ECMAScript dialects and at the same time how they can be harness to provide additional features and functionalities.

I hope that from now on, you will refrain from placing them in the "this provides undefined behaviour" and start noticing when they could be used to clear-up and enhance you codes.

This article will be followed by more on the topic of functional programming but I had to tackle closures before going further.

P.S. Do not hesitate to ask precisions, or to write suggestions in the comments.

lundi 4 février 2013

C#.NET throught Euler#10

Intro

After I was finished writing my last post, I went on looking for Euler's  problem implementation in C# and I was amazed at most of the answer I found. Every question regarding Euler's implementation in C# were overtaken by people asking to get the fastest possible implementation. Even thought I am always up for speed, I think there are missing the point. C# is an incredibly powerful language if it is fighting in its own turf, but if you are looking at micro-optimization how fast can C# dereference an array element that you are outside it's comfort zone.

Problem 10

I wasn't planning on doing another post right after problem #9 but I couldn't resist seeing how well it suited the language.

So problem #10 definitions is as follows :
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
the sum of all the primes below two million.

It's simple and straight to the point.

Generating Prime

The only part that isn't totally straight forward is how I generate my prime numbers. I am using the fact that a number is prime if it is not dividable by any prime from 2, to the square root of the number. Using this explanation, you should understand my logic.

Speed

Speed was not the goal here, I did absolutely no optimisation. My only constraint was that it must end before 10 sec as Euler's rules stipulates.

Implementation

As in the last post, I will provide a brief description of new operators.
  • Any - Return true if the predicates is true for any element.
  • Sum - Sums all the element.

Final words

Is it not splendid?

It feels like you're teaching your computer to speak English. Let me defines those as prime numbers and than take all primes under 2M and sum them.

Now we are in C#'s turf. Knowing you could do this in C# it pains me to see implementation like this : http://ideone.com/55j4F

I know it is faster, I know it is more efficient, but you have lost all that makes this a great language to work with.

C#.Net through Euler #9

+Randall Munroe often talks about how much he likes learning a new programming language by solving problems  on the website http://projecteuler.net. I have taken the habit of doing the same, not only to learn new languages but also when trying to exploit a languages features and specialization.

The situation

I have been working on a small C# project recently that included some data management and live presentation and manipulation. Even thought I had already worked with C#/WPF, I never had the time to learn and make mistakes. This time, everything is different. I most have rewritten the whole application 3 or 4 times trying to get closer to the idiomatic way of doing things. That led me to some of +Jon Skeet old blogs on rewriting linq to object in C#.

The problem

We are going to do Euler Problem #9 and look at an implementation featuring concepts of C# and LINQ in action.

Euler Problem #9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a2 + b2 = c2
Find the product abc.

For example, 32 + 42 = 9 + 16 = 25 = 52.
There exists exactly one Pythagorean triplet for which a + b + c = 1000.

First thoughts and background

A quick search on Wikipedia.org shows that there is a way to generate primitive Pythagorean triplet from a ternary tree (a 3-branch on each node tree). Basically, you can start from the first know triplet (3, 4, 5) and than apply one of three transformation to obtain another and from there you can do the same thing. 

The article also says that if (a, b, c) is a primitive triplet, for any positive integer k, (ka, kb, kc) is also a triplet.

First implementation

From that information, I knew some way of generating triplet and knew my stopping conditions from Euler's problem. I got cracking.

Having done some Haskell recently in which generating infinite sequence is an easy task, I went on thinking I would use the same pattern. I am using a BreathFirstSearch of my Tree instead of a DepthFirst in order to kept my triple in ascending order. Don't look too much as to why I am using a SortedSet instead of a Queue, we will check that later.


Expectations

Having done some LINQ before, this is what I came with. I thought that it seemed pretty reasonable and easy to read. We have some fonction that generates a infinite enumerable element and from those elements, we want only those whose sum is below or equal to 1000.

What really happened : The program outputted the correct data (yes!) but hanged forever after... 

Thinking about it, it was to be expected the implementation of LINQ "Where" operator is a much or less a foreach with a predicate and iterating over our infinite collection will take an infinite time.

Fix

We know that we currently have more than we really need. We have a collection that is more or less sorted and we know that our infinite generator will stream object that have a constantly growing sum. We therefore only need to stop when we are over our target.

There is a useful concept that has this effect : the iterator. I therefore went on implementing an IEnumerator infinite generator. It were doing the right thing, and I could stop the iteration after as many step as I wanted. But what I really wanted is to apply a filter that would do that automatically. Bad luck, when trying autocomplete, our new IEnumerator seemed pretty lonely having MoveNext() and Current() as its only two methods not deriving from "object".

I went on writing a static class for extension methods named EnumeratorEx with a TakeWhile() method that takes a predicate and iterates while the predicate is true. All when on working just fine, but this didn't seemed right.

Deferred execution

Deferred execution is the act by which we defer something until we no longer have the choice to do it. I shouldn't have to explain it in too much detail since it's self-explanatory for anyone who attended university. A quit search on Google showed that there were three operator in LINQ that offered deferred execution "Take", "TakeWhile", "Skip", "SkipWhile".

There we go, not only do we have what we need, it even has the same name as what we have given it.

De-fixing

After redoing everything to use an Enumerator, we now know that TakeWhile is using the IEnumarable.GetEnumerator and handling all of the fun stuff itself. It also means that we have to revert to our first implementation. Using the new TakeWhile, instead of the Where gives us exactly what we want and even stop when it's no longer needed.

Final Straight

We can now print all element up whose sum is up to 1000 and, bad luck, our item isn't a primitive Pythagorean Triple. We have to calculate our composite triples, but knowing the deferred execution trickery, we can use a number generator to dynamically calculate those.

We also see that GenerateInfinitePrime isn't really generating purely ascending items because the three modification used to obtain the next item doesn't guarantee order (the reason for the SortedSet instead of the Queue). Now, we have purely ascending primitive and are ready to make composite.

Composite

For each primitive that we have generated, we are going to calculate an infinite series starting at 1 and growing by 1. To those element we will use the "Select" operator to transform our input "an int" into something else "a triple". Now we have infinite composites!

Final

Now that everything is in place, we can show our final query. Our whole program is only an infinite generator of IEnumerable and filters as if we were in a functional language.

A fast topo of the function that are used :
  • Generate
    • Purpose built function for infinite generation based on a pattern.
  • TakeWhile
    • Deferred execution that enumerates until the predicate is false.
  • Select
    • Allow to "project" meaning to associate each element of our enumeration to something else.
  • Where
    • Filter element in an enumeration based on a predicate.
  • First
    • Returns the first element.
  • new {
    • Creates an anonymous type on the fly with the names attributes.

Introduction

This will be the very first post of this blog. I've been playing with the idea of writing such a blog for a long time now but I always was shut down by the fact that I couldn't choose a single subject to focus on.

It is for that reason that I willingly choose not to focus this blog on any language or technology. I will post on whatever I am doing right now that I think would benefit someone else.

On that note, let's jump to the first post.