Monday, December 31, 2007

2007 Year-End Language Version Wrapup

Following the 2006 language version wrapup, we present the latest stable version or other improvements to some of our favorite languages and tools at the end of 2007 :

While I don't use all of these a lot (or even a little, like Ada), they're all tools close to me.

As we close the new year, I'd like to invite my readers to leave a comment (can be done anonymously) stating (1) your #1 most used programming language this year (2) a language you'd most like to try out.

Friday, December 28, 2007

Revisiting Tree Traversal Patterns

Experts may disagree, but I like to agree with LtU that the killer app for functional languages is compiler writing. I propose that one simple reason for the success is structural pattern matching, because it lets you write compact and natural tree traversal code:

datatype Expr = Atom of string | Pair of {car : Expr, cdr : Expr};
fun textFormatter(Atom a) = a
| textFormatter(Pair{car=x, cdr=y}) =
concat["(",textFormatter x,",",textFormatter y,")"]
Do OO languages have any hope of approaching this kind of conciseness? That led to my question in Tree Traversal in Object-Oriented Languages "which of these two techniques do you like better and is there a better one?"

In that post JFKBits reader "peter" commented my "event model" was just the Visitor Pattern. I'd had another idea of what the Visitor Pattern was. After some digging I learned there are two variations both considered the Visitor Pattern, and today we'll look at what difference it makes for writing programming language processors.

Why Tree Traversal Matters

For the programming language tool writer, a tree traversal pattern is like the for loop (or other iteration pattern) for most other programmers -- after all, your bread and butter data structure is the tree, not a flat sequence.

In a word, tree traversal matters if you traverse a lot of trees - sum up the number of traversals you write in a single program or the number of processors you write over time.

You could be writing a series of toy interpreters each with a single eval loop, like this one for Scheme and this one for Lisp both written in Python.

On the other hand, you could have one large project with many phases. I have a 12,000 line compiler for Ila written in Standard ML with five major tree traversals areas in the compiler core, plus some utility traversals like error message pretty printing and a Javadoc-like HTML generator. Writing that compiler one time impressed me that tree traversal pattern matters, especially since there were quite a few node types.

Further, your choice of tree traversal pattern will immediately affect the way you think about your algorithm. I think one variation of visitor makes it unnecessarily difficult, and one makes it quite a bit more natural.

Visitor Pattern in General

The visitor pattern is generally described as a way to decouple algorithms that operate on a data structure of related node classes from the node classes themselves.

The double-dispatch technique is often described in presentations of visitor. To use the visitor pattern, take the tree object t to traverse, a visitor object v corresponding to the algorithm (type checking, syntax highlighting) and call the virtual method t.accept(v) (this is the first dispatch). The node subclasses (Atom, Pair) each have an implementation of accept that calls the visitor method corresponding to their particular class (the second dispatch, hence "double dispatch"). That way the visitor can be written as a collection of methods that each know the exact node subtype they're dealing with.

Visitor Pattern for Language Processors

What's often glossed over is the critical question where is the knowledge about a node's children? In other words, where does the recursion/iteration occur - in the acceptor or the visitor? I originally imagined the visitor pattern was defined to mean recursion occurs in the acceptor. Either way is considered an accepted variation of the pattern, but I claim it makes a substantial difference for most compiler algorithms.

Recursion in the Acceptor

Here's recursion-in-the-acceptor for the Lisp structure above:

public abstract class Expr
public abstract void accept(Visitor v);

public class Atom extends Expr
public String value;
public void accept(Visitor v)
v.visit(this); // Atom has no children, simple accept

public class Pair extends Expr
public Expr car;
public Expr cdr;

public void accept(Visitor v)
car.accept(v); // children visited in the acceptor
v.visit(this); // postorder traversal

public interface Visitor
void visit(Atom a);
void visit(Pair p);
Now, given those definitions, how would you write the TextFormatter iterator that produces the same output as the SML example given earlier?

