Laziness, trampolines, monoids and other functional amenities: this is not your father's Java

Lambdas are the main feature introduced with Java 8, but the biggest part of Java developers are still not very familliar with the most common functional idioms and patterns. The purpose of this talk is presenting with practical examples concepts like high-order functions, currying, functions composition, persistent data structures, lazy evaluation, recursion, trampolines and monoids showing how to implement them in Java and how thinking functionally can help us to design and develop more readable, reusable, performant, parallelizable and in a word better, code.

Transcript

1. trampolines, monoids & other functional amenities This is NOT your father's by Mario Fusco mario.fusco@gmail.com twitter: @mariofusco Laziness,
2. public static <T> void sort(List<T> list, Comparator<? super T> c) Essence of Functional Programming Data and behaviors are the same thing! Data Behaviors Collections.sort(persons, (p1, p2) -> p1.getAge() – p2.getAge())
3. Higher-order functions Are they so mind-blowing?
4. Higher-order functions Are they so mind-blowing? … but one of the most influent sw engineering book is almost completely dedicated to them
5. Command Template Method Functions are more general and higher level abstractions Factory Strategy
6. public interface Converter { double convert(double value); } public class AbstractConverter implements Converter { public double convert(double value) { return value * getConversionRate(); } public abstract double getConversionRate(); } public class Mi2KmConverter extends AbstractConverter { public double getConversionRate() { return 1.609; } } public class Ou2GrConverter extends AbstractConverter { public double getConversionRate() { return 28.345; } } A strategy pattern Converter
7. public List<Double> convertValues(List<Double> values, Converter converter) { List<Double> convertedValues = new ArrayList<Double>(); for (double value : values) { convertedValues.add(converter.convert(value)); } return convertedValues; } List<Double> values = Arrays.asList(10, 20, 50); List<Double> convertedDistances = convertValues(values, new Mi2KmConverter()); List<Double> convertedWeights = convertValues(values, new Ou2GrConverter()); Using the Converter
8. A functional Converter public class Converter implements ExtendedBiFunction<Double, Double, Double> { @Override public Double apply(Double conversionRate, Double value) { return conversionRate * value; } } @FunctionalInterface public interface ExtendedBiFunction<T, U, R> extends BiFunction<T, U, R> { default Function<U, R> curry1(T t) { return u -> apply(t, u); } default Function<T, R> curry2(U u) { return t -> apply(t, u); } }
9. Currying Converter converter = new Converter(); double tenMilesInKm = converter.apply(1.609, 10.0); Function<Double, Double> mi2kmConverter = converter.curry1(1.609); double tenMilesInKm = mi2kmConverter.apply(10.0); Converter value rate result Mi2km Converter value rate=1.609 result curry1 List<Double> values = Stream.of(10, 20, 50) .map(new Converter().curry1(1.609)) .collect(toList())
10. Function Composition Celsius  Fahrenheit : F = C * 9/5 + 32 Converter value rate=9/5
11. Function Composition Celsius  Fahrenheit : F = C * 9/5 + 32 Converter value rate=9/5 andThen n -> n+32 result
12. Function Composition Celsius  Fahrenheit : F = C * 9/5 + 32 Converter value rate=9/5 andThen n -> n+32 result Celsius2FarenheitConverter Function<Double, Double> c2fConverter = new Converter().curry1(9.0/5) .andThen(n -> n + 32);
13. More Function Composition @FunctionalInterface public interface ExtendedBiFunction<T, U, R> extends BiFunction<T, U, R> { default <V> ExtendedBiFunction<V, U, R> compose1(Function<? super V, ? extends T> before) { return (v, u) -> apply(before.apply(v), u); } default <V> ExtendedBiFunction<T, V, R> compose2(Function<? super V, ? extends U> before) { return (t, v) -> apply(t, before.apply(v)); } } default <V> Function<V, R> compose(Function<? super V, ? extends T> before) { return (V v) -> apply(before.apply(v)); }
14. More Function Composition Fahrenheit  Celsius : C = (F - 32) * 5/9 Converter rate=5/9 result
15. More Function Composition Fahrenheit  Celsius : C = (F - 32) * 5/9 Converter rate=5/9 value n -> n-32 result compose2
16. More Function Composition Fahrenheit  Celsius : C = (F - 32) * 5/9 Converter rate=5/9 value n -> n-32 result Farenheit2CelsiusConverter Function<Double, Double> f2cConverter = new Converter().compose2((Double n) -> n - 32) .curry1(5.0/9); Functions are building blocks to create other functions compose2
17. Monoids A monoid is a triple (T, , ∗ z) such that ∗ is an associative binary operation on T, and z ∈ T has the property that for all x ∈ T it holds that x∗z = z∗x = x. interface Monoid<T> { T append(T a, T b); T zero(); } class Appender implements Monoid<String> { public String append(String a, String b) { return a + b; } public String zero() { return ""; } } class Multiplier implements Monoid<Integer> { public Integer append(Integer a, Integer b) { return a * b; } public Integer zero() { return 1; } }
18. Endomorphisms & Monoids interface Endomorphism<A> extends Function<A, A> { } interface EndoMonoid<A> extends Monoid<Endomorphism<A>> { @Override default Endomorphism<A> append(Endomorphism<A> f1, Endomorphism<A> f2) { return ??? } @Override default Endomorphism<A> zero() { return ??? } }
19. Endomorphisms & Monoids interface Endomorphism<A> extends Function<A, A> { } interface EndoMonoid<A> extends Monoid<Endomorphism<A>> { @Override default Endomorphism<A> append(Endomorphism<A> f1, Endomorphism<A> f2) { return ??? } @Override default Endomorphism<A> zero() { return ??? } } f1.andThen(f2); Function.identity();
20. public class SalaryCalculator { // B = basic + 20% public double plusAllowance(double d) { return d * 1.2; } // C = B + 10% public double plusBonus(double d) { return d * 1.1; } // D = C - 30% public double plusTax(double d) { return d * 0.7; } // E = D - 10% public double plusSurcharge(double d) { return d * 0.9; } public double calculate(double basic, boolean[] flags) { double salary = basic; if (flags[0]) salary = plusAllowance(salary); if (flags[1]) salary = plusBonus(salary); if (flags[2]) salary = plusTax(salary); if (flags[3]) salary = plusSurcharge(salary); return salary; } } SalaryCalculator
21. public class FluentEndoMonoid<A> implements EndoMonoid<A> { private final Endomorphism<A> endo; public FluentEndoMonoid(Endomorphism<A> endo) { this.endo = endo; } public FluentEndoMonoid(Endomorphism<A> endo, boolean b) { this.endo = b ? endo : zero(); } public FluentEndoMonoid<A> add(Endomorphism<A> other) { return new FluentEndoMonoid<A>(append(endo, other)); } public FluentEndoMonoid<A> add(Endomorphism<A> other, boolean b) { return add(b ? other : zero()); } public Endomorphism<A> get() { return endo; } public static <A> FluentEndoMonoid<A> endo(Endomorphism<A> f, boolean b) { return new FluentEndoMonoid<A>(f, b); } } FluentEndoMonoid
22. public class SalaryCalculator { public double calculate(double basic, boolean [] flags) { return getCalculator(bs).apply(basic); } public Endomorphism<Double> getCalculator(boolean[] flags) { return endo(this::plusAllowance, flags[0]) .add(this::plusBonus, flags[1]) .add(this::plusTax, flags[2]) .add(this::plusSurcharge, flags[3]) .get(); } } Endomorphism<Double> f = salaryCalc.getCalculator(true, false, false, true); double aliceNet = f.apply(alice.getIncome()); double brianNet = f.apply(brian.getIncome()); Functional SalaryCalculator You can calculate a single salary … … but also obtain a calculator for a given combination of flags (Factory)
23. Lazy Evaluation Lazy evaluation (or call-by-name) is an evaluation strategy which delays the evaluation of an expression until its value is needed I know what to do. Wake me up when you really need it
24. Creating a Stream of prime numbers public static IntStream primes(int n) { return IntStream.iterate(2, i -> i + 1) .filter(n –> isPrime(n)) .limit(n); } public static boolean isPrime(int candidate) { int candidateRoot = (int) Math.sqrt((double) candidate); return IntStream.rangeClosed(2, candidateRoot) .noneMatch(i -> candidate % i == 0); }
25. Creating a Stream of prime numbers public static IntStream primes(int n) { return IntStream.iterate(2, i -> i + 1) .filter(n –> isPrime(n)) .limit(n); } public static boolean isPrime(int candidate) { int candidateRoot = (int) Math.sqrt((double) candidate); return IntStream.rangeClosed(2, candidateRoot) .noneMatch(i -> candidate % i == 0); } It iterates through every number every time to see if it can be exactly divided by a candidate number, but it would be enough to only test numbers that have been already classified as prime Inefficient
26. Recursively creating a Stream of primes static Intstream numbers() { return IntStream.iterate(2, n -> n + 1); } static int head(IntStream numbers) { return numbers.findFirst().getAsInt(); } static IntStream tail(IntStream numbers) { return numbers.skip(1); } static IntStream primes(IntStream numbers) { int head = head(numbers); return IntStream.concat( IntStream.of(head), primes(tail(numbers).filter(n -> n % head != 0)) ); }
27. Recursively creating a Stream of primes static Intstream numbers() { return IntStream.iterate(2, n -> n + 1); } static int head(IntStream numbers) { return numbers.findFirst().getAsInt(); } static IntStream tail(IntStream numbers) { return numbers.skip(1); } static IntStream primes(IntStream numbers) { int head = head(numbers); return IntStream.concat( IntStream.of(head), primes(tail(numbers).filter(n -> n % head != 0)) ); } Cannot invoke 2 terminal operations on the same Streams Problems? No lazy evaluation in Java leads to an endless recursion
28. Lazy evaluation in Scala def numbers(n: Int): Stream[Int] = n #:: numbers(n+1) def primes(numbers: Stream[Int]): Stream[Int] = numbers.head #:: primes(numbers.tail filter (n -> n % numbers.head != 0)) lazy concatenation In Scala the #:: method (lazy concatenation) returns immediately and the elements are evaluated only when needed
29. interface HeadTailList<T> { T head(); LazyList<T> tail(); default boolean isEmpty() { return true; } } Implementing a lazy list in Java class LazyList<T> implements HeadTailList<T> { private final T head; private final Supplier<MyList<T>> tail; public LazyList(T head, Supplier<HeadTailList<T>> tail) { this.head = head; this.tail = tail; } public T head() { return head; } public HeadTailList<T> tail() { return tail.get(); } public boolean isEmpty() { return false; } }
30. … and its lazy filter public HeadTailList<T> filter(Predicate<T> p) { return isEmpty() ? this : p.test(head()) ? new LazyList<>(head(), () -> tail().filter(p)) : tail().filter(p); } 2 3 4 5 6 7 8 9 2 3 5 7
31. Back to generating primes static HeadTailList<Integer> primes(HeadTailList<Integer> numbers) { return new LazyList<>( numbers.head(), () -> primes(numbers.tail() .filter(n -> n % numbers.head() != 0))); } static LazyList<Integer> from(int n) { return new LazyList<Integer>(n, () -> from(n+1)); } LazyList<Integer> numbers = from(2); int two = primes(numbers).head(); int three = primes(numbers).tail().head(); int five = primes(numbers).tail().tail().head();
32. Printing primes static <T> void printAll(HeadTailList<T> list) { while (!list.isEmpty()){ System.out.println(list.head()); list = list.tail(); } } printAll(primes(from(2))); static <T> void printAll(HeadTailList<T> list) { if (list.isEmpty()) return; System.out.println(list.head()); printAll(list.tail()); } printAll(primes(from(2))); iteratively recursively
33. Iteration vs. Recursion  External Iteration public int sumAll(int n) { int result = 0; for (int i = 0; i <= n; i++) { result += i; } return result; }  Recursion public int sumAll(int n) { return n == 0 ? 0 : n + sumAll(n - 1); }  Internal Iteration public static int sumAll(int n) { return IntStream.rangeClosed(0, n).sum(); }
34. public class PalindromePredicate implements Predicate<String> { @Override public boolean test(String s) { return isPalindrome(s, 0, s.length()-1); } private boolean isPalindrome(String s, int start, int end) { while (start < end && !isLetter(s.charAt(start))) start++; while (start < end && !isLetter(s.charAt(end))) end--; if (start >= end) return true; if (toLowerCase(s.charAt(start)) != toLowerCase(s.charAt(end))) return false; return isPalindrome(s, start+1, end-1); } } Another Recursive Example Tail Rescursive Call
35. What's the problem? List<String> sentences = asList( "Dammit, I’m mad!", "Rise to vote, sir!", "Never odd or even", "Never odd and even", "Was it a car or a cat I saw?", "Was it a car or a dog I saw?", VERY_LONG_PALINDROME ); sentences.stream() .filter(new PalindromePredicate()) .forEach(System.out::println); Exception in thread "main" java.lang.StackOverflowError at java.lang.Character.getType(Character.java:6924) at java.lang.Character.isLetter(Character.java:5798) at java.lang.Character.isLetter(Character.java:5761) at org.javaz.trampoline.PalindromePredicate.isPalindrome(PalindromePredicate.java:17) at org.javaz.trampoline.PalindromePredicate.isPalindrome(PalindromePredicate.java:21) at org.javaz.trampoline.PalindromePredicate.isPalindrome(PalindromePredicate.java:21) at org.javaz.trampoline.PalindromePredicate.isPalindrome(PalindromePredicate.java:21) ……..
36. Tail Call Optimization int func_a(int data) { data = do_this(data); return do_that(data); } ... | executing inside func_a() push EIP | push current instruction pointer on stack push data | push variable 'data' on the stack jmp do_this | call do_this() by jumping to its address ... | executing inside do_this() push EIP | push current instruction pointer on stack push data | push variable 'data' on the stack jmp do_that | call do_that() by jumping to its address ... | executing inside do_that() pop data | prepare to return value of 'data' pop EIP | return to do_this() pop data | prepare to return value of 'data' pop EIP | return to func_a() pop data | prepare to return value of 'data' pop EIP | return to func_a() caller ...
37. Tail Call Optimization int func_a(int data) { data = do_this(data); return do_that(data); } ... | executing inside func_a() push EIP | push current instruction pointer on stack push data | push variable 'data' on the stack jmp do_this | call do_this() by jumping to its address ... | executing inside do_this() push EIP | push current instruction pointer on stack push data | push variable 'data' on the stack jmp do_that | call do_that() by jumping to its address ... | executing inside do_that() pop data | prepare to return value of 'data' pop EIP | return to do_this() pop data | prepare to return value of 'data' pop EIP | return to func_a() pop data | prepare to return value of 'data' pop EIP | return to func_a() caller ... caller avoid putting instruction on stack
38. from Recursion to Tail Recursion  Recursion public int sumAll(int n) { return n == 0 ? 0 : n + sumAll(n - 1); }  Tail Recursion public int sumAll(int n) { return sumAll(n, 0); } private int sumAll(int n, int acc) { return n == 0 ? acc : sumAll(n – 1, acc + n); }
39. Tail Recursion in Scala def isPalindrome(s: String): Boolean = isPalindrome(s, 0, s.length-1) @tailrec def isPalindrome(s: String, start: Int, end: Int): Boolean = { val pos1 = nextLetter(s, start, end) val pos2 = prevLetter(s, start, end) if (pos1 >= pos2) return true if (toLowerCase(s.charAt(pos1)) != toLowerCase(s.charAt(pos2))) return false isPalindrome(s, pos1+1, pos2-1) } def nextLetter(s: String, start: Int, end: Int): Int = if (start > end || isLetter(s.charAt(start))) start else nextLetter(s, start+1, end) def prevLetter(s: String, start: Int, end: Int): Int = if (start > end || isLetter(s.charAt(end))) end else prevLetter(s, start, end-1)
40. Tail Recursion in Java?  Scala (and many other functional languages) automatically perform tail call optimization at compile time  @tailrec annotation ensures the compiler will optimize a tail recursive function (i.e. you will get a compilation failure if you use it on a function that is not really tail recursive)  Java compiler doesn't perform any tail call optimization (and very likely won't do it in a near future) How can we overcome this limitation and have StackOverflowError-free functions also in Java tail recursive methods?
41. Trampolines to the rescue A trampoline is an iteration applying a list of functions. Each function returns the next function for the loop to run. Func1 return apply Func2 return apply Func3 return apply FuncN apply … result return
42. Implementing the TailCall … @FunctionalInterface public interface TailCall<T> { TailCall<T> apply(); default boolean isComplete() { return false; } default T result() { throw new UnsupportedOperationException(); } default T invoke() { return Stream.iterate(this, TailCall::apply) .filter(TailCall::isComplete) .findFirst() .get() .result(); } // ... missing terminal TailCall }
43. … and the terminal TailCall public static <T> TailCall<T> done(final T value) { return new TailCall<T>() { @Override public boolean isComplete() { return true; } @Override public T result() { return value; } @Override public TailCall<T> apply() { throw new UnsupportedOperationException(); } }; }
44. Using the Trampoline public class PalindromePredicate implements Predicate<String> { @Override public boolean test(String s) { return isPalindrome(s, 0, s.length()-1).invoke(); } private TailCall<Boolean> isPalindrome(String s, int start, int end) { while (start < end && !isLetter(s.charAt(start))) start++; while (end > start && !isLetter(s.charAt(end))) end--; if (start >= end) return done(true); if (toLowerCase(s.charAt(start)) != toLowerCase(s.charAt(end))) return done(false); int newStart = start + 1; int newEnd = end - 1; return () -> isPalindrome(s, newStart, newEnd); } }
46. Mario Fusco Red Hat – Senior Software Engineer mario.fusco@gmail.com twitter: @mariofusco Q A Thanks … Questions?