Name:

SE580 midterm exam: Practice Exam

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) Programming language syntax.

b) Parser.

c) Abstract syntax tree.

Question 2 (5 points)

Consider the following grammar:

  Block ::=  
    LetBlock |
    IfBlock |
    ReturnBlock

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

  IfBlock ::= 
    "if" "(" Val ")" "{" Block "}" "else" "{" 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) return;

c) let x = 37; return A;

d) if (y) { return x; } else { return A; }

e) if (y) { return x; }

Question 3 (15 points)

Consider the grammar described in Question 2.

a) Give a class diagram for a first-cut representation of the grammar as an AST. Your class diagram should include at least classes for Block, Val and Var, and should include all of the fields for each of the classes, but does not need to include methods.

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

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

Question 3 continued

Question 4 (10 points)

Consider the dynamic semantics given by rules:

(Dynamic If True)
  if (True) { B } else { C } 
    -->  B

(Dynamic If False)
  if (False) { B } else { C } 
    -->  C

(Dynamic Let)
  let x = V; B 
    --> [ x := V ]B

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

  let x = True; if (x) { let y = False; return Nothing; } else { 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;) = ????

  [σ](if (V) { B } else { C }) = ????

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

a) Complete this definition.

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

  [ x:=True, y:=False ] ( let x = Nothing; let z = y; return x; )

Question 5 continued

Question 6 (10 points)

Consider the following substitution:

  [ x:=y ] ( let y = True; return x; )

a) What incorrect behaviour arises if we allow this subtitution?

b) Give two possible solutions to this problem.

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

  (Γ,x : T,Δ)(x) = (x : T)   (if x not in dom(Δ))
  (Γ,object a : T,Δ)(a) = (object a : T)  (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 If)
  If ????
  then Γ |- (if (V) { B } else { C }) : T

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

a) Complete this definition.

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

  let x = True; if (x) { let y = False; return Nothing; } else { return Nothing; }

in a type context Γ defined:

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

Question 7 continued

Question 8 (20 points)

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

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

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

d) Explain, with an example, why field overriding in an object oriented language can be covariant for immutable classes, but has to be invariant for mutable classes.

Question 8 continued

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.