Mike Schaeffer's Blog

April 29, 2015

Since my last post, I dropped by an Apple Store to take a look at the 2015 MacBook. It is difficult to overstate how startlingly small the new machine is in person. I may be biased by the internal specifications, but the impression is much more 'big tablet' than 'small laptop'. The other standout feature was the touchpad. It continues Apple's tradition of high-quality touchpad implementations, removes the mechanicical switch and hinge, and adds force sensititivy and haptic feedback. The mechanical simplifications alone are a worthwhile improvement.

I also spent some time typing on the keyboard. It's as shallow as you'd think, but the keys are very direct have a positive feel. There's none of the subtle rattling found on most small keyboards and it registered every keypress. I'm not completely convinced yet, but it at least seems possible that this type of keyboard could become the preferred keyboard for some typists.

The performance of the machine is also a point of interest. Even the lightly loaded demo machine on the showroom floor had a few hiccups paging the display around from one virtual desktop to the next. Maybe it's nothing, but it does make me wonder if the machine can keep up with daily use, particuarly after a few OSX updates have been released. (For me, I think it'd be fine, but I spend most my time in Terminal, Emacs, and Safari, none of which are exactly heavy-hitters.)

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

Older Articles...