Recursion in the acceptor introduces some problems. One is that it fixes the traversal order -- postorder in this case. Now the iterators need to know what the traversal order is, a dynamic property that must be remembered when writing each visitor. Also, what if postorder isn't what you need? In particular, in order to generate the grouping parentheses, which are associated with the Pair, you would like code associated with the Pair to run both before and after visiting the Pair's children. Further, you wanted to generate a comma in between -- that means a visit in between the two children. You're forced to write something like this:

import java.util.Stack;
public class TextFormatter implements Visitor
private Stack m_stack = new Stack();
private String m_result = null;

public void visit(Atom a)

public void visit(Pair p)
// We need to know the order of children traversal. Hmmm.
String cdr = (String)m_stack.pop();
String car = (String)m_stack.pop();
String value = "("+car+","+cdr+")";

public String toString()
if(m_result == null)
m_result = (String)m_stack.pop();
return m_result;
Using an explicit stack is not 100% always bad -- if you tend to process programs with extremely deep nesting, you may hit your implementation language's control stack limit, but overall this is not the style in which I'd prefer to write dozens of visitors.

Note that the SAX parser model, which follows recurse-in-the-acceptor, addresses the fixed-order problem by having multiple visit methods for nodes with children: it has startElement as well as endElement, and the like.

The other problem with this approach is that not every visitor needs to visit every node. Some may only need to go so deep. That brings us to the recurse in the visitor approach, which I would consider the recommended one for programming language processors.

Recurse in the Visitor

This approach has the advantage that the accept method is always the trivial v.visit(this), and the visitors can be written in a more natural style:

public class TextFormatter implements Visitor
private StringBuffer m_buff = new StringBuffer();
private String m_result = null;

public void visit(Atom a)

public void visit(Pair p)

public String toString()
if(m_result == null)
m_result = m_buff.toString();
return m_result;
Is this what I'd like to write as a functional programmer? Of course not. I'd prefer to have accept return a value, so I could write visit(Pair) more like this:

public void visit(Pair p)
Which of course means that visit should return a type, instead of accumulating results in a member variable. But then we need to know what type to return, which in Java most likely needs to be Object. It all gets ugly again.

Conclusion - Still Not Perfect

So, a visitor with recursion in the visitor is acceptable, but still not ideal, and it doesn't come close to the conciseness of pattern matching. The accept method needs to be added to each node class, which is a pain for the rapid prototyping, and the visitor of its nature requires that you accumulate state in member variables instead of using a functional style of combining returned results in a single expression.

Still, I'm just one guy with a certain slice of experience --- is there a better (more compact, less boilerplate) tree traversal technique for OO languages?

Or is this really the ultimate pattern, OO loses this particular battle, and Nice multi-methods or Scala case classes or other language extensions become necessary parts of an OO-capable language that supports programming language implementations as well as the functional languages?

Thursday, December 27, 2007


Inspired by Jam-Packed FoxTrot I'm declaring FoxTrot the Official Cartoon of JFKBits:

Jason: So if the Times Square ball doesn't fall at midnight...
Does that mean the guy who drops the ball dropped the ball?
And if he drops it correctly, has he then not dropped the ball?
Roger: I could use a refill on the champagne, Hon.
After all, if the Official Cartoon doesn't have impredicative humor, what good is it?

Wednesday, December 26, 2007

XEmacs Groks file://path

On a whim, I just found out you can paste this into XEmacs' mini-buffer when you Ctrl-x Ctrl-f to open a file:

It's nice to know XEmacs understands file:// URLs, and I expect this now falls into my recommendation as a best practice for user interfaces.

Unfortunately, XEmacs won't import a web page that way: you can't Ctrl-x Ctrl-f and edit the news.

Friday, December 21, 2007

Lighthearted: Roundoff Error

I'm gettin' nothin' for Christmas
Amazon dot com is mad
I'm getting nothin' for Christmas
Cuz I reported their bug
On my blog


Inspired by the buy-this-get-that-free promotion where we put 2 of this and 3 of that in the shopping cart, and all 3 thats were accounted to be free. Don't want any server queue riots now...

Wednesday, December 19, 2007

Tree Traversal in an Object-Oriented Language

