edited by
9,095 views
40 votes
40 votes

The following program fragment is written in a programming language that allows global variables and does not allow nested declarations of functions.

global int i=100, j=5;
void P(x) {
	int i=10;
    print(x+10);
    i=200;
    j=20;
    print (x);
}
main() {P(i+j);}

If the programming language uses static scoping and call by need parameter passing mechanism, the values printed by the above program are:

  1. $115, 220$
  2. $25, 220$
  3. $25, 15$
  4. $115, 105$
edited by

5 Answers

Best answer
29 votes
29 votes

Answer : D

First refer the following question on Call-by-name parameter passing technique then solve this question.

https://gateoverflow.in/43575/gate2003-74?show=338119#a338119

Call by Name vs. Call by Need :

Assume X is the formal and e the corresponding actual expression. 

Call-by-Name : 

1. Delays evaluation of arguments past call until a reference to the formal.

2.  Re-evaluates argument e on each reference to X in environment of caller.

3.  No local variable X is allocated

Call-by-Need : 

1. Delays evaluation of arguments past call until a reference to the formal.

2.  Evaluates e on 1st reference in environment of caller & loads local variable X; no re-evaluation: subsequent references use local X


Since "Call by need"  parameter passing technique, it is almost same as Call-by-name But the difference is that Actual argument is evaluated only once(on the first reference) and then that value is saved and re-used on further references But the actual argument is Not re-evaluated.

Caller function's Actual argument contains variable $i$ which clashes with called function P's local variable $i,$ hence, we rename called function P's local variable $i$ and change it to $i'.$

global int i=100, j=5;
void P(x) {
    int i'=10;   // this i' refers to the local variable i' in function P.
    print(x+10);  // this is first reference of x, so here, x= i+j, and these i,j refer to i,j in the caller function i.e. main function's environment
    i'=200;    // this i' refers to the local variable i' in function P.
    j=20;      // this j refers to j in the caller function i.e. main function's environment
    print (x);   // this x is second reference, so, we do not replace it with i+j because in call by need, we do not re-evaluate. So, we use the already calculated value of variable x and use it here.
}
main() {
    P(i+j);
}

In case of Static scoping : 115, 105

In case of Dynamic scoping : 115, 105

Note that there are no local variable $i,j$ in main function, so, when we say that $i,j$ refer to the $i,j$ in main's environment , we mean that If $i,j$ were accessed/updated in main function then depending on the scoping, which $i,j$ would they refer.

Here, in this question, in both static and dynamic scoping case, $i,j$ will refer to the Global variables. 

And in function P, in the 4th statement (i.e. $j = 20$), the Global variable $j$ will be updated. 

selected by
36 votes
36 votes

Call-by-name : Is a lazy evaluation (expression passed as an argument evaluated only when used) technique.

Call-by-need: Is a version of call-by-name but when an expression is evaluated during first use, is saved and reused for all later uses.

global int i=100, j=5; 
//memory created for i and j variable and 100 and 5 stored in them respectively (1)

void P(x) {// p(i+j) (3)
    int i=10;
    // new variable created i with value 10 store in it. (4)
   
    print(x+10);
    // print(x+10); = print(i+j +10);= 10 + 5 +10 = 25  
    // here need of i+j so i+j replced by 15 evrywhere .(5)
   
    i=200;
    // local i value changed to 200. 
    
    j=20;
    //global j value changed to 20 as there is no local j.
    //if dynamic scoping used, then the scope of j comes from scope of j in main as 
    //main called this function. Here, main also uses global j and hence no change.
    
    print (x);
    // print (x);= print (i+j); = printf(15) = 15 (7)
    // due to call by need. If call by name used answer is 200+20 = 220
}
main() {P(i+j);}  
// 1st function call since it is call by need no evaluation done 
//here i and j value refer to global values(2) 

Answer is (C).

Reference : https://www.cs.bgu.ac.il/~comp161/wiki.files/ps9.pdf

edited by
15 votes
15 votes

In Gate official keys the answer for this question is given as the option (D) and for the next one it is (A) and that is the correct solution.

Call-by-Name: Here the expression is evaluated every time it is requested, no cache is stored.  

Call-by-Need: Here the expression is evaluated only once and it is stored for further reference, no cache is stored.  

In static scoping, the local variables have more preference than global variables if the name of both the variables is same. In dynamic scoping, the global variables are preferred over local variables. 

Now let us look at the program.

Static scoping and Call-by-need

global int i=100, j=5;
void P(x) {
	int i=10; // Local variable declared and initialized to value 10
    print(x+10); //Requested the evaluation of the expression, but the expression uses global i not local i so x + 10 = i + j +10 = 105 +10 =115 
    i=200; // Local i assigned to 200 as static scoping prefers local variable
    j=20; // No confusion here, the global value is changed to 20
    print (x); // Here again as it is Call-by-Need and is only evaluated once so this will print 105 as x is 105
}
main() {P(i+j);} // Here the expression i+j is passed but it is not evaluated yet.
Here in static scoping the local variable is preferred over global but that does not mean that in print(x) line, i is local variable but it is the global one as the expression is evaluated from the scope of the main() function from which it was called.
So the answer is (D)

Dynamic scoping and Call-by-name

global int i=100, j=5;
void P(x) {
	int i=10; // Local variable declared and initialized to value 10
    print(x+10); //Requested the evaluation of the expression, but the expression uses global i not local i so x + 10 = i + j +10 = 105 +10 =115 
    i=200; // Here is the difference where assignment of is done on the global one not the local one
    j=20;// Here global value is changed.
    print (x); // Now again expression is requested as it is call by name and now as the global values have changed so the answer is 200 + 20 = 220 
}
main() {P(i+j);} // Here the expression i+j is passed but it is not evaluated yet.
(A) is the answer


 

  

3 votes
3 votes
Static scoped and call by need..

Call by need means if any expression is evaluted that is stored and later on used when same expression is needed..

Here in first printf : I + j is evaluated..

Since it is of static scope..

I= 10 and j= 5 so I + j is 15

So first printf prints 25

Now second printf : I+j which is already evaluated that is 15

So it prints 15

Ans.C
Answer:

Related questions

22 votes
22 votes
3 answers
4