User Tools

Site Tools


cc17:homework_3

Differences

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

Link to this comparison view

cc17:homework_3 [2017/04/03 18:04] (current)
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.
 +
 +<code java>
 +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)));​  ​
 +  }
 +}
 +</​code>​
 +
 +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:
 +
 +<code java>
 +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;
 +    }
 +  }
 +}
 +</​code>​
 +
 +  * 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