Discuss type equality based on record field order

[brendanzab]

Currently records with identical fields but with different ordering don't unify, for example: { x : Int, y : String } != { y : String, x : Int }. As commented at https://github.com/Marwes/gluon/pull/109#discussion_r74745341:

It might be a bit cumbersome but it lets the interpreter access fields just by offset instead of by an hashmap.

Do we want to continue using these semantics going forward? I personally find it a bit surprising. Perhaps we could have some deterministic ordering of fields in the VM to allow us to still use offsets?

[Marwes]

I agree that it can be pretty confusing behavior but I also think that forfeiting the ability to only use offsets for field accesses is rather unfortunate as well. Having a deterministic order may overall be the best solution. It is something I have considered before but as I wasn't sufficiently annoyed by it I refrained from implementing it.

There is another solution which might work and that is if row polymorphism #92 is implemented. Then it might be possible to consider two distinct types of records { x : Int, y : String | r } and { x : Int, y : String } where the former works with no regard to the order of the fields while the latter would take order into account letting field accesses be done as just offsets. I only say it might work however because there essentially needs to be some sort of subtyping relationship between polymorphic and and non-polymorphic records (non-polymorphic records must be 'widened' to polymorphic if they are unufied) which may be tricky/impossible to properly to typecheck.

[Marwes]

To get deterministic ordering it is enough to sort the fields by name when emitting code, it will make record construction slightly more complicated however.

[brendanzab]

I guess it just feels very surprising from a user point of view. Maybe a bit of complexity in the implementation is worth it?

[Marwes]

I don't want to put to much emphasis on the complexity of implementing it as it as omitting it for now has been more due to unwillingness to commit to fixing the order that way.

Thought of some other (potential) drawbacks from enforcing a specific order to solve this problem.

• Low level languages can use order to pack fields more tightly (probably not relevant for gluon but its worth mentioning).
• More specific for gluon maybe it can be used to group garbage collected and non garbage collected values to let mark phase proceed quicker. So if fields containing garbage collected values were put first then the record could have some information to tell the collector that only the first n values need to be scanned.

Probably avoiding surprises is better than potential performance improvements but still... It is something to consider at least.

[Marwes]

Reminded by another argument for having { x : Int, y : String } == { y : String, x : Int } from seeing this thread https://internals.rust-lang.org/t/pre-rfc-unnamed-struct-types/3872. Records are going to be useful as 'named arguments' and for that case one definitely want to be able to type the arguments in any order (since that is half the reason to used 'named arguments' over normal 'positional arguments'.