CIS 425 Midterm Solution

Grammars

exp ::= cast |  call |  LPAREN exp RPAREN | IDENTIFIER

cast ::= LPAREN type RPAREN exp

call ::= function LPAREN argument RPAREN

function ::= exp

argument ::= exp

type ::= IDENTIFIER

Prove the syntactic ambiguity of the this grammar by finding a string that has more than one parse tree. Draw the parse trees.

Solution

• casting the parenthesized expression y to type x, or
• calling parenthesized function x with argument y

ML Datatypes

datatype shape = 
    Rect 
  | Square 
  | Circle 
  | Intersect of (shape * shape)

val s1 = Rect
val s2 = Circle
val s3 = Intersect(s1,s2)
val s4 = Intersect(s2,s3)

- countC(s1);
val it = 0 : int
- countC(s2);
val it = 1 : int
- countC(s3);
val it = 1 : int
- countC(s4);
val it = 2 : int

Solution

fun countC Rect = 0
  | countC Square = 0
  | countC Circle = 1
  | countC (Intersect(s1,s2)) = countC(s1) + countC(s2)

Invariants

#include "assert.h"

main () {
  int x = 3;
  int y = 5;
  assert (x > 0 && y < 10);
  x = x+y;
  assert (x < 0);
}

Assertion failed: x < 0, file testassert.c, line 8
Abort

A programmer developing a new fast multiplication algorithm carefully intrumented the code with assertions that would guarantee the correctness of the code:

int fastmul (int a0, int b0) {
  int result = 0;
  int a = a0;
  int b = b0;
  assert(result == a0*b0 - a*b);
  while (a >= 1) {
    assert(result == a0*b0 - a*b);
    if (a % 2 == 0) {
      result = 2 * result;
      a = a / 2;
    }
    else {
      result = result + b;
      a = a - 1;
    }
  }
  assert(result == a0*b0 - a*b && a == 0);
  return result;
}

• Find two numbers x and y such that all assertions succeed when executing the call fastmul(x,y).

  Solution x = 0, y = 7

• Find two other numbers m and n such that at least one assertion fails when executing the call fastmul(m,n).

  Solution x = 5, y = 7

• Fix the bug in the program by changing the code. (The assertions are correct!)

  Solution

  int fastmul (int a0, int b0) {
    int result = 0;
    int a = a0;
    int b = b0;
    assert(result == a0*b0 - a*b);
    while (a >= 1) {
      assert(result == a0*b0 - a*b);
      if (a % 2 == 0) {
        b = b * 2; /** CHANGED THIS LINE **/
        a = a / 2;
      }
      else {
        result = result + b;
        a = a - 1;
      }
    }
    assert(result == a0*b0 - a*b && a == 0);
    return result;
  }
  

Types

datatype BOp = PLUS | DIV | EQ

datatype Expression =
    Number of int
  | True | False
  | Binary of Expression * BOp * Expression

datatype ExpType = Integer | Boolean

exception TypeError

fun typecheck (Number(i)) = Integer
  | typecheck (True) = Boolean
  | typecheck (False) = Boolean
  | typecheck (Binary(e1,bop,e2)) = 
    let val t1 = typecheck(e1)
        val t2 = typecheck(e2)
    in case (t1,bop,t2) of 
        (Integer,PLUS,Integer) => Integer
      | (Integer,DIV,Integer) => Integer
      | (_,EQ,_) => if t1=t2 then Boolean else raise TypeError
      | _ => raise TypeError
    end

• Write an expression in our little language that fails to typecheck.

  Solution Binary(Number(1),PLUS,True)

• Write an expression in our little language that typechecks but would cause an error if later executed.

  Solution Binary(Number(1),DIV,Number(0))

• Much like we have done in Homework II, we are going to extend the datatype declaration of Expression by adding the following two lines:

    | Define of string * Expression * Expression 
    | Variable of string 
  

  The intention is that a Define gives a name to a subexpression that can be reused later, for example,

  Define("x", Number(3), Binary(Variable "x", PLUS, Variable "x"))
  

  Extend the typechecker to handle the additional two cases. Write the complete code for any additional functions you might use.

  Solution

  datatype Expression =
      Number of int
    | True | False
    | Binary of Expression * BOp * Expression
    | Define of string * Expression * Expression
    | Variable of string
  
  fun lookup ([],_) = raise TypeError
    | lookup ((s,t)::env, key) = if s=key then t else lookup(env,key)
  
  fun typecheck (Number(i),_) = Integer
    | typecheck (True,_) = Boolean
    | typecheck (False,_) = Boolean
    | typecheck (Binary(e1,bop,e2),env) = 
      let val t1 = typecheck(e1,env)
  	val t2 = typecheck(e2,env)
      in case (t1,bop,t2) of 
  	(Integer,PLUS,Integer) => Integer
        | (Integer,DIV,Integer) => Integer
        | (t1,EQ,t2) => if t1=t2 then Boolean else raise TypeError
        | _ => raise TypeError
      end
    | typecheck (Define(s,e1,e2),env) = 
      let val t1 = typecheck (e1,env)
      in typecheck (e2,((s,t1)::env))
      end
    | typecheck (Variable(s),env) = lookup(env,s)
  

Scope and Parameter-Passing

#include 

#define count(N) { int i; for(i=1; i<=N; i++) { printf("%d\n", i); } }

void main () {
    int i;
    for(i=0; i < 3; i++) {
        count(i);
    }
}

Solution Infinite loop printing

1
2
3
4
5
...

If we were to change the definition of count from a macro to the following function, what would the program print?

void count(int N) { 
    int i; 
    for(i=1; i<=N; i++) { 
        printf("%d\n", i); 
    } 
}

Solution

1
1
2

Extra Credit

class A {
    int x = 3;
    int f (int x) { return x+x; }
}

class B {
    int x = 4;
    int f (C c) { 
        c.x = 100; 
        c = new C();
        return x; 
    }
}

class C {
    int x = 5;
}

class Main {
    public static void main (String[] args) {
        int x = 6;
        A a = new A();
        B b = new B();
        C c = new C();
        System.out.println(a.f(x)); // ..............................
        System.out.println(b.f(c)); // ..............................
        System.out.println(c.x);    // ..............................
    }
}

Solution

12
4 
100