Tail Call Optimization

From wikipedia

… the main reason for having a Call Stack is to keep track of the point to which each active subroutine should return control when it finishes executing …

Call stack is also used to store the local variables and parameters. Maintaining the stack is very important and no need to mention that it grows based on the function calls we make.

If the last expression of a function (say funA) is nothing but another function (say funB) call, it is called the tail call and it can be easily optimized by the compiler. Compiler recognizes that once funB is done, there is no need to return back to funA and based on this a call stack entry is saved. Please note that the tail function call should be the whole, complete last statement not just a part of the last statement.

This optimization may not be seen as a big thing in imperative programming. But when it comes to the languages where we don’t have the loop constructs, this optimization brings us the huge benefit. Recursive functions can reap considerable benefits based on this.

If the iterative versions of the corresponding recursive versions work faster, then it should be mainly due to the overhead involved in managing the stack.

Though recursive, factorial(50) may return the result quickly but fibonacci(50) would take too much time. This is because the recursive call occurs only once for factorial (factorial(n) = n * factorial(n)) whereas for fibonacci it occurs twice (fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2)).

Please see how the recursive factorial function can be optimized to make tail calls.

(Not sure about the Tail Recursive version of Fibonacci terms calculation. I would be happy to see one.)
<update> Simple search on Google returned http://tratt.net/laurie/tech_articles/articles/tail_call_optimization </update>

So, it means that it is still in the programmers’ hand to write the efficient code.

Food for thought: Apart from loops and recursion, is there any other way to accomplish the same but in a faster manner?

Happy Programming!
Cheers!

Advertisements

Interviewing and Coding

Recently (around Sep 2012) I got a chance to interview a few persons (five) but I did not select any one of them. It was because that I interviewed them with a constraint that they should be able to write some good code. I also expected a couple of questions from them by framing my questions ambiguously. I wonder whether I did anything wrong there.

The first two were of 2 to 3 years of experience; the other one was with 1 to 1.5 years; the fourth one with 6 years of experience and the fifth one also with 1 to 1.5 years of experience.

The first two answered more or less very similarly (yes, both of them from same team).
They told about their application clearly. They were aware of ETL concepts. They also knew something about Unix (including vi editor). They also mentioned that they tuned a few queries by replacing IN with EXISTS. Both of them mentioned the same SQL tuning. They didn’t do any application level tuning. One of them told that it was based on guidance from senior members. And the other one cleverly mentioned that he tuned by himself (but he told he referred Google).

They were not exceptional but they were good enough to fill in the requirement we had.
Though with some IFs and BUTs, I was really impressed with them.
To finish-off the interview, I asked them to write a simple PL/SQL procedure which prints no. of employees in a particular department and no. of departments. (Well, the question is not exactly this, but sort of this). (Standard SCOTT schema; EMP;DEPT tables).

The 1st person wrote a SQL query without any line breaks (or) indentation. But perhaps he word-wrapped it. The 2nd one wrote a query without using the parameter which the procedure takes.

The 3rd person had 1.5 years of total experience but worked only 2 months each in 3 projects. He was on bench for the other 1 year. I did not expect anything. But he tried so hard to answer my questions. Though I appreciate that he wanted to answer, he should not have struggled at the time of interview. He should have put some efforts on interview preparation, at least. (Even I was rejected once for the same reason. I understood now why they rejected me 😉

The 4th person had 6+ years of experience which is similar to my level of experience. So, I hesitated to interview him. I thought that he might also be a better skilled person compared to me. But it was topsy-turvy. He spoke a fluent English but when I gave the same task to print the no. of employees for a particular department, he just wrote four words “CREATE OR REPLACE BEGIN” and then told “I don’t know”. I did not want to disappoint him by quitting the interview at that moment itself. So, I asked him a few more questions for which also I received the same answer “I don’t know”.

It is not me who decided on whether to select or not select. It is the time constraint we had in our project. We did not have enough time to train the persons. “There is no plan to attack. Attack is the only plan”. With enough time, I would have gone to take either the 1st or 2nd person.

I just asked “the programmers” to write 10-15 lines of code.
Am I asking inappropriate stuff?

I read somewhere in the web that hiring a programmer who does not write code is like hiring a driver who does not know what a clutch is.

After these four interviews, the fifth interview was a good one.
She had 2 years of experience. She use to write SQLs for generating reports but our project requirement was to migrate PL/SQL code to Perl. Whatever the question shooted from SQL, she answered perfectly. She wrote the SQL code for two queries. We selected her and she quickly learned Perl and PL/SQL in no period of time.

Happy on selecting her!

Datatypes in JavaScript and Perl

Oracle PL/SQL is a strongly-typed language.
Which means when declaring the variables, we need to specify the data-type as well.
(Note: PL/SQL is not discussed here)

We do not do it either in JavaScript or Perl.
But, there is a subtle difference exists.

function fun1() {
    var x1 = "4", x2 = "2";  // though numbers, if quoted, got treated as string
    alert(x1 + x2);
    var y1 = 4, y2 = 2;
    alert(y1 + y2);
}
fun1();

In the above JavaScript snippet, the “+” operator, when one of its operand is a string, acts as a concatenation operator or else additive operator.
In Perl, we need to use two different operators for these operations.

sub fun1 {
    my $x1 = "4"; my $x2 = "2";
    print $x1 . $x2, "\n";       # concatenation operator is dot "."
    my $y1 = 4; my $y2 = 2;
    print $y1 + $y2, "\n";
}
fun1();

What if we want to add two numbers stored as a string?

function add(a, b) {
    return a + b;
}
alert(add(4, 2));
alert(add("4", "2"));
alert(add("x", "y")); // This also works

Our “add” function breaks when the quoted numbers are passed.
We can rewrite the function as below.

function add(a, b) {
    a = parseInt(a, 10);  // 2nd arg to parseInt is the radix
    b = parseInt(b, 10);
    return a + b;
}
alert(add(4, 2));
alert(add("4", "2"));
alert(add("x", "y")); // Are you serious? Want to add two strings?

parseInt function takes the stringified number as the argument and returns the actual number.
In Perl, there is no parseInt equivalent. The parsing is taken care automagically.

sub add {
    return $_[0] + $_[1];
}
print add(4, 2), "\n";
print add("4", "2"), "\n";
print add("x", "y"), "\n"; # Here the result is Zero!

Perl does more with Strings and Numbers.

sub fun2 {
    my $x = "AA98";
    $x++; print "$x\n";
    $x++; print "$x\n";
}
fun2();