Date: Fri, 29 Mar 2024 05:27:51 -0500 (CDT) Message-ID: <151787643.1155.1711708071703@wiki-n2.rice.edu> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_1154_330055116.1711708071700" ------=_Part_1154_330055116.1711708071700 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html
Write a Java program boolSimp.dj
that reduces boolean expre=
ssions (represented in the input and output streams in Scheme-like notation=
) to simplified form. For the purposes of this assignment, boolean expressi=
ons are Scheme expressions constructed from:
T
and F
denoting the boolean valu=
es true
and false
;T
, !
, &
, |
, >=
;
, and ?
that can be bound to either true
=
or false
.!
meaning not
.&
, |
, and >=
denoting and
, or
, and implies
, respectively), and?
meaning if
.The shorter names T
, F
, !
, =
&
, |
, >
, and ?
are use=
d instead of true
, false
, not
, and
, or
, implies
, and if
for=
notational brevity which matters in very large inputs.
The course staff is providing:
boolsimp.ss
equivalent to the=
Java program that you are required to write;boolSimp.dj
that defines a composite hi=
erarchy of "abstract syntax" tree classes rooted in the class Form representing boolean expressions;
Parser.java
contain a class Pars=
er
with=20
read()
method that reads a boolean expression represente=
d in "Scheme form" and returns the corresponsing Java Form
abs=
tract syntax tree andreduce()
method that composes the visitors you must writ=
e in boolSimp.dj
to reduce whatever formula the Parser=
code> instance contains to simplified form.
boolSimpTest.java
that includes so=
me rudimentary tests of the code in the boolSimp.dj
stub file.=
The stub file BoolSimp.dj
also includes comments showing yo=
u 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 f=
ile BoolSimpTest.java
.
The file Parser.java
is provided to enable you to test your=
solution on large inputs stored in files. Parser.java
include=
s two Parser
constructors Parser(File file)
and <=
code>Parser(String form) for building parsers to parse the boolean e=
xpression (in external text form) in the specified File
or File
i=
s defined in the package java.io
, you need to insert either
import = java.io.*;
or more specifically
import = java.io.File;
at the head of a test file that uses the Parser
class on th=
e contents of a file.
To construct a Parser
for the formula in a file <fil=
eName>
you must invoke
new Par= ser(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>"<=
/code>. which is interpreted as a simple boolean variable. The
File=
code> input format is important because it enables us to conveniently apply=
your simplifier to formulas that are thousands of symbols long. As a resul=
t, you only have to translate the Scheme code in
and boolsimp.ss
i=
nto corresponding cleanly-written OO Java code by filling in the gaps in ou=
r Java stub file boolSimp.dj
. You are expected to appropriatel=
y use the composite, interpreter, singleton, and visitor patterns in the co=
de that you write. Since the only stub files that you have to modify are boolSimpTest.java
, simply submit ex=
panded versions of these files via OwlSpace to submit your assignment. =
Warning: we will run your program on large inputs to determine if you =
wrote the code correctly. Try using the large test files provided on the co=
urse wiki.
We have formatted the test files as a .java
file rather tha=
n a .dj
because the Language Levels facility peforms no useful=
augmentation of JUnit test classes and bypassing the language levels trans=
lator avoids some annoying bugs in the implementation of that facility. Whe=
n using the "Save As" command, please remember to save you file boolS=
impTest.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 parse
and unparse
to translate Scheme lists into abstr=
act syntax trees and vice-versa. Scheme provides a simple external syntax f=
or 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 Print
in the BoolSimp.java
file pe=
rforms unparsing of the abstract syntax types Form
and I=
fForm
to type String.
The Scheme parsing functions rely on the following Scheme data definitio= ns.
Given
(define= -struct ! (arg)) (define-struct & (left right)) (define-struct \| (left right)) (define-struct > (left right)) (define-struct ? (test conseq alt))
a boolExp
is either:
true
and false
;S
representing a boolean variable;(make-Not X)
where X
is a boolExp
;(make-And X Y) where =3DX
and Y
are boo=
lExps
;(make-Or X Y) where =3DX
and Y
are bool=
Exps
;(make-Implies X Y) where {{X
and Y
are =
boolExps
; or(make-If X Y Z)
where X
, Y
, and =
Z
are boolExps
.Note: The or
operator must be written as
\|
in Scheme instead of |
because |
is a metasymb=
ol with a special meaning in Scheme.
Given a parsed input of type boolExp
, the simplification pr=
ocess consists of following four phases:
if
form implemented by the function co=
nvert-to-if
.normalize
.eval
.convert-to-bool
.These phases are described in detail in HW6.
The Java abstract syntax classes include a separate composite hierarchy =
(called IfForm
) for representing boolean expression as conditi=
onals (the type ifExp
in boolsimp.ss
). This repre=
sentation includes only three concrete variant classes, making it much easi=
er to write the visitors that perform normalization, evaluation, and clean-=
up.
The visitor pattern is a straightforward but notationally involved alter= native to the interpreter pattern. You can mechanically translate interpret= er pattern code to visitor pattern code. (Perhaps IDEs like Eclipse should = support such transformations.) The interpreter solution to this assignment = is easier to write than the visitor solution described in the preceding pro= gram description. If you are still learning Java mechanics, you are encoura= ged to write an interpreter solution first and translate it (if you can) to= visitor form. A perfect interpreter solution will only be penalized 15% ve= rsus a perfect visitor solution. If you submit an interpreter solution, you= r program must conform to class signatures given in the interpreter pattern= support code below (just as a visitor solution must conform to the class s= ignatures given in the visitor pattern code below).
The interpreter version of the support code replaces the ConvertTo=
If
, Normalize
, HeadNormalize
, Evalua=
te
, and Print
visitors by methods named convertTo=
If
, normalize
, headNormalize
, eval=
code>, and
print
.
Here are the links for the files:
InterpParser.java
is distinct from Parser.java
=
because the code for the reduce
method embedded in the parser=
is different in the two versions.
The following files contain large formulas that can be reduced by your s=
implifier. Only the files named bigData
x require a larger thr=
ead stack size than the JVM default on most platforms. NOTE: to handle the bigData
x files, you must set JVM argument -X=
ss64M 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.