CS计算机代考程序代写 ocaml Lambda Calculus chain compiler Java c++ c# Haskell junit COMP 348 Principles of Programming Languages

COMP 348 Principles of Programming Languages

COMP 348
PRINCIPLES OF
PROGRAMMING
LANGUAGES

LECTURE 12 –ADVANCED TOPICS IN JAVA

Fall 2021Dept. of Computer Science and Software Engineering, Concordia University

Advanced Object-Oriented Programming

with Java

Variance, Covariance, and Contravariance

2

Variance refers to how subtyping between more complex types

relates to subtyping between their components.

For instance, given Cat is a subtype of Animal, variance is

referred to how a list of Cats relate to a list of Animals, Or how

should a function that returns Cat relate to a function that returns

Animal.

3

Variance, Covariance, and Contravariance

Within the type system of a programming language, a typing rule

or a type constructor is:

• covariant if it preserves the ordering of types (≤), which orders types from more

specific to more generic; also known as sub-typing

• contravariant if it reverses this ordering;

• bivariant if both of above apply

• variant if covariant, contravariant or bivariant;

• invariant or nonvariant if not variant.

Example:

• covariant: a Cat[] is an Animal[];

• contravariant: an Animal[] is a Cat[];

• invariant: an Animal[] is not a Cat[] and a Cat[] is not an Animal[].

4

Variance, Covariance, and Contravariance

5

Variance, Covariance, and Contravariance

https://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science)

In Java, Arrays are said to be covariant which basically means

that, given the subtyping rules of Java, an array of type T[] may

contain elements of type T or any subtype of T. For instance:

Additionally, the subtyping rules of Java also state that an array

S[] is a subtype of the array T[] if S is a subtype of T.

Now, what if one does the following?

6

Java Arrays are covariant

Number[] numbers = new Number[3];

numbers[0] = new Integer(10);

numbers[1] = new Double(3.14);

Integer[] ia = {1, 2, 3};

Number[] na = ia;

na[0] = 3.14;

What if we try the following?

The Above complies but it causes ArrayStoreException during

runtime. The issue is referred to as the heap pollution.

In the Java programming language, heap pollution is a situation

that arises when a variable of a parameterized type refers to an

object that is not of that parameterized type.

7

Heap Pollution

Integer[] ia = {1, 2, 3};

Number[] na = ia;

na[0] = 3.14;

Consider the following function

The above function may be used to calculate the sum of arrays

of numbers, integers, longs, etc.

8

Covariance and functions

static long sum(Number[] numbers) {

long s = 0;

for(Number number : numbers) {

s += number.longValue();

}

return s;

}

Integer[] myInts = {1,2,3,4,5};

Long[] myLongs = {1L, 2L, 3L, 4L, 5L};

Double[] myDoubles = {1.0, 2.0, 3.0, 4.0, 5.0};

System.out.println(sum(myInts));

System.out.println(sum(myLongs));

System.out.println(sum(myDoubles));

Advanced Object-Oriented Programming

with Java

Wildcards and Generics

9

Java generics use type erasure. Therefore the type information

is not only discarded by the compiler and therefore not available

at run time.

Consider the following example:

Unlike arrays, Java Generics are invariant. For instance, the

following is illegal“:

10

Wildcards and Generics

List myInts = new ArrayList();

myInts.add(1);

myInts.add(2);

List nums = myInts; //compiler error

Consider the following example:

The above function may NOT be used, because generics are not

covariant.

11

Wildcards and Generics

static long sum(List numbers) {

long s = 0;

for(Number number : numbers) {

s += number.longValue();

}

return s;

}

List myInts = Arrays.asList(1,2,3,4,5);

List myLongs = Arrays.asList(1L, 2L, 3L, 4L);

List myDoubles = Arrays.asList(1.0, 2.0, 3.0);

System.out.println(sum(myInts)); // compiler error

System.out.println(sum(myLongs)); // compiler error

System.out.println(sum(myDoubles)); // compiler error

Java wildcards provide a solution to this. Instead of using a type

