3 ms·

> When the type system accurately represents relationships, there is no need for users of a data structure to be careful to obey rules. Of course. Unfortunatel

> When the type system accurately represents relationships, there is no need for users of a data structure to be careful to obey rules. Of course. Unfortunately sticking everything into an array and pointing to things via integers instead of raw pointers doesn't provide you any help from typesystem. My whole point is that there is a huge class of datastructures and algorithms which can not be reperented in a type-safe way without automatic manual memory management. You either have to be accurate when writing your algorithms, or introduce runtime costs for validity checks. You get pretty much 0 support from your compiler (for imperative language without GC) if you are not dealing with hierarchical datastructure without backreferences. It does not really matter how you reperesent it. No language can model that at type level. You can either encapsulate it into some abstraction and prove (and/or hope) that it is implemented correctly. This is a common way to approach the problem of type-system no helping you (for example, pretty much all foundational Rust libraries are unsafe underneath to get around borrow checker; STL in C++ lives and breathes with raw pointers in the implementation of succint datastructures like maps, etc). If you can't encapsulate it fully, you try to be accurate OR use some helpers to deal with the complexity (shared and weak ptr, this raw_ptr that article is talking etc). > Any "fragmentation issue" is off-topic: if something is an "issue", you do something differently so it isn't anymore. You were selling pushing everything into an array as a solution to not using pointers. I tried to give an example why this might be not the solution that you want. Specifically in browsers. > (Anything-oriented design is code smell.) Data-oriented design is a name for what you were proposing, I just brought it up for easier reference of your point. I.e. Modelling your data as a set of tables with relations between them.

ncmncm 4y ago
If you thought I was hustling something-oriented design, you missed the point. And, if you think that a type system can be no help with some family of data structures, it can only because you are unfamiliar with powerful type systems. Rust coders rely on the compiler to protect them from themselves. C++ coders rely on the type system and libraries in the same way. The language is powerful enough to enable building libraries that can only be used correctly; or that it is much more work to use incorrectly, so no one is tempted.
- the-lazy-guy 4y ago
  > And, if you think that a type system can be no help with some family of data structures, it can only because you are unfamiliar with powerful type systems. I am. Would you please point me at some things to study? The best I can imagine is languages like F* (https://www.fstar-lang.org/ https://www.fstar-lang.org/, and more specifically the Low* subset for dealing with memory) which make you prove everything. And thus are such a PITA to program in that it make sense to code only the most security-demanding things. Dependant types are also not able to protect you from memory bugs in self-referential datastructures AFAIK. I am open to reading about research in PL. But if you point me at some mainstream (or just production-ready) languages/runtimes it would be even better. Thanks.
  - ncmncm 4y ago
    You are in luck: ML, Haskell, and C++ all support powerful type systems. Rust's has been growing in power, coming from behind. Its recent addition of an analog to C++'s numeric template arguments was a big improvement. Meanwhile, C++20's long-gestating "concept" support moved it into new territory. So reading up on what can now be done with C++ concepts should give you some ideas. For a more abstract treatment, read about Haskell's type classes.
    - the-lazy-guy 4y ago
      ML and Haskell are languages with garbage collection. In case of Haskell it is also pure and lazy which makes it a huge PITA to use for any non-trivial non-hierarchical datastructures. You can look at Okasaki's book to see what level of mental gymnastics is needed to make it usable in some cases. Neither C++ now Rust can help you self-referential datastructures through types. In both you have either give up any help from compiler. Or pay some price for runtime checks (via shared_ptr/weak_ptr in C++ or their friends Rc/Weak in rust). Exactly like the ones described in the article. Concepts, Rust traits, Haskell Type classes provide close to 0 help with memory management. These are a typesafe way to write generic code. Things which do help with memory management at the language level (with 0 runtime costs) are Rust's borrow checker (and more generally(?) linear/affine types), F* proofs, and dependant types (you can prove index bounds with them to some extent). All of them are useful, but can't really model all interesting programs (i.e. you have to sidestep typesystem and just tell compiler "I know that I am right").

ncmncm 4y ago

If you thought I was hustling something-oriented design, you missed the point. And, if you think that a type system can be no help with some family of data structures, it can only because you are unfamiliar with powerful type systems. Rust coders rely on the compiler to protect them from themselves. C++ coders rely on the type system and libraries in the same way. The language is powerful enough to enable building libraries that can only be used correctly; or that it is much more work to use incorrectly, so no one is tempted.

the-lazy-guy 4y ago
> And, if you think that a type system can be no help with some family of data structures, it can only because you are unfamiliar with powerful type systems. I am. Would you please point me at some things to study? The best I can imagine is languages like F* (https://www.fstar-lang.org/ https://www.fstar-lang.org/, and more specifically the Low* subset for dealing with memory) which make you prove everything. And thus are such a PITA to program in that it make sense to code only the most security-demanding things. Dependant types are also not able to protect you from memory bugs in self-referential datastructures AFAIK. I am open to reading about research in PL. But if you point me at some mainstream (or just production-ready) languages/runtimes it would be even better. Thanks.
- ncmncm 4y ago
  You are in luck: ML, Haskell, and C++ all support powerful type systems. Rust's has been growing in power, coming from behind. Its recent addition of an analog to C++'s numeric template arguments was a big improvement. Meanwhile, C++20's long-gestating "concept" support moved it into new territory. So reading up on what can now be done with C++ concepts should give you some ideas. For a more abstract treatment, read about Haskell's type classes.
  - the-lazy-guy 4y ago
    ML and Haskell are languages with garbage collection. In case of Haskell it is also pure and lazy which makes it a huge PITA to use for any non-trivial non-hierarchical datastructures. You can look at Okasaki's book to see what level of mental gymnastics is needed to make it usable in some cases. Neither C++ now Rust can help you self-referential datastructures through types. In both you have either give up any help from compiler. Or pay some price for runtime checks (via shared_ptr/weak_ptr in C++ or their friends Rc/Weak in rust). Exactly like the ones described in the article. Concepts, Rust traits, Haskell Type classes provide close to 0 help with memory management. These are a typesafe way to write generic code. Things which do help with memory management at the language level (with 0 runtime costs) are Rust's borrow checker (and more generally(?) linear/affine types), F* proofs, and dependant types (you can prove index bounds with them to some extent). All of them are useful, but can't really model all interesting programs (i.e. you have to sidestep typesystem and just tell compiler "I know that I am right").