search

brownplt / pyret-lang

The Pyret language.
Other
1.07k stars 110 forks source link

Dictionaries as a built-in datatype #100

Open jpolitz opened 10 years ago

jpolitz commented 10 years ago

We should add dictionaries as a built-in datatype. They should support anything with a _hash and _equals method, which we should supply for the builtins. Mutable built-ins can get a simple id (so hashing is eq-ness), while strings and numbers will need reasonable hash functions (we can probably defer to existing implementations at first).

We need to pick what _hash will get as a default implementation on data, which could either be an id-based hash that is eq-like, or could recursively hash members.

blerner commented 9 years ago

We haven't done this, have we? Certainly not in the generality of extensibly hashable data...

jpolitz commented 9 years ago

Mm, yeah, maybe worth reopening it. Haven't heard a hue and a cry for it, and thought it was referring to string-dicts.

blerner commented 9 years ago

I want it, to improve parts of the compiler. We currently have no way to represent a key=>value mapping in a single object with O(1) lookup unless the key is a string.

I'd reopen it, while noting that we do have string-dicts, so many of the common use cases are handled.

schanzer commented 7 years ago

Did this happen during the winter optimization work? I recall @blerner working on dictionaries quite a bit, but maybe that was internal-only?

schanzer commented 6 years ago

@blerner , still an issue?

blerner commented 6 years ago

Yep

Eugleo commented 3 years ago

Any news on this? For an outsider (just a teacher using Pyret), what work would one need to do to help you implement this?

blerner commented 3 years ago

No work has been done yet. We have string-dictionaries, and I have a tentative plan for how to implement more general dictionaries, but there hasn't been any time to implement this yet.

Eugleo commented 3 years ago

Thanks for the heads up. Any way to help you achieve this? (not promising anything, just checking)

jpolitz commented 3 years ago

Full dictionaries supporting e.g. hashing/comparison plus equality on arbitrary keys is, I think, a long journey.

I pushed just now a quick sketch of what dictionaries for arbitrary keys might look like under the constraints of:

So that's a place to start looking at adding methods/functionality while getting something pretty performant. Thanks for prompting this!

https://github.com/brownplt/pyret-lang/pull/1547/files