This shows you the differences between two versions of the page.
— |
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. |