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(λxy.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)FullyevaluateTsothatnofurtherβ-reductionispossible.Showdetailedstepsofyourcomputation.
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 (nf z) PLUSλmn.mSUCCn PAIRλxyf.f xy LEFTλp.pλxy.x RIGHTλp.pλxy.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 value- result?
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