There are two methods I know of for representing an expression in classes: the event-model and the subclass model. The main problem I see is in how to traverse the tree without replicating verbose "if this type, then" boilerplate and without piling all the code that might ever use the expression into the same sets of classes. I'm merely observing in this post, if you have any opinions on which you like better, let me know.


For both of these, w'll use the following grammar:

E -> INT | STRLIT | VARREF | List[E,...] | E(E) | FN(x){E}

An expression is either an integer constant or a string literal, a variable reference, a function call, or a function definition.

Subclass Model

In the subclass model, we'd start with a class for E itself:
class E
We'd augment E with lots of handy utility functions and fancy abstract (pure virtual) methods. Then we'd define a subclass of E for each of the possible "actual" expression types:
class Int extends E
int k;

class StringLit extends E
String s;

class Varref extends E
String x;
ScopeLevel level;

class EList extends E
List elts; // List of E objects

class Call extends E
E function;
E argument;

class FnDef extends E
String x;
E body;
One thing I don't like here is adding a virtual method to E to handle anything anybody might do to an expression. Type checking? Add a typeCheck method. Code generation? Add a generateCode method. Optimization or source transformation passes? Good luck with that. I think it's sticking too much unrelated code into each class.

And if you separate your concerns and have code elsewhere that gets handed E objects, you end up with this structure that suggests you haven't learned about old-code-calls-new-code virtual methods yet:

void f(E expr)
if(expr instanceof Int)
else if(expr instanceof StringLit)
else ...
else // Oh no!
;// It wasn't one of the types I thought it could be!

Event Model

The other model is already known in Java programming as the event model, as in the way SAX parsers work. I like to think of the True Origins of this concept, in lambda calculus encoding. Every basic type we know of in the functional languages like ML (tuples, lists, integers) has an encoding in the pure, 3-form lambda calculus. And the type we're talking about here is called a sum type. Sum is related to "OR" just as product is related to "AND." An expression is an int OR a string literal OR a variable reference, and so on.

Here's what I like about the event model: it factors out the "if expr is this choice, call this; else if expr is that choice, call that..." code to one place and you are freed up to write functions that are given the exact subtype:
interface EHandler
Object handle(Int i);
Object handle(StringLit s);
Object handle(Varref v);
Object handle(EList l);
Object handle(Call c);
Object handle(FnDef f);
Now your language processor phases can be written in terms of EHandlers:
class TypeCheck extends EHandlerImpl
Object handle(Int i)
return Types.INT;

Object handle(Varref v)
// look up v. if unbound, flag an error
// if bound, return its type

Object handle(Call c)
Object fnType = this.handle(c.function);
Object argType = this.handle(c.argument);
// check that fnType is a function,
// make sure fnType's range type matches argument type
// return fnType's return type
This is fine as long as you only need to look at one level of the tree at a time. And if we wanted these handle functions to return a type other than Object, or if we want to add another argument to each handle function such as an environment or accumulator object (not likely since we could make it a class member, but conceivable) we'd need to create another interface and/or abstract base class.

This second one appeals to me because I'm so accustomed to ML's pattern matching facility (which also appears in other languages like Haskell and Scala), which is the sweetest of syntactic sugar for sum types, and sum types in turn are the bread-and-butter of language processors.


Either of these two approaches seems fine for small and simple expression tree types (meaning the number of different types of nodes, not the size of a particular tree), but I think there's got to be a better way for representing sum types in classes that can handle larger sum types and more complex processing needs. Do you know what it is? Leave a comment or email to jfkbits at the mail domain of google.

Update 12/20: Fixed code formatting.

Monday, December 17, 2007

Your Idea on RAILs

Read this with the voice of Deep Thoughts by Jack Handy:

If you want your code to survive,
you want to put it on RAILs -
a Redundant Array of Inexpensive Languages.
That way, if one language fails, your ideas will still be around in one of the other ones.

Saturday, December 15, 2007

You Want Electrical Grounding

