Java doesn't have pointer types. Perl does, but doesn't allow pointer arithmetic. C++ has pointers and allows pointer arithmetic like this:
int *p; p = new int(5); p++;
Show, by example, that use of pointer arithmetic can allow a function in C++ to access variables that it should not be able to access according to the binding rules of C++.
In C++, but not Java, a pointer can hold either the address of an object allocated on the heap or on the stack. For example,
int *p, *q;
void f()
{
int x = 10;
q = &x; // q points to an int on the stack (in f's A.R.)
}
void g()
{
int y = 5;
p = new int; // p points to an int allocated on the heap
*p = y;
}
int main()
{
f();
cout << "*q after f(): " << *q << endl; // dangling pointer
g();
cout << "*p after g(): " << *p << endl;
// Check *q's value after calling g.
cout << "Now check *q: " << *q << endl; // dangling pointer
return 0;
}
In the BNF grammar below, @ and # are binary operators. Which has higher precedence?
<E> ::= <E> @ <T> | T <T> ::= <P> # <T> | <P> <P> ::= a | ( <E> )
In the previous problem, is @ left-associative or right-associative? (Left associative means that in the expression, a @ b @ c, the left operator, a @ b, is executed first.)
Is the operator # left associative or right associative?
Assume all operators are right associative, but with the usual precedence. Draw a syntax tree (with operators as nodes and numbers as leaves). What is the value of the expression?
52 - 20 / 2 * 5 - 1
Extended BNF notation (EBNF) for grammars uses { x } to mean 0 or more occurrences of x and [ x ] to mean 0 or 1 occurrences of x. EBNF can always be converted to equivalent BNF, although EBNF is usally easier to read. Convert the following EBNF grammar to an equivalent BNF grammar:
<Exp> ::= <Term> { + <Term> }
<Term> ::= id | ( <Exp> )
Hint: Replace { + <Term> } by a new non-terminal, <MoreTerms>, which can generate 0 or more occurrences of + <Term>. E.g.,
<Exp> ::= <Term> <MoreTerm> <MoreTerm> ::= ... <Term> ::= id | ( <Exp> )
Assume identifiers are bound to declarations using lexical scope binding (static binding). Draw an arrow from each identifier to its corresponding declaration. If an identifier has no corresponding declaration (i.e., if it is free), circle it.
fun M(x:int):int =
(
let
fun P(y:int):int =
(
let
fun Q(x:int):int =
(
x + y
)
in
x + Q(y)
end
)
in
x + P( a )
end
);
What is the output of:
int n = 5;
F(int x, int y)
{
x = x + n;
print (x,y);
y = x;
}
main()
{
int n = 10;
int x = 1;
F(x,x);
print x;
}
|
assuming parameters are passed a. by value b. by reference c. by value-result d. by macro expansion |
Assume a block structured language uses lexical scope binding. Procedures P, Q, R, S and T are nested in some fashion inside M, which is at level 0. Suppose it is legal for Q to call S. If Q is at level 2, what can you say about the level of S?
Assume lexical scope binding (static binding). Give the output of the first print statement executed and draw the stack of activation records and their contents at that point. Include the static link, dynamic link (or frame pointer), and local variables (with their current values) and the return address in each activation record. Use the line numbers to the left for addresses.
void m()
{
int a, b;
void P()
{
int a;
1) a = 5;
2) Q();
3) print(a,b);
}
void Q()
{
4) b = a + 1;
5) print(a, b);
}
6) a = 10;
7) b = 20;
8) P();
9) print(a,b);
}
M()
{
P()
{
Q()
{
}
}
R()
{
}
}
Suppose that the program begins execution and M calls P and then P calls R. At that point can R call Q if
What is the type of each of the following ML functions?
(The answer should be in the form: type1 -> type2, where type1 is the parameter type and type2 is the return type.)
fun f(x) = ( [x] )
fun f(x,y) = ( (x+1.0)::y )
fun f(x) =
(
case x of
nil => nil
| y::ys =>
(y+1)::f(ys)
)
fun f(x,y) = ( x@[y] )
Show the stepwise evaluation of fill(0, [2,0,1],
5). That is, for each call to fill, show the arguments and
substitue the arguments into the body and evaluate.
fun fill(k, lst, n) =
(
if length(lst) >= n then
lst
else if member(k, lst) then
fill(k+1, lst, n)
else
fill(k+1, k::lst, n)
);
Is the previous function tail-recursive?
Given the ML datatype
datatype 'a bintree =
EMPTY
| Leaf of 'a
| Node of ('a bintree) * 'a * ('a bintree);
Write an ML function, nodeCount: 'a bintree ->
int, which returns the number of non EMPTY "nodes" in a
bintree.
Block structured imperative languages have used stack based allocation for activation records. In such languages a function P which has a function Q nested inside of P cannot have its return value be the function Q. Briefly explain why this is not allowed.
Functional languages do allow functions to be return values of other functions. In particular, a function P which has a function Q's definition nested inside of P can have its return value be Q. More precisely, P returns a function closure for Q. A function closure consists of two parts. One part is the code for the function. What is the other part?
What is the output for the following C++ object method calls?
class B
{
public:
void executeTask(string s)
{
this->prepare(s);
this->execute(s);
}
virtual void prepare(string s)
{
cout << "B::prepare " << s << endl;
}
virtual void execute(string s)
{
cout << "B::execute " << s << endl;
}
};
class D: public B
{
public:
virtual void prepare(string s)
{
cout << "D::prepare " << s << endl;
}
virtual void execute(string s)
{
cout << "D::execute " << s << endl;
}
};
int main()
{
B b, *pb1, *pb2;
D d;
pb1 = new B();
pb2 = new D();
b.executeTask("stack B");
d.executeTask("stack D");
pb1->executeTask("heap B");
pb2->executeTask("heap D");
}
Use the example of the previous problem to explain the difference between static and dynamic dispatch. In particular, which is used for each of the calls:
pb1->executeTask("heap B");pb2->executeTask("heap D");this->execute(s);this->prepare(s);Java allocates objects only on the heap. C++ can allocate objects either on the heap or on the stack. When are objects deallocated in Java? In C++? (For C++ distinguish between heap and stack allocated objects.)
Objects are allocated on the heap in Java and method dispatch is (almost) always dynamic by default. When is method dispatch dynamic in C++? When is it static in C++?
Consider the following function, and refer to the classes B and
D in a previous problem. The function f is a
polymorphic function? What different types can be passed
to f? Does f do different things (print differently)
depending on what type is passed to it?
void f(B *pb)
{
pb->prepare("task");
pb->execute("task")
}