# Name:

SE580 midterm exam: Autumn 2002-2003

Time allowed: 2 hours

Total number of points: 100

### Question 1 (5 points)

Give a one- or two-sentence definition of:

a) Syntax.

b) Static semantics.

c) Dynamic semantics.

### Question 2 (10 points)

Consider the following grammar:

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

Dec ::= ThreadDec | ObjectDec | ClassDec

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

ClassDec ::= "class" GlobalId "{" FieldAbstract ... FieldAbstract "}"

FieldConcrete ::= LocalId "=" Val

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

Block ::=  LetBlock | IfBlock | ReturnBlock

LetBlock ::= "let" Var "=" Exp ";" Block

IfBlock ::= "if" "(" Val ")" "{" Block "}" "else" "{" Block "}"

ReturnBlock ::= "return" Val ";"

Exp ::= Val | Val "." LocalId

Val ::= LocalVal | GlobalVal

LocalVal ::= LocalId

GlobalVal ::= GlobalId

Var ::= LocalId ":" Type

Type ::= GlobalId

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

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

Which of the following is a valid Block?

a) `return foo;`

b) `return Foo;`

c) `let x:Baz = Foo.bar; return x;`

c) `let x:Baz = foo.Bar; return x;`

d) `if (x) { return foo; } else { return bar; }`

e) `if (Foo.bar) { return foo; } else { return bar; }`

### Question 3 (25 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`:

```  class C { field foo : Boolean; }
object O:C { foo=False }
```

### Question 4 (10 points)

Consider the dynamic semantics given by rules:

```(Dynamic Let)
thread a { let x:T = V; B } P
--> thread a { [ x:=V ]B } P

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

(Dynamic If True)
thread a { if (True) { B1 } else { B2 } } P
--> thread a { B1 } P

(Dynamic If False)
thread a { if (False) { B1 } else { B2 } } P
--> thread a { B2 } P
```

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

```  class C { field foo : Boolean; }
object O:C { foo=False }
thread Main { let y:Boolean = O.foo; if (y) { return False; } else { return True; } }
```

### Question 5 (20 points)

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

```  Substitution ::= Subst "," ... "," Subst
Subst ::= LocalId ":=" 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
[σ](V.f) = ([σ]V).f

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

[σ](let x:T = E; B) = ????

[σ](if (V) { B1 } else { B2 }) = ????
```

a) Complete this definition.

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

```  [ x:=True, y:=False ] ( let x:Boolean = False; if (x) { return y; } else { return x; } )
```

### Question 6 (25 points)

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

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

(Γ,x : T,Δ)(x) = (x : T)   (if x not in dom(Δ))
(Γ,object a : T,Δ)(a) = (object a : T)  (if a not in dom(Δ))
(Γ,class a { F1...Fb },Δ)(a) = (class a { F1...Fb }) (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

then Γ |- a : Thread

(Static Exp Field Access)
If ????
then Γ |- V.f : T

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

(Static Block Let)
If ????
then Γ |- (let x:U = E; B) : T

(Static Block If)
If ????
then Γ |- (if (V) { B1 } else { B2 }) : T
```

a) Complete this definition.

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

```   let x:Boolean = O.foo; if (x) { return False; } else { return True; }
```

in a type context Γ defined:

```  Γ = (
object True : Boolean; object False : Boolean; object O : C;
class C { field foo : Boolean; }
)
```

### Question 7 (5 points)

If you could change one feature of the Java language specification, what would it be? Give a one- or two-sentence reason for your choice.

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