Computer Science, JavaScript, Languages, Learning, Programming Languages, Python

Understanding Partial Application and Currying


Partial application and currying are two popular concepts from functional programming and help cut code replication in certain scenarios. This article assumes an understanding of the JavaScript bind function; binding is synonymous with partial application in JavaScript.

Partial Application

In pure functional languages, functions are not ‘invoked’, rather a set of arguments is ‘applied’ to them. Now, if all the arguments are not passed in, then the function is being  ‘partially‘ applied.

Partial application converts variadic functions (i.e. functions with multiple parameters) into functions of lesser arity by pre-specifying certain argument values.

Lets take the exponential function (x^y) from the mathematics domain as an example; an exponent value of 2 gives the square function while a value of 3 gives the cube function. The base exponential function has one of its inputs fixed to a certain value. Partial application can lead to new functions.

function add(a,b) {
    return a + b;
}

//partial application
function increment(n) {
    return add.bind(null,n);
}

var add2 = increment(2);
add2(2);
//4

var add4 = increment(4);
add4(10);
//14

Currying

No, not Indian/Pakistani Curry (they taste awesome by the way… :) ). The name Curry comes from Haskell Curry, a renowned mathematician who has a lot of things named after him (Haskell is another one) .

Currying is somewhat similar – it turns a variadic function into a sequence of chained monadic (i.e. single argument) functions. For example, a curried triadic function will be invoked as a chain of 3 monadic functions.

function add(a,b) {
    return a + b;
}

//currying
function curriedAdd(a) {
    return function(b) {
        return add(a,b);
    };
}

curriedAdd(3)(4);
//7

var add3 = curriedAdd(3);
add3(7);
//10

That was a simple example, let’s look at a more generic curry function.

function curry (fn)
{
 var arity = fn.length,
 exec = function (args){
   args = args || [];
   return function helper(){
       var helperArgs =
            [].slice.apply(arguments);
       var argsTally =
            args.concat(helperArgs);
       if(argsTally.length >= arity){
          return fn.apply(null,argsTally);
       }else{
          return exec(argsTally);
       }
    };
 };

 return exec();
}

function sum (x,y,z) {
    return x * y * z;
};

curriedProduct = curry(sum);

curriedProduct(1)(2)(3);
curriedProduct(1, 2)(3);
curriedProduct(1, 2, 3);
curriedProduct(1)(2, 3);
//All return 6

How does this work?!

Let’s dive in and take it apart! Fun!!

1. The length property of the function being curried is its arity (number of expected parameters).

2. The exec function allows currying until all parameters are matched, its args array grows during repeated invocations.

3. The helper function is returned on curry calls. Its helperArgs array allows capturing new parameters until the original function’s arguments are all matched.

If the number of parameters in helperArgs equals the original function’s arity, then all parameters have been passed in and we can execute the function successfully. Otherwise, returning the exec function with the updated arguments allows currying to continue.

This process continues batching up arguments until the curried function’s arity is matched or exceeded.

4. Note that extra parameters are dropped when functions are called with excessive arguments. The curry tastes good with extra input ;)

Let’s trace it out!

A curried function’s execution is traced out below:

curriedProduct = curry(sum);
[arity:3]
-> exec()
-> helper() 
//Gets returned to curriedProduct
curriedProduct(1,2)(3) 
-> helper(1,2) 
[argsTally: [1,2], argsTally.length(2) < arity(3)]
-> exec([1,2])
-> helper() 
[args:[1,2]; available to helper through closure]
-> helper(3) 
[argsTally:[1,2,3]; argsTally.length(3) >= arity(3)]
-> sum.apply(null, [1,2,3])
-> 6

Note: Technically, currying allows only monadic functions…

Differences

While it does seem currying and partial application are the same thing but for two subtle differences:

1. Currying will only invoke the original function when all parameters have been passed in while partial application will invoke the base function regardless of this.

2. Curried functions will always return new functions until all arguments have been applied whereas partially applied functions will always return the same base function with some pre-determined argument values. This becomes quite obvious in functions with an arity > 2.

