Tuesday, January 19, 2016

What if there are no looping constructs in your language?

Being a professional software engineer, we cannot say that we are done we cannot program without looping control flow. Developers who started their career in machine or assembly language don't get scared of this. Similarly who understood and practiced machine and assembly language in college in. They will simply use 'go to' along with if statement and get the things done.

Forgot to tell in the question 'go to' is banned as always.So how can we tackle it without goto.

Lets come to code. Here we are going to see the scenario in 2 famous languages C# and Javascript. Below is the code to display numbers 1,2,3...10 in descending order which is written using loops.

JavascriptC#
function LoopWithWhileKeyword(loopCount) {
    while (loopCount > 0) {
        logLine(loopCount);
        loopCount -= 1;
    }
}
void LoopWithWhileKeyword(int loopCount)
{
    while (loopCount > 0)
    {
        logLine(loopCount);
        loopCount -= 1;
    }
}

This is straight forward. The code to call these functions is omitted to get focus, Now lets think how we can avoid this loop.

What is happening here

If we step back and think we can see there are mainly 2 code blocks. 
  • One block determines the continuation of execution.
  • Second is the actual code to execute multiple times.
Some idea might have triggered in everybody's brain who had done some programming. Nothing but extracting those separate blocks to functions.

We can use 'if' statement to decide whether to continue execution or not based on the return value if we move the condition logic to function. Then how do we execute the repeatable code block again without go to?

Execute the same function again. All of us has tried this in college when dealing with Fibonacci series. If we call a function from inside same function we can simulate loops. Yes recursion!!!

Lets see the code below which is rewritten with recursion.
JavascriptC#
function LoopWithoutWhileKeyword(loopCount) {
    WhileLoop(function () {
        return loopCount > 0
    },

    function () {
        logLine(loopCount);
        loopCount -= 1;
    });
}

function WhileLoop(condition, action) {
    if (condition()) {
        action();
        WhileLoop(condition, action);
    }
}
void LoopWithoutWhileKeyword(int loopCount)
{
    WhileLoop(
        () => loopCount > 0,
        () =>
    {
        logLine(loopCount);
        loopCount -= 1;
    });
}
void WhileLoop(Func<bool> condition,
Action action)
{
    if (condition())
    {
        action();
        WhileLoop(condition, action);
    }
}

Good. Isn't it? For those who gets headache on seeing recursion please read the explanation.

Here the WhileLoop function accepts 2 functions. It checks whether I should continue or not. Similar to the evaluation inside the while loop condition check. If the result of condition check is true, it calls the action method which has the code  needs to be executed multiple times.

Then it calls the WhileLoop function again to repeat the cycle. Since the action function has the code to reduce the loop count, it will end when the loopCount becomes 0.

Higher Order Function

We learned a jargon in programming called Higher Order Function. Any function which accepts another function or returns a function can be called as higher order function. Thinking that its this simple refer wiki

Most of us might be thinking, why we learned the loops if functions can do the job of loops. Why there are many ways to do same thing in computer science?

Tail call optimization

Normally developers has a tendency to use new things learned in their day job because of excitement. They might have heard it or saw one demo which touched the good parts of the concept / feature / technology.

Before anybody apply this technique in your production app understand and test it properly. Let's test this code by given 100,000 to the function.

In C# your will encounter 
An unhandled exception of type 'System.StackOverflowException' occurred in mscorlib.dll

In browser, you will get 
Uncaught RangeError: Maximum call stack size exceeded

In my machine I got javascript error when the recursion reaches 17911 and c# 4.0 failed after 12202 iterations.

Don't think that this issue will occur always. There are technologies and languages in which this issue will never occur. If we we are getting this, that tells us that our run-time or compiler does not do tail call optimization. Google for what is tail call optimization.

1 comment:

Blogger said...

If you want your ex-girlfriend or ex-boyfriend to come crawling back to you on their knees (even if they're dating somebody else now) you need to watch this video
right away...

(VIDEO) Win your ex back with TEXT messages?