Functional Elements and Evaluations in Java
CSE 216 : Programming Abstractions Department of Computer Science Stony Brook University Dr. Ritwik Banerjee
Functional Programming
The boundaries between language categories are fuzzy.
• Mostlyfunctional:Haskell,Lisp,ML.
• Mostlyimperative,withsomeelementsof
functional programming: Java, Python.
Functional languages typically heavily depend on (sometimes implicit) parametric polymorphism and the use of lists.
• Wehaveseentwotypesofexplicitpolymorphism so far (in Java):
the use of generics for parametric polymorphism. with inheritance, for subtype polymorphism.
Functional programming also relies a lot on recursion.
• Therefore,programbehaviorandperformance depend a lot on how parameters are evaluated.
1
© 2019 Ritwik Banerjee
Functional Programming
• Functional programming defines the output(s) of a program as a mathematical function of the input(s).
It has no concept of an ‘internal state’.
It has no ‘side effects’. That is, it does not change anything other than transforming the input to the corresponding output.
• For practical use, however, functional programs must interact with non-functional programs in some way.
For example, if you are generating an output, you would usually want to store it somewhere.
In the ‘big picture’, that is a change in the state of, say, a file.
So, practical applications usually include some components of the larger system written functionally, while other components deal with change-of-state, etc.
2
© 2019 Ritwik Banerjee
Features of functional programming
Functions are first-class values.
•a function can be passed as a parameter, •returned from a subroutine/procedure, •assigned to a variable, and
•can be created as new values at runtime.
Higher-order functions.
•Functions that can take other functions as parameters, and/or return a function as the result.
Polymorphism.
•Either inherently polymorphic because of dynamic typing, or polymorphic due to type inference.
List types and operators.
•Lists naturally embody recursion, and many operations can be performed by recursively applying the same logic on the first (or last) element of a list.
3
© 2019 Ritwik Banerjee
Features of functional programming
Aggregates for structured objects.
•Some imperative languages provide constructs to specify a structured value in-line.
•Some languages (e.g., Python, Ruby, Java) provide aggregates that can represent an unnamed functional value in-line. These aggregates are called lambda expressions.
•Lambda expressions allow these languages to create new objects ‘all-at-once’ during runtime.
Garbage collection.
•In most imperative languages, garbage collection frees up heap memory, but it does nothing to the local variables in a function (which are stored in the stack – this is fine, because the stack elements get thrown away after the function has been used).
•[these are objects with limited extent; objects that persist as long as there exists a reference to them, are said to have unlimited extent]
•Because functional languages are designed to provide unlimited extent for objects (including functions), all dynamically allocated data is stored in the heap.
4
© 2019 Ritwik Banerjee
A Java example: abstraction
• Mostexperiencedprogrammersfindit to be aesthetically more appealing and easier for reasoning, compared to imperative languages.
• Anabsenceofside-effectsmeansthat functional programs are easier to write, debug and maintain.
Issues like, say, dangling or uninitialized references don’t occur with functional programs.
void imperativeFindingChicago() { boolean found = false;
for (String city : cities) {
if (city.equals(“Chicago”)) { found = true;
break; }
}
System.out.println(“Found Chicago?:” + found); }
void functionalFindingChicago() {
System.out.println(“Found chicago?:” + cities.contains(“Chicago”)); }
5
© 2019 Ritwik Banerjee
A Java example: abstraction
• Nomanipulationofmutablevariables.
• Noneedtoworryaboutiterationdetails;theyhavebeenabstractedaway.
• Lessverbosecode;lessclutter.
• Easierfortheprogrammertostayfocusedontheintentofthecode,rather than get bogged down in details of ‘how to achieve the intent’.
• Debuggingismodular–thecontains()method(whichisafunctional component in itself) can be tested separately, and if that is bug-free, this code is automatically bug-free.
void functionalFindingChicago() {
System.out.println(“Found chicago?:” + cities.contains(“Chicago”)); }
6
© 2019 Ritwik Banerjee
A Java example: the Stream API
double totalDiscountedPrice(List
for (double price : prices) {
if (price * (1 – k/100) > n) totalDiscountedPrice += price * (1 – k/100);
}
return totalDiscountedPrice; }
public static void main(String… args) {
List
}
Given a list of item prices, find the total discounted price of items costing above $𝑛 after a 𝑘% discount.
7
© 2019 Ritwik Banerjee
A Java example: the Stream API
public static void main(String… args) {
List
System.out.println(prices.stream()
.filter(p -> p * (1 – k / 100) > n)
.map(p -> p * (1 – k / 100))
.reduce(0d, (x, y) -> x + y));}
With the use of higher-order functions like filter(), map(), and reduce(), we don’t need to write our own function at all!
8
© 2019 Ritwik Banerjee
A Java example: the Stream API • Thestream()methodconvertsatraditionaliterableobject(i.e.,anythingthat
prices.stream()
.filter(p -> p*(1 – k/100) > n)
.map(p -> p*(1 – k/100))
.reduce(0d, (x,y) -> x + y));
implements the Iterable
A ‘stream’ in Java is a sequence of objects, but they are built for functional programming.
They differ from traditional sequences (lists, etc.) in their evaluation.
• Thefilter()methodappliesabooleanfunctiontoeveryelementofastream, letting through only those elements that evaluate to true.
• Themap()methodappliesatransformationtoeveryelementofastream.
• Thereduce()methodusesaninitialvalue(inthiscase,0d)andaccumulates elements from the stream as specified by a function that takes in two parameters.
9
© 2019 Ritwik Banerjee
Evaluation
• Sofar,wehaveassumed(oftenimplicitly)thatargumentsareevaluated before they are passed to a subroutine. This is called applicative-order evaluation.
• Thisisnotalwaystrue.Itispossibletopassarepresentationofthe unevaluated arguments, and evaluate them if and when the value is actually needed. This is called normal-order evaluation.
• Considerafunction‘dbl’,whichdoublesanumber,andafunction‘avg’, which computes the average of two numbers:
def dbl(x): add(x,x)
def avg(x,y): div(add(x,y),2)
10
© 2019 Ritwik Banerjee
Example: normal-order & applicative-order
dbl(avg(2,4)
dbl(avg(2,4))
=> add(avg(2,4), avg(2,4))
=> add(div(add(2,4),2), avg(2,4))
=> add(div(6,2), avg(2,4))
=> add(3, avg(2,4))
=> add(3, div(add(2,4),2))
=> add(3, div(6,2))
=> add(3,3)
=> 6
dbl(avg(2,4))
=> dbl(div(add(2,4), 2)
=> dbl(div(6,2))
=> dbl(3)
=> add(3,3)
=> 6
11
Applicative-order
Normal-order
© 2019 Ritwik Banerjee
Evaluation
Normal-order
• Theleft-mostfunctionapplicationis always evaluated first.
• Inourexample,evaluatedthe expression avg(2,4) twice.
Applicative-order
• Theinner-mostfunctionsare evaluated first.
❗ Does extra work.
Now let’s consider the ‘if-then-else’-condition with an invalid argument:
• Semantically, if-else takes three arguments – if the first argument evaluates to true, return the second argument; otherwise, return the third argument.
• ifless(3,4)add(5,5)elsediv(1,0)
12
© 2019 Ritwik Banerjee
Example: normal-order & applicative-order
if less(3,4) add(5,5) else div(1,0)
if less(3,4) add(5,5)
else div(1,0)
=> if true add(5,5) else div(1,0) => if true add(5,5)
=> add(5,5)
=> 10
if less(3,4) add(5,5)
else div(1,0)
=> if true add(5,5) else div(1,0) => if true 10 div(1,0)
=> Error: division by zero!
13
Applicative-order
Normal-order
© 2019 Ritwik Banerjee
Lazy Evaluation
• In practice, almost no programming language uses normal-order evaluation because of the performance penalty.
• It is also difficult to use strict applicative- order evaluation because it results in too many non-terminating programs (infinite recursion, invalid argument, etc.).
With lazy evaluation, the evaluation is delayed (until needed) in a way that avoids multiple evaluations of the same expression.
• Tries to combine the best of normal-order and applicative-order evaluations.
• A value is evaluated only when needed, but once that is done, all copies of that expression are updated with the value.
14
© 2019 Ritwik Banerjee
Strict & Non- strict evaluation
• Evaluation order (i.e., how an expression is evaluated) affects the speed of a program, and also its correctness.
• A function* is said to be strict if it is undefined (i.e., fails to terminate or encounters an error) whenever its argument(s) is/are undefined. Otherwise, it is said to be non-strict.
Non-strict functions can sometimes provide an output even with invalid arguments.
• A language is said to be strict if it only allows functions that are strict. Otherwise, it is said to be a non-strict language.
• Among purely functional languages, ML is strict while Haskell is non-strict.
* In the context of functional programming, we will use the word ‘function’ to mean functions that have no side-effects.
15
© 2019 Ritwik Banerjee
Evaluation in functional languages
• Functionallanguagesmakeheavyuseoflazyevaluationsothattheydon’t have to evaluate expressions whose values are not needed.
• Islazyevaluationstrictornon-strict?
Hint: think of an if-else condition where the 3rd argument is invalid.
• Lazyevaluationisveryusefulforcreating‘infinite’or‘lazy’datastructures, where the actual structure with data is created on-the-fly as and when needed during runtime.
Strictly speaking, these are not data structures, but it helps us to think of them as some sort of infinite data structure that exists in theory.
E.g., imagine a program that analyzes each tweet as and when the tweets arrive. A programmer can think of this is an infinite list of strings, where the actual analysis will only happen when the actual string becomes available.
This is a scenario where, if you’re coding in Java, you should use the Iterable
16
© 2019 Ritwik Banerjee
Exercise
Consider the two widely-used binary logical operations ‘and’ and ‘or’, and try out simple code snippets to answer the following:
? What kind of evaluation does Java use for binary logical operations?
? What kind of evaluation does Python use for binary logical operations?
Streams
• Astreamisanunbounded-length(inpractice,boundedbytheprecisionofa 32- or 64-bit machine) sequence of elements that are evaluated lazily.
• InthefunctionalapproachinJava,themostcommonuseofstreamsisto simplify iterations and manipulate collections.
After all, a traditional collection can be viewed as a finite stream. Iterating over a list:
List
for(int i = 0; i < friends.size(); i++) { System.out.println(friends.get(i));
}
18
© 2019 Ritwik Banerjee
Streams and Iterations There is the slightly better
for (String friend : friends) System.out.println(friend);
Behind the scenes, this calls the Iterator
• Bothversionsendupmixingwhatwewanttodo(iterate)withhowwedoit. Both are imperative styles.
• WithJava8,thereisalsotheenhancedforEach()method,whichusesthe anonymous-class syntax:
friends.forEach(new Consumer
public void accept(String s) {
System.out.println(s); }
});
19
© 2019 Ritwik Banerjee
Streams and Iterations
The consumer interface has exactly one method, accept(T t), and the forEach() method invokes the accept(T t) method of the consumer for each element in the collection:
friends.forEach(new Consumer
public void accept(String s) { System.out.println(s);
} });
? Why or how are we specifying the generic parameter T to be String in the consumer used in the above example?
20
© 2019 Ritwik Banerjee
Streams and Iterations
• TheanonymousinnerclassusagewithforEach()isclearlymoreverbose! • Butitcanbereplacedwithalambdaexpression:
friends.forEach(s -> System.out.println(s));
• Infact,thereisasyntacticsugartofurtherreducetheamountofcode,
called a method reference: friends.forEach(System.out::println);
❗ Parameters cannot be modified inside a lambda expression. You may not have declared them to be final, but they are effectively final inside a lambda expression.
21
© 2019 Ritwik Banerjee
Streams and Transformations
• Using streams, it is very easy to transform one collection into another.
• The following, for instance, are easy to do:
applying a function to every element
filtering out certain elements
accumulate all elements into a single object
22
© 2019 Ritwik Banerjee
Method References
• We will normally use lambda expressions much more than method references when programming in Java.
• Method references are still very useful to keep to code concise.
• They are nice replacements when the lambda expressions are really short and make direct calls to either an instance method or a static method, using only the parameter being passed through.
In other words, if lambda expressions merely pass their parameters through, we can replace them with method references.
23
© 2019 Ritwik Banerjee
The DRY principle
• Intheworldofprogramming,DRYstandsfordon’trepeatyourself.
• Butgivenhowsimpleitistoaccomplishrelativelycomplextasksinoneline, using lambda expressions, it is easy to forget this principle and write code like this:
List
long c1 = friends.stream().filter(n -> n.startsWith(“N”)).count(); long c2 = editors.stream().filter(n -> n.startsWith(“N”)).count(); long c3 = others.stream().filter(n -> n.startsWith(“N”)).count();
24
© 2019 Ritwik Banerjee
The DRY principle
• Intheworldofprogramming,DRYstandsfordon’trepeatyourself.
• Instead,youshouldseparatelywritetheinternallogicoftherepeating lambda expression using a
•
Predicate
private static Predicate
}
long frnds_n1 = friends.stream().filter(startsWithN).count(); long frnds_n2 = friends.stream().filter(startsWith(“N”)).count(); long frnds_b1 = friends.stream().filter(startsWith(“B”)).count();
25
© 2019 Ritwik Banerjee
Lazy Evaluations in Java
• Java uses eager, applicative-order evaluation for method arguments.
• All arguments are fully evaluated before the method is invoked.
• If the method doesn’t actually use all the arguments, the program has wasted resources in evaluating them!
• But we can use streams and lambda expressions to postpone the execution of select arguments, and instantiation.
Lazy instantiation is very useful when the object being created is resource- intensive (in terms of memory).
26
© 2019 Ritwik Banerjee
27
Lazy Instantiation in Java
Lazy class Lazy object loading creation
© 2019 Ritwik Banerjee
• Built into the Java runtime environment (JRE).
• A class is loaded into memory only when they are first
referenced. This can happen in two ways:
// first call to a static method in a class
MyClass.aMethod();
// first instantiation of an object
MyObject o = new MyObject();
• Due to lazy class loading, if a part of a program is never executed during runtime, classes referenced only in that part will never be loaded.
E.g., if the ‘else’ part never actually runs in an if- then-else statement.
Lazy class loading
abstract class MessageBox {
private String message;
protected void setMessage(String s) { message = s; } public abstract void display();
}
class ErrorMessageBox extends MessageBox { public void display() { /* implementation */ }
}
class HelpMessageBox extends MessageBox { … } class StarterMessageBox extends MessageBox { … }
class Frame {
private StarterMessageBox smbox = new StarterMessageBox(); private HelpMessageBox hmbox = new HelpMessageBox(); private ErrorMessageBox embox = new ErrorMessageBox();
private void showError(String err) { embox.setMessage(err); embox.display();
} }
Lazy object creation
• When an instance of Frame is created, all the different types of message boxes are also created.
• This is a recursive process. That is, if those message boxes have other fields that need instantiation, all of that will also happen when you instantiate a new Frame.
• But if, at runtime, we never have to display an error message, i.e., Frame#showError(String) is never
invoked, we are wasting memory.
• This is the kind of situation where we would want lazy instantiation.
Lazy class loading
class LazyFrame {
}
// all three fields are left as null
private StarterMessageBox smbox; private HelpMessageBox hmbox; private ErrorMessageBox embox;
private void showError(String err) {
/* embox is null if and only if this is the first call to
this method */
if (embox == null)
embox = new ErrorMessageBox();
embox.setMessage(err);
embox.display(); }
Lazy object creation
• Streams have two types of operations: intermediate and terminal.
• We can chain a sequence of operations where the last one is a terminal operation, and the preceding are all intermediate operations.
• Intermediate:map()andfilter().
Calls to them return immediately and the lambda
expressions provided to them are not evaluated right away.
• Terminal:reduce().
The behavior of intermediate operations is ‘cached’, and used only when the terminal operation is invoked.
Laziness of Streams
public class LazyStreams {
static String toUpper(final String name) { System.out.println(“to uppercase: ” + name); return name.toUpperCase();
}
public static void main(final String[] args) { List
”brad”, ”kate”, ”kim”, ”jack”, “Joe”, ”mike”, ”susan”, “George”, “Robert”, ”Julia”, ”parker”, ”benson”);
final String aShortName = names.stream()
.filter(n -> n.length() == 3)
.map(LazyStreams::toUpper)
.findFirst().orElse(“N/A”); System.out.println(aShortName);
} }
Evaluation: Read this code from right to left, bottom up. Each step in the call chain will only do enough work to make sure that the terminal operation completes properly.
Laziness of Streams
Image Courtesy: Subramaniam, Venkat. Functional Programming in Java: Harnessing the Power Of Java 8 Lambda Expressions. Pragmatic Bookshelf; 1st Edition (2014). p. 113.
34
Hypothetical eager evaluation
© 2019 Ritwik Banerjee
Image Courtesy: Subramaniam, Venkat. Functional Programming in Java: Harnessing the Power Of Java 8 Lambda Expressions. Pragmatic Bookshelf; 1st Edition (2014). p. 113.
35
Lazy stream evaluation
© 2019 Ritwik Banerjee