Turtles all the way.

January 18, 2008 at 12:24 am · Filed under Uncategorized ·Tagged Haskell, HStringTemplate

HStringTemplate had a very irritating hack in it up until about twenty minutes ago. Every time we worked with some of StringTemplate’s fancier constructs, particularly chaining template application (i.e. $foo:bar():baz():etc()$ which applies foo to bar, feeds it to baz, then feeds it in turn to etc) or using a template as an attribute (i.e. ${$foo$}$ which creates an anonymous template, that in turn grabs foo from the outer scope) the value had to be rendered down to a string before passing it back into the next scope. Now, this normally would have been unfortunately ugly, but not that harmful. However, because of the wrapping and indentation support that HStringTemplate provides, it meant that we couldn’t get proper indentation in such a case since we didn’t know where to wrap the expression yet (i.e. how far it would be indented) at the time we evaluated it.

That last ugliness is now gone. The approach is genuinely turtles all the way down, as the saying goes. This not only makes things work right, but it makes the entire data model cleaner and more efficient. And, while there were a number of changes to type signatures to pass the right information around (sometimes I feel type signatures are the Dorian Gray’s portrait of the Haskell world — the more elegant your code gets, the more complicated and unwieldy your signatures), the end result required only three changes to lines of actual code, and actually resulted in something slightly smaller!

I hope to get to this in a later blog post, but the lesson is that static typing and type inference aren’t just about bondage and discipline and safety. They can also give you a sort of incredible expressive power, where the information on what you’re doing is carried around invisibly in the type system as a sort of secret parameter that can give you a great deal of control over the way your code actually behaves. While the Java version of StringTemplate, for example, uses separate renderers that control how output displays, everything in HStringTemplate (lexing, parsing, construction of functions, establishing pretty-printing relationships) can be done in a single pass. And thanks to laziness and higher-order functions, this pass can produce partially applied functions where everything else (such as indentation levels) can be figured out in a second single pass at runtime. (NB: this idiom, completely natural to Haskell, is sometimes known as runtime compilation although it’s a different use of the term than is usually the case.)

So what does that mean to the end user? Well, you can do this, for one:


> putStr $ PP.renderStyle (PP.style {PP.lineLength=80}) $ toPPDoc $
  setAttribute "foo" [[(1::Double)..30],[200..230]] $ newSTMP
  "Some long text: $foo:{Some label: [$it$]}:{#$it$#};separator=', '$ END"


Some long text: #Some label: [1.0, 2.0, 3.0, 4.0, 
                              5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 
                              14.0, 15.0, 16.0, 17.0, 18.0, 19.0, 20.0, 21.0, 
                              22.0, 23.0, 24.0, 25.0, 26.0, 27.0, 28.0, 29.0, 
                              30.0]
                 Some label: [200.0, 201.0, 202.0, 203.0, 204.0, 
                              205.0, 206.0, 207.0, 208.0, 209.0, 210.0, 211.0, 
                              212.0, 213.0, 214.0, 215.0, 216.0, 217.0, 218.0, 
                              219.0, 220.0, 221.0, 222.0, 223.0, 224.0, 225.0, 
                              226.0, 227.0, 228.0, 229.0, 230.0]# END

So what’s happening with this expression? The newSTMP call, as usual, parses a string into a template. The setAttribute call inserts, “foo”, a list of two lists of doubles, into the template. The toPPDoc call evaluates the template in the context of the attributes we’ve set, and returns a Pretty Printer Doc. The render call is to the Text.PrettyPrint.HughesPJ library (which I’ve imported, qualified as PP), and tells it how long we want the lines to be, and finally, the putStr call displays the returned string with newline characters appropriately rendered.

Now onto the mechanics of the StringTemplate itself. First we print some text, and then foo, as a list, is iterated over and repeatedly passed into the next part of the expression. The sublists of foo are each printed, preceded by “Some label: ” and surrounded in braces. The values of each sublist are separated by commas, because we set that option in the top level expression, and that gets propagated downwards as well, and then the whole resulting expression gets wrapped in pound signs by the final template application. And the new cool part is, because everything is “turtles all the way,” those sublists are not rendered and wrapped until the entire shebang is called, meaning that not only do we preserve multiple levels of indentation, but that when those sublists are displayed, everything, including the pound signs that were only inserted *after* we evaluated the sublists of foo, is taken into account such that they indent and wrap properly.

The beauty of programming in a language that supports abstractions as elegantly as Haskell does is that doing it this way not only gives nicer performance, and nicer features, but that it creates cleaner, simpler code. Implementing this feature properly didn’t mean fighting the language, but just giving into to what the types had been whispering to me all along.

Permalink