Wednesday, April 02, 2014

Hash Maps in LFE: Request for Comment

As you may have heard, hash maps are coming to Erlang in R17. We're all pretty excited about this. The LFE community (yes, we have one... hey, being headquartered on Gutland keeps us lean!) has been abuzz with excitement: do we get some new syntax for Erlang maps? Or just record-like macros?

That's still an open question. There's a good chance that if we find an elegant solution, we'll get some new syntax.

In an effort to (re)start this conversation and get us thinking about the possibilities, I've drawn together some examples from various Lisps. At the end of the post, we'll review some related data structures in LFE... as a point of contrast and possible guidance.

Note that I've tried to keep the code grouped in larger gists, not split up with prose wedged between them. This should make it easier to compare and contrast whole examples at a glance.

Before we dive into the Lisps, let's take a look at maps in Erlang:

Erlang Maps

Common Lisp Hash Tables

Racket Hash Tables

Clojure Hash Maps

Shen Property Lists

OpenLisp Hash Tables

LFE Property Lists

LFE orddicts

I summarized some very basic usability and aesthetic thoughts on the LFE mail list, but I'll restate them here:
  • Erlang syntax really is quite powerful; I continue to be impressed.
  • Clojure was by far the most enjoyable to work with... however, doing something similar in LFE would require quite a bit of additions for language or macro infrastructure. My concern here is that we'd end up with a Clojure clone rather than something distinctly Erlang-Lispy.
  • Racket had the fullest and most useful set of hash functions (and best docs).
  • Chicken Scheme was probably second.
  • Common Lisp was probably (I hate to say it) the most awkward of the bunch). I'm hoping we can avoid pretty much everything the way it was done there :-/
One of the things that makes Clojure such a joy to work with is the unified aspect of core functions and how one uses these to manipulate data structures of different types. Most other implementations have functions/macros that are dedicated to working with just maps. While that's clean and definitely has a strong appeal, Clojure reflects a great deal of elegance.

That being said, I don't think today is the day to propose unifying features for LFE/Erlang data types ;-) (To be honest, though, it's certainly in the back of my mind... this is probably also true for many folks on the mail list.)

Given my positive experience with maps (hash tables) in Racket, and Robert's initial proposed functions like map-new, map-set, I'd encourage us to look to Racket for some inspiration:
Additional thoughts:
  • "map" has a specific meaning in FPs (: lists map), and there's a little bit of cognitive dissonance for me when I look at map-*
  • In my experience, applications generally don't have too many records; however, I've known apps with 100s and 1000s of instances of hash maps; as such, the idea of creating macros for each hash-map (e.g., my-map-get, my-map-set, ...) terrifies me a little. I don't believe this has been proposed, and I don't know enough about LFE's internals (much less, Erlang's) to be able to discuss this with any certainty.
  • The thought did occur that we could put all the map functions in a module e.g., (: maps new ... ), etc. I haven't actually looked at the Erlang source and don't know how maps are implemented in R17 yet (nor how that functionality is presented to the developer). Obviously, once I have, this point will be more clear for me.
With this done, I then did a thought experiment in potential syntax additions for LFE. Below are the series of gists that demonstrate this.

Looking at this Erlang syntax:

My fingers want to do something like this in LFE:

That feels pretty natural, from the LFE perspective. However, it looks like it might require hacking on the tuple-parsing logic (or splitting that into two code paths: one for regular tuple-parsing, and the other for maps...?).

The above syntax also lends itself nicely to these:

The question that arises for me is "how would we do this when calling functions?" Perhaps one of these:

Then, for Joe's other example:

We'd have this for LFE:

Before we pattern match on this, let's look at Erlang pattern matching for tuples:

Compare this with pattern matching elements of a tuple in LFE:

With that in our minds, we turn to Joe's matching example against a specific map element:

And we could do the same in LFE like this:

I'm really uncertain about add-pair and update-pair, both the need for them and the names. Interested to hear from others who know how map is implemented in Erlang and the best way to work with that in LFE...

No comments: