platypope.org

It’s been a week, but I’m still revved up from attending Clojure/conj. The energy, dedication, and intelligence in the Clojure community all continue to impress me, and definitely influence my choice of Clojure as my preferred programming language. Of course the language itself remains the most significant factor, and that’s something I’ve been meaning to blog about for some time.

My language of choice has gone from C to Perl1 to Python to Ruby to Python again, and then finally to Clojure. Each transition has been motivated by a perceived increase in practical expressiveness – an ability to communicate both effect and intent more directly and efficiently, both to the computer and to other humans. C to Perl provided garbage collection, first-class collections, and CPAN. Perl to Python provided real objects, comprehensible semantics, and a syntax that did not resemble line-noise. Python to Ruby provided blocks, open classes, and pervasive metaprogramming.

Ruby back to Python takes a bit more explaining. In so many ways the languages are so similar as to be almost indistinguishable.

One difference is in the communities surrounding the languages. Ruby has come a long, long way from the days when most of its documentation was only available in Japanese. But – there are differing cultural norms between the two communities on how best to balance documentation, stable interfaces, implementation quality, and the introduction of new features. I feel that the Ruby community pervasively emphasizes the latter above the others to a greater extent than I prefer. The Python language, standard library, and third-party libraries tend to be better documented and more stable than their Ruby counterparts. Not universally or to an unjustifiable extent – just sufficiently that I see a distinction, and prefer Python.

The other most significant aspect is that I believe Python APIs tend to be more value-oriented than their equivalent Ruby APIs. This one is a little difficult to explain...

Ruby more closely follows the canonical OO model by having a concept of “messages.” All method invocations and function calls are actually deliveries of messages to objects. When you see a line of Ruby code like:

invoke_method arg

All you know is that the implicit self at that particular line is going to receive the invoke_method message with the argument arg. You first need to unwind the evaluation state to figure what object self is at that point. Then you need to figure out how it will actually handle the message, which may be via a class instance method, an included module method, or method_missing. Messages themselves aren’t first-class or introspectable, so there’s no way to ask “if I send the invoke_method message here, who exactly will respond?”

Python in contrast has no implicit scopes and models everything in terms of attribute access and function-calling2. When you see a line of Python code like:

object.method(arg)

You know there is an in-scope, introspectable value named object at this line. That value is asked via the attribute-access protocol for its method member, which yields another introspectable value. That attribute value is invoked via the function call protocol with the argument arg. At every step of the way you have a concrete, introspectable value backed by code you can find and follow.

In my experience these differences aren’t just a curiosity, but directly impact the way one most concisely expresses code in the two languages. In Ruby libraries it is a very common idiom to provide methods invoked within a class definition or instance_eval’d block which build state by modifying the implicit self. The moral analog of this in Python (metaclasses) is relatively rare, and most Python libraries provide interfaces in terms of concrete values. For a good example of what I’m talking about, look at the difference between the ruby-ffi and Python ctypes libraries.

And then finally, Clojure.

For the few years I’ve been using it, I’ve found that Clojure maximizes practical expressiveness in three ways which beat all other languages I’ve tried. It has everything you’d expect from a language like Python or Ruby, but then has adds these things on top.

First there’s the obvious: macros. Ruby and Python provide metaprogramming facilities which allow programmatically generating any constructs one could produce directly through code. But doing so is not always going to be as legible or compact as simply writing out the desired result, nor will it necessarily bear a clear relation to that directly-expressed version. With Clojure macros, you instead have the ability to do arbitrary in-code code-generation, using the same functions as for general-purpose code, and acting effectively like executable structural templates for the expanded code. In Clojure, there never needs to be any boilerplate – even if macros aren’t always the best method for eliminating code repetition, they are a method which can be used to eliminate any code repetition.

Second is the language’s functional style and culture. Without the language itself enforcing functional purity, the style of the Clojure standard library and the norms of the Clojure community encourage it. This gives what I see as the best of both worlds: the ability to write and reason about most code as pure functions operating on immutable values, while escaping to side effects and mutation when necessary without any excess ceremony. This makes it even more value-oriented that Python, with almost all execution happening in terms of values which are not only concrete and visible, but also immutable.

Third is Clojure’s definition as an explicitly hosted language, and specifically the JVM as the best-supported hosting platform. I was a bit resistant at first to getting deeply acquainted with the JVM and (oh, the humanity!) Java, but I now see it as a significant benefit. Part of practical expressiveness is not needing to write code incidental to the application domain. The vast ecosystem of Java libraries and the ease with which Leiningen allows access to them significantly cuts down on incidental code. The JVM itself of course is rock-solid, fast3, and universal. From a practical perspective, it’s a clear win for almost all applications.

Anyway, enough blogging – time to go write some Clojure!

1 In college >10 years ago, so cut me a little slack.

2 Which I believe you could think of as being messages, but I’m not sure that really helps much.

3 Well, after boot.

Update: Ok, I was wrong!; or at least greatly over-stated my case. People have shown me lots of great examples of when comments-qua-comments can be useful1. I still think that much of the time, the time spent writing explanatory comments would be better spent just making the implementation clearer. But code can’t always perfectly capture intent or the influence of external factors. Consider my incipient dogmatism rescinded.

I am on the record at my current office saying that I prefer to work on code-bases without comments. I do my best to follow this preference in the code I write myself, which occasionally provokes some, er – comment. I can see why this might be controversial, so I’d like to explain.

Not comments

First off, some things that aren’t “comments” in the sense I mean; this:

(defn clojure-function
  "Calculates a result from arguments `args`."
  [& args] ... result)

Or this:

def python_function(*args):
    """Calculates a result from arguments `args`."""
    ...
    return result

Or even this:

/**
 * Calculates a result from arguments.
 *
 * @param args  the arguments to use in the calculation
 */
AbstractInterfaceAdaptorProxy
javaMethod(FlyweightFacadeFactory args...) {
    ...
    return result;
}

The first two examples are obviously not comments – they’re strings. To be precise, they’re docstrings. The third example uses Java’s syntax for comments, but only because Java doesn’t have docstrings. All three are pieces of interface documentation which are consumed in a structured way by an automated documentation system. The syntax of comments provides a convenient way to bolt on structured in-line interface documentation for languages which don’t have built-in support for it, but it’s hardly what comments are “for”; otherwise languages with real docstrings wouldn’t have a separate syntax for comments.

Also not comments: the input to systems like docco and marginalia. These sorts of systems use the syntax of comments to bolt on support for producing comprehensive, structured implementation documentation. They only use the syntax of comments because no one aside from Donald Knuth seems to be able to make it work to write the implementation in-line in the documentation2. Turning the documentation/implementation relationship inside-out shows use of the “comment” syntax as an artifact of convenience.

Comments, a taxonomy

Ok, so what does that leave as “actually comments”?

Implementation-repetition

# Append a dot to the end
some_string += "."

I can read just fine, thanks!

From the peanut gallery

# Wow, what a kludge
object.send(:private_method)

Well, then why are you doing it?

Completely wrong

# Only show users specials on Sunday
return false unless username =~ VALID_USERNAME_RE

Looks like someone changed the code without making sure the comments still matched!

Right?

# Increment by 2 to account for leap-seconds since 2004
seconds += 3

Just close enough to create the potential for confusion. Has there been another leap-second, or is seconds being incremented for a completely different reason?

What I tell you three times is true

# BACKEND-192: Implement secondary sort so that we can track preferences
#   on a per-user basis.
operation.sort_key = [:overall_rating, :user_preference]

So now there’s three different explanations of what the code is doing: the high-level description linked to changing requirements in the issue tracking system, the historical implementation description in the associated commit message, and... this comment, which isn’t linked to changing requirements or to the history of changes. Unless you look at the ticket to see what’s changed, or look at the commit log to see the change in context. The comment in the code adds absolutely nothing.

Right, but...

# Increment by 3 to account for leap-seconds since 2004
seconds += 3

