<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">Hi!<br>
<br>
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.<br>
<br>
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.<br>
<br>
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.<br>
<br>
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.)<br>
<br>
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. <br>
<br>
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.<br>
<br>
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. <br>
<br>
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...<br>
<br>
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.<br>
<br>
Cheers,<br>
Patrik<br>
<br>
On 05/08/2013 04:18 PM, 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="">_______________________________________________
eeps mailing list
<a class="moz-txt-link-abbreviated" href="mailto:eeps@erlang.org">eeps@erlang.org</a>
<a class="moz-txt-link-freetext" href="http://erlang.org/mailman/listinfo/eeps">http://erlang.org/mailman/listinfo/eeps</a>
</pre>
</blockquote>
<br>
</body>
</html>