共计 3158 个字符,预计需要花费 8 分钟才能阅读完成。
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;
}
- (4pt) What are the outputs if the language uses static scoping and all parameters are passed by value?
- (4pt) What are the outputs if the language uses dynamic scoping and all parameters are passed by
reference? - (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)))) - (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. - (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