Mike Schaeffer's Blog

In the last installation of this series, we started using Java iterators to decompose the monolithic REPL (read-eval-print-loop) into modular compoments. This let us start decoupling the semantics of the REPL from the mechanisms that it uses to implement read, evaluate, and print. Unfortunately, the last version of rpncalc only modularized the command prompt itself: the ‘R’ in REPL. The evaluator and printer are still tightly bound to the main command loop. In this post I’ll use another kind of custom iterator to further decompose the main loop, breaking out the evaluator and leaving only the printer itself in the loop.

Going back to the original command loop from the stateobject version of rpncalc, the loop traverses two sequences of values in parallel.

state = new State();
 
while(running) {
    System.out.println();
    showStack();
    System.out.print("> ");
 
    String cmdLine = System.console().readLine();
 
    if (cmdLine == null)
        break;
 
    Command cmd = parseCommandString(cmdLine);
 
    State initialState = state;
 
    state = cmd.execute(state);
 
    lastState = initialState;
}

Neither of the two sequences this loop traverses are made explicit within the code, both are implicit in the sequence of values taken on by variables managed by the loop. The first sequence the loop traverses is the sequence of commands that the user enters at the console. This sequence manifests in the code as the sequence of values taken on by cmd through each iteration of the loop. The second sequence is similarly implicit: the sequence of states that state takes on through each iteration. Last post, when we added the CommandStateIterator, the key to that refactoring was that we took one of the implicit loop sequences and made it explicitly a sequence witin the code. Having an explicit structure within the code for the sequence of commands provided a place for the loop to invoke the reader that wasn’t in the body of the loop itself.

// Set initial state
State state = new State();
 
// Loop over all input commands
for(Command cmd : new ConsoleCommandStream()) {
 
    // Evaluate the command and produce the next state.
    state = cmd.execute(state);
 
    if (state == null)
        break;
 
    // Print the current state
    showStack(state);
}

Looking forward, the next refactoring for the REPL is to make explicit the implicit sequence of result states in the same way we transformed the sequence of input commands. This will let us take our current loop, which loops over input commands, and turn it into a loop over states. The call to evaluate will be pushed into an iterator in the same way that we pushed the reader into an iterator in the last post. This leaves us with a main loop that simply loops over states and prints them out:

for(State state : new CommandStateReduction(new State(), new CommandStream()))
    showStack(state);

This code is short, but it’s dense: most of the logic is now outside the text of the loop, and within CommandStateReduction and CommandStream. The command stream is the same stream of commands used in the last version of rpncalc. The ‘command state reduction’ stream is the stream that invokes the commands to produce the sequence of states. I’ve given it the name ‘reduction’ because of the way it relates to reduce in funcional programming. To see why, look back at abstract class we’re using to model a command:

abstract class Command
{
    abstract State execute(State in);
}

Given a state, applying a command results in a new state, returned from the execute method. A second command can then be applied to the new state giving an even newer state, and there’s no inherent bound on the number of times this can happen. In this way, a sequence of commands applied to an initial state produces a corresponding sequence of output states. The sequence of output states is the sequence of command results that the REPL needs to print for each entered command. Each time a command is executed, the result state needs to be printed and stored for the next command.

The relationship between this and reduction comes from the fact that reduction combines the elements of a sequence into an aggregate result. Reducing + over a list of numbers gives the sum of those numbers. Applying a sequence of commands combines the effects of those commands into a single final result. The initial value that gets passed into the reduction is the initial state. The sequence over which the reduction is applied is the sequence of commands from the console. The combining operator is command application. The most significant difference between this and traditional reduce is that we need more than just the final result, we also need each intermediate result. (This makes our reduction more like Haskell’s scan operator.)

Practically speaking CommandStateReduction is implemented as an Iterable. The constructor takes two arguments: the initial state before any commands are executed, and a sequence of commands to be executed.

