Mike Schaeffer's Blog

March 26, 2014

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.

January 28, 2014

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.

January 2, 2014

Up to now, the calculator’s main command loop has been a straightforward implementation of a REPL, or ‘read-eval-print-loop’. If you’re unfamiliar with the term, REPLs are the traditional means that interactive programming languages use to provide their interactivity. REPL’s provide a command prompt that a user can use to explore and manipulate the programming environment. In this way, a REPL makes it possible to work more quickly than traditional environments that require a program to be recompiled and restarted to test code changes.

While REPLs can become very complex in the details, the core idea is quite simple. As the name implies, REPL’s read a command from the user, evaluate that command, print the result of that evaluation, and loop back to start again. In rpncalc, all four of these steps are clearly evident in the code of the REPL. This is useful for explanatory purposes, but it closely couples the REPL to specific implementations of ‘read’, ‘evaluate’ and ‘print’. For this post, we’ll look into another way to model a REPL in code that offers a way to break this coupling.

The main command loop of rpncalc contains explicit code for each of the steps in an REPL:


// Set initial state
State state = new State();
 
// Loop until we no longer have a state.
while(state != null) {
 
    // Print the current state
    System.out.println();
    showStack(state);
 
    // Print a prompt, and read the next command from the user.
    System.out.print("> ");
    String cmdLine = System.console().readLine();
 
    if (cmdLine == null)
        break;
 
    Command cmd = parseCommandString(cmdLine);
 
    // Evaluate the command and produce the next state.
    state = cmd.execute(state);
}

This code is easy to read and explicit in intent, but it totally breaks down if commands can’t be read from the console. In the case of a REPL running on a server, it may be the case that a REPL needs to print and read over a (secured!) network connection. What would be useful is a way to decouple the mechanism for reading command from the loop itself.

In functionally oriented languages, this problem can be addressed by extending the REPL function with function arguments. These function arguments allow different implementations of read and print to be plugged into the same basic loop structure. Default implementations can be provided that connect to the console, with other implementations that might read and print using a network connection, or some other command transport. In Java, a similar effect can be achieved using functional interfaces (aka SAM types) to provide the pluggable alternative implementations. In fact, Java 8’s syntax for anonymous functions will make this approach syntactically convenient. Java also provides ways to achieve this extensiblity via class derivation.

Another way to view this problem can be seen by slightly changing your perspective on the REPL. It may not be completely obvious, but as with many loops, the REPL is iterating over a sequence of values. In the case of the REPL, the sequence is the sequence of commands that the user enters in response to prompts. For each command in the sequence, the REPL updates the current state and advances to the next sequence element. This isn’t as concrete as iterating over an in-memory data structure (and it isn’t necessarily bounded) but the semantics of the iteration are the same. The key to implementing this design is to provide a version of Iterable that implements iteration over a command stream. Given an iterable command stream, the REPL takes on a slightly different character:

// 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);
}

Compared to the initial loop implementation, this version is completely detached from the mechanisms used to prompt the user for input and read incoming commands. The termination criteria is also simpler: there isn’t an explicit check for the end of the command stream. The implicit termination check within the foreach loop captures that requirement.

The other component of this implementation is the implementation of the CommandStream. Unfortunately, this is where Java extracts its tax in lines of code for the additional modularity of this design. Like all iterable objects, the console command stream implements the Iterable interface. The iterator itself is defined as an anonymous inner class:

class ConsoleCommandStream implements Iterable<Command>
{
    public Iterator<Command> iterator()
    {
        return new Iterator<Command> ()
        {

One of the complexities of implementing Java’s Iterator interface is that callers must be able to call hasNext any number of times (zero to n) before each call to next. It’s not possible to assume one and only one call to hasNext for each call to next, despite the fact that the foreach does make that guarantee. Without going into the details, this implies that the actual advance operation can occur within either next or hasNext. While there are several ways to implement this, the approach I like to use is to have a separate method that advances the iterator, but only if it needs to be advanced. (Calls to next put the iterator into ‘requires advance’ state.) The advanceIfNecessary method is where the bulk of the work of the command stream takes place, including prompting the user, and reading and parsing the command.

Command nextCmd = null;
 
private void advanceIfNecessary()
{
    if (nextCmd != null)
        return;
 
    System.out.println();
    System.out.print("> ");
 
    String cmdLine = System.console().readLine();
 
    if (cmdLine == null)
        return;
 
    try {
        nextCmd = parseCommandString(cmdLine);
    } catch (Exception ex) {
        throw new RuntimeException("Error while parsing command: " + cmdLine, ex);
    }
}

In this way, Java’s built in support for iteration can be used to break the REPL apart into sub-compoments for handling the stages of command processing. The REPL is still clearly a REPL, but it no longer has explicit dependencies on the means used to acquire input commands. Unfortunately, the REPL still has explicit coupling for command evaluation and printing the result. As it stands now, we could modify the REPL to read commands from a network port, but we couldn’t redirect the output away from the local console. In the next post in the series, we’ll use the idea of reduce from functional programming to break the REPL into a pipeline of iterators. This will bring the rest of the flexibility we need.

December 17, 2013

Throughout the last four parts of this series, the common theme has been that the state of the calculator program has been managed globally. This requires the main command loop to directly update global data after each command, to prepare the state for the next command. While this works, it would be nice to remove the need for the global update. This post talks about how that’s done in the functional version of rpncalc.

The last installment in the series updated the calculator by adding a Java class to model State. This allows the entire state of the calculator to be managed as a first-class entity within the program. That’s evident from the fact that the calculator now models state through a single global reference:

public class RpnCalc extends Calculator
{
    // ...
 
    private State state = null;

Before I continue, I should clarify by saying that state isn’t truly a global variable. Obviously state is an instance variable within a single instance of RpnCalc. However, because of the fact that the calculator program only runs with a single instance of RpnCalc, any instance variables within that class are effectively global within the program, and suffer many of the same problems associated with true globals. This parallel is also true for instance variables within singletons managed by Spring. They’re instance variables, but they act like globals and should be viewed with the same kind of suspicion.

To remove the global state, we’re going to take advantage of the fact that the last update to rpncalc changed the signature for a command, so that it returns a new copy of the state:

abstract class Command
    {
        State execute(State in)

This implies that the main command loop has direct access to the updated state, and can manage it as a local variable:

public void main()
        throws Exception
    {
        State state = new State();
 
        while(state != null) {
            // ...read and gather command...
            state = cmd.execute(state);
        }
    }

This eliminates the global variable, moving the same data to a single variable contained within a function definition. This hugely reduces the variable’s footprint within the code. The global variable can be read and updated by 200 lines of code, compared to 20 lines of code for the local variable. For a developer, this makes the management of state more evident within the code, and makes it easier to write and maintain correct code.

Unfortunately, there’s a problem. For most of the commands, storing state in a local variable works well: a command like addition only needs access to the current state to produce the next state. Where it breaks down is in the undo command. In contrast to every other command, undo doesn’t need access to the current state, it needs access to the previous state. Now that we’ve moved the state management entirely within the command loop function, there’s no way for the undo command to get access to the history of states. Given that undo is a requirement, we need to find a solution.

One approach would be to extend the command loop to maintain a full history of states, and then broaden the command function signature to accept both the current and previous states. Each command would then be a function on a history of states. This approach has some appeal, but a simpler way to achieve the same result is to acknowledge the fact that each state is a function of the previous state, and store a back reference within each state:

private class State
{
    State prev;
    // ...
 
    State()
    {
        prev = null;
        // ...
    }
 
    State(State original)
    {
        prev = original;
        // ...
    }
}

This makes undo easy:

cmds.put("undo", new Command() {
        public State execute(State in) {
            // skip past the copy made for 'undo', and get to the previous.
            return in.prev.prev;
        }
    });

This design is also closely related to how git stores commits: each commit stores a back link to the previous commit in the history. It does have potentially unbounded memory usage, but our state in rpncalc is small enough in size and our memory is large enough that this shouldn’t present a problem. If it ever did present a memory consumption problem, adding a bound on the length number of retained states is as simple as walking down the previous links and nulling the previous link of the last history element to retain.

Next up, we’ll start taking a bit more advantage of the newly functional nature of rpncalc, and start using functional techniques to decompose the main command loop into component modules.

December 10, 2013

In the last installment of this series, I built a basic undo facility on top of the command pattern. One of the problems with that implementation is that the Command class has to know too much about how to save and restore the overall state of the calculator. In this post, I’ll introduce a way around this problem.

To see the problem, note that every instance of `Commandq has a private member variable for each global state variable maintained by the calculator:

private Deque<Double> oldStack;
private Double[] oldRegs;

Commands also have methods to save and restore the global state from the calculator instance itself:

void saveState()
{
    oldStack = new LinkedList<Double>(stack);
    oldRegs = Arrays.copyOf(regs, regs.length);
}
 
void restoreState()
{
    stack = new LinkedList<Double>(oldStack);
    regs = Arrays.copyOf(oldRegs, oldRegs.length);
}

Aside from the fact that Commands are directly updating the global state of the calculator, this design makes it more difficult to extend or modify the calculator’s notion of state. Any change to the calculator’s design that that adds a global state variable forces the Command class to be extended to manage the new global state. This means at least adding new private fields to Command and updating saveState and restoreState implementations. The stateobject version of RpnCalc addresses this issue by introducing a new class for the purpose of managing calculator state: State.

As you might have guessed, State has the two fields we need to store our current notion of state:

Deque<Double> stack = null;
 Double[] regs = null;

There are also two constructors, one for constructing a new, blank state, and a copy constructor for duplicating an existing state:

State()
{
    stack = new LinkedList<Double>();
    regs = new Double[NUM_REGISTERS];
}
 
State(State original)
{
    stack = new LinkedList<Double>(original.stack);
    regs = Arrays.copyOf(original.regs, original.regs.length);
}

The State class simplifies the calculator’s state variable declaration down to a single member variable:

private State state = null;

Along with that simplification, Command no longer needs to worry about state management, so it’s back down to a single method:

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

The biggest change here is that the execute method now returns an instance of State. With state objects, the behavior of a command is now that it accepts a ‘before’ state, and then returns the state that results from applying the command to the output state. Every implementation of Command, save for two, first makes a copy of the state using the copy constructor, and then updates the copied state and returns it to the caller. The command doesn’t touch the input state, aside from the initial copy operation (which isn’t an update).

At this point, you might want to re-read that last paragraph - it’s kind of a big deal. With this latest change to the calculator, we’ve really made two big improvements. The first is the change that motivated the post in the first place: Commands no longer need to know how to save and restore state and the no longer need to be aware of the contents of that state. The second change is that Commands are no longer modifying global state at all. Each command is now a Function, mapping from state to state.

This second aspect of the design change has many positive implications, but the first is that it makes it easier to implement undo. Because the input state passed into Command.execute isn’t touched, the caller can save off a copy of the previous state in its entirety. The calculator’s main command loop does just that:

Command cmd = parseCommandString(cmdLine);
 
State initialState = state;
 
state = cmd.execute(state);
 
LastState = initialState; // (lastState is an instance variable alongside state)

The undo command itself just ignores its input state and returns whatever the lastState was:

cmds.put("undo", new Command() {
        public State execute(State in) {
            return lastState;
        }
    });

This version of the calculator gets us most of the way to a mathematically functional implementation. The next installment will take us further by removing state and lastState.

November 19, 2013

One of the reasons given in the GoF book for the use of the command pattern is to support undo. By recording the commands executed by a user, and giving the commands the ability to reverse themselves, a user interface can be designed to allow users to undo mistakes they make. For this post, I’ll talk about how this is done by extending the last version of the calculator to support undo.

There are three main extensions to rpncalc that enable it to support undo. The first is that I’ve broadened the Command interface into an abstract class that supports operations for managing state. There is a new method, saveState, that saves a copy of the globally shared state within the command instance itself:

abstract class Command
{
    private Deque<Double> oldStack;
    private Double[] oldRegs;
 
    void saveState()
    {
        oldStack = new LinkedList<Double>(stack);
        oldRegs = Arrays.copyOf(regs, regs.length);
    }

There is also the inverse of saveState, restoreState:

void restoreState()
{
    stack = new LinkedList<Double>(oldStack);
    regs = Arrays.copyOf(oldRegs, oldRegs.length);
}

Taken together, these changes provide the two new fundamental operations necessary to support undo: Saving global state, in case an undo operation requires that it be restored at a later point in time. If the definition of global state ever broadens to include other variables, the change can be confined to these two methods. If there’s ever a more efficient way for a command to save state than a full copy, the change can be confined to these two methods. In this way the two methods provide an abstraction over the idea of ‘global state’. By adding methods (verbs) to manipulate global state, we’ve extended the language to allow direct statements about global state.

The next step is to use this new abstraction to implement undo. The first step is easy: each command needs to be modified to save the current global state before it executes. There are other ways to do this, but what I’ve done here is add a call to saveState at the beginning of each command implementation. This is simple, and for a small program like rpncalc, it works well:

cmds.put("+", new Command() {
        public void execute() {
            saveState();
 
            Double x = stack.pop();
            Double y = stack.pop();
 
            stack.push(x + y);
        }
    });

Implementing undo is just a bit trickier. One way to think about undo is that it restores the state at the beginning of the last command that was executed. To implement undo in these terms requires that we keep a record of the last executed command.

Command cmd = parseCommandString(cmdLine);
 
cmd.execute();
 
lastCmd = cmd;

From here, ‘undo’ is a new command that restores the state at the beginning of lastCmd:

cmds.put("undo", new Command() {
        public void execute() {
            saveState();
 
            lastCmd.restoreState();
        }
    });

Note that undo itself saves its own state. This makes undo a reversible operation: ‘undo’ can be ‘undone’.

To this point, we’ve developed the basic calculator idea around the idea of state contained in a collection of global variables. The methods saveState and `restoreStateq provide a nice, verb-oriented way to hide the details behind state management.

This approach has a great deal of headroom, but it doesn’t take advantage of the capabilities of the language to logically group data into tuples. The next installation of this series will look into a way we can use a Java object to package our entire calculator state into a single object that can be manipulated as a whole. If this post introduced verbs for managing state, the next post will introduce the noun.

October 28, 2013

If you’ve played around with the basic version of the Java calculator from the last post in this series, you may have tried to enter multiple commands on the same prompt line:

Begin: class com.ksmpartners.rpncalc.basic.RpnCalc

> 1 2
Uncaught Exception: For input string: "1 2"
java.lang.NumberFormatException: For input string: "1 2"

This is a convenient way to enter calculator commands, but it doesn’t work for two reasons. This post discusses why it fails, and how to fix it:

The immediate failure is because the parser considers the entire input string as a single command, without regard to whitespace. The parser looks for a command named "1 2", fails to find it, and then attempts to parse the entire string as a number. The number parse then fails and throws an exception that kills the process. This part of the problem can be fixed by altering the parser to split the input string into tokens, and parsing each token separately as its own command. Unfortunately, this shows the second more structural problem. The way the REPL is currently written, it’s built to read and execute a single Command for each prompt:

Command cmd = parseCommandString(cmdLine.trim());
 
cmd.execute();

To correct the second problem, the data flow between parseCommandString and execute needs to be widened so that the parser can return multiple commands for a single input string. The easiest way to achieve this is to have the parser return a list of Commands.

List<Command> cmds = parseCommandString(cmdLine.trim());
 
for(Command cmd : cmds)
    cmd.execute();

This approach works well because it’s simple. It doesn’t add any additional class definitions, there’s still a single call site for execute(), and java.util.List is well-understood by developers that use Java. However, if you’re willing to trade some of that simplicity away, there’s an alternative approach to the problem. The alternative approach allows the original REPL to go unchanged, and still process groups of commands. It does this by introducing a new and more powerful kind of command object that can be used to compose lists of commands into single Command instances. The parser then uses these CompositeCommands to signal to the REPL that there are multiple commands to be executed:

private Command parseCommandString(String cmdStr)
    throws Exception
{
    List<Command> subCmds = new LinkedList<Command>();
 
    for (String subCmdStr : cmdStr.split("\\s+"))
        subCmds.add(parseSingleCommand(subCmdStr));
 
    return new CompositeCommand(subCmds);
}

There are a few things to notice about this code. The first is that the type signature of parseCommandString is unchanged: it’s still a function from String to Command. This is why the REPL doesn’t need to be updated. The second aspect of the code is that there’s still a list of command objects: The list of commands we introduced when we modified the REPL example is still present, even with the CompositeCommand. What the composite command object does is hide the list from the REPL; It wraps the list up, abstracts it away, and lets the REPL pretend that there aren’t any lists.

The internal machinery that lets composite command achieve this isn’t too involved. All CompositeCommand has to do is remember the Command objects it’s composing, and execute each of those commands as if they were entered individually:

private class CompositeCommand implements Command
{
    private List<Command> subCmds = new LinkedList<Command>();
 
    CompositeCommand(Collection<Command> subCmds)
    {
        this.subCmds.addAll(subCmds);
    }
 
    public void execute()
    {
        for(Command subCmd : subCmds)
            subCmd.execute();
    }
}

And that’s all there is to it. While this approach doesn’t have the surface simplicity of our first attempt, what it has done for us is give us a new abstraction for sequences of commands. This is fully a third of the ‘sequence’, ‘selection’, and ‘iteration’ that are necessary to express any computable program. That’s not a bad result for a single class definition.

October 21, 2013

The first implementation of the RPN calculator I’m going to look at is the basic Java implementation. The link takes you directly a a view of the source file for this version, but if you’d like to play with the code, you can also clone the whole project with git. Cloning the git project will bring down all the versions of the calculator, and also let you compile and run the software locally. I’ll discuss more about how the implementation works, after the jump:

When you run the calculator, it works a lot like an interactive programming language with a read-eval-print-loop (REPL). The calculator presents a prompt, reads a command, executes it, prints the result, and then loops back around until the user types quit. A user session that computes the sum of two and three looks like this (user entry in bold):

Begin: class com.ksmpartners.rpncalc.basic.RpnCalc

> 2

1> 2.0
> 3

1> 2.0
2> 3.0
> +

1> 5.0
> quit
end run.

The implementation has to address several problems:

  • The stack has to be stored.
  • The current state of the calculator needs to be displayed to the user.
  • Commands need to be accepted from the user.
  • User commands need to be dispatched to code that performs the requested action.

Storage of the stack is simple. The basic version of the calculator uses a Java collection stored as an instance variable of the calculator class:

public class RpnCalc extends Calculator
{
    //...
 
    private Deque<Double> stack = new LinkedList<Double>();

Printing the stack is also simple, although it’s made more verbose by the fact that the Java foreach loop requires an Iterable, rather than an Iterator:

private void showStack()
{
    int ii = 0;
 
    for (Iterator<Double> it = stack.descendingIterator(); it.hasNext(); ) {
        Double val = it.next();
 
        System.out.println((ii + 1) + ">" + val);
        ii++;
    }
}

Similarly, the read, eval, print loop looks almost exactly like you’d expect. The most interesting bits are these:

Command cmd = parseCommandString(cmdLine.trim());
 
cmd.execute();

The last two statements translate whatever the user entered into a Command, an object that encapsulates the user’s intent into something that can be stored and directly executed at a later point in time. It is a command in the sense of the GoF Command Pattern:

interface Command
{
    void execute();
}

The command themselves do their work via direct mutation of the state stored in the stack instance variable:

cmds.put("+", new Command() {
    public void execute() {
        Double x = stack.pop();
        Double y = stack.pop();
 
        stack.push(x + y);
    }});

One tricky detail of this design is hidden in the fact that every command string entered by the user ultimately goes through Command.execute(). There is no special case for entering numbers, which therefore must also be done via a command. What’s different about the numeric entry command is that it contains a bit of instance data representing the number to be entered. The command parser creates a separate instance of PushNumberCommand for each number that’s entered on the command line.

private class PushNumberCommand implements Command
    {
        Double number;
 
        PushNumberCommand(Double number) { this.number = number; }
        public void execute() { stack.push(number); }
    }

In this design, you can make a strong argument that parseCommandString serves as a rudimentary compiler. Rather than translating from Java into classfiles, it translates from text into command instances. While this specific implementation only translates from strings containing a single command into command objects that perform a single operation, there’s nothing inherent in the design that prevents it from parsing complex command strings into complex command objects:

private Command parseCommandString(String cmdStr)
    throws Exception
{
    Command cmd = cmds.get(cmdStr);
 
    if (cmd != null)
        return cmd;
    else
        return new PushNumberCommand(Double.parseDouble(cmdStr));
}

Next time, I’ll talk a bit more about generalizing parseCommandString into a more powerful kind of compiler. This will enrich both the user command entry syntax, and give us a more powerful example of the command pattern within the calculator.

October 3, 2013

One of the things I remember most about middle school math class is that I went through it in a perpetual state of disorganization. During one particularly bad spell, I lost two calculators within a week. The loss, and the reaction of my parents, drove me to try to fix the problem once and for all. My plan was simple: buy an expensive calculator with the hope that it’d serve as an incentive to keep track of my stuff. The next weekend, I took weeks of allowance money to the local Service Merchandise and bought a new HP-11C pocket calculator. Almost 30 years later, I still have both the calculator and a fascination for its unusual Reverse Polish Notation (RPN) user interface. Over those decades, I’ve also found out that RPN provides a good way to explore a number of fundamental ideas in the field of software design.

If you haven’t used an RPN calculator, your first attempt will probably be a confusing experience. Unlike most calculators, The HP didn’t have an ‘=’ key. Instead, it had a large button down the center labeled ‘Enter’, which pushed the most recently keyed number onto an internal four-level stack. The mathematical operations then worked against this stack. The ‘+’ key popped off two numbers, added them, and pushed the result back onto the stack. To add 2 and 3, you’d make the following keystrokes: [2][ENTER][3][+].

In detail:

  • [2] – Begin entering the number ‘2’ into the top level of the stack.
  • [ENTER] – Duplicate the number ‘2’ on the top of the stack so it’s in the top two levels.
  • [3] – Begin entering the number ‘3’ into the top level of the stack, replacing one of the copies of the number ‘2’.
  • [+] – Pop off the top two levels of the stack, pushing back the sum of the two numbers.

Because the display shows the top level of the stack, it shows the answer (5) as soon as the user presses [+]. Because the answer, 5, is on the top of the stack, it’s also immediately ready to be used as an input to another calculation. This last bit is why RPN calculators can be so compelling to use: they make it easy to start with a small calculation and extend it into something larger. As long as a number is on the stack, it can be used in a calculation; The origin of the number doesn’t matter to the way it can be used. In computer science terms, this is the beginning of Referential Transparency. The FORTH programming language builds on this foundation, extending the basic tenets of RPN into a complete programming language. RPN combined with functional decomposition gives the language a great deal of expressive power, but due to the simplicity of stacks a small FORTH can be implemented in a very small amount of memory.

As this series of blog posts continues, I intend to explore some of these ideas using a set of RPN calculator implementations written in Java and in Clojure. We’ll start off with a simple implementation in Java, spend a bit of time exploring the command pattern, and then move into more functional approaches to the problem.

August 19, 2013

As part of a team conversation this morning, I worked up a quick Java translation of some more-interesting-than-it-looks Clojure code. It’s a good example of how lexical closures map to objects.

The code we started out with was this:

(defn make-adder [x]
  (let [y x]
    (fn [z] (+ y z))))
 
(def add2 (make-adder 2))
 
(add2 4)

What this code does is define and return a new type of function that adds values to the constant x. In Java, it looks like this:

// Not needed in Clojure... the Clojure runtime implicitly gives types
// that look similar to this to all Clojure functions.
interface Function
{
   Integer invoke(Integer z);
}
 
public class Foo
{
   // (defn make-adder [x]
   //   (let [y x]
   //     (fn [z] (+ y z))))
   public static Function makeAdder(Integer x)
   {
       final Integer y = x;
 
       return new Function() {
           public Integer invoke(Integer z) {
               return z + y;
           }
       }
   }
 
   public static int main(String[] args)
   {
       // (def add2 (make-adder 2))
       Function add2 = Foo.makeAdder(2);
 
       // (add2 4)
       System.out.println(add2.invoke(4));
   }
}

Five lines of Clojure code translate into 30 lines of Java: a function definition becomes a class definition, with state.

This idiom is powerful, but coming from Java, the power is hidden behind unusual syntax and terse notation. There are good reasons for both the syntax and the notation, but if you’re not used to either, it’s very easy to look at a page of Clojure code and be completely lost. Getting past this barrier by developing an intuitive feel for the language is a major challenge faced by teams transitioning to Clojure and Scala. One of the goals I have for my posts in this blog is help fellow developers along the way. It should be a fun ride.

Older Articles...