cc17:homework_3

# Differences

This shows you the differences between two versions of the page.

 — cc17:homework_3 [2017/04/03 18:04] (current)hossein created 2017/04/03 18:04 hossein created 2017/04/03 18:04 hossein created Line 1: Line 1: + ====== 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. 