Functional Programming MN1

###
Distance Course (1DL027)

Uppsala University, Sweden

# Assignment 4

## K. Environments

Define an data structure for environments, i.e., a map from strings to
boolean values.
You may use any data structure that has been presented on the lecture
notes or invent one of your own,
(but document it according to the coding conventions).
Among the operations you define on the data structure there should be
a way to
- create an empty environment,
- add a variable and give it a value,
- find the boolean value associated with a string,
- list the variables of an environment, and
- print the contents of an environment.

In the solution to the last question, you may use the following code as a
starting-point:
fun printEnv env =
(List.app
(fn (name) =>
(print("\n"); print(name); print(" = ");
print(Bool.toString(valOf(lookupVar env name)))))
(varList env)
; print "\n")

## L. Verify

Consider the following datatype for logic formulas:
datatype formula =
True
| False
| Var of string
| Not of formula
| And of formula * formula
| Or of formula * formula

Define a function `verify` that given a formula and an
environment determines whether the formula holds.
Example:

Given the empty environment, `verify` should return
`true` for the formula `True` and `false`
for the formula `False`.

Given an environment that maps `"x"` to `true`
and `"y"` to `false`, `verify` should give:

`Var("x")` is `true`
`Not(Var("x"))` is `false`
`And(Var("x"), Var("y"))` is `false`

If a variable is not defined in the environment but mentioned in the
formula it may be impossible for `verify` to compute a
result. You must decide how to handle such situations.
## M. Simplify

Write a function that takes a formula and simplifies it. There are
many strategies for simplifying a logic formula, but you should at
least apply the following rules:
Or(True, x) simplifies to True
Or(False, x) simplifies to x
Or(x, True) simplifies to True
Or(x, False) simplifies to x
And(True, x) simplifies to x
And(False, x) simplifies to False
And(x, True) simplifies to x
And(x, False) simplifies to False
Not(Not(x)) simplifies to x
Not(True) simplifies to False
Not(False) simplifies to True

In the rules, `x` refers to any formula.
You should be able to apply the rules to sub-formulas. Also,
application of one simplification rule might other simplifications
possible.
For example,
Not(And(And(False, Var("x")), Var("y")))

can be simplied to
Not(And(False, Var("y")))

which can in turn be simplified to
Not(False)

and further to
True.