Reference no: EM133024267

Consider
- the grammar

Expression e := 01succe | true | false | iszeroe | if e then e else e | x| fun (x : T) -> e | (e e) | let x = e in e

Numeric Value nv := 0 1 succ v

Value v := nv | true | false

Type T := int | bool | T -> T

Where numbers are constructed with a successor keyword called succ, i.e. 0 = 0

1 = succ 0
2 = succ (succ 0)
and so on.
and where xs are variables.

Paper 2

Write a paper of max 3 pages (notice that front + back of a paper = 2 pages) where you

1) Using the grammar above, provide an example of expression with exactly 3 free variables.

2) Explain the phenomenon of "variable capture" in the context of substitution. Using the grammar above, provide an example of variable capture that is not the example in the textbook.

3) Using the grammar above, provide a function that returns a function, and provide the derivation tree that shows that such function is well-typed.

4) Explain the difference between Static Scoping (also known as Lexical Scoping) and Dynamic Scoping. Using the grammar above, provide an example, which must be different from the example in the lecture notes, that leads to different results when let-declarations are interpreted with Static Scoping and Dynamic Scoping.