<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<div class="moz-cite-prefix">Hi!<br>
<br>
Thank you all who have contributed in this discussion!<br>
<br>
Instead of replying to every mail I will try to address and
correct some misconceptions. <br>
<br>
- As stated earlier by several people. Maps are <b>not</b>
Frames.<br>
<br>
- There are several semantic and syntax differences. Most notably
arbitrary terms as keys.<br>
<br>
- 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.<br>
<br>
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):<br>
<br>
{ {K1, ...,Kn}, V1, ..., Vn}<br>
<br>
This structure will also allow key-sharing between Maps of the
same "type", i.e. Maps with identical keys. <br>
<br>
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.<br>
<br>
<br>
- Maps are of type ordered set and follows term order. This has
several implications.<br>
- Term order does not distinguish between types float and
integer. <br>
- 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.<br>
- 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.<br>
<br>
Maps emulates the behaviour of ETS ordered set in this sense.<br>
<br>
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.<br>
<br>
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).<br>
<br>
<br>
- Deep updates of Maps are not covered by this EEP. We would
welcome suggestions on this.<br>
<br>
Thank you! <br>
<br>
Regards,<br>
Björn-Egil<br>
<br>
On 2013-05-08 16:18, Björn-Egil Dahlberg wrote:<br>
</div>
<blockquote cite="mid:518A5ED1.2030507@erlang.org" type="cite">
<meta http-equiv="content-type" content="text/html;
charset=ISO-8859-1">
Hi everyone! <br>
<br>
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.<br>
<br>
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. <br>
<br>
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. <br>
<br>
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 <b
class="moz-txt-star"><span class="moz-txt-tag"></span></b><span
class="moz-txt-star">thing</span><b class="moz-txt-star"><span
class="moz-txt-tag"></span></b>. <br>
<br>
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. <br>
<br>
- If Frames are that good, why a separate EEP? <br>
- It boils down to goals and constraints. <br>
<br>
A record replacement is just that, a replacement. <br>
It's like asking the question, "What do we have?" instead of "What
can we get?"<br>
The instant rebuttal would be "What do we need?" I say Maps. <br>
<br>
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. <br>
<br>
Some Notes and Disclaimers: <br>
<br>
Later iterations of Maps has gone through some changes, most
significantly, <br>
<br>
* From a set of key-values to a ordered set of key-value
associations <br>
<br>
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. <br>
<br>
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.<br>
<br>
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.<br>
<br>
From the very beginning Maps was envisioned to have the ability to
bind variables derived from the environment. Like this: <br>
<br>
function(K1, #{ K1 := K2, K2 := V }) -> V. <br>
<br>
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: <br>
<br>
function(Skip, <<_:Skip/binary, Value:Size,
_/bits>>, Size) -> Value. <br>
<br>
It is uncertain how effective such an implementation would be and
in the end we might not want this feature at all.<br>
<br>
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.<br>
<br>
The proposal is included as an attachment but can also be viewed
at this git-repository:<br>
<a moz-do-not-send="true" class="moz-txt-link-freetext"
href="https://github.com/psyeugenic/eep/blob/egil/maps/eeps/eep-0043.md">https://github.com/psyeugenic/eep/blob/egil/maps/eeps/eep-0043.md</a><br>
<br>
<br>
Regards, <br>
Björn-Egil Dahlberg <br>
Erlang/OTP <br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
erlang-questions mailing list
<a class="moz-txt-link-abbreviated" href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a>
<a class="moz-txt-link-freetext" href="http://erlang.org/mailman/listinfo/erlang-questions">http://erlang.org/mailman/listinfo/erlang-questions</a>
</pre>
</blockquote>
<br>
</body>
</html>