www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - [GSOC] Persistent Data Structures detailed information

reply Jay <jay24rajput gmail.com> writes:
Hello, My name is Jay Rajput.

In Persistent Data Structures, I am planning to implement DS 
algos for lists, sets, trees,etc.. Should these data structures 
store elements of different data types at the same time? ( like 
python)
eg: list=['hello',123,67,98]

Also, it would be really helpful if someone can brief me about 
the pre-requisites. I have implemented all the data Structures in 
C, also I have taken courses in Advanced Algorithms and 
Functional Programming.

Thanks,
Jay Rajput
Apr 05
next sibling parent AltFunction1 <af1af1af1 af1.af1> writes:
On Friday, 5 April 2019 at 15:00:43 UTC, Jay wrote:
 Hello, My name is Jay Rajput.

 In Persistent Data Structures, I am planning to implement DS 
 algos for lists, sets, trees,etc.. Should these data structures 
 store elements of different data types at the same time? ( like 
 python)
 eg: list=['hello',123,67,98]
No, people can use a Variant as item type for that.
 Also, it would be really helpful if someone can brief me about 
 the pre-requisites. I have implemented all the data Structures 
 in C, also I have taken courses in Advanced Algorithms and 
 Functional Programming.

 Thanks,
 Jay Rajput
Apr 06
prev sibling parent reply Seb <seb wilzba.ch> writes:
On Friday, 5 April 2019 at 15:00:43 UTC, Jay wrote:
 Also, it would be really helpful if someone can brief me about 
 the pre-requisites. I have implemented all the data Structures 
 in C, also I have taken courses in Advanced Algorithms and 
 Functional Programming.
