• Jay (12/12) Apr 05 2019 Hello, My name is Jay Rajput.
• AltFunction1 (2/14) Apr 06 2019
• Seb (10/15) Apr 06 2019 Like all projects offered by DLang, we do expect a solid
• Jay (5/20) Apr 07 2019 Yeah, I have already put by GitHub id and the projects, which I
• Stefanos Baziotis (44/53) Apr 07 2019 Hello Jay,
• Jay (10/68) Apr 08 2019 Hey Stefanos, firstly thanks a lot for replying and helping out
• Stefanos Baziotis (12/22) Apr 08 2019 Do you mean dynamic memory allocation?
• Jay (4/27) Apr 09 2019 Thanks a ton, I will include the insights you gave me in the
• Stefanos Baziotis (6/9) Apr 09 2019 You're welcome and thank you!

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

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

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.

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

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!

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.

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

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

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