3 ms·

Why does Ocaml need to tag types? (as opposed to statically knowing the type of everything) Do they not monomorphize generics?

by devit 3y ago

octachron 3y ago
No, OCaml compiles polymorphic functions once by using an universal representation of values which tends to play better with a type system with recursively polymorphic functions, higher-rank polymorphism or existential types (which all imply that concrete types are not always known statically in OCaml).
ithkuil 3y ago
The GC scans the heap and stack and it would be hard for the GC to scan the heap while maintaining perfect knowledge about all the types. Go has this problem too but they choose to use a "conservative collector" which will just assume that if something is a word that contains something that happens to be a valid location in memory it considers that location to be alive even if it's actually garbage. The main drawback is that if you're not sure if something is really a pointer, you cannot relocate objects and compact the heap. Ocaml has a generational collector with a nursery implemented with a semi space collector. A semi space collector performs a collection which involves moving live objects and leaving the garbage behind. This is very efficient because young objects are less likely to survive and thus the amount of work is proportional to the amount of surviving objects and not the garbage.
- zeeboo 3y ago
  Go's GC has been precise since 1.4 released about 13 years ago.
  - ithkuil 3y ago
    Time flies
- gpderetta 3y ago
  It is still not clear to me why it is necessary to store the type information inline. I'm absolutely not an expert, but I thought that some GC'd languages had stack layout metadata[1], to figure out the type of each stack slot. Similarly heap allocated data should have an associated type layout info. [1] possibly static and indexed by the instruction pointer, not unlike DWARF unwind info.
  - ithkuil 3y ago
    It's not necessary. Indeed there are many GCs that use type information (as a sibling comment says, Go GC is now precise). But it's more complicated, so it's a tradeoff. You may pay some little cost in dealing with tagged arithmetic but you gain a simpler GC codebase, one perhaps that can work with both the AOT and bytecode compilers (just speculating)

Why does Ocaml need to tag types? (as opposed to statically knowing the type of everything) Do they not monomorphize generics?

by devit 3y ago

Why does Ocaml need to tag types? (as opposed to statically knowing the type of everything) Do they not monomorphize generics?

octachron 3y ago

No, OCaml compiles polymorphic functions once by using an universal representation of values which tends to play better with a type system with recursively polymorphic functions, higher-rank polymorphism or existential types (which all imply that concrete types are not always known statically in OCaml).

ithkuil 3y ago

The GC scans the heap and stack and it would be hard for the GC to scan the heap while maintaining perfect knowledge about all the types. Go has this problem too but they choose to use a "conservative collector" which will just assume that if something is a word that contains something that happens to be a valid location in memory it considers that location to be alive even if it's actually garbage. The main drawback is that if you're not sure if something is really a pointer, you cannot relocate objects and compact the heap. Ocaml has a generational collector with a nursery implemented with a semi space collector. A semi space collector performs a collection which involves moving live objects and leaving the garbage behind. This is very efficient because young objects are less likely to survive and thus the amount of work is proportional to the amount of surviving objects and not the garbage.

zeeboo 3y ago
Go's GC has been precise since 1.4 released about 13 years ago.
- ithkuil 3y ago
  Time flies
gpderetta 3y ago
It is still not clear to me why it is necessary to store the type information inline. I'm absolutely not an expert, but I thought that some GC'd languages had stack layout metadata[1], to figure out the type of each stack slot. Similarly heap allocated data should have an associated type layout info. [1] possibly static and indexed by the instruction pointer, not unlike DWARF unwind info.
- ithkuil 3y ago
  It's not necessary. Indeed there are many GCs that use type information (as a sibling comment says, Go GC is now precise). But it's more complicated, so it's a tradeoff. You may pay some little cost in dealing with tagged arithmetic but you gain a simpler GC codebase, one perhaps that can work with both the AOT and bytecode compilers (just speculating)