[eeps] Maps

[Björn-Egil Dahlberg]

Hi everyone!

We finally have a Maps EEP for you. This will get you an idea on what we 
are working on. Some of the ideas presented here was presented at Erlang 
Factory SF Bay Area 2013.

I am sure that there will be some discussions about the contents of this 
EEP and I hope the discussions will be both fruitful and civilized.

The journey of Maps and this EEP has been long and by no means a 
straight-forward or continuous one. I had a crystal clear picture of 
what I wanted Maps to be when we first started discussing it within OTP 
about two-three years ago. This EEP resembles that vision but it has had 
a lot of contributions of other ideas from both within and outside of OTP.

The idea was a functional data-type, a syntax aware mapping of key-value 
associations with pattern matching. A syntax similar to records but 
without the hazzle of compile-time dependency and with arbitrary terms 
as keys. Order was not important and it could be implemented with a 
Hash-Array-Mapped-Trie with good performance and memory trade-offs. This 
was not an approach to replace records. It was meant to replace records 
where suitable and in other regards not be a replacement but its own thing.

 From the community there has been many wishes of a Map like data-type 
and a few suggestions.  The one suggestion that stands out is of course 
the Frames proposal from Richard O'Keefe. It is the most complete 
proposal I've seen and is very well thought out. Its goal is to be a 
record replacement and the proposal satisfies this goal very well.

- If Frames are that good, why a separate EEP?
- It boils down to goals and constraints.

A record replacement is just that, a replacement.
It's like asking the question, "What do we have?" instead of "What can 
we get?"
The instant rebuttal would be "What do we need?" I say Maps.

Frames has certainly influenced Maps. In many regards Maps also 
encompasses Frames but Maps tries to do more. I think the most 
significant difference would be, arbitrary terms as keys and how many 
different keys we would have in a Map. In the end I believe they are two 
different things and have different goals.

Some Notes and Disclaimers:

Later iterations of Maps has gone through some changes, most significantly,

   * From a set of key-values to a ordered set of key-value associations

I was originally against this change since it forces restrictions on the 
implementation and it illuminates the lack of distinction between 
arithmetic order and term order, i.e. the problem of mixing integer and 
float types as keys in a tree. However, I was later persuaded that key 
ordering is necessary. We have to respect the totalitarian order of terms.

Considerations has been made on how to, if at all possible, apply Frames 
characteristics to Maps. Most significantly memory space and key-sharing 
characteristics. This is not detailed in the EEP though, just mentioned.

The function interface has had many revisions as well. At some stage the 
API was considered to be a drop-in-replacement for `dict` and thus would 
have the same function-names. This goal/constraint was dropped by 
Technical Board decision recently.

 From the very beginning Maps was envisioned to have the ability to bind 
variables derived from the environment. Like this:

     function(K1, #{ K1 := K2, K2 := V }) -> V.

This feature is a beast. Powerful and scary. It is not confined to only 
Maps but should also be applicable to other types as well:

     function(Skip, <<_:Skip/binary, Value:Size, _/bits>>, Size) -> Value.

It is uncertain how effective such an implementation would be and in the 
end we might not want this feature at all.

In this EEP we will describe syntax and semantics of Maps but very 
little is disclosed of its actual implementation. Current prototypes 
stems from using sparse tuples in a HAMT-like data structure and 
tuple-like data structures. The HAMT-like data structure is discontinued 
and will be replaced by some ordered tree.

The proposal is included as an attachment but can also be viewed at this 
git-repository:
https://github.com/psyeugenic/eep/blob/egil/maps/eeps/eep-0043.md


Regards,
Björn-Egil Dahlberg
Erlang/OTP
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/eeps/attachments/20130508/1835da21/attachment.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: eep-XXX.md
Type: text/x-markdown
Size: 51297 bytes
Desc: not available
URL: <http://erlang.org/pipermail/eeps/attachments/20130508/1835da21/attachment.bin>