Re: std.container: fork in the road
On 06/18/2015 06:44 PM, Andrei Alexandrescu wrote: Thanks for the input. So I'll go with the option of adding std.experimental.collection and leave std.container be at least for now. There'll be std.experimental.collection.mutable and std.experimental.collection.functional because they have complementary strengths. Any pointers to functional data structures aside from the classics (Okasaki and Scala's containers), please post them here. Thanks, Andrei There's also the ephemeral/persistent terminology. https://en.wikipedia.org/wiki/Persistent_data_structure
Re: std.container: fork in the road
Thanks for the input. So I'll go with the option of adding std.experimental.collection and leave std.container be at least for now. There'll be std.experimental.collection.mutable and std.experimental.collection.functional because they have complementary strengths. Any pointers to functional data structures aside from the classics (Okasaki and Scala's containers), please post them here. Thanks, Andrei
Re: std.container: fork in the road
On Thursday, 18 June 2015 at 16:44:04 UTC, Andrei Alexandrescu wrote: Thanks for the input. So I'll go with the option of adding std.experimental.collection and leave std.container be at least for now. There'll be std.experimental.collection.mutable and std.experimental.collection.functional because they have complementary strengths. Any pointers to functional data structures aside from the classics (Okasaki and Scala's containers), please post them here. Thanks, Andrei http://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki
Re: std.container: fork in the road
On Tue, 16 Jun 2015 23:08:56 -0700, Andrei Alexandrescu wrote: > ... I strongly favor going with 3. There is no need to be tied up to the old design in anyway and there is no need to break people's code. If the name is such an issue for some people, I suggest `std.container.v2`.
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: Took a fresh look at std.container from a Design by Introspection perspective, and my assessment is as follows: ... Andrei 2 or 3, I wouldn't mind breaking changes, personally I feel like D has gotten too scared of breaking changes and it's holding it back(but that's OT). I use Dlists and Slists a lot but that is is, everything else in containers seems completely unusable/unfinished to me. Having allocator support is a must.
Re: std.container: fork in the road
1. Just keep the current spec and deal with it. Some containers are and will remain garbage collected because they started as such. Add new containers that are better alongside them. 2. Do break compatibility of containers, mainly by taking advantage of them being under-documented. In a way we wouldn't break much because not much has been specified. There are, however, parts where we'd need to change specification. 3. Leave std.container alone and move forward with std.experimental.collection. I am confident the language and its endorsed idioms have reached enough maturity to not make this addition into a regular event. Andrei 3 or 2. std.allocator support is important as well (otherwise may as well continue rolling my own incomplete containers). std.container was always 'sorta usable' but never good enough.
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: This is another manifestation of the systemic problem of our community that's been discussed here in the past - there are matters that greatly affect negatively the uptake of D, yet they stay unresolved for literally months and years in spite of being trivially simple. For a potential user who sees today "std.container" in the library offering list, the subsequent click will lead almost by necessity to a vote of non-confidence. Is there a central list of such matters? Should we make one?
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 16:00:30 UTC, Wyatt wrote: I guess I'll have to wait for Adam's write-up, then. I'm probably going to write that one tomorrow, but won't post it until Sunday night/Monday morning. The short of it is to check for what methods are available instead of trying to name each possible combination. So instead of like checking if(is(A == DealloctableAllocator)), check if(hasMember!(A, "deallocate")) The combination of potential methods makes it easier to look at one bit at a time instead of trying to abstract them all into concepts.
Re: std.container: fork in the road
(3)
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 16:21:18 UTC, ixid wrote: On Wednesday, 17 June 2015 at 15:57:38 UTC, Wyatt wrote: But "sanity" and "API versioning" may exist at opposite ends of a spectrum, if I recall my history. What are the downsides? Issues, off the top of my head: figuring out which is which in the first place, separate compilation causing multiple modules to pull in different versions of the same symbols, run-time linking hell when external libraries are added to the mix, and library bloat when different projects depend on different versions. I'm reasonably certain there are other things too. It _might_ be possible to do sanely if this had all been worked out from the outset for D/D2, but I'm not at all confident that it's possible to retrofit (rather, I expect it isn't). -Wyatt
Re: std.container: fork in the road
On 6/17/15 8:17 AM, rsw0x wrote: On Wednesday, 17 June 2015 at 15:03:40 UTC, Andrei Alexandrescu wrote: On 6/17/15 2:59 AM, "Marc =?UTF-8?B?U2Now7x0eiI=?= " wrote: I think this decision should be left to the end-user. A container that supports only RC is just as bad as one that supports only GC. Instead, use SList!T or SList!(Unique!T) or SList(RefCounted!T) as appropriate. All internal metadata, on the other hand, should be treated as owned by the container. Calling clear() or removing individual elements needs to destroy the associated meta data, which in turn will correctly call the payload's (e.g. RefCounted!T or Unique!T) destructor if it has one. Yah, management strategy refers to the metadata. -- Andrei Do you plan on std.collections being usable both with and without the GC? Collections are a perfect candidate for reference counted management. (a) Orderly structure so the likelihood of cycles is arguably lower than for arbitrary object models; (b) "Heavy", i.e. collections tend to be large enough to warrant care with allocation and deallocation. -- Andrei
Re: std.container: fork in the road
On 6/17/15 7:57 AM, Wyatt wrote: On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: Took a fresh look at std.container from a Design by Introspection perspective I've seen you use this term a few times now; what does it mean? (Lack of) Google results seem to indicate it's your own neologism. Yah, it's the topic of my DConf talk. Need to write an article about it, and probably a book too because it's an awesome topic. -- Andrei
Re: std.container: fork in the road
On Wed, 17 Jun 2015 14:57:38 +, Wyatt wrote: > 'm not > using std.container anywhere and I suspect it's much the same for most > everyone else. it seems that people rolling their own containers, preferring to stay away from "std.container". so i don't think that it is used anywhere except some "helloworld" tries (and maybe another 2.5 projects at max). rename it to "std.container.unusable" and write new "std.conainer". signature.asc Description: PGP signature
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 15:57:38 UTC, Wyatt wrote: On Wednesday, 17 June 2015 at 15:29:34 UTC, ixid wrote: On Wednesday, 17 June 2015 at 14:57:40 UTC, Wyatt wrote: but std.collection isn't nearly so good a name. std.container2 and so on? Dunno. That's not something that really needs addressed right now, is it? Off-the-cuff, in an ideal world there would be some way of easily knowing which API was intended and forwarding to std.deprecated on an as-needed basis (with a warning when it happens). But "sanity" and "API versioning" may exist at opposite ends of a spectrum, if I recall my history. -Wyatt What are the downsides? It would make it explicit what tutorials and programs were referring to in a very clear way, as well as abandon the pretense of a library being in stasis.
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 15:50:51 UTC, John Colvin wrote: On Wednesday, 17 June 2015 at 14:57:40 UTC, Wyatt wrote: On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: Took a fresh look at std.container from a Design by Introspection perspective I've seen you use this term a few times now; what does it mean? (Lack of) Google results seem to indicate it's your own neologism. It comes from Andrei's DConf talk. Oh. I guess I'll have to wait for Adam's write-up, then. Or has it been expanded in written form elsewhere? -Wyatt
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 15:29:34 UTC, ixid wrote: On Wednesday, 17 June 2015 at 14:57:40 UTC, Wyatt wrote: but std.collection isn't nearly so good a name. std.container2 and so on? Dunno. That's not something that really needs addressed right now, is it? Off-the-cuff, in an ideal world there would be some way of easily knowing which API was intended and forwarding to std.deprecated on an as-needed basis (with a warning when it happens). But "sanity" and "API versioning" may exist at opposite ends of a spectrum, if I recall my history. -Wyatt
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 14:57:40 UTC, Wyatt wrote: On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: Took a fresh look at std.container from a Design by Introspection perspective I've seen you use this term a few times now; what does it mean? (Lack of) Google results seem to indicate it's your own neologism. It comes from Andrei's DConf talk.
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: 2. Do break compatibility of containers, mainly by taking advantage of them being under-documented. In a way we wouldn't break much because not much has been specified. There are, however, parts where we'd need to change specification. 3. Leave std.container alone and move forward with std.experimental.collection. I am confident the language and its endorsed idioms have reached enough maturity to not make this addition into a regular event. Andrei 2. would break code, but I feel 3. would break semantics; collection != container. A container might contain 2 collections, and a collection might span 2 containers. I can have a collection where part of the data is stored in one kind of container, and other parts are stored in other types of containers, to exploit certain properties of containers against data access patterns. Also, in std.collection I might expect push-based collections. No, I consider containers to be at a lower level of abstraction compared to collections. I am favoring std.deprecated. Although the poor chap compiling old code in a few years from now is going to have a great time figuring out he needs to change an import. It'll take him half a day to type 12 goddamn letters :)
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 14:57:40 UTC, Wyatt wrote: On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: Took a fresh look at std.container from a Design by Introspection perspective I've seen you use this term a few times now; what does it mean? (Lack of) Google results seem to indicate it's your own neologism. * The documentation is appallingly bad, making std.container worse than non-existent. I tried using it a couple times. Failed miserably every time. Regarding compatibility, I see three possibilities: #breakmycode! ...is my first impulse. But really it doesn't matter much-- I'm not using std.container anywhere and I suspect it's much the same for most everyone else. I guess option 3 is fine, but std.collection isn't nearly so good a name. -Wyatt std.container2 and so on?
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: Took a fresh look at std.container from a Design by Introspection perspective, and my assessment is as follows: [...] (3)
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 15:03:40 UTC, Andrei Alexandrescu wrote: On 6/17/15 2:59 AM, "Marc =?UTF-8?B?U2Now7x0eiI=?= " wrote: I think this decision should be left to the end-user. A container that supports only RC is just as bad as one that supports only GC. Instead, use SList!T or SList!(Unique!T) or SList(RefCounted!T) as appropriate. All internal metadata, on the other hand, should be treated as owned by the container. Calling clear() or removing individual elements needs to destroy the associated meta data, which in turn will correctly call the payload's (e.g. RefCounted!T or Unique!T) destructor if it has one. Yah, management strategy refers to the metadata. -- Andrei Do you plan on std.collections being usable both with and without the GC?
Re: std.container: fork in the road
On 6/17/15 2:59 AM, "Marc =?UTF-8?B?U2Now7x0eiI=?= " wrote: I think this decision should be left to the end-user. A container that supports only RC is just as bad as one that supports only GC. Instead, use SList!T or SList!(Unique!T) or SList(RefCounted!T) as appropriate. All internal metadata, on the other hand, should be treated as owned by the container. Calling clear() or removing individual elements needs to destroy the associated meta data, which in turn will correctly call the payload's (e.g. RefCounted!T or Unique!T) destructor if it has one. Yah, management strategy refers to the metadata. -- Andrei
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: Took a fresh look at std.container from a Design by Introspection perspective I've seen you use this term a few times now; what does it mean? (Lack of) Google results seem to indicate it's your own neologism. * The documentation is appallingly bad, making std.container worse than non-existent. I tried using it a couple times. Failed miserably every time. Regarding compatibility, I see three possibilities: #breakmycode! ...is my first impulse. But really it doesn't matter much-- I'm not using std.container anywhere and I suspect it's much the same for most everyone else. I guess option 3 is fine, but std.collection isn't nearly so good a name. -Wyatt
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: Regarding compatibility, I see three possibilities: I believe that at this moment it is necessary to implement step 3, but... In the future, it is necessary to refine and revise std.container.
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: Even if we implement the change to be memory-safe, there's still changes in semantics (e.g. the behavior of orphan ranges changes). And even if we change behavior that wasn't specified explicitly in the docs, it's still a change in behavior. The same goes for other functions that remove elements from containers. std.container.gc and std.container.rc? Oh, and one more thing I noticed: * The documentation is appallingly bad, making std.container worse than non-existent. We have a liability squared to deal with here. I've pretended to myself I hadn't implemented SList and it was nigh impossible to use it competently from documentation alone, let alone understand the deeper architectural underpinnings that apply to other containers. This is another manifestation of the systemic problem of our community that's been discussed here in the past - there are matters that greatly affect negatively the uptake of D, yet they stay unresolved for literally months and years in spite of being trivially simple. For a potential user who sees today "std.container" in the library offering list, the subsequent click will lead almost by necessity to a vote of non-confidence. I will take a look at the docs over the next couple of days and see if I can improve them. Regarding compatibility, I see three possibilities: 1. Just keep the current spec and deal with it. Some containers are and will remain garbage collected because they started as such. Add new containers that are better alongside them. 2. Do break compatibility of containers, mainly by taking advantage of them being under-documented. In a way we wouldn't break much because not much has been specified. There are, however, parts where we'd need to change specification. 3. Leave std.container alone and move forward with std.experimental.collection. I am confident the language and its endorsed idioms have reached enough maturity to not make this addition into a regular event. 3 seems to be the best option, or 1 in a pinch. I don't think 2 is really necessary if std.container is separated into GC'd and RC'd containers. As an aside, I've only used std.container once, to port some trivial Java code to D. I ended up spending far more time than was necessary trying to get my code to even compile, due to issues such as RedBlackTree!(int, (a, b) => a < b) and RedBlackTree(int, (a, b) => a < b) being two different types. It did not leave me with a good impression of std.container.
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: 3. Leave std.container alone and move forward with std.experimental.collection. I am confident the language and its endorsed idioms have reached enough maturity to not make this addition into a regular event. How about 3 with a forwards compatible naming convention?
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: 3. Leave std.container alone and move forward with std.experimental.collection. I am confident the language and its endorsed idioms have reached enough maturity to not make this addition into a regular event. I'm really not a fan of "collection" or "collections" and think that container is a far better name, but if we want to avoid breaking existing code, I don't think that we have much choice but to rename it - though for myself, I wouldn't mind just having std.container be fixed in a manner that breaks existing code. I'd rather deal with the code breakage than the name collection or collections, but as a community, that's probably not a good way to go about things, particularly since we do want to minimize breakage to the times when we really need to break code. - Jonathan M Davis
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: Regarding compatibility, I see three possibilities: 1. Just keep the current spec and deal with it. Some containers are and will remain garbage collected because they started as such. Add new containers that are better alongside them. 2. Do break compatibility of containers, mainly by taking advantage of them being under-documented. In a way we wouldn't break much because not much has been specified. There are, however, parts where we'd need to change specification. 3. Leave std.container alone and move forward with std.experimental.collection. I am confident the language and its endorsed idioms have reached enough maturity to not make this addition into a regular event. Andrei 2 or 3 Better 3. And I like idea to move std.container to std.deprecated container in future.
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: Took a fresh look at std.container from a Design by Introspection perspective, and my assessment is as follows: [...] 3. Implement std.experimental.collection and leave std.container for backwards compatibility. Then follow the usual deprecation path.
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: Regarding compatibility, I see three possibilities: 1. Just keep the current spec and deal with it. Some containers are and will remain garbage collected because they started as such. Add new containers that are better alongside them. 2. Do break compatibility of containers, mainly by taking advantage of them being under-documented. In a way we wouldn't break much because not much has been specified. There are, however, parts where we'd need to change specification. 3. Leave std.container alone and move forward with std.experimental.collection. I am confident the language and its endorsed idioms have reached enough maturity to not make this addition into a regular event. Andrei (2) or (3) please.
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 10:58:58 UTC, weaselcat wrote: (3) After some more thought, I agree with this. std.container could just be warned against using in favor of std.collections. I agree, deprecation is a good balance between the agile evolution of D contra user friendlieness.
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 10:07:17 UTC, Walter Bright wrote: (3) After some more thought, I agree with this. std.container could just be warned against using in favor of std.collections.
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 10:07:17 UTC, Walter Bright wrote: (3) 3, it facilitates benchmarking both implementations in apps, even when using the binary d distriburion.
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: Regarding compatibility, I see three possibilities: 1. Just keep the current spec and deal with it. Some containers are and will remain garbage collected because they started as such. Add new containers that are better alongside them. 2. Do break compatibility of containers, mainly by taking advantage of them being under-documented. In a way we wouldn't break much because not much has been specified. There are, however, parts where we'd need to change specification. 3. Leave std.container alone and move forward with std.experimental.collection. I am confident the language and its endorsed idioms have reached enough maturity to not make this addition into a regular event. Andrei One vote for 2. Never used std.container, and when occasionally it didn't last long. For example, Array does not use the GC but is not @nogc etc.
Re: std.container: fork in the road
(3)
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: Consider e.g. "SList!T.clear()". Right now it's O(1) and only reassigns the root to point to no element, thus leaving all elements to be collected. Moreover, if there are ranges iterating the now cleared list, they'll just continue wandering in the desert as if nothing happened. What I think SList should do is first switch to a refcounted implementation. Then, clear() should call destroy() for payloads of all nodes, safely invalidate all ranges, and deallocate memory allocated for all nodes. I think this decision should be left to the end-user. A container that supports only RC is just as bad as one that supports only GC. Instead, use SList!T or SList!(Unique!T) or SList(RefCounted!T) as appropriate. All internal metadata, on the other hand, should be treated as owned by the container. Calling clear() or removing individual elements needs to destroy the associated meta data, which in turn will correctly call the payload's (e.g. RefCounted!T or Unique!T) destructor if it has one.
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: ... 2. I've never used std.container, it looks incomplete.
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: 1. Just keep the current spec and deal with it. Some containers are and will remain garbage collected because they started as such. Add new containers that are better alongside them. 2. Do break compatibility of containers, mainly by taking advantage of them being under-documented. In a way we wouldn't break much because not much has been specified. There are, however, parts where we'd need to change specification. 3. Leave std.container alone and move forward with std.experimental.collection. I am confident the language and its endorsed idioms have reached enough maturity to not make this addition into a regular event. 2. std.container has always looked like a draft, discouraging from actually using it for something serious.
Re: std.container: fork in the road
On 6/17/2015 3:08 PM, Andrei Alexandrescu wrote: Regarding compatibility, I see three possibilities: 1. Just keep the current spec and deal with it. Some containers are and will remain garbage collected because they started as such. Add new containers that are better alongside them. 2. Do break compatibility of containers, mainly by taking advantage of them being under-documented. In a way we wouldn't break much because not much has been specified. There are, however, parts where we'd need to change specification. 3. Leave std.container alone and move forward with std.experimental.collection. I am confident the language and its endorsed idioms have reached enough maturity to not make this addition into a regular event. My vote goes for 2. I've always understood std.container to be incomplete anyway, waiting for the day that std.allocator is ready.
Re: std.container: fork in the road
On Wednesday, 17 June 2015 at 06:08:57 UTC, Andrei Alexandrescu wrote: 1. Just keep the current spec and deal with it. Some containers are and will remain garbage collected because they started as such. Add new containers that are better alongside them. 2. Do break compatibility of containers, mainly by taking advantage of them being under-documented. In a way we wouldn't break much because not much has been specified. There are, however, parts where we'd need to change specification. 3. Leave std.container alone and move forward with std.experimental.collection. I am confident the language and its endorsed idioms have reached enough maturity to not make this addition into a regular event. Andrei My vote for 2 or 3. Is it a stupid idea to move std.container to std.deprecated.container? So if someone still need that, he just needs to change import probably. Andrea
Re: std.container: fork in the road
On 17/06/2015 6:08 p.m., Andrei Alexandrescu wrote: Took a fresh look at std.container from a Design by Introspection perspective, and my assessment is as follows: * The current design of std.container is adequate but requires rather verbose implementations because it predates UFCS. For example, containers that define "stableRemove" must also alias "remove" to it etc. It's quite tedious to define complete containers. * It is possible to make things a lot better by taking advantage of DbI and UFCS. This does break client code, but only really odd cases that use advanced introspection to inspect methods of containers. * Things could and should be taken further to manage memory better. However, that's liable to produce subtle code breakages. Consider e.g. "SList!T.clear()". Right now it's O(1) and only reassigns the root to point to no element, thus leaving all elements to be collected. Moreover, if there are ranges iterating the now cleared list, they'll just continue wandering in the desert as if nothing happened. What I think SList should do is first switch to a refcounted implementation. Then, clear() should call destroy() for payloads of all nodes, safely invalidate all ranges, and deallocate memory allocated for all nodes. Even if we implement the change to be memory-safe, there's still changes in semantics (e.g. the behavior of orphan ranges changes). And even if we change behavior that wasn't specified explicitly in the docs, it's still a change in behavior. The same goes for other functions that remove elements from containers. Oh, and one more thing I noticed: * The documentation is appallingly bad, making std.container worse than non-existent. We have a liability squared to deal with here. I've pretended to myself I hadn't implemented SList and it was nigh impossible to use it competently from documentation alone, let alone understand the deeper architectural underpinnings that apply to other containers. This is another manifestation of the systemic problem of our community that's been discussed here in the past - there are matters that greatly affect negatively the uptake of D, yet they stay unresolved for literally months and years in spite of being trivially simple. For a potential user who sees today "std.container" in the library offering list, the subsequent click will lead almost by necessity to a vote of non-confidence. Regarding compatibility, I see three possibilities: 1. Just keep the current spec and deal with it. Some containers are and will remain garbage collected because they started as such. Add new containers that are better alongside them. 2. Do break compatibility of containers, mainly by taking advantage of them being under-documented. In a way we wouldn't break much because not much has been specified. There are, however, parts where we'd need to change specification. 3. Leave std.container alone and move forward with std.experimental.collection. I am confident the language and its endorsed idioms have reached enough maturity to not make this addition into a regular event. Andrei 2 please. At least to me they feel just unfinished. They should also support std.allocator. This is a biggy. As well as reserving of elements. Things have changed as you said since it was originally written. We now have new requirements.