User Tools

Site Tools


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;
      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.
cc17/homework_3.txt · Last modified: 2017/04/03 18:04 by hossein