6 ms·

In my Perfect Programming Language That Doesn't Have To Deal With The Problems Of Actually Existing, serialization of data structures into memory is explicitly

by jerf 6y ago

In my Perfect Programming Language That Doesn't Have To Deal With The Problems Of Actually Existing, serialization of data structures into memory is explicitly defined in the language, just as one would define a JSON or Protobuf serialization. One could define a "Point3{x,y,z}", and hypothetically define one array of them in the conventional manner, define another array as a columnar serialization, and potentially even define a compressed data structure right there in memory if that was advantageous. It opens a wide array of exciting problems and possibilities, if you start thinking of that as something a language should let you twiddle with rather than hard coding it. It seems like a lot of high performance stuff is moving in a direction where this would be advantageous. (For example, if you compress an array, you lose random access. The language would have to carefully build up capabilities from scratch so it can have a concept of "arrays" that can't be randomly accessed, can only be written in some very particular manner that may even require a "flush" concept, etc. My gut says it ought to be possible, since, after all, we can do it manually, but it would be a very careful operation to disentangle casual assumptions about what data structures can do based on the definition of what data they contain vs. how they are represented in memory, and what capabilities you get from that.)

svrb 6y ago
Sign me up! I'm constantly defining `XYZ` and `PackedXYZ` for memory-bound problems and I have often though it would be nice to be able to do this (in a more generic way than mere bitfields). It never occurred to me that it could be extended to column stores though.
zero_iq 6y ago
Jonathan Blow's new language, Jai, has some control over layout allowing easy switching between array of structs and struct of arrays without having to change the accessing code.
- andi999 6y ago
  There is no Jai.
  - jacobush 6y ago
    There Is Only IBM And AT&T And Exxon?
    - andi999 6y ago
      Could you explain? What I meant, I believe Jai is vaporware and gets too much attention. I mean Jai sound exciting until you find out that the download link is missing.
      - zero_iq 6y ago
        It's still under development, with no public release, but I think it's a bit unfair to call it vapourware, since he has produced plenty of material that demonstrates he has a working compiler and has clearly spent a great deal of time developing it, not just talking about it. Whether it gets too much attention is debatable. He has some good ideas, imo, worth exploring, although I don't agree with all of his opinions. He has a prominent enough profile that it will likely inspire others to incorporate features from Jai if they are seen to be desirable, even if Jai is not ultimately released. (Personally, I think it will eventually.)
        andi999 6y ago
        Well, what is your hunch when it will be released? My expectation is eithet never, or there will be a release and it will crumble quickly when people want to do things with it.
- clucas 6y ago
  Here is the demo video of the stuff zero_iq is talking about: https://www.youtube.com/watch?v=ZHqFrNyLlpA https://www.youtube.com/watch?v=ZHqFrNyLlpA Basically right on point with what the GP is saying.
  - epistasis 6y ago
    That video briefly mentions the CppCon 2014 talk by Mike Afton, "Data-oriented Design and C++". The talk was great, pretty much lined up with how I think of modern systems (treat RAM like disk: seeks take a long time, but streams will likely be able to maximize CPU usage) But the questions at the end, and the resistance to these basic ideas, roughly "what about platform portability, programmer productivity, etc."; these questions were a bit shocking to me. Is this not a C++ conference? This was six years ago, so perhaps the machine constraints were not as well known back then, but it really shows how strongly the community culture will influence a language and its capabilities.
- runevault 6y ago
  I thought he pulled that back out of the language, though with the intent of re implementing it with as a library with the metaprogramming facilities of the language for anyone who wanted it?
  - jiggawatts 6y ago
    I haven't seen the update, but to me that seems a bit silly. This is a pretty fundamental type manipulation, and ideally the compiler would have some understanding of it...