We just moved our home office to a different room with two-prong outlets. One outlet was on the fritz, so it got my attention enough to realize the lack of a ground connection was probably not a good thing. I wanted to understand it better, so I consulted the good ol' Electrical Wiring FAQ (written back in the days when FAQs weren't written by marketing people).

The FAQ first explains that without a ground, your surge suppressor is working at a disadvantage:

A word about grounding: most suppressors and EFI filters
require real grounds. Any that don't are next to useless.

For example, most surge suppressors use MOVs (metal oxide
varistors) to "clamp" overvoltages. Yes, you can have a
suppressor that only has a MOV between neutral and hot to
combat differential-mode voltage excursions, but that isn't
enough. You need common-mode protection too. Good suppressors
should have 3 MOVs, one between each pair of wires. Which
means you should have a good solid ground. Eg: a solidly
connected 14ga wire back to the panel. Not rusty BX armour or
galvanized pipe with condensation turning the copper connection
And then it goes on to give three more good reasons to have a real ground installed on the outlets where your computer lives:
Without a ground, a surge or spike is free to "lift" your
entire electronics system well away from ground. Which is
ideal for blowing out interface electronics for printer ports

Secondly, static electricity is one of the major enemies of
electronics. Having good frame grounds is one way of
protecting against static zaps.

If you're in the situation of wanting to install computer
equipment on two wire groundless circuits take note:

Adding a GFCI outlet to the circuit makes the circuit safe for
you. But it doesn't make it safe for your equipment - you need
a ground to make surge suppressors or line filters effective.
If you ever open up the case and have the habit of discharging static electricity on the metal frame, it's not going to do any good if the case isn't actually connected to ground.

This has been a public service announcement about the importance of upgrading your hardware infrastructure.

Friday, December 14, 2007

TBB's parallel_for

Today I wanted to tell you about a very simple but interesting function, parallel_for, included in the Intel Threading Building Blocks (TBB) C++ library (available under either a commercial license for a fee, or as a GPL open source free library). It does the work of partitioning an embarrassingly parallel loop onto different threads, and all you need to do is write a couple of small adapter classes.

The sequential loop might be this:

for(i=0; i < vec.size(); ++i)
out[i] = vec[i]->serialize();
The parallel version requires that we abstract the loop into a Range and a Body, both classes, and let TBB partition the vector and assign chunks of the loop to different threads. You don't need to create the threads. The call site above would change to something like
parallel_for(Range(vec), Body(vec));
The algorithm uses methods you define in Range to partition the entire range into chunks of the vector that you (or the library code) decide is just small enough that there's no more parallelism to exploit but not so small that scheduling overheads eat into the benefit. A Range needs to implement methods
bool empty() const
bool is_divisible() const
Range(Range& original, tbb:split)
The empty predicate is used to know if a range is empty and thus can be abandoned. The is_divisible method implements your grain size policy, e.g. is_divisible returns true unless there are less than 1000 elements.The copy constructor actually performs a split. This is a classic C++ idiom, the constructor creates the new object representing one part of the range, and the original object being destructively updated to represent the other part of the range. I imagine these Range objects as being quite lightweight, containing perhaps begin and end pointers or array indices into the original collection.

Once TBB has gotten a range of the desired grain size, it gets put onto a thread queue for execution by invoking the Body's function operator:
void operator()(Range&) const
Invoking the function operator on an object looks just like the object is a function; a Body object b's function operator is invoked b(r).

The trivial extra work in wrapping your collection in these Range and Body classes is rewarded by the fact that you don't need to write a line of thread-aware code to get your loop partitioned, and that you can take advantage of the thought someone else put into how best to do the partitioning and queuing.

TBB has taken some insights from Cilk for scheduling, and while it splits your range depth-first (splits a non-empty range and recurses on the left range until reaching a non-divisible range), but "steals" bread-first. The insight is that a thread should be scheduled with parent/child and similar neighboring ranges to take advantage of cache locality between the ranges in the same CPU core. Stealing refers to the way that a thread's queue is replenished when it is emptied, in that an entry from a randomly selected alternate thread's queue is removed.

Wednesday, December 12, 2007

Things to Do With Your Programming Language Course