class CommandStateReduction implements Iterable<State>
{
    CommandStateReduction(State initialState, Iterable<Command> cmds)

Note that the only property that the command state reduction requires of the sequence of commands is that it be Iterable and produce Commands. There’s nothing about the signature of the reduction iterator that requires the sequence of commands to be concrete and known ahead of time. This is useful, because our current command source is CommandStream, which lazily produces commands. Both the command stream and the command state reduction are lazily evaluated, and only operate when a caller makes a request. The command stream doesn’t read until the evaluator requests a command, the evaluator doesn’t evaluate until the printer makes a request for a value. Despite the fact that it’s hidden behind a pipeline of iterable object, the REPL still operates as it did before: first it reads, then it evaluates, then it prints, and then it loops back.

As with the command state iterator, most of the logic in command state reduction is handled with a single advanceIfNecessary method. The instance variable state is used to maintain the state between command applications:

private State state = initialState;
 
private boolean needsAdvance = true;
 
Iterator<Command> cmdIterator = cmds.iterator();
 
private void advanceIfNecessary()
{
    if (!needsAdvance)
        return;
 
    needsAdvance = false;
 
    if (cmdIterator.hasNext())
        state = cmdIterator.next().execute(state);
    else
        state = null;
}

Looking back at the code, the Java version of the RPN calculator has come a long way. From heavily procedural origins, we’ve added command pattern based undo logic, switched over to a functional style of implementation, and redesigned our main loop so that it operates via lazy operations on streams of values. We’ve taken a big step in the direction of functional programming. The downside has been in the size of the code. The functional style has many benefits, but it’s not a style that’s idiomatic to Java (at least before Java 8). Our code side has more than doubled from 150 to 320 LOC. In the next few entries of this series, we’ll continue evolving rpncalc, but switch over to Clojure. This will let us continue this line of development without getting buried in the syntax of Java.

Sometimes, it’s easy to focus so much on the architecture of a system that the details of its implementation get lost. While it’s true that inattention to architectural concerns can cause a system to fail, it’s also true that poor attention to the details can undermine even the best overall system design. This post covers a few minor details of code structure that I’ve found to be useful in my work:

It’s a small thing, but one of my favorite utility methods is a short way to throw run-time exceptions.

public static void FAIL(String message)
{
    throw new RuntimeException(message);
}

Defining this method accomplishes a few useful goals. The first is that (with an import static) it makes it possible to throw a RuntimeException with 22 fewer characters of source text per call site. If you’re writing usefully descriptive error messages (which you should be), this can significantly improve the readability of the code. The text FAIL tends to stand out in source code listings, and bringing the error message closer to the left margin of the source text makes it more obvious. The symbol FAIL is also easy to identify with tools like grep, ack, and M-x occur.

To handle re-throw scenarios, it's also useful to have another definition that lets you specify a cause for the failure.

public static void FAIL(String message, Throwable cause)
{
    throw new RuntimeException(message, cause);
}

Related to this is a useful naming convention for loop control variables. Thanks in large part to FORTRAN, and its mathematical heritage, it's very common to use the names i, j, and k for loop control variables. These names aren't very descriptive, but they're short and for small loop bodies, there's usually enough context that a longer name would be superfluous. (If your loop spans pages of text, you should use a more descriptive variable name... but first, you should try to break up your loop into sensible, testable functions.) One technique I've found useful for making loop control variables more obvious (and searchable) without going to fully descriptive variable names is to double up the letters, giving ii, jj, and kk.

These are both small changes, but they both can improve the readability of the code. Try them out and see if you like them. If you disagree that they are improvements, it's easy to switch back.

Update 2019-01-17: KSM recently redesigned their website in a way that removes the original blog. Because of this, I've taken some of what I wrote then for KSM and re-hosted it here. Thanks are due both to KSM Technology Partners for allowing me to do this and to the Wayback Machine for retaining the content. All the links below are updated to reflect the articles' new locations.

Sorry for the radio silence, but recently I've been focusing my writing time on the KSM Techology Partners Blog. My writing there is still technical in nature, but it tends to be more heavily focused on the JVM. If you're interested, here are a few of what I consider to be the highlights.

In mid-2013, I started out writing about how to use Runnable to explictly enforce dynamic extent in Java. In a nutshell, this is a way to implement try...with...resources in versions of Java that don't have it built in to the language. I then used the dynamic extent technique to build a ThreadLocal that plays nicely with thread pools. This is useful because thread pools require an understanding of which thread you're running on, which thread pooling techniques can abstract away.

Later in the year, I focused more on Clojure, starting off with a quick bit on the relationship of lexical closures to Java inner classes. I also wrote about a particular kind of stack overflow exception that can happen with lazy sequences. Lazy sequences can nicely remove the need to use recursion while traversing their length, but each time two unrealized lazy sequences are combined, it adds to the recursive depth required to compute the first element. For me, this stack overflow was a difficult error to diagnose, because it seemed so counter-intuitive.

I'm also in the middle of a series of posts that relate the GoF command pattern to functional programming. The posts start off with Java, but will ultimately describe a Clojure implementation that compiles a stack based expression language into optimized Java bytecode. If you'd like to play with the code, it's on github.

• Middle School Math, Reverse Polish Notation, and Software Design
• RPN Calc, Part 1 - A Simple Calculator in Java and the Command Pattern
• RPN Calc, Part 2 - Composite Commands
• RPN Calc, Part 3 - Undo
• RPN Calc, Part 4 - A Noun for State
• RPN Calc, Part 5 - Eliminating the Globals
• RPN Calc, Part 6 - Refactoring the REPL with an Iterator
• RPN Calc, Part 7 - Refactoring Loops with Reduce
• RPN Calc Part 8 – Moving to Clojure
• RPN Calc Part 9 – State and Commands in Clojure
• RPN Calc Part 10 – Macros and the Intent of the Code

I’ll get back to rpncalc shortly, but before I do, I wanted to take a post to talk about a surprising problem I recently had with lazy sequences. As part of my day job, I am developing a Clojure based system for accumulating and displaying time series data on a web page. One of the core algorithms in my implementation is a incremental merge sort. I have a function that takes two seq’s, both ordered by time, and produces a lazy result seq with all values from both inputs, also in time order. Every few seconds, as new input values are read from their sources, the program uses the ordered merge function to integrate the new values into a seq that contains a complete history of all values. It’s a straightforward and flexible design, and initially, it appeared to work quite well. The problems only started to arise after several hours of run time: traversing the history list would then immediately result in stack overflow exceptions.

If you’re familiar with lazy sequences, this may seem like an odd result. After all, one of the benefits of lazy sequences (aside from their laziness) is that they can eliminate recursion and reduce pressure on the stack. Lazy sequences might require more heap allocation, but they shouldn’t require all that much stack. To explore this idea a bit further, I’m going to use a simpler example than my merge function, I’m going to start with a recursive version of map:

(defn my-map [ fn xs ]
  (if (empty? xs)
     ()
     (cons (fn (first xs)) (my-map fn (rest xs)))))

For simple use cases, my-map has the same interface as the built-in function map:

user> (my-map #(+ 1 %) (range 3))
(1 2 3)
user> (map #(+ 1 %) (range 3))
(1 2 3)

The limitations of my-map start to become apparent for larger sequences:

user> (map #(+ 1 %) (range 10000))
(1 2 3 4 5 6 7 8 9 10 ...)
user> (my-map #(+ 1 %) (range 10000))
StackOverflowError   clojure.lang.Numbers.add (Numbers.java:1685)

What’s happening here is that the recursive call to my-map causes the function to allocate a stack frame for each element of the input sequence. The stack has a fixed size limit, so this places a fixed limit on the size of the sequence that my-map can manipulate. Any input sequences beyond that length limit will cause the function to overflow the stack. map gets around this through laziness, which is something that we can also use:

(defn my-map-lazy [ fn xs ]
  (lazy-seq
    (if-let [ xss (seq xs) ]
     (cons (fn (first xs)) (my-map-lazy fn (rest xs)))
     ())))

With this definition, all is right with the world:

user> (my-map-lazy #(+ 1 %) (range 10000))
(1 2 3 4 5 6 7 8 9 10 ...)

While the text of my-map and my-map-lazy is similar, the functions internally are quite different in operation. my-map completely computes the result of the mapping before it returns: it eagerly evaluates and returns the fully calculated result. In contrast, my-map-lazy doesn’t compute any of the mapping before it returns: it lazily defers the calculation until later and returns a promise to compute the result later on. The difference may be more clear, looking at a slightly macro-expanded form of my-map-lazy:

(defn my-map-lazy [ fn xs ]
  (new clojure.lang.LazySeq
     (fn* []
       (if-let [xss (seq xs)]
          (cons (fn (first xs)) (my-map-lazy fn (rest xs)))
         ()))))

The only computations that happen between the entry and exit of my-map-lazy are the allocation of a new lexical closure and then the instantiation of a new instance of LazySeq. While the body my-map-lazy still contains a call to itself, the call doesn’t happen until after my-map-lazy returns and the LazySeq invokes the closure. There is no recursive call, and there is no risk of overflowing the stack. (The traversal state that was stored on the stack in the recursive version is stored on the heap in the lazy version.)

So why was my merge sort overflowing the stack? To see why, I’m going to introduce a new function, using Clojure’s internal map function. This function serves no purpose, other than to introduce a layer of laziness. It is only useful for the purposes of this discussion:

(defn lazify [ xs ]
  (map identity xs))

Because the evaluation of map is lazy, we can predict that what lazify returns is a LazySeq. This turns out to be true:

user> (.getClass [1 2 3 4 5])
clojure.lang.PersistentVector
user> (.getClass (lazify [1 2 3 4 5]))
clojure.lang.LazySeq

Calling lazify on the result of lazify produces another LazySeq, distinct from the first.

user> (def a (lazify [1 2 3 4 5]))
#'user/a
user> (.getClass a)
clojure.lang.LazySeq
user> (def b (lazify a))
#'user/b
user> (.getClass b)
clojure.lang.LazySeq
user> (identical? a b)
false

Due to the way lazify is defined, the results of the sequences a and b are identical to each other - they both result in (1 2 3 4 5). However, despite the similarity in the results they produce, the two sequences are distinct and produce their results with different code paths. Sequence a computes the identity of each element of the vector [1 2 3 4 5] and sequence b computes the identity of each element of sequence a. Sequence b has to go through sequence a to get the value from the vector that underlies both. Even in lazy sequences, this process is still eager, still recursive, and it still consumes stack.

To confirm this theory, I’ll use another function that applies lazify to a sequence any number of times.

(defn lazify-n [ n seq ]
  (loop [n n seq seq]
    (if (> n 0)
      (recur (- n 1) (lazify seq))
      seq))

This function builds a tower of lazy sequences n sequences tall. Computing even the first element of the result sequence, involves recursively computing every element of each sequence in this tower, down to the original input seq to lazify-n. The depth of the stack required to maintain this recursive stack is proprortional to n. High values of n should produce sequences that can’t be traversed without throwing a stack overflow error. This turns out to be true:

user> (lazify-n 1 [1 2 3 4 5])
(1 2 3 4 5)
user> (lazify-n 4000 [1 2 3 4 5])
StackOverflowError   clojure.core/seq (core.clj:133)

Going back to my original merge sort stack overflow, it is caused by the same issue that we see in lazify-n. The calls to merge two lists don’t merge the lists at the time of the call. Rather, the calls produce promises to merge the lists at some later point in time. Every call to merge increases the number of lists to merge, and increases the depth of the stack that the merge process needs to use during the merge operation. After a while, the number of lists to be merged gets high enough that they can’t be merged without overflowing the stack. This is the cause of my initial stack overflow.

So what’s the solution? One easy solution is to give up some amount of laziness.

(defn lazify-n! [ n seq ]
  (loop [n n seq seq]
    (if (> n 0)
      (recur (- n 1) (doall (lazify seq)))
      seq))

The only difference between this new version of lazify-n and the previous is the call to doall on the fourth line. What doall does is force the full evaluation of a lazy sequence. So, while lazify-n! still produces an n high tower of lazy sequences, they’re all been fully traversed. Because LazySeq caches values the first time it’s traversed traversal, there’s no need to recursively call up the tower of sequences to traverse the final output sequence. This gives up some laziness, but it avoids both stack overflow issues we’ve discussed in this blog post: the overflow on long input sequence lengths and the overflow on deeply nested lazy sequences. The cost (there’s always a cost) is that this requires more heap storage than many alternative structures.