Differences

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

@@ 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.

User Tools

Site Tools

Differences

Page Tools