Often the best way to get the “feel” of a new language is to look at some real code. Preferably code that does a non-trivial task, but a task with which you are generally familiar. To this end I’m posting here the code for a binary-tree representation of a dictionary. There are three files: the binary tree itself, a test suite using gUnit, and a simple visualization of the tree using Knuth’s algorithm. (This algorithm never re-uses a horizontal position, so it’s not much good for large trees.)

I was particularly pleased with the way that Grace’s blocks (λ-expressions) and lexical scope simplified the tricky problem of inserting nodes into the tree. What’s the “tricky problem”? To insert a node, one has to update a reference in an ancestor node, which might be the root, or the left of a parent node, or the right of a parent node. Handling each case separately leads to a combinatorial explosion of special cases. Here is the solution in Grace: at()put() is the public (interface) method, and addNode()in()setParent() the internal (confidential) recursive method that actually does the insertion.

The “trick” that lets us use the same code in all situations is for the requestor of addNode… to pass as an argument the code snippet that, when executed, will update the appropriate parent reference. The same trick works for deleting a node; see the whole module here.

If you want to try out this code yourself, you can do so using the web-based IDE (which you should open in Chrome or Firefox). Here is the tree visualization code running in the IDE.