Teaching G711 F '05 Assignments Set 1 Set 2 Set 3 Set 4 Set 5 Set 6 Set 7 Set 8 Set 9

### Problem Set 3: Simple Interpretation

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.

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: