Homework 7 - Fall 2021

Principles of Programming Languages — Homework 7

Due by class time Tuesday, October 5

Boolean expressions are defined by the following grammar:

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

where <variable> is any symbol not in the set {True, False, AND, OR, NOT}. Examples:

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

Write the function (get-bvars exp), which takes a valid boolean expression defined by the above grammar and returns a list of all of the variables that appear in the expression, in the order that they appear. Examples:
```
(get-bvars b1)  => ()
(get-bvars b5)  => (y)
(get-bvars b8)  => (x y)
(get-bvars b10)  => (x y z)
(get-bvars b11) => (z y x z w)
```
Write the function (bvars-only? exp), which takes a valid boolean expression and returns true if the expression contains only variables or operator symbols, with no True or False constants anywhere. Examples:
```
(bvars-only? b4)  => #f
(bvars-only? b6)  => #t
(bvars-only? b8)  => #f
(bvars-only? b10) => #f
(bvars-only? b11) => #t
```
Write the function (show-bform exp), which takes a valid boolean expression and constructs an identical expression except with each constant True or False replaced by the symbol bool and each variable replaced by the symbol var. Examples:
```
(show-bform b1) => bool
(show-bform b3) => var
(show-bform b5) => (AND bool var)
(show-bform b8) => (OR bool (NOT (AND var var)))
(show-bform b12) => (AND var (AND bool bool))
```

Infix expressions are defined by the grammar:

  <exp> ::= <number>
          | <variable>
          | (<exp> <operator> <exp>)

where <operator> is a symbol in the set {+, -, *, /}. Examples:

(define in1 '42)
(define in2 'apple)
(define in3 '(2 + 3))
(define in4 '(x * 5))
(define in5 '(x * (2 - y)))
(define in6 '((a * a) + (b * b)))
(define in7 '(((9 / 5) * celsius) + 32))
(define in8 '((5 * (fahrenheit - 32)) / 9))
(define in9 '((3 * 4) / ((2 * 3) - 5)))
(define in10 '((2 + (x / y)) * ((a * a) - (2 * (b - c)))))

Write the function (count-ivars exp), which takes a valid infix expression defined by the above grammar and returns the total number of variables that appear in the expression. Examples:
```
(count-ivars in3)  => 0
(count-ivars in5)  => 2
(count-ivars in6)  => 4
(count-ivars in7)  => 1
(count-ivars in10) => 6
```
Write the function (get-inums exp), which takes a valid infix expression and returns a list of all of the numbers that appear in the expression, in the order that they appear. Examples:
```
(get-inums in6)  => ()
(get-inums in7)  => (9 5 32)
(get-inums in8)  => (5 32 9)
(get-inums in9)  => (3 4 2 3 5)
(get-inums in10) => (2 2)
```
Write the function (get-iops exp), which takes a valid infix expression and returns a list of all of the operator symbols that appear in the expression, in the order that they appear. Hint: use a combination of append and cons to construct your answer. Examples:
```
(get-iops in1)  => ()
(get-iops in3)  => (+)
(get-iops in5)  => (* -)
(get-iops in6)  => (* + *)
(get-iops in10) => (+ / * * - * -)
```
Write the function (ivars-only? exp), which takes a valid infix expression and returns true if the expression contains only variables or operator symbols, with no numbers anywhere. Examples:
```
(ivars-only? in2)  => #t
(ivars-only? in4)  => #f
(ivars-only? in5)  => #f
(ivars-only? in6)  => #t
(ivars-only? in10) => #f
```

Write the function (show-iform exp), which takes a valid infix expression and constructs an identical expression except with each number replaced by the symbol num and each variable replaced by the symbol var. Examples:

(show-iform in4)  => (var * num)
(show-iform in5)  => (var * (num - var))
(show-iform in6)  => ((var * var) + (var * var))
(show-iform in7)  => (((num / num) * var) + num)
(show-iform in9)  => ((num * num) / ((num * num) - num))

Prefix expressions are defined by the grammar below. In a prefix expression, the operator symbol comes first, followed by the arguments.

  <exp> ::= <number>
          | <variable>
          | (<operator> <exp> <exp>)

Examples:

(define pre1 '42)
(define pre2 'apple)
(define pre3 '(+ 2 3))
(define pre4 '(* x 5))
(define pre5 '(* x (- 2 y)))
(define pre6 '(+ (* a a) (* b b)))
(define pre7 '(+ (* (/ 9 5) celsius) 32))
(define pre8 '(/ (* 5 (- fahrenheit 32)) 9))
(define pre9 '(/ (* 3 4) (- (* 2 3) 5)))
(define pre10 '(* (+ 2 (/ x y)) (- (* a a) (* 2 (- b c)))))

Write the function (infix-to-prefix exp), which takes an infix expression and converts it into an equivalent prefix expression. Examples:

(infix-to-prefix in3) => (+ 2 3)
(infix-to-prefix in5) => (* x (- 2 y))
(infix-to-prefix in6) => (+ (* a a) (* b b))
(infix-to-prefix in7) => (+ (* (/ 9 5) celsius) 32)
(equal? (infix-to-prefix in10) pre10) => #t

Write the function (prefix-to-infix exp), which takes a prefix expression and converts it into an equivalent infix expression. Examples:

(prefix-to-infix pre3) => (2 + 3)
(prefix-to-infix pre5) => (x * (2 - y))
(prefix-to-infix pre6) => ((a * a) + (b * b))
(prefix-to-infix pre7) => (((9 / 5) * celsius) + 32)
(equal? (prefix-to-infix pre10) in10) => #t

Postfix expressions are defined by the grammar below. In a postfix expression, the arguments come first, followed by the operator symbol at the end.

  <exp> ::= <number>
          | <variable>
          | (<exp> <exp> <operator>)

Examples:

(define post1 '42)
(define post2 'apple)
(define post3 '(2 3 +))
(define post4 '(x 5 *))
(define post5 '(x (2 y -) *))
(define post6 '((a a *) (b b *) +))
(define post7 '(((9 5 /) celsius *) 32 +))
(define post8 '((5 (fahrenheit 32 -) *) 9 /))
(define post9 '((3 4 *) ((2 3 *) 5 -) /))
(define post10 '((2 (x y /) +) ((a a *) (2 (b c -) *) -) *))

Write the function (infix-to-postfix exp), which takes an infix expression and converts it into an equivalent postfix expression. Examples:

(infix-to-postfix in3) => (2 3 +)
(infix-to-postfix in5) => (x (2 y -) *)
(infix-to-postfix in6) => ((a a *) (b b *) +)
(infix-to-postfix in7) => (((9 5 /) celsius *) 32 +)
(equal? (infix-to-postfix in10) post10) => #t

Write the function (postfix-to-infix exp), which converts a postfix expression into an equivalent infix expression. Examples:

(postfix-to-infix post5)  => (x * (2 - y))
(postfix-to-infix post6)  => ((a * a) + (b * b))
(postfix-to-infix post7)  => (((9 / 5) * celsius) + 32)
(equal? (postfix-to-infix post8) in8)  => #t
(equal? (postfix-to-infix post9) in9)  => #t

Write the functions (prefix-to-postfix exp) and (postfix-to-prefix exp), which convert between prefix and postfix expressions. Hint: these are one-liners if you use the appropriate infix conversion functions as helpers. Examples:
```
(prefix-to-postfix pre3)  => (2 3 +)
(postfix-to-prefix post7) => (+ (* (/ 9 5) celsius) 32)
(equal? (prefix-to-postfix pre9) post9) => #t
(equal? (postfix-to-prefix post10) pre10) => #t
```

Turning in Your Homework

Save all of your function definitions in a single Scheme file called assign7.scm and submit it using the Homework Upload Site. Make sure to include your name and the assignment number in a comment at the top of your file.
If you have questions about anything, don't hesitate to ask!