pyret-lang icon indicating copy to clipboard operation
pyret-lang copied to clipboard

Published 20 hours ago • verified publisher icon brownplt

Dictionaries as a built-in datatype

Open jpolitz opened this issue 11 years ago • 10 comments

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.

jpolitz avatar Nov 06 '13 22:11 jpolitz

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

blerner avatar Jun 04 '15 18:06 blerner

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

jpolitz avatar Jun 04 '15 18:06 jpolitz

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.

blerner avatar Jun 04 '15 18:06 blerner

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

schanzer avatar Feb 21 '17 02:02 schanzer

@blerner , still an issue?

schanzer avatar Nov 04 '17 02:11 schanzer

Yep

blerner avatar Nov 04 '17 02:11 blerner

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

Eugleo avatar Nov 24 '20 11:11 Eugleo

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.

blerner avatar Nov 24 '20 12:11 blerner

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

Eugleo avatar Nov 24 '20 12:11 Eugleo

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:

  • Mutable dictionaries only (because JS Map is)
  • Only <=>/identical comparison for keys (because JS ===/sameValue matches identical pretty well)

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

jpolitz avatar Nov 25 '20 17:11 jpolitz