Separating a Hash type from Object

[Lars T Hansen]

On 5/7/07, zwetan <zwetan at gmail.com> wrote:
> Hi Lars, I don't know if your answer was mean only to me or the list,
> but as I don't see it on the list I answer to you directly.

I'm not always convinced that gmail's "reply" defaults are right, but
anyhow it's my fault, it was intended for the list (hereby cc'd).

> On 5/7/07, Lars T Hansen <lth at acm.org> wrote:
> > On 5/7/07, zwetan <zwetan at gmail.com> wrote:
> > > On 5/7/07, Lars T Hansen <lth at acm.org> wrote:
> > > [snip..]
> > > >
> > > > Following is the proposed API for the dictionary class, note this
> > > > proposal has been *rejected* for ES4.  It would be rejected even
> > > > without the provision for weak refs.  I'm including it only to make
> > > > the point that, like a lot of other data structures, it can be
> > > > implemented in portable ES4 and does not need to be part of the
> > > > language.  (That happens not to be the case for ByteArray, whose
> > > > entire reason for existence is storage efficiency coupled with
> > > > performance.)
> > > >
> > > > class Dictionary.<K,V> {
> > > >     function Dictionary(weak: boolean = false)
> > > >     public function from(x : Object!)
> > > >     public function size() : uint
> > > >     public function get(key: K) : V?
> > > >     public function put(key:K, value:V) : void
> > > >     public function has(key:K) : boolean
> > > >     public function remove(key:K) : boolean
> > > >     iterator function get(deep: boolean = false) : iterator::IteratorType.<K>
> > > >     iterator function getKeys(deep: boolean = false) :
> > > > iterator::IteratorType.<K>
> > > >     iterator function getValues(deep: boolean = false) :
> > > > iterator::IteratorType.<V>
> > > >     iterator function getItems(deep: boolean = false) :
> > > > iterator::IteratorType.<[K,V]>
> > > > }
> > > >
> > >
> > > so if this API can be implemented in ES4, where is the problem ?
> >
> > It depends on whose job you think it is to provide a Dictionary, I
> > guess.  The language spec will almost certainly not contain this
> > class, so every user will have to build his own or rely on some
> > third-party library.  Some people probably do not like that (I'm not
> > sure I do). But at least that's possible.
>
> my main concern is to be able to build such Dictionary class
> with the ES4 language itself.
>
> And if I take the only real-world example that I know of now,
> which is AS3 compiled with Flex,
> if the Dictionary class was not there, it would be kind of difficult
> to implement one.

Right.  The AS3 Dictionary class was discussed a little in the
committee, and we weren't unanimously sure that it has the interface
you want to have in that kind of a class, even though -- as I remember
it -- it allows you to access the object using convenient
dereferencing a la obj[name].

> As I see it now, ES4 just define the basis of the language, not a
> standard framework or standard library around it, and it can be fine,
> if developers can build their own library,
> provided the language give them enougth access to do that.

That's the hope.

> > Some people also don't like that you have to write code that looks a
> > lot like Java instead of using super-convenient syntax, and that seems
> > to be what much of the discussion is about.  For as much as I like JS
> > syntax conveniences and would enjoy seeing one here we've been around
> > that track several times now and we're not really getting anywhere as
> > far as I can tell.
> >
>
> Personally, I think the two style can be combined,
> if something is missing or can not be done in a non-strict JS dynamic style,
> I see no problem to implement it ala Java in a strict static style, so
> it can be used
> later in a non-strict dynamic style.
> (hope I'm clear here)
>
>
> > > it's hard to follow here why people even discussing all that,
> > > as I see it if such API has been *rejected*, what are the chances
> > > for a new syntax as obj.#toString to be *accepted* ?
> >
> > I wouldn't put a lot of money on it.
> >
> > > maybe adding to catchall (
> > > http://developer.mozilla.org/es4/proposals/catchalls.html )
> > > would have better chances to be *accepted* ?
> >
> > Not likely.
> >
> > > for ex:
> > > function get *(ident), the catchall getter. (return the value)
> > > -> function get2 *(val) (return the ident)
> > >
> > > function intrinsic::get(ident), the non-overridable universal property getter.
> > > -> function intrinsic::get2(val)
> > >
> > > afaik, the Dictionary class in AS3 is very usefull to avoid O(n)
> > > search of ident,
> > > maybe I don't fully understand the whole problem here, but for hashes speed
> > > sake some *magic* O(1) access to the ident would be more than welcome.
> >
> > I'm sure there's something I don't understand in what you write,
> > because a hash table (dictionary) provides O(1) access time, and no
> > magic is necessary for that, provided you have an efficient means of
> > generating hash codes for a value.  For many applications you don't
> > even need intrinsic::hashcode().
> >
>
> well, right now, with what I can access in a language as AS3,
> or better with some tests compiling with ASC for avmplus.exe
> if I try to define my own Dictionary class I can not obtain a O(1) access time,
> so my comment is surely flawed because I can not connect all the dots
> of what ES4 can really do as I got no final implementation to test with.
>
> the same is true with hashcodes, I implemented in AS3 some hashcode routines
> based on Fowler/Noll/Vo, and basically it works but when it comes to
> object Object it can be tricky.

Yes, that's why intrinsic::hashcode has been proposed.  You need that
to do general object hashing efficiently.

> Granted that AS3 is limited compared to what ES4 can do,
> but for ex if intrinsic::hashcode() did not make it into the spec,
> for a reason like very few application use it, people wanting
> to use hashcodes will be stuck and/or have to do some nasty hacks
> like serializing an object to bytearray, and generate the hash from that.
>
> My point here is : if a Dictionary class can be implemented in
> portable ES4, great,
> but what if we don't have enought efficient means in the language to
> handle weak refs for exemple ?

Well, as it stands you don't have the tools in ES4 to implement weak
refs.  The most you can hope for on the user level right now is
efficient, general hashing, but weak refs require machinery we have
not been willing to spec.

There are lots of candidates for that machinery but (a) picking one is
work we are not willing/able to do right now and (b) it's an open
question whether you want to place the burden of this mechanism on the
implementers.  Nobody disputes the utility of weak refs, just the cost
(calculated several ways).

--lars