dtonhofer

dtonhofer

Functional Programming in Java, Second Edition: All the code for Chapter 8, "Using Tail-Call Optimization", in one class

All the code for Chapter 8, Using Tail-Call Optimization, in one class. But without the part where we later need to “fix the arithmetic overflow”, an ancillary problem that is solely due to the fact that the example recursive function we use is the factorial. Here we use a simple recursive sum instead.

package chapter8.tailcalls;

import org.junit.jupiter.api.Test;

import java.util.function.Function;
import java.util.stream.Stream;

public class Chapter8_TailCallOptimization {

    private final static int limit = 70000;

    // ---
    // The "very slick stack simulator" (VSSS) for optimizable (not necessarily recursive) tail calls
    // This is the code "recur/fpij/TailCall.java" on p.142
    // with a fix: the .get() on the Stream has been replaced by .orElseThrow()
    // If we only use get(), the linter tells us: "Optional.get() without "isPresent()" check".
    // ---

    @FunctionalInterface
    public interface TailCall<T> {

        TailCall<T> apply();

        default boolean isComplete() {
            return false;
        }

        default T result() {
            throw new Error("not implemented");
        }

        default T invoke() {
            return Stream.iterate(this, TailCall::apply)
                    .filter(TailCall::isComplete)
                    .findFirst()
                    .orElseThrow()
                    .result();
        }
    }

    // "recur/fpij/TailCalls.java" on p.143

    public static class TailCalls {

        // call() simply exists so that usage has a symmetric look
        // (...but I'm not sure this improves understanding)

        public static <T> TailCall<T> call(final TailCall<T> nextCall) {
            return nextCall;
        }

        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 Error("not implemented");
                }
            };
        }
    }

    // ---
    // Summing using a recursive call that is not a tail call (avoid if possible, though
    // it is not always possible)
    // Replaces "recur/fpij/Factorial.java" on page 140.
    // ---

    private static class SumRecursivelyNaively {

        public static long sum(final int number) {
            return (number == 1) ? 1 : (number + sum(number - 1));
        }
    }

    // ---
    // Summing using a recursive call that is a proper tail call.
    // This approach uses an accumulator while going "down/into" the recursion.
    // On the way "back up/outo of" the recursion there are only "returns".
    // This can be optimized so that only 1 stack frame is used. However, the Java compiler
    // (and/or the JVM?) does not do that fully (maybe because it needs to keep track of
    // stack frames for debugging?), so we still get stack overflow after some time.
    // ---

    private static class SumRecursivelyUsingTailCalls {

        public static long sum(final int number) {
            return sum_inner(1, number);
        }



        private static long sum_inner(final long accumulator, final int number) {
            if (number == 1) {
                return accumulator;
            } else {
                return sum_inner(accumulator + number, number - 1);
            }
        }
    }

    // ---
    // An application of VSSS - the very sly stack simulator
    // Replaces "recur/fpij/Factorial.java" on p.141
    // ---

    private static class SumRecursivelyWithVSSS {

        public static long sum(final int number) {
            return sum_inner(1, number).invoke();
        }

        // Note that this method is *never* called recursively!

        public static TailCall<Long> sum_inner(final long accumulator, final int number) {
            if (number == 1) {
                // Return the "TailCalls" instance that ends the stream
                return TailCalls.done(accumulator);
            } else {
                // "call()" does nothing, and we could just return the closure directly, but it looks nice
                return TailCalls.call(
                        // When called by Stream.iterate(), this closure is supposed to generate&return the
                        // "next TailCall instance" of the stream
                        () -> sum_inner(accumulator + number, number - 1)
                );
            }
        }
    }

    // === TESTING SUPPORT BEGINS ===

    private static boolean callSum(final boolean skip, final String name, int n, Function<Integer, Long> sum) {
        boolean skipNextTime = skip;
        if (!skip) {
            try {
                long res = sum.apply(n);
                // Properly, this test should be in the caller
                if (n == limit - 1) {
                    System.out.println("Reached the end: " + name + "(" + n + ") = " + res);
                }
            } catch (StackOverflowError err) {
                System.out.println("Stack overflow for " + name + "(" + n + ")");
                skipNextTime = true;
            }
        }
        return skipNextTime;
    }

    // Running the three approaches at summing recursively till stack overflow occurs!
    // Works best if one reduces the maximum stack size of the JVM,
    // options "-Xss1m" or "-XX:ThreadStackSize=1024" (the latter in KiB)
    // See https://docs.oracle.com/en/java/javase/17/docs/specs/man/java.html#advanced-runtime-options-for-java
    //
    // Example output:
    //
    // Stack overflow for SumRecursivelyNaively.sum(38919)
    // Stack overflow for SumRecursivelyUsingTailCalls.sum(58375)
    // Reached the end: SumRecursivelyWithVSSS.sum(69999) = 2449965000

    @Test
    public void runThem() {
        boolean skipNaiveVersion = false;
        boolean skipTailCallVersion = false;
        boolean skipVsssVersion = false;
        for (int n = 1; n < limit && !(skipTailCallVersion && skipNaiveVersion && skipVsssVersion); n += 1) {
            skipNaiveVersion = callSum(skipNaiveVersion, "SumRecursivelyNaively.sum", n, SumRecursivelyNaively::sum);
            skipTailCallVersion = callSum(skipTailCallVersion, "SumRecursivelyUsingTailCalls.sum", n, SumRecursivelyUsingTailCalls::sum);
            skipVsssVersion = callSum(skipVsssVersion, "SumRecursivelyWithVSSS.sum", n, SumRecursivelyWithVSSS::sum);
        }
    }

}

