Hash Tables and a Wee Bit of Sugar in Common Lisp

In topic Article :: Published Monday, January 26, 2009

Updated Saturday, April 4th, 2009

Update 2009-01-26: Zach Beane pointed out that &rest lists are useful. The reader macro was written by Rainer Joswig in a Reddit-comment. Cookies to Zach and Rainer!

There's been some discussion in the Reddit crowd about the supposed nasty syntax of Common Lisp's hash tables. Well, there is no hash table syntax, only function calls. Compare the Python version:

>>> dict([("Abe", 26), ("Lincoln", 25)])
{'Lincoln': 25, 'Abe': 26}

to the Lisp version:

(let ((h (make-hash-table :test 'equal)))
  (setf (gethash "Abe" h) 26
        (gethash "Lincoln" h) 25)
  h)

Alright, a bit tedious. There is precious little sugar in Lisp. What you can do, instead, is to make a small convenience function. It was suggested at Response to: Problems with Lisp to make a fairly straight-forward translation of alists into hash tables:

({} '(("Lincoln" . 26) ("Abe" . 25)))

A bit verbose, though, and if we're going to throw away the extra conses, there's really no point in making it an explicit alist. We might as well use a prettier syntax, how about:

(defun {} (pairs)
  (let ((h (make-hash-table :test 'equal)))
    (loop for (key value) on pairs by #'cddr do (setf (gethash key h) value))
    h))

Usage:

* ({} '("abe" 26 "lincoln" 25))
#<HASH-TABLE :TEST EQUAL :COUNT 2 {...}>
* (loop for key being the hash-keys of *
  do (format t "~A is ~A years old~%" key (gethash key *)))

abe is 26 years old
lincoln is 25 years old

Better?

Yes, but we can make it better yet. How about just throwing all arguments into a list? Great for the trivial case where we just want a simple hash table. Enter &rest argument lists:

(defun {} (&rest pairs)
  (let ((h (make-hash-table :test 'equal)))
    (loop for (key value) on pairs by #'cddr do (setf (gethash key h) value))
    h))

And we got rid of the enclosing list:

({} "abe" 26 "lincoln" 24)

Excellent! Reader macro version left as an exercise to the reader...

Responses

You can follow any responses to this entry through the RSS 2.0 feed.

bearophile said on February 6th, 2009 at 10:26 (link)

In Python the syntax for dicts it just:
```
{'Lincoln': 25, 'Abe': 26}
```
Or:
```
dict(Abe=26, Lincoln=25)
```
You never write:
```
dict([("Abe", 26), ("Lincoln", 25)])
```
Mikael Jansson said on February 6th, 2009 at 10:34 (link)

I forgot about the second version which is indeed less verbose than what I wrote.

The point was that without syntactic sugar, i.e., your first version, you’d have to write it out fully. In Lisp, where you don’t have shortcuts, it would be enough to sprinkle some grains on the basic functionality and come up with something fairly closely resembling the native Python {} syntax. Or, like I concluded, a reader macro.

Which is to say, while Lisp has little sugar, it allows you to invent your own preferred syntax, making the original posts’ argument a moot point in practice.
bearophile said on February 6th, 2009 at 11:23 (link)

The following syntax is bad, because there’s no guide for the eye to tell apart pairs:
({} 7 5 5 55 2 15 25 5 1 9 5 11 57 9)
{} is ugly as function name, better something like dict or hash or make-hash something else.
Can some separator be added? Is this possible?
(dict 7 5; 5 55; 2 15; 25 5; 1 9; 5 11; 57 9)
A possible syntax for the empty hash:
(dict)
Finally, a really important thing the author here has missed is that such hash syntax has to become standard, so everyone uses it, and you can understand it as soon as you see it. If everyone re-invents something different it’s nearly useless.
Mikael Jansson said on February 6th, 2009 at 11:36 (link)

The key is to create a readable notation for hash tables. That way, everyone will be able to understand that it is, indeed, a hash table.

Adding separators for the sake of readability is trivial, it is just a simple matter of skipping that item when deconstructing the list. Semicolon is not possible, as it’s reserved for comments.

If you’re not picky about the keys, however, there is already built-in syntax for mappings, called property lists:
```
* (defvar *presidents* (list :abe 25 :lincoln 26))
* (get *presidents* :abe)
25
```
where (list) would be the empty mapping.
bearophile said on February 6th, 2009 at 13:28 (link)

If that nice syntax already exists, what’s the point of this whole blog post?
Mikael Jansson said on February 6th, 2009 at 13:38 (link)

Property lists are less efficient than hash-tables for larger sizes.

But you’re missing the point. Lisp is the programmable programming language.

You need new syntax? Add it! Try doing the same thing in Python.

In fact, add do...while to your current version of Python as portable Python code so people won’t have to replace their Python with your Python.

In Lisp, that’s just a defmacro away. How much work is it in your language?
Mikael Jansson » Blog Archive » Jag, en arg LCHF-människa? said on March 5th, 2009 at 21:21 (link)

[...] Hash Tables and a Wee Bit of Sugar in Common Lisp [...]