Name:

SE580 midterm exam: Autumn 2001-2002

Answer all questions.

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 ::=
    ThreadDec |
    ObjectDec

  TheadDec ::=
    "thread" GlobalId "{" Block "}"

  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 5 continued

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 6 continued

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 7 continued

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.