It's finals week across the country, and thousands of computer science students are finishing up a programming language course. At least a handful of these have been infected with the fascination of the subject, and I hope to meet them someday. From the enthusiast to the couldn't-care-less, here are my thoughts about where you can go from here with one programming language course under your belt.

Going Pro

Take more classes, participate in an open source language project, go to grad school, and get a job with a company that makes a compiler or interpreter (IBM, Microsoft, Wind River). Remember that there are lots of languages with a smaller reach that still need people to work on them. Embedded systems have lots of chips (purpose-built CPUs and microcontrollers) that need compilers and development environments.

Programming Tools Development

Similar to Going Pro. Not every parser is feeding a code generator. Join a team making an IDE, an IDE plugin, a code formatter, or a code checker (a la LINT). Eclipse puts this category within reach of anyone (so did EMACS). In order to develop at this level you probably want to take at least one more course or do a semester long project to have a fighting chance of getting enough experience.

In-House Tools Development

The need to make sweeping changes or do some kind of transformation on a code base comes up all the time on large projects. I should probably say the "opportunity" rather than the need, because some problems that could be solved by a transformational tool will be worked around. But here's where a little initiative and paying attention during those parsing lectures will pay off.

Better Programming and Debugging

Even if you don't directly use your programming languages course, even if you hated it, if you took the right kind of course you will have your mind trained in ways that make you a better programmer. It's not a substitute for reading good code and learning from experienced practitioners, but it is similar to learning how to disassemble, clean, and reassemble a car engine blindfolded. It's analytical training for a language, you see what parts compose the tokens and phrases of the language, and see how they're combined into your program. It helps dispel myths about how your program is likely to work under the hood. This of course is especially true if the language you implement is similar to the language you write in, but if you can't go too far wrong working with a language more "interesting" than you're likely to work in.

Even the time you spend studying language design is not wasted. At some point, programming on a large team involves discussions and development of a coding standard for the group. These discussions are in a sense exercises in language design, because a coding standard effectively limits the expressive power of a language into a subset of the language that everybody is comfortably working with.

Recommended Reading

"Essentials of Programming Language" by Friedman, Wand and Haynes. Build up your knowledge of interpreters and compilers, starting with a simple lambda calculus, then to Scheme, building up to the powerful and high-performance techniques of continuation-passing style and tail recursion. Sometimes used as a text in PL courses. Maybe you like my arch-geek friend Tony will use your newfound knowledge to spend your Christmas break writing a Scheme compiler for your HP scientific calculator.

"A Retargetable C Compiler" by Hanson and Fraser. A funny book, it uses literate programming to document and explain the implementation of lcc, a C compiler used to compile Quake III. From memory management (arenas with constant time deallocation) and string hashing, the authors show and explain their C code from the bottom up. The ANSI C style is a little odd, but for the modern student, C will perhaps seem odd anyway.

Friday, December 07, 2007

Hashtables and Wedding Days

While using a commercial STL hash implementation a few years ago, my program appeared to hang (the old halting problem dilemma; is it in an infinite loop or just slow?) on a hash table insert. I got a trace of the key/value pairs inserted and wrote a minimal program only doing the inserts. That hung too. Sent it off to the vendor who found a bug in his bucket rebalancing code.

He sent back a patch for the implementation with the advice to get a better hash function, since a lot of the inserts were hashing to the same location. Using the key object's address as the hash value was a poor choice: it was word aligned, and the lower 2 bits were always zero. So we changed the hash function to right-shift the address, and with the patched code, we were off and running again.

Jeff Atwood draws an analogy of the birthday paradox and the probability of two objects hashing to the same location. The problem with my poor hash function resembles the Wedding Day Paradox, as I'm calling it. I recently had a conversation with a coworker:

Me: My anniversary is coming up.
Coworker: Mine too! How many years?
Me: Four.
Coworker: Me too. When were you married?
Me: October, how about you?

