Sunday, March 9, 2014

Bird Watching with JavaScript -- The Kestrel

"I will entertain Bardolph; he shall draw, he shall tap."
-- Shakespeare, The Merry Wives of Windsor
Act I, Scene III, Line 10

The Forest


In the Combinator Forest we hear the repeating call of the Kestrel.  As we sing out DO RE, we hear the Kestrel sing back DO.  We sing out LA but the Kestrel is still singing back DO.  We try again by singing out DO RE MI FA SO LA TI DO, but the Kestrel sings back DO DO DO DO DO DO DO DO.

Kestrel


The kestrel or K combinator is written as Kxy.x.  Meaning that no matter what value is given as y we always get x back from K.



We see that we always get the first argument back from the combinator K.

Kestrel in Haskell


In the package Data.Aviary.Birds we see the kestrel has the following definition:

kestrel :: a -> b -> a

We find that it is implement in the following way:

-- | K combinator - kestrel - Haskell 'const'.
-- Corresponds to the encoding of @true@ in the lambda calculus.
kestrel :: a -> b -> a
kestrel = const

see also: http://hackage.haskell.org/package/data-aviary-0.2.3/docs/src/Data-Aviary-Birds.html#kestrel

We see that this is calling nothing more than the const function in Prelude, which is implement in the following way:

-- | Constant function.
const                   :: a -> b -> a
const x _               =  x

see also: http://hackage.haskell.org/package/base-4.3.0.0/docs/src/GHC-Base.html#const

This means no matter what we pass as a second argument to const the pattern matching will match it and will simply just return the first argument.  Let's play with this on tryhaskell.org:


λ const 42 "another value"
42
:: Num a => a
λ let only42 = const 42 in only42 [1..5]
42
:: Num a => a
λ let onlyChickens = const "Chicken" in 
map onlyChickens ["Hen", "Rooster", "Cow"]
["Chicken","Chicken","Chicken"]
:: [[Char]]
λ  

We see when we call const no matter what the second argument is only the first argument is returned.

Underscore.js' constant

The K combinator is one of the newly added function in the popular Underscore.js library.  It has been implement as constant.

Here is what the implementation looks like:

  _.constant = function(value) {
    return function () {
      return value;
    };
  };

We see that constant will return a function which always returns value no matter what we call that function with.

Let's do some characterization testing on Underscore's constant.


Is a function

it("Constat will return a function", function(){
expect(_.constant("Hello world")).to.be.a("function");
})

We see that result of calling constant is a function no matter what we call it with.


Always returns the first value given to it


it("Given two values constant will return the first", function(){
var alwaysFirst = _.constant("First");
expect(alwaysFirst("Second")).to.be.equal("First");
})

We also see that when we call the function which constant returns we always get the same value which we initially called constant with.

In fact we can call constant with another function and have that function always returned from the function which constant returns (it is functions all the way down!).

it("Given a function constant will return that function", function(){
var theTruth = function(){return true;},
nothingButTheTruth = _.constant(theTruth);
expect(nothingButTheTruth()).to.be.a("function");
expect(nothingButTheTruth(false)()).to.be.ok();
expect(nothingButTheTruth(_.identity(42))()).to.be.equal(true);
});

Tap


Constant is a very simple implementation of the K combinator, but it has limit uses.  Tap is another way to implement the K combinator, but unlike constant it has a ton of uses.  In fact it is included in many languages core libraries including Ruby's.

Underscore.js' tap


"The primary purpose of this method is to "tap into" a method chain, in order to perform operations on intermediate results within the chain."
-- tap, Underscore.js documentation

Underscore has an implementation of tap which looks like this.

  _.tap = function(obj, interceptor) {
    interceptor(obj);
    return obj;
  };

Looking at the code above we see that if we call tap with a function we will pass the value through the function before we return the value.



Let's play around with the tap function to see what it is like to work with.



Can be used like constant


We see that give a value and a function which does nothing, the value is returned.

it("Give a string and a function which does nothing the string will be the same", function(){
expect(_.tap("Mr. Jack", function(){})).to.be.equal("Mr. Jack");
}),

and

var array = [1, 2, 3, 4, 5];
beforeEach(function(done){
array = [1, 2, 3, 4, 5]; // to reset before each test case
done();
});
it("Given an array and a function which does nothing array will be the same", function(){
expect(_.tap(array, function(){})).to.be.eql(array);
}),

Can have side effects


We see that we can attach a function to the value so that we have an effect take place when we access it.

it("Given a value and a function which increments ...", function(){
var counter = 0,
increment = function(){counter++;},
peek = function(){return _.tap("Look here", increment);};
expect(counter).to.be.equal(0);
expect(peek()).to.be.equal("Look here");
expect(counter).to.be.equal(1);
peek();
expect(counter).to.be.equal(2);
});

This is very interesting, in fact the most common use of tap is for logging which is very similar to what we have above.

Ciao


It may seem odd to work with a function which "only" returns the same value on each call but we find in fact that the Kestrel is a very useful function.

Stopping the Madness OR How to Do TDD in Windows with a Rat Terrier in the Room

"To worry lambs and lap their gentle blood"
-- Shakespeare, Richard III
Act IV, Scene IV, Line 50

Test Driven Development


I like to think of myself as a professional in the field of software development as such one of the practices I do is Test Driven Development (TDD).  The way that TDD works is that you write a failing test, then write just enough code to make it pass, next refactor your code, and finally repeat by writing another failing test.


The key is starting with a failing test.  Why a failing test?  If the test is failing you know it is actually testing something.  When you write a test after the code, you do not know if the test is actually testing the code in the way you expect it to.  Early in my career I fell into the test after trap.  I got burned by this process and am now a firm believer in Test First.

One of the side effects of the TDD process is that you have lot of failing unit tests which cause some type of beeping noise in most testing frameworks.  This beeping noise is usually not an issue at work, but at home this can cause issues.

Mr. Jack


Anyone that knows me, knows that I have a loving Rat Terrier named Jack.


Mr. Jack was a rescue dog from Heartland Animal Shelter in Northbrook, Illinois.  Jack is a great dog but dislikes beeping noises.  What is a TDDer to do?

Turning the Beep Off in Windows