Like all projects offered by DLang, we do expect a solid programming background (doesn't have to be in D) and at least first experiences with D. We are realistic here and understand that most students will have their first big dive into D during the GSoC. tl;dr: we're more interested in your prior Open Source history and your personal story.
 I have implemented all the data Structures in C
In your example I would advise you to add a link to e.g. your GitHub repository with this content to support your claim.
Apr 06
parent reply Jay <jay24rajput gmail.com> writes:
On Saturday, 6 April 2019 at 22:21:55 UTC, Seb wrote:
 On Friday, 5 April 2019 at 15:00:43 UTC, Jay wrote:
 Also, it would be really helpful if someone can brief me about 
 the pre-requisites. I have implemented all the data Structures 
 in C, also I have taken courses in Advanced Algorithms and 
 Functional Programming.
Like all projects offered by DLang, we do expect a solid programming background (doesn't have to be in D) and at least first experiences with D. We are realistic here and understand that most students will have their first big dive into D during the GSoC. tl;dr: we're more interested in your prior Open Source history and your personal story.
 I have implemented all the data Structures in C
In your example I would advise you to add a link to e.g. your GitHub repository with this content to support your claim.
Yeah, I have already put by GitHub id and the projects, which I have performed. To support by algorithms and data structure knowledge, I am attaching the links to my Codechef and Hackerrank ids. Would that be good to go??
Apr 07
parent reply Stefanos Baziotis <sdi1600105 di.uoa.gr> writes:
On Sunday, 7 April 2019 at 17:33:10 UTC, Jay wrote:
 Yeah, I have already put by GitHub id and the projects, which I 
 have performed. To support by algorithms and data structure 
 knowledge, I am attaching the links to my Codechef and 
 Hackerrank ids. Would that be good to go??
Hello Jay, Since I'm also applying for the persistent data structures, I may be able to offer some help. Here's my take on the matter: I should point out first that a lot of this understanding emerged from a response from Andrei. However, I'm still waiting for a review in the proposal and a response for some clarification, so take this with a grain of salt, this is only my current understanding. So, the main question in implementing persistent data structures in D is not "How do I implement persistent data structures?". I think this is well-studied and more of a general matter. Rather, the problem is more specific to D and it is "How do these data structures handle memory?". Somewhat quoting Andrei:
 The thing is that most people would not want these DSs to use
 the garbage collector, i.e. employ some sort of reference 
 counting.
 However, changing the reference count destroys the concept of 
 immutability.
Another way to look at it (for me) is that the DS has to allocate memory, but if this memory comes from GC, then the GC might at some point free a previous version of the DS. Now, one could reason that this breaks only the theoretical model (i.e. we lost one version, so the DS is not persistent) but not the practical since the GC will only free unreachable code. But the problem is that if we take a mark and sweep GC (I really don't know what techniques the D GC employs), the GC will actually compact the reachable memory pages, i.e. it will move memory around. That means that if you have a direct pointer to some of this memory then access, pointer arithmetic etc. goes out of the window. I think that this will be a problem since from what I have seen, in D the GC never works with direct pointers. All this results in that you have to allocate memory out of the type system. To be honest, this is where I start to lose it... I proposed that a simple strongly-typed allocator (i.e. not C Standard Library malloc returning void*) might help to do these allocations but doesn't seem like a good solution (both to me and I guess everyone else). Good luck!
Apr 07
parent reply Jay <jay24rajput gmail.com> writes:
On Sunday, 7 April 2019 at 18:19:48 UTC, Stefanos Baziotis wrote:
 On Sunday, 7 April 2019 at 17:33:10 UTC, Jay wrote:
 Yeah, I have already put by GitHub id and the projects, which 
 I have performed. To support by algorithms and data structure 
 knowledge, I am attaching the links to my Codechef and 
 Hackerrank ids. Would that be good to go??
Hello Jay, Since I'm also applying for the persistent data structures, I may be able to offer some help. Here's my take on the matter: I should point out first that a lot of this understanding emerged from a response from Andrei. However, I'm still waiting for a review in the proposal and a response for some clarification, so take this with a grain of salt, this is only my current understanding. So, the main question in implementing persistent data structures in D is not "How do I implement persistent data structures?". I think this is well-studied and more of a general matter. Rather, the problem is more specific to D and it is "How do these data structures handle memory?". Somewhat quoting Andrei:
 The thing is that most people would not want these DSs to use
 the garbage collector, i.e. employ some sort of reference 
 counting.
 However, changing the reference count destroys the concept of 
 immutability.
Another way to look at it (for me) is that the DS has to allocate memory, but if this memory comes from GC, then the GC might at some point free a previous version of the DS. Now, one could reason that this breaks only the theoretical model (i.e. we lost one version, so the DS is not persistent) but not the practical since the GC will only free unreachable code. But the problem is that if we take a mark and sweep GC (I really don't know what techniques the D GC employs), the GC will actually compact the reachable memory pages, i.e. it will move memory around. That means that if you have a direct pointer to some of this memory then access, pointer arithmetic etc. goes out of the window. I think that this will be a problem since from what I have seen, in D the GC never works with direct pointers. All this results in that you have to allocate memory out of the type system. To be honest, this is where I start to lose it... I proposed that a simple strongly-typed allocator (i.e. not C Standard Library malloc returning void*) might help to do these allocations but doesn't seem like a good solution (both to me and I guess everyone else). Good luck!
Hey Stefanos, firstly thanks a lot for replying and helping out even though you are submitting a proposal for the same project :-p. It hadn't even come to my notice that D does not have a malloc-like function for dynamic address generation. All I can think of as of now is interfacing c++ library in creating the data structure, but as it won't be the best solution the only option we have is implementing a <stdlib.h> like library. Would love to hear your any other ideas on the same.
Apr 08
parent reply Stefanos Baziotis <sdi1600105 di.uoa.gr> writes:
On Monday, 8 April 2019 at 11:32:01 UTC, Jay wrote:
 Hey Stefanos, firstly thanks a lot for replying and helping out 
 even though you are submitting a proposal for the same project 
 :-p.
It's a team sport :)
 It hadn't even come to my notice that D does not have a 
 malloc-like function for dynamic address generation.
Do you mean dynamic memory allocation?
 All I can think of as of now is interfacing c++ library in 
 creating the data structure, but as it won't be the best 
 solution the only option we have is implementing a <stdlib.h> 
 like library. Would love to hear your any other ideas on the 
 same.
Roughly this is what I meant with the creation of a strongly-typed allocator, but not a C++ one, rather a D one. There's a great discussion of this here [1] which is about another GSoC idea. Even then though, it still doesn't seem like a very good plan to me. [1] https://forum.dlang.org/thread/pvhacqomqgnhmqienfpi forum.dlang.org
Apr 08
parent reply Jay <jay24rajput gmail.com> writes:
On Monday, 8 April 2019 at 12:59:44 UTC, Stefanos Baziotis wrote:
 On Monday, 8 April 2019 at 11:32:01 UTC, Jay wrote:
 Hey Stefanos, firstly thanks a lot for replying and helping 
 out even though you are submitting a proposal for the same 
 project :-p.
It's a team sport :)
 It hadn't even come to my notice that D does not have a 
 malloc-like function for dynamic address generation.
Do you mean dynamic memory allocation?
 All I can think of as of now is interfacing c++ library in 
 creating the data structure, but as it won't be the best 
 solution the only option we have is implementing a <stdlib.h> 
 like library. Would love to hear your any other ideas on the 
 same.
Roughly this is what I meant with the creation of a strongly-typed allocator, but not a C++ one, rather a D one. There's a great discussion of this here [1] which is about another GSoC idea. Even then though, it still doesn't seem like a very good plan to me. [1] https://forum.dlang.org/thread/pvhacqomqgnhmqienfpi forum.dlang.org
Thanks a ton, I will include the insights you gave me in the proposal. All the best for both the projects. :)
Apr 09
parent Stefanos Baziotis <sdi1600105 di.uoa.gr> writes:
On Tuesday, 9 April 2019 at 14:42:42 UTC, Jay wrote:
 Thanks a ton, I will include the insights you gave me in the 
 proposal.

 All the best for both the projects. :)
You're welcome and thank you! I would like if the project mentors mentioned whether there is any interest on this project (I dropped my proposal for that reason, so good luck!). - Stefanos
Apr 09