T as the type argument of a given generic type, we can use a

wildcard declared as ? extends T, where T is a known base type.

The above function may now be used, because of using the

wildcard.

12

Wildcards and Generics

static long sum(List numbers) {

long s = 0;

for(Number number : numbers) {

s += number.longValue();

}

return s;

}

List myInts = Arrays.asList(1,2,3,4,5);

List myLongs = Arrays.asList(1L, 2L, 3L, 4L);

System.out.println(sum(myInts)); // OK

System.out.println(sum(myLongs)); // OK

Using static import, one may rewrite the code as:

This sometimes is very useful if a common static method is

extensively used in a class file.

Note: static imports may not be compared to “include” feature in

other programming languages. In java, it is purely used as a

short cut for coding, and the imported methods are purely called

and are not added to the class at all. Static imports are used to

translate function calls during the compile time. 13

Side Note: Static Imports

import static java.util.Arrays.asList;

.

.

.

List myInts = asList(1,2,3,4,5); // calls Arrays.asList() method

.

.

.

Static import is a feature introduced in the Java 5 that allows

members (fields and methods) which have been scoped within

their container class as public static, to be used in Java code

without specifying the class in which the field has been defined.

When defined in the class

Question: Can we apply this on System.out.println as well?

14

Side Note: Static Imports

import static java.lang.Math.PI;

import static java.lang.Math.pow;

public class HelloWorld {

public static void main(String[] args) {

System.out.println(“Considering a circle with a diameter of 5 cm, it has”);

System.out.println(“a circumference of ” + (PI * 5) + ” cm”);

System.out.println(“and an area of ” + (PI * pow(2.5, 2)) + ” sq. cm”);

}

}

Static imports are heavily used in JUnit.

The @Test above is an annotation class which is discussed at

the end of this chapter.

15

Side Note: Static Imports

import static org.junit.jupiter.api.Assertions.assertEquals;

import org.junit.jupiter.api.Test;

public class MyTests {

@Test

public void myTestProc() {

MyClass tester = new MyClass(); // MyClass is being tested

// assert statement

assertEquals(0, tester.multiply(10, 0), “10 x 0 must be 0”);

}

}

Java supports three types of wildcards:

• The unbounded wildcard type is specified using the wildcard

character (?)

• The upper bounded wildcard type restricts the unknown type

to be a specific type or a subtype of that type and is

represented using the extends keyword:

• A lower bounded wildcard is expressed using the super

keyword, followed by its lower bound:

16

Types of Wildcards

Collection

List

Comparator

With covariance we can read items from a structure, but we

cannot write anything into it.

17

Wildcards and Covariance

List na = new ArrayList();

// List na = new ArrayList();

// List na = new ArrayList();

Number n = na.get(0); // OK

na.add(45L); //compiler error

For contravariance we use a different wildcard called ? super T,

where T is our base type. With contravariance we can do the

opposite. We can put things into a generic structure, but we

cannot read anything out of it.

Contravariance may be used as output parameters.

18

Wildcards and Contravariance

// List na;

Number n = na.get(0); //compiler error

Reading and Writing to generics may be illustrated using the

following example:

19

Covariance and Contravariance in parameters

static void copy(List src,

List dest) {

for(Number n : src) {

dest.add(n);

}

}

List ia = Arrays.asList(1, 2, 3, 4);

List da = Arrays.asList(3.14, 6.28);

List oa = new ArrayList();

copy(ia, oa); // OK

copy(da, oa); // OK

• Wildcard and multiple types:

• Wildcards and multiple extensions (inheritance)

Note the use of & character (as opposed to using , in extending multiple

interfaces).

Question: What does the following mean?

20

More on Wildcards

Pair

List

List

Advanced Object-Oriented Programming

with Java

Java Annotations

21

• In the Java, an annotation is a form of syntactic metadata that

can be added to Java source code.

• Classes, methods, variables, parameters and Java packages

may be annotated.

• Java annotations can be read from source files (i.e.

Javadoc) as well as be embedded in after they are

