Principles of Programming Languages — Homework 6

Due by class time Friday, October 1

Boolean expressions, which we discussed in class, are defined by the following grammar:

  <exp> ::= True
          | False
          | <variable>
          | (NOT <exp>)
          | (AND <exp> <exp>)
          | (OR <exp> <exp>)

   where <variable> is any symbol other than {True, False, AND, OR, NOT}

Some example expressions are provided below. You may want to cut and paste these definitions into your program file for testing.

(define b1 'True)
(define b2 'False)
(define b3 'x)
(define b4 '(NOT False))
(define b5 '(AND True y))
(define b6 '(AND a b))
(define b7 '(OR a b))
(define b8 '(OR (OR x y) z))
(define b9 '(AND x (NOT y)))
(define b10 '(OR False (NOT (AND x y))))
(define b11 '(AND True (OR False (NOT True))))
(define b12 '(NOT (AND (OR x (NOT True)) (AND (OR (NOT y) False) z))))
(define b13 '(AND (AND (OR (AND (NOT z) y) x) z) (NOT w)))
(define b14 '(AND x (AND True True)))
(define b15 '(AND (OR False False) x))

Exercises

  1. Write the function (count-bvars exp), which takes a valid boolean expression defined by the above grammar and counts the total number of variables that appear in the expression. Think recursively, and use the structure of the grammar as a guide in writing your function. Hint: this function will be very similar to count-bools, which we wrote in class. Examples:

    (count-bvars 'False) → 0
(count-bvars '(AND True y)) → 1
(count-bvars '(OR False (NOT (AND x y)))) → 2
(count-bvars '(AND (AND (OR (AND (NOT z) y) x) z) (NOT w))) → 5

  2. Write the function (count-bops exp), which takes a valid boolean expression defined by the above grammar and counts the total number of boolean operators (AND, OR, NOT symbols) that appear in the expression. Examples:

    (count-bops 'False) → 0
(count-bops '(AND True y)) → 1
(count-bops '(OR False (NOT (AND x y)))) → 3
(count-bops '(AND (AND (OR (AND (NOT z) y) x) z) (NOT w))) → 6

  3. Write the function (bools-only? exp), which takes a valid boolean expression defined by the above grammar and returns true if the expression contains only True or False constants but no variables. This function is analogous to the function numbered? for arithmetic expressions from Chapter 6 of The Little Schemer. 

    (bools-only? '(NOT False)) → #t
(bools-only? '(AND True y)) → #f
(bools-only? '(AND True (OR False (NOT True)))) → #t
(bools-only? '(AND (OR False False) x)) → #f
(bools-only? '(OR False (NOT (AND x y)))) → #f
(bools-only? '(NOT (AND (OR x (NOT True)) (AND (OR (NOT y) False) z)))) → #f
(bools-only? '(AND (OR (NOT True) False) (AND True False))) → #t

  4. Write the function (get-bops exp), which takes a valid boolean expression defined by the above grammar and returns a list containing all of the boolean operators (AND, OR, NOT symbols) that appear in the expression, in the order that they appear. Examples:

    (get-bops 'False) → ()
(get-bops '(AND True y)) → (AND)
(get-bops '(OR False (NOT (AND x y)))) → (OR NOT AND)
(get-bops '(AND (AND (OR (AND (NOT z) y) x) z) (NOT w))) → (AND AND OR AND NOT NOT)

Turning in Your Homework