Name:

SE580 midterm exam: Winter 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) Syntax.

b) Static semantics.

c) Dynamic semantics.

Question 2 (10 points)

Consider the following grammar:

  Program ::=
    Dec ... Dec

  Dec ::=
    ThreadDec

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

  Block ::=  
    LetBlock |
    IfBlock |
    ReturnBlock

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

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

  ReturnBlock ::= 
    "return" Val ";"

  Exp ::=
    Val |
    Val "==" 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 x = Foo == Bar; return foo;

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

e) if (Foo == Bar) { return foo; } else { return bar; }

Question 3 (20 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:

  Thread Main { if (True) { return False; }  else { return True; } }

Question 4 (20 points)

Consider the dynamic semantics given by rules:

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

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

(Dynamic Let == False)
  thread a { let x = (V1 == V2); B } P
    --> thread a { [ x:=False ]B } P
      (where V1 != V2)

(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:

  thread Main { let x = Main; let y = (x == Main); if (y) { return A; } else { return B; } }

Question 5 (20 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; B) = ????

  [σ](let x = (V1 == V2); 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 = y; if (x) { return A; } else { return B; } )

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 | 
    "object" GlobalId ":" Type |
    "thread" GlobalId

  (Γ,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(Δ))

  (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 Block Return)
  If ????
  then Γ |- (return V;) : T

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

  (Static Block Let Eq)
  If ????
  then Γ |- (let x = (V1 == V2); 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 = False; let y = (x == True); if (y) { return True; } else { return False; }

in a type context Γ defined:

  Γ = (object True : Boolean, object False : Boolean)

Question 6 continued

Question 7 (5 points)

What is your favourite object oriented programming language? 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.