Assignment 2

Microproject

Write one or more Clojure function(s) to symbolically convert logical expressions using the and, or, and not connectives to expressions using only nor. To do this, use a Lisp-style prefix notation to represent the logical expressions as unevaluated lists, allowing for a single argument for the not connective, and two or more arguments for the and and or connectives. In this microproject you do not need to worry about recursive cases (i.e., nested logical expressions), though you will need to for the main project. To perform the symbolic conversion you must have your program deconstruct the input lists and build new lists to output. A sample of the conversions for you to generalize from are provided below.

In order to ease your implementation, I recommend, but do not require, following the below checklist to guide your work. Remember to follow good practices and thoroughly test each function as your implementation progresses.

• Implement a function taking a list representing a not-expression as an argument, and returning a list representing a nor-expression created from the input.
• Implement a function taking a list representing an or-expression as an argument, and returning a list representing a nor-expression created from the input.
• Implement a function taking a list representing an and-expression as an argument, and returning a list representing a nor-expression created from the input. Make use of a higher-order function to help.
• Implement a function taking a list representing an expression as an argument which returns the result of the appropriate more specific function called with the input expression.

A sample REPL interaction with your program might look like the following:

Main Project

In this project you will write a Clojure program to recursively convert logical expressions made up of the and, or, and not connectives to expressions using only the nor connective, then symbolically simplify the resulting expression.

As in the microproject, expressions are created as unevaluated lists. For example:

You should begin by building upon the microproject to implement a function which uses recursion to build the output for a nested expression. Your life will be easiest if the function works from the “inside” expressions outward. You may wish to modify deep-substitute for this task.

Then, write a Clojure program using at least one higher order function (e.g., map, filter, reduce, some, …) to symbolically simplify boolean nor relations of arbitrary length >= 1 represented as unevaluated lists. Simplification consists of replacing particular forms with equivalent forms or symbols. For example, in each of the below sample simplifications, given an unevaluated list representation of the item on the left, the result should be the item on the right.

You should generalize for any length expression based on these patterns. Your program must work for any arbitrary variables used. As in the microproject you may wish to write functions to handle certain kinds of cases, and handle the non-recursive case before you handle the recursive one.

The main entry point to the program, evalexp, calls functions that simplify, nor-convert, and bind these expressions. Binding consists of replacing some or all of the variables in expressions with constants (true or false), and then returning the partially evaluated form. We’ve already written a function which does this, in the form of deep-substitute.

The evalexp function should take a symbolic expression and a binding map and return the simplest form (that might just be a constant). One way to define this is:

Example:

binds x and z (but not y) in p1, leading to

Then the conversion to nor occurs resulting in:

and then further simplifies to just false. You may wish to work out other cases for yourself in order to thoroughly test your code. Try experimenting with p1, p2, and p3 with varied variable binding maps.

Suggested Development Environment

Either:

• IntelliJ IDEA + Cursive
• emacs + cider