Description
Prerequisite
• Caught up to Unit 32 of Lecture Notes
• Completed Lab 5
Files
The following functional interfaces are already provided:
• cs2Ø3Øs.fp.Action
• cs2Ø3Øs.fp . Immutator
• cs2Ø3Øs.fp . Constant
• cs2Ø3Øs.fp . Combiner
• This is a new functional interface to combine two values into one.
• If Immutator takes in only one value, Combiner takes in two values.
Additionally, the following interfaces are already provided as well:
• cs2Ø3Øs.fp . Actionable
• cs2Ø3es.fp.Immutatorab1e
Copy your implementation of Actually over before you get started with Lab 6. A skeleton for Lazy<T> and Memo<T> are provided for your. Additionally, you are given the simple and non-lazy implementation of Boolean expression:
• Cond . java : an interface abstracting a boolean condition that can be evaluated
• Bool . java : a boolean value
• And . java : a conjunction
• Or . java : a disjunction
• Not. java : a negation
The files Testl . java , Test-2 . java , etc., as well as CS2Ø3ûSTest.java , are provided for testing. You can edit them to add your test cases, but they will not be submitted.
Being Lazy and Smarter
Programming languages such as Scala support lazy values, where the expression that produces a lazy value is not evaluated until the value is needed. Lazy value is useful for cases where producing the value is expensive, but the value might not eventually be used. Java, however, does not provide a similar abstraction. So, you are going to build one.
This task is divided into several stages. You are highly encouraged to read through all the stages to see how the different levels are related.
You are required to design a Lazy and Memo classes as part of the cs293es . fp package with one field. You are not allowed to add additional fields to Lazy .
public class Lazy<T> / * implements Immutatorab1e<T> (for later) * / {
2 private Constant<? extends T > init ;
3
4
public class Memo<T> extends Lazy<T> {
2 private value;
3
4
The Basics of Being Lazy
The idea of being lazy is that we do not compute unless we really really really need to. When do we need to compute the value? Simple, that is when we try to get the value.
Define a generic Lazy<T> class to encapsulate a value with the following operations such that for each derive the most flexible type:
• protected constructor protected . . > c) that takes in a constant that produces the value when needed.
• static from(T v) method that instantiate the Lazy object with the given value using the protected constructor above.
• static from(Constant< . . > c) method that takes in a constant that produces the value when needed and instantiate the Lazy object.
• get() method that is called when the value is needed. Compute the value and return.
• toString( ) : returns the string representation of the value.
j shell> import cs2Ø3Øs.fp.Constant
2
3 j shell> import cs2Ø3ûs.fp.Lazy
4 j shell> Lazy<lnteger> mod 1 Lazy . from(2û3Ø)
5 j shell> modl .get( )
6
7 2939
8 j shell> Lazy<String> mod2 Lazy. from( () ‘l cs2e3es ‘I )
9 j shell> mod2 . get( )
19
1 1 ‘l cs20es ‘I
12 j shell> Lazy<String> hello – Lazy. from( ( )
13 System . out . print In( “world !
14
15 >
return “hello’
16 j shell> hello. get( )
17 world !
18 hello
19
j shell> world ! hello.get( ) // note “world! is printed again
21 ” hello ”
You can test your code by running the Test 1 . java provided. The following should compile without errors or warnings. Make sure your code follows the CS2030S Java style and can generate the documentation without error.
• $ javac cs2Ø3Øs/fp/*java
2 $ javac -Xlint :rawtypes Test 1 . java
3 $ java Test 1
4 $ java -jar
5 Lazy. java
$ javadoc -quiet -private -d docs cs2Ø3Ês/fp/Lazy.java
Smarter Lazy
The smarter idea of being lazy is that if we have computed the value before (i.e., called get( ) ) then we do not compute the value again. This is called memoization (the word comes from memo and not a typo from memorization). Since we already have an
, when we try perform a computation and the current value might still be uninitialised we treat this like a failure. In order to prevent this failure, we first produce the value using a Constant to initialise the value. Now, this is no longer a failure but a success!
Take note of the following constraints:
• Avoid using the Actually: : unwrap method and avoid access the classes
Actually. Success<T> or Actually . Failure directly.
• Since Actually has internalized try-catch (which kind of mimics if-else ) checks for whether the value is there or not, you must not use any form of conditional statements and/or try-catch to compare if value has been initialised or not.
• You are not allowed to use any raw types.
• You don’t need any @SuppressWarnings for this lab, but if you do, it must be used responsibly.
Define a generic Memo<T> class to encapsulate a value with the following operations such that for each derive the most flexible type:
• you should not have public constructor.
• static from(T v) method that initializes the Memo object with the given value. In this case, the Memo is already initialised (i.e., already computed).
• static from(Constant< . . > c) method that takes in a constant that produces the value when needed. In this case, the Memo is uninitialised.
• get() method that is called when the value is needed. If the value is already available return that value; otherwise, compute the value and return it. The computation should only be done once for the same value.
• toString() : returns if the value is not yet available; returns the string representation of the value otherwise.
Note that for our class to be immutable and to make the memoization of the value transparent, toString should call get() and should never return “?” . We break the rules of immutability and encapsulation here, just so that it is easier to debug and test the laziness of your implementation.
• jshell> import cs2Ø3Ês.fp.Constant
2 jshell> import cs2Ø3Øs.fp.Memo
3
4 jshell> Memo<lnteger> mod 1 Memo . from(2Ø3Ø)
5 jshell> modl
6 mod 1 2939
7 jshell> mod 1 .get( )
8 $ 293Ê
9
19 jshell> Memo<String> mod2 – Memo . from( ( )
11 jshell> mod2
12 mod2
13 jshell> mod2 .get( )
14
15 ‘l cs2e3es lI
16 j shell> Memo<String> hello – Memo .
17 System. out . print “world ! ” ) •
18
19 return “hello’
29 j shell> hello
21 hello Il
hello”
22 j shell> hello. get( ) 23 world !
24″ hello ”
25 j shell> hello.get( ) // note “world! ‘l is NOT printed again
26 hello
You can test your code by running the Test2 . java provided. The following should compile without errors or warnings. Make sure your code follows the CS2030S Java style and can generate the documentation without error.
$ javac cs2Ø3Øs/fp/*java
2 $ javac -Xlint : rawtypes Test2.java
3 $ java Test2
4 $ java -jar -vcs2Ø3es/bin/checksty1e.jar -c
5 Memo . java
$ javadoc -quiet -private -d docs cs2Ø3Øs/fp/Memo.java
Implementing Immutatorable and Adding Next
Now let’s implement Immutatorable interface to our Lazy and Memo as well as adding next method. To do this, add the transform and next method to both Lazy and Memo . First, for Lazy .
Add the transform method to Lazy . Additionally, add the next method (we did not have an interface for this for simplicity). Remember that Lazy should not evaluate anything until get() is called, so the function f passed into Lazy through transform and next should not be evaluated until get() is called. The result should not be cached (i.e., memoized).
Next, add the transform and next method to Memo . These two methods should override the methods from Lazy . This should limit the type of the input parameter. But the return type here should be as specific as method overriding allows. Remember that Memo should cache the result. In other words, they should only be evaluated once, so that function must not be called again.
j shell> import cs2Ø3Ês.fp.Constant
2 j shell> import cs2Ø3es.fp.Immutator
3 j shell> import cs2Ø3Ês.fp.Lazy
4
5 j shell> import cs2Ø39s.fp.Memo
6 j shell> Constant<String> password ” 123456’
7
8 jshell> Lazy<String> lazy Lazy. from(password)
9 jshell> lazy
19 lazy 123456
11 jshell> lazy. transform(str -> str .substring(e, 1 ) )
12
13
14 jshell> Memo<String> memo – Memo . from(password) 1 5 jshell> memo. transform(str -> str.substring(û, 1 ) )
16
17 jshell> memo
1 8 memo
19 jshell> memo. transform(str -> str.substring(û, l ) ) .get( )
29
21 jshell> memo
22 memo 123456
23 j shell> memo . get( )
24
25 ‘1 1 23456 ”
26 j shell>
Immutator<lnteger, String> len – str System . out . print “length” ) ;
28
29
39 return str . length( ) ;
31 j shell> Lazy<lnteger> lazyLen – lazy. transform(len)
32
33
34 j shell> length lazyLen lazyLen
35
36 j shell> length
lazyLen . get( )
6
38
39
41 j shell> length
lazyLen . get( )
6
42 j shell> Memo<lnteger> memoLen – memo. transform(len)
43
44 j shell> memoLen memoLen
45
46
47
49
59 j shell> length
j shell>
memoLen . get ( )
6 memoLen . get ( ) 6
51
52
53 j shell> stepl Memo<lnteger>
stepl Memo. from(1ØIØ)
54
55 j shell> step2 Memo<lnteger>
step2 – stepl . transform(i -> i * 2)
56 j shell> Memo<lnteger> step3 – step2.next(i -> Memo. from(i + 18) )
57 step3
58 j shell> step3 . get()
59
69 j shell> step2 // to get() step3 need to get( ) step2
61 step2 ‘2Ê2e
62 j shell> stepl // to get() step2 need to get( ) stepl
63 stepl 1919
64
65 j she 11> Memo<lnteger> noErr Memo. from(e)
66 noErr j shell> Memo<lnteger> – noErr.transform(x -> 1 / x)
68 err
69 j shell> // if you run err .get( ) , you will get an exception
You can test your code by running the Test3 . java provided. The following should compile without errors or warnings. Make sure your code follows the CS2030S Java style and can generate the documentation without error.
$ javac cs2Ø3Øs/fp/*java
2 $ javac -Xlint : rawtypes Test3 . java
3 $ java Test3
4 $ java -jar
5 Lazy. java
6 $ javadoc -quiet -private -d docs cs2Ø3Ês/fp/Lazy.java
7 $ java -jar Ncs2Ø3es/bin/checksty1e.jar -c
Memo . java
$ javadoc -quiet -private -d docs cs2Ø3Ês/fp/Memo.java
Combine
We have provided an interface called Combiner<R, S, T> in cs2Ø3Ûs . fp , with a single combine method to combine two values, of type S and T respectively, into a result of type R .
j shell> import cs2Ø3Ês.fp.Combiner
2 j shell> import cs2Ø3Øs.fp.Memo
3
4 j shell> Memo<lnteger> twenty, thirty, modlnt
5 twenty null
6 thirty null
7 modlnt null
8
9
19 j shell> twenty twenty
Memo . from( ( )
11 j shell> thirty Memo . from( ( )
12 thirty
13
14 j shell> Combiner<String, Integer, Integer > concat – (x,
15 System . out . print ” combine” ) ;
16 return x.toString( ) + y.toString( ) ;
17
18
19 j shell> modlnt – twenty. combine(thirty, (x, y) -> x * 10 + y)
29 modlnt
21 j shell> Memo<String> modStr – twenty. combine(thirty, concat)
22 modStr
23
24 j shell> modStr . get( )
25 combine
26 j shell> twenty 28 twenty 29
29 j shell> thirty
39 thirty 39
31
32 j shell> modlnt
35 j shell> Combiner<String, Integer, Double> comb (x, y) -> x.toString( ) +
36 y. toString( )
j shell> Memo<String> s modlnt . combine(Memo . from(û.l ) , comb)
38 s
39 j shell>
s .get( )
‘1 2939 + e . 1
41 j shell> modlnt
33 modlnt
42
modlnt293B
43
44 j shell> Memo<lnteger> xMemo . from(l )
45 j shell> for (int i
46final Memo<lnteger> y x ; // final just to ensure it is
47 unchanged final int j – i ;
49 x Memo . from( ( ) > { System.out.println(j ) ; return y.get( ) +
59 y.get( ) ;
51
52 j shell> x. get( ) ;
53 9
54 8
55 7
56 6
57 5
58 4
59 3
69 2
1 924
You can test your code by running the Test4. java provided. The following should compile without errors or warnings. Make sure your code follows the CS2030S Java style and can generate the documentation without error.
javac cs2Ø3Øs/fp/*java
2 javac -X lint : rawtypes Test4. java
3 java Test4
4 $ java -jar
5 Lazy. java
6 $ javadoc -quiet -private -d docs cs2Ø3Øs/fp/Lazy.java
7 $ java -jar -vcs2Ø3ûs/bin/checksty1e.jar -c
Memo . java
$ javadoc -quiet -private -d docs cs2Ø3Ês/fp/Memo.java
Boolean Algebra
The Memo class can be used to build a function with short-circuit operation.
Consider a boolean expression with 4 classes abstracted into an interface Cond . java :
• Bool.java : stores a boolean value which maybe true or false .
• And . java : conjunction of two boolean expressions, created from And(Cond IVa1, Cond rVa1) to mean IVa1 && rVa1 .
• Or. java : disjunction of two boolean expressions, created from Or(Cond IVa1, Cond rVa1) to mean IVa1 I l rVa1 .
• Not . java : negation of a boolean expression, created from Not (Cond val) to mean ! val .
Creating an instance of boolean expression above requires us to have fully evaluated the arguments. As such, when we call the eval method, all the values have actually been evaluated. But remember that the operation && and I I are actually short-circuit operation. In particular, false && X and true I I X should not evaluate the value X since the result will already be false and true respectively.
But suppose x takes very long to evaluate. Short-circuit operation will simply return the result without evaluating the value of x and that saves us time. This is exactly what we want to do. We want to avoid evaluating this X whenever possible. Study the code below to understand how the classes work. You do not really have to know how negation method neg works. But if you are interested in it, you can look up De Morgan’s Law.
j shell> / open Cond.java
2 j shell> /open Bool.java
3 j shell> /open And . java
4 j shell> /open Or. java
5
6 j shell> /open Not . java
7 j shell> Constant<B001ean> t – new Constant<>() {
8 public Boolean init() {
9
19
11 return true;
12 j shell> Constant<B001ean> f = new Constant<>() {
13 public Boolean init() {
14 String res –
15 for (int i=Û; i<leeeee,•
16
17 res i;
18
19 return false;
29
21 j shell> // the following line will take some time to run
22 j shell> Cond cond new And(new Or (new Bool(t) , new Bool(f) ) , new Not (new
23 Not (new Bool(t) ) ) )
24 cond –
25
26 j shell>
cond.neg( )
28 j shell>
cond.neg( ) .neg( )
29 j shell> cond.eval()
39 true
31 j shell> cond.neg( ) .eval( )
32 false
33 j shell>
cond.neg( ) .neg( ) .eval( ) true
Change the boolean expression implementation above such that a value is only evaluated when it is truly needed. You should use Memo class in your changes.
Hint: you only need to make minimal changes. Neither a new field nor a new function is necessary. If done correctly, the following sample run below should run very quickly.
j shell> / open Cond.java 2 j shell> /open Bool.java
3 j shell> /open And . java
4 j shell> /open Or. java
5 j shell> /open Not . java
6
7 j shell> Constant<B001ean> t – new Constant<>() {
8 public Boolean init() {
9 return true;
19
11
12 j shell> Constant<B001ean> f = new Constant<>() {
13 public Boolean init() {
14 String res –
15 for (int i=Û; i<leegee,• i++) {
16 res i;
17
18 return false;
19
29
21 j shell> // the following line will run very quickly
22 j shell> Cond cond – new And(new Or (new Bool(t) , new Bool(f) ) , new Not (new
23 Not (new Bool(t) ) ) )
24 cond
25 jshell> cond .neg( )
26 jshell> cond .neg( ) .neg( )
28
29 j she 11> cond . eval( )
39 true
31 j shell> cond . neg( )
32
33 j shell> cond.neg( ) .neg( )
You can test your code by running the Test5 . java provided. The following should compile without errors or warnings. Make sure your code follows the CS2030S Java style but there is no need to generate javadoc.
$ javac cs2Ø3Øs/fp/*java
2 $ javac -Xlint : rawtypes Test5.java 3 $ java Test5
Following CS2030S Style Guide
You should make sure that your code follows the given Java style guide.
Grading
This lab is worth 12 marks and contributes 3% to your final grade. The marking scheme is as follows:
• Documentation: 2 marks
• Everything Else: 10 marks
We will deduct 1 mark for each unnecessary use of @SuppressWarnings and each raw type. @SuppressWarnings should be used appropriately and not abused to remove compilation warnings.
Note that general style marks are no longer awarded will only be awarded for documentation. You should know how to follow the prescribed Java style by now. We will still deduct up to 2 marks if there are serious violations of styles. In other words, if you have no documentation and serious violation of styles, you will get deducted 4 marks.
Submission
Similar to Lab 5, submit the files inside the directory cs2030s/fp along with the other file without the need for folder. Your cs2030s/fp should only contain the following files:
Action. java
Actionable . java
Actually. java
Combiner . java
Constant . java
Immutator . java
Immutatorable . java
Lazy. java
Memo . java
Additionally, you must submit the file Lab6 . h . Otherwise, you CodeCrunch submission will not run.
