www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - idiomatic D: what to use instead of pointers in constructing a tree

reply "Laeeth Isharc" <laeethnospam spammenot_laeeth.com> writes:
Another schoolboy question.

Suppose I am constructing a tree (in this case it is an AST).  In 
C I would have a pointer for the child to find the parent, and an 
array or linked list of pointers to find the children from the 
parent.

Obviously, I could still use pointers, but that would not be 
idiomatic.

I also could just use integer array index references.

A slice seems overkill to refer to just one object, but is that 
the best way ?
Jan 07 2015
next sibling parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Wed, Jan 07, 2015 at 02:52:51PM +0000, Laeeth Isharc via Digitalmars-d-learn
wrote:

 Another schoolboy question.
 
 Suppose I am constructing a tree (in this case it is an AST).  In C I
 would have a pointer for the child to find the parent, and an array or
 linked list of pointers to find the children from the parent.
 
 Obviously, I could still use pointers, but that would not be
 idiomatic.


Not true. If you're using a tree structure, you *should* use pointers.
Unless you're using classes, which are by-reference, in which case you
can just use the class as-is. :-)


--T
Jan 07 2015
next sibling parent reply "Laeeth Isharc" <laeethnospam spammenot_laeeth.com> writes:
  Not true. If you're using a tree structure, you *should* use

 pointers.
 Unless you're using classes, which are by-reference, in which 
 case you
 can just use the class as-is. :-)


Thanks v much.

I just came to that realization also when I stepped away.

class node
{
	string name;
	node ref;
}

what's wrong with the code above ?  i get an error no identifier 
for declarator node.  (I have not used classes much, since 
structs often seem to be enough for what I need to do mostly).
Jan 07 2015
next sibling parent reply "Paulo Pinto" <pjmlp progtools.org> writes:
On Wednesday, 7 January 2015 at 15:02:34 UTC, Laeeth Isharc wrote:

  Not true. If you're using a tree structure, you *should* use

 pointers.
 Unless you're using classes, which are by-reference, in which 
 case you
 can just use the class as-is. :-)


 Thanks v much.

 I just came to that realization also when I stepped away.

 class node
 {
 	string name;
 	node ref;
 }

 what's wrong with the code above ?  i get an error no 
 identifier for declarator node.  (I have not used classes much, 
 since structs often seem to be enough for what I need to do 
 mostly).


ref is a reserved keyword.

--
Paulo
Jan 07 2015
next sibling parent "Laeeth Isharc" <laeethnospam spammenot_laeeth.com> writes:
 ref is a reserved keyword.


doh!

Thanks.
Jan 07 2015
prev sibling parent reply "Baz" <bb.temp gmx.com> writes:
On Wednesday, 7 January 2015 at 15:04:24 UTC, Paulo  Pinto wrote:

 On Wednesday, 7 January 2015 at 15:02:34 UTC, Laeeth Isharc 
 wrote:

 Not true. If you're using a tree structure, you *should* use

 pointers.
 Unless you're using classes, which are by-reference, in which 
 case you
 can just use the class as-is. :-)


 Thanks v much.

 I just came to that realization also when I stepped away.

 class node
 {
 	string name;
 	node ref;
 }

 what's wrong with the code above ?  i get an error no 
 identifier for declarator node.  (I have not used classes 
 much, since structs often seem to be enough for what I need to 
 do mostly).


 ref is a reserved keyword.

 --
 Paulo


this conversation is so funny: well what's wrong with this . It's 
a keyword...
Aa Ha ha ha ha , rol.
Seriously, is it so complicated to use a D editor ? I mean with 
syntax color...
Jan 07 2015
next sibling parent "Tobias Pankrath" <tobias pankrath.net> writes:
 what's wrong with the code above ?  i get an error no 
 identifier for declarator node.  (I have not used classes 
 much, since structs often seem to be enough for what I need 
 to do mostly).


 ref is a reserved keyword.

 --
 Paulo


 this conversation is so funny: well what's wrong with this . 
 It's a keyword...
 Aa Ha ha ha ha , rol.
 Seriously, is it so complicated to use a D editor ? I mean with 
 syntax color...