The comment is right, and usefully explains what’s happening semantically, but why have a comment when you could just make the implementation read as clearly without a comment?:

LEAP_SECONDS_SINCE_2004 = 3
...
seconds += LEAP_SECONDS_SINCE_2004

If you need to explain why you’re adding in the leap-seconds, you can add a semantically-named function/method which performs the operation. I strongly believe that in most situations it’s possible to make the code itself just as clear as any comment could make it.

Explaining the horror

# Warning: massive kludge, but we can’t fix it until we re-implement
# the primary business logic, which is currently written in a dialect
# of REXX invented by Jim, who quit yesterday.
object.send(:private_method)

Hey, that’s actually useful!

It also indicates a code-base I’d really prefer not to work on if I can avoid it, and is also the kind of comment I certainly never want to feel the need to write myself.

Conclusion

So that’s why I prefer there be no comments: the only real use I see for comments-qua-comments is unstructured documentation of the reasons behind specific implementation warts. If I can help it, I prefer the code-bases I work on not have such warts. QED.

Comments?

1 Erik Peterson’s list in the comments on this post is a pretty good summary.

2 I know that there are other literate programming practitioners out there, but I must confess to never having tried it myself. Maybe some day.

Couldn’t sleep, worked on blog instead.

I managed to get comments up with Disqus yesterday. Now I’ve got Jekyll rendering posts using Emacs muse-mode, just like my old blogging system did. Among other things, that means that I can use Emacs as my syntax-highlighting engine again:

(defn with-starts?
  "Does string s begin with the provided prefix?"
  {:inline (fn [prefix s & to]
             `(let [^String s# ~s, ^String prefix# ~prefix]
                (.startsWith s# prefix# ~@(when (seq to) [`(int ~@to)]))))
   :inline-arities #{2 3}}
  ([prefix s] (.startsWith ^String s ^String prefix))
  ([prefix s to] (.startsWith ^String s ^String prefix (int to))))

And I once again have footnotes1 which jump over into the side margin. I had to convert my old footnote-mangling code to jQuery from Prototype (yes, it was that old). But hey – it works now!

And I even added back an Atom feed and the archived posts page.

I think that’s actually it. Blog once again fully armed and operational. Not too shabby for a few hours of insomnia. Zzz...

1 So yes, actually sidenotes when everything works properly.

My now very former hosting provider “lost” my blog VPS, and I lost everything on it. My automated backup process had apparently stopped working when I’d shuffled some paths around. Oops. Thankfully the Wayback machine archived my blog for me, so I’ll be able to get back most of it. My previous process and custom+creaky blog engine was too complicated anyway – let’s give a try to a static site (generated with Jekyll).

I’ll be restoring functionality and old blog posts as I go, but I wanted to get something back online. It’s felt odd not having a Web presence – like I was no longer really there on the Internet, or some sort of Internet ghost. Spooooooky.

Anyway, I’m glad to be back.

I lost the original version of this post. C’est la vie. The gist is that Clojure’s standard case macro somewhat surprisingly (to me) does not support arbitrary expressions as test conditions – only read-time constants. It does this because it’s primary use from the Clojure-implementation perspective is to support fast dispatch on symbol/keyword values.

Other people have blogged about this and provided their own less-surprising implementations, include cemerick.

I didn’t like any of the ones I found elsewhere, so here’s mine:

(defmacro case-expr
  "Like case, but only supports individual test expressions, which are
evaluated at macro-expansion time."
  [e & clauses]
  `(case ~e
     ~@(concat
        (mapcat (fn [[test result]]
                  [(eval `(let [test# ~test] test#)) result])
                (partition 2 clauses))
        (when (odd? (count clauses))
          (list (last clauses))))))

Enjoy!

With Amazon.com not selling Macmillian books at the moment, now might seem like a good time to go to the source and buy ebooks directly from Macmillian. And they even have multiple formats available!: the “Adobe Digital Edition” format and the “Adobe eReader” format.

Wait, what?

