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 class Form representing boolean expressions;
• a Java library file Parser.java containing a class Parser with
  
  • a read() method that reads a boolean expression represented in "Scheme form" and returns the corresponsing Java Form abstract syntax tree and
  • a reduce() method that composes the visitors you must write in boolSimp.dj in  to reduce whatever formula the Parser instance contains to simplified form.
• a Java "stub" test file BoolSimpTest.java that includes some rudimentary tests of the code in the BoolSimp.java stub file.

...

(define-struct ! (arg))bigData0
(define-struct & (left right))
(define-struct \| (left right))
(define-struct > (left right))
(define-struct ? (test conseq alt))

...

• boolsimp.ss is the reference Scheme program.
• BoolSimp.java 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.

Sample Input Files

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)))))))))"