Where Next?

Popular Pragmatic Bookshelf topics Top

brianokken
Many tasks_proj/tests directories exist in chapters 2, 3, 5 that have tests that use the custom markers smoke and get, which are not decl...
New
edruder
I thought that there might be interest in using the book with Rails 6.1 and Ruby 2.7.2. I’ll note what I needed to do differently here. ...
New
conradwt
First, the code resources: Page 237: rumbl_umbrella/apps/rumbl/mix.exs Note: That this file is missing. Page 238: rumbl_umbrella/app...
New
AndyDavis3416
@noelrappin Running the webpack dev server, I receive the following warning: ERROR in tsconfig.json TS18003: No inputs were found in c...
New
jskubick
I think I might have found a problem involving SwitchCompat, thumbTint, and trackTint. As entered, the SwitchCompat changes color to hol...
New
brunogirin
When I run the coverage example to report on missing lines, I get: pytest --cov=cards --report=term-missing ch7 ERROR: usage: pytest [op...
New
kolossal
Hi, I need some help, I’m new to rust and was learning through your book. but I got stuck at the last stage of distribution. Whenever I t...
New
dtonhofer
@parrt In the context of Chapter 4.3, the grammar Java.g4, meant to parse Java 6 compilation units, no longer passes ANTLR (currently 4....
New
mcpierce
@mfazio23 I’ve applied the changes from Chapter 5 of the book and everything builds correctly and runs. But, when I try to start a game,...
New
dachristenson
I’ve got to the end of Ch. 11, and the app runs, with all tabs displaying what they should – at first. After switching around between St...
New

Other popular topics Top

Exadra37
Please tell us what is your preferred monitor setup for programming(not gaming) and why you have chosen it. Does your monitor have eye p...
New
siddhant3030
I’m thinking of buying a monitor that I can rotate to use as a vertical monitor? Also, I want to know if someone is using it for program...
New
DevotionGeo
I know that -t flag is used along with -i flag for getting an interactive shell. But I cannot digest what the man page for docker run com...
New
AstonJ
Thanks to @foxtrottwist’s and @Tomas’s posts in this thread: Poll: Which code editor do you use? I bought Onivim! :nerd_face: https://on...
New
New
AstonJ
We’ve talked about his book briefly here but it is quickly becoming obsolete - so he’s decided to create a series of 7 podcasts, the firs...
New
PragmaticBookshelf
Rails 7 completely redefines what it means to produce fantastic user experiences and provides a way to achieve all the benefits of single...
New
PragmaticBookshelf
Author Spotlight Mike Riley @mriley This month, we turn the spotlight on Mike Riley, author of Portable Python Projects. Mike’s book ...
New
PragmaticBookshelf
A concise guide to MySQL 9 database administration, covering fundamental concepts, techniques, and best practices. Neil Smyth MySQL...
New
Fl4m3Ph03n1x
Background Lately I am in a quest to find a good quality TTS ai generation tool to run locally in order to create audio for some videos I...
New

Latest in Functional Programming in Java, Second Edition

Functional Programming in Java, Second Edition Portal

Sub Categories: