cc17:homework_3

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

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