new contributed library: <treap>

[Neel Krishnaswami <neelk@xxxxxxxxxxxx>]

Hi all,

I wrote a new collection class in goo, and stuck it on the wiki (under
GooLibs). I'll blurb it a little, so you know what I'm talking about,
and then write about what I found easy/hard about the experience.

o <treap> is a new mapping class that implements purely functional
  balanced binary trees. It has O(log n) expected-time insertion,
  search and removal. Like all binary trees it uses comparison to
  order its elements, and <treap> currently uses the system '<'
  comparison. If you want to use value equality rather than '==', this
  will do it for you.  Finally, the fact that it's functional means
  that adding or deleting elements gives gets you a new tree, which
  makes it handy if you need to save old versions or need a
  thread-safe mapping class.

Comments on writing it:

I picked a functional map to slightly push the goo collection protocol
a little, since it's a kind of collection that the protocol hadn't
been designed in mind with. Overall, the experience was fairly
straightforward, once jrb diagnosed that you have to implement the
enumeration protocol before anything else.

o That's probably symptomatic of my main difficulty: it's not clear
  which methods I must override in order to have a collection that
  works reliably with all the collection methods. It would be really
  great if there were a 'Collection-writing 101' document that
  described exactly which methods need to get overridden. Restarting
  goo again and again as methods called each other without a
  terminating base case and crashed goo was not so much fun.

  I'm still not sure I have a complete set of collection methods,
  actually. I'm sure that the set is *small*; I'm just not sure
  I got it all. (col was a last-minute addition, for example.)

o I had a similar problem with the exception system: I wasn't
  sure which exceptions to throw where, so I just used an (error
  "foo") everywhere. This is rather suboptimal, because it really
  degrades the value of the exception system for library users.

  Python is a good model here. It has a fine-grained, well-documented
  exception hierarchy, and the std library makes use of it
  everywhere. So it's easy to figure out which exception you should
  throw, and people actually do it. That annoyed me about Dylan: it
  had this mondo powerful system with restartable exceptions and
  everything, but no one seemed to make any substantial use of it.

o There are a couple of missing functions from the protocol:

  add-key: (c|<map> key|<any> val|<any> => <map>)

   This is just the dual of del. 

  fold-map: (f|<fun> init|<any> c|<col> => <any>)
    
    This is (f (f (f (f init k0 v0) k1 v1) ...))
    where ki/vi are key-value pairs.

  do-map: (f|<fun> c|<col>)
  
   This calls (f k v) on each key/value pair for side-effect. 

  These seem like obvious adds. If I understood how packers work
  there are probably analogs there, too. 

o It's also clear that the goo collection protcol is *very* heavily
  aimed at sequences and mappings. I started out writing <treap> as a
  set type, and then changed it into a mapping to make it actually
  exercise the collection libraries. Right now, I don't think sets
  fit at all comfortably into the goo collection worldview. This is
  annoying because sets are basically the only other common kind of
  collection, and it sure would be nice if goo could handle them
  easily.

o I really like how goo generates a display for a map:

  goo/user 0<= (col <treap> 1 'a 2 'b 3 'c)
  goo/user 0=> #<<treap> 1: a 3: c 2: b>

  It would be way cool if the reader could use that as literal syntax
  for any kind of map. So #<<foo> 1: "a" 3: "c" 2:"b"> would morph
  into (col <foo> 1 "a" 3 "c" 2 "b"), or something like that.

o I'd like an option to display backtraces automatically, and for
  there to be line number information in errors. 

-- 
Neel Krishnaswami
neelk@alum.mit.edu