compiled.

• Therefore annotations can be retained by the Java virtual

machine at run-time and read via reflection.

• Additionally, It is possible to create meta-annotations out of

the existing ones in Java.
22

Java Annotations

• The @ symbol is used to specify annotations.

• Java defines a set of annotations that are built into the

language, examples: @Override, @Deprecated,

@SuppressWarnings, …

• Custom annotations are supported as well.

23

Java Annotations

• Annotations are the meta data that are attached to the

classes, methods, etc. This meta data may be retrieved

during the runtime. The process is referred to as reflection.

• Annotations and their attribute values may be examined

during the runtime which enables us with code injection during

runtime.

• Java Persistence API (JPA) is an example of using

annotations for code injection. Another example is aspect-

oriented programming using spring AOP.

• Annotations may have different names in other languages.

For instance C# supports the very concept by Attributes. The

concept is referred to as attribute programming.
24

Applications of Annotations

• Annotation type declarations are similar to normal interface

declarations. An at-sign (@) precedes the interface keyword.

• Once declared and imported, it can simply be used in other

classes. For instance, the above annotation is used to

annotate a method:

25

Defining Custom Annotations

public @interface MyAnnotation {

}

@MyAnnocation

public void toggle() {

}

• Annotations are the meta data that are attached to the

classes, methods, etc. This meta data may be retrieved

during the runtime. The process is referred to as reflection.

• For example suppose you want to examine if a Subject class

is annotated with an MyAnnotation or not.

• This may be done using the following code sample:

26

Annotations and Reflection

@MyAnnotation

Public class AnnotatedClass {

}

import java.lang.annotation.Annotation;

// import java.lang.reflect.Method;

Class c = AnnotatedClass.class;

