Description

Mark: 3%
Prerequisite
• Caught up to Unit 32 of Lecture Notes
• Completed Lab 5
Files
The following functional interfaces are already provided:
• cs2030s.fp.Action
• cs2030s.fp . Immutator
• cs2030s.fp . Constant
• cs2030s.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:
• cs2030s.fp . Actionable
• cs2030s.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 , Test2 . java , etc., as well as CS2030STest.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 cs2030s . 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 ActuallY<T> 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 . . . > 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 cs2030s.fp.Constant
2
3 j shell> import cs2030s.fp.Lazy
4 j shell> Lazy<lnteger> mod 1 – Lazy. from(2030)
5 j shell> modl .get( )
6
7 2030
8 j shell> Lazy<String> mod2 = Lazy. from( () ‘l CS2030S” )
9 j shell> mod2 . get( )
10
1 1 ‘ICS2030S”
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 ‘l
‘l hello
19 j shell> hello.get( ) // note “world! ‘ is printed again
20 world ! ‘I
21 ‘I 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 cs2030s/fp/*java
2 $ javac -Xlint :rawtypes Test 1 . java
3 $ java Test 1
4 $ java -jar æcs2030s/bin/checksty1e.jar -c
5 Lazy. java $ javadoc -quiet -private -d docs cs2030s/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 cs2030s.fp.Constant
2 jshell> import cs2030s.fp.Memo
3
4 jshell> Memo<lnteger> mod 1 = Memo. from(2030)
5 jshell> modl
6 mod 1 2030
7 jshell> mod 1 .get( )
8 $ 2030
9
10 jshell> Memo<String> mod2 = Memo. from( ()
11 jshell> mod2
12 mod2
13 jshell> mod2 .get( )
14
15 ‘l cs2030s lI
16 j shell> Memo<String> hello – Memo. from( ( )
17 System . out . print In( “world ! ” ) ;
18
19 return “hello” ;
20 j shell> hello
21

hello”hello”
22 j shell> hello. get( ) 23 world !
24’I hello ‘I
25 j shell> hello.get( ) // note “world! ‘I is NOT printed again
26’l hello ‘l
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 cs2030s/fp/*java
2 $ javac -Xlint : rawtypes Test2.java
3 $ java Test2
4 $ java -jar pucs2030s/bin/checksty1e.jar -c
5 Memo . java
$ javadoc -quiet -private -d docs cs2030s/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).
j shell> import cs2030s.fp.Constant
2 j shell> import cs2030s.fp.Immutator
3 j shell> import cs2030s.fp.Lazy
4
5 j shell> import cs2030s.fp.Memo
6 j shell> Constant<String> password ” 123456 ”
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.
7
8 jshell> Lazy<String> lazy – Lazy. from(password)
9 jshell> lazy
10 lazy 123456
11 jshell> lazy. transform(str -> str.substring(0, 1 ) )
12
13
14 jshell> Memo<String> memo = Memo . from(password) 1 5 jshell> memo. transform(str -> str.substring(0, 1 ) )
16
17 jshell> memo
1 8 memo
19 jshell> memo. transform(str -> str.substring(0, l ) ) .get( )
20
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
30 return str . length( ) ;
31 j shell> Lazy<lnteger> lazyLen – lazy. transform(len)
32 j shell> lazyLen
33 length
34 lazyLen
35 j shell> lazyLen . get( )
36 length
6
38 j shell> lazyLen . get( )
39 length
40
41 6
42 j shell> Memo<lnteger> memoLen – – memo. transform(len)
43
44 j shell> memoLen memoLen

45
46
47

49
50 j shell> length

j shell>
memoLen . get ( )
6 memoLen . get ( )
6
51 j shell> Memo<lnteger> stepl – Memo. from(1010)
52
53 stepl 1010
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 + 10) )
57 step3
58 j shell> step3 . get()
59 2030
60 j shell> step2 // to get() step3 need to get( ) step2
62 j shell> stepl // to get() step2 need to get( ) stepl 63 stepl 1010
64
65 j she 11> Memo<lnteger> noErr = Memo. from(0)
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 cs2030s/fp/*java
2 $ javac -Xlint : rawtypes Test3 . java
3 $ java Test3
4 $ java -jar æcs2030s/bin/checksty1e.jar -c
5 Lazy. java 6 $ javadoc -quiet -private -d docs cs2030s/fp/Lazy.java
7 $ java -jar æcs2030s/bin/checksty1e.jar -c
Memo . java
$ javadoc -quiet -private -d docs cs2030s/fp/Memo.java
Combine
We have provided an interface called Combiner<R, S, T> in cs2030s . 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 cs2030s.fp.Combiner
2 j shell> import cs2030s.fp.Memo
3
4 j shell> Memo<lnteger> twenty, thirty, modlnt
5 twenty null
6 thirty null
7 modlnt null
8
9 j shell> twenty = Memo. from( ( ) – > 20)
10 twenty
11 j shell> thirty – Memo. from( ( ) 30)
12 thirty
13
14 j shell> Combiner<String, Integer, Integer > concat = (x,
15 System . out . print ‘I combine” ) ;
16 return x.toString( ) + y.toString( ) ;
17
18
19 j shell> modlnt – twenty. combine(thirty, (x, y) -> x * 100 + y)
20 modlnt
21 j shell> Memo<String> modStr = twenty. combine(thirty, concat)
22 modStr
23
24 j shell> modStr . get( )
25 combine
26 “2030” j shell> twenty 28 twenty 20
29 j shell> thirty
30 thirty 30
31
32 j shell> modlnt
33 modlnt

35 j shell> Combiner<String, Integer, Double> comb – (x, y) -> x.toString( ) +
361 1y. toString( ) j shell> Memo<String> s = modInt.combine(Memo.from(0.1 ) , comb)
38 s
39 j shell> s .get( )
40″2030 + 0.1
41 j shell> modlnt
42

modlnt2030
43
44 j shell> Memo<lnteger> x = Memo . from(l )
45 j shell> for (int i – 0 ; i < 10 ; i ++) {
46final Memo<lnteger> y – x ; // final just to ensure it is
47 unchanged final int j – i ;
49 Memo . from( ( ) > { System.out.println(j ) ; return y.get( ) +
50 y.get( ) ;
51
52 j shell> x. get( ) ;
53 9
54 8
55 7
56 6
57 5
58 4
59 3
60 2
1 024
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 cs2030s/fp/*java
2 javac -X lint : rawtypes Test4. java
3 java Test4
4 $ java -jar æcs2030s/bin/checksty1e.jar -c æcs2030s/bin/cs2030_checks.xm1 5 Lazy. java
6 $ javadoc -quiet -private -d docs cs2030s/fp/Lazy.java
7 $ java -jar æcs2030s/bin/checksty1e.jar -c
Memo . java
$ javadoc -quiet -private -d docs cs2030s/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
10
11 return true;
12 j shell> Constant<B001ean> f = new Constant<>() {
13 public Boolean init() {
14 String res = 1 1
15 for (int i=0; i<100000;
16
17 res += i;
18
19 return false;
20
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()
30 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;
10
11
12 j shell> Constant<B001ean> f = new Constant<>() {
13 public Boolean init() {
14 String res –
15 for (int i=0; i<100000; i++) {
16 res += i;
17
18 return false;
19
20
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( )
30 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 cs2030s/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.