Thursday, February 14, 2008

Function as parameter

All decent programming language allows function calls, with parameters.

Level 1 of parameter is a literal. It's safe, the literal is read-only and has no side effect outside the scope of the function.

Level 2 of parameter is a variable. More useful, but may have side effect if the variable is modified in the body of the function. Even when variables are copied before the function call, they can still points to data that may be modified.

Level 3 is a function. Even more power, but more risks. Some programming languages allow to pass functions as parameter, directly or indirectly (like a parameter of type Runnable in Java).

Why is it more dangerous than variables ?

Let's take a symbolic function, name it delta, with the following body:
void delta(x) { x(x); }
which reads "delta of x does: x applies to x". In lambda-calculus, it is written D = (\x.xx). I'll stick with this notation as it is more compact. Delta looks harmless. I mean, there is no obvious bug in the body of delta.

However problem occurs when you apply, for instance, delta to itself:

DD = (\x.xx)(\x.xx), and when you apply D to D, you substitute x in the first D by the second D, and you obtain (\x.xx)(\x.xx), i.e. DD.

So no way to escape, when the machine computes DD, the result is still DD and we enter in an infinite loop.

A slight variation, D' = (\ is even worth because D'D' -> D'D'D' -> D'D'D'D' -> etc. D'D' is then a growing infinite loop.

So you see the hazard. The body of D (or D') looks safe. There is no explicit infinite loop inside. Actually D explodes only with suitable parameter that behaves as the second half of the bomb. That's something that couldn't occur with level1 or level2 parameter. Careful with that level3 parameter, Eugen.

No comments: