Mike Schaeffer's Blog

Articles with tag: java
December 20, 2014

One of the key attributes I look for when writing and reviewing code is that code should express the intent of the developer more than the mechanism used to achieve that intent. In other words, code should read as much as possible as if it were a description of the end goal to be achieved. The mechanism used to achieve that goal is secondary.

Over the years, I’ve found this emphasis improves the quality of a system by making it easier to write correct code. By removing the distraction of the mechanism underneath the code: it’s easier for the author of that code to stay in the mindset of the business process they’re implementing. To see what I mean, consider how hard it would be to query a SQL database if every query was forced to specify the details of each table scan, index lookup, sort, join, and filter. The power of SQL is that it eliminates the mechanism of the query from consideration and lets a developer focus on the logic itself. The computer handles the details. Compilers do the same sort of thing for high level languages: coding in Java means not worrying about register allocation, machine instruction ordering, or the details of free memory reclamation. In the short-term, these abstractions make it easier to think about the problem I’m being paid to solve. Over a longer time scale, the increased distance between the intent and mechanism makes it easier to improve the performance or reliability of a system. Adding an index can transparently change a SQL query plan and Java seamlessly made the jump from an interpreter to a compiler.

One of the unique sources of power in the Lisp family of languages is a combination of features that makes it easier build the abstractions necessary to elevate code from mechanism to intent. The combination of dynamic typing, higher order functions, good data structures, and macros can make it possible to develop abstractions that allow developers to focus more on what matters, the intent of the paying customer, and less on what doesn’t. In this article, I’ll talk about what that looks like for the calculator example and how Clojure brings the tools needed to focus on the intent of the code.

To level set, I’m going to go back to the calculator’s addition command defined in the last installment of this series.:

(fn [ { [x y & more] :stack } ]
   { :stack (cons (+ y x) more)})

Given a stack, this command removes the top two arguments from the stack, adds them, and pushes the result back on top of the stack. This stack:

1 2 5 7

becomes this stack:

3 5 7

While the Clojure addition command is shorter than the Java version, the Clojure version still includes a number of assumptions about the machinery used in the underlying implementation:

  • Calculator state is passed to the command as a map with a key :stack that holds the stack.
  • The input stack can be destructured as a sequence.
  • The output state is represented in a map allocated at the end of the command’s execution.
  • The output stack is a sequence of cons cells and the output of this command is stored in a newly allocated cell.
  • The command has a single point in time at which it begins execution.
  • The command has a single point in time at which it ends execution.
  • The execution of this command cannot overlap with other commands that manipulate the stack.

Truth be told, there isn’t a single item on this list that’s essential to the semantics of our addition command. Particularly in the case where a sequence of commands is linked together to make a composite command, every item on that list might be incorrect. This is because the state of the stack between elements of a composite command might not ever be directly visible to the user. Keeping that in mind, what would be nice is some kind of shorthand notation for stack operations that hides these implementation details. This type of notation would make it possible to express the intent of a command without the machinery. Fortunately, the programming language Forth has a stack effect notation often used in comments that might do the trick.

Forth is an interesting and unique language with a heavy dependency on stack manipulation. One of the coding conventions sometimes used in Forth development is that every ‘composite command’ (‘word’, in Forth terminology) is associated with a comment that shows a picture of the stack at the beginning and end of the command’s execution. For addition, such a comment might look like this:

: add ( x y -- x+y ) .... ;

This comment shows that the command takes two arguments off the top of the stack, ‘x’ and ‘x’, and returns a single value ‘x+y’. None of the details regarding how the stack is implemented are included in the comment. The only thing that’s left in the comment are the semantics of the operation. This is more or less perfect for defining a calculator command. Mapped into Clojure code, it might look something like this:

(stack-op [x y] [(+ x y)])

This Clojure form indicates a stack operation and has stack pictures that show the top of the stack both before and after the evaluation of the command. The notation is short, yes, but it’s particularly useful because it doesn’t overspecify the command by including the details of the mechanics. All that’s left in this notation is the intent of the command.

Of course, the mechanics of the command still need to be there for the command to work. The magic of macros in Clojure is that they make it easier to bridge the gap from the notation you want to the mechanism you need. Fortunately, all it takes in this case is a short three line macro that tells Clojure how to reconstitute a function definition from our new stack-op notation:

(defmacro stack-op [ before after ]
  `(fn [ { [ ~@before & more# ] :stack } ]
     { :stack (concat ~after more# ) } ) )

Squint your eyes, and the structure of the original Clojure add command function should be visible within the macro definition. That’s because this macro really serves as a kind of IDE snippet hosted by the compiler, providing blanks to be filled in with the macro parameters. Multiple calls to a macro are like expanding the same snippet multiple times with different parameters. The only difference is that when you expand a snippet within an IDE, it only helps you when you’re entering the code into the editor; the relationship between a block of code in the editor and the snippet from which it came is immediately lost. Macros preserve that relationship, and thanks to Lisp’s syntax, do so in a way that avoids some of the worst issues that plague C macros. This gives us both the more ‘intentional’ notation, as well as the ability to later change the underlying implementation in more profound ways.

Before I close the post, I should mention that there are ways to approach this type of design in other languages. In C, the preprocessor provides access to compile-time macro expansion, and for Java and C#, code generation techniques are well accepted. For JavaScript, any of the higher level languages that compile into JavaScript can be viewed as particularly heavy-weight forms of this technique. Where Lisp and Clojure shine is that they make it easy by building it into the language directly. This post only scratches the surface, but the next post will continue the theme by exploring how we can improve the calculator now that we have a syntax that more accurately expresses our intent.

December 15, 2014

In my last post, I started porting the RPN calculator example from Java to Clojure, moving a functional program into a functional language. In this post, I finish the work and show how the Clojure calculator models both state and calculator commands.

Going back to the last post, the Clojure version of the Read-Eval-Print-Loop (REPL) has the following code.

(defn main []
  (loop [ state (make-initial-state) ]
    (let [command (parse-command-string (read-command-string state))]
      (if-let [new-state (apply-command state command)]
        (recur new-state)
        nil))))

As with the Java REPL, this function continually loops, gathering commands to evaluate, evaluating them against the current state, and printing the state after each command is executed. The REPL function controls the lifecycle of the calculator state from beginning to end, starting by invoking the state constructor function:

(defn make-initial-state []
  {
   :stack ()
   :regs (vec (take 20 (repeat 0)))
   })

Like main, the empty brackets signify that this is a 0-arity function, a function that takes 0 arguments. Looking back at the call site, this is why the name of the function appears by itself within the parenthesis:

(make-initial-state)

If the function required arguments, they’d be to the right of the function name at the call site:

(make-initial-state <arg-0> ... <arg-n>)

This is the way that Lisp like languages represent function and macro call sites. Every function or macro call is syntactically a list delimited by parenthesis. The first element of that list identifies the function or macro being invoked, and the arguments to that function or macro are in the second list position and beyond. This is the rule, and it is essentially universal, even including the syntax used to define functions. In this form, defn is the name of the function definition macro, and it takes the function name, argument list, and body as arguments:

(defn make-initial-state []
  {
   :stack ()
   :regs (vec (take 20 (repeat 0)))
   })

For this function, the body of the function is a single statement, a literal for a two element hash map. In Clojure, whenever run time control flow passes to an object literal, a new instance of that literal is constructed and populated.

{
 :stack ()
 :regs (vec (take 20 (repeat 0)))
 }
 

This one statement is thus the rough equivalent of calling a constructor and then a series of calls to populate the new object. Paraphrasing into faux-Java:

Mapping m = new Mapping();
 
m.put("stack", Sequence.EMPTY);
m.put("regs", vec(take(20, repeat(0)));

Once the state object is constructed, the first thing the REPL has to do is prompt the user for a command. The function to read a new command takes a state as an argument. This is so it can print out the state prior to prompting the user and reading the command string:

(defn read-command-string [ state ]
  (show-state state)
  (print "> ")
  (flush)
  (.readLine *in*))

This code should be fairly understandable, but the last line is worthy of an explicit comment. *in* is a reference to the usual java.lang.System.in, and the leading dot is Clojure syntax for invoking a method on that object. That last line is almost exactly equivalent to this Java code:

System.in.readLine();

There’s more use of Clojure/Java interoperability in the command parser:

(defn parse-command-string [ str ]
  (make-composite-command
   (map parse-single-command (.split (.trim str) "\\s+"))))

The Java-interop part is in this bit here:

(.split (.trim str) "\\s+")

Translating into Java:

str.trim().split("\\s+")

Because str is a java.lang.String, all the usual string methods are available. This makes it easy to use standard Java facilities to trim the leading and trailing white space from a string and then split it into space-delimited tokens. Going back to part 2 of this series, this is the original algorithm I used to handle multiple calculator commands entered at the same prompt.

The rest of parse-command-string also follows the original part-2 design: each token is parsed individually as a command, and the list of all commands is then assembled into a single composite command. The difference is that there’s less notation in the Clojure version, mainly due to the use of the higher-order function map. map applies a function to each element of an input sequence and returns a new sequence containing the results. This one function encapsulates a loop, two variable declarations, a constructor call, and the method call needed to populate the output sequence:

List<Command> subCmds = new LinkedList<Command>();
  
for (String subCmdStr : cmdStr.split("\\s+"))
    subCmds.add(parseSingleCommand(subCmdStr));

What’s nice about this is that eliminating the code eliminates the possibility of making certain kinds of errors. It also makes the code more about the intent of the logic, and less about the mechanism used to achieve that intent. This opens up optimization opportunities like Clojure’s lazy evaluation of mapping functions.

The final bit of new notation I’d like to point out is the way the Clojure version represents commands. Commands in the Clojure version of the calculator are functions on calculator state, represented as Clojure functions:

(fn [ { [x y & more] :stack } ]
    { :stack (cons (+ y x) more)})

This function, the addition command, accepts a state object and uses argument list destructuring to extract out the stack portion of the state. It then assembles a new state object that contains a version of the stack that contains the sum of the top two previous stack elements. Rather than focusing on the machinery used to gather and manipulate stack arguments, Clojure’s notation makes it easier for the code behind the command to match the intent. As before, this helps reduce the chance for errors, and it also opens up new optimization opportunities.

(If you’ve read closely and are wondering what happened to regs, commands in the Clojure version of the calculator can actually return a partial state. If a command doesn’t return a state element, then the previous value for that state element is used in the next state. Because add doesn’t change regs, it doesn’t bother to return it.)

December 2, 2014

So far in this series, I’ve taken a basic calculator written in Java and transformed it from a command-oriented procedural design into a more functional style. In some ways, this has made for simpler code: calculator state is better encapsulated in value objects, and explicit control flow structures have been replaced with domain-specific higher order functions. Unfortunately, Java wasn’t designed to be a functional language, so the notation has become progressively more cumbersome and lengthy. 151 lines of idiomatic Java is now 327 lines of inner classes, custom iterators, and inverted control flow patterns. It should be difficult to get this kind of code through a serious Java code review.

Despite this difficulty, there is value in the functional design approach; What we need is a new notation. To show what I mean, this article switches gears and ports the latest version of the calculator from Java to Clojure. This reduces the size of the code from 327 lines down to a more reasonable-for-the-functionality 82. More importantly, the new notation opens up new opportunities for better expressiveness and further optimization. Building on the Clojure port, I’ll ultimately build out a version of the calculator that uses eval for legitimate purposes, and compiles calculator macros and can run them almost as fast as code written directly in Java.

The first step to understanding the Clojure port is to understand how it’s built from source. For the Java versions of the code, I used Apache Maven to automate the build process. Maven provides standard access to dependencies, a standard project directory structure, and a standard set of verbs for building, installing, and running the project. In the Clojure world, the equivalent tool is called Leiningen. It provides the same structure and services for a Clojure project as Maven does for a Java project, including the ability to pull in Maven dependencies. While it’s possible to build Clojure code with Maven, Leiningen is a better choice for new work, largely because it’s more well integrated into the Clojure ecosystem out of the box.

For the RPN calculator project, the project definition file looks like this:

(defproject rpn-calc "0.1.0-SNAPSHOT"
  :description "KSM Partners - RPN Calculator"
 
  :license {:name "Eclipse Public License"
            :url "http://www.eclipse.org/legal/epl-v10.html"}
 
  :dependencies [[org.clojure/clojure "1.5.0"]]
 
  :repl-options {
                 :host "0.0.0.0"
                 :port 53095
                 }
 
  :main rpn-calc.main)

This file contains the same sorts of information as the equivalent POM file for the Java version of the project. (In fact, Leiningen provides way to take a Leiningen project definition file and translate it into an equivalent Maven pom.xml.) Rather than XML, the Leiningen project file is written in an S-expression, and it contains a few additional settings. Notably, the last line is the name of the project’s entry point: the function that gets called when Leiningen runs the project. For this project, rpn-calc.main is a function that ultimately delegates to one of three entry points for the three Clojure versions of the calculator. For this post, the implementation specific entry point looks like this:

(defn main []
  (loop [ state (make-initial-state) ]
    (let [command (parse-command-string (read-command-string state))]
      (if-let [new-state (apply-command state command)]
        (recur new-state)
        nil))))
public void main() throws Exception
{
    State state = new State();
 
    while(state != null) {
        System.out.println();
        showStack(state);
        System.out.print("> ");
 
        String cmdLine = System.console().readLine();
 
        if (cmdLine == null)
            break;
 
        Command cmd = parseCommandString(cmdLine);
 
        state = cmd.execute(state);
    }
}

Unwrapping the code, both function definitions include construction of the initial state and then the body of the Read-Eval-Print-Loop. These two lines of code include both elements.

(loop [ state (make-initial-state) ]
    ...
    (recur new-state))

The loop form, surrounded by parentheses, is the body of the loop. Any loop iteration variables are defined and initialized within the bracketed form at the beginning of the loop. In this case, a variable state is initialized to hold the value returned by a call to make-initial-state. Within the body of the loop, there can be one or more recur forms that jump back to the beginning of the loop and provide new values for all the iteration variables defined for the loop. This gives a bit more flexibility than Java’s while loop: there can be multiple jumps to the beginning of a loop.

The body of this loop form is entirely composed of a let form. A let form establishes local variable bindings over a block of source code and provides initial values for those variables. If this sounds a lot like a loop form without the looping, that’s exactly what it is.

(let [command (parse-command-string (read-command-string state))]
   ...)

This code calls read-command-string, passing in the current state and then passes the returned command string into a call to parse-command-string. The result of this two step read process is the Clojure equivalent of a command object, which is modeled as a function from a calculator state to a state.

Digressing a moment, there are several attributes of the Clojure syntax that are worth pointing out. The most important is that, as with most Lisps, parenthesis play a major role in the syntax of the language. Parenthesis (and braces and brackets) delimit all statements and expressions, group statements into logical blocks, delimit function definitions, and serve as the syntax for composite object literals. In contrast, a language like Java uses a combination of semicolons, braces, and parsing grammar to serve the same purposes. This gives Clojure a more homogeneous syntax, but a syntax with fewer rules that’s easier to parse and analyze. Explicit statement delimiters also allow Lisp more freedom to pick symbol names. Symbols in Lisp can include characters (‘-‘, ‘<', '&', etc.) that infix languages can't use for the purpose, because the explicit statement grouping makes it easier to distinguish a symbol from its context. The topic of Lisp syntax is really interesting enough for its own lengthy series of posts and articles. Going back to the Clojure calculator's main loop, the next statement in the loop is yet another binding form. Like loop, this binding form also includes an element of control flow.

(if-let [new-state (apply-command state command)]
   (recur new-state)
   nil)

It may be easiest to see the meaning of this block of code by paraphrasing it into Java:

State newState = applyCommand(state, command);
 
if (newState != null)
    return recur(newState);
else
    return null;

What if-let does is to establish a new local variable and then conditionally pick between two alternative control flow paths based on the value of the new variable. It’s a common pattern within code, so it’s good to have a specific syntax for the purpose. What’s interesting about Clojure, though, is that if the language didn’t have it built in, a programmer working in Clojure could add it with a macro and you couldn’t tell the difference from built-in features. (In fact, the default Clojure implementation of if-let is itself a macro.)

At this point, I’ve covered the basic structure of the Clojure project, as well as the project’s main entry point. Subsequent posts will cover modeling of application state within Clojure, as well as the command parser, and the commands themselves. Once I’ve covered the basic functionality of the calculator, I’ll use that as a starting point to discuss custom syntax for command definitions, and ultimately a compiler for the calculator.

June 1, 2014

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.

March 31, 2014

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.

Tags:javaksm
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 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.

Older Articles...