CMPSC 461: Programming Language Concepts
Midterm 2 Practice Questions
Racket Programming
Problem 1
a) (2pt) Given the following racket code,what is the output of the program?
#lang racket
(define (mystery1 t) (foldl cons null t))
(mystery1 ’(1 2 3))
b) (6pt) We define the size of a value as follows: the size of a non-list value is 1; the size of a list value is the
sum of the sizes of its elements; the size of an empty list is 0. Implement a recursive function sizeOf
that takes a value and returns the size of that value. For example:
(sizeOf 2) ; returns 1
(sizeOf ’(1 ("abc" ()) 2)) ; returns 3
(sizeOf ’()) ; returns 0
(sizeOf ’(a b (c d e (f g)) ((h i) (j)))) ; returns 10
Use (list? v) to check if a value v is a list.
c) (4pt) Write a function squarelist that given a list of numbers, create a list of the square of the same
numbers. You CAN NOT USE RECURSION to implement this function. Use map. Your function
should do the following:
(squarelist ’()) ; returns ’()
(squarelist ’(1 2 3 4)) ; returns ’(1 4 9 16)
Lambda Calculus
Problem 2 For the following lambda term:
T , (λx y. x y) (λx. y) x
a) (4pt) Calculate the set of free variables FV(T) and connect all bound variables in T to their definitions
with lines. For example, the bound variables for λx. x y should be λ x. x y.
b) (8pt) Fully evaluate T so that no further β-reduction is possible. Show detailed steps of your computation.
Problem 3 Recall the following definitions of Church Encoding we defined in our class,
n , λf z. fn
z ZERO , λf z. z ONE , λf z. f z
SUCC , λn. λf z. f (n f z) PLUS , λm n. m SUCC n
PAIR , λx y f.f x y LEFT , λp.p λx y.x RIGHT , λp.p λx y.y
1/3
a) Fully evaluate RIGHT (PAIR 1 0) so that no further β-reduction is possible. Show detailed steps of your
computation.
b) Define a function MULTPAIR in λ-calculus so that given a pair of two church numerals, it returns a
church numeral that represents the product of the two numbers. For example, MULTPAIR (PAIR 2 3)
should evaluate to 6 (or some equivalent term under α/β-reduction). You can use all λ-terms above.
Subroutine and Control Abstraction
Problem 4 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. (4pt) What are the outputs if the language uses static scoping and all parameters are passed by value?
2. (4pt) What are the outputs if the language uses dynamic scoping and all parameters are passed by
reference?
3. (4pt) What are the outputs if the language uses static scoping and all parameters are passed by valueresult?
Problem 5 Consider the following Racket code that calculates sum of squares from 0 to n.
(define (sumsquare n) (if (= n 0) 0 (+ (sumsquare (- n 1)) (* n n))))
1. (4pt) Explain Why this implementation of sumsquare will take a long time to run and uses a lot of
memory (sometimes even run out of memory) with a large n.
2. (4pt) Rewrite implement this function sumsquare so that it will run faster and doesn’t run out of
memory even with a large n.
Problem 6 (4pt) What is the output of the following Java program where the exception handling uses
”replacement” semantics?
import java.io.*;
class p2 {
private static void foo(Integer i) {
try {
System.out.println("A");
Midterm 2 Practice Questions, Cmpsc 461 2021 Spring
int j = i.intValue();
System.out.println("B");
j = j / 0;
System.out.println("C");
}
catch (ArithmeticException e) {
System.out.println("D");
}
catch (NullPointerException e) {
System.out.println("E");
}
finally {
System.out.println("F");
}
}
public static void main(String[] args) {
try {
System.out.println("G");
foo(null);
int x = 461/0;
System.out.println("H");
}
catch (ArithmeticException e) {
System.out.println("I");
}
catch (NullPointerException e) {
System.out.println("J");
}
finally {
System.out.println("K");
}
}
}
Midterm 2 Practice Questions, Cmpsc 461 2021 Spring