[eeps] [erlang-questions] Maps

[Björn-Egil Dahlberg]

Hi!

Thank you all who have contributed in this discussion!

Instead of replying to every mail I will try to address and correct some 
misconceptions.

- As stated earlier by several people. Maps are *not* Frames.

- There are several semantic and syntax differences. Most notably 
arbitrary terms as keys.

- The implementation of Maps will have Frame like characteristics for 
"simple" Maps, i.e. small number of associations (at most ~30 - 40 
entries) and immediates as keys. Granted, the type information will not 
be there at compile-time, and Maps will not have literals as keys (as 
proposed in Frames), but should otherwise be comparable in performance 
with Frames for those cases. I also believe this would cover most of the 
use-cases as a record-replacement.

The internal structure in the "simple" case would best be described with 
two tuples (but it would not have some other header and might have 
additionally meta-data in the header if necessary):

     { {K1, ...,Kn}, V1, ..., Vn}

This structure will also allow key-sharing between Maps of the same 
"type", i.e. Maps with identical keys.

When the Map no longer satisfies this "simple" arrangement it will 
transform into a tree and loose the previous characteristics and gain 
the characteristics of a tree.


- Maps are of type ordered set and follows term order. This has several 
implications.
   - Term order does not distinguish between types float and integer.
   - If data is stored in a tree where we search entries based on keys 
and we do so by term order. Since term order does not distinguish 
between float and integer, floats and integers which are equal occupy 
the same place.
   - When iterating over keys in a Map it is done so in Term order, or 
reversed Term order, meaning it is expected that floats and integer are 
mixed, ex. 1 < 2.0 < 3 < 4.0 < 5 < 6.0. If we distinguish between floats 
and integers in Maps, let's say integer < doubles, the previous order 
would be, ex: 1 < 3 < 5 < 2.0 < 4.0 < 6.0. We would no longer iterate in 
Term order and this would not be consistent with the rest of Erlang, 
hence unacceptable.

Maps emulates the behaviour of ETS ordered set in this sense.

I think we can all agree that this is an unfortunate feature of Erlangs 
term order. I also agree that it would be best to have *matching* only, 
and not *equals* but I don't see how this could be achieved easily. At 
least not in an acceptable way. For example, we cannot achieve this by 
specifying our own Term order since that would violate iteration order, 
printing order, etc, or at least expected order.

As noted previously, if we had Maps of type set we would not have this 
problem. However, since Maps needs to fit into Erlangs term order, Maps 
needs to be ordered (unless we could somehow abandon this strict rule).


- Deep updates of Maps are not covered by this EEP. We would welcome 
suggestions on this.

Thank you!

Regards,
Björn-Egil

On 2013-05-08 16:18, Björn-Egil Dahlberg wrote:
> 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
>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/eeps/attachments/20130513/48d94b05/attachment.htm>