# Name:

SE580 midterm exam: Winter 2001-2002

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

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

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

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