No need to make fun of anyone.
Jan 08 2015
prev sibling parent reply "Laeeth Isharc" <Laeethnospam nospam.laeeth.com> writes:
 this conversation is so funny: well what's wrong with this . 
 It's a keyword...
 Aa Ha ha ha ha , rol.
 Seriously, is it so complicated to use a D editor ? I mean with 
 syntax color...


Man afraid to ask stoopid questions stays stoopid.  And compiler 
error message far from informative.
Not everyone is very visually oriented, and sometimes vi is 
quicker.
Jan 08 2015
next sibling parent "Mengu" <mengukagan gmail.com> writes:
On Thursday, 8 January 2015 at 11:29:30 UTC, Laeeth Isharc wrote:

 this conversation is so funny: well what's wrong with this . 
 It's a keyword...
 Aa Ha ha ha ha , rol.
 Seriously, is it so complicated to use a D editor ? I mean 
 with syntax color...


 Man afraid to ask stoopid questions stays stoopid.  And 
 compiler error message far from informative.
 Not everyone is very visually oriented, and sometimes vi is 
 quicker.


don't worry about it. use whatever you're comfortable with.
Jan 08 2015
prev sibling parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Thu, Jan 08, 2015 at 11:29:29AM +0000, Laeeth Isharc via Digitalmars-d-learn
wrote:

 

this conversation is so funny: well what's wrong with this . It's a
keyword...
Aa Ha ha ha ha , rol.
Seriously, is it so complicated to use a D editor ? I mean with
syntax color...


 
 Man afraid to ask stoopid questions stays stoopid.  And compiler error
 message far from informative.
 Not everyone is very visually oriented, and sometimes vi is quicker.


Vim supports syntax highlighting.

But I don't use it either -- I find it distracts from clarity of
thought. I use plain vanilla vim in a text-only terminal.


T

-- 
Those who've learned LaTeX swear by it. Those who are learning LaTeX swear at
it. -- Pete Bleackley
Jan 08 2015
next sibling parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 01/08/2015 09:40 AM, H. S. Teoh via Digitalmars-d-learn wrote:


 Vim supports syntax highlighting.

 But I don't use it either -- I find it distracts from clarity of
 thought. I use plain vanilla vim in a text-only terminal.


I am halfway there: I use syntax highlighting in Emacs but I chose to 
make keywords and variables the same color.

Ali
Jan 08 2015
prev sibling parent reply "Paulo Pinto" <pjmlp progtools.org> writes:
On Thursday, 8 January 2015 at 17:42:23 UTC, H. S. Teoh via 
Digitalmars-d-learn wrote:

 On Thu, Jan 08, 2015 at 11:29:29AM +0000, Laeeth Isharc via 
 Digitalmars-d-learn wrote:

 

this conversation is so funny: well what's wrong with this . 
It's a
keyword...
Aa Ha ha ha ha , rol.
Seriously, is it so complicated to use a D editor ? I mean 
with
syntax color...


 
 Man afraid to ask stoopid questions stays stoopid.  And 
 compiler error
 message far from informative.
 Not everyone is very visually oriented, and sometimes vi is 
 quicker.


 Vim supports syntax highlighting.

 But I don't use it either -- I find it distracts from clarity of
 thought. I use plain vanilla vim in a text-only terminal.


 T


I don't get this, then again I am using syntax highlighting 
editors since MS-DOS IDEs supported it.

--
Paulo
Jan 08 2015
parent "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Thu, Jan 08, 2015 at 07:13:28PM +0000, Paulo Pinto via Digitalmars-d-learn
wrote:

 On Thursday, 8 January 2015 at 17:42:23 UTC, H. S. Teoh via
 Digitalmars-d-learn wrote:


[...]

Vim supports syntax highlighting.

But I don't use it either -- I find it distracts from clarity of
thought. I use plain vanilla vim in a text-only terminal.




[...]

 I don't get this, then again I am using syntax highlighting editors
 since MS-DOS IDEs supported it.


[...]

It's just a personal preference. I find that overuse of colors produces
a kaleidoscopic rainbow pattern on the screen which, while pretty,
distracts from the essence of the code itself, which is what I'm
focusing on. It's like a webpage with every other word italicized and/or
bolded -- after a while, your brain just tunes it out and it becomes
just meaningless (and distracting) noise. I much rather learn to parse
the text (resp. code) accurately by eye and let it speak for itself.