if (c.isAnnotationPresent(MyAnnotation.class)) {

Annotation ac = c.getAnnotation(MyAnnotation.class);

MyAnnotation a = (MyAnnotation)ac;

// read values of the attributes of the annotation…

• In the previous example, the target of the annotation was a

class.

• Java annocation framework provides controlling the target of

a custom annotation through some other built in annotations.

27

Annotations and Reflection

@Retention(RetentionPolicy.RUNTIME) // Make this annotation accessible at

// runtime via reflection.

@Target({ElementType.METHOD}) // This annotation can only be applied

// to class methods.

public @interface MyAnnocation {

}

• Annotations may have properties. Consider the following

example:

• In the above example, a local variable book is annotated with

@Author with specific first and last time. The above properties

are defined using interface methods:

28

Annotations Properties

@Author(first = “John”, last = “Doe”)

Book book = new Book();

public @interface Author {

String first();

String last();

}

Advanced Topics in Java

Lambda Expressions and Functional

Interfaces

29

• A class with Single Abstract Method is called SAM.

• A functional interface is an interface with single abstract

method.

• An interface with more than one abstract method is not a

functional interface unless all other methods have default

implementation.

• Functional Interfaces essentially simulate a callbacks, a

mechanism that does not exist in java. This is however

supported differently in other languages (see delegates in

C#).

30

Functional Interfaces and SAMs

public interface MyInterface {

void printIt(String text);

}

• The following interface is indeed a valid functional interface:

31

Example

public interface MyInterface {

void printIt(String text);

default public void printUtf8To(String text,

OutputStream outputStream){

try {

outputStream.write(text.getBytes(“UTF-8”));

} catch (IOException e) {

throw new RuntimeException(

“Error writing String as UTF-8 to OutputStream”,

e);

}

}

static void printItToSystemOut(String text){

System.out.println(text);

}

}

• The lambda calculus was introduced in the 1930s by Alonzo

Church as a mathematical system for defining computable

functions.

• The lambda calculus serves as the computational model

underlying functional programming languages such as Lisp,

Haskell, and Ocaml.

• Lambda expressions have been incorporated into many

widely used programming languages like C++ and now very

recently Java 8.

32

Lambda Calculus

• In computer programming, an anonymous function (function

literal, lambda abstraction, or lambda expression) is a function

definition that is not bound to an identifier.

• A Java 8 lambda is basically a method in Java without a

declaration usually written as

(parameters) -> { body }

• Examples of lambda expressions are given in the following:

33

What is a Lambda Expression?

x -> x * x // a lambda with one parameter

// typed parameters with code block

(int x, int y) -> { return x + y; }

() -> x // a lambda with no parameter but returning a value

• Lamda Expressions are an alternative way of creating

anonymous classes.

• Given a functional interface or a SAM base class, a lamda

expression may simply replace the anonymous class.

• Suppose we want to implement the following interface:

34

Lambda Expressions and Anonymous Classes

public interface MyEventConsumer {

public void consume(Object event);

}

• Using anonymous classes, we may write:

• The above example may be simply written using lambda

expression:

• The above lambda may even be more simplified as:

Note that the type inference is automatically done at the compile type.

35

Lambda Expressions and Anonymous Classes

MyEventConsumer consumer = new MyEventConsumer() {

public void consume(Object event){

System.out.println(event.toString() + ” consumed”);

}

};

MyEventConsumer consumer = (Object e) -> {

System.out.println(e.toString() + ” consumed”); };

MyEventConsumer consumer =

e -> System.out.println(e.toString() + ” consumed”);

• Returning values:

36

Examples of Lambda Expressions

(param) -> {

System.out.println(“param: ” + param);

return “return value”; }

(a1, a2) -> { return a1 > a2; } // is greater than?

(a1, a2) -> a1 > a2 // is greater than (simplified version)

• Lambda expressions are replacements for anonymous classes that

implement functional interfaces or SAMs.

• They are indeed anonymous types and are complied to one.

• As a result, Objects of the related types may hold a reference to

lambdas.

Example:

37

Lambdas are Objects

public interface MyComparator {

public boolean isgreaterthan(int a1, int a2);

}

MyComparator myComparator = (a1, a2) -> return a1 > a2;

boolean result = myComparator.isgreaterthan(2, 5);

• Similar to anonymous and local classes, local variables may also be

captured by lambda expressions:

• However, only immutable or final objects are allowed.

38

Lambdas and Variable Capture

String myString = “Test”; // immutable

MyFactory myFactory = (chars) -> {

return myString + “:” + new String(chars); };

// the following causes compiler error since Object a is not final.

/* final */ ClassA a = new ClassA();

MyLambda l = () -> “Capturing: ” + a.toString();

Advanced Object-Oriented Programming

with Java

Java Stream API

39

• Stream represents a sequence of objects from a source,

which supports aggregate operations.

• Stream processing is a computer programming paradigm,

equivalent to dataflow programming, event stream

processing, and reactive programming, that allows some

applications to more easily exploit a limited form of parallel

processing.

• Most programming languages, such as Java or C++, provide

supports for stream processing. This is not to be confused

with I/O Streams.

40

Stream Processing

• Java Stream API released as of Java 8, provides such a

support.

• The idea of Java Stream API was based on the

implementation of Microsoft .Net enumerable queries that had

been used in Microsoft Language Integrated Query (LINQ).

• Java Stream API is defined in java.util.stream package.

• The stream package defines classes and interfaces to support

functional-style operations on streams of elements, such as

map-reduce transformations on collections.

41

Java Stream API

• Stream API using functional programming and provides sets

of methods that receive functional interfaces as parameters.

• Any iterable class may simply be transformed into a stream

object which inherently supports the above methods.

• Most iterable classes, however, may directly be used as

streams.

42

Java Stream API

• Deferred execution means that the evaluation of an

expression is delayed until its realized value is actually

required. Deferred execution can greatly improve

performance when you have to manipulate large data

collections, especially in programs that contain a series of

chained queries or manipulations.

• In lazy evaluation, a single element of the source collection is

processed during each call to the iterator. This is the typical

way in which iterators are implemented.

• In eager evaluation, the first call to the iterator will result in

the entire collection being processed. For example, applying

an order-by operation has to sort the entire collection before

returning the first element.

43

Deferred Execution and Lazy Evaluation

• Both Java Stream Processing and C# LINQ provide support

for parallel stream processing.

• This is extremely useful in processing big pipelines of data

which may be executed over multiple cores.

44

Parallelism

• Constructing streams:

– done via a call to stream() or parallelStream() methods.

• forEach():

– Iterates through every element of the stream

• map():

– used to map each element to a desired result

• filter():

– to filter data based on selection criteria (similar to a where clause)

• limit():

– To limit the resulting data to certain numbers (similar to a top clause)

• sorted():

– Used to sort the data in the stream (similar to order by)

• Collectors:

– done via a call to collect() or groupingBy(), … (similar to group by)

• Statistics:

– builtin class to provide statistics (such as max, min, sum, average, …)
45

Stream Operations

• Below is an example of using forEach() method:

• The lambda expression x -> System.out.println(x) defines an

anonymous class with one parameter named x of type Integer

and no return.

• Output:

46

Using the forEach() method

List intSeq = Arrays.asList(1, 2, 3);

intSeq.forEach(x -> System.out.println(x));

1

2

3

• Another example using forEach() method:

• Note that braces are needed to enclose a multiline body in a

lambda expression.

• Output:

47

Using the forEach() method

List intSeq = Arrays.asList(1, 2, 3);

intSeq.forEach(x -> {

x += 2;

System.out.println(x);

});

3

4

5

• Another example using forEach() method:

• Just as with ordinary functions, you can define local variables

inside the body of a lambda expression

• Output:

48

Using the forEach() method

List intSeq = Arrays.asList(1, 2, 3);

intSeq.forEach(x -> {

int y = x * 2;

System.out.println(y);

});

2

4

6

• Defining explicit types in lambda often prevents unintended

errors.

• Output:

49

Using the forEach() method

List intSeq = Arrays.asList(1, 2, 3);

intSeq.forEach((Integer x -> {

x += 2;

System.out.println(x);

});

3

4

5

• Method reference may be compared to the notion of a pointer

to function (i.e. a callback, or a delegate in C#).

• Although the notion a function pointer does not exist in java,

the concept is somehow supported through functional

interfaces.

• As such, java 8 provides using method references, which in

turn is translated into a lambda equivalent.

• Method reference are represented using scope resolution

operation (::), a notation borrowed from the C++ language.

50

Method references

• Method references can be used to pass an existing function in

places where a lambda is expected

• The signature of the referenced method needs to match the

signature of the functional interface method

• The following table summarizes the different types of method

references.

51

Method references

Method Reference

Type

Syntax Example

static ClassName::StaticMethodName String::valueOf

constructor ClassName::new ArrayList::new

specific object instance objectReference::MethodName x::toString

arbitrary object of a

given type

ClassName::InstanceMethodName Object::toString

• Consider the following lambda expression:

• The above lambda expression may be rewritten more

concisely using a method reference as:

52

Method reference example

intSeq.forEach(x -> System.out.println(x));

intSeq.forEach(System.out::println);

• Method chaining is a common syntax for invoking multiple

method calls in object-oriented programming languages.

• Each method returns an object, allowing the calls to be

chained together in a single statement without requiring

variables to store the intermediate results.

• An example is given below:

• The above is an example of filter and map operations.

• Since almost all methods in Stream API return a stream

object, the methods may be chained together.

• A counter example to the above is the use of forEach()

method which has a void return type and therefore cannot not

be further used in methods chaining .
53

Chaining methods

int sum = widgets.stream()

.filter(w -> w.getColor() == RED)

.mapToInt(w -> w.getWeight())

.sum();

• A map-reduce program is composed of

– a map procedure, which performs filtering and sorting (such as

sorting students by first name into queues, one queue for each name),

– and a reduce method, which performs a summary operation (such as

counting the number of students in each queue, yielding name

frequencies).

• Map-reduce programming is extensively used in big-data

processing.

• Below is a simple example of a map reduce implementation:

54

Building a map-reduce

double avgsal =

employees.stream().mapToDouble(e -> e.getSalary()).

average().getAsDouble();

• Below is an example of using map reduce to count the

number of occurrence per item.

• Output:

55

A group-by example

List numbers = Arrays.asList(1, 2, 1, 2, 3, 1);

Map result =

numbers.stream().collect(

Collectors.groupingBy(

Function.identity(), Collectors.counting()));

result.entrySet().stream()

.sorted(

Map.Entry.comparingByValue().reversed())

.forEachOrdered(

e -> System.out.println(

“Number ” + e.getKey() + ” occurred ” +

e.getValue() + ” times”));

Number 1 occurred 3 times

Number 2 occurred 2 times

Number 3 occurred 1 times

• numbers.stream() constructs a stream that is ready to be

processed.

• The collect() method receives a group by method reference. A

built-in group by method is used: Collectors.groupingBy()

• The Collectors.groupingBy() method requires two lambda

arguments.

56

A group-by example explained

Map result =

numbers.stream().collect(

Collectors.groupingBy(

Function.identity(), Collectors.counting()));

• The first argument of the groupingBy collector is a map

function:

– identity function in this example, i.e. x -> x

• The second argument of the groupingBy collector is a reduce

function:

– Count function, an aggregate function specified as

That received has three generic types:

• the type of input elements (T),

• the mutable accumulation type of the reduction operation (?),

• and The result type of the reduction operation (Long)
57

A group-by example explained

Collectors.groupingBy(Function.identity(), Collectors.counting()));

public static Collector counting()

• The output result is further processed by sorting out the key-

value pairs of the resulting map.

• The sorting is performed by calling the sorted() method, which

receives a Comparator.

58

A group-by example explained

result.entrySet().stream()

.sorted(

Map.Entry.comparingByValue().reversed())

.forEachOrdered(

e -> System.out.println(

“Number ” + e.getKey() + ” occurred ” +

e.getValue() + ” times”));

• This code uses a builtin comparator that is provided by

comparingByValue() method from the Map.Entry generic

class.

• The result is then reversed in order to maintain the

ascending order.

• And finally each item is printed out by using forEachOrdered()

method.

59

A group-by example explained

result.entrySet().stream()

.sorted(

Map.Entry.comparingByValue().reversed())

.forEachOrdered(

e -> System.out.println(

“Number ” + e.getKey() + ” occurred ” +

e.getValue() + ” times”));

• The use of forEachOrdered() is preferred over forEach() as it

guarantees the order, especially in parallel processing.

60

forEach vs. forEachOrdered

result.entrySet().stream()

.sorted(

Map.Entry.comparingByValue().reversed())

.forEachOrdered(

e -> System.out.println(

“Number ” + e.getKey() + ” occurred ” +

e.getValue() + ” times”));

• https://dzone.com/articles/covariance-and-contravariance

• https://docs.oracle.com/javase/tutorial/java/generics/wildcards.html

• https://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science)

• http://tutorials.jenkov.com/java/lambda-expressions.html

• https://en.wikipedia.org/wiki/Java_annotation

• https://docs.oracle.com/javase/6/docs/technotes/guides/language/annotations.html

• https://www.baeldung.com/java-8-streams

• https://stackify.com/streams-guide-java-8/

• https://www.tutorialspoint.com/java8/java8_streams.htm

• https://en.wikipedia.org/wiki/Method_chaining

• https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html

61

Acknowledgements

https://dzone.com/articles/covariance-and-contravariance
https://dzone.com/articles/covariance-and-contravariance
https://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science)
http://tutorials.jenkov.com/java/lambda-expressions.html
https://en.wikipedia.org/wiki/Java_annotation
https://docs.oracle.com/javase/6/docs/technotes/guides/language/annotations.html
https://www.baeldung.com/java-8-streams

A Guide to Java Streams in Java 8: In-Depth Tutorial With Examples


https://www.tutorialspoint.com/java8/java8_streams.htm
https://en.wikipedia.org/wiki/Method_chaining
https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html