# Name:

SE580 midterm exam: Autumn 2001-2002

Time allowed: 2 hours

Total number of points: 100

### Question 1 (5 points)

Give a one- or two-sentence definition of:

a) Static semantics.

b) Dynamic semantics.

c) Subject reduction.

### Question 2 (5 points)

Consider the following grammar:

```  Program ::=
Dec ... Dec

Dec ::=
ObjectDec

ObjectDec ::=
"object" GlobalId ":" GlobalId "{" FieldConcrete ","..."," FieldConcrete "}"

FieldConcrete ::=
LocalId "=" Val

Block ::=
FieldAccessBlock |
FieldUpdateBlock |
ReturnBlock

FieldAcceessBlock ::=
"let" Var "=" Val "." LocalId ";" Block

FieldUpdateBlock ::=
Val "." LocalId ":=" Val ";" Block

ReturnBlock ::=
"return" Val ";"

Val ::=
LocalVal |
GlobalVal

LocalVal ::= LocalId

GlobalVal ::= GlobalId

Var ::= LocalId

LocalId ::= [ 'a'-'z' ] ( ['a'-'z' ] | [ 'A'-'Z' ])*

GlobalId ::= [ 'A'-'Z' ] ( ['a'-'z' ] | [ 'A'-'Z' ])*
```

Which of the following is a valid Block?

a) `return x;`

b) `let x = True; return x;`

c) `let foo.bar = True; return foo;`

d) `foo.bar := True; return foo;`

e) `foo.bar := True;`

### Question 3 (15 points)

Consider the grammar described in Question 2.

a) Complete this class diagram for a first-cut representation of this grammar as an AST:

### Question 3 continued

b) Give an object diagram showing the AST representation for the following `Program`:

```  object Foo : C { bar = Foo, baz = Bar }
object Bar : D { }
```

### Question 4 (15 points)

Consider the dynamic semantics given by rules:

```(Dynamic Field Access)
thread a { let x = b.f; B } P
--> thread a { [ x:=V ]B } P
(where object b : c { ...,f=V,... } in P)

(Dynamic Field Update)
thread a { b.f0 := V; B } object b : c { f0=V0, f1=V1,..., fn=Vn } P
--> thread a { B } object b : c { f0=V, f1=V1,..., fn=Vn } P
```

Use these rules to show the execution of the following program:

```  object Foo { bar = True }
thread Main { let x = Foo.bar; Foo.bar := x; return Nothing; }
```

### Question 5 (15 points)

A partial definition of substitution for the language described in Question 2 is:

```  Substitution ::= Subst "," ... "," Subst
Subst ::= Var ":=" Val

(σ,x:=V,ρ)(x) = V  (when x not in dom(ρ))

[σ]x = σ(x)  (if x in dom(σ))
[σ]x = x   (if x not in dom(σ))
[σ]a = a

[σ](return V;) = ????

[σ](let x = V.f; B) = ????

[σ](V.f = W; B) = ????
```

a) Complete this definition.

b) Show how your definition can be used in the following substitution:

```  [ x:=True, y:=False ] ( let x = Foo.bar; Foo.bar := x; return y; )
```

### Question 6 (20 points)

A partial definition of the static semantics of the language described in Question 2 is:

```  Type ::=
GlobalId

TypeContext ::= Ctxt "," ... "," Ctxt
Ctxt ::=
LocalId ":" Type |
Mutability "class" GlobalId "{" FieldAbstract ","..."," FieldAbstract "}" |
"object" GlobalId ":" Type

FieldAbstract ::=
"field" LocalId ":" Type

Mutability ::=
"mutable" |
"immutable"

(Γ,x : T,Δ)(x) = (x : T)   (if x not in dom(Δ))
(Γ,object a : T,Δ)(a) = (object a : T)  (if a not in dom(Δ))
(Γ,u class a { F1,...,Fn },Δ)(a) = (u class a { F1,...,Fn })  (if a not in dom(Δ))

(Static Val Local)
If Γ(x) = (x:T)
then Γ |- x : T

(Static Val Global Object)
If Γ(a) = (object a : T)
then Γ |- a : T

(Static Block Return)
If ????
then Γ |- (return V;) : T

(Static Block Field Access)
If ????
then Γ |- (let x = a.f; B) : T

(Static Block Field Update)
If ????
then Γ |- (a.f := V; B) : T
```

a) Complete this definition.

b) Show how your definition can be used to typecheck the following program:

```  let x = F.bar; F.bar := x; return Nothing;
```

in a type context Γ defined:

```  Γ = (
mutable class Foo { bar : Boolean },
object F : Foo,,
object Nothing : Unit
)
```

### Question 7 (20 points)

a) Explain, with an example, what a covariant use of a type is.

b) Explain, with an example, what an contravariant use of a type is.

c) Explain, with an example, what the principal of subsumption is.

d) Explain, with an example, why method overriding in an object oriented language can be covariant for the return type and contravariant for the argument types.

### Question 8 (5 points)

If you could make one change to the Java language design, what change would it be? Give a one- or two-sentence justification for your suggested change.

### Worksheet

You can use this sheet as scrap paper.

### Worksheet

You can use this sheet as scrap paper.

### Worksheet

You can use this sheet as scrap paper.

### Worksheet

You can use this sheet as scrap paper.