Putative Assignment: Symbolic Evaluation of Boolean Expressions in Java
Background
Comp 411 presumes familiarity with functional programming in Scheme and mastery of object-oriented design in Java, most notably how to write functional programs (only involving immutable objects) in Java. Historically, the courses Comp 210 and 212 (and later Comp 211) covered this material. Several years ago, the core programming curriculum was revised, de-emphasizing functional programming and object-oriented design. As a result, it is unclear how well undergraduate students are prepared for this course. This web page presents a functional programming assignment in Java where the behavior of the Java is specified by a purely functional program in Scheme. Students who enroll in this course should be comfortable tackling this assignment (taken directly from Comp 211 in Spring 2011).
Overview
Write a Java program boolSimpBoolSimp.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:
...
- a Scheme program in the file boolsimp.ss equivalent to the Java program that you are required to write;
- a Java "stub" file
BoolSimp.java
for your program that defines a composite hierarchy of "abstract syntax" tree classes rooted in the classForm
representing boolean expressions; - a Java library file
Parser.java
containing a classParser
with- a
read()
method that reads a boolean expression represented in "Scheme form" and returns the corresponsing JavaForm
abstract syntax tree and - a
reduce()
method that composes the visitors you must write inboolSimp.dj
in to reduce whatever formula theParser
instance contains to simplified form.
- a
- a Java "stub" test file
BoolSimpTest.java
that includes some rudimentary tests of the code in theBoolSimp.java
stub file.
...
Code Block |
---|
(define-struct ! (arg))bigData0
(define-struct & (left right))
(define-struct \| (left right))
(define-struct > (left right))
(define-struct ? (test conseq alt))
|
...
The following files contain large formulas that can be reduced by your simplifier. Only the files named bigData x may require a larger thread stack size than the JVM default on most platforms. NOTE: to handle the bigData
x files bigData0 and bigData1, 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)))))))))"