Due date: 10/04 @ 5:00 pm

The goal of this problem set is to implement an interpreter for the kernel of a C-like language.

Use the Pretty Big language and require the EoPL language in DrScheem.

---

The following problems concern this small programming language:

 Block is: { Declarations* Statement+ }

 Declaration is: (Type Variable = Expression) 

 Type is one of: 
 -- bool 
 -- int 

 Variable is: alphanumeric sequence of characters 

 Expression is one of: 
 -- Variable 
 -- Number 
 -- (Expression + Expression) 
 -- (Expression > Expression) 

 Statement is one of: 
 -- (Variable = Expression) 
 -- (if Expression Block else Block)
 -- (while Expression Block)

Assume that Variables are Scheme symbols and Numbers are Scheme numbers.

Here is one simple program (block) in this language:

  { (int x = 10)
    (int sum = 0)
    (while (x > 0) {
     (sum = (sum + x))
     (x = (x + -1))
     })           
    }

Problem 1:

Use your algebraic datatype representation from Problem Set 2(1) to represent the above sample program.

Use an intuitive C-like semantics to predict the effect of running this program.

Additional Problem 2:

Define a representation for expressed values in this language.

Define a representation for denoted values in this language.

Design an environment abstract datatype with the following operations:

;; type Value 
;; the denoted values 

;; type Env 

;; env.mt : Env

;; env.extend : Env Variable Value -> Env

;; env.apply : Env Variable -> Value 

;; env.plain : 
;;   Env -> (Listof (list Symbol Value))
;; present the given environment as a list of 
;; associations between symbols and values 

;; The functions should satisfy these equations: 
(env.apply (env.extend env x v) x) = v 
(env.apply (env.extend env y v) x) 
  = (env.apply env x) (for x != y)
(env.apply env.mt x) is an error 

Design an interpreter for this language. The interpreter consumes a program (as an AST if you weren't in the mood to design a parser). The program is closed (contains no free variables) and is type correct (whatever this exactly means). It produces a plain association list that associates all variables declared at the top-level with a Scheme value.
Hints: The interpretation for a block consumes a block and an environment and produces an environment. The interpretation for an expression consumes an expression and an environment; it produces an expressed value.

Problem 3:

Add a for-statement to the language and modify your program appropriately.

Add a declaration for int and bool arrays to the language. Also add array operations for putting a value into a slot and dereferencing a slot; if a slot hasn't been assigned before it is dereferenced, signal an error.