CMPSC 461: Programming Language Concepts Midterm 2 Practice Questions
Use these problems in addition to Assignment 4, 5 and 6 to prepare for the 2nd midterm.
Problem 1 For each of the following Scheme programs, circle all x’s that refer to (i.e., are in the scope of) the definition of x at the FIRST LINE. You don’t need to circle anything if no such x exists.
(let ((x 1)) (let ((x 2))
(+ x y)))
(let ((x 3))
(let ((x 4) (y x))
(+ x y)))
(let ((x 5) (y 6)) (let* ((y x) (x y))
(+ x y)))
Problem 2 What is the difference between static, stack, and heap allocation and how do they affect the lifetime of a variable?
Problem 3 What is a tail-recursive function? What makes it an interesting concept?
Problem 4 What outputs are produced by the following pseudo code if the language uses static scoping?
What are the outputs if the language uses dynamic scoping?
a=2; b=3; int f1(a) {
return a + b; }
int f2(b) {
return 2 * f1(b);
}
print f1(a) * f2(a);
Problem 5 Consider the following pseudo code.
int a=0;
void A(int m) {
print a;
m = a; }
void main () { int a=1, b=2; A(b);
print b;
}
1. What are the outputs if the language uses static scoping and all parameters are passed by value?
2. Whataretheoutputsifthelanguageusesdynamicscopingandallparametersarepassedbyreference?
1/2
Problem 6 Use the following typing rules to write down the proof tree for the term ((λx : bool . (λy : bool . x ∧ y)) true).
Typing rules:
Γ ⊢ true : bool (T-TRUE) Γ ⊢ false : bool (T-FALSE) Γ, x : τ ⊢ x : τ (T-VAR) Γ⊢e1 :τ →τ′ Γ⊢e2 :τ Γ,x:τ ⊢e:τ′
Γ⊢e1 e2 :τ′ (T-APP) Γ⊢(λx:τ .e):τ →τ′ (T-ABS)
Γ⊢e1 :bool Γ⊢e2 :bool
(T-AND)
Γ ⊢ (e1 ∧ e2) : bool
Problem 7 Follow the constraint unification rules in Lecture Note 4 to solve the following constraint
(int → α = β → β; β = int)
Midterm 2 Practice Questions, Cmpsc 461 2020 Fall 2/2