Assignment 2

For this assignment, please put all your code into a single file named a2.rkt. Use ; characters to separate the code for each question so it is easy for the marker to read your source code.

When you’re done, submit a2.rkt on Canvas.

Make sure to use exactly the same function names and arguments (otherwise the marking software may give you 0!).

Please stick to basic list-oriented Racket functions that do not end with a !, i.e. just use lists and non-mutating functions. You are encouraged to use standard built-in Racket forms when possible.

All the code you write should be written by you — do not use any code from any other sources. Cite any and all help you got for this assignment in the source code of the relevant file.

You can (and probably should!) create helper functions for some of the questions.

Part 1: Warm-up

In Racket, the value #\a is a character literal. In a language like C++, we would write it 'a', but Racket character literals start with #\. The char? function tests if a literal is a character, e.g.:

> (char? #\a)
#t
> (char? #\7)
#t
> (char? #\()      ;; #\( is the character '('
#t
> (char? #\space)  ;; a space character, e.g. ' '
#t

> (char? 'a)
#f
> (char? "a")
#f

Note that single-character symbols are not characters (they’re symbols).

1. Implement the function (is-digit? c) that returns #t if c is one of the characters #\0, #\1, …, #\9, and #f for any other value.

   For example:

   > (is-digit? #\4)
   #t
   > (is-digit? 4)
   #f
   > (is-digit? "4")
   #f
   > (is-digit? '(cheese shoes string))
   #f
   > (andmap is-digit? (string->list "0123456789"))
   #t
   

   Use char->integer in a sensible way to help implement this function.

2. Implement the function (is-letter? c) that returns #t if c is one of the 26 lowercase letters #\a, …, #z, or one of the 26 uppercase letters #\A, …, #\Z. For all other values of c, it should return #f.

   For example:

   > (is-letter? #\m)
   #t
   > (is-letter? #\Q)
   #t
   > (is-letter? 's)
   #f
   > (is-letter? "T")
   #f
   > (is-letter? '(cheese shoes string))
   #f
   > (andmap is-letter? (string->list "OnceUponAtime"))
   #t
   

   Use char->integer in a sensible way to help implement this function.

3. Implement the function (is-vble? x) that returns #t if x is a symbol that has the form of a variable (defined below), and #f for every other value.

   The following EBNF rules define what symbols are variables:

       variable = letter {letter | digit} .
   
         letter = letter_lower | letter_upper .
   letter_lower = "a" ... "z" .
   letter_upper = "A" ... "Z" .
          digit = "0" ... "9" .
   

   In addition to these rules, there is one extra constraint: a variable cannot be the symbol 't or 'f.

   For example:

   > (is-vble? 'x)
   #t
   > (is-vble? 'flag)
   #t
   > (is-vble? '4tune)    ;; variables can't start with a digit
   #f
   > (is-vble? 'c34)
   #t
   > (is-vble? 'f)        ;; 't and 'f are not legal variables
   #f
   > (is-vble? 'f3)
   #t
   > (is-vble? `big-val)  ;; - is not a legal character symbol
   #f
   > (is-vble? `BigVal)
   #t
   > (is-vble? "flag")
   #f
   > (is-vble? '(cheese shoes string))
   #f
   

   Try to implement this in a readable way without recursion. Instead, try to use standard higher-order functions.

4. Lets define a boolean environment to be a list of (var truth-value) pairs, where (is-vble? var) is true, and truth-value is either t or f (no # character at the start!).

   Implement the function (is-bool-env? x) that returns #t if x is a list containing one, or more, pairs of the form (var truth-value) as described above. If a variable occurs more than once, then return the value of its first occurrence.

   For example:

   > (is-bool-env? '((p t) (p f) (q f) (r f)))  ;; repeated variables are allowed
   #t
   > (is-bool-env? '((p t) (q f) (r f)))
   #t
   > (is-bool-env? '((p t) (4q f) (r f)))
   #f
   > (is-bool-env? '((f t) (p f) (q f) (r f)))  ;; f is an illegal variable name
   #f
   > (is-bool-env? '(cheese shoes string))
   #f
   

   Try to implement this in a readable way without recursion. Instead, try to use standard higher-order functions. The assoc function might be useful here.

Part 2: Boolean Expressions

Consider the following EBNF description of a propositional logic language that allows both boolean literals and variables:

            expr =   variable | bool-literal
                   | not-expr | and-expr | or-expr | implication-expr .

        variable = a symbol v for which (is-vble? v) returns #t .

    bool-literal = "t" | "f" .

        not-expr = "(" "not" expr ")" .

        and-expr = "(" expr "and" expr ")" .

         or-expr = "(" expr "or" expr ")" .

implication-expr = "(" expr "-->" expr ")" .

5. Implement the function (is-bool-expr? expr) that returns #t if expr is a valid boolean expression (as defined above), and #f otherwise. For example:

   > (is-bool-expr? 't)
   #t
   > (is-bool-expr? '(t or (not f)))
   #t
   > (is-bool-expr? '((p and (p --> f)) --> q))
   #t
   > (is-bool-expr? '((p and (p --> f)) --> q))
   #t
   > (is-bool-expr? '(cheese shoes string))
   #f
   

6. Implement the function (eval-bool expr env) that evaluates the boolean expr using the given boolean environment env. You can assume that both (is-bool-expr? expr) and (is-bool-env? env) are true. For example:

   > (eval-bool 'f '((a t) (b f) (c f) (d t) (a f)))
   'f
   > (eval-bool '(t and t) '((a t) (b f) (c f) (d t) (a f)))
   't
   > (eval-bool 'a '((a t) (b f) (c f) (d t) (a f)))
   't
   > (eval-bool 'x '((a t) (b f) (c f) (d t) (a f)))
   . . eval-bool: undefined variable
   > (eval-bool '(not (c --> d)) '((a t) (b f) (c f) (d t) (a f)))
   'f
   > (eval-bool '((c and a) --> (d or c)) '((a t) (b f) (c f) (d t) (a f)))
   't
   

7. Implement the function (get-vbles expr) that returns a list of all the different variables in expr. You can assume (is-expr? expr) is true. The returned list should not have any duplicates, and the order of the variables doesn’t matter. For example:

   > (get-vbles '((p or (not q)) --> (not p)))
   '(p q)
   > (get-vbles '((f or (not t)) --> (not p)))
   '(p)
   > (get-vbles 'r)
   '(r)
   > (get-vbles 't)
   '()
   

8. Implement the function (all-truth-values n) that returns a list of all \(2^n\) different lists of length n consisting just of 'f or 't values. You can assume n is an integer greater than 0. For example:

   > (all-truth-values 1)
   '((f) (t))
   > (all-truth-values 2)
   '((f f) (f t) (t f) (t t))
   > (all-truth-values 3)
   '((f f f) (f f t) (f t f) (f t t) (t f f) (t f t) (t t f) (t t t))
   

   Your implementation should, at least in theory, work for any positive value of n. In practice, the returned list of lists quickly becomes huge, and so most computers won’t have enough memory to actually work correctly in those cases.

9. Implement the function (sat expr) that returns a boolean environment that contains a value for all the variables in expr such that expr evaluates to true in that environment, and 'unsat if there is no such environment. In other words, if (sat expr) returns an environment, then (eval-bool expr (sat expr)) returns 't.

   If there is no assignment of values to the variables of expr that make it true, then we say expr is unsatisfiable. If expr is unsatisfiable, then (sat expr) returns the symbol 'unsat.

   For example:

   > (sat '((p or q) --> p))
   '((p t) (q t))
   
   > (sat '(p and (not p)))
   'unsat
   

It’s possible that there’s more than one environment that satisfies expr, and in that case (sat expr) can return any one of those environments. All that matters is (eval-bool expr (sat expr)) returns 't.

Your algorithm does not need to be extremely efficient. In fact, it’s fine if it runs in time that is exponential in the number of variables in expr.