Archive for July, 2009

Good! F# (May 2009) support tail recursion very well!

July 23, 2009

What’s the tail recursion?

In computer science, tail recursion (or tail-end recursion) is a special case of recursion in which the last operation of the function, the tail call, is a recursive call. Such recursions can be easily transformed to iterations. Replacing recursion with iteration, manually or automatically, can drastically decrease the amount of stack space used and improve efficiency. This technique is commonly used with functional programming languages, where the declarative approach and explicit handling of state promote the use of recursive functions that would otherwise rapidly fill the call stack. (from Wikipedia)

Still don’t understand? OK, let me show you the code.

int f(int n) {
    return f(n + 1);    // it's the last operation.
}

If you run f(0), you will get a StackOverFlowException.

How about F#?

let rec f n = f (n + 1)

The keyword “rec” tell compiler it’s a recursive function.

We use Reflector to see how it looks like as a C# code:

public static a f<a>(int n)
{
    while (true)
    {
        n++;
    }
}

The magic the compiler done is called Tail Call Optimization. (see Adventures in F#–Tail Recursion in Three Languages)

Another case of tail recursion:

type t() =
member x.f1 n = x.f2 (n + 1)
member x.f2 n = x.f1 (n + 1)

This time, when you run t().f1 0, you will get the StackOverFlowException too.

Don’t worry. Just open the F# project properties dialog and the Build tab. Check the “Generate tail calls” on. Then the exception disappeared.

See what’s different of the IL code:

“Generate tail calls” unchecked

.method public instance !!a f1(int32 n) cil managed
{
.maxstack 5
L_0000: nop
L_0001: ldc.i4.s 0x2e
L_0003: call void [mscorlib]System.Console::Write(char)
L_0008: ldarg.0
L_0009: ldarg.1
L_000a: ldc.i4.1
L_000b: add
L_000c: call instance !!0 Program/t::f2(int32)
L_0011: ret
}

“Generate tail calls” checked


.method public instance !!a f1
(int32 n) cil managed
{
.maxstack 5
L_0000: nop
L_0001: ldc.i4.s 0x2e
L_0003: call void [mscorlib]System.Console::Write(char)
L_0008: ldarg.0
L_0009: ldarg.1
L_000a: ldc.i4.1
L_000b: add
L_000c: tail
L_000e: call instance !!0 Program/t::f2(int32)
L_0013: ret
}

One more case:

type t() =
member x.f3 n = x.f3 (n + 1)

No matter you check the “Generate tail calls” or not, the compiler will do the Tail Call Optimization.

The reflector will render it like this:

public a f3<a>(int n)
{
    while (true)
    {
        n++;
        this = this;
    }
}

Scala compile will do the Tail Call Optimization too, but there’s no “tail” in JVM until now. So we need to wait for the Java 7.

.NET’s CultureInfo do not support all languages in ISO 639-1

July 4, 2009

When I wanna replace the Language enum in Google translate API for .NET, I found that, there are at two three language that Google supported but .NET Framework not.

The Filipino (tl) or Tagalog;

The Maltese (mt).

And the Hebrew, Google use “iw” as the code for its language api, but .NET and ISO 639 use “he”.

Well, where is the Babel?!

Reset your firefox location bar search if it changed by AVG

July 4, 2009

When you install the latest AVG free, it will install two firefox addons, AVG safe search and AVG security toolbar.

Disable them by Tools->Addons, click the Disable on them.

But AVG also change your location bar. When you input some keyword, it used to go to that website directly or search it as keywords by google. Now it becomes yahoo search!!!

If you don’t like yahoo or you just wanna another search engine, you can change by the steps below:

  1. Type “about:config” in the location bar and click “enter”. Now you can see the configuration page for your firefox.
  2. Find out the “keyword.URL” and reset or modify the value.
  3. Close the configuration page. Then your old location bar comes back.