Why should I care about this?

1. Allows you to think in a new way about programming.

2. Both concepts allow you to create new helper functions and utilities that are useful in a lot of situations.

3. Functional programming is cool.

4. At least you now (hopefully) know the difference between partial application and currying!

Conclusion

What do you think about both functional programming concepts? Add your comments and do check out other interesting posts.

1. Understanding Tail Recursion

2. Programming Language Type Systems II

3. Programming Language Type Systems I

4. Quirky Quirky JavaScript: Episode One

Standard
Computer Science, JavaScript, Languages, Programming Languages, Python

Understanding Tail Recursion


A tail call is the last call executed in a function; if a tail call leads to the parent function being invoked again, then the function is tail recursive.

function bar() {};
function baz() {};
function biz() {};

function foo() {
    bar();
    return baz();
}

function foo2() {
    if(bar()){
        return baz();
    } else {
        return biz();
    }
}

In the first function – foo; the baz() function is a tail call while in foo2, the baz and biz are tail calls because both are the last calls to get executed in the function. The second example shows that the tail call doesn’t have to be the last line of the function – it just has to be the last call the function makes before it returns.

Deep Dive

Lets analyze the factorial function.

function fact(n) {
    if(n <= 1) {
        return 1;
    } else {
    	return n * fact(n-1);
    }
}

fact(5);
//120

fact(30000);
//RangeError: Maximum call stack
//size exceeded

A fact(3) call is traced out below:

fact(3) -> 3 * fact(2)
3 * (2 * fact(1))
3 * (2 * 1)
3 * 2
6

Every recursive call has to be totally evaluated before the final value can be calculated.

Now let’s make a tail-recursive version of the same function.

function fact2(n) {
    function tailFact(n, acc) {
        if(n <= 1) { return acc; }
        return tailFact(n-1, n * acc);
    }

    return tailFact(n, 1);
}

Evaluation of this function now looks like this:

fact2(3) -> tailFact(3, 1)
tailFact((3-1), (3*1))
tailFact(2, 3)
tailFact((2 -1), (2*3))
tailFact(1, 6)
6

The tail recursive function does not use the stack; the function calculates the factorial as it goes along! The last recursive call performs a simple calculation based on the input arguments and returns.

Thus, there is no need to push frames on to the stack because the new function  already has everything it needs. As such stack overflows would not occur with tail call optimized functions.

One neat little thing to know is that the tail-recursive calls do not change the original values; in the factorial function example above, the value of n is never changed, rather new n values are passed in to new function calls.

Optimizing tail calls
A few languages (e.g. scheme) will optimize tail calls so that they run as loops however other languages e.g. JavaScript, Python do not; even if a function is in the tail call form; it’ll still run out of stack space.

The trick to get a non-optimizing compiler to simulate tail recursion involves the use of a trampoline; lets see examples below

//tail-call version runs out of space

fact2(30000);
//RangeError: Maximum call stack
//size exceeded

function trampoline(fn) {
    var result = fn;
    while (result instanceof Function) {
        result = result();
    }
    return result;
}

//Has subtle error
function fact3(n){
    function tailFact(n, acc){
        if(n <= 1) { return acc;}
        return tailFact(n-1, n*acc);
    }

    return trampoline(tailFact(n,1));
}

fact3(30000);
//RangeError: Maximum call stack
//size exceeded

The fact3 function trampoline call fails because we pass in a function expression and not a function reference. The execution steps are traced out below:

fact3(2)
trampoline(tailFact(2,1))
trampoline(tailFact(1, 2))
trampoline(2);

The trampoline is only called after the tailFact completes its recursive operations. We need to make two changes:

1. Return a function reference from the tailFact function.

2. Pass in a function reference to the trampoline function.

The Function.prototype.bind function is perfectly suited for this purpose and the transformed functions are

//Tail recursive
function fact4(n){
    function tailFact(n, acc){
        if(n <= 1) { return acc;}
        //return function reference
        return
          tailFact.bind(null,n-1,n*acc);
    }

    //update to function reference
    return trampoline(
       tailFact.bind(null,n,1)
    );
}

