Mike Schaeffer's Blog

Articles with tag: ksm
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.

August 6, 2013

Occasionally, it’s useful to be able to print nicely formatted tables of data to a textual output stream. This is particularly the case when writing command line tools. To make the output of these tools more readable, any tables they write should have columns that line-up from row to row. The Unix tool ls does this when it prints out long form directory listings. In this example, notice how the dates line up, even though the file size column varies in width.

drwxr-xr-x+ 1 mschaef Domain Users        0 Oct  3 09:20 docs
-rwxr-xr-x  1 mschaef Domain Users 29109013 Oct 10 13:38 file.zip
-rwxr-xr-x  1 mschaef Domain Users    77500 Oct 10 13:17 file2.zip

To accomplish this, it’s necessary to accumulate all of the lines of text to be written, compute the column widths when all lines are known, and then print the lines out, with appropriate padding to ensure that columns occupy the same width in each row. This is easy to accomplish, with just a bit of reusable Java.

package com.ksmpartners.utility;
 
import java.util.LinkedList;
import java.util.List;
 
import org.apache.commons.lang3.StringUtils;
 
public class TableBuilder
{
    List<String[]> rows = new LinkedList<String[]>();
 
    public void addRow(String... cols)
    {
        rows.add(cols);
    }
 
    private int[] colWidths()
    {
        int cols = -1;
 
        for(String[] row : rows)
            cols = Math.max(cols, row.length);
 
        int[] widths = new int[cols];
 
        for(String[] row : rows) {
            for(int colNum = 0; colNum < row.length; colNum++) {
                widths[colNum] =
                    Math.max(
                        widths[colNum],
                        StringUtils.length(row[colNum]));
            }
        }
 
        return widths;
    }
 
    @Override
    public String toString()
    {
        StringBuilder buf = new StringBuilder();
 
        int[] colWidths = colWidths();
 
        for(String[] row : rows) {
            for(int colNum = 0; colNum < row.length; colNum++) {
                buf.append(
                    StringUtils.rightPad(
                        StringUtils.defaultString(
                            row[colNum]), colWidths[colNum]));
                buf.append(' ');
            }
 
            buf.append('\n');
        }
 
        return buf.toString();
    }
 
}

The calling convention for this class is very much in line with the calling convention for Java’s StringBuilder.

TableBuilder tb = new TableBuilder();
 
tb.addRow("alpha", "beta", "gamma");
tb.addRow("-----", "----", "-----");
tb.addRow("1", "20000000", "foo");
tb.addRow("x", "yzz", "y");
 
System.out.println(tb.toString());

That code will write the following output:

alpha beta     gamma
----- ----     -----
1     20000000 foo
x     yzz      y

This isn’t necessarily the prettiest output in the world, but it’s easy to accomplish and is much better than many of the alternatives.

Tags:javaksm
Older Articles...