[erlang-questions] [eeps] Maps

Fri May 17 11:11:44 CEST 2013

Hi!

I think we need to clarify a few things from the perspective of the 
technical board that gave Björn-Egil the premises for this EEP.

1) Maps are Maps and Frames are Frames. Maps is not some kind of 
extension to Frames, as Frames hold properties that Maps never should 
hold. What was decided, and what Björn-Egil is working on, was to 
investigate if a clever implementation of a dictionary can be a good 
enough record replacement to be used in situations like interfaces 
between modules, instead of records and property lists. As the 
implementation is not yet done, we only have the interface to Maps to 
discuss. Even if the EEP mentions complexity, we still have to see if 
the implementation in a "record-like" situation can be made efficient 
both when it comes to memory consumption and time complexity.

2) Maps is *not* to be implemented using HAMT's, so discussing the 
complexity or implementation of HAMT's is interesting, but beside the 
point. The task is to define an ordered dictionary. Maps have keys in 
order. How that is implemented is not defined and that job is yet to be 
done. A maximal O(log N) complexity in look up was the only requirement, 
but an implementation with low memory consumption for "simple" Maps was 
*suggested*. Discussing characteristics of an implementation that is no 
more than a general idea seems futile. There are expectations, but no 
facts about the performance characteristics.

3) The behavior of float and integer keys that compare equal is the same 
as the one for ordered_set ETS tables. Even though we don't like it, 
that behavior is the only consistent we've found for ordered 
dictionaries. If we want to define two types of comparison in Erlang, 
that is another discussion. (An EEP for that would be welcome. Do not 
forget to add suggestions for all current interfaces where order is 
used, like lists:sort, orddict etc.)

4) Maps is supposed to be general, a general mapping from keys to 
values. The thinking was that the current data types (at least the 
compound ones) are very general. Also the current dictionaries have no 
restrictions on the keys or values. A Map data type should of course not 
have that either. When used in place of records, the Map gives maybe to 
much freedom, that is the price to pay when being very general.

5) To be able to differentiate between operations where you possibly add 
new keys and operations where you replace existing keys was a 
requirement. The arguments have already been outlined in Joe's earlier 
posts, so I see no point in repeating that.

6) Imposing an order on the keys was thought to make the data type fit 
better with the current built in types. Using for example the HAMT 
implementation to describe the order between Maps, to have a 
serialization looking different depending on how the map was 
constructed, or having random order of the keys when serializing or 
displaying the data, would make the Map an odd creature in the Erlang 
world. If we for example want to serialize and send two Maps to a 
program written in another language, we would like to be able to 
describe the order between the Maps so that comparison could be done in 
that other language. The order between Maps as they look in this EEP is 
easily described and comparison is simple to implement. Suggestions like 
"sorting the MAP before comparing and printing" was rejected. Making a 
comparison between two elements possibly have the complexity of O(N log 
N) was thought unacceptable.

7) To publish an EEP even before there was a prototype implementation 
was a requirement from the technical board, as we wanted feedback on the 
API, the semantics etc. I think this thread has shown that there is 
definitely a lot to discuss. It however also shows that as long as there 
is no description of the actual implementation, there's a lot that 
cannot be discussed, but we really would want to discuss...

So - these were the premises and I think Björn-Egil has done a really 
good job in writing this EEP. A lot of people has also taken the time to 
give valuable feedback. I think the EEP and the current feedback gives 
me reason enough to suggest a prototype implementation. Possibly with a 
few adjustments to the EEP text, examples etc.

Cheers,
Patrik

On 05/08/2013 04:18 PM, 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
>
>
> _______________________________________________
> eeps mailing list
> eeps@REDACTED
> http://erlang.org/mailman/listinfo/eeps

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20130517/65729409/attachment.htm>