thechao 6y ago
I was privy to a fairly high-wattage conversation between Walid Taha, Jeremy Siek, Todd Veldhuizen, et al, where they discussed this issue at length. They were concerned that languages almost universally equate data types with data structures. Their opinion (drunkenly expressed) was that the program semantics should be based on both. The wrinkle was was happened if you wanted to expose transformations of the underlying structure against the type when trying to say something reasonable about escape hatches. If I had a PPLTDHTWTPOAE (?) it'd have this capability for sure.
- jerf 6y ago
  Yes, as I was typing this up I began to realize that's where I was really going. Essentially turning an entire struct of, say, { int A; string B; Thingy C } into only a set of promises about being able to get an int, a string, a Thingy, etc., and promises around being able to set them (let's just do a struct for now, no methods or hiding), and then decoupling the type, being the set of promises being made, from the structure, being the concrete layout in memory and corresponding code capable of fulfilling those promises. It's all easy in the simple struct case, gets more interesting when you start trying to manipulate them by putting them into arrays or associative maps, etc. On the one hand, this is nearly revolutionary in some sense, but in another it's simply an incremental advance in a direction we're already going. "Object's are a poor man's closures, closures are a poor man's objects" being an old saying leaning in this direction, and it's hardly a new observation in Haskell that there's not a heck of a lot of practical difference between an associative array of X -> Y and a function (x -> y), at least when it comes to reading them.
  - thechao 6y ago
    In a language like Haskell, you'd parameterize every function by both the "data type" and the "data structure": monomorphization will happily emit ABI-compatible functions. I think a more interesting case is how you'd do this without a monomorphization explosion. It seems like being able to describe both subtyping and substructuring relationship (a la C's structure prefix ABI convention) would keep things mostly in check. I dunno... seems like you'd be combining all the hard bits of a nominative type system with all the hard bits of a polymorphic structural type subsystem.
chriswarbo 6y ago
The idea of "univalence", being pursued in Homotopy Type Theory (AKA HoTT), is that isomorphic types (i.e. we can convert back and forth without information loss) are equal, and hence one can be used in place of the other. The dream scenario is to write all of our libraries and application code using types that are the most straightforward (e.g. counting in unary, mapping over linked-lists, looking up values from lists of key/value pairs, etc.), then cast these to more efficient types (e.g. machine words, arrays, tries, etc.) for the final program. It's still ongoing, and a naive approach would simply lead to a bunch of conversion functions being scattered around (making the program even slower), so a smart approach would be needed, e.g. where compilers can fuse away these conversions.
- voxl 6y ago
  HoTT changes what equal means. In order for univalence to work you must be comfortable with arbitrary code running to perform the necessary substitutions. Isomorphism isn't for free, you can do some fancy cast-conversions (where cast is an identity function) that has been explored in generic zero-cost reuse [1] but this is not HoTT and uses essentially an UIP equality (which is inconsistent with HoTT). Your usage of the word "cast" in the second paragraph is a misnomer, because no systems programmer is going to want to perform an expensive transporation in HoTT! [1] https://arxiv.org/abs/1803.08150 https://arxiv.org/abs/1803.08150
  - rocqua 6y ago
    That sounds like, for performance reasons, you want control over the actual types used. But you could eliminate those changes from affecting the semantic representation of your program. Or at the very least with an easy check that the optimization doesn't affect your semantics.
  - chriswarbo 6y ago
    That's what I was getting at w.r.t. naive vs smart implementations. The point of univalence is that, from a logical/functional perspective, `slowFoo(slowX)` is indistinguishable from `fastToSlow(fastFoo(slowToFast(slowX)))`. Applying this to composite expressions will produce lots of calls like `slowToFast(fastToSlow(x))` which can be optimised down to `x`. The problem, of course, is that we can't enforce this within the logic (since those expressions are indistinguishable), so we must rely on compiler optimisations (i.e. deforestation/fusion). That link looks interesting, but appears to be more about re-using the same computational-content/runtime-representation for multiple compile-time/proof-context semantics (akin to McBride's "ornaments"), which seems more like a dual problem to that of swapping out slow representations for fast ones.
p1necone 6y ago
Isn't this just an interface in an OO language?

by jerf 6y ago

svrb 6y ago

Sign me up! I'm constantly defining `XYZ` and `PackedXYZ` for memory-bound problems and I have often though it would be nice to be able to do this (in a more generic way than mere bitfields). It never occurred to me that it could be extended to column stores though.

zero_iq 6y ago

Jonathan Blow's new language, Jai, has some control over layout allowing easy switching between array of structs and struct of arrays without having to change the accessing code.

andi999 6y ago
There is no Jai.
- jacobush 6y ago
  There Is Only IBM And AT&T And Exxon?
  - andi999 6y ago
    Could you explain? What I meant, I believe Jai is vaporware and gets too much attention. I mean Jai sound exciting until you find out that the download link is missing.
    - zero_iq 6y ago
      It's still under development, with no public release, but I think it's a bit unfair to call it vapourware, since he has produced plenty of material that demonstrates he has a working compiler and has clearly spent a great deal of time developing it, not just talking about it. Whether it gets too much attention is debatable. He has some good ideas, imo, worth exploring, although I don't agree with all of his opinions. He has a prominent enough profile that it will likely inspire others to incorporate features from Jai if they are seen to be desirable, even if Jai is not ultimately released. (Personally, I think it will eventually.)
      - andi999 6y ago
        Well, what is your hunch when it will be released? My expectation is eithet never, or there will be a release and it will crumble quickly when people want to do things with it.
clucas 6y ago
Here is the demo video of the stuff zero_iq is talking about: https://www.youtube.com/watch?v=ZHqFrNyLlpA https://www.youtube.com/watch?v=ZHqFrNyLlpA Basically right on point with what the GP is saying.
- epistasis 6y ago
  That video briefly mentions the CppCon 2014 talk by Mike Afton, "Data-oriented Design and C++". The talk was great, pretty much lined up with how I think of modern systems (treat RAM like disk: seeks take a long time, but streams will likely be able to maximize CPU usage) But the questions at the end, and the resistance to these basic ideas, roughly "what about platform portability, programmer productivity, etc."; these questions were a bit shocking to me. Is this not a C++ conference? This was six years ago, so perhaps the machine constraints were not as well known back then, but it really shows how strongly the community culture will influence a language and its capabilities.
runevault 6y ago
I thought he pulled that back out of the language, though with the intent of re implementing it with as a library with the metaprogramming facilities of the language for anyone who wanted it?
- jiggawatts 6y ago
  I haven't seen the update, but to me that seems a bit silly. This is a pretty fundamental type manipulation, and ideally the compiler would have some understanding of it...

thechao 6y ago

I was privy to a fairly high-wattage conversation between Walid Taha, Jeremy Siek, Todd Veldhuizen, et al, where they discussed this issue at length. They were concerned that languages almost universally equate data types with data structures. Their opinion (drunkenly expressed) was that the program semantics should be based on both. The wrinkle was was happened if you wanted to expose transformations of the underlying structure against the type when trying to say something reasonable about escape hatches. If I had a PPLTDHTWTPOAE (?) it'd have this capability for sure.

jerf 6y ago
Yes, as I was typing this up I began to realize that's where I was really going. Essentially turning an entire struct of, say, { int A; string B; Thingy C } into only a set of promises about being able to get an int, a string, a Thingy, etc., and promises around being able to set them (let's just do a struct for now, no methods or hiding), and then decoupling the type, being the set of promises being made, from the structure, being the concrete layout in memory and corresponding code capable of fulfilling those promises. It's all easy in the simple struct case, gets more interesting when you start trying to manipulate them by putting them into arrays or associative maps, etc. On the one hand, this is nearly revolutionary in some sense, but in another it's simply an incremental advance in a direction we're already going. "Object's are a poor man's closures, closures are a poor man's objects" being an old saying leaning in this direction, and it's hardly a new observation in Haskell that there's not a heck of a lot of practical difference between an associative array of X -> Y and a function (x -> y), at least when it comes to reading them.
- thechao 6y ago
  In a language like Haskell, you'd parameterize every function by both the "data type" and the "data structure": monomorphization will happily emit ABI-compatible functions. I think a more interesting case is how you'd do this without a monomorphization explosion. It seems like being able to describe both subtyping and substructuring relationship (a la C's structure prefix ABI convention) would keep things mostly in check. I dunno... seems like you'd be combining all the hard bits of a nominative type system with all the hard bits of a polymorphic structural type subsystem.

chriswarbo 6y ago

The idea of "univalence", being pursued in Homotopy Type Theory (AKA HoTT), is that isomorphic types (i.e. we can convert back and forth without information loss) are equal, and hence one can be used in place of the other. The dream scenario is to write all of our libraries and application code using types that are the most straightforward (e.g. counting in unary, mapping over linked-lists, looking up values from lists of key/value pairs, etc.), then cast these to more efficient types (e.g. machine words, arrays, tries, etc.) for the final program. It's still ongoing, and a naive approach would simply lead to a bunch of conversion functions being scattered around (making the program even slower), so a smart approach would be needed, e.g. where compilers can fuse away these conversions.

voxl 6y ago
HoTT changes what equal means. In order for univalence to work you must be comfortable with arbitrary code running to perform the necessary substitutions. Isomorphism isn't for free, you can do some fancy cast-conversions (where cast is an identity function) that has been explored in generic zero-cost reuse [1] but this is not HoTT and uses essentially an UIP equality (which is inconsistent with HoTT). Your usage of the word "cast" in the second paragraph is a misnomer, because no systems programmer is going to want to perform an expensive transporation in HoTT! [1] https://arxiv.org/abs/1803.08150 https://arxiv.org/abs/1803.08150
- rocqua 6y ago
  That sounds like, for performance reasons, you want control over the actual types used. But you could eliminate those changes from affecting the semantic representation of your program. Or at the very least with an easy check that the optimization doesn't affect your semantics.
- chriswarbo 6y ago
  That's what I was getting at w.r.t. naive vs smart implementations. The point of univalence is that, from a logical/functional perspective, `slowFoo(slowX)` is indistinguishable from `fastToSlow(fastFoo(slowToFast(slowX)))`. Applying this to composite expressions will produce lots of calls like `slowToFast(fastToSlow(x))` which can be optimised down to `x`. The problem, of course, is that we can't enforce this within the logic (since those expressions are indistinguishable), so we must rely on compiler optimisations (i.e. deforestation/fusion). That link looks interesting, but appears to be more about re-using the same computational-content/runtime-representation for multiple compile-time/proof-context semantics (akin to McBride's "ornaments"), which seems more like a dual problem to that of swapping out slow representations for fast ones.

p1necone 6y ago

Isn't this just an interface in an OO language?