Starting from:
$26.10
Assignment1: Function evaluator for boolean functions
Assignment1
FunctionalProgramming(10marks)
In this assignment you will implement a function evaluator for boolean functions. Please choose one ofthefollowingfunctionalprogramminglanguagestoimplementyourassignmentin: LISP, SCHEME or Haskell. Your assignment should run on the ucpu[01] machines. We define a set of Boolean functions for a variable environment. A variable environment is a list of pairs, each associating a Boolean value with a variable, i.e., an environment is given as:
((var1, value1) ... (varN, valueN))
WeassumethatdatavaluesinanassociationlistareBooleans,i.e.,eitherthevalue#tor#f. Another assumptionisthatwehaveforasinglevariableauniquepairinthevariableenvironment. Forexample the following variable environment describes the values of variables a, b, and c.
variable value a #t b #f c #t
This table is translated to following list object:
( define my-environment ’((a #t) (b #f) (c #t)) )
1
COMP3109
Foravariableenvironment,wewouldliketoformulatea“composed”booleanfunction. Thisboolean function queries the environment for variable values, and computes Boolean operations. A Boolean functionisgiveninformofarecursivelydefinedlist. Therecursivelistisanelementofthefollowing inductively defined set Q:
1. If v is a variable, then (s-var v)∈ Q. 2. If a, b∈ Q then (s-nand a b)∈ Q. 3. If a∈ Q then (s-not a)∈ Q. 4. Nothing else is in Q.
where the Boolean operator s-nand represents the negated-and i.e.,¬(a∧b), the Boolean operator s-not representsthenegation,i.e.,¬a,and s-var retrievesthevalueofthegivenvariablefromthe variable environment. For example the following list (s-not (s-nand (s-var a) (s-var b))) is in Q and semantically models the query: ¬(¬(a∧b)).
Task1 (3marks)
Write a function (find-vars <query) that recursively traverses a query and returns a list of variables that are used in the query. For example
(find-vars ’(s-nand (s-nand (s-var a) (s-var b)) (s-var a)))
should return (a b). Do not return multiple occurrences of variables. You may assume that the recursive list <query is always an element of Q, so error-handling is not needed.
Task2 (3marks)
Writeafunction(transformer <query)thattakesaqueryinQasanargumentandgenerates a function as output. The generated function has a variable environment as input and returns #t (for true) if the predicate of the query holds, otherwise it returns #f (for false). Note that the transformer reads recursively the elements of a query and constructs a lambda function on the fly. For example
(define tq (transformer ’(s-not (s-nand (s-var a) (s-var b))))) ... (apply tq ’((a #t) (b #f))) #f (apply tq ’((a #t) (b #t))) #t
Hint: Start simple. Try to translate the variable environment access and from there you construct lambda terms for operators “not” and “nand”.
Programming Languages and Paradigms Page2of 3
COMP3109
Task3 (4marks)
This task is to write a query simplifier (simplify <query), where <query is an element in Q, the set of recursively defined lists. The simplifier produces a new query as a result that is simpler. Find an extensive rule set to simplify queries. Read up about De-Morgan’s law. You can startwithsimplerulessuchas(simplify ’(s-not (s-not (s-var a))))thatmayreturn (s-var a). Aim for minimizing the number of operators in the result query.
FunctionalProgramming(10marks)
In this assignment you will implement a function evaluator for boolean functions. Please choose one ofthefollowingfunctionalprogramminglanguagestoimplementyourassignmentin: LISP, SCHEME or Haskell. Your assignment should run on the ucpu[01] machines. We define a set of Boolean functions for a variable environment. A variable environment is a list of pairs, each associating a Boolean value with a variable, i.e., an environment is given as:
((var1, value1) ... (varN, valueN))
WeassumethatdatavaluesinanassociationlistareBooleans,i.e.,eitherthevalue#tor#f. Another assumptionisthatwehaveforasinglevariableauniquepairinthevariableenvironment. Forexample the following variable environment describes the values of variables a, b, and c.
variable value a #t b #f c #t
This table is translated to following list object:
( define my-environment ’((a #t) (b #f) (c #t)) )
1
COMP3109
Foravariableenvironment,wewouldliketoformulatea“composed”booleanfunction. Thisboolean function queries the environment for variable values, and computes Boolean operations. A Boolean functionisgiveninformofarecursivelydefinedlist. Therecursivelistisanelementofthefollowing inductively defined set Q:
1. If v is a variable, then (s-var v)∈ Q. 2. If a, b∈ Q then (s-nand a b)∈ Q. 3. If a∈ Q then (s-not a)∈ Q. 4. Nothing else is in Q.
where the Boolean operator s-nand represents the negated-and i.e.,¬(a∧b), the Boolean operator s-not representsthenegation,i.e.,¬a,and s-var retrievesthevalueofthegivenvariablefromthe variable environment. For example the following list (s-not (s-nand (s-var a) (s-var b))) is in Q and semantically models the query: ¬(¬(a∧b)).
Task1 (3marks)
Write a function (find-vars <query) that recursively traverses a query and returns a list of variables that are used in the query. For example
(find-vars ’(s-nand (s-nand (s-var a) (s-var b)) (s-var a)))
should return (a b). Do not return multiple occurrences of variables. You may assume that the recursive list <query is always an element of Q, so error-handling is not needed.
Task2 (3marks)
Writeafunction(transformer <query)thattakesaqueryinQasanargumentandgenerates a function as output. The generated function has a variable environment as input and returns #t (for true) if the predicate of the query holds, otherwise it returns #f (for false). Note that the transformer reads recursively the elements of a query and constructs a lambda function on the fly. For example
(define tq (transformer ’(s-not (s-nand (s-var a) (s-var b))))) ... (apply tq ’((a #t) (b #f))) #f (apply tq ’((a #t) (b #t))) #t
Hint: Start simple. Try to translate the variable environment access and from there you construct lambda terms for operators “not” and “nand”.
Programming Languages and Paradigms Page2of 3
COMP3109
Task3 (4marks)
This task is to write a query simplifier (simplify <query), where <query is an element in Q, the set of recursively defined lists. The simplifier produces a new query as a result that is simpler. Find an extensive rule set to simplify queries. Read up about De-Morgan’s law. You can startwithsimplerulessuchas(simplify ’(s-not (s-not (s-var a))))thatmayreturn (s-var a). Aim for minimizing the number of operators in the result query.
1 file (86.0KB)
