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 2: Programming with Accumulators

Due date: 9/27 @ 5:00 pm

The goal of this problem set is to practice programming with accumulators.

Use the Pretty Big language and require the EoPL language.

EoPL Problems:

1.19, 1.21, 1.24 (read up on LET and LET* via HelpDesk), 1.27, 1.29, 1.30, 1.31, 1.32

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)
(bool b = (0 > 0))
(x = 11)
(while b {
(x = x)
})
}
```

Design an algebraic datatype representation using the EoPL language. If you're in the mood, design a parser that consumes the obvious concrete Scheme representation (S-expressions) and produces an AST in your algebraic datatype. If not, type in instances of the algebraic type directly. [My parser is 60 lines long and took 45 minutes to complete.]

Create three examples. At least one should contain blocks nested three levels deep.

Design the function count, which consumes a block b and a symbol x and counts how many times x occurs in b.

Define what it means for a variable to appear free in a block. Hint: You will need auxiliary relations.

Define what it means for a variable to appear bound in a block.

Design the function free, which consumes a block and produces (a representation of) the set of free variables.

Design the function bound, which consumes a block and produces the set of bound variables.