Luckily there is a way to turn the beeping noise off in the Windows Console (I've been using Windows again after using Linux for many years but I have a new Mac on the way so please do not judge me too badly).

c:\>net stop beep

The Beep service was stopped successfully.

This will stop the console from beep for this session.  To re-enable the beeping use: net start beep.

c:\>net start beep

The Beep service was started successfully.

As one would guess this answer was found on SuperUser (a StackExchange site).

Great Animals Need Your Help

Why did I write this blog?  One reason was to be able to look this command up at a later time.  Yes, I use my own blog post to remind myself, to my knowledge this is common among authors of all types.

Another reason to write a post like this is to let people know that there are great animals available at your local animal shelter.  For reasons beyond their own control many animals find themselves at shelters.  Often these animals are well behaved and are loving but just need a new place and family to call home.  If you are looking to add an animal to your life look to your local shelter first.

Sunday, March 2, 2014

Currying in JavaScript

"If I had a suit to
Master Shallow, I would humour his men with the
imputation of being near their master; if to his men, I
would curry with Master Shallow that no man could
better command his servants."
-- Shakespeare, Henry IV Part 2
Act V, Scene I, Lines 64.ii - 68.i

What is Currying?


Using the HaskellWiki as a dictionary.

"Currying is the process of transforming a function that takes multiple arguments into a function that takes just a single argument and returns another function if any arguments are still needed."
-- HaskellWiki

In even more detail with historical context.

"Currying has its origins in the mathematical study of functions. It was observed by Frege in 1893 that it suffices to restrict attention to functions of a single argument. For example, for any two parameter function f(x,y), there is a one parameter function f' such that f'(x) is a function that can be applied to y to give (f'(x))(y) = f (x,y)."

In other words currying allows for you to think of your functions in such a way as that they only take one argument while in fact they have many arguments.

Example, say we have the following function f.

f(x, y) = y/x

We can curry f with the argument of 2 giving us a new function h.

h(y) = y/2

We can then call h with arguments obtaining the result of dividing those values by 2.

h(4) = 2
h(10) = 5
h(2) = 1

We could also define the function f in the following way.

f(h(y),x) = y/x

Now we get the following given the argument of 2.

h(y) = y/2

Thus getting same result as above.

In Haskell Everything is Curried


"Every function in Haskell officially only takes one parameter."
-- Miran Lipovača, Learn You a Haskell for Great Good
Chapter 6


When I first read the statement above my mind was blown.  Having read nothing about currying before I could not believe what I was reading.  Everything is curried?!?  If I define a function add which takes two arguments, then that function will be curried by default!?!

Using tryhaskell.org we can do the following.


λ (\x y -> x + y)
:: Num a => a -> a -> a
λ (\x y -> x + y) 2
:: Num a => a -> a
λ (\x y -> x + y) 2 3
5
:: Num a => a

In the first line we see the lambda function(\x y -> x + y)which takes x and y this is defined as a -> a -> a where a is a Number.  If we call the exact same lambda function with one argument we get a new function defined as a -> a.  Lastly if we take the same function and apply two arguments to it we get the value back.

This is currying in action.  All the functions are really just unary functions which will either return a anothing function or a value (which you could think about as a function that does not do anything other than returning the same value every time you call it).

In JavaScript Nothing is Free


How do we curry in JavaScript?  Well JavaScript does not curry by default like Haskell does, so we will have curry our functions ourselves.



Roll Our Own


In the gist above on lines 11-17 a curry add which takes three arguments.

var ownAdd = function(a){
return function(b){
return function(c){
return a + b + c;
}
}
};

This function returns functions until it has all three arguments, once it has all three arguments it will return the sum of the arguments.  This will work but it really sucks!  Luckily currying is a well known pattern, so we have our pick of implementations of it in JavaScript like: underscore-contrib, allong.es, lemond, ...

Allong.es


Allong.es has a curry function which when applied to a function will return a curried version of the function.

var addThree = function(a, b, c){return a + b + c;},
allongesAdd = curry(addThree);

We see another version of add in the gist on lines 19 and 20.  Yes, that is a lot less work.  Even better when we look at the example tests, we see the following on 46 and 47.

expect(allongesAdd(1)(2)(3)).to.be.equal(6);
expect(allongesAdd(1, 2, 3)).to.be.equal(6); // for free!

Yes, you get to call the function in a Haskell like curried maner and allong.es does all the hard work for you.

Mapping Fun


I know this is all well and fine, but how does one use this in a typical real world manner?  Glad you asked.  I spend a lot of time in my day job working on collections of data, one way I've used currying is with higher order functions.

Say you have an array which represent the combination to your luggage (not 100% real world, but much funnier than see same thing similar with securities, orders, executions, commissions, ...).

var luggageCombination = [1, 2, 3, 4, 5],
luggageMappings = map(luggageCombination);

This works until someone accuses you having an idiots combination for your luggage, so you figured your keep your current combination but will apply a mapping function against it to have a less idiotic combination.  In allong.es every function is curried, so you can apply map against your combination and try out different functions to see which give the best result.

Using this we can square and mod 10 the values to give us the combination of 1, 4, 9, 6, 5.  Now who is the idiot!

var squared = function(x){return x * x;},
squaredMod10 = compose(function(x){return x % 10;}, squared); // Who's an idiot now?!?
expect(luggageMappings(squaredMod10)).to.be.eql([1, 4, 9, 6, 5]);

This example is really good, since we are composing our squaredMod10 function!