Language _S

Note: This section must use the AST defined in file hw4-util.rkt whose functions are prefixed with s:.

1. Your goal is to implement the substitution operation, notation e[x 7 v]. Implement function

(s:subst exp var val) where exp is an expression s:expression?, var is a variable s:variable?, and val is a value s:value?. Function s:subst must return an expression of type s:expression?. Test cases are included in the template file.

2. Your goal is to implement the evaluation of expressions using substitution, notation e v. Implement function (s:eval subst exp), where subst is a variable substitution function given by the system,^[1]and exp is an expression of type s:expression?. Function s:eval must return a value of type s:value?. Test cases are included in the template file.

Language _E

Note: This section must use the AST defined in file hw4-util.rkt whose functions are prefixed with e:.

3. Your goal is to implement the evaluation of expressions using environments, notation e _E v. Implement function (e:eval env exp) where env is a hash-table of type hash?, whose keys have a type e:variable? and values have a type e:value?, and expression exp has type e:expression?. Function e:eval must return a value of type e:value?. Test cases are included in the template file.

Manually graded questions

4. Manually graded. Describe one situation where implementing -Racket without environments is a

better alternative than -Racket with environments. Conversely, describe one situation where -Racket with environments is a better alternative than -Racket without environments.

5. Manually graded. Describe two benefits of using a formal specification to help with the implementation of a software system.

[1] We choose to make variable substitution a parameter of evaluation so that Exercise 2 can be graded independently from Exercise 1.