Date: Thu, 28 Mar 2024 17:12:37 -0500 (CDT) Message-ID: <527773247.1047.1711663957355@wiki-n2.rice.edu> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_1046_1189434890.1711663957354" ------=_Part_1046_1189434890.1711663957354 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html
Write a (functional) Java program that constructs primes
, t=
he lazy inifinite stream of prime numbers 2, 3, 5, 7, ... where numbers are=
represented using Java type int
. Ignore the fact that t=
he int
type only supports integer values less than 2^31. =
We will only compute the first few thousand primes, so no one will notice.=
Obviously such a program could easily be generalized to use type java.math.BigInteger
primeSieve.java
provides the inter=
face IntStream
which is the root of a composite class hie=
rarchy supporting lazy streams of int
, including methods=
to print finite ones in conventional Lisp-like notation. The formula=
tion of streams supported in Java starting with Java 8 is not func=
tional. Simple operations like extracting the first element of a stre=
am or the length of a finite stream destroy the stream. Consequently,=
we must develop our own IntStream
library from scratch. =
Fortunately, it is not very difficult and requires comparatively little co=
de. The equivalent program in Haskell (generalized to unbounded integ=
ers) is simply
primes =3D filterPrime [2..]
=
where filterPrime (p:xs) =3D
=
p : filterPrime [x | x <- xs, x `mod` p /=3D 0]
Of course, Haskell has built-in support for lazy streams and the recursi=
ve definition of functions (like filterprime
) using pattern ma=
tching all supported by an aggressive optimizing compiler. Your task =
is to extend the provided code to support a static final field called prime=
s in the top-level interface IntStrea=
m bound to the lazy infinite stream of primes (ignoring the fact that int
arithmetic will overflow when numbers get too large. You =
also need to augment the JUnit test file (compatible with JUnit 4 as provid=
ed by DrJava) IntStreamTest.java
to further test your cod=
e. You may assume that all of the provided code is correct. [Please t=
ell us if you discover any bugs!] You do not need to test any of=
the methods in the IntStream
interface provided by the origin=
al version of primeSieve.java
.
If the course staff makes any enhancements to the support code files&nbs=
p;primeSieve.java
and PrimeSieveTest.java
, we&nbs=
p;will post messages to that effect to Piazza.
Java is strictly a call-by-value language and lacks macros, so we are go= ing to have to wrap the stream argument in a "cons" construction in a suspe= nsion (an object with a method to evaluate it and a cell to store that valu= e). This will make translating the simple Haskell code above more cum= bersome. There is a price to writing functional code in Java, a langu= age not intended to support lazy evaluation. In Racket/Scheme, we wou= ld make the stream cons operation a macro that automatically performs the w= rapping.
Inside the svn directory https://s=
vn.rice.edu/r/comp311/turnin/F20/<netid>/
, create a direct=
ory JavaProject
and put your modified files
Your task is to reimplement the Boolean Simplifier in Haskell which is v= ery easy if you are comfortable with the core constructs of Haskell. = We are providing support code to handle all IO. You only have to= use the API provided by the support code. All of the support c= ode including test files for this project is located in the Rice SVN reposi= tory at the URL https://svn.rice.edu/r= /comp311/course/HaskellProject/.
First you need to review the description of Homework 5 for to recall the= high-level steps in the simplifier. Your Haskell code will use= types very similar to the corresponding Java program, but they are slightl= y more detailed and their explication and usage is simpler than the corresp= onding Java class hierarchies.
All of the critical type definitions that you will use are defined in th=
e support file Types.hs
in the SVN repository. In =
Types.hs
, the type SimpleExpr
is either just=
a Boolean Constant, i.e, True
or False&nb=
sp;
or an identifier (a string). The type BoolExpr<=
/code> consists of more complex boolean expressions which are trees wi=
th leaves that are of type
SimpleExpr
with intermediate nodes =
(constructors) BAnd
, BOr
, BImplies,
BNot
and BIf
. The first thr=
ee are binary (two children), BNot
is =
unary, and BIf
is ternary as you would expect. =
; You must wrap a SimpleExpr
in the constructor BLe=
af
to make it a value of type BoolExpr
. Recall that in Haskell every value has a unique basic type (=
akin to a Java class).
The type IfExpr
, which is disjoint from BoolExp=
r
(just as IfForm
is disjoint from Form in the corresponding Java program)
is either a SimpleE=
xpr
(wrapped in the constructor ILeaf
) or an IIf<=
/code> which is an if-expression whose subexpressions are if expressions (a=
kin to
IfIf
in the corresponding Java program). There is a thi=
rd type NExpr
corresponding to normalized if-expressions.=
The Java program does not introduce this third type, but it could ha=
ve done so at the cost of introducing more class definitions. Haskell=
is so much lighter weight that the extra cost is negligible. Recall =
that a normalized if-expression can only have literals in the test position=
.
The simplifier itself consists of same parts as the coresponding Java pr=
ogram. A skeleton for the simplifier appears in Simplifier.hs=
code>. You only need to fill in the missing parts of this file. These are t=
he main steps of the simplification:
Tests are defined in the file Tests.hs
. Add some simple tes=
ts for eval
and toBool
. Add your tests to the uni=
tTests definition as well. Consider adding extra tests for the other functi=
ons as you see fit. We are providing a parser String -> BoolExpr=
code> called
parseBoolExpr
defined in the file Pars=
er.hs
. There is also an unparser in the file UnParser.hs
. We have setup some machinery in Main.hs
so that you can use=
the parser to feed input to the simplifier directly. To run this, simply r=
un the main action, either using ghci, or compile it with ghc and then run =
it. Ask Agnishom if you need help with this.
The assignment is self-contained in the sense that we do not require you= to install any libraries beyond what is already available in the base pack= age. So, it should be possible to run everything on https://repl.it/.&n= bsp; Corky is going to do the assignment on his laptop using Haskell Platfo= rm. He will post messages on Piazza stating what tools he is using.= p>
In the process of your development, you may, by mistake, include an infi= nite loop which builds a very large expression in memory. Haskell programs = can be very fast and this could very quickly consume a lot of memory freezi= ng your computer. This is sometimes a frustrating part of the development e= xperience. If everything is done right, however, the simplifier should be a= ble to simplify the expression in bigData1 in under a second.
Annotate all your top level definitions with types. Do not import any li= braries. Ask the course staff if you need exemption from this policy.= Do not rename or change the type of any function that has already been pro= vided to you.
Inside the svn directory https://svn.rice.edu/r/comp311/turnin/F20=
/netid/
, create a directory HaskellProject
and put the =
modified files for Simplifier.hs
and Tests.hs
. Fo=
r example, since Agnishom's netid is ac132, he would create https://s=
vn.rice.edu/r/comp311/turnin/F20/ac132/HaskellProject/
and put his f=
iles there. You should not need to upload any other files, since these are =
the only two files you will need to modify. If you do need to include anyth=
ing else; please ask course staff if you have any questions in this regard.=
Do not create any subfolders. Please use the exact path given here.<=
/p>
The final project is conducted under the same honor code as our programm= ing assignments. You may ask the staff questions and/or post question= s on Piazza about the conceptual issues in the projects but no sharing of c= ode with other people (students and non-students) or copying of code from a= ny source, notably reference books and the internet, is permitted. In= general, we prefer that you ask questions on Piazza so that all students i= n the class can see the answer.