Lab 6: Manipulating Programs as Data Solution

# Introduction: Goals for this lab




+ Get more comfortable with the `expr` data type we've been designing

in class for representing simple programs




+ See some examples of writing functions to manipulate values of this

type







Writing simple programs as `expr` values




The file `program.ml` contains a declaration of the type `expr` for

representing programs that we've been discussing in class. It also

includes the definition of the `eval` function that evaluates an

`expr` given a lexical environment binding names to values (called

initially with `[]`) and a type-checking function, `typeof`, that

infers the type of a program, raising an exception if the expression

is not well-typed. Take a look at these definitions and see if you

understand how they work.




Once you've convinced yourself that you understand them, add bindings for two

programs, `prog1` and `prog2,` that are well-typed. Your programs should

involve control flow (`If`) and use let bindings, but otherwise they can compute

anything you like. Evaluate these programs in `utop` to see if they behave as

you expect, and check their types using `typeof`. Then add two more program

values, `err1`, `err2`, but make these values correspond to programs with type errors. Confirm that calling `typeof` on these programs results in an exception.




Computing on `expr` values: finding constants




Add a definition for a function `find_constants : expr -

expr list` that traverses a program `expr` and assembles a list of all

of the boolean and integer constants present in the expression. So for

example, evaluating `find_constants e1` should result in the list

`[Const 3; Const 7; BConst true; BConst false]`, and evaluating

`find_constants badtype1` should result in the list

`[Const 7; BConst true; Const 1; Const 3; BConst false]`.




Manipulating `expr` values: removing variables




Now add a definition for a function `rm_vars: expr - expr` that

creates a copy of its argument with all of the `Name` sub expressions

replaced by constants. Your program will need to keep track of the

_types_ of names: a name that is bound to an integer value should

be replaced by `Const 0` and a name that is bound to a boolean value

should be replaced by `BConst false`. Some sample evaluations:




+ `rm_vars e1` should evaluate to

`Let ("x", Const 3, Let( "y", Const 7, If (Gt(Const 0, Const 0), Print

(BConst true), Print (BConst false))))`

+ `rm_vars (Let("artoo", Const 42, Name "artoo"))` should evaluate to

`Let ("artoo", Const 42, Const 0)`.

+ `rm_vars (Let("z", BConst true, If(Name "z", Name "z", Not(Name

"z"))))` should evaluate to `Let("z", BConst true, If(BConst false,

BConst false, Not(BConst false)))`.







# Commit and push so that everything is up on GitHub




Now you need to just turn in your work. Commit your changes and push

them up to your central GitHub repository.




Verify that this worked, by using your browser to see the changes on

https://github.umn.edu.




If you do not properly push your changes to the repository we

cannot give you credit for the lab, so please remember to do this

step!







Note that any required changes must exist in your repository on

github.umn.edu. Doing the work but failing to push those changes

to your central repository will mean that we cannot see your work

and hence can't grade it.