According to their Ebooks information and help page, “Adobe eReader” books enable you “to read high-fidelity ebooks alongside other PDF files. Only this reader software displays ebooks with the pictures, graphics, and rich fonts you’ve come to expect from printed books.” While “Adobe Digital Editions” is “Adobe’s reader designed for eBooks” and “uses a format based on the Open Publishing Standard with the extension .epub,” but “ADE will also display your PDF files in a double-page, single page, or fit-to-width view — or you can specify your own custom fit.” Both formats have software download links, which both redirect to Adobe’s current Digital Editions page.

So. Er. I think “Adobe eReader” is PDF and “Adobe Digital Editions” is EPUB. Format proliferation is bad enough without making format identification more difficult than necessary.

A few years ago I discovered that Wizards of the Coast had started selling PDF versions of pretty much the entire catalog of TSR-published original D&D, AD&D, and AD&D 2nd Ed material, all at quite reasonable prices. I’ve been fond of the Planescape setting ever since I was first introduced to it, and I impulsively bought the majority of the AD&D 2nd Ed Planescape manuals. You known, in case I ever get suddenly transported back to the 90’s or something. I later lost those precious, fully-paid-for bits in a hard drive crash, and didn’t bother redownloading them again because of reasons which seemed reasonable at the time. I mean, the vendor I bought them from will surely let them download them again whenever I decide to. What could possibly go wrong?

Fast forward to the present. Finally setting up a reasonable backup scheme jogged my memory of previously lost bits, and I decided to try downloading new copies of those RPG manuals. And… the vendor still exists… I’m able to log in… they have my complete order history… they have download links!… and – no. Apparently WotC pulled the plug, stopping all e-book sale of their both current and out-of-print material, including re-downloads of already-sold titles.

Of course, a quick search turned up Rapidshare-hosted copies of all the books I’d purchased, which I felt no scruples about downloading. But chicken or egg – are the books so easily available because WotC removed them from legitimate channels? Or was the pull in the first place a response to widespread piracy? Either way, I don’t see how WotC is benefiting.

Faruk Ates responds to Mark Pilgrim’s Tinker’s Sunset by trivializing tinkering and claiming that the ease-to-use devices like the iPad are fostering a Creative Revolution:

The simple matter is that these guys are old, and they grew up in an age where tinkering was the only possible course of action if you wanted to use the latest and greatest technology to its fullest potential. The Mac, in 1984, shifted that paradigm of creativity and creation towards average consumers a little. The iPhone and iPad are shifting it even further towards consumers, away from the tinkerers of old, the small little “elite” that excludes the vast majority of people.

He may be right about fostering creativity, but he’s missing the point. Making the iPad accessible to non-tinkers and making it untinkerable are completely orthogonal.

Imagine that the iPad worked exacly as Apple has already presented, but it also had a “tinker” switch. When on, this switch allowed users to run applications not signed by Apple, with appropriately dire warnings. Problem solved, without impacting typical user experience.

“Tinkering” is easy to trivialize, but doing so ignores what its prevention represents technically. What we’re talking about on the iPad is an impenetrable cryptographic shield which gives Apple absolute control over what code is allowed to run. Apple, not users, determines what applications are appropriate. Apple is free to censor not only content which fails to meet their technical standards, but also content which conflicts with their business interests or they deem to be “obscene.” No matter how light the shackles, on the iPad (and iPhone) you are not free.

On the flip side, like Pilgrim I do see “tinkering” as valuable in itself. Software stacks more than any other engineered systems are inherently knowable, and one can learn from them. Fully free systems (in Stallman’s sense) are the most knowable and most instructive by virtue of the source code for every component being there for the asking. With a cryptographically shielded platform like the iPad this is impossible, and the system is unknowable and there is nothing to be learned even for the “elite.”

For Christmas my girlfriend gave me a series of increasingly difficult wooden-block puzzles, yielding up each one only as I solved the previous. She’d show me the assembled puzzle — to mock me, I assume — then dump it disassembled into my lap1. The first one was a quickly-solved freebie, but the remaining three were pretty difficult. Difficult enough even that I decided to let computers do the boring work and wrote programs to solve them. Ah, the joys of being a software engineer!

