 
  		        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);
        }
    }
}
Popular Pragmatic Bookshelf topics
                         
                      
                       
          
                As per the title, thanks.
              
            
            
          
              New
 
          
                Hi Brian, 
Looks like the api for tinydb has changed a little. Noticed while working on chapter 7 that the .purge() call to the db throws...
              
            
            
          
              New
 
          
                Title: Hands-On Rust (Chapter 11: prefab) 
Just played a couple of amulet-less games.  With a bit of debugging, I believe that your can_p...
              
            
            
          
              New
 
          
                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
 
          
                Hi @venkats, 
It has been mentioned in the description of ‘Supervisory Job’ title that 2 things as mentioned below result in the same eff...
              
            
            
          
              New
 
          
                Hello! Thanks for the great book. 
I was attempting the Trie (chap 17) exercises and for number 4 the solution provided for the autocorre...
              
            
            
          
              New
 
          
                I ran this command after installing the sample application: 
$ cards add do something --owner Brian 
And got a file not found error: 
Fil...
              
            
            
          
              New
 
          
                Skimming ahead, much of the following is explained in Chapter 3, but new readers (like me!) will hit a roadblock in Chapter 2 with their ...
              
            
            
          
              New
 
          
                Book: Programming Phoenix LiveView, page 142 (157/378), file lib/pento_web/live/product_live/form_component.ex, in the function below: 
d...
              
            
            
          
              New
 
          
                @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
Other popular topics
                         
                      
                       
          
                A thread that every forum needs! 
Simply post a link to a track on YouTube (or SoundCloud or Vimeo amongst others!) on a separate line an...
              
            
            
          
              New
New
 
          
                I’ve been hearing quite a lot of comments relating to the sound of a keyboard, with one of the most desirable of these called ‘thock’, he...
              
            
            
          
              New
 
          
                Think Again 50% Off Sale »
The theme of this sale is new perspectives on familiar topics. 
Enter coupon code ThinkAgain2021 at checkout t...
              
            
            
          
              New
 
          
                Use WebRTC to build web applications that stream media and data in real time directly from one user to another, all in the browser.
  
...
              
            
            
              
          
              New
 
          
                Programming Ruby is the most complete book on Ruby, covering both the language itself and the standard library as well as commonly used t...
              
            
            
              
          
              New
 
          
                zig/http.zig at 7cf2cbb33ef34c1d211135f56d30fe23b6cacd42 · ziglang/zig. 
General-purpose programming language and toolchain for maintaini...
              
            
            
              
          
              New
 
          
                Will Swifties’ war on AI fakes spark a deepfake porn reckoning? 
              
            
            
              
          
              New
 
          
                Hello, 
I’m a beginner in Android development and I’m facing an issue with my project setup. In my build.gradle.kts file, I have the foll...
              
            
            
          
              New
 
          
                Fight complexity and reclaim the original spirit of agility by learning to simplify how you develop software. The result: a more humane a...
              
            
            
              
          
              New
Categories:
Sub Categories:
Popular Portals
- /elixir
- /rust
- /ruby
- /wasm
- /erlang
- /phoenix
- /keyboards
- /python
- /rails
- /js
- /security
- /go
- /swift
- /vim
- /clojure
- /haskell
- /emacs
- /java
- /svelte
- /onivim
- /typescript
- /kotlin
- /crystal
- /c-plus-plus
- /tailwind
- /react
- /gleam
- /ocaml
- /elm
- /flutter
- /vscode
- /ash
- /opensuse
- /html
- /centos
- /php
- /zig
- /deepseek
- /scala
- /lisp
- /sublime-text
- /textmate
- /react-native
- /nixos
- /debian
- /agda
- /kubuntu
- /arch-linux
- /django
- /revery
- /ubuntu
- /deno
- /spring
- /manjaro
- /nodejs
- /diversity
- /lua
- /julia
- /c
- /slackware
 
    





