Functional Java

Functional Java
> Click or hit Control-Enter to run Example.main above

This semester we’ve introduced you to three different programming styles using Java:

Imperative programming: using a series of statements to show the computer how to solve a problem
Object-oriented programming: using objects to combine program state (data) and behavior (algorithms)
Recursive programming: solving problems by breaking them into smaller pieces

But there’s a lot more to learn about both computer science and programming

Most working programmers know multiple different languages
Frequently those multiple languages will enable programming in multiple environments and in different styles
Solving a problem then starts by choosing the right language
Many of today’s languages (Java, Python, JavaScript, C++) also support multiple programming styles or paradigms
You can find lots of advice online about which to use

The following argument is a reprise of part of an article by Paul Graham, famous Silicon Valley entrepreneur.

Programming styles vary in power
In general you want to choose the most powerful style available
(There are many exceptions to this rule. Sometimes your choice is constrained by what you want to do, or by needing to use a particular library or language.)
Programmers typically find less-powerful styles familiar but limited
Programmers typically find more-powerful styles unfamiliar and bewildering

As long as our hypothetical programmer is looking down the power continuum, she knows she’s looking down. Styles less powerful than the one she uses are obviously less powerful, because they’re missing some feature she’s used to. But when our hypothetical programmer looks in the other direction, up the power continuum, she doesn’t realize she’s looking up. What she sees are merely weird styles. She probably considers them about equivalent in power to what she’s used to, but with all this other hairy stuff thrown in as well. How she programs is good enough for her, because it’s how she thinks.

(Paraphrased from this article.)

— Paraphrased from Paul Graham

Let’s think about how we arrived at today:

Purely imperative: you can solve every problem by just writing one class, but you wouldn’t want to because you’d rather…
Object-oriented: …use objects to combine state and behavior and allow you to model real-world entities. Like trees, which you could walk iteratively except…
Recursive: …that recursion provides a much cleaner and more powerful way to program using trees.
For many of you one or several of these concepts was new and unfamiliar at first, but then became more natural with practice

Let’s imagine we have a group of dogs with ages and birthdays stored in a Dog class.

Say we want to write a function that, given a list of Dog objects, finds ones matching some criteria.

> Click or hit Control-Enter to run Example.main above

Writing imperative code forces you to tell the computer exactly how to do everything:

List<Dog> birthdayDogs = new ArrayList<>();
for (Dog dog : dogs) {
  if (dog.getBirthday() == today) {
    birthdayDogs.add(dog);
  }
}

Writing declarative code allows you to tell the computer what you want and let it figure out how to accomplish it:

// Give me only the items in dogs where dog.getBirthday() == today
// How do we do that?

List<Dog> filterDogs(List<Dog> dogs, // filter specification...?) {
  List<Dog> filteredDogs = new ArrayList<>();
  for (Dog dog : dogs) {
    // if dog should be in the list, add it
  }
  return filteredDogs;
}

We need to pass something to filterDogs that allows the caller to specify which dogs should be included in as general a way as possible.

Many programming languages support so-called first class functions, meaning that functions can be stored as variables and passed to other functions:

function filterDogs(dogs, filter) {
  filteredDogs = []
  for (dog of dogs) {
    if (filter(dog)) {
      filteredDogs.push(dog)
    }
  }
  return filteredDogs;
}
const filteredDogs = filterDogs(dogs, dog => { return dog.age > 10 })

But why am I showing you JavaScript code above, rather than Java code?
Because Java doesn’t support first-class functions. Doh!

List<Dog> filterDogs(List<Dog> dogs, // filter specification...?) {
  List<Dog> filteredDogs = new ArrayList<>();
  for (Dog dog : dogs) {
    // if dog should be in the list, add it
  }
  return filteredDogs;
}

filterDogs needs guarantees about what it can do with it’s second argument…
…but the goal is still to provide a flexible filtering function.
We’ve seen something like this before.

interface DogFilter {
  boolean include(Dog dog);
}
List<Dog> filterDogs(List<Dog> dogs, DogFilter dogFilter) {
  List<Dog> filteredDogs = new ArrayList<>();
  for (Dog dog : dogs) {
    if (dogFilter.include(dog)) {
      filteredDogs.add(dog);
    }
  }
  return filteredDogs;
}

filterDogs knows that it can call include on dogFilter and get a boolean
But the caller can implement dogFilter any way it wants!

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class Dog {
  private int age;
  private int birthday;
  private String name;
  Dog(int setAge, int setBirthday, String setName) {
    age = setAge;
    birthday = setBirthday;
    name = setName;
  }
  void incrementAge() {
    age++;
  }
  public int getAge() {
    return age;
  }
  public int getBirthday() {
    return birthday;
  }
  public String getName() {
    return name;
  }
  public String toString() {
    return name;
  }
}
interface DogFilter {
  boolean include(Dog dog);
}
public class Example {
  public static List<Dog> filterDogs(List<Dog> dogs, DogFilter dogFilter) {
    List<Dog> filteredDogs = new ArrayList<>();
    for (Dog dog : dogs) {
      if (dogFilter.include(dog)) {
        filteredDogs.add(dog);
      }
    }
    return filteredDogs;
  }
  public static void main(String[] unused) {
    List<Dog> dogs = new ArrayList<>(Arrays.asList(new Dog[] {
      new Dog(14, 100, "Chuchu"),
      new Dog(15, 88, "Balou"),
      new Dog(3, 88, "Lulu")
    }));
    int today = 100;
  }
}

> Click or hit Control-Enter to run Example.main above

We can make this a bit cleaner with the help of some new Java syntax: anonymous classes.

public interface DogFilter {
  boolean include(Dog dog);
}
// Use new on the interface type...
DogFilter birthdayFilter = new DogFilter() {
  // And immediately provide an implementation
  public boolean include(Dog dog) {
    return dog.getBirthday() == 100;
  }
}

That implementation of DogFilter is now stored in reference variable birthdayFilter
But otherwise has no name, hence it being an anonymous class
Anonymous classes are convenient when you only use a class once

Anonymous classes can also be used to extend an existing class and override its methods.

public class Dog {
  String toString() {
    return "Dog";
  }
}
Dog sweetOldDog = new Dog() {
  String toString() {
    return "SweetOldDog";
  }
}

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class Dog {
  private int age;
  private int birthday;
  private String name;
  Dog(int setAge, int setBirthday, String setName) {
    age = setAge;
    birthday = setBirthday;
    name = setName;
  }
  void incrementAge() {
    age++;
  }
  public int getAge() {
    return age;
  }
  public int getBirthday() {
    return birthday;
  }
  public String getName() {
    return name;
  }
  public String toString() {
    return name;
  }
}
interface DogFilter {
  boolean include(Dog dog);
}
public class Example {
  public static List<Dog> filterDogs(List<Dog> dogs, DogFilter dogFilter) {
    List<Dog> filteredDogs = new ArrayList<>();
    for (Dog dog : dogs) {
      if (dogFilter.include(dog)) {
        filteredDogs.add(dog);
      }
    }
    return filteredDogs;
  }
  public static void main(String[] unused) {
    List<Dog> dogs = new ArrayList<>(Arrays.asList(new Dog[] {
      new Dog(14, 100, "Chuchu"),
      new Dog(15, 88, "Balou"),
      new Dog(3, 88, "Lulu")
    }));
    int today = 100;
  }
}

> Click or hit Control-Enter to run Example.main above

We can make this even cleaner yet with the help of some new Java syntax: lambda expressions.

public interface DogFilter {
  boolean include(Dog dog);
}
DogFilter birthdayFilter = new DogFilter() {
  public boolean include(Dog dog) {
    return dog.getBirthday() == 100;
  }
}
// Is the same as
DogFilter birthdayFilter = (dog) -> { return dog.getBirthday() == 100; };
// Or, even cleaner
DogFilter birthdayFilter = (dog) -> dog.getBirthday() == 100;

An anonymous function (function literal, lambda abstraction, or lambda expression) is a function definition that is not bound to an identifier. Anonymous functions are often arguments being passed to higher-order functions, or used for constructing the result of a higher-order function that needs to return a function.

The name lambda comes from the work of Alonzo Church on the λ-calculus: a formal system for expression computation mathematically
Many programming languages have lambda functions. (Python actually uses the lambda keyword to declare one.)

public interface DogFilter {
  boolean include(Dog dog);
}
DogFilter birthdayFilter = (dog) -> dog.getBirthday() == 100;

So while Java does not have first-class functions, but we can approximate them using:

Functional interfaces: interfaces that only require implementing a single method
Lambda expressions: by using the arrow syntax we can cleanly provide an anonymous class that implements the single function of a functional interface

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class Dog {
  private int age;
  private int birthday;
  private String name;
  Dog(int setAge, int setBirthday, String setName) {
    age = setAge;
    birthday = setBirthday;
    name = setName;
  }
  void incrementAge() {
    age++;
  }
  public int getAge() {
    return age;
  }
  public int getBirthday() {
    return birthday;
  }
  public String getName() {
    return name;
  }
  public String toString() {
    return name;
  }
}
interface DogFilter {
  boolean include(Dog dog);
}
public class Example {
  public static List<Dog> filterDogs(List<Dog> dogs, DogFilter dogFilter) {
    List<Dog> filteredDogs = new ArrayList<>();
    for (Dog dog : dogs) {
      if (dogFilter.include(dog)) {
        filteredDogs.add(dog);
      }
    }
    return filteredDogs;
  }
  public static void main(String[] unused) {
    List<Dog> dogs = new ArrayList<>(Arrays.asList(new Dog[] {
      new Dog(14, 100, "Chuchu"),
      new Dog(15, 88, "Balou"),
      new Dog(3, 88, "Lulu")
    }));
    System.out.println(filterDogs(dogs, (dog) -> dog.getBirthday() == 100));
  }
}

> Click or hit Control-Enter to run Example.main above

public static List<Dog> filterDogs(List<Dog> dogs, DogFilter dogFilter) {
  List<Dog> filteredDogs = new ArrayList<>();
  for (Dog dog : dogs) {
    if (dogFilter.include(dog)) {
      filteredDogs.add(dog);
    }
  }
  return filteredDogs;
}

A higher-order function is a function that operates on or uses another function
filterDogs above is really a higher-order function, since DogFilter is a functional interface

When operating on collections of items (like lists) certain higher-order operations are common:

filter: retain only items that pass some test
map: apply some transformation to each item that produces a new list
forEach: perform some operation for each item that does not produce a new list

interface DogFilter {
  boolean include(Dog dog);
}

Do we really need to provide a special filter interface just for Dogs?

public static List<Dog> filterDogs(List<Dog> dogs, DogFilter dogFilter) {
  List<Dog> filteredDogs = new ArrayList<>();
  for (Dog dog : dogs) {
    if (dogFilter.include(dog)) {
      filteredDogs.add(dog);
    }
  }
  return filteredDogs;
}

And do we really need a Dog-specific filter function?

> Click or hit Control-Enter to run Example.main above

What we’ve been doing today is exploring Java’s support for functional programming.

As a style, functional programming emphasizes:

Solving problems by composing functions rather than writing loops
Which leads to declarative rather than imperative code
Reusable higher-order functions like removeIf, map, and filter

While Java supports some aspects of functional programming, it’s a worse fit for others:

Pure functions and immutable data fly in the face of object-oriented programming
So if you want to really learn functional programming, learn a more strict functional language like Haskell or OCaml

Java streams allow us to compactly represent a series of operations on a collection as a sequence of functional transformations:

dogs.stream()
  .filter(dog -> dog.getAge() <= 10)
  .map(dog -> dog.getName())
  .map(String::toUpperCase)
  .sorted()
  .forEach(System.out::println);

(There are a few other new ideas in this example, including function references. Use the internet to find out more!)

> Click or hit Control-Enter to run Example.main above

Writing declarative code allows you to tell the computer what you want and let it figure out how to accomplish it:

// Give me only the items in dogs where dog.getBirthday() == today
.filter(dog -> dog.getBirthday() == today)

Go forth and have fun, but always remember: if something seems confusing, it might actually be more powerful. So don’t get scared off!

Thursday AM: you’ll receive an email telling you what room to demo in.
4:45PM: setup throughout Siebel.
5–7:45PM: demos and judging.
8PM: awards and wrap-up in Foellinger. (Yes, you have to walk. No, it’s not far.)

CS 125 by numbers. (Anyone want to guess how many times you looked at the slides this semester?)
ICES forms: these matter and we take your feedback extremely serious. Please come.

Please double-check your grades this week to make sure they look correct.
My office hours continue today from 10AM–12PM in Siebel 2227. Please stop by! It’s not too late. I’d still love to meet you if we haven’t already.
We’re grading your final project in lab this week and selecting the best to feature in this week’s final project fair.

Programming Styles

Beyond Java

Powerful Programming

Looking Up

Our Progression

But There’s More Ahead—Or Above

Motivating Example

Imperative Programming

Declarative Programming

Dog Filtering

First-Class Functions

Let’s Regroup

Interfaces to the Rescue

Anonymous Classes

Anonymous Classes: Extension

And Cleaner Still With Lambda Expressions

Lambda Functions

First-Class Functions in Java

Higher-Order Functions

Common Higher-Order Functions

Additional Generality

Even More Generality

Java Collection `removeIf`

Functional Programming

Functional Java

Java Streams

Declarative Programming

There Is Always More

Questions About Functional Java?

Final Project Fair Details

Wednesday

Announcements

Programming Styles

Beyond Java

Powerful Programming

Looking Up

Our Progression

But There’s More Ahead—Or Above

Motivating Example

Imperative Programming

Declarative Programming

Dog Filtering

First-Class Functions

Let’s Regroup

Interfaces to the Rescue

Anonymous Classes

Anonymous Classes: Extension

And Cleaner Still With Lambda Expressions

Lambda Functions

First-Class Functions in Java

Higher-Order Functions

Common Higher-Order Functions

Additional Generality

Even More Generality

Java Collection removeIf

Functional Programming

Functional Java

Java Streams

Declarative Programming

There Is Always More

Questions About Functional Java?

Final Project Fair Details

Wednesday

Announcements

Java Collection `removeIf`