cc17:homework_3

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

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.

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} \]

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?

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.

cc17/homework_3.txt · Last modified: 2017/04/03 18:04 by hossein