fact4(30000);
//Infinity

Benefits

The biggest advantage of using tail calls is that they allow you to do extensive operations without exceeding the call stack. This makes it possible to do a lot of work in constant space without running into out of memory exceptions; this happens because the frame for the currently executing function is re-used by the newly-executed function call.

It is possible to write the same function using tail call recursion and this will allow you to do it for arbitrarily large values. The space optimization is from O(n) to O(1) since every new function call reuses existing frames rather than pushing stuff on the stack.

Another advantage is that tail calls are essential for the continuation passing style (also called fluent programming; a popular example is jQuery function chains). Imagine chaining a huge set of calls together without needing to worry about running out of stack space – after all you need a location to store the executing functions.

The disadvantage of tail-call optimized code however is that it is difficult to debug; how would you know what function call lead to what function call if the call stack frames are being reused?

Conclusion

Do share your thoughts about tail recursion in the comments or check out these other exciting posts!

1. JavaScript’s Function.prototype.bind

2. Quirky Quirky JavaScript: Episode One

3. The Immediately Invoked Function Expression

4. Functional JavaScript – Tail Call Optimization and Trampolines

Addendum

I spent about a week trying to figure out why my original trampoline didn’t work until I ran into Don Taylor’s excellent article; it sure did help! Can you figure out why it’s wrong too?


function trampoline(fn) {
    var res = fn();
    while (res && res instanceof Function) {
        res = res();
    }
    return res;
}
Standard
JavaScript, Languages, Programming Languages

JavaScript’s Function.prototype.bind


The bind function allows you to set the context with which a function will execute. It takes in a ‘context object and returns a new function which has its context set to the passed in object. The variadic method, which exists on all function objects, provides a workaround for the annoying and elusive ‘this’ context issue in JavaScript.

As web developers; we all nearly need to create references to object methods at some time or the other. The annoying thing is that the original context is uusally lost when we need it most! Let’s see how bind can help in these scenarios.

var obj = {
    val: 10,
    getVal: function () {
         return this.val;
    }
};

obj.getVal();
//10

var valGetter = obj.getVal;
valGetter();
//undefined

var boundValGetter = valGetter.bind(obj);
boundValGetter();
//10

Function Signature

Function.bind(thisObj, arg1, arg2,…)

thisObj refers to the new context for the function. However if the newly returned function is used as a constructor (i.e. called using the new operator), the this context will be a new empty object as expected.

arg1, arg2,… are extra parameters that are prepended to the list of arguments that the newly bound function is called with. Assuming you declare two arguments in the original bind call and then pass three new arguments to the returned bound function, then the two original bound arguments appear before the three newly passed in arguments.

var fn = function () {};
var bound = fn.bind(window, 1,2);

#equivalent forms
bound(3);
fn.call(window, 1,2,3)

If the bound function is invoked as a constructor, then the bound arguments are still passed on.

Uses

The most common application would be to avoid the use of the ‘that = this’ pattern in JavaScript. This is especially the case when you need to pass in context to event handlers, use anonymous functions or do something similar.

var ordExample = {
     log : function () {
           console.log('logger called');
     },
     asyncCall : function (callback) {
          //...
          callback();
     },
     useAsync : function () {
          var that = this;
          this.asyncCall(function () {
               that.log();
          });
     }
}

//Bind form
var bindExample = {
     log : function () {
          console.log('logger called');
     },
     asyncCall : function (callback) {
          //...
          callback();
     },
     useAsync : function () {
          this.asyncCall(function () {
               this.log();
          }.bind(this));
     }
}

ordExample.useAsync();
//logger called
bindExample.useAsync();
//logger called

As seen from the example above, we can use this in all sort of scenarios – from timers, Ajax callback handlers, event handlers, custom objects etc.

Issues

You cannot unbind after binding a function; anytime you call the Function.prototype.bind, you get a new function which has its ‘this’ context already prefixed to the pre-supplied value.

var fn = function () {};
console.log(fn.bind(this)===fn.bind(this));
//false