We quickly discovered we both had our weddings fall on the same day of the same year. We realized this should not surprise us, since most weddings occur on a Saturday. Knowing that we were both married in the same month of the same year gives only 4 or 5 choices. This effect is even more significant than the seasonal variations of birthdays with more concentration in some ranges than in others.

I've filed this under bugs, so let this serve as a cautionary tale if you undertake to do your own hash functions; consider well the distribution of your keys. Also, if you write a hash table implementation, include in your test suite a scenario where the hash function is really dumb.

Wednesday, December 05, 2007

Type Directed Code Search

We live in a Golden Age. You can buy Ubuntu desktop computers at Wal*Mart for under $200, there are more choices of programming language than ever, and their software libraries are rich and well-designed with lots of orthogonality. Let's say you're learning one of these new libraries, you're feeling all baroque and XMLish, and you set your heart on acquiring an org.w3c.dom.Document object. Where do people get those, anyway? Where's the parser that spits it out? After much digging, you find that a javax.xml.parsers.DocumentBuilder will make you your document. Ah, but that's an abstract class. Now, who makes DocumentBuilders? DocumentBuilderFactory, of course. This kind of searching gets old quickly.

Maybe this kind of run-around is unavoidable when learning libraries, and documentation and books can certainly help orient you, but there's another tool for our kit which may help in some cases. What might be useful is an index keyed by type that points to methods using the type, either in parameters or in the return type. This index could answer the question "where can I find methods that return type X?" or "what are all the methods that take an X as an argument?" Such an index could help both in learning as described above but in any activity where you need to search the code.

Eclipse goes pretty far in implementing this, not far enough, but enough to hint at what we could do. In the dialog below I've typed to search for "DocumentBuilder", selected to Search For "Type", and limited the search to "References". Ideally I'd like to limit the search to methods returning the given type; I want to know what methods generate this type. Also note that we've checked "JRE libraries" because we want to know what built-in library generates the DocumentBuilder:

The search results:
This feature seems a natural for Java since it is both statically typed and has the necessary reflection to allow a tool to do the analysis. However, it looks like type inference is coming to the dynamically typed languages too, including Ruby and Javascript and even Wasabi. Since types are not as much part of their language, it may not be as natural to think of searching this way, but the need will grow as more and bigger applications get written in these languages.

With a type-informed search, you can do debugging research. One thing I've seen with large team projects is the bug that has an exact duplicate lurking elsewhere. For example, you find a URL object for a web server has omitted setting the port number via the config.getPortNumber() call. Since everybody tests with the well-known default port 80, things appear to work, but a real customer configures with a different port and suddenly links break. You track it down, add the right calls, and close the bug only to have the customer call back with a different broken link, same root cause but in a different spot in the code. Once you identify a bad pattern like that, you typically want to look for other places it might occur. To find this pattern you could do a text search for URL, but a type-informed one or an AST-search is likely to cut down on unrelated references to "URL" in comments and other areas.

In conclusion, this is yet another application of type information. It's a little on the fringes, perhaps not an everyday tool, but for learning a new library, for doing research prior to refactoring or for debugging, it could be a standard feature in IDEs of the future.

Monday, December 03, 2007

Bonus Links - Jonathan Coulton Music

For your listening pleasure, allow me to recommend this twin spin from Jonathan Coulton, your new favorite Internet singer/songwriter:

1. Chiron Beta Prime (mp3), a little relief from the "Well, Our Producer Says We Had to Record this Christmas Song (And We Only Have Two More Verses To Go Now)" music on the air since last week.

2. Code Monkey (mp3), which can be accompanied by the mesmerizing Guitar Hero wannabe video that visually demonstrates the choppy power chords are a dovetail fit to the monkey-talk lyric style:

Code Monkey get up get coffee
Code Monkey go to job
Code Monkey have boring meeting
With boring manager Rob
Rob say Code Monkey very diligent
But his output stink
His code not functional or elegant
What do code monkey think
I say let's take up a collection and commission a work from this guy. He, ahem, rocks. Chords, lyrics and tab available for you who know how to use them.

What one programming language design and implementation topic would you pay real money to hear a song about?

Update: Corrected lyrics. Revised line break formatting.