Name:

SE580 midterm exam: Autumn 2002-2003

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) Syntax.

b) Static semantics.

c) Dynamic semantics.

Question 2 (10 points)

Consider the following grammar:

  Program ::= Dec ... Dec

  Dec ::= ThreadDec | ObjectDec | ClassDec

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

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

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

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 |
    "thread" GlobalId |
    "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(Δ))
  (Γ,thread a,Δ)(a) = (thread a)  (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

  (Static Val Global Thread)
  If Γ(a) = (thread a)
  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 6 continued

Question 6 continued

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.