Describing a tree

[Nick Keighley]

"Nick Keighley"<[email protected]>  ha scritto nel messaggioA possibly dumb question: Given a labeled or unlabeled tree
(in the sense of graphs), how could one best use C to describe it?
what form is it in now or how are you going to enter it?
/* tree.c */
#include<stdio.h>
typedef struct tree_tag
{
    char *data;
    struct tree_tag *left;
    struct tree_tag *right;
} Tree;
void walk (Tree *tree)
{
    if (tree != NULL)
    {
        printf ("%s ", tree->data);
        walk (tree->left);
        walk (tree->right);
    }
}
int main (void)
{
    Tree yggdrasil[] =
    {
        {"red",&yggdrasil[1],&yggdrasil[2]},
        {"blue",&yggdrasil[3],&yggdrasil[4]},
        {"black", 0, 0},
        {"yellow", 0, 0},
        {"green", 0, 0}
    };
    walk (yggdrasil);
    return 0;
}
Error E2063 tree1.c 27: Illegal initialization in function main
*** 1 errors in Compile ***

I'm surprised! It compiled and executed ok for me with an old Windows
compiler. And on gcc unless I stuck -pedantic on... ok fair cop

It's perfectly valid C.

ah yes, even with pedantic I only got

D:\bin\net>gcc -W -Wall -pedantic -ansi tree.c
tree.c: In function `main':
tree.c:27: warning: initializer element is not computable at load time
[several times]

 

[Ersek, Laszlo]

struct node {
const char *label;
const struct node *left, *right;
};

const struct node mytree[] = {
{"root", &mytree[1], &mytree[2]},
{"left", &mytree[3], 0},
{"right", 0, &mytree[4]},
{"leftleft", 0, 0},
{"rightright", 0, 0}
};

This is great!

Inside the initializer, the array object ("mytree") has incomplete type
and is not yet defined. So one couldn't use "sizeof mytree", for example.
However, since "mytree" is already declared and it decays to a pointer to
its first element, "mytree + offset" works.

Thanks,
lacos

 

[Ben Bacarisse]

"Nick Keighley"<[email protected]>  ha scritto nel messaggioOn 20 July, 13:10, Mok-Kong Shen<[email protected]>  wrote:

A possibly dumb question: Given a labeled or unlabeled tree
(in the sense of graphs), how could one best use C to describe it?

what form is it in now or how are you going to enter it?

/* tree.c */

typedef struct tree_tag
{
    char *data;
    struct tree_tag *left;
    struct tree_tag *right;
} Tree;

void walk (Tree *tree)
{
    if (tree != NULL)
    {
        printf ("%s ", tree->data);
        walk (tree->left);
        walk (tree->right);
    }
}

int main (void)
{
    Tree yggdrasil[] =
    {
        {"red",&yggdrasil[1],&yggdrasil[2]},
        {"blue",&yggdrasil[3],&yggdrasil[4]},
        {"black", 0, 0},
        {"yellow", 0, 0},
        {"green", 0, 0}
    };

    walk (yggdrasil);
    return 0;
}

Error E2063 tree1.c 27: Illegal initialization in function main
*** 1 errors in Compile ***

I'm surprised! It compiled and executed ok for me with an old Windows
compiler. And on gcc unless I stuck -pedantic on... ok fair cop

It's perfectly valid C.

I'd say that it is not. An implementation is permitted to reject the
code which goes against what most people would call perfectly valid C.

ah yes, even with pedantic I only got

D:\bin\net>gcc -W -Wall -pedantic -ansi tree.c
tree.c: In function `main':
tree.c:27: warning: initializer element is not computable at load time
[several times]

That does not tell you if it is or is not valid C!

The standard says that when an address constant references an object it
much be a static object. I.e. a conforming C implementation can reject
(but, as it happens, need not reject) the program. Is that "perfectly
valid C"? I'd say not, although it is OK in the sense that an
implementation may permit other forms of constant expression so there is
no reason that it should not be accepted. If you use that sort of
construct your code won't always compile on other systems.

 

[Ian Collins]

On 07/21/10 07:17 PM, Nick Keighley wrote:

