CIS 425 Homework IV

Types; due 10/26

Part I

Research a security problem in Java that was due to a typing loophole. Write one or two paragraphs describing the problem.

Part II

We are going to write a type checker for a small language. The expressions of the language are described using the following ML datatypes: 
datatype BOp = PLUS | MINUS | TIMES | DIV
             | AND | OR 
             | EQ | LT | LEQ | GT | GEQ | NEQ

datatype UOp = NOT | UMINUS

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

datatype ExpType = Integer | Boolean
All expressions should have type Integer or Boolean . The operations BOp and UOp have the usual meanings. The intention is that PLUS, MINUS, TIMES, DIV, UMINUS can only be applied to integers, that NOT, AND, OR can only be applied to booleans, and that EQ, LT, LEQ, GT, GEQ, NEQ can only be applied to two expressions of the same type (two integers or two booleans but not a boolean and an integer). A Cond(e1,e2,e3) expression is like the Java expression e1? e2:e3 : the expression e1 should have boolean type, and the expressions e2, e3 should have the same type.

Write an ML function that takes an Expression and either:

Here are some examples: 
- val e1 = Number(3);
val e1 = Number 3 : Expression
- val e2 = True;
val e2 = True : Expression
- val e3 = False;
val e3 = False : Expression
- val e4 = Number(4);
val e4 = Number 4 : Expression
- val e5 = Binary(e1,PLUS,e2);
val e5 = Binary (Number 3,PLUS,True) : Expression
- val e6 = Binary(e2,AND,e3);
val e6 = Binary (True,AND,False) : Expression
- val e7 = Cond(e6, e1, e4);
val e7 = Cond (Binary (True,AND,False),Number 3,Number 4) : Expression
- typecheck e1;
val it = Integer : ExpType
- typecheck e2;
val it = Boolean : ExpType
- typecheck e3;
val it = Boolean : ExpType
- typecheck e4;
val it = Integer : ExpType
- typecheck e5;

uncaught exception TypeError
  raised at: types.sml:45.20-45.29
- typecheck e6;
val it = Boolean : ExpType
- typecheck e7;
val it = Integer : ExpType

Visited times since September 21, 1999 (or the last crash).

sabry@cs.uoregon.edu