2
$\begingroup$

This is question is related to this past question.

I am currently studying the textbook Principles of Program Analysis by Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Chapter 1.4 Constraint Based Analysis says the following:

1.4 Constraint Based Analysis The purpose of Control Flow Analysis is to determine information about what "elementary blocks" may lead to what other "elementary blocks". This information is immediately available for the $\mathrm{While}$ language unlike what is the case for more advanced imperative, functional and object-oriented languages. Often Control Flow Analysis is expressed as a Constraint Based Analysis as will be illustrated in this section.
Consider the following functional program:

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

It defines a higher-order function f with formal parameter x and body x 1; then it defines two functions g and h that are given as actual parameters to f in the body of the let-construct. Semantically, x will be bound to each of these two functions in turn so both g and h will be applied to 1 and the result of the computation will be the value $7$.
An application of f will transfer control to the body of f, i.e. to x 1, and this application of x will transfer control to the body of x. 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: $$\text{For each function application, which functions may be applied.}$$ As is typical of functional languages, the labelling scheme used would seem to have a very different character than the one employed for imperative languages because the "elementary blocks" may be nested. We shall therefore label all subexpressions as in the following simple program that will be used to illustrate the analysis. Example 1.2 Consider the program: $$[[ \text{fn} \ x => [x]^1]^2 [ \text{fn} \ y => [y]^3]^4]^5$$ It calls the identity function $\text{fn} \ x => x$ on the argument $\text{fn} \ y => y$ and clearly evaluates to $\text{fn} \ y => y$ itself (omitting all $[ \dots ]^\mathscr{l}$).

I'm unsure about this part:

It calls the identity function $\text{fn} \ x => x$ on the argument $\text{fn} \ y => y$ and clearly evaluates to $\text{fn} \ y => y$ itself (omitting all $[ \dots ]^\mathscr{l}$).

Looking at the program $[[ \text{fn} \ x => [x]^1]^2 [ \text{fn} \ y => [y]^3]^4]^5$, aren't the statements $\text{fn} \ x => [x]^1$ and $\text{fn} \ y => [y]^3]$ executed separately, the former first and then leading to the latter? So what do the authors mean when they say that "it calls the identity function $\text{fn} \ x => x$ on the argument $\text{fn} \ y => y$ and clearly evaluates to $\text{fn} \ y => y$ itself (omitting all $[ \dots ]^\mathscr{l}$)", because this sounds like something different? Am I misunderstanding this?


EDIT:

This chapter's slides from the textbook's website.

$\endgroup$
6
  • $\begingroup$ @D.W. I'll delete the one on cs.stackexchange, since someone asked a highly related question from the same textbook on cstheory in the past. $\endgroup$ – The Pointer Dec 6 '20 at 4:00
  • $\begingroup$ This is a duplicate of cs.stackexchange.com/questions/132947/…, please delete this instance as it is not research-level. $\endgroup$ – Andrej Bauer Dec 6 '20 at 9:54
  • 1
    $\begingroup$ Ah ok, not quite a duplicate, but certainly this question does not belong here, because it is not research-level. It is about understanding how functional programs work. $\endgroup$ – Andrej Bauer Dec 6 '20 at 9:55
  • 1
    $\begingroup$ Hi @AndrejBauer. Are you sure? I asked it here because I saw this cstheory.stackexchange.com/q/8354/44297 question, which is from the same section of the same textbook, so I thought that it would be appropriate. $\endgroup$ – The Pointer Dec 6 '20 at 15:25
  • $\begingroup$ Yeah, I downvoted that one as well :-) $\endgroup$ – Andrej Bauer Dec 6 '20 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.