• spir <denis.spir gmail.com> Oct 14 2010
• bearophile <bearophileHUGS lycos.com> Oct 14 2010
• bearophile <bearophileHUGS lycos.com> Oct 14 2010
• bearophile <bearophileHUGS lycos.com> Oct 14 2010
• spir <denis.spir gmail.com> Oct 14 2010
• Andrej Mitrovic <andrej.mitrovich gmail.com> Oct 14 2010

spir <denis.spir gmail.com> writes:

Hello,

As a way to start learning D by practicing, I'm trying to implement a symbo=
l table as linked list: see prototype code of the structs below. (Hints abo=
ut good D coding welcome :-)

2 little questions about pointers:
1. To please the compiler, I had to wrap dereferencing in parens, like in "=
(*symbol).name". Is this just normal (for disambiguation)?
2. Just noticed the compiler accepts "symbol.name", while symbol is a point=
er: is there implicit dereferencing of pointers to structs? If yes, does th=
is also apply to pointers to arrays (for information, this what Oberon does=
).

And a note: had forgotten to add an empty main(), just for compiling: the l=
inker produced a rather big amount of error text without any hint to the ac=
tual issue. Maybe dmd could cope with that before calling gcc?

Finally: the reference is rather harsh for me, esp there are very few examp=
le (I have few practice of C, and none of C++); the bits of tutorials I fou=
nd are too light or just started (toc points to empty pages). Is there anyw=
here online a kind of D programming guide, even not polished or possibly un=
finished (I know about the book; maybe I'll order it, but in meantime...).

Thank you,
Denis

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D code =3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
struct Symbol {
    string name  =3D "" ;
    int element  =3D 0 ;
    Symbol* next =3D null ;
}
struct List {
    Symbol* first =3D null ;
    int element(string name) {
        Symbol* symbol =3D this.first ;
        while (symbol) {
            if ((*symbol).name =3D=3D  name) {return (*symbol).element ;} ;
            symbol =3D (*symbol).next ;
        }
        return 0 ;
    }
}
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

-- -- -- -- -- -- --
vit esse estrany =E2=98=A3

spir.wikidot.com

bearophile <bearophileHUGS lycos.com> writes:

spir:

 As a way to start learning D by practicing, I'm trying to implement a symbol
table as linked list: see prototype code of the structs below. (Hints about
good D coding welcome :-)


I have modified your code a little:

struct Symbol {
    string name;
    int element;
    Symbol* next;

    this(string n, int e, Symbol* s=null) {
        name = n;
        element = e;
        next = s;
    }
}

struct List {
    Symbol* first;

    int element(string name) {
        for (auto symbol = this.first; symbol != null; symbol = symbol.next)
            if (symbol.name == name)
                return symbol.element;
        return 0;
    }
}

void main() {
    auto l = List(new Symbol("baz", 3, new Symbol("bar", 2, new Symbol("foo",
1))));
    assert(l.element("bar") == 2);
}

- There's no need to initialize int to 0, string to "", pointers to null, etc,
the compiler does it for you on default. Each type has a default init value
(for floating point values it uses a NaN).
- Generally don't put a space before the ending semicolon.
- Four spaces indent and no space before the "*" of the pointer, as you have
done, is OK.
- Using a while loop as you have done is OK, I have used a for loop just to
show a shorter alternative.
- It's generally better to put one or two blank lines before structs,
functions, etc
- (*symbol).name is written symbol.name in D.
- After an { generally a \n is used, there's no need to use the ; after the }
- using 0 as error return value is sometimes OK, but also keep in mind that
exceptions are present.
- while(symbol) is acceptable, but some people prefer to put an explicit
comparison to make the code more readable.
- sometimes using "auto" helps.
- In D linked lists are doable, but much less used, think about using a dynamic
array, or even in this case an associative array:

void main() {
    auto aa = ["foo": 1, "bar": 2, "baz": 3];
    assert(aa["bar"] == 2);
}


 1. To please the compiler, I had to wrap dereferencing in parens, like in
"(*symbol).name". Is this just normal (for disambiguation)?
 2. Just noticed the compiler accepts "symbol.name", while symbol is a pointer:
is there implicit dereferencing of pointers to structs? If yes, does this also
apply to pointers to arrays (for information, this what Oberon does).


Generally the field dereferencing doesn't require the "(*symbol).name", in D
you use "symbol.name".
Pointers to arrays are possible, but quite uncommon in D.


 And a note: had forgotten to add an empty main(), just for compiling: the
linker produced a rather big amount of error text without any hint to the
actual issue. Maybe dmd could cope with that before calling gcc?


I agree, I have bug report 4680 open on something similar:
http://d.puremagic.com/issues/show_bug.cgi?id=4680


 Finally: the reference is rather harsh for me, esp there are very few example
(I have few practice of C, and none of C++); the bits of tutorials I found are
too light or just started (toc points to empty pages). Is there anywhere online
a kind of D programming guide, even not polished or possibly unfinished (I know
about the book; maybe I'll order it, but in meantime...).


The D2 documentation isn't abundant yet :-)

Bye,
bearophile

bearophile <bearophileHUGS lycos.com> writes:

spir:

 (Hope you don't mind if I send other bits of code to be improved that way?)


Feel free to show them, if I am busy other people may give you an answer. The
worst that may happen is that no one answers you.


 Right. I think at keeping explicit defaults like "int element = 0" for
documentation.


Not putting a value, unless it's different from the standard initializator, is
a very common idiom in D. It's easy to remember the inits: zero, empty string,
NaN, null, invalid Unicode chars.


 If I ever write a lib for public use, I'll follow such styling guidelines ;-)


The D style:
http://www.digitalmars.com/d/2.0/dstyle.html


 Wouldn't have ever thought that the "stepping" statement of a for loop can be
something else as incrementation.


This is a kind of incrementation:
symbol = symbol.next;

In C-derived languages this line of code:
symbol = symbol + 5;
May be written:
symbol += 5;

In the same way you may think of this (this is not D syntax):
symbol .= next;
As a compact version of:
symbol = symbol.next;


 Right, guess you mean while(symbol != null)?


Right. But some people don't like that.


 I need to explore this further (what's the actual purpose of "auto").


It just asks the compiler to use the default type, it performs a bit of local
type inferencing.


 For curiosity, I intend to benchmark lists vs sequential arrays vs associative
arrays, for various element counts.


Good, it's a way to understand the language better. In the lists vs dynamic
array I suggest you to also take a look at the produced (dis)assembly.


 to know what kind of data structures were suited for symbol tables
representing the content of record-like objects, which number of entries is
typically small since hand-written by the programmer: sophisticated structures
like associative arrays and tries started to perform better than plain
sequences for counts >> 100.)<


D dynamic arrays are not bad, but they are not very efficient, so a sequential
scan in a small array of integer numbers is faster than an hash search.

You may also try a "perfect hash", for your purpose. Around you may find C code
(that's easy to translate to D) to create a perfect hash out of a sequence of
strings.

A binary search in an array of strings-int pairs is an easy option too.

If your symbol are names are short you may also put your string+int pairs in a
single flat data structure (even keeping a fixed length for each one of them),
to increase CPU cache locality a bit, something like:

struct Pair { char[10] name; int element; }
Pair[20] data;

In C/C++/D languages usually there are *many* complicated ways to speed up code
:-) You generally want to use them only in the spots where the profiler tells
you you need performance. The profiler is used with the DMD -profile switch.

It's also good if you learn D to start using unittests and design by contract
from the beginning. They help a lot avoid bugs. And the more hairy (pointers,
etc) your code is, the more useful they are.

Bye,
bearophile

bearophile <bearophileHUGS lycos.com> writes:

 D dynamic arrays are not bad, but they are not very efficient,


I meant associative array, sorry.

spir <denis.spir gmail.com> writes:

On Thu, 14 Oct 2010 17:16:23 -0400
bearophile <bearophileHUGS lycos.com> wrote:

 spir:
=20
 As a way to start learning D by practicing, I'm trying to implement a s=




 about good D coding welcome :-)
=20
 I have modified your code a little:
=20
 struct Symbol {
     string name;
     int element;
     Symbol* next;
=20
     this(string n, int e, Symbol* s=3Dnull) {
         name =3D n;
         element =3D e;
         next =3D s;
     }
 }
=20
 struct List {
     Symbol* first;
=20
     int element(string name) {
         for (auto symbol =3D this.first; symbol !=3D null; symbol =3D sym=


             if (symbol.name =3D=3D name)
                 return symbol.element;
         return 0;
     }
 }
=20
 void main() {
     auto l =3D List(new Symbol("baz", 3, new Symbol("bar", 2, new Symbol(=


     assert(l.element("bar") =3D=3D 2);
 }


Thank you very much! That's exactly what I need to learn good practice, eve=
n more with comments below. (Hope you don't mind if I send other bits of co=
de to be improved that way?)

 - There's no need to initialize int to 0, string to "", pointers to null,=


 value (for floating point values it uses a NaN).

Right. I think at keeping explicit defaults like "int element =3D 0" for do=
cumentation. It means "that's precisely what I want as default value", as o=
pposed to just the language's "init". (So, for Symbol fields, I would only =
write element & next defaults explicitely, since name has no meaningful def=
ault: it must be provided.)

 - Generally don't put a space before the ending semicolon.
 - Four spaces indent and no space before the "*" of the pointer, as you h=


 - It's generally better to put one or two blank lines before structs, fun=



(About ';', I like to separate actual code from grammatical separators, whi=
ch are just noise to my eyes. If I ever write a lib for public use, I'll fo=
llow such styling guidelines ;-)

 - Using a while loop as you have done is OK, I have used a for loop just =



Thanks, as I said I'm not used to PLs of the C family. Wouldn't have ever t=
hought that the "stepping" statement of a for loop can be something else as=
 incrementation.

 - (*symbol).name is written symbol.name in D.


Very good.

 - After an { generally a \n is used, there's no need to use the ; after t=



Right.

 - using 0 as error return value is sometimes OK, but also keep in mind th=



;-) Was just a placeholder before I decide how to cope with "finding failur=
e".

 - while(symbol) is acceptable, but some people prefer to put an explicit =



Right, guess you mean while(symbol !=3D null)?

 - sometimes using "auto" helps.


I need to explore this further (what's the actual purpose of "auto").

 - In D linked lists are doable, but much less used, think about using a d=


 void main() {
     auto aa =3D ["foo": 1, "bar": 2, "baz": 3];
     assert(aa["bar"] =3D=3D 2);
 }


Yes, it was just an exercise. For curiosity, I intend to benchmark lists vs=
 sequential arrays vs associative arrays, for various element counts.
(Did that already in another language (freepascal), to know what kind of da=
ta structures were suited for symbol tables representing the content of rec=
ord-like objects, which number of entries is typically small since hand-wri=
tten by the programmer: sophisticated structures like associative arrays an=
d tries started to perform better than plain sequences for counts >> 100.)

 1. To please the compiler, I had to wrap dereferencing in parens, like =




 2. Just noticed the compiler accepts "symbol.name", while symbol is a p=




s this also apply to pointers to arrays (for information, this what Oberon =
does).
=20
 Generally the field dereferencing doesn't require the "(*symbol).name", i=


 Pointers to arrays are possible, but quite uncommon in D.


Sure, there are builtin dynamic arrays :-)
I'll check whether manually pointed arrays also silently dereferencing (on =
element access, on attribute access)?

 And a note: had forgotten to add an empty main(), just for compiling: t=




e actual issue. Maybe dmd could cope with that before calling gcc?
=20
 I agree, I have bug report 4680 open on something similar:
 http://d.puremagic.com/issues/show_bug.cgi?id=3D4680


Good.

 Finally: the reference is rather harsh for me, esp there are very few e=




 found are too light or just started (toc points to empty pages). Is there =
anywhere online a kind of D programming guide, even not polished or possibl=
y unfinished (I know about the book; maybe I'll order it, but in meantime..=
.).
=20
 The D2 documentation isn't abundant yet :-)


I'll do what I can on one of the already started wikibooks about D if I fin=
d energy for that...

 Bye,
 bearophile


Thanks again,
Denis
-- -- -- -- -- -- --
vit esse estrany =E2=98=A3

spir.wikidot.com

Andrej Mitrovic <andrej.mitrovich gmail.com> writes:

On 10/14/10, bearophile <bearophileHUGS lycos.com> wrote:

 Generally the field dereferencing doesn't require the "(*symbol).name", in D
 you use "symbol.name".
 Pointers to arrays are possible, but quite uncommon in D.


I'm not sure, but I think function pointers (the C syntax ones, not
variables declared with function/delegate) still need parenthesis for
dereferencing? IIRC I was getting back some weird errors a few days
ago when I was trying it out. I might be wrong though..