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
page 37
ANTLRInputStream input = new ANTLRInputStream(is);
as of ANTLR 4 .8 should be:
CharStream stream = CharStreams.fromStream(i...
New
Running the examples in chapter 5 c under pytest 5.4.1 causes an AttributeError: ‘module’ object has no attribute ‘config’.
In particula...
New
Title: Web Development with Clojure, Third Edition - migrations/create not working: p159
When I execute the command:
user=> (create-...
New
Title: Intuitive Python: docker run… denied error (page 2)
Attempted to run the docker command in both CLI and Powershell
PS C:\Users\r...
New
I’m running Android Studio “Arctic Fox” 2020.3.1 Patch 2, and I’m embarrassed to admit that I only made it to page 8 before running into ...
New
Hi, I have just acquired Michael Fazio’s “Kotlin and Android Development” to learn about game programming for Android. I have a game in p...
New
I found an issue in Chapter 7 regarding android:backgroundTint vs app:backgroundTint.
How to replicate:
load chapter-7 from zipfile i...
New
The markup used to display the uploaded image results in a Phoenix.LiveView.HTMLTokenizer.ParseError error.
lib/pento_web/live/product_l...
New
Modern Front-End Development for Rails - application does not start after run bin/setup (page xviii)
After some hassle, I was able to finally run bin/setup, now I have started the rails server but I get this error message right when I vis...
New
I got this error when executing the plot files on macOS Ventura 13.0.1 with Python 3.10.8 and matplotlib 3.6.1:
programming_ML/code/03_...
New
Other popular topics
Take your Go skills to the next level by learning how to design, develop, and deploy a distributed service. Start from the bare essential...
New
Stop developing web apps with yesterday’s tools. Today, developers are increasingly adopting Clojure as a web-development platform. See f...
New
Andy and Dave wrote this influential, classic book to help their clients create better software and rediscover the joy of coding. Almost ...
New
No chair. I have a standing desk.
This post was split into a dedicated thread from our thread about chairs :slight_smile:
New
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
Rails 7 completely redefines what it means to produce fantastic user experiences and provides a way to achieve all the benefits of single...
New
Author Spotlight
Dmitry Zinoviev
@aqsaqal
Today we’re putting our spotlight on Dmitry Zinoviev, author of Data Science Essentials in ...
New
Author Spotlight
Erin Dees
@undees
Welcome to our new author spotlight! We had the pleasure of chatting with Erin Dees, co-author of ...
New
Get the comprehensive, insider information you need for Rails 8 with the new edition of this award-winning classic.
Sam Ruby @rubys
...
New
Hair Salon Games for Girls Fun
Girls Hair Saloon game is mainly developed for kids. This game allows users to select virtual avatars to ...
New
Categories:
Sub Categories:
Popular Portals
- /elixir
- /rust
- /wasm
- /ruby
- /erlang
- /phoenix
- /keyboards
- /python
- /js
- /rails
- /security
- /go
- /swift
- /vim
- /clojure
- /java
- /emacs
- /haskell
- /svelte
- /typescript
- /onivim
- /kotlin
- /c-plus-plus
- /crystal
- /tailwind
- /react
- /gleam
- /ocaml
- /vscode
- /elm
- /flutter
- /ash
- /html
- /deepseek
- /opensuse
- /zig
- /centos
- /php
- /scala
- /react-native
- /lisp
- /textmate
- /sublime-text
- /nixos
- /debian
- /agda
- /deno
- /django
- /kubuntu
- /arch-linux
- /nodejs
- /ubuntu
- /spring
- /revery
- /manjaro
- /julia
- /lua
- /diversity
- /markdown
- /quarkus