T

-- 
Those who've learned LaTeX swear by it. Those who are learning LaTeX swear at
it. -- Pete Bleackley
Jan 08 2015
prev sibling parent reply Joseph Rushton Wakeling via Digitalmars-d-learn writes:
On 07/01/15 16:02, Laeeth Isharc via Digitalmars-d-learn wrote:

 class node
 {
      string name;
      node ref;
 }


Small recommendation (apart from the reserved word issue which you fixed): it's 
generally considered good D style to give structs and classes names that start 
with capital letters, JustLikeThis.  So, I suggest Node rather than node.

Very minor point, and of course, your code is yours to style as you wish, but
it 
can be helpful to meet the "standard" style conventions in order to make it as 
easy as possible for everyone else to understand.

See also: http://dlang.org/dstyle.html
Jan 08 2015
parent "Laeeth Isharc" <laeethnospam nospamlaeeth.com> writes:
 Small recommendation (apart from the reserved word issue which 
 you fixed): it's generally considered good D style to give 
 structs and classes names that start with capital letters, 
 JustLikeThis.  So, I suggest Node rather than node.

 Very minor point, and of course, your code is yours to style as 
 you wish, but it can be helpful to meet the "standard" style 
 conventions in order to make it as easy as possible for 
 everyone else to understand.



Thanks for the reminder.  I use D Style when I am writing 
properly, but haven't yet internalized it for a quick example and 
old habits die hard.
Jan 10 2015
prev sibling parent reply "Laeeth Isharc" <laeethnospam spammenot_laeeth.com> writes:
On Wednesday, 7 January 2015 at 14:59:58 UTC, H. S. Teoh via 
Digitalmars-d-learn wrote:

 On Wed, Jan 07, 2015 at 02:52:51PM +0000, Laeeth Isharc via 
 Digitalmars-d-learn wrote:

 Another schoolboy question.
 
 Suppose I am constructing a tree (in this case it is an AST).  
 In C I
 would have a pointer for the child to find the parent, and an 
 array or
 linked list of pointers to find the children from the parent.
 
 Obviously, I could still use pointers, but that would not be
 idiomatic.


 Not true. If you're using a tree structure, you *should* use 
 pointers.
 Unless you're using classes, which are by-reference, in which 
 case you
 can just use the class as-is. :-)


 --T


The GC is allowed to move structs around, as I undestand it.  
Under what circumstances do I get into trouble having a pointer 
to them?
Jan 13 2015
parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
On Tuesday, 13 January 2015 at 17:19:42 UTC, Laeeth Isharc wrote:

 The GC is allowed to move structs around, as I undestand it.  
 Under what circumstances do I get into trouble having a pointer 
 to them?


None, a GC that moves structs around must update every pointer 
afterwards and as far as I know, the standard GC doesn't do that 
(moving things around).

You may not have a pointer inside a struct that points to the 
struct itself. This allows the compiler to elide some copies.
Jan 13 2015
parent reply "Laeeth Isharc" <laeethnospam nospamlaeeth.com> writes:
On Tuesday, 13 January 2015 at 17:41:53 UTC, Tobias Pankrath 
wrote:

 On Tuesday, 13 January 2015 at 17:19:42 UTC, Laeeth Isharc 
 wrote:

 The GC is allowed to move structs around, as I undestand it.  
 Under what circumstances do I get into trouble having a 
 pointer to them?


 None, a GC that moves structs around must update every pointer 
 afterwards and as far as I know, the standard GC doesn't do 
 that (moving things around).

 You may not have a pointer inside a struct that points to the 
 struct itself. This allows the compiler to elide some copies.


Got it - thanks.
Jan 14 2015
parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Wed, Jan 14, 2015 at 07:05:16PM +0000, Laeeth Isharc via Digitalmars-d-learn
wrote:

 On Tuesday, 13 January 2015 at 17:41:53 UTC, Tobias Pankrath wrote:

On Tuesday, 13 January 2015 at 17:19:42 UTC, Laeeth Isharc wrote:

The GC is allowed to move structs around, as I undestand it.  Under
what circumstances do I get into trouble having a pointer to them?


None, a GC that moves structs around must update every pointer
afterwards and as far as I know, the standard GC doesn't do that
(moving things around).

You may not have a pointer inside a struct that points to the struct
itself. This allows the compiler to elide some copies.


 
 Got it - thanks.


Having a pointer inside a struct that points to itself can also cause
unexpected and sometimes very hard to find bugs. Example from real code
where this bug occurred:

	struct S {
		// Resources we wish to cleanup
		Resource1 r1;
		Resource2 r2;
		...

		// List of cleanup routines we'd like to run when the
		// struct is destroyed.
		void delegate()[] cleanups;

		this(...) {
			// Acquire a resource
			r1 = acquireResource1();

			// Clean it up once we're done.
			// N.B.: the delegate implicitly closes over
			// 'this' -- this is what gets us in trouble
			// later.
			cleanups ~= { freeResource1(this.r1); };

			r2 = acquireResource2();
			cleanups ~= { freeResource2(this.r2); };

			...
		}

		~this() {
			// Cleanup resources in reverse order we
			// acquired them.
			foreach_reverse(dg; cleanups) {
				dg();
			}
		}
	}

	/* This function works without any problems. */
	void func1() {
		auto s = S(...); // create an instance of S
		doStuff();
		// Here, S gets cleaned up, and S's dtor releases the
		// resources correctly. No problem.
	}

	/* The following pair of functions, however, have problems... */
	S makeS() {
		// This is just a convenience function for creating an
		// instance of S. Useful for factoring out any messy
		// implementation details that may be needed from the
		// body of func2().
		return S(...);
	}
	void func2() {
		// Make an instance of S, as before.
		auto s = makeS();

		// Do some stuff
		doStuff();

		// And now we are done, so s's dtor should cleanup.
		// ... except, it crashes instead. Why??
	}

func1() runs perfectly normally, no problem. However, func2() crashes
upon exit. Why?

The reason is that the delegates created by S.this() close over the
'this' pointer to the new instance of S. But since S is a struct, this
pointer is actually a pointer to a local variable on the stack of the
caller. This is not a problem in func1() because this local variable
resides in the same scope as the body of func1(), so the cleanup
delegates get invoked before the local variable goes out of scope.
However, in makeS(), we are returning a newly-created instance of S. The
compiler actually implements this by creating a temporary local variable
to hold the new instance of S, which means the 'this' pointer closed
over by the delegates points to this temporary local variable, and then
when the new instance of S is returned to func2(), since S is a by-value
type, it gets bitwise copied into *another* local variable, that is, 's'
in func2(). So the instance of S that func2() sees is actually a
different copy of S than the one created by makeS(). The copy created by
makeS() has now gone out of scope; however, the delegates registered in
s.cleanups have not been adjusted, so they are still closing over the
address of the original copy of S in makeS().

Now when func2() finishes and prepares to return, s's dtor gets invoked,
and it calls the cleanup delegates which attempt to access the instance
of S at the original address, which is now invalid. The result is that
they see garbage data instead of the real values of .r1 and .r2, and it
crashes the program. (If you're lucky, that is. If you're not so lucky,
it won't crash, but will corrupt memory and/or get into an inconsistent
state which causes malfunctions later on. Good luck tracing down the
problem then!)

Moral of the story: don't have struct fields that point to the struct
itself. This is almost always a bad idea. Structs have value semantics,
and the implicit copying around will almost certainly break any
self-referencing pointers, which leads to dangling pointers, good
friends of memory corruption, et al. :-P


T

-- 
Trying to define yourself is like trying to bite your own teeth. -- Alan Watts
Jan 14 2015
parent reply "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Wednesday, 14 January 2015 at 19:36:44 UTC, H. S. Teoh via 
Digitalmars-d-learn wrote:

 Moral of the story: don't have struct fields that point to the 
 struct
 itself. This is almost always a bad idea. Structs have value 
 semantics,
 and the implicit copying around will almost certainly break any
 self-referencing pointers, which leads to dangling pointers, 
 good
 friends of memory corruption, et al. :-P


If it actually had value semantics you would not be allowed to 
take the address of it... :-P
Jan 14 2015
parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Wed, Jan 14, 2015 at 07:43:17PM +0000, via Digitalmars-d-learn wrote:

 On Wednesday, 14 January 2015 at 19:36:44 UTC, H. S. Teoh via
 Digitalmars-d-learn wrote:

Moral of the story: don't have struct fields that point to the struct
itself. This is almost always a bad idea. Structs have value
semantics, and the implicit copying around will almost certainly
break any self-referencing pointers, which leads to dangling
pointers, good friends of memory corruption, et al. :-P


 
 If it actually had value semantics you would not be allowed to take
 the address of it... :-P


Huh? ints have value semantics, yet you can take the address of a local
int variable. What's your point?


T

-- 
Not all rumours are as misleading as this one.
Jan 14 2015
parent reply "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Wednesday, 14 January 2015 at 20:23:26 UTC, H. S. Teoh via 
Digitalmars-d-learn wrote:

 Huh? ints have value semantics, yet you can take the address of 
 a local
 int variable. What's your point?


Strictly speaking the "int" looses its value semantics if you 
take the address of it, hold it and give it a new name (assign it 
to a pointer). It is forced to be an object with an identity 
(cannot sit in a register and is no longer alias free and 
indistinguishable from other ints with same value). Same issue 
with your struct, you turn it into an object with identity by 
holding the identity, yet keep acting if it is a value.

C's type system has questionable soundness, but I guess it could 
be corrected with behavioural typing... I.e. the preceding events 
and the state is part of the type and determines what actions it 
can participate it. Like a behavioural type for a file would make 
it an error at compile time to close a file before opening it. 
You could do something similar for taking the address of an int. 
(Which is kinda what linear typing tries to do.)
Jan 14 2015
parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
(( It follows from this that it will be challenging to achieve 
full memory safety without fixing the type system first. ))
Jan 14 2015
prev sibling parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
  A slice seems overkill to refer to just one object, but is that

 the best way ?


struct Tree
{
     Tree[] children;
}

Is one way to do it.
Jan 07 2015
parent reply "Meta" <jared771 gmail.com> writes:
On Wednesday, 7 January 2015 at 16:17:47 UTC, Tobias Pankrath 
wrote:

  A slice seems overkill to refer to just one object, but is that

 the best way ?


 struct Tree
 {
     Tree[] children;
 }

 Is one way to do it.


You can add some nice sugar for this as well:

struct Tree
{
     this(string data, Tree[] children...)
     {
         this.data = data;
         this.children = children;
     }

     string data;
     Tree[] children;
}

http://dpaste.dzfl.pl/76a8a4c44345
Jan 07 2015
parent reply "anonymous" <anonymous example.com> writes:
On Wednesday, 7 January 2015 at 20:25:10 UTC, Meta wrote:

 struct Tree
 {
     this(string data, Tree[] children...)
     {
         this.data = data;
         this.children = children;


Don't do this without `dup`ing. Quoting the documentation:


 An implementation may construct the object or array instance on 
 the stack. Therefore, it is an error to refer to that instance 
 after the variadic function has returned:


[...]

 int[] test(int[] a ...)
 {
    return a;       // error, array contents invalid after return
    return a[0..1]; // error, array contents invalid after return
    return a.dup;   // ok, since copy is made
}


http://dlang.org/function#variadic


     }

     string data;
     Tree[] children;
 }
Jan 07 2015
parent reply "Meta" <jared771 gmail.com> writes:
On Wednesday, 7 January 2015 at 23:27:19 UTC, anonymous wrote:

 Don't do this without `dup`ing. Quoting the documentation:


Oh, whoops. I thought those special variadic args were always 
allocated on the heap.
Jan 07 2015
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 1/8/15 12:15 AM, Meta wrote:

 On Wednesday, 7 January 2015 at 23:27:19 UTC, anonymous wrote:

 Don't do this without `dup`ing. Quoting the documentation:


 Oh, whoops. I thought those special variadic args were always allocated
 on the heap.


Nope,

Which makes it annoying, what if the argument IS passed on the heap?

Fortunately, there is a solution (one I use in dcollections):

foo(T[] x...)
foo(T[] x)

Can be overloaded. If you ever pass in parameters one at a time, the 
first is called, and x is guaranteed to be on the stack.

The second is called with an actual array only, you are able to not 
'dup', and just warn people that x will NOT be dup'd in that case.

-Steve
Jan 08 2015