*Answer all questions.*

*Time allowed: 2 hours*

*Total number of points: 100*

Give a one- or two-sentence definition of:

a) Syntax.

b) Static semantics.

c) Dynamic semantics.

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; }`

Consider the grammar described in Question 2.

a) Complete this class diagram for a first-cut representation of this grammar as an AST:

b) Give an object diagram showing the AST representation
for the following `Program`

:

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

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 = (V_{1}== V_{2}); B } P --> thread a { [ x:=False ]B } P (where V_{1}!= V_{2}) (Dynamic If True) thread a { if (True) { B_{1}} else { B_{2}} } P --> thread a { B_{1}} P (Dynamic If False) thread a { if (False) { B_{1}} else { B_{2}} } P --> thread a { B_{2}} 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; } }

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 = (V_{1}== V_{2}); B) = ???? [σ](if (V) { B_{1}} else { B_{2}}) = ????

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; } )

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 = (V_{1}== V_{2}); B) : T (Static Block If) If ???? then Γ |- (if (V) { B_{1}} else { B_{2}}) : 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)

What is your favourite object oriented programming language? Give a one- or two-sentence reason for your choice.

You can use this sheet as scrap paper.

You can use this sheet as scrap paper.

You can use this sheet as scrap paper.

You can use this sheet as scrap paper.