Ben Cowboy Alman has written a Function.protoype.unbind polyfill here.

The other issue is that there is some overhead with using bind; it adds some overhead and is not as optimal as using the ‘this = that‘ approach (variable vs function). Here is a jsperf run for four various bind styles.

So that’s it; now go bind some functions.

Standard
Software Development, Version Control

I Git! Stashing Explained


Imagine these scenarios when working in Git:

1. You do not want to commit your unfinished work but need to switch to a new branch to start some new work immediately.

2. A git pull results in conflicts however you do not want to commit local changes yet.

3. You realize you have worked in the wrong branch and want to move your uncommitted work to the right branch.

The Git stash command would help in these situations – it takes all the changes in your working directory and puts them in a stack you can always access later.

The command does two things:

1. It saves the working directory and index to a safe temporary place (the latest stash is usually at .git/refs/stash).

2. Then, it restores the working directory and index to the most recent commit (i.e. the commit pointed to by HEAD).

Thus, you can go ahead and switch to a new branch or complete the pull after a stash.

git stash

It might fail if you do not have any commit in the repository. You need to have at least a single revision as shown below:

git init
git stash
//fatal: Bad revision 'HEAD'
//fatal: Bad revision 'HEAD'
//fatal: Needed a single revision
//You do not have the initial commit yet

Now, let’s try again after making some commits to the repository

echo "Temp" > temp
git add temp
git commit -m "stash first commit"
git stash
//No local changes to save

Next, lets stash some temporary changes; note that stashing does not save changes that are being tracked (more on tracking vs staging areas in an upcoming post insha Allaah).

echo "staging" >> temp

#Add changes to staging area
git add temp
git status
#Should show staged changes to temp

echo "tracking" > tracking
git status
#shows staged and tracked changes

git stash
#Saved working directory and index state
#WIP on master: 2038ddd stash

git status
#clean staging area
#Tracked changes unmodified

Using stashed work

The stash is a stack and can contain multiple changes. The following commands show how to interact with it.

#list all stashed changes
git stash list

#apply the topmost stashed changes
git stash apply

#Show applied changes
git status

#Stash still has applied stash
git stash list

#Pop the stashed change at ref 2
git stash pop stash@{2}

#Show applied changes
git status

#Verify stash@{2} was removed
git stash list

#delete stash at ref 3
git stash drop stash@{3}

#Delete all stash entries
git stash clear

The difference between apply and pop is simple: apply is non-destructive, it preserves the stashed entry on the stack while pop will remove it. The pop command can be seen as an apply + drop combo. And yes, it is possible to create a new branch from a stashed entry.

# create a new branch from stash
git stash branch newBranchForStash

It automatically checks out the branch too; but make sure the branch name is unique!

Done! Happy Stashing!!

Standard
JavaScript, Languages, Programming Languages

Quirky Quirky JavaScript: Episode One


JavaScript is an awesome language however it exhibits some quirks; this posts examines some of these fine odd aspects of JS; dive in, you’ll love it!

First, what do these 3 code snippets do?

3.toString();

void 0;

(3,4);

If your answers were ‘SyntaxError: Unexpected token ILLEGAL‘, undefined and 4; then give yourself a pat on the back! You nailed it. Now, lets find out why…

1. 3.toString() – Decimal Point or Number method?

This throws a SyntaxError because the code is confusing to the JavaScript Interpreter. The dot after the 3 is ambiguous –  does it signify a decimal point or a method of the Number object?

JavaScript chooses to interpret it as a decimal number, it thus expects valid decimal digits after the dot – e.g. 3.0, 3.1, 3.999999999 etc. When it finds ‘toString’ instead of a digit; the interpreter goes KA-Boom! SyntaxError!!

Workarounds

Here are a couple of ways to fix this:

1. Wrap the decimal in parentheses – this forces it to be seen as a single expression; e.g. (3.).toString();.

2. Add a decimal digit after the dot – 3.1.toString(); this removes all ambiguity about the dots: the first is the decimal point while the second is a method from the Number object (after all, there can’t be two decimal points in a single number).

