Putative Assignment: Symbolic Evaluation of Boolean Expressions in Java
Write a Java program
boolSimp.java that reduces boolean expressions (represented in the input and output streams in Scheme-like notation) to simplified form. For the purposes of this assignment, boolean expressions are Scheme expressions constructed from:
- the symbols
Fdenoting the boolean values
- boolean variables (represented by symbols other than
?that can be bound to either
- the unary function
- the binary functions
implies, respectively), and
- the ternary function
The shorter names
? are used instead of
if for notational brevity which matters in very large inputs.
The course staff is providing:
- a Scheme program in the file
boolsimp.ssequivalent to the Java program that you are required to write;
- a Java "stub" file
boolSimp.javathat defines a composite hierarchy of "abstract syntax" tree classes rooted in the class
Formrepresenting boolean expressions;
- a Java library file
Parser.javacontain a class
read()method that reads a boolean expression represented in "Scheme form" and returns the corresponsing Java
Formabstract syntax tree and
reduce()method that composes the visitors you must write in
boolSimp.djto reduce whatever formula the
Parserinstance contains to simplified form.
- a Java "stub" test file
boolSimpTest.javathat includes some rudimentary tests of the code in the
The stub file
BoolSimp.java also includes comments showing you exactly what code you have to write to complete writing your simplifier. Of course, you also need to write corresponding tests and add them to the file
Parser.java is provided to enable you to test your solution on large inputs stored in files.
Parser.java includes two
Parser(File file) and
Parser(String form) for building parsers to parse the boolean expression (in external text form) in the specified
String, respectively. Since the library class
File is defined in the package
java.io, you need to insert
at the head of a test file that uses the
Parser class on the contents of a file.
To construct a
Parser for the formula in a file
<fileName> you must invoke
new Parser(new File("<fileName>"));
If you omit the
new File(...) construction in the argument to
Parser and use
"<fileName>" instead, you will create a
Parser for the String
"<fileName>". which is interpreted as a simple boolean variable. The
File input format is important because it enables us to conveniently apply your simplifier to formulas that are thousands of symbols long. As a result, you only have to translate the Scheme code in
boolsimp.ss into corresponding cleanly-written OO Java code by filling in the gaps in our Java stub file
boolSimp.java. You are expected to appropriately use the composite, interpreter, singleton, and visitor patterns in the code that you write. Since the only stub files that you have to modify are
boolSimpTest.java, your assignment is to create expanded versions of these files including a comprehensive test suite in boolSimpTest.java. Warning: your program must handle large inputs like large test files provided below.
We have formatted the test files as a
.java file rather than a
.dj because the Language Levels facility peforms no useful augmentation of JUnit test classes and bypassing the language levels translator avoids some annoying bugs in the implementation of that facility. When using the "Save As" command, please remember to save you file
boolSimpTest.java as a
.java file not as a
.dj file. The "Save" command always retains the file types of all files.
The Scheme file
boolsimp.ss includes Scheme functions
unparse to translate Scheme lists into abstract syntax trees and vice-versa. Scheme provides a simple external syntax for lists (in homage to its LISP heritage) but Java does not. Hence the Java
Parser class works on Java strings instead of lists. The Java visitor class
BoolSimp.java file performs unparsing of the abstract syntax types
IfForm to type String.
The Scheme parsing functions rely on the following Scheme data definitions.
(define-struct ! (arg)) (define-struct & (left right)) (define-struct \| (left right)) (define-struct > (left right)) (define-struct ? (test conseq alt))
boolExp is either:
- a boolean constant
- a symbol
Srepresenting a boolean variable;
(make-And X Y) where Xand
(make-Or X Y) where Xand
(make-Implies X Y) where Xand
(make-If X Y Z)where
or operator must be written as
in Scheme instead of
| is a metasymbol with a special meaning in Scheme.
Description of the Provided Scheme program
Given a parsed input of type
boolExp, the simplification process consists of following four phases:
- Conversion to
ifform implemented by the function
- Normalization implemented by the function
- Symbolic evaluation implemented by the function
- Conversion back to conventional boolean form implemented by the function
These phases are described in detail in HW6.
Hints on Writing Your Java Code
The Java abstract syntax classes include a separate composite hierarchy (called
IfForm) for representing boolean expression as conditionals (the type
boolsimp.ss). This representation includes only three concrete variant classes, making it much easier to write the visitors that perform normalization, evaluation, and clean-up.
The visitor pattern is a straightforward but notationally involved alternative to the interpreter pattern. If you do not have much experience writing and debugging Java code involving visitors, we suggest that you write a solution using the interpreter pattern first and then translate your interpreter pattern code to visitor pattern code. (Perhaps IDEs like Eclipse should support such transformations.) We are providing support code for writing an interpreter solution. The support code for interpreter solution replaces the
Here are the links for the files:
- boolsimp.ss is the reference Scheme program.
- BoolSimp.dj is a stub program for a visitor solution.
- BoolSimpTest.java\ is a stub test file for a visitor solution.
- Parser.java is a parser file for a visitor solution.
- InterpBoolSimp.dj is a stub program for an interpreter solution.
- InterpBoolSimpTest.java is a stub test file for an interpreter solution.
- InterpParser.java is a parser file for an interpreter solution.
InterpParser.java is distinct from
Parser.java because the code for the
reduce method embedded in the parser is different in the two versions.
Sample Input Files
The following files contain large formulas that can be reduced by your simplifier. Only the files named
bigData x require a larger thread stack size than the JVM default on most platforms. NOTE: to handle the
bigData x files, you may need to pass the JVM argument -Xss64M for the Interactions JVM using the DrJava Preferences command on the Edit menu. The JVM argument setting can be found on the last panel (called JVMs) in the Preferences categories tree.
- littleData1\ -> "T"
- littleData2\ -> "T"
- littleData3\ -> "(> h (> g (> f (> e (> d (> c (! b)))))))"
- littleData4\ -> "(> h (> g (> f (> e (| d (| c (| b a)))))))"
- bigData0\ -> "T"
- bigData1\ -> "(> j (> i (> h (> g (> f (> e (| d (| c (| b a)))))))))"