And if you think this is “cheating,” I feel the final results from my “bonus round” (at the end of this post) validate the approach.

Round 1 was the King Snake. This puzzle is a 4x4x4 cube composed of 64 linearly connected unit-cubes. The strand of unit-cubes is divided into 46 segments of 2-4 cubes each. Each segment shares a joint cube with its previous segment and freely rotates to form any right angle with that segment. A naive estimation of the problem space is greater than 1e27 (4 right-angles to the power of 46 segments). However, most moves eliminate 25-75% of the remaining problem space by either running into already-filled space or leaving the allowed 4x4x4 grid. Counting on the constraints quickly reducing the problem space, I initially solved this one with a pretty naive depth-first search written in Python.

The Python program took about 5 hours to run, and was designed to find only one solution. But hey! — it worked and found a solution. I later revisited this puzzle with what I learned from solving the others, but I’ll get to that at the end.

Round 2 was the Shipper’s Dilemma Z. This puzzle is a 5x5x5 cube composed of 25 identical, 5-unit-cube, vaguely Z-shaped pieces. For this one I did some research, hoping something about tessellation would help. Alas, even though the pieces are all identical, it appears that this is still an (NP-complete) packing problem. There are 960 positions a piece could occupy within the space, which for 25 pieces yields a naive complexity estimate of greater than 1e492. Ouch. It seemed much less likely in this case that the basic problem constraints would help much, as a naive depth-first search would prune only a few possibilities with each move. I wrote a simple first-try in Python anyway. It got absolutely nowhere, which led me to decide to try something different, something “clever.” And thus down a rabbit-hole I went.

I’ll leave out most of the details, but I wasted a lot of holiday time trying to solve this puzzle with something akin to dynamic programming. I’d build groups of 3 pieces “attached” to a vertex, combine those into groups of 6 pieces attached to a quadrant, combine those into group of 12 attached to a side, then combine those into groups of 24 which (for solutions) would (theoretically) form the full cube with one piece-shaped hole somewhere in the middle. It was a terrible, terrible idea. The computational complexity of each step varied wildly as I changed my methods for forming groups and what assumptions I made about the properties of solution-participating groups. At one point the execution-time was lagging just enough that I re-wrote the solution-grinding code in C. Later the complexity was just where it wasn’t feasible to run at home, but I could run it on Amazon’s Elastic MapReduce. I did learn how to use Hadoop, EC2, and EMR, but — long story short — none of it yielded a solution. I eventually climbed out of the rabbit-hole and went back to a depth-first search, but this time with a much better conceptualization of the problem.

Fast C primitives help3, but the only real way to solve a problem of this sort is by exponentially reducing the search space. The first step is to avoid working on any “unsolvable” states. Many patterns of piece-placement leave gaps which no subsequent piece can fill. I test for this by filling in a copy of the board state with all the pieces which could fit, even if those pieces themselves overlap. If the cube isn’t completely filled, then the initial board state cannot lead to a solution.

Another obvious step for any sort of space-pattern problem is to eliminate all rotations and reflections which result in other states in the same symmetry group. For a cubical puzzle like this one, eliminating symmetries reduces the state-space by a factor of 48. In this case, I did so by initially calculating all symmetrically unique states which have 8 pieces placed, one in each corner. This also has the nice side-effect of splitting the search-space into parallelizable segments, although that turned out to be unnecessary.

The final step necessary to explore all the “interesting” states in a reasonable amount of time is to eliminate the exploration of duplicate states. Just naively iterating over piece combinations will result in trying both piece A then B and piece B then A, even though they result in exploring the same board states. I iterated over a couple approaches to this, but eventually hit upon simply ensuring that each position in the puzzle is filled in a fixed sequence. This minimizes the number of options available for each placement and doesn’t require any explicit book-keeping to short-circuit previously-explored board states.

Final running-time: 2.5 minutes to generate all four solutions.