int main (void)
{
Tree yggdrasil[] =
{
{"red",&yggdrasil[1],&yggdrasil[2]},
{"blue",&yggdrasil[3],&yggdrasil[4]},
{"black", 0, 0},
{"yellow", 0, 0},
{"green", 0, 0}
};


It's perfectly valid C.

I'd say that it is not. An implementation is permitted to reject the
code which goes against what most people would call perfectly valid C.

ah yes, even with pedantic I only got

D:\bin\net>gcc -W -Wall -pedantic -ansi tree.c
tree.c: In function `main':
tree.c:27: warning: initializer element is not computable at load time
[several times]

That does not tell you if it is or is not valid C!

If you compile for the correct version of C, it is.

The standard says that when an address constant references an object it
much be a static object. I.e. a conforming C implementation can reject
(but, as it happens, need not reject) the program. Is that "perfectly
valid C"? I'd say not, although it is OK in the sense that an
implementation may permit other forms of constant expression so there is
no reason that it should not be accepted. If you use that sort of
construct your code won't always compile on other systems.

Both C99 compilers I tried are happy with the code, C89 compilers
complained.

 

[Mok-Kong Shen]

Nick Keighley:

"natural trees"!? You mean like The Larch? What properties natural
trees do you wish to describe? Phylogeny? Morphology? Leaf count?
Beetle count?

I don't know enough to correctly answer in your terms. An example of
what I thoght of is a tree structure that is commonly seen in
literatures on evolution of the diverse biological species.

M. K. Shen

 

[Ben Bacarisse]

On 07/21/10 07:17 PM, Nick Keighley wrote:

int main (void)
{
Tree yggdrasil[] =
{
{"red",&yggdrasil[1],&yggdrasil[2]},
{"blue",&yggdrasil[3],&yggdrasil[4]},
{"black", 0, 0},
{"yellow", 0, 0},
{"green", 0, 0}
};


It's perfectly valid C.

I'd say that it is not. An implementation is permitted to reject the
code which goes against what most people would call perfectly valid C.

ah yes, even with pedantic I only got

D:\bin\net>gcc -W -Wall -pedantic -ansi tree.c
tree.c: In function `main':
tree.c:27: warning: initializer element is not computable at load time
[several times]

That does not tell you if it is or is not valid C!

If you compile for the correct version of C, it is.

Sorry, I don't follow you. All I am saying is that a warning from gcc
does not tell you if the code is valid.

The error is not a constraint violation so a compiler need not say a
word about it. Had gcc been silent on the matter you could not conclude
that the code is fine. Equally, gcc is permitted to warn about anything
it likes, so a warning does not mean that the code is not valid.

Both C99 compilers I tried are happy with the code, C89 compilers
complained.

I still don't get your point. It's good that the C89 compilers
complained but what do you mean by pointing out that the C99 ones are
happy with it? Does that lead you to believe that there is no problem
with the construct?

No C99 compiler need diagnose the error (well, lets's call it an
extension rather than an error) so the fact that they seem happy does
not tell you much about the validity of the construct.

 

[Ben Bacarisse]

On 07/21/10 07:17 PM, Nick Keighley wrote:

int main (void)
{
Tree yggdrasil[] =
{
{"red",&yggdrasil[1],&yggdrasil[2]},
{"blue",&yggdrasil[3],&yggdrasil[4]},
{"black", 0, 0},
{"yellow", 0, 0},
{"green", 0, 0}
};


It's perfectly valid C.

I'd say that it is not. An implementation is permitted to reject the
code which goes against what most people would call perfectly valid C.

ah yes, even with pedantic I only got

D:\bin\net>gcc -W -Wall -pedantic -ansi tree.c
tree.c: In function `main':
tree.c:27: warning: initializer element is not computable at load time
[several times]

That does not tell you if it is or is not valid C!

If you compile for the correct version of C, it is.

Yup. Scratch my last reply. Trying to read to many things at once I
got my versions all mixed. I'd summarise what I think is the case about
this only I am sure I'd make even more confusion.

It's fine in C99.

 

[Ben Bacarisse]

On 07/21/10 07:17 PM, Nick Keighley wrote:

int main (void)
{
Tree yggdrasil[] =
{
{"red",&yggdrasil[1],&yggdrasil[2]},
{"blue",&yggdrasil[3],&yggdrasil[4]},
{"black", 0, 0},
{"yellow", 0, 0},
{"green", 0, 0}
};


It's perfectly valid C.

I'd say that it is not. An implementation is permitted to reject the
code which goes against what most people would call perfectly valid C.

ah yes, even with pedantic I only got

D:\bin\net>gcc -W -Wall -pedantic -ansi tree.c
tree.c: In function `main':
tree.c:27: warning: initializer element is not computable at load time
[several times]

That does not tell you if it is or is not valid C!

If you compile for the correct version of C, it is.

Sorry, I don't follow you. All I am saying is that a warning from gcc
does not tell you if the code is valid.

For the record: I follow now! This is a C89 /C99 difference (though I
can't claim that was why I said what I said -- in fact I have no idea
*what* I was thinking!).

The error is not a constraint violation so a compiler need not say a
word about it. Had gcc been silent on the matter you could not conclude
that the code is fine. Equally, gcc is permitted to warn about anything
it likes, so a warning does not mean that the code is not valid.

This is all correct but it clouds the issue because the code is, in
fact, fine.

I still don't get your point. It's good that the C89 compilers
complained but what do you mean by pointing out that the C99 ones are
happy with it? Does that lead you to believe that there is no problem
with the construct?

As indeed you should!

Sorry for the confusion. I hope this correction is fast enough to
prevent the confusion spreading any further.

<snip>

 

[Ian Collins]

For the record: I follow now! This is a C89 /C99 difference (though I
can't claim that was why I said what I said -- in fact I have no idea
*what* I was thinking!).


This is all correct but it clouds the issue because the code is, in
fact, fine.



As indeed you should!

Sorry for the confusion. I hope this correction is fast enough to
prevent the confusion spreading any further.

Just in time. I was composing a reply when yours popped up!

I'm sorry I was so vague in my earlier replies, if I'd just said "It's
perfectly valid C99", much bandwidth would have been saved.

 

[Ben Bacarisse]

Just in time. I was composing a reply when yours popped up!

I'm sorry I was so vague in my earlier replies, if I'd just said "It's
perfectly valid C99", much bandwidth would have been saved.

I wish I could accept that gracious thought, but you did say that --
word for word! There is no need to think you should have to repeat
yourself just because I was having some kind of brain burp.

 

[Ersek, Laszlo]

On 07/21/10 07:17 PM, Nick Keighley wrote:

int main (void)
{
Tree yggdrasil[] =
{
{"red",&yggdrasil[1],&yggdrasil[2]},
{"blue",&yggdrasil[3],&yggdrasil[4]},
{"black", 0, 0},
{"yellow", 0, 0},
{"green", 0, 0}
};


It's perfectly valid C.

I'd say that it is not. An implementation is permitted to reject the
code which goes against what most people would call perfectly valid C.

ah yes, even with pedantic I only got

D:\bin\net>gcc -W -Wall -pedantic -ansi tree.c
tree.c: In function `main':
tree.c:27: warning: initializer element is not computable at load time
[several times]

That does not tell you if it is or is not valid C!

If you compile for the correct version of C, it is.

Yup. Scratch my last reply. Trying to read to many things at once I
got my versions all mixed. I'd summarise what I think is the case about
this only I am sure I'd make even more confusion.

It's fine in C99.

C89 6.5.7 "Initialization", p4 (in "Constraints"):

"All the expressions in an initializer for an object that has static
storage duration or in an initializer list for an object that has
aggregate or union type shall be constant expressions."


C99 6.7.8 "Initialization", p4 (in "Constraints"):

"All the expressions in an initializer for an object that has static
storage duration shall be constant expressions or string literals."


"&yggdrasil[1]" in the above is not an address constant, because
"yggdrasil"'s storage duration is not static (it's auto). This holds for
both C89 (6.4) and C99 (6.6 p7,9). Consequently, using "&yggdrasil[1]" in
the initializer list for "yggdrasil" (which has array, ie. aggregate type)
is a constraint violation under C89.

OTOH, C99 doesn't require the expressions in an initializer list for a
(non-static) aggregate/union object to be constant expressions. The C99
Foreword mentions "relaxed constraints on aggregate and union
initialization" as a "[m]ajor change[]".


.... Did you think of this?

(For the record, my own interpretation of Alan Curry's suggestion was
bogus, or at least very inexact. I never looked at the "address constant"
paragraphs before, sorry.)

Thanks,
lacos

 

[Ben Bacarisse]

On 07/22/10 01:00 AM, Ben Bacarisse wrote:
On 07/21/10 07:17 PM, Nick Keighley wrote:

int main (void)
{
Tree yggdrasil[] =
{
{"red",&yggdrasil[1],&yggdrasil[2]},
{"blue",&yggdrasil[3],&yggdrasil[4]},
{"black", 0, 0},
{"yellow", 0, 0},
{"green", 0, 0}
};


It's perfectly valid C.

I'd say that it is not. An implementation is permitted to reject the
code which goes against what most people would call perfectly valid C.

ah yes, even with pedantic I only got

D:\bin\net>gcc -W -Wall -pedantic -ansi tree.c
tree.c: In function `main':
tree.c:27: warning: initializer element is not computable at load time
[several times]

That does not tell you if it is or is not valid C!

If you compile for the correct version of C, it is.

Yup. Scratch my last reply. Trying to read to many things at once I
got my versions all mixed. I'd summarise what I think is the case about
this only I am sure I'd make even more confusion.

It's fine in C99.

C89 6.5.7 "Initialization", p4 (in "Constraints"):

"All the expressions in an initializer for an object that has static
storage duration or in an initializer list for an object that has
aggregate or union type shall be constant expressions."

C99 6.7.8 "Initialization", p4 (in "Constraints"):

"All the expressions in an initializer for an object that has static
storage duration shall be constant expressions or string literals."

"&yggdrasil[1]" in the above is not an address constant, because
"yggdrasil"'s storage duration is not static (it's auto). This holds
for both C89 (6.4) and C99 (6.6 p7,9). Consequently, using
"&yggdrasil[1]" in the initializer list for "yggdrasil" (which has
array, ie. aggregate type) is a constraint violation under C89.

OTOH, C99 doesn't require the expressions in an initializer list for a
(non-static) aggregate/union object to be constant expressions. The
C99 Foreword mentions "relaxed constraints on aggregate and union
initialization" as a "[m]ajor change[]".

... Did you think of this?

Yes, but too late. &yggdrasil[1] is not an address constant but that
does not matter in C99 where, as you say, initialisers of auto objects
are not required to be constant expressions.

(For the record, my own interpretation of Alan Curry's suggestion was
bogus, or at least very inexact. I never looked at the "address
constant" paragraphs before, sorry.)

What was bogus (I don't remember anything except that you seemed not to
have see the technique before)? Alan Curry's example was of a static
object so the references to the array members *are* constant
expressions. The example he gave is valid C90 and C99.

 

[Ersek, Laszlo]

Yes, but too late.

Sorry, I made several English language errors in my post; I was very
tired. I meant "Did you mean this?" That is, emphasis on "this", not
"think".

What was bogus (I don't remember anything except that you seemed not to
have see the technique before)? Alan Curry's example was of a static
object so the references to the array members *are* constant
expressions. The example he gave is valid C90 and C99.

Yes, it is. I meant "I interpreted Alan's great example wrongly", *not*
"in my interpretation, Alan's example was bogus".

(a) "my own interpretation of Alan Curry's suggestion was bogus"

(b) "my own interpretation of Alan Curry's suggestion was: bogus!"

I meant (a).

lacos

 

[Ben Bacarisse]

Yes, it is. I meant "I interpreted Alan's great example wrongly",
*not* "in my interpretation, Alan's example was bogus".

Yes, that's what I understood you to mean. I just don't recall any
interpretation you made of it that was wrong. Don't worry about. I
don't need to know and I'll take your word for it -- I was just saying I
don't recall any bogus interpretations from you. Be glad, and lets move
on!

 

[Richard Bos]

Nick Keighley:


I don't know enough to correctly answer in your terms. An example of
what I thoght of is a tree structure that is commonly seen in
literatures on evolution of the diverse biological species.

That doesn't pin your problem down very precisely - have you heard of
ring species?

Richard

 

[David Thompson]

So, let's give an example:
The LISP structure (A (B C) D (E (F G) H)) consists of 4 elements. The
first and third of these are scalars, the second and fourth are lists.
The last element is a list consisting of a scalar, a two-element list,
and then a scalar,

I suppose that it would be possible in C to create a polyvalent and
variable argument function Construct_List to do the same thing that
LISP's CONS function does and the equivalent to <LISP>(CONS Z (A (B C)
D (E (F G) H)) )</LISP> would be

No, CONS isn't remotely like that. It creates (and *returns*) the most
primitive structure, a pair (aka dotted pair), from exactly 2 values.
The LIST function does take variable arguments, and the most direct
way to build that structure would be
(LIST 'A (LIST 'B 'C) 'D (LIST 'E (LIST 'F 'G) 'H))

(In practice you would usually either quote the input, in which case
READ has already built the structure and no function is needed; or
backquote and it expands to something like the LIST calls above.)

<C>
Z = Construct_List ('A', Construct_List ('B', 'C'), 'D',
Construct_List ('E', Construct_List ('F, 'G'), 'H'));
</C>

In C a varargs function can only use numbers and types of arguments
that can be 'predicted' by the callee. In LISP everything (of interest
here) is the same type, so you only need to worry about number. You
will need to either pass a prefix count (a nuisance to write manually)
or a trailing sentinel (easier to write, but easier to accidentally
omit causing chaos). If you do use a sentinel, you can't use NIL,
since that's a perfectly valid value, and in particular list element;
and if you use C NULL for LISP NIL as is pretty natural, you've 'lost'
the most convenient sentinel and need to invent another.