Buckets vs. Alists? 3 points by evanrmurphy 2558 days ago | 5 comments I was reading The Art of the Interpreter [1] and was surprised by the implementation of symbol tables/environments:A symbol table is represented as a list of buckets; each bucket is a list whose car is a list of names and whose cdr is a list of corresponding values. {Note This ain't A-lists} (page 11)I had never heard of buckets before, though I understand their structure now [2]. What I don't understand is the tradeoffs: why would you want to use a bucket over an alist? I can't see any performance / algorithmic difference yet except exchanging some cars for cdrs, but I'm probably missing something.Update: Ah, I didn't realize the "{Note This ain't A-lists}" was an endnote. Still reading it, but their choice seems to be about both aesthetics and efficiency.To summarize, they say the routines they use to act on buckets (bind and lookup) have nicer names than the ones Lisp 1.5 uses to act on alists (pairlis and assoc). More importantly, "that the number of conses use to bind a given number of variables is usually smaller."---[1] http://www.scribd.com/doc/2416804/Lisp-Art-of-the-interpreter-sussman[2] A simple example in case anyone else was unfamiliar with buckets. First, an alist that maps some symbols to values:`````` (= al '((a 1) (b 2) (c 3))) `````` Or, if you subscribe to http://arclanguage.org/item?id=13387:`````` (= al '((a . 1) (b . 2) (c . 3))) `````` In either case, the corresponding bucket would be:`````` (= bucket '((a b c) . (1 2 3))) `````` Alternatively written without dot notation as:`` (= bucket '((a b c) 1 2 3))``
 1 point by evanrmurphy 2555 days ago | link > Well, there are definitely fewer conses in ((a b) 1 2) than in ((a 1) (b 2)), but ((a . 1) (b . 2)) has them both beat. (Maybe I'm missing something.)I resorted to cons counting to confirm it for my own simple mind and... you're correct! ^_^`````` ; bucket (5 conses) ((a . (b . nil)) . (1 . (2 . nil)) ) ; "frugal" alist (4 conses) ((a . b) . ((b . 2) . nil)) `````` Note, however, that it's a constant difference of 1 cons. The difference doesn't grow with the size of the data, so it's rather insignificant.Sorry I don't have time to respond to the rest of your comment right now.-----