Round 3 was the RAMU OCTAHEDRON4. This one is kind of a irregular decahedron5 represented as a 5x5x5 cube with the 4 unit-cubes at each vertex removed. It splits into 8 very irregularly-shaped pieces. There are also two small wooden spheres which occupy unfilled space within the cube and “lock” it by preventing motion of the “key” piece unless the spheres are shifted into particular positions. The site calls the Ramu Octahedron their “most difficult puzzle” and claims that only one person has solved it without reference to the solution. The difficulties of this puzzle are three-fold: the irregularity of the pieces makes conceptualizing their spatial placement difficult; many of the pieces can only be placed by combinations of separate “insertion” then “locking” motions; and once the puzzle is assembled, one must determine how to maneuver the spheres within the unfilled internal space to allow re-disassembly.

Fortunately the piece-irregularity holds little difficulty for a computer. After laboriously entering the shapes of each piece, I was able to re-use code I’d written for the previous puzzle to generate all the interesting piece rotations and translations6 and their various combinations. Once that gave me the solution spatial arrangement, it required a bit of trial-and-error to figure out a working piece order and insert/lock sequences, but I was able to manage it by hand. Figuring out the necessary unlocking rotations was also easy enough, at least after I added a map of the unfilled internal space to the solution.

Final running-time: 1 second to generate the single solution.

Bonus round, back to the King Snake. I decided to come back to this puzzle with what I’d learned from solving the others and try to generate all its solutions in a reasonable amount of time. I didn’t have any new ideas about how to frame the puzzle, but I did have some new implementation tools: pre-generating and indexing by position all legal piece arrangements, and representing puzzle states as bit-fields. These two together allow for a blazing-fast solution.

Final running-time: 30 seconds to generate all four solutions7.

If you own this puzzle, you may at this point be thinking “Wait, what?” The marketing copy and provided instructions for the King Snake claim there are only two solutions. But nope, four. The two extras solutions are very similar to each other, but are quite distinct from the two “official” solutions, and none are simply symmetries of the others.

“Cheating” — hah!

Puzzle-solving code available for your edification.

1 Best Christmas present ever, seriously.

2 For comparison, chess apparently has between 1e43 and 1e50 legal board states.

3 Most actions on a the puzzle-state are just a few bitwise operations.

4 Which I really like putting in all caps, for some reason.

5 Yeah, the name confuses me too.

6 But not reflections, what with three dimensional limitation and all.

7 FYI, I number from the opposite end than the provided solutions.

Possible lesson: don’t get upset with a book for not being a completely different book the author hasn’t written yet, but will later.

I few months ago I bought The Definitive ANTLR Reference by Terence Parr1. The book’s subtitle is “Building Domain-Specific Languages,” so I was rather disappointed when I found out that it has absolutely no information on building domain-specific languages — or any other applications — using ANTLR. It’s a great ANTLR reference, but doesn’t have any examples of using ANTLR to do anything other than just parse (and emit and handle parsing errors). Without any practical examples, it took bit of head-scratching on my part to realize how to even e.g. make my Z-code assembler available to my ANTLR-generate AST walker.

But today I learned that Terence Parr has also written another book titled Language Implementation Patterns. I haven’t had a chance to read much of it yet, but it looks like exactly what I wanted in the first place — a guide to actually writing various sorts of applications which involve parsing languages, mostly using ANTLR-generated parsers. This book has the oddly-similar subtitle “Create Your Own Domain-Specific and General Programming Languages,” but which seems rather more apt here. In any case, I’m looking forward to it.

And on a side note, Parr’s publisher, the Pragmatic Bookshelf, kicks ass. Their e-book deployment is even better than O’Reilly’s. While both provide PDF, Mobipocket, and EPUB versions for perpetual re-download, the PragProgs also (a) offer almost their entire catalog as e-books, and (b) make e-book editions available as “beta books” several months prior to the print release date. In fact, Language Implementation Patterns is currently only available in an e-book beta version. But available it is, for delicious pre-final-draft reading by the adventurous.

1 Primary author of ANTLR, so you can see the draw.