cc17:homework_3

# Homework 03

Due Wednesday, April 12, 9:00am. Please hand it in before the beginning of the recitation session.

## Problem 1

Consider the following piece of code.

import java.util.function.*;
public class World {
int x = 1;
int y = 2;
IntUnaryOperator p = x -> (x + y);
int q(IntUnaryOperator r) {
return r.applyAsInt(p.applyAsInt(x * y));
}
IntUnaryOperator f = (x) -> q(p);
int g(IntBinaryOperator q) {
int y = 3;
IntUnaryOperator p = x -> x - y;
return q(f);
}
public static void main(String args[]) {
World w = new World();
System.out.print(w.g((x,y) -> (-x)));
}
}

Determine the output of the code using static scoping and dynamic scoping.

## Problem 2

Recall that regular expressions are defined as following: \begin{aligned} r &=\\ &| ~~\epsilon \\ &| ~~a \\ &| ~~r_1 ~.~r_2 \\ &| ~~r_1 ~|~r_2 \\ &| ~~r∗ \\ \end{aligned} We can define a string of characters using the following grammar: $s = ~ \mbox{nil} ~~|~~ a :: s$ The first rule denotes the empty string, the second rule denotes a string with first character $a\in\Sigma$ and rest of characters $s$. For example, the string “abc” is “a” :: “b” :: “c” :: $\mbox{nil}$ in this grammar. Consider the following judgment which means that the string $s$ matches the regular expression $r$: $s \mbox{ matches } r$ Design a set of inference rules to define how a string matches a regular expression. As an example, the following axiom considers the base case where the input string is empty.

$\frac{\begin{array}{@{}c@{}} \end{array}}{ \mbox{nil}~ \mbox{matches}~\epsilon}$

## Problem 3

We can partition the set of positive integers $\mathbb{N}^{+} = \{1,2,3,\cdots\}$ into the set of $\textit{even}=\{2,4,6,\cdots\}$ and the set of $\textit{odd}=\{1,3,5,\cdots\}$ numbers.
Assume that we have the types pos, even and odd in a programming language. Give the type rules for addition, multiplication, division and exponentiation.
For division, consider the following cases.

• Division rounds up the result: x / y is interpreted as $\lceil x/y\rceil$.
• Division returns the quotient: x / y is interpreted as $\lfloor x/y\rfloor$.

Specify in which case(s) there may be run-time error. Is there any way to prevent the run-time error at the type checking phase?

## Problem 4

Consider the following class:

class Rectangle {
int width;
int height;
int xPos;
int yPos;
int area() {
if(width > 0 && height > 0)
return width * height;
else
return 0;
}
void resize(int maxSize) {
while(area() > maxSize) {
width = width / 2;
height = height / 2;
}
}
}
• Determine the environment of this class.
• By giving the type derivation trees for each method, show that this class type checks. 