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.

4. 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. Describe two benefits of using a formal specification to help with the implementation of a software system.

hw4.rkt