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

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

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.

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??

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!

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.

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

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. :)

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