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
  1. create an empty environment,
  2. add a variable and give it a value,
  3. find the boolean value associated with a string,
  4. list the variables of an environment, and
  5. 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:

  1. Var("x") is true
  2. Not(Var("x")) is false
  3. 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.