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)
     })
  }

Additional Problem 1:

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.

Additional Problem 2:

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.

Additional Problem 3:

Define the lexical address of a variable for this block language.

Design a function lexical, which consumes a block, ensures that it has no free variables, and replaces all variable occurrences with their lexical address.