3. Use 3..toString(); this is less readable but works too. As explained above, 3. is a float while 3 is an integer; thus any dots appearing after 3. will definitely refer to a method of the Number object.

2. Void 0 – The Void Operator

This evaluates the expression that appears after it and always returns undefined. void 1, void 2 or void “blah” also work (any expression is fine) however the convention is to stick to void 0.

This can be used to ensure that undefined is always undefined (in JS land, clobbering window.undefined  is fair game). Since the return value of the void operator is guaranteed to be undefined; functions like the one below are employed as safeguards. In fact a couple of JS libraries (e.g. underscore) use this technique quite often.


undefined = "defined"; //Gotcha!

function getUndefined() {
    return void 0;
}

The void operator is also used in bookmarklets (bookmarks that allow you to do stuff by executing JavaScript) and while using the javascript:url coding style (which I assume no one uses…).

In these scenarios; returning a value will make the browser navigate to the returned value. Thus evaluating the expression in a void call kills two birds with a stone – you get to evaluate your expression while still preventing the browser from navigating away.

3. (3,4) – The Comma Operator

The comma operator takes a series of expressions, evaluates all of them from left to right and returns the result of the last expression. This can be leveraged in evaluating multiple scenarios where only a single expression is expected. So you can do something like 2,3,4,5,”wow… this is valid JavaScript!”, 9 and the result will be 9! Impressive huh?

The comma operator should not be confused with the comma separator in variable declarations; that comma separator allows the combination of multiple var declarations into a single one.

The comma operator only occurs within expressions as shown below:


var x = 2,3,4,5,"valid JavaScript!",9
//SyntaxError: Unexpected number

//Wrap in expression
var x = (2,3,4,5,"valid JavaScript!",9)
console.log(x);
//9

If you are pedantic then you find it pleasing to know that the comma operator in JavaScript was taken from the C comma operator

Extra Bonus

The typeof operator is a unary operator but calling it like a function (i.e. typeof(3) ) seems to work perfectly. Strange?

Here is what I believe happens:

typeof(3) -> typeof   (3) -> typeof  3 -> Number

The same reasoning would apply to the void operator; and that’s why you have usages like void (0).

There you go! Now go spread some JavaScript love!! :D

Standard
Computer Science, Languages, Learning, Programming Languages

Programming Paradigms: An Introduction


A programming paradigm is a way of programming, a style of solving problems and thinking about the domain. Languages directly or indirectly influence programming style; for example, Haskell is purely functional while Python allows a blend of OOP, functional and imperative programming.

Even though most new languages are multi-paradigm, they usually make it easiest to program in a single paradigm; C programs can be written in a functional programming style (instead of the orthodox procedural fashion) –  it is just extremely difficult. Ever wondered why classes are needed to add two numbers in OOP Java?

Paradigms can be viewed as abstractions and metaphors for modelling problems – logic programs can be viewed as theorem solvers; functional programs rely on mathematical models while OOP models real-life objects and their interactions.

Nearly every standard problem can be solved using any of the programming paradigms however some problems are best solved using some paradigms (e.g. recursion vs loops). Thus knowing many paradigms helps programmers in producing very neat and elegant solutions; since they know different ways of solving problems and modelling domains.

Let’s take a shallow dive into some of the popular paradigms.

1. Imperative Programming

imperate: Done by express direction, not involuntary; commanded

In the imperative paradigm, programs are written as a series of instructions that affect global state. It is conceptually similar to cooking recipes which strictly list the steps in preparing a dish.

The imperative paradigm was quite popular until Dijkstra published his famous ‘GOTO considered harmful‘ letter. This fueled the adoption of the structured programming paradigm (albeit at the detriment of imperative programming).

2. Structured Programming

Structured programming is somewhat similar to imperative programming however control flow is defined in terms of loops, subroutines and conditionals; this distinguishes it from the imperative model of jumping around at the heck and bequest of every GOTO call.

The introduction of lexical scoping also helps to prevent the inadvertent overwriting of variables in the global scope.

3. Declarative Programming

Declarative programs have implicit execution: programs say what they want but not how the results should be gotten. SQL is a popular example, have you ever wondered how the SQL engine is able to calculate sums, averages, max etc.

A conceptual example is that of a manager declaring sales targets for his marketing team: the team is smart enough to figure out heuristics and also to go do it on their own (hopefully within ethical and legal limits).

4. Functional Programming (FP)

The functional programming paradigm is a subset of the declarative paradigm. All computation is done using functions – it attempts to do away with the use of variables and value assignments.

Pure functional programs are written as a combination of function calls which have no side effects and return the same result every time they are called with the same input no matter the environment. The elegance of FP comes from the use of higher-order functions (functions which can accept/return other functions e.g. differentiation/integration in the maths domain), referential transparency and high levels of abstraction.

On the other hand, some concepts might be inefficient (e.g. Y combinator) or ugly.

5. Object Oriented Programming (OOP)

This is probably the most popular and probably most widely-used of all programming paradigms. Object oriented programming is built on four major principles – encapsulation, polymorphism, inheritance and data abstraction.

OOP allows the creation of abstract models that mirror real-life objects’ interactions and behaviour. This enables the creation of huge complex software systems having intricate interactions such as state preservation, communication exchanges and behaviour handling.

There are two flavours: classical (where objects are defined and share their characteristics and behaviour based on a class’ blueprint) and prototypical (objects get their behaviour and characteristics from an original prototype object).

Conclusion

Some other paradigms include the event-driven where program respond to events (think web apps) while the logical programming paradigm tries to infer the solution when it is given a set of constraints and or conditions.

Upcoming posts would insha Allaah take a more thorough look at some of the popular paradigms.

Standard
Design Patterns, JavaScript, Languages

The Immediately Invoked Function Expression


The Immediately Invoked Function Expression (IIFE, pronounced iffy) is a named/anonymous function expression that is executed immediately after its declaration.

It typically involves appending the function invocation operator ‘()’ to the end of a function expression; this triggers its immediate invocation.

(function () {
    console.log("IIFE!");
})();

//Another style
(function () {
    console.log("IIFE!");
}());

//passing in variables
(function ($) {
    console.log('jQuery:', $);
})(jQuery);

Some background

The IIFE used to be wrongly regarded as a Self Invoked Anonymous Function (SIAF) until Ben “Cowboy” Alman (of GruntJS and tinypubsub fame) suggested the more appropriate IIFE term. An IIFE does not have to be self-executing or anonymous all the time.

//Named function expression
!function name() {
    console.log("IIFE!");
}();

Self Invoked Anonymous Functions (SIAF)

A self-executing function is a function that executes itself, a self-executing function would usually have this pattern:

function selfExecFn() {
     selfExecFn();
}

Anonymous functions are function expressions with no identifiers/names.

(function () {
    //...code here
})()

A SIAF has to be both self-executing and anonymous right? Anonymous functions have no identifier, thus the callee property of the arguments object is used to achieve self-invocation – arguments.callee always refers to the currently executing function.

Combining all these, a self-invoked anonymous function will look like the code snippet below:

(function () {
    arguments.callee();
})()

Note: arguments.callee is going to be deprecated and does not work in EcmaScript 5’s strict mode. So technically, it’ll be impossible to create a SIAF!

Aside, I wonder why they are not called recursive anonymous functions – RAF which sounds much more apt.

What are the uses of the IIFE?

1. Data encapsulation is probably the biggest benefit. IIFEs help to prevent properties in the global object from getting overwritten and/or polluted while protecting the local variables from external parties. This is what makes it possible to use libraries like jQuery and Prototype which both override the $ variable side by side.

2. IIFEs create closures  which can be used in turn to simulate ‘private’ variables in JavaScript.

3. Comes in handy for the module pattern.

Want to achieve a deeper understanding of JavaScript? Here are a couple more posts:

1. The JavaScript Function

2. Three Important JavaScript Concepts

3. Defining JavaScript Functions

Standard