Typed Racket pretends mutable sets don't exist, and yet it assumes all hashtables could be mutable

[lexi-lambda]

Typed Racket only provides types for immutable set operations. It would be painless to add types for mutable operations as well, but TR also considers Setof types to be covariant, which obviously isn't true with mutable sets.

This is inconsistent with how TR handles hashtables. In an ideal world, I'd like HashTable to be immutable and have a separate MutableHashTable for mutable hash tables and mutable operations. This would be nice for a number of reasons:

• This would let hashtables be covariant.
• This would make contracts on immutable hashtables flat contracts, so predicate generation and occurrence typing would work with them.
• Mutability would need to be explicitly noted in the type system.

I'd unfortunately guess that this is not possible to change at this point. Still, the behavior with sets and hashtables are inconsistent. If we can't change HashTable, can we make MutableHashTable and ImmutableHashTable subtypes? Then could we make the equivalent variations for sets?

[endobson]

That is because TR's set code was written before mutable sets existed.

Splitting out HashTable might be useful, but I'm not sure if you would want to split out ImmutableHashTable or ReadableHashTable. The first gets you the flat contracts/predicates, the second gets you covariance. Nothing gets you required explicit mutability because you can just revert to HashTable and not specify it.

Sets get more complicated because there are also generic sets which TR still doesn't support.

[lexi-lambda]

@shekari Could you explain the typing difference between immutable hash tables and readable hash tables? Why wouldn't they be equivalent?

[samth]

Immutable hash tables would support hash-set, and you can't pass a mutable hash table where one is expected.

Read-only tables would admit mutable ones, but you could only read them.

Sam

[lexi-lambda]

@samth Oh, I see, that makes sense. ImmutableHashTable would still get you covariance, though, yes?

Wouldn't having explicit mutability still be helpful, though? Contracts support it, and then hash-set! and friends would be checked statically rather than at runtime. Though I suppose it wouldn't be backwards-compatible.

[samth]

Yes, all of these things would be good ideas, and I think we could make everything compatible.

[lexi-lambda]

Should we fork HashTable into ReadableHashTable, ImmutableHashTable, and MutableHashTable? Then just leave HashTable as-is? It would make HashTable a sort of silly type to use for anything, but I guess that's the price to pay for compatibility.

Then w.r.t. Set, should we make it analogous to the new HashTable types?

[samth]

HashTable would be a supertype of the other types.

I think the story for Set is less obvious. It's not clear that supporting more without supporting generic sets is useful.

[lexi-lambda]

With Set, I think we need to at least support mutable hash sets. I ran into this originally when trying to use mutable hash sets in typed code, and the support for them currently simply doesn't exist. Obviously we wouldn't be able to support generic sets, but I think mutable sets are still a pretty valid use case.

[samth]

Sure, if there's need, we should support it. I think we should just split Set and MutableSet though.

[lexi-lambda]

You mean make Set and MutableSet entirely disparate types, like Pair and MPair? I think having the type structure of the proposed hash table rework would be nice.

[lexi-lambda]

In a perfect world, I think ReadableHashTable would be the supertype (and we could just call it HashTable), and ImmutableHashTable and MutableHashTable would be subtypes. You'd get flat contracts with Immutable, mutability with Mutable, and covariance with Readable and Immutable.

I don't think this is possible while maintaining backwards-compatibility, though. Should we keep HashTable around as a legacy type and add Readable/Immutable/Mutable in parallel?

[racket-discourse-github-bot]

This issue has been mentioned on Racket Discourse. There might be relevant details there:

https://racket.discourse.group/t/typed-racket-mutable-hash-sets/3339/6