CMPSC 461: Programming Language Concepts Final Exam Practice Questions
Use these problems in addition to previous HWs, midterms, practice problems to prepare for the final exam.
Problem 1 There are two approaches of checking the validity of a Hoare triple: forward reasoning and backward reasoning. The former starts from the desired precondition, and checks whether the computed strongest postcondition for the program implies the desired postcondition; the latter starts from the desired postcondition, and computes the weakest precondition rather than the strongest postcondition. What makes the second approach more appealing and popular in practice?
Problem 2 Use the following three rules we gave in lecture to prove that the following two Hoare triples are valid.
• wp(x:=e, Q)=Q[x ← e]
• wp(s1;s2, Q)=wp(s1,wp(s2,Q))
• wp(if (E) s1 else s2, Q) = E ⇒wp(s1,Q)∧¬E ⇒wp(s2,Q)
1.
2.
Problem 3 The following program sets the return value r to 1 + 2 + · · · + n where n is an input. Write down a loop invariant and show that the Hoare triple is valid. Recall that a loop invariant should be 1) true before the first execution of the loop, 2) true after the execution of each loop iteration, given that the loop condition and the invariant are both true before the iteration, and 3) strong enough to prove the correctness of the code (i.e., r = Sum(n) is true after the loop, if it terminates).
To simplify your notation, assume Sum(n) is a function in logics that returns ni=1 i.
{n>0}
i := 1;
r := 0;
while (i ≤ n) {
r := r + i;
i++; }
{r = Sum(n)}
Problem 4 What are the key elements in any OOP language? Briefly explain every element in your own
words.
Problem 5 What is the difference between static and dynamic dispatching? Which dispatching method is used to implement subtype polymorphism?
Problem 6 Consider the following classes defined in Java, which uses dynamic dispatching.
{x > −1}
y := x + x; y := y + 2; {y > 0}
{y>=0}
if (y<1) x := y+1; else x := y; {x>0}
1/2
class A {
public int a () { return 5;}
public void b () { System.out.println( “A” + a()); }
}
class B extends A {
public void b () { System.out.println( “C” + a()); }
}
class C extends B {
public int a() {return 10;}
}
Givenapolymorphicfunctionvoid func(A a){a.b();},whataretheoutputsofthefollowingcode?
B b = new B(); C c = new C(); func(b); func(c);
Problem 7
Consider the heap state as shown below before garbage collection. For each of the following algorithms, write down the objects being visited during the collection in sequence. Assume 1) reachability analysis uses depth-first search, which will skip objects that have already been visited, 2) search starts from p, and then q, 3) when the entire heap is traversed, objects are visited from left to right. You don’t need to write down the newly created object copies, if any.
1. Mark-and-Sweep 2. Mark-and-Compact 3. Stop-and-Copy
Stack Heap p
q
A
B
C
D
E
F
G
Final Exam Practice Questions, Cmpsc 461 2020 Fall 2/2