Summary
This proposal aims to add a compact representation for SourceTypes which would be consumed by the externs and consequentially, the IDE server.
Proposal
This proposal defines a compact representation for the SourceType type, similar in vein to GHC's efficient serialization for HIE files. To present a simple example, consider the following Type type:
data Type a
= Constructor a String
| Variable a String
| Application a (Type a) (Type a)
We can refactor the recursive cases such that they're represented by Int indices:
data CompactType a
= CompactConstructor a String
| CompactVariable a String
| CompactApplication a Int Int
And to preserve information, they'll be accompanied by a Map Int (CompactType a). This also means that we get the following functions:
compact :: Ord a => Type a -> (Map Int (CompactType a), CompactType a)
decompact :: Ord a => Map Int (CompactType a) -> CompactType a -> Type a
We can also take this further and compact the annotations and names, if need be.
Serialization
As for serialization into externs.cbor outputs, I was thinking that each module should have its own compact type mapping. However, since this representation essentially makes it so that types are compacted nominally (i.e. based on their structure, not necessarily semantic meaning), we could make it so there exists a "shared" one that all other externs.cbor files reference to.
Performance?
I've yet to write a proof-of-concept for this proposal, but I can imagine that we would have to take care of when and where we want to call decompact for retrieving the original AST representations of types. OTOH, I can see how this can potentially help with the memory footprint of externs files being stored in memory, but only a concrete implementation can reveal what this actually entails.
Maybe in the future, the core of the compiler can make use of this encoding as well?
Summary
This proposal aims to add a compact representation for
SourceTypes which would be consumed by the externs and consequentially, the IDE server.Proposal
This proposal defines a compact representation for the
SourceTypetype, similar in vein to GHC's efficient serialization for HIE files. To present a simple example, consider the followingTypetype:We can refactor the recursive cases such that they're represented by
Intindices:And to preserve information, they'll be accompanied by a
Map Int (CompactType a). This also means that we get the following functions:We can also take this further and compact the annotations and names, if need be.
Serialization
As for serialization into
externs.cboroutputs, I was thinking that each module should have its own compact type mapping. However, since this representation essentially makes it so that types are compacted nominally (i.e. based on their structure, not necessarily semantic meaning), we could make it so there exists a "shared" one that all otherexterns.cborfiles reference to.Performance?
I've yet to write a proof-of-concept for this proposal, but I can imagine that we would have to take care of when and where we want to call
decompactfor retrieving the original AST representations of types. OTOH, I can see how this can potentially help with the memory footprint of externs files being stored in memory, but only a concrete implementation can reveal what this actually entails.Maybe in the future, the core of the compiler can make use of this encoding as well?