A question in constraint based analysis

Question

I may have a very naive question on Constraint Based Analysis. (a technique of static program analysis).

I am reading an informal introduction from F. Nielson

He gives such an example,

let f = fn x => x 1; 
    g = fn y => y + 2;
    h = fn z => z + 3
in (f g) + (f h)

The author explained that:

...the problem is that we cannot immediately point to the body of x: we need to know what parameters f will be called with. This is exactly the information that the Control Flow Analysis gives us:

For each function application, which functions may be applied.

However, in my naive point of view, this information can be obtained statically and exactly, at least seen from this example. It suffices to check the "in-" part of the instruction "let...in..." to decide the functions that may be applied, doesn't it?? Although I do see in OO programming, it would not be evident to decide what the virtual calls really calls at run-time, I find from this above example that this piece of information can be obtained in a trivial way by looking at its syntax.

So where am I wrong? Thank you for your ideas.

Answer 1

Can you point to where this example comes from? It might help.

I think the author is trying to express something a little different than what you're anticipating with this example. For instance, for a C programmer reading this introduction, this example would illustrate that "x 1" in the first line isn't like x(1) in C, it's more like (*x)(1) in C -- you're calling a function there, sure, you even know the type of the function you're calling, but you don't know which function. Certainly you are correct that in this example you can figure out "oh, it's either got to be the function associated with g or the function associated with h." But I posit that when you sort this out in your own head, what you're doing is just executing the program, which is of course the most straightforward way of "statically analyzing" any terminating code!

The example is small; any example that's going to be easy enough for you to straightforwardly understand is, almost by definition, going to be one where your brain can "statically" figure out the answer. The challenge that Control Flow Analysis tries to solve is working over potentially large programs, quickly and precisely.

Answer 2

I actually recognize that fragment since I'm still reading that book.

Your insight is correct, you just misinterpreted the author when he writes. "... we cannot immediately point to the body ....". By immediately he means without reasoning about the code, be it your own reasoning expressed in your question, or by the Constraint Based Analysis being introduced by the book.

Constraint Based Analysis is just another way a computer can tell which of the two functions will be bound to x at each step of the execution.

It